My Project
Loading...
Searching...
No Matches
bigintmat.h
Go to the documentation of this file.
1/****************************************
2* Computer Algebra System SINGULAR *
3****************************************/
4/*
5* ABSTRACT: class bigintmat: matrices of number
6*
7* Matrices are stored as 1-dim c-arrays but interpreted 2-dim as matrices.
8* Both modes of addressing are supported, note however, that the 1-dim
9* addressing starts at 0, the 2-dim at 1.
10*
11* Matrices are meant to represent column modules, thus the default
12* operations are always by column.
13*
14* While basic operations are supported over any ring (coeff), some more
15* advanced ones require more special rings: eg. echelon forms, solving
16* of linear equations is only effective over principal ideal or even
17* Euclidean rings.
18*
19* Be careful with the get/set/view/rawset functions to understand which
20* arguments are copied/ deleted or only assigned.
21*/
22
23#ifndef BIGINTMAT_H
24#define BIGINTMAT_H
25
26#include "coeffs/coeffs.h"
27
28/**
29 * @class bigintmat bigintmat.h <coeffs/bigintmat.h>
30 *
31 * Matrices of numbers
32 *
33 * Matrices are stored as 1-dim c-arrays but interpreted 2-dim as matrices.
34 * Both modes of addressing are supported, note however, that the 1-dim
35 * addressing starts at 0, the 2-dim at 1.
36 *
37 * Matrices are meant to represent column modules, thus the default
38 * operations are always by column.
39 *
40 * While basic operations are supported over any ring (coeff), some more
41 * advanced ones require more special rings: eg. echelon forms, solving
42 * of linear equations is only effective over principal ideal or even
43 * Euclidean rings.
44 *
45 * Be careful with the get/set/view/rawset functions to understand which
46 * arguments are copied/ deleted or only assigned.
47 *
48 * @Note: no reference counting here!
49 */
51{
52 private:
54 number *v;
55 int row;
56 int col;
57 public:
58
60
62
63 /// transpose in place
64 void inpTranspose();
65
66
67 /// constructor: the r times c zero-matrix. Beware that the creation
68 /// of a large zero matrix is expensive in terms of time and memory.
69 bigintmat(int r, int c, const coeffs n): m_coeffs(n), v(NULL), row(r), col(c)
70 {
71 assume (rows() >= 0);
72 assume (cols() >= 0);
73
74 const int l = r*c;
75
76 if (l>0) /*(r>0) && (c>0) */
77 {
78 v = (number *)omAlloc(sizeof(number)*l);
79
80 assume (basecoeffs() != NULL);
81 for (int i = l - 1; i>=0; i--)
82 {
83 v[i] = n_Init(0, basecoeffs());
84 }
85 }
86 }
87
88 /// copy constructor
90 {
91 const int l = row*col;
92
93 if (l > 0)
94 {
95 assume (rows() > 0);
96 assume (cols() > 0);
97
98 assume (m->v != NULL);
99
100 v = (number *)omAlloc(sizeof(number)*row*col);
101
102 assume (basecoeffs() != NULL);
103
104 for (int i = l-1; i>=0; i--)
105 {
106 v[i] = n_Copy((*m)[i], basecoeffs());
107 }
108 }
109 }
110 /// dubious: 1-dim access to 2-dim array. Entries are read row by row.
111 inline number& operator[](int i)
112 {
113#ifndef SING_NDEBUG
114 if((i<0)||(i>=row*col))
115 {
116 Werror("wrong bigintmat index:%d\n",i);
117 }
118 assume ( !((i<0)||(i>=row*col)) );
119#endif
120 return v[i]; // Hier sollte imho kein nlCopy rein...
121 }
122 inline const number& operator[](int i) const
123 {
124#ifndef SING_NDEBUG
125 if((i<0)||(i>=row*col))
126 {
127 Werror("wrong bigintmat index:%d\n",i);
128 }
129 assume ( !((i<0)||(i>=row*col)) );
130#endif
131 return v[i];
132 }
133#define BIMATELEM(M,I,J) (M)[(I-1)*(M).cols()+J-1]
134
135 /// UEberladener *=-Operator (fuer int und bigint)
136 /// Frage hier: *= verwenden oder lieber = und * einzeln?
137 /// (coeffs in Singular are always commutative)
138 void operator*=(int intop);
139
140 /// inplace version of skalar mult. CHANGES input.
141 void inpMult(number bintop, const coeffs C = NULL);
142
143 inline int length() { return col*row; }
144 inline int cols() const { return col; }
145 inline int rows() const { return row; }
146 inline coeffs basecoeffs() const { return m_coeffs; }
147
148 /// canonical destructor.
150 {
151 if (v!=NULL)
152 {
153 for (int i=row*col-1;i>=0; i--) { n_Delete(&(v[i]), basecoeffs()); }
154 omFreeSize((ADDRESS)v, sizeof(number)*row*col);
155 v=NULL;
156 }
157 }
158
159 /// helper function to map from 2-dim coordinates, starting by 1 to
160 /// 1-dim coordinate, starting by 0
161 int index(int r, int c) const
162 {
163 assume (rows() >= 0 && cols() >= 0);
164
165 assume (r > 0 && c > 0);
166 assume (r <= rows() && c <= cols());
167
168 const int index = ((r-1)*cols() + (c-1));
169
170 assume (index >= 0 && index < rows() * cols());
171 return index;
172 }
173
174 /// get a copy of an entry. NOTE: starts at [1,1]
175 number get(int i, int j) const;
176 /// view an entry an entry. NOTE: starts at [1,1]
177 //do NOT delete.
178 number view(int i, int j) const;
179
180 /// get a copy of an entry. NOTE: starts at [0]
181 number get(int i) const;
182 /// view an entry. NOTE: starts at [0]
183 number view(int i) const;
184
185 /// replace an entry with a copy (delete old + copy new!).
186 /// NOTE: starts at [1,1]
187 void set(int i, int j, number n, const coeffs C = NULL);
188
189 /// replace an entry with a copy (delete old + copy new!).
190 /// NOTE: starts at [0]
191 void set(int i, number n, const coeffs C = NULL);
192
193
194 /// replace an entry with the given number n (only delete old).
195 /// NOTE: starts at [0]. Should be named set_transfer
196 inline void rawset(int i, number n, const coeffs C = NULL)
197 {
198 assume (C == NULL || C == basecoeffs());
199 assume (i >= 0);
200 const int l = rows() * cols();
201 assume (i<l);
202
203 if (i < l)
204 {
205 n_Delete(&(v[i]), basecoeffs()); v[i] = n;
206 }
207#ifndef SING_NDEBUG
208 else
209 {
210 Werror("wrong bigintmat index:%d\n",i);
211 }
212#endif
213 }
214
215 /// as above, but the 2-dim version
216 inline void rawset(int i, int j, number n, const coeffs C = NULL)
217 {
218 rawset( index(i,j), n, C);
219 }
220
221 ///IO: String returns a singular string containing the matrix, needs
222 /// freeing afterwards
223 char * String();
224 ///IO: writes the matrix into the current internal string buffer which
225 /// must be started/ allocated before (e.g. @ref StringSetS)
226 void Write();
227 ///IO: simply prints the matrix to the current output (screen?)
228 void Print();
229
230 /**
231 * Returns a string as it would have been printed in the interpreter.
232 * Used e.g. in print functions of various blackbox types.
233 */
234 char * StringAsPrinted();
235 void pprint(int maxwid);
236 int compare(const bigintmat* op) const;
237 int * getwid(int maxwid);
238
239
240 // Funktionen von Kira, Jan, Marco
241 // !WICHTIG: Überall, wo eine number übergeben wird, und damit gearbeitet wird, die coeffs mitübergeben und erst
242 // überprüfen, ob diese mit basecoeffs übereinstimmen. Falls nein: Breche ab!
243
244 /// swap columns i and j
245 void swap(int i, int j);
246
247 /// swap rows i and j
248 void swaprow(int i, int j);
249
250 ///find index of 1st non-zero entry in row i
251 int findnonzero(int i);
252
253 ///find index of 1st non-zero entry in column j
254 int findcolnonzero(int j);
255
256 ///copies the j-th column into the matrix a - which needs to be pre-allocated with the correct size.
257 void getcol(int j, bigintmat *a);
258
259 ///copies the no-columns staring by j (so j...j+no-1) into the pre-allocated a
260 void getColRange(int j, int no, bigintmat *a);
261
262 void getrow(int i, bigintmat *a); ///< Schreibt i-te Zeile in Vektor (Matrix) a
263 void setcol(int j, bigintmat *m); ///< Setzt j-te Spalte gleich übergebenem Vektor (Matrix) m
264 void setrow(int i, bigintmat *m); ///< Setzt i-te Zeile gleich übergebenem Vektor (Matrix) m
265
266 ///horizontally join the matrices, m <- m|a
267 void appendCol (bigintmat *a);
268
269 ///append i zero-columns to the matrix
270 void extendCols (int i);
271
272 bool add(bigintmat *b); ///< Addiert zur Matrix die Matrix b dazu. Return false => an error occurred
273 bool sub(bigintmat *b); ///< Subtrahiert ...
274 bool skalmult(number b, coeffs c); ///< Multipliziert zur Matrix den Skalar b hinzu
275 bool addcol(int i, int j, number a, coeffs c); ///< addiert a-faches der j-ten Spalte zur i-ten dazu
276 bool addrow(int i, int j, number a, coeffs c); ///< ... Zeile ...
277 void colskalmult(int i, number a, coeffs c); ///< Multipliziert zur i-ten Spalte den Skalar a hinzu
278 void rowskalmult(int i, number a, coeffs c); ///< ... Zeile ...
279 void coltransform(int i, int j, number a, number b, number c, number d); ///< transforms cols (i,j) using the 2x2 matrix ((a,b)(c,d)) (hopefully)
280 void concatrow(bigintmat *a, bigintmat *b); ///< Fügt zwei Matrixen untereinander/nebeneinander in gegebene Matrix ein, bzw spaltet gegebenen Matrix auf
281 void concatcol(bigintmat *a, bigintmat *b);
282 void splitrow(bigintmat *a, bigintmat *b); ///< Speichert in Matrix a den oberen, in b den unteren Teil der Matrix, vorausgesetzt die Dimensionen stimmen überein
283 void splitcol(bigintmat *a, bigintmat *b); ///< ... linken ... rechten ...
284 void splitcol(bigintmat *a, int i); ///< Speichert die ersten i Spalten als Teilmatrix in a
285 void splitrow(bigintmat *a, int i); ///< ... Zeilen ...
286 bool copy(bigintmat *b); ///< Kopiert Einträge von b auf Bigintmat
287 void copySubmatInto(bigintmat *, int sr, int sc, int nr, int nc, int tr, int tc);
288 void one(); ///< Macht Matrix (Falls quadratisch) zu Einheitsmatrix
289 int isOne(); ///< is matrix is identity
290 void zero(); ///< Setzt alle Einträge auf 0
291 int isZero();
292 int colIsZero(int i);
293 bigintmat *elim(int i, int j); ///< Liefert Streichungsmatrix (i-te Zeile und j-te Spalte gestrichen) zurück
294 number pseudoinv(bigintmat *a); ///< Speichert in Matrix a die Pseudoinverse, liefert den Nenner zurück
295 number trace(); ///< the trace ....
296 number det(); ///< det (via LaPlace in general, hnf for euc. rings)
297 number hnfdet(); ///< det via HNF
298 /// Primzahlen als long long int, müssen noch in number umgewandelt werden?
299 void hnf(); ///< transforms INPLACE to HNF
300 void howell(); ///<dito, but Howell form (only different for zero-divsors)
301 void swapMatrix(bigintmat * a);
302 bigintmat * modhnf(number p, coeffs c); ///< computes HNF(this | p*I)
304 void skaldiv(number b); ///< Macht Ganzzahldivision aller Matrixeinträge mit b
305 void colskaldiv(int j, number b); ///< Macht Ganzzahldivision aller j-ten Spalteneinträge mit b
306 void mod(number p); ///< Reduziert komplette Matrix modulo p
307 bigintmat* inpmod(number p, coeffs c); ///< Liefert Kopie der Matrix zurück, allerdings im Ring Z modulo p
308 number content(); ///<the content, the gcd of all entries. Only makes sense for Euclidean rings (or possibly constructive PIR)
309 void simplifyContentDen(number *den); ///< ensures that Gcd(den, content)=1
310 ///< enden hier wieder
311};
312
313bool operator==(const bigintmat & lhr, const bigintmat & rhr);
314bool operator!=(const bigintmat & lhr, const bigintmat & rhr);
315
316/// Matrix-Add/-Sub/-Mult so oder mit operator+/-/* ?
317/// @Note: NULL as a result means an error (non-compatible matrices?)
319bigintmat * bimAdd(bigintmat * a, long b);
321bigintmat * bimSub(bigintmat * a, long b);
323bigintmat * bimMult(bigintmat * a, long b);
324bigintmat * bimMult(bigintmat * a, number b, const coeffs cf);
325
326///same as copy constructor - apart from it being able to accept NULL as input
327bigintmat * bimCopy(const bigintmat * b);
328
329class intvec;
331bigintmat * iv2bim(intvec * b, const coeffs C);
332
333// Wieder von Kira, Jan, Marco
334bigintmat * bimChangeCoeff(bigintmat *a, coeffs cnew); ///< Liefert Kopier von Matrix a zurück, mit coeffs cnew statt den ursprünglichen
335void bimMult(bigintmat *a, bigintmat *b, bigintmat *c); ///< Multipliziert Matrix a und b und speichert Ergebnis in c
336
337///solve Ax=b*d. x needs to be pre-allocated to the same number of columns as b.
338/// the minimal denominator d is returned. Currently available for Z, Q and Z/nZ (and possibly for all fields: d=1 there)
339///Beware that the internal functions can find the kernel as well - but the interface is lacking.
340number solveAx(bigintmat *A, bigintmat *b, bigintmat *x); // solves Ax=b*d for a minimal denominator d. if x needs to have as many cols as b
341
342///a basis for the nullspace of a mod p: only used internally in Round2.
343/// Don't use it.
344int kernbase (bigintmat *a, bigintmat *c, number p, coeffs q);
346// enden wieder
348
349#endif /* #ifndef BIGINTMAT_H */
void * ADDRESS
Definition auxiliary.h:120
#define swap(_i, _j)
int kernbase(bigintmat *a, bigintmat *c, number p, coeffs q)
a basis for the nullspace of a mod p: only used internally in Round2. Don't use it.
number solveAx(bigintmat *A, bigintmat *b, bigintmat *x)
solve Ax=b*d. x needs to be pre-allocated to the same number of columns as b. the minimal denominator...
bigintmat * bimChangeCoeff(bigintmat *a, coeffs cnew)
Liefert Kopier von Matrix a zurück, mit coeffs cnew statt den ursprünglichen.
bigintmat * bimCopy(const bigintmat *b)
same as copy constructor - apart from it being able to accept NULL as input
Definition bigintmat.cc:403
void diagonalForm(bigintmat *a, bigintmat **b, bigintmat **c)
bool nCoeffs_are_equal(coeffs r, coeffs s)
intvec * bim2iv(bigintmat *b)
Definition bigintmat.cc:339
bigintmat * bimMult(bigintmat *a, bigintmat *b)
Definition bigintmat.cc:253
bigintmat * bimSub(bigintmat *a, bigintmat *b)
Definition bigintmat.cc:216
bigintmat * iv2bim(intvec *b, const coeffs C)
Definition bigintmat.cc:347
bool operator!=(const bigintmat &lhr, const bigintmat &rhr)
Definition bigintmat.cc:174
bigintmat * bimAdd(bigintmat *a, bigintmat *b)
Matrix-Add/-Sub/-Mult so oder mit operator+/-/* ? @Note: NULL as a result means an error (non-compati...
Definition bigintmat.cc:180
bool operator==(const bigintmat &lhr, const bigintmat &rhr)
Definition bigintmat.cc:157
CanonicalForm den(const CanonicalForm &f)
int l
Definition cfEzgcd.cc:100
int m
Definition cfEzgcd.cc:128
int i
Definition cfEzgcd.cc:132
Variable x
Definition cfModGcd.cc:4090
int p
Definition cfModGcd.cc:4086
CanonicalForm cf
Definition cfModGcd.cc:4091
CanonicalForm b
Definition cfModGcd.cc:4111
Matrices of numbers.
Definition bigintmat.h:51
bigintmat * modgauss(number p, coeffs c)
void Print()
IO: simply prints the matrix to the current output (screen?)
Definition bigintmat.cc:437
~bigintmat()
canonical destructor.
Definition bigintmat.h:149
void colskaldiv(int j, number b)
Macht Ganzzahldivision aller j-ten Spalteneinträge mit b.
int length()
Definition bigintmat.h:143
number det()
det (via LaPlace in general, hnf for euc. rings)
void splitrow(bigintmat *a, bigintmat *b)
Speichert in Matrix a den oberen, in b den unteren Teil der Matrix, vorausgesetzt die Dimensionen sti...
number & operator[](int i)
dubious: 1-dim access to 2-dim array. Entries are read row by row.
Definition bigintmat.h:111
coeffs m_coeffs
Definition bigintmat.h:53
int isOne()
is matrix is identity
void zero()
Setzt alle Einträge auf 0.
void appendCol(bigintmat *a)
horizontally join the matrices, m <- m|a
number trace()
the trace ....
bool addrow(int i, int j, number a, coeffs c)
... Zeile ...
Definition bigintmat.cc:978
void coltransform(int i, int j, number a, number b, number c, number d)
transforms cols (i,j) using the 2x2 matrix ((a,b)(c,d)) (hopefully)
bool addcol(int i, int j, number a, coeffs c)
addiert a-faches der j-ten Spalte zur i-ten dazu
Definition bigintmat.cc:954
number * v
Definition bigintmat.h:54
void hnf()
transforms INPLACE to HNF
char * StringAsPrinted()
Returns a string as it would have been printed in the interpreter.
Definition bigintmat.cc:445
void swapMatrix(bigintmat *a)
int cols() const
Definition bigintmat.h:144
int isZero()
number hnfdet()
det via HNF Primzahlen als long long int, müssen noch in number umgewandelt werden?
int findnonzero(int i)
find index of 1st non-zero entry in row i
Definition bigintmat.cc:718
bigintmat * modhnf(number p, coeffs c)
computes HNF(this | p*I)
void setcol(int j, bigintmat *m)
Setzt j-te Spalte gleich übergebenem Vektor (Matrix) m.
Definition bigintmat.cc:821
int * getwid(int maxwid)
Definition bigintmat.cc:574
void inpMult(number bintop, const coeffs C=NULL)
inplace version of skalar mult. CHANGES input.
Definition bigintmat.cc:143
bigintmat * transpose()
Definition bigintmat.cc:35
void setrow(int i, bigintmat *m)
Setzt i-te Zeile gleich übergebenem Vektor (Matrix) m.
Definition bigintmat.cc:855
void Write()
IO: writes the matrix into the current internal string buffer which must be started/ allocated before...
Definition bigintmat.cc:411
void rowskalmult(int i, number a, coeffs c)
... Zeile ...
bool skalmult(number b, coeffs c)
Multipliziert zur Matrix den Skalar b hinzu.
Definition bigintmat.cc:933
void simplifyContentDen(number *den)
ensures that Gcd(den, content)=1 enden hier wieder
void extendCols(int i)
append i zero-columns to the matrix
void splitcol(bigintmat *a, bigintmat *b)
... linken ... rechten ...
number content()
the content, the gcd of all entries. Only makes sense for Euclidean rings (or possibly constructive P...
void skaldiv(number b)
Macht Ganzzahldivision aller Matrixeinträge mit b.
void colskalmult(int i, number a, coeffs c)
Multipliziert zur i-ten Spalte den Skalar a hinzu.
int colIsZero(int i)
bool copy(bigintmat *b)
Kopiert Einträge von b auf Bigintmat.
int index(int r, int c) const
helper function to map from 2-dim coordinates, starting by 1 to 1-dim coordinate, starting by 0
Definition bigintmat.h:161
void getcol(int j, bigintmat *a)
copies the j-th column into the matrix a - which needs to be pre-allocated with the correct size.
Definition bigintmat.cc:742
number pseudoinv(bigintmat *a)
Speichert in Matrix a die Pseudoinverse, liefert den Nenner zurück.
bigintmat(const bigintmat *m)
copy constructor
Definition bigintmat.h:89
bigintmat * inpmod(number p, coeffs c)
Liefert Kopie der Matrix zurück, allerdings im Ring Z modulo p.
int rows() const
Definition bigintmat.h:145
number get(int i, int j) const
get a copy of an entry. NOTE: starts at [1,1]
Definition bigintmat.cc:117
void pprint(int maxwid)
Definition bigintmat.cc:604
void getColRange(int j, int no, bigintmat *a)
copies the no-columns staring by j (so j...j+no-1) into the pre-allocated a
Definition bigintmat.cc:773
void rawset(int i, int j, number n, const coeffs C=NULL)
as above, but the 2-dim version
Definition bigintmat.h:216
void concatcol(bigintmat *a, bigintmat *b)
int findcolnonzero(int j)
find index of 1st non-zero entry in column j
Definition bigintmat.cc:730
void copySubmatInto(bigintmat *, int sr, int sc, int nr, int nc, int tr, int tc)
copy the submatrix of b, staring at (a,b) having n rows, m cols into the given matrix at pos....
number view(int i, int j) const
view an entry an entry. NOTE: starts at [1,1]
Definition bigintmat.cc:125
void inpTranspose()
transpose in place
Definition bigintmat.cc:48
void one()
Macht Matrix (Falls quadratisch) zu Einheitsmatrix.
void howell()
dito, but Howell form (only different for zero-divsors)
void rawset(int i, number n, const coeffs C=NULL)
replace an entry with the given number n (only delete old). NOTE: starts at [0]. Should be named set_...
Definition bigintmat.h:196
bigintmat(int r, int c, const coeffs n)
constructor: the r times c zero-matrix. Beware that the creation of a large zero matrix is expensive ...
Definition bigintmat.h:69
void operator*=(int intop)
UEberladener *=-Operator (fuer int und bigint) Frage hier: *= verwenden oder lieber = und * einzeln?...
Definition bigintmat.cc:134
const number & operator[](int i) const
Definition bigintmat.h:122
coeffs basecoeffs() const
Definition bigintmat.h:146
void getrow(int i, bigintmat *a)
Schreibt i-te Zeile in Vektor (Matrix) a.
Definition bigintmat.cc:786
void concatrow(bigintmat *a, bigintmat *b)
Fügt zwei Matrixen untereinander/nebeneinander in gegebene Matrix ein, bzw spaltet gegebenen Matrix a...
void set(int i, int j, number n, const coeffs C=NULL)
replace an entry with a copy (delete old + copy new!). NOTE: starts at [1,1]
Definition bigintmat.cc:93
bigintmat * elim(int i, int j)
Liefert Streichungsmatrix (i-te Zeile und j-te Spalte gestrichen) zurück.
int compare(const bigintmat *op) const
Definition bigintmat.cc:360
bool sub(bigintmat *b)
Subtrahiert ...
Definition bigintmat.cc:911
char * String()
IO: String returns a singular string containing the matrix, needs freeing afterwards.
Definition bigintmat.cc:430
void swaprow(int i, int j)
swap rows i and j
Definition bigintmat.cc:699
void mod(number p)
Reduziert komplette Matrix modulo p.
Coefficient rings, fields and other domains suitable for Singular polynomials.
static FORCE_INLINE number n_Copy(number n, const coeffs r)
return a copy of 'n'
Definition coeffs.h:455
static FORCE_INLINE void n_Delete(number *p, const coeffs r)
delete 'p'
Definition coeffs.h:459
static FORCE_INLINE number n_Init(long i, const coeffs r)
a number representing i in the given coeff field/ring r
Definition coeffs.h:539
const CanonicalForm int s
Definition facAbsFact.cc:51
int j
Definition facHensel.cc:110
STATIC_VAR unsigned add[]
Definition misc_ip.cc:108
#define assume(x)
Definition mod2.h:389
The main handler for Singular numbers which are suitable for Singular polynomials.
#define omFreeSize(addr, size)
#define omAlloc(size)
#define NULL
Definition omList.c:12
void Werror(const char *fmt,...)
Definition reporter.cc:189
#define A
Definition sirandom.c:24