# source:git/libpolys/coeffs/bigintmat.h

spielwiese
Last change on this file was 86de52, checked in by Hans Schoenemann <hannes@…>, 9 months ago
bigintmat: int->long
• Property mode set to `100644`
File size: 12.7 KB
Line
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* adressing 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 * adressing 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 */
50class bigintmat
51{
52  private:
53    coeffs m_coeffs;
54    number *v;
55    int row;
56    int col;
57  public:
58
59    bigintmat(): m_coeffs(NULL), v(NULL), row(1), col(0){}
60
61    bigintmat * transpose();
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
89    bigintmat(const bigintmat *m): m_coeffs(m->basecoeffs()), v(NULL), row(m->rows()), col(m->cols())
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    }
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    /// problem: what about non-commuting rings. Is this from left or right?
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.
149    ~bigintmat()
150    {
151      if (v!=NULL)
152      {
153        for (int i=row*col-1;i>=0; i--) { n_Delete(&(v[i]), basecoeffs()); }
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    #ifdef HAVE_RINGS
303    bigintmat * modhnf(number p, coeffs c); ///< computes HNF(this | p*I)
304    #endif
305    bigintmat * modgauss(number p, coeffs c);
306    void skaldiv(number b); ///< Macht Ganzzahldivision aller MatrixeintrÃ€ge mit b
307    void colskaldiv(int j, number b); ///< Macht Ganzzahldivision aller j-ten SpalteneintrÃ€ge mit b
308    void mod(number p); ///< Reduziert komplette Matrix modulo p
309    bigintmat* inpmod(number p, coeffs c); ///< Liefert Kopie der Matrix zurÃŒck, allerdings im Ring Z modulo p
310    number content(); ///<the content, the gcd of all entries. Only makes sense for Euclidean rings (or possibly constructive PIR)
311    void simplifyContentDen(number *den); ///< ensures that Gcd(den, content)=1
312    ///< enden hier wieder
313};
314
315bool operator==(const bigintmat & lhr, const bigintmat & rhr);
316bool operator!=(const bigintmat & lhr, const bigintmat & rhr);
317
318/// Matrix-Add/-Sub/-Mult so oder mit operator+/-/* ?
319/// @Note: NULL as a result means an error (non-compatible matrices?)
320bigintmat * bimAdd(bigintmat * a, bigintmat * b);
321bigintmat * bimAdd(bigintmat * a, long b);
322bigintmat * bimSub(bigintmat * a, bigintmat * b);
323bigintmat * bimSub(bigintmat * a, long b);
324bigintmat * bimMult(bigintmat * a, bigintmat * b);
325bigintmat * bimMult(bigintmat * a, long b);
326bigintmat * bimMult(bigintmat * a, number b, const coeffs cf);
327
328///same as copy constructor - apart from it being able to accept NULL as input
329bigintmat * bimCopy(const bigintmat * b);
330
331class intvec;
332intvec * bim2iv(bigintmat * b);
333bigintmat * iv2bim(intvec * b, const coeffs C);
334
335// Wieder von Kira, Jan, Marco
336bigintmat * bimChangeCoeff(bigintmat *a, coeffs cnew); ///< Liefert Kopier von Matrix a zurÃŒck, mit coeffs cnew statt den ursprÃŒnglichen
337void bimMult(bigintmat *a, bigintmat *b, bigintmat *c); ///< Multipliziert Matrix a und b und speichert Ergebnis in c
338
339///solve Ax=b*d. x needs to be pre-allocated to the same number of columns as b.
340/// the minimal denominator d is returned. Currently available for Z, Q and Z/nZ (and possibly for all fields: d=1 there)
341///Beware that the internal functions can find the kernel as well - but the interface is lacking.
342number 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
343
344///a basis for the nullspace of a mod p: only used internally in Round2.
345/// Don't use it.
346int kernbase (bigintmat *a, bigintmat *c, number p, coeffs q);
347bool nCoeffs_are_equal(coeffs r, coeffs s);
348// enden wieder
349void diagonalForm(bigintmat *a, bigintmat **b, bigintmat **c);
350
351#endif /* #ifndef BIGINTMAT_H */
Note: See TracBrowser for help on using the repository browser.