1 | |
---|
2 | /**************************************************************************\ |
---|
3 | |
---|
4 | MODULE: mat_GF2 |
---|
5 | |
---|
6 | SUMMARY: |
---|
7 | |
---|
8 | The class mat_GF2 implements matrices over GF(2). |
---|
9 | Each row is a vec_GF2 of the same length. |
---|
10 | |
---|
11 | For a mat_GF2 M, one may access row i of M as M[i], |
---|
12 | indexing from 0, or as M(i), indexing from 1. |
---|
13 | |
---|
14 | Individual elements of M may be accessed as M[i][j], |
---|
15 | indexing from 0, or M(i, j), indexing from 1. |
---|
16 | Some restrictions apply (see vec_GF2.txt for details). |
---|
17 | Alternatively, one may use methods get and put. |
---|
18 | |
---|
19 | \**************************************************************************/ |
---|
20 | |
---|
21 | |
---|
22 | #include <NTL/vec_vec_GF2.h> |
---|
23 | |
---|
24 | class mat_GF2 { |
---|
25 | public: |
---|
26 | |
---|
27 | mat_GF2(); // initially 0 x 0 |
---|
28 | |
---|
29 | mat_GF2(const mat_GF2& a); |
---|
30 | mat_GF2& operator=(const mat_GF2& a); |
---|
31 | ~mat_GF2(); |
---|
32 | |
---|
33 | mat_GF2(INIT_SIZE_TYPE, long n, long m); |
---|
34 | // mat_T(INIT_SIZE, n, m) initializes an n x m matrix, |
---|
35 | // clearing all bits. |
---|
36 | |
---|
37 | |
---|
38 | |
---|
39 | void SetDims(long n, long m); |
---|
40 | // M.SetDims(n, m) makes M have dimension n x m. If the number of |
---|
41 | // columns (m) changes, previous storage is freed, and space for M |
---|
42 | // is reallocated and initialized; otherwise, more rows are |
---|
43 | // allocated as necessary (when number of rows increases), |
---|
44 | // excess rows are retained (when number of rows decreases), |
---|
45 | // and--importantly--the contents do not change. |
---|
46 | |
---|
47 | long NumRows() const; |
---|
48 | // M.NumRows() returns the number of rows of M |
---|
49 | |
---|
50 | long NumCols() const; |
---|
51 | // M.NumCols() returns the number of columns of M |
---|
52 | |
---|
53 | vec_GF2& operator[](long i); |
---|
54 | const vec_GF2& operator[](long i) const; |
---|
55 | // access row i, initial index 0. Any attempt to change the length |
---|
56 | // of this row will raise an error. |
---|
57 | |
---|
58 | |
---|
59 | vec_GF2& operator()(long i); |
---|
60 | const vec_GF2& operator()(long i) const; |
---|
61 | // access row i, initial index 1. Any attempt to change the length |
---|
62 | // of this row will raise an error. |
---|
63 | |
---|
64 | |
---|
65 | GF2 get(long i, long j) const; |
---|
66 | // returns entry (i, j), indexing from 0 |
---|
67 | |
---|
68 | void put(long i, long j, GF2 a); |
---|
69 | void put(long i, long j, long a); |
---|
70 | // set entry (i, j) to a, indexing from 0 |
---|
71 | |
---|
72 | // Here are the subscripting operations defined using |
---|
73 | // the "helper" classes subscript_GF2 and const_subscript_GF2. |
---|
74 | |
---|
75 | subscript_GF2 operator()(long i, long j); |
---|
76 | |
---|
77 | const_subscript_GF2 operator()(long i, long j) const; |
---|
78 | |
---|
79 | long position(const vec_GF2& a) const; |
---|
80 | // returns index of a in matrix, or -1 if not present; |
---|
81 | // equivalent to rep(*this).position(a); |
---|
82 | |
---|
83 | long position1(const vec_GF2& a) const; |
---|
84 | // returns index of a in matrix, or -1 if not present; |
---|
85 | // equivalent to rep(*this).position1(a); |
---|
86 | |
---|
87 | void kill(); // free space and make 0 x 0. |
---|
88 | |
---|
89 | }; |
---|
90 | |
---|
91 | const vec_vec_GF2& rep(const mat_GF2& a); |
---|
92 | // read-only access to underlying representation. |
---|
93 | |
---|
94 | void swap(mat_GF2& X, mat_GF2& Y); |
---|
95 | // swap X and Y (fast pointer swap) |
---|
96 | |
---|
97 | void conv(mat_GF2& X, const vec_vec_GF2& A); |
---|
98 | mat_GF2 to_mat_GF2(const vec_vec_GF2& A); |
---|
99 | // convert a vector of vec_GF2's to a matrix |
---|
100 | |
---|
101 | // equality testing: |
---|
102 | |
---|
103 | long operator==(const mat_GF2& A, const mat_GF2& B); |
---|
104 | long operator!=(const mat_GF2& A, const mat_GF2& B); |
---|
105 | |
---|
106 | // Input/Output: |
---|
107 | // input format is the same as for a vector of vec_GF2s. |
---|
108 | |
---|
109 | istream& operator>>(istream&, mat_GF2&); |
---|
110 | ostream& operator<<(ostream&, const mat_GF2&); |
---|
111 | |
---|
112 | |
---|
113 | |
---|
114 | |
---|
115 | // procedural arithmetic routines: |
---|
116 | |
---|
117 | void add(mat_GF2& X, const mat_GF2& A, const mat_GF2& B); |
---|
118 | // X = A + B |
---|
119 | |
---|
120 | void sub(mat_GF2& X, const mat_GF2& A, const mat_GF2& B); |
---|
121 | // X = A - B = A + B |
---|
122 | |
---|
123 | void negate(mat_GF2& X, const mat_GF2& A); |
---|
124 | // X = -A = A |
---|
125 | |
---|
126 | void mul(mat_GF2& X, const mat_GF2& A, const mat_GF2& B); |
---|
127 | // X = A * B |
---|
128 | |
---|
129 | void mul(vec_GF2& x, const mat_GF2& A, const vec_GF2& b); |
---|
130 | // x = A * b |
---|
131 | |
---|
132 | void mul(vec_GF2& x, const vec_GF2& a, const mat_GF2& B); |
---|
133 | // x = a * B |
---|
134 | |
---|
135 | |
---|
136 | void mul(mat_GF2& X, const mat_GF2& A, GF2 b); |
---|
137 | void mul(mat_GF2& X, const mat_GF2& A, long b); |
---|
138 | // X = A * b |
---|
139 | |
---|
140 | void mul(mat_GF2& X, GF2 a, const mat_GF2& B); |
---|
141 | void mul(mat_GF2& X, long a, const mat_GF2& B); |
---|
142 | // X = a * B |
---|
143 | |
---|
144 | void determinant(GF2& d, const mat_GF2& A); |
---|
145 | GF2 determinant(const mat_GF2& A); |
---|
146 | // d = determinant of A |
---|
147 | |
---|
148 | void transpose(mat_GF2& X, const mat_GF2& A); |
---|
149 | mat_GF2 transpose(const mat_GF2& A); |
---|
150 | // X = transpose of A |
---|
151 | |
---|
152 | void solve(GF2& d, vec_GF2& x, const mat_GF2& A, const vec_GF2& b); |
---|
153 | // A is an n x n matrix, b is a length n vector. Computes d = det(A). |
---|
154 | // If d != 0, solves x*A = b. |
---|
155 | |
---|
156 | void inv(GF2& d, mat_GF2& X, const mat_GF2& A); |
---|
157 | // A is an n x n matrix. Computes d = det(A). If d != 0, |
---|
158 | // computes X = A^{-1}. |
---|
159 | |
---|
160 | void sqr(mat_GF2& X, const mat_GF2& A); |
---|
161 | mat_GF2 sqr(const mat_GF2& A); |
---|
162 | // X = A*A |
---|
163 | |
---|
164 | void inv(mat_GF2& X, const mat_GF2& A); |
---|
165 | mat_GF2 inv(const mat_GF2& A); |
---|
166 | // X = A^{-1}; error is raised if A is singular |
---|
167 | |
---|
168 | void power(mat_GF2& X, const mat_GF2& A, const ZZ& e); |
---|
169 | mat_GF2 power(const mat_GF2& A, const ZZ& e); |
---|
170 | |
---|
171 | void power(mat_GF2& X, const mat_GF2& A, long e); |
---|
172 | mat_GF2 power(const mat_GF2& A, long e); |
---|
173 | // X = A^e; e may be negative (in which case A must be nonsingular). |
---|
174 | |
---|
175 | |
---|
176 | void ident(mat_GF2& X, long n); |
---|
177 | mat_GF2 ident_mat_GF2(long n); |
---|
178 | // X = n x n identity matrix |
---|
179 | |
---|
180 | long IsIdent(const mat_GF2& A, long n); |
---|
181 | // test if A is n x n identity matrix |
---|
182 | |
---|
183 | |
---|
184 | void diag(mat_GF2& X, long n, GF2 d); |
---|
185 | mat_GF2 diag(long n, GF2 d); |
---|
186 | // X = n x n diagonal matrix with diagonal element d |
---|
187 | |
---|
188 | long IsDiag(const mat_GF2& A, long n, long d); |
---|
189 | // test if X is an n x n diagonal matrix with diagonal element (d mod 2) |
---|
190 | |
---|
191 | |
---|
192 | long gauss(mat_GF2& M); |
---|
193 | long gauss(mat_GF2& M, long w); |
---|
194 | // Performs unitary row operations so as to bring M into row echelon |
---|
195 | // form. If the optional argument w is supplied, stops when first w |
---|
196 | // columns are in echelon form. The return value is the rank (or the |
---|
197 | // rank of the first w columns). |
---|
198 | |
---|
199 | void image(mat_GF2& X, const mat_GF2& A); |
---|
200 | // The rows of X are computed as basis of A's row space. X is is row |
---|
201 | // echelon form |
---|
202 | |
---|
203 | |
---|
204 | void kernel(mat_GF2& X, const mat_GF2& A); |
---|
205 | // Computes a basis for the kernel of the map x -> x*A. where x is a |
---|
206 | // row vector. |
---|
207 | |
---|
208 | // miscellaneous: |
---|
209 | |
---|
210 | |
---|
211 | void clear(mat_GF2& X); |
---|
212 | // X = 0 (dimension unchanged) |
---|
213 | |
---|
214 | long IsZero(const mat_GF2& A); |
---|
215 | // test if A is the zero matrix (any dimension) |
---|
216 | |
---|
217 | |
---|
218 | // arithmetic operator notation: |
---|
219 | |
---|
220 | mat_GF2 operator+(const mat_GF2& a, const mat_GF2& b); |
---|
221 | mat_GF2 operator-(const mat_GF2& a, const mat_GF2& b); |
---|
222 | mat_GF2 operator*(const mat_GF2& a, const mat_GF2& b); |
---|
223 | |
---|
224 | mat_GF2 operator-(const mat_GF2& a); |
---|
225 | |
---|
226 | |
---|
227 | // matrix/scalar multiplication: |
---|
228 | |
---|
229 | mat_GF2 operator*(const mat_GF2& a, GF2 b); |
---|
230 | mat_GF2 operator*(const mat_GF2& a, long b); |
---|
231 | |
---|
232 | mat_GF2 operator*(GF2 a, const mat_GF2& b); |
---|
233 | mat_GF2 operator*(long a, const mat_GF2& b); |
---|
234 | |
---|
235 | // matrix/vector multiplication: |
---|
236 | |
---|
237 | vec_GF2 operator*(const mat_GF2& a, const vec_GF2& b); |
---|
238 | |
---|
239 | vec_GF2 operator*(const vec_GF2& a, const mat_GF2& b); |
---|
240 | |
---|
241 | |
---|
242 | // assignment operator notation: |
---|
243 | |
---|
244 | mat_GF2& operator+=(mat_GF2& x, const mat_GF2& a); |
---|
245 | mat_GF2& operator-=(mat_GF2& x, const mat_GF2& a); |
---|
246 | mat_GF2& operator*=(mat_GF2& x, const mat_GF2& a); |
---|
247 | |
---|
248 | mat_GF2& operator*=(mat_GF2& x, GF2 a); |
---|
249 | mat_GF2& operator*=(mat_GF2& x, long a); |
---|
250 | |
---|
251 | vec_GF2& operator*=(vec_GF2& x, const mat_GF2& a); |
---|
252 | |
---|
253 | |
---|