Macros | Functions
bigintmat.cc File Reference
#include <misc/auxiliary.h>
#include "bigintmat.h"
#include <misc/intvec.h>
#include "rmodulon.h"
#include <math.h>
#include <string.h>

Go to the source code of this file.

Macros

#define swap(_i, _j)
 
#define MIN(a, b)   (a < b ? a : b)
 

Functions

static coeffs numbercoeffs (number n, coeffs c)
 create Z/nA of type n_Zn More...
 
bool operator== (const bigintmat &lhr, const bigintmat &rhr)
 
bool operator!= (const bigintmat &lhr, const bigintmat &rhr)
 
bigintmatbimAdd (bigintmat *a, bigintmat *b)
 Matrix-Add/-Sub/-Mult so oder mit operator+/-/* ? : NULL as a result means an error (non-compatible matrices?) More...
 
bigintmatbimAdd (bigintmat *a, int b)
 
bigintmatbimSub (bigintmat *a, bigintmat *b)
 
bigintmatbimSub (bigintmat *a, int b)
 
bigintmatbimMult (bigintmat *a, bigintmat *b)
 
bigintmatbimMult (bigintmat *a, int b)
 
bigintmatbimMult (bigintmat *a, number b, const coeffs cf)
 
intvecbim2iv (bigintmat *b)
 
bigintmativ2bim (intvec *b, const coeffs C)
 
bigintmatbimCopy (const bigintmat *b)
 same as copy constructor - apart from it being able to accept NULL as input More...
 
static int intArrSum (int *a, int length)
 
static int findLongest (int *a, int length)
 
static int getShorter (int *a, int l, int j, int cols, int rows)
 
bigintmatbimChangeCoeff (bigintmat *a, coeffs cnew)
 Liefert Kopier von Matrix a zurück, mit coeffs cnew statt den ursprünglichen. More...
 
void bimMult (bigintmat *a, bigintmat *b, bigintmat *c)
 Multipliziert Matrix a und b und speichert Ergebnis in c. More...
 
static void reduce_mod_howell (bigintmat *A, bigintmat *b, bigintmat *eps, bigintmat *x)
 
static bigintmatprependIdentity (bigintmat *A)
 
static number bimFarey (bigintmat *A, number N, bigintmat *L)
 
static number solveAx_dixon (bigintmat *A, bigintmat *B, bigintmat *x, bigintmat *kern)
 
static number solveAx_howell (bigintmat *A, bigintmat *b, bigintmat *x, bigintmat *kern)
 
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 d is returned. Currently available for Z, Q and Z/nZ (and possibly for all fields: d=1 there) Beware that the internal functions can find the kernel as well - but the interface is lacking. More...
 
void diagonalForm (bigintmat *A, bigintmat **S, bigintmat **T)
 
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. More...
 
bool nCoeffs_are_equal (coeffs r, coeffs s)
 

Macro Definition Documentation

§ MIN

#define MIN (   a,
  b 
)    (a < b ? a : b)

§ swap

#define swap (   _i,
  _j 
)
Value:
int __i = (_i), __j=(_j); \
number c = v[__i]; \
v[__i] = v[__j]; \
v[__j] = c \
const Variable & v
< [in] a sqrfree bivariate poly
Definition: facBivar.h:37

Function Documentation

§ bim2iv()

intvec* bim2iv ( bigintmat b)

Definition at line 344 of file bigintmat.cc.

345 {
346  intvec * iv = new intvec(b->rows(), b->cols(), 0);
347  for (int i=0; i<(b->rows())*(b->cols()); i++)
348  (*iv)[i] = n_Int((*b)[i], b->basecoeffs()); // Geht das so?
349  return iv;
350 }
int rows() const
Definition: bigintmat.h:146
Definition: intvec.h:14
static FORCE_INLINE long n_Int(number &n, const coeffs r)
conversion of n to an int; 0 if not possible in Z/pZ: the representing int lying in (-p/2 ...
Definition: coeffs.h:551
int cols() const
Definition: bigintmat.h:145
int i
Definition: cfEzgcd.cc:123
coeffs basecoeffs() const
Definition: bigintmat.h:147

§ bimAdd() [1/2]

bigintmat* bimAdd ( bigintmat a,
bigintmat b 
)

Matrix-Add/-Sub/-Mult so oder mit operator+/-/* ? : NULL as a result means an error (non-compatible matrices?)

Definition at line 183 of file bigintmat.cc.

184 {
185  if (a->cols() != b->cols()) return NULL;
186  if (a->rows() != b->rows()) return NULL;
187  if (a->basecoeffs() != b->basecoeffs()) { return NULL; }
188 
189  const coeffs basecoeffs = a->basecoeffs();
190 
191  int i;
192 
193  bigintmat * bim = new bigintmat(a->rows(), a->cols(), basecoeffs);
194 
195  for (i=a->rows()*a->cols()-1;i>=0; i--)
196  bim->rawset(i, n_Add((*a)[i], (*b)[i], basecoeffs), basecoeffs);
197 
198  return bim;
199 }
Matrices of numbers.
Definition: bigintmat.h:51
int rows() const
Definition: bigintmat.h:146
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:197
The main handler for Singular numbers which are suitable for Singular polynomials.
static FORCE_INLINE number n_Add(number a, number b, const coeffs r)
return the sum of &#39;a&#39; and &#39;b&#39;, i.e., a+b
Definition: coeffs.h:660
int cols() const
Definition: bigintmat.h:145
int i
Definition: cfEzgcd.cc:123
#define NULL
Definition: omList.c:10
coeffs basecoeffs() const
Definition: bigintmat.h:147

§ bimAdd() [2/2]

bigintmat* bimAdd ( bigintmat a,
int  b 
)

Definition at line 200 of file bigintmat.cc.

201 {
202 
203  const int mn = a->rows()*a->cols();
204 
205  const coeffs basecoeffs = a->basecoeffs();
206  number bb=n_Init(b,basecoeffs);
207 
208  int i;
209 
210  bigintmat * bim = new bigintmat(a->rows(),a->cols() , basecoeffs);
211 
212  for (i=0; i<mn; i++)
213  bim->rawset(i, n_Add((*a)[i], bb, basecoeffs), basecoeffs);
214 
215  n_Delete(&bb,basecoeffs);
216  return bim;
217 }
Matrices of numbers.
Definition: bigintmat.h:51
int rows() const
Definition: bigintmat.h:146
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:542
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:197
The main handler for Singular numbers which are suitable for Singular polynomials.
static FORCE_INLINE number n_Add(number a, number b, const coeffs r)
return the sum of &#39;a&#39; and &#39;b&#39;, i.e., a+b
Definition: coeffs.h:660
int cols() const
Definition: bigintmat.h:145
int i
Definition: cfEzgcd.cc:123
coeffs basecoeffs() const
Definition: bigintmat.h:147
static FORCE_INLINE void n_Delete(number *p, const coeffs r)
delete &#39;p&#39;
Definition: coeffs.h:459
const poly b
Definition: syzextra.cc:213

§ bimChangeCoeff()

bigintmat* bimChangeCoeff ( bigintmat a,
coeffs  cnew 
)

Liefert Kopier von Matrix a zurück, mit coeffs cnew statt den ursprünglichen.

Definition at line 1814 of file bigintmat.cc.

1815 {
1816  coeffs cold = a->basecoeffs();
1817  bigintmat *b = new bigintmat(a->rows(), a->cols(), cnew);
1818  // Erzeugt Karte von alten coeffs nach neuen
1819  nMapFunc f = n_SetMap(cold, cnew);
1820  number t1;
1821  number t2;
1822  // apply map to all entries.
1823  for (int i=1; i<=a->rows(); i++)
1824  {
1825  for (int j=1; j<=a->cols(); j++)
1826  {
1827  t1 = a->get(i, j);
1828  t2 = f(t1, cold, cnew);
1829  b->set(i, j, t2);
1830  n_Delete(&t1, cold);
1831  n_Delete(&t2, cnew);
1832  }
1833  }
1834  return b;
1835 }
Matrices of numbers.
Definition: bigintmat.h:51
int rows() const
Definition: bigintmat.h:146
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:96
int j
Definition: myNF.cc:70
The main handler for Singular numbers which are suitable for Singular polynomials.
number(* nMapFunc)(number a, const coeffs src, const coeffs dst)
maps "a", which lives in src, into dst
Definition: coeffs.h:73
int cols() const
Definition: bigintmat.h:145
FILE * f
Definition: checklibs.c:7
int i
Definition: cfEzgcd.cc:123
static FORCE_INLINE nMapFunc n_SetMap(const coeffs src, const coeffs dst)
set the mapping function pointers for translating numbers from src to dst
Definition: coeffs.h:725
coeffs basecoeffs() const
Definition: bigintmat.h:147
static FORCE_INLINE void n_Delete(number *p, const coeffs r)
delete &#39;p&#39;
Definition: coeffs.h:459
number get(int i, int j) const
get a copy of an entry. NOTE: starts at [1,1]
Definition: bigintmat.cc:120
const poly b
Definition: syzextra.cc:213

§ bimCopy()

bigintmat* bimCopy ( const bigintmat b)

same as copy constructor - apart from it being able to accept NULL as input

Definition at line 408 of file bigintmat.cc.

409 {
410  if (b == NULL)
411  return NULL;
412 
413  return new bigintmat(b);
414 }
Matrices of numbers.
Definition: bigintmat.h:51
#define NULL
Definition: omList.c:10

§ bimFarey()

static number bimFarey ( bigintmat A,
number  N,
bigintmat L 
)
static

Definition at line 2058 of file bigintmat.cc.

2059 {
2060  coeffs Z = A->basecoeffs(),
2061  Q = nInitChar(n_Q, 0);
2062  number den = n_Init(1, Z);
2063  nMapFunc f = n_SetMap(Q, Z);
2064 
2065  for(int i=1; i<= A->rows(); i++)
2066  {
2067  for(int j=1; j<= A->cols(); j++)
2068  {
2069  number ad = n_Mult(den, A->view(i, j), Z);
2070  number re = n_IntMod(ad, N, Z);
2071  n_Delete(&ad, Z);
2072  number q = n_Farey(re, N, Z);
2073  n_Delete(&re, Z);
2074  if (!q)
2075  {
2076  n_Delete(&ad, Z);
2077  n_Delete(&den, Z);
2078  return NULL;
2079  }
2080 
2081  number d = n_GetDenom(q, Q),
2082  n = n_GetNumerator(q, Q);
2083 
2084  n_Delete(&q, Q);
2085  n_Delete(&ad, Z);
2086  number dz = f(d, Q, Z),
2087  nz = f(n, Q, Z);
2088  n_Delete(&d, Q);
2089  n_Delete(&n, Q);
2090 
2091  if (!n_IsOne(dz, Z))
2092  {
2093  L->skalmult(dz, Z);
2094  n_InpMult(den, dz, Z);
2095 #if 0
2096  PrintS("den increasing to ");
2097  n_Print(den, Z);
2098  PrintLn();
2099 #endif
2100  }
2101  n_Delete(&dz, Z);
2102  L->rawset(i, j, nz);
2103  }
2104  }
2105 
2106  nKillChar(Q);
2107  PrintS("bimFarey worked\n");
2108 #if 0
2109  L->Print();
2110  PrintS("\n * 1/");
2111  n_Print(den, Z);
2112  PrintLn();
2113 #endif
2114  return den;
2115 }
static FORCE_INLINE number n_IntMod(number a, number b, const coeffs r)
for r a field, return n_Init(0,r) always: n_Div(a,b,r)*b+n_IntMod(a,b,r)==a n_IntMod(a,b,r) >=0
Definition: coeffs.h:632
static FORCE_INLINE number n_GetNumerator(number &n, const coeffs r)
return the numerator of n (if elements of r are by nature not fractional, result is n) ...
Definition: coeffs.h:612
void PrintLn()
Definition: reporter.cc:310
static FORCE_INLINE void n_InpMult(number &a, number b, const coeffs r)
multiplication of &#39;a&#39; and &#39;b&#39;; replacement of &#39;a&#39; by the product a*b
Definition: coeffs.h:645
static FORCE_INLINE BOOLEAN n_IsOne(number n, const coeffs r)
TRUE iff &#39;n&#39; represents the one element.
Definition: coeffs.h:472
int rows() const
Definition: bigintmat.h:146
rational (GMP) numbers
Definition: coeffs.h:31
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:542
#define Q
Definition: sirandom.c:25
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:197
static FORCE_INLINE number n_Mult(number a, number b, const coeffs r)
return the product of &#39;a&#39; and &#39;b&#39;, i.e., a*b
Definition: coeffs.h:640
const CanonicalForm CFMap CFMap & N
Definition: cfEzgcd.cc:49
int j
Definition: myNF.cc:70
The main handler for Singular numbers which are suitable for Singular polynomials.
number(* nMapFunc)(number a, const coeffs src, const coeffs dst)
maps "a", which lives in src, into dst
Definition: coeffs.h:73
bool skalmult(number b, coeffs c)
Multipliziert zur Matrix den Skalar b hinzu.
Definition: bigintmat.cc:948
number view(int i, int j) const
view an entry an entry. NOTE: starts at [1,1]
Definition: bigintmat.cc:128
int cols() const
Definition: bigintmat.h:145
FILE * f
Definition: checklibs.c:7
int i
Definition: cfEzgcd.cc:123
void PrintS(const char *s)
Definition: reporter.cc:284
static FORCE_INLINE nMapFunc n_SetMap(const coeffs src, const coeffs dst)
set the mapping function pointers for translating numbers from src to dst
Definition: coeffs.h:725
void Print()
IO: simply prints the matrix to the current output (screen?)
Definition: bigintmat.cc:446
static FORCE_INLINE number n_Farey(number a, number b, const coeffs r)
Definition: coeffs.h:801
#define NULL
Definition: omList.c:10
CanonicalForm den(const CanonicalForm &f)
coeffs basecoeffs() const
Definition: bigintmat.h:147
static FORCE_INLINE number n_GetDenom(number &n, const coeffs r)
return the denominator of n (if elements of r are by nature not fractional, result is 1) ...
Definition: coeffs.h:607
static FORCE_INLINE void n_Delete(number *p, const coeffs r)
delete &#39;p&#39;
Definition: coeffs.h:459
void nKillChar(coeffs r)
undo all initialisations
Definition: numbers.cc:496
void n_Print(number &a, const coeffs r)
print a number (BEWARE of string buffers!) mostly for debugging
Definition: numbers.cc:568
coeffs nInitChar(n_coeffType t, void *parameter)
one-time initialisations for new coeffs in case of an error return NULL
Definition: numbers.cc:334

§ bimMult() [1/4]

bigintmat* bimMult ( bigintmat a,
bigintmat b 
)

Definition at line 256 of file bigintmat.cc.

257 {
258  const int ca = a->cols();
259  const int cb = b->cols();
260 
261  const int ra = a->rows();
262  const int rb = b->rows();
263 
264  if (ca != rb)
265  {
266 #ifndef SING_NDEBUG
267  Werror("wrong bigintmat sizes at multiplication a * b: acols: %d != brows: %d\n", ca, rb);
268 #endif
269  return NULL;
270  }
271 
272  assume (ca == rb);
273 
274  if (a->basecoeffs() != b->basecoeffs()) { return NULL; }
275 
276  const coeffs basecoeffs = a->basecoeffs();
277 
278  int i, j, k;
279 
280  number sum;
281 
282  bigintmat * bim = new bigintmat(ra, cb, basecoeffs);
283 
284  for (i=1; i<=ra; i++)
285  for (j=1; j<=cb; j++)
286  {
287  sum = n_Init(0, basecoeffs);
288 
289  for (k=1; k<=ca; k++)
290  {
291  number prod = n_Mult( BIMATELEM(*a, i, k), BIMATELEM(*b, k, j), basecoeffs);
292 
293  number sum2 = n_Add(sum, prod, basecoeffs); // no inplace add :(
294 
295  n_Delete(&sum, basecoeffs); n_Delete(&prod, basecoeffs);
296 
297  sum = sum2;
298  }
299  bim->rawset(i, j, sum, basecoeffs);
300  }
301  return bim;
302 }
Matrices of numbers.
Definition: bigintmat.h:51
int rows() const
Definition: bigintmat.h:146
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:542
int k
Definition: cfEzgcd.cc:93
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:197
static FORCE_INLINE number n_Mult(number a, number b, const coeffs r)
return the product of &#39;a&#39; and &#39;b&#39;, i.e., a*b
Definition: coeffs.h:640
int j
Definition: myNF.cc:70
#define assume(x)
Definition: mod2.h:403
The main handler for Singular numbers which are suitable for Singular polynomials.
static FORCE_INLINE number n_Add(number a, number b, const coeffs r)
return the sum of &#39;a&#39; and &#39;b&#39;, i.e., a+b
Definition: coeffs.h:660
int cols() const
Definition: bigintmat.h:145
int i
Definition: cfEzgcd.cc:123
#define BIMATELEM(M, I, J)
Definition: bigintmat.h:134
#define NULL
Definition: omList.c:10
coeffs basecoeffs() const
Definition: bigintmat.h:147
fq_nmod_poly_t prod
Definition: facHensel.cc:95
static FORCE_INLINE void n_Delete(number *p, const coeffs r)
delete &#39;p&#39;
Definition: coeffs.h:459
void Werror(const char *fmt,...)
Definition: reporter.cc:189

§ bimMult() [2/4]

bigintmat* bimMult ( bigintmat a,
int  b 
)

Definition at line 304 of file bigintmat.cc.

305 {
306 
307  const int mn = a->rows()*a->cols();
308 
309  const coeffs basecoeffs = a->basecoeffs();
310  number bb=n_Init(b,basecoeffs);
311 
312  int i;
313 
314  bigintmat * bim = new bigintmat(a->rows(),a->cols() , basecoeffs);
315 
316  for (i=0; i<mn; i++)
317  bim->rawset(i, n_Mult((*a)[i], bb, basecoeffs), basecoeffs);
318 
319  n_Delete(&bb,basecoeffs);
320  return bim;
321 }
Matrices of numbers.
Definition: bigintmat.h:51
int rows() const
Definition: bigintmat.h:146
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:542
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:197
static FORCE_INLINE number n_Mult(number a, number b, const coeffs r)
return the product of &#39;a&#39; and &#39;b&#39;, i.e., a*b
Definition: coeffs.h:640
The main handler for Singular numbers which are suitable for Singular polynomials.
int cols() const
Definition: bigintmat.h:145
int i
Definition: cfEzgcd.cc:123
coeffs basecoeffs() const
Definition: bigintmat.h:147
static FORCE_INLINE void n_Delete(number *p, const coeffs r)
delete &#39;p&#39;
Definition: coeffs.h:459
const poly b
Definition: syzextra.cc:213

§ bimMult() [3/4]

bigintmat* bimMult ( bigintmat a,
number  b,
const coeffs  cf 
)

Definition at line 323 of file bigintmat.cc.

324 {
325  if (cf!=a->basecoeffs()) return NULL;
326 
327  const int mn = a->rows()*a->cols();
328 
329  const coeffs basecoeffs = a->basecoeffs();
330 
331  int i;
332 
333  bigintmat * bim = new bigintmat(a->rows(),a->cols() , basecoeffs);
334 
335  for (i=0; i<mn; i++)
336  bim->rawset(i, n_Mult((*a)[i], b, basecoeffs), basecoeffs);
337 
338  return bim;
339 }
Matrices of numbers.
Definition: bigintmat.h:51
int rows() const
Definition: bigintmat.h:146
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:197
static FORCE_INLINE number n_Mult(number a, number b, const coeffs r)
return the product of &#39;a&#39; and &#39;b&#39;, i.e., a*b
Definition: coeffs.h:640
The main handler for Singular numbers which are suitable for Singular polynomials.
int cols() const
Definition: bigintmat.h:145
int i
Definition: cfEzgcd.cc:123
#define NULL
Definition: omList.c:10
coeffs basecoeffs() const
Definition: bigintmat.h:147
const poly b
Definition: syzextra.cc:213

§ bimMult() [4/4]

void bimMult ( bigintmat a,
bigintmat b,
bigintmat c 
)

Multipliziert Matrix a und b und speichert Ergebnis in c.

Definition at line 1942 of file bigintmat.cc.

1943 {
1944  if (!nCoeffs_are_equal(a->basecoeffs(), b->basecoeffs()))
1945  {
1946  WerrorS("Error in bimMult. Coeffs do not agree!");
1947  return;
1948  }
1949  if ((a->rows() != c->rows()) || (b->cols() != c->cols()) || (a->cols() != b->rows()))
1950  {
1951  WerrorS("Error in bimMult. Dimensions do not agree!");
1952  return;
1953  }
1954  bigintmat *tmp = bimMult(a, b);
1955  c->copy(tmp);
1956 
1957  delete tmp;
1958 }
Matrices of numbers.
Definition: bigintmat.h:51
int rows() const
Definition: bigintmat.h:146
void WerrorS(const char *s)
Definition: feFopen.cc:24
bigintmat * bimMult(bigintmat *a, bigintmat *b)
Definition: bigintmat.cc:256
int cols() const
Definition: bigintmat.h:145
coeffs basecoeffs() const
Definition: bigintmat.h:147
bool copy(bigintmat *b)
Kopiert Einträge von b auf Bigintmat.
Definition: bigintmat.cc:1269
bool nCoeffs_are_equal(coeffs r, coeffs s)
Definition: bigintmat.cc:2655

§ bimSub() [1/2]

bigintmat* bimSub ( bigintmat a,
bigintmat b 
)

Definition at line 219 of file bigintmat.cc.

220 {
221  if (a->cols() != b->cols()) return NULL;
222  if (a->rows() != b->rows()) return NULL;
223  if (a->basecoeffs() != b->basecoeffs()) { return NULL; }
224 
225  const coeffs basecoeffs = a->basecoeffs();
226 
227  int i;
228 
229  bigintmat * bim = new bigintmat(a->rows(), a->cols(), basecoeffs);
230 
231  for (i=a->rows()*a->cols()-1;i>=0; i--)
232  bim->rawset(i, n_Sub((*a)[i], (*b)[i], basecoeffs), basecoeffs);
233 
234  return bim;
235 }
static FORCE_INLINE number n_Sub(number a, number b, const coeffs r)
return the difference of &#39;a&#39; and &#39;b&#39;, i.e., a-b
Definition: coeffs.h:673
Matrices of numbers.
Definition: bigintmat.h:51
int rows() const
Definition: bigintmat.h:146
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:197
The main handler for Singular numbers which are suitable for Singular polynomials.
int cols() const
Definition: bigintmat.h:145
int i
Definition: cfEzgcd.cc:123
#define NULL
Definition: omList.c:10
coeffs basecoeffs() const
Definition: bigintmat.h:147

§ bimSub() [2/2]

bigintmat* bimSub ( bigintmat a,
int  b 
)

Definition at line 237 of file bigintmat.cc.

238 {
239  const int mn = a->rows()*a->cols();
240 
241  const coeffs basecoeffs = a->basecoeffs();
242  number bb=n_Init(b,basecoeffs);
243 
244  int i;
245 
246  bigintmat * bim = new bigintmat(a->rows(),a->cols() , basecoeffs);
247 
248  for (i=0; i<mn; i++)
249  bim->rawset(i, n_Sub((*a)[i], bb, basecoeffs), basecoeffs);
250 
251  n_Delete(&bb,basecoeffs);
252  return bim;
253 }
static FORCE_INLINE number n_Sub(number a, number b, const coeffs r)
return the difference of &#39;a&#39; and &#39;b&#39;, i.e., a-b
Definition: coeffs.h:673
Matrices of numbers.
Definition: bigintmat.h:51
int rows() const
Definition: bigintmat.h:146
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:542
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:197
The main handler for Singular numbers which are suitable for Singular polynomials.
int cols() const
Definition: bigintmat.h:145
int i
Definition: cfEzgcd.cc:123
coeffs basecoeffs() const
Definition: bigintmat.h:147
static FORCE_INLINE void n_Delete(number *p, const coeffs r)
delete &#39;p&#39;
Definition: coeffs.h:459
const poly b
Definition: syzextra.cc:213

§ diagonalForm()

void diagonalForm ( bigintmat A,
bigintmat **  S,
bigintmat **  T 
)

Definition at line 2485 of file bigintmat.cc.

2486 {
2487  bigintmat * t, *s, *a=A;
2488  coeffs R = a->basecoeffs();
2489  if (T)
2490  {
2491  *T = new bigintmat(a->cols(), a->cols(), R),
2492  (*T)->one();
2493  t = new bigintmat(*T);
2494  }
2495  else
2496  {
2497  t = *T;
2498  }
2499 
2500  if (S)
2501  {
2502  *S = new bigintmat(a->rows(), a->rows(), R);
2503  (*S)->one();
2504  s = new bigintmat(*S);
2505  }
2506  else
2507  {
2508  s = *S;
2509  }
2510 
2511  int flip=0;
2512  do
2513  {
2514  bigintmat * x, *X;
2515  if (flip)
2516  {
2517  x = s;
2518  X = *S;
2519  }
2520  else
2521  {
2522  x = t;
2523  X = *T;
2524  }
2525 
2526  if (x)
2527  {
2528  x->one();
2529  bigintmat * r = new bigintmat(a->rows()+a->cols(), a->cols(), R);
2530  bigintmat * rw = new bigintmat(1, a->cols(), R);
2531  for(int i=0; i<a->cols(); i++)
2532  {
2533  x->getrow(i+1, rw);
2534  r->setrow(i+1, rw);
2535  }
2536  for (int i=0; i<a->rows(); i++)
2537  {
2538  a->getrow(i+1, rw);
2539  r->setrow(i+a->cols()+1, rw);
2540  }
2541  r->hnf();
2542  for(int i=0; i<a->cols(); i++)
2543  {
2544  r->getrow(i+1, rw);
2545  x->setrow(i+1, rw);
2546  }
2547  for(int i=0; i<a->rows(); i++)
2548  {
2549  r->getrow(i+a->cols()+1, rw);
2550  a->setrow(i+1, rw);
2551  }
2552  delete rw;
2553  delete r;
2554 
2555 #if 0
2556  Print("X: %ld\n", X);
2557  X->Print();
2558  Print("\nx: %ld\n", x);
2559  x->Print();
2560 #endif
2561  bimMult(X, x, X);
2562 #if 0
2563  Print("\n2:X: %ld %ld %ld\n", X, *S, *T);
2564  X->Print();
2565  Print("\n2:x: %ld\n", x);
2566  x->Print();
2567  PrintLn();
2568 #endif
2569  }
2570  else
2571  {
2572  a->hnf();
2573  }
2574 
2575  int diag = 1;
2576  for(int i=a->rows(); diag && i>0; i--)
2577  {
2578  for(int j=a->cols(); j>0; j--)
2579  {
2580  if ((a->rows()-i)!=(a->cols()-j) && !n_IsZero(a->view(i, j), R))
2581  {
2582  diag = 0;
2583  break;
2584  }
2585  }
2586  }
2587 #if 0
2588  PrintS("Diag ? %d\n", diag);
2589  a->Print();
2590  PrintLn();
2591 #endif
2592  if (diag) break;
2593 
2594  a = a->transpose(); // leaks - I need to write inpTranspose
2595  flip = 1-flip;
2596  } while (1);
2597  if (flip)
2598  a = a->transpose();
2599 
2600  if (S) *S = (*S)->transpose();
2601  if (s) delete s;
2602  if (t) delete t;
2603  A->copy(a);
2604 }
bigintmat * transpose()
Definition: bigintmat.cc:38
const CanonicalForm int s
Definition: facAbsFact.cc:55
const poly a
Definition: syzextra.cc:212
void PrintLn()
Definition: reporter.cc:310
#define Print
Definition: emacs.cc:83
void getrow(int i, bigintmat *a)
Schreibt i-te Zeile in Vektor (Matrix) a.
Definition: bigintmat.cc:801
Matrices of numbers.
Definition: bigintmat.h:51
int rows() const
Definition: bigintmat.h:146
void setrow(int i, bigintmat *m)
Setzt i-te Zeile gleich übergebenem Vektor (Matrix) m.
Definition: bigintmat.cc:870
const ring r
Definition: syzextra.cc:208
int j
Definition: myNF.cc:70
bigintmat * bimMult(bigintmat *a, bigintmat *b)
Definition: bigintmat.cc:256
The main handler for Singular numbers which are suitable for Singular polynomials.
#define A
Definition: sirandom.c:23
const ring R
Definition: DebugPrint.cc:36
number view(int i, int j) const
view an entry an entry. NOTE: starts at [1,1]
Definition: bigintmat.cc:128
int cols() const
Definition: bigintmat.h:145
void hnf()
transforms INPLACE to HNF
Definition: bigintmat.cc:1670
int i
Definition: cfEzgcd.cc:123
void PrintS(const char *s)
Definition: reporter.cc:284
static FORCE_INLINE BOOLEAN n_IsZero(number n, const coeffs r)
TRUE iff &#39;n&#39; represents the zero element.
Definition: coeffs.h:468
void Print()
IO: simply prints the matrix to the current output (screen?)
Definition: bigintmat.cc:446
std::pair< ideal, ring > flip(const ideal I, const ring r, const gfan::ZVector interiorPoint, const gfan::ZVector facetNormal, const gfan::ZVector adjustedInteriorPoint, const gfan::ZVector adjustedFacetNormal)
Definition: flip.cc:18
coeffs basecoeffs() const
Definition: bigintmat.h:147
bool copy(bigintmat *b)
Kopiert Einträge von b auf Bigintmat.
Definition: bigintmat.cc:1269
Variable x
Definition: cfModGcd.cc:4023
static jList * T
Definition: janet.cc:37
void one()
Macht Matrix (Falls quadratisch) zu Einheitsmatrix.
Definition: bigintmat.cc:1335

§ findLongest()

static int findLongest ( int *  a,
int  length 
)
static

Definition at line 540 of file bigintmat.cc.

541 {
542  int l = 0;
543  int index;
544  for (int i=0; i<length; i++)
545  {
546  if (a[i] > l)
547  {
548  l = a[i];
549  index = i;
550  }
551  }
552  return index;
553 }
const poly a
Definition: syzextra.cc:212
int i
Definition: cfEzgcd.cc:123
static int index(p_Length length, p_Ord ord)
Definition: p_Procs_Impl.h:592
int l
Definition: cfEzgcd.cc:94

§ getShorter()

static int getShorter ( int *  a,
int  l,
int  j,
int  cols,
int  rows 
)
static

Definition at line 555 of file bigintmat.cc.

556 {
557  int sndlong = 0;
558  int min;
559  for (int i=0; i<rows; i++)
560  {
561  int index = cols*i+j;
562  if ((a[index] > sndlong) && (a[index] < l))
563  {
564  min = floor(log10((double)cols))+floor(log10((double)rows))+5;
565  if ((a[index] < min) && (min < l))
566  sndlong = min;
567  else
568  sndlong = a[index];
569  }
570  }
571  if (sndlong == 0)
572  {
573  min = floor(log10((double)cols))+floor(log10((double)rows))+5;
574  if (min < l)
575  sndlong = min;
576  else
577  sndlong = 1;
578  }
579  return sndlong;
580 }
const poly a
Definition: syzextra.cc:212
static int min(int a, int b)
Definition: fast_mult.cc:268
int j
Definition: myNF.cc:70
int i
Definition: cfEzgcd.cc:123
static int index(p_Length length, p_Ord ord)
Definition: p_Procs_Impl.h:592
int l
Definition: cfEzgcd.cc:94

§ intArrSum()

static int intArrSum ( int *  a,
int  length 
)
static

Definition at line 532 of file bigintmat.cc.

533 {
534  int sum = 0;
535  for (int i=0; i<length; i++)
536  sum += a[i];
537  return sum;
538 }
const poly a
Definition: syzextra.cc:212
int i
Definition: cfEzgcd.cc:123

§ iv2bim()

bigintmat* iv2bim ( intvec b,
const coeffs  C 
)

Definition at line 352 of file bigintmat.cc.

353 {
354  const int l = (b->rows())*(b->cols());
355  bigintmat * bim = new bigintmat(b->rows(), b->cols(), C);
356 
357  for (int i=0; i < l; i++)
358  bim->rawset(i, n_Init((*b)[i], C), C);
359 
360  return bim;
361 }
Matrices of numbers.
Definition: bigintmat.h:51
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:542
int rows() const
Definition: intvec.h:88
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:197
int i
Definition: cfEzgcd.cc:123
int cols() const
Definition: intvec.h:87
int l
Definition: cfEzgcd.cc:94

§ kernbase()

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.

Definition at line 2610 of file bigintmat.cc.

2611 {
2612 #if 0
2613  PrintS("Kernel of ");
2614  a->Print();
2615  PrintS(" modulo ");
2616  n_Print(p, q);
2617  PrintLn();
2618 #endif
2619 
2620  coeffs coe = numbercoeffs(p, q);
2621  bigintmat *m = bimChangeCoeff(a, coe), *U, *V;
2622  diagonalForm(m, &U, &V);
2623 #if 0
2624  PrintS("\ndiag form: ");
2625  m->Print();
2626  PrintS("\nU:\n");
2627  U->Print();
2628  PrintS("\nV:\n");
2629  V->Print();
2630  PrintLn();
2631 #endif
2632 
2633  int rg = 0;
2634 #undef MIN
2635 #define MIN(a,b) (a < b ? a : b)
2636  for(rg=0; rg<MIN(m->rows(), m->cols()) && !n_IsZero(m->view(m->rows()-rg,m->cols()-rg), coe); rg++);
2637 
2638  bigintmat * k = new bigintmat(m->cols(), m->rows(), coe);
2639  for(int i=0; i<rg; i++)
2640  {
2641  number A = n_Ann(m->view(m->rows()-i, m->cols()-i), coe);
2642  k->set(m->cols()-i, i+1, A);
2643  n_Delete(&A, coe);
2644  }
2645  for(int i=rg; i<m->cols(); i++)
2646  {
2647  k->set(m->cols()-i, i+1-rg, n_Init(1, coe));
2648  }
2649  bimMult(V, k, k);
2650  c->copy(bimChangeCoeff(k, q));
2651  return c->cols();
2652 }
void PrintLn()
Definition: reporter.cc:310
return P p
Definition: myNF.cc:203
Matrices of numbers.
Definition: bigintmat.h:51
int rows() const
Definition: bigintmat.h:146
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:542
int k
Definition: cfEzgcd.cc:93
#define MIN(a, b)
static FORCE_INLINE number n_Ann(number a, const coeffs r)
if r is a ring with zero divisors, return an annihilator!=0 of b otherwise return NULL ...
Definition: coeffs.h:705
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:96
static coeffs numbercoeffs(number n, coeffs c)
create Z/nA of type n_Zn
Definition: bigintmat.cc:22
bigintmat * bimMult(bigintmat *a, bigintmat *b)
Definition: bigintmat.cc:256
The main handler for Singular numbers which are suitable for Singular polynomials.
#define A
Definition: sirandom.c:23
number view(int i, int j) const
view an entry an entry. NOTE: starts at [1,1]
Definition: bigintmat.cc:128
int cols() const
Definition: bigintmat.h:145
int m
Definition: cfEzgcd.cc:119
int i
Definition: cfEzgcd.cc:123
void PrintS(const char *s)
Definition: reporter.cc:284
static FORCE_INLINE BOOLEAN n_IsZero(number n, const coeffs r)
TRUE iff &#39;n&#39; represents the zero element.
Definition: coeffs.h:468
bigintmat * bimChangeCoeff(bigintmat *a, coeffs cnew)
Liefert Kopier von Matrix a zurück, mit coeffs cnew statt den ursprünglichen.
Definition: bigintmat.cc:1814
void diagonalForm(bigintmat *A, bigintmat **S, bigintmat **T)
Definition: bigintmat.cc:2485
void Print()
IO: simply prints the matrix to the current output (screen?)
Definition: bigintmat.cc:446
bool copy(bigintmat *b)
Kopiert Einträge von b auf Bigintmat.
Definition: bigintmat.cc:1269
static FORCE_INLINE void n_Delete(number *p, const coeffs r)
delete &#39;p&#39;
Definition: coeffs.h:459
void n_Print(number &a, const coeffs r)
print a number (BEWARE of string buffers!) mostly for debugging
Definition: numbers.cc:568

§ nCoeffs_are_equal()

bool nCoeffs_are_equal ( coeffs  r,
coeffs  s 
)

Definition at line 2655 of file bigintmat.cc.

2656 {
2657  if ((r == NULL) || (s == NULL))
2658  return false;
2659  if (r == s)
2660  return true;
2661  if ((getCoeffType(r)==n_Z) && (getCoeffType(s)==n_Z))
2662  return true;
2663  if ((getCoeffType(r)==n_Zp) && (getCoeffType(s)==n_Zp))
2664  {
2665  if (r->ch == s->ch)
2666  return true;
2667  else
2668  return false;
2669  }
2670  // n_Zn stimmt wahrscheinlich noch nicht
2671  if ((getCoeffType(r)==n_Zn) && (getCoeffType(s)==n_Zn))
2672  {
2673  if (r->ch == s->ch)
2674  return true;
2675  else
2676  return false;
2677  }
2678  if ((getCoeffType(r)==n_Q) && (getCoeffType(s)==n_Q))
2679  return true;
2680  // FALL n_Zn FEHLT NOCH!
2681  //if ((getCoeffType(r)==n_Zn) && (getCoeffType(s)==n_Zn))
2682  return false;
2683 }
only used if HAVE_RINGS is defined
Definition: coeffs.h:44
rational (GMP) numbers
Definition: coeffs.h:31
{p < 2^31}
Definition: coeffs.h:30
only used if HAVE_RINGS is defined
Definition: coeffs.h:43
static FORCE_INLINE n_coeffType getCoeffType(const coeffs r)
Returns the type of coeffs domain.
Definition: coeffs.h:425
#define NULL
Definition: omList.c:10

§ numbercoeffs()

static coeffs numbercoeffs ( number  n,
coeffs  c 
)
static

create Z/nA of type n_Zn

Definition at line 22 of file bigintmat.cc.

23 {
24  mpz_t p;
25  number2mpz(n, c, p);
26  ZnmInfo *pp = new ZnmInfo;
27  pp->base = p;
28  pp->exp = 1;
29  coeffs nc = nInitChar(n_Zn, (void*)pp);
30  mpz_clear(p);
31  delete pp;
32  return nc;
33 }
mpz_ptr base
Definition: rmodulon.h:19
only used if HAVE_RINGS is defined
Definition: coeffs.h:44
return P p
Definition: myNF.cc:203
poly pp
Definition: myNF.cc:296
static FORCE_INLINE void number2mpz(number n, coeffs c, mpz_t m)
Definition: coeffs.h:1001
The main handler for Singular numbers which are suitable for Singular polynomials.
unsigned long exp
Definition: rmodulon.h:19
coeffs nInitChar(n_coeffType t, void *parameter)
one-time initialisations for new coeffs in case of an error return NULL
Definition: numbers.cc:334

§ operator!=()

bool operator!= ( const bigintmat lhr,
const bigintmat rhr 
)

Definition at line 177 of file bigintmat.cc.

178 {
179  return !(lhr==rhr);
180 }

§ operator==()

bool operator== ( const bigintmat lhr,
const bigintmat rhr 
)

Definition at line 160 of file bigintmat.cc.

161 {
162  if (&lhr == &rhr) { return true; }
163  if (lhr.cols() != rhr.cols()) { return false; }
164  if (lhr.rows() != rhr.rows()) { return false; }
165  if (lhr.basecoeffs() != rhr.basecoeffs()) { return false; }
166 
167  const int l = (lhr.rows())*(lhr.cols());
168 
169  for (int i=0; i < l; i++)
170  {
171  if (!n_Equal(lhr[i], rhr[i], lhr.basecoeffs())) { return false; }
172  }
173 
174  return true;
175 }
int rows() const
Definition: bigintmat.h:146
int cols() const
Definition: bigintmat.h:145
int i
Definition: cfEzgcd.cc:123
coeffs basecoeffs() const
Definition: bigintmat.h:147
static FORCE_INLINE BOOLEAN n_Equal(number a, number b, const coeffs r)
TRUE iff &#39;a&#39; and &#39;b&#39; represent the same number; they may have different representations.
Definition: coeffs.h:464
int l
Definition: cfEzgcd.cc:94

§ prependIdentity()

static bigintmat* prependIdentity ( bigintmat A)
static

Definition at line 2046 of file bigintmat.cc.

2047 {
2048  coeffs R = A->basecoeffs();
2049  bigintmat *m = new bigintmat(A->rows()+A->cols(), A->cols(), R);
2050  m->copySubmatInto(A, 1, 1, A->rows(), A->cols(), A->cols()+1, 1);
2051  number one = n_Init(1, R);
2052  for(int i=1; i<= A->cols(); i++)
2053  m->set(i,i,one);
2054  n_Delete(&one, R);
2055  return m;
2056 }
Matrices of numbers.
Definition: bigintmat.h:51
int rows() const
Definition: bigintmat.h:146
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:542
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:96
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...
Definition: bigintmat.cc:1297
The main handler for Singular numbers which are suitable for Singular polynomials.
const ring R
Definition: DebugPrint.cc:36
int cols() const
Definition: bigintmat.h:145
int m
Definition: cfEzgcd.cc:119
int i
Definition: cfEzgcd.cc:123
coeffs basecoeffs() const
Definition: bigintmat.h:147
static FORCE_INLINE void n_Delete(number *p, const coeffs r)
delete &#39;p&#39;
Definition: coeffs.h:459

§ reduce_mod_howell()

static void reduce_mod_howell ( bigintmat A,
bigintmat b,
bigintmat eps,
bigintmat x 
)
static

Definition at line 1960 of file bigintmat.cc.

1961 {
1962  //write b = Ax + eps where eps is "small" in the sense of bounded by the
1963  //pivot entries in H. H does not need to be Howell (or HNF) but need
1964  //to be triagonal in the same direction.
1965  //b can have multiple columns.
1966 #if 0
1967  PrintS("reduce_mod_howell: A:\n");
1968  A->Print();
1969  PrintS("\nb:\n");
1970  b->Print();
1971 #endif
1972 
1973  coeffs R = A->basecoeffs();
1974  assume(x->basecoeffs() == R);
1975  assume(b->basecoeffs() == R);
1976  assume(eps->basecoeffs() == R);
1977  if (!A->cols())
1978  {
1979  x->zero();
1980  eps->copy(b);
1981 
1982 #if 0
1983  PrintS("\nx:\n");
1984  x->Print();
1985  PrintS("\neps:\n");
1986  eps->Print();
1987  PrintS("\n****************************************\n");
1988 #endif
1989  return;
1990  }
1991 
1992  bigintmat * B = new bigintmat(b->rows(), 1, R);
1993  for(int i=1; i<= b->cols(); i++)
1994  {
1995  int A_col = A->cols();
1996  b->getcol(i, B);
1997  for(int j = B->rows(); j>0; j--)
1998  {
1999  number Ai = A->view(A->rows() - B->rows() + j, A_col);
2000  if (n_IsZero(Ai, R) &&
2001  n_IsZero(B->view(j, 1), R))
2002  {
2003  continue; //all is fine: 0*x = 0
2004  }
2005  else if (n_IsZero(B->view(j, 1), R))
2006  {
2007  x->rawset(x->rows() - B->rows() + j, i, n_Init(0, R));
2008  A_col--;
2009  }
2010  else if (n_IsZero(Ai, R))
2011  {
2012  A_col--;
2013  }
2014  else
2015  {
2016  // "solve" ax=b, possibly enlarging d
2017  number Bj = B->view(j, 1);
2018  number q = n_Div(Bj, Ai, R);
2019  x->rawset(x->rows() - B->rows() + j, i, q);
2020  for(int k=j; k>B->rows() - A->rows(); k--)
2021  {
2022  //B[k] = B[k] - x[k]A[k][j]
2023  number s = n_Mult(q, A->view(A->rows() - B->rows() + k, A_col), R);
2024  B->rawset(k, 1, n_Sub(B->view(k, 1), s, R));
2025  n_Delete(&s, R);
2026  }
2027  A_col--;
2028  }
2029  if (!A_col)
2030  {
2031  break;
2032  }
2033  }
2034  eps->setcol(i, B);
2035  }
2036  delete B;
2037 #if 0
2038  PrintS("\nx:\n");
2039  x->Print();
2040  PrintS("\neps:\n");
2041  eps->Print();
2042  PrintS("\n****************************************\n");
2043 #endif
2044 }
static FORCE_INLINE number n_Sub(number a, number b, const coeffs r)
return the difference of &#39;a&#39; and &#39;b&#39;, i.e., a-b
Definition: coeffs.h:673
const CanonicalForm int s
Definition: facAbsFact.cc:55
Matrices of numbers.
Definition: bigintmat.h:51
void setcol(int j, bigintmat *m)
Setzt j-te Spalte gleich übergebenem Vektor (Matrix) m.
Definition: bigintmat.cc:836
int rows() const
Definition: bigintmat.h:146
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:542
void zero()
Setzt alle Einträge auf 0.
Definition: bigintmat.cc:1360
int k
Definition: cfEzgcd.cc:93
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:197
static FORCE_INLINE number n_Mult(number a, number b, const coeffs r)
return the product of &#39;a&#39; and &#39;b&#39;, i.e., a*b
Definition: coeffs.h:640
int j
Definition: myNF.cc:70
#define assume(x)
Definition: mod2.h:403
The main handler for Singular numbers which are suitable for Singular polynomials.
const ring R
Definition: DebugPrint.cc:36
number view(int i, int j) const
view an entry an entry. NOTE: starts at [1,1]
Definition: bigintmat.cc:128
int cols() const
Definition: bigintmat.h:145
int i
Definition: cfEzgcd.cc:123
void PrintS(const char *s)
Definition: reporter.cc:284
static FORCE_INLINE BOOLEAN n_IsZero(number n, const coeffs r)
TRUE iff &#39;n&#39; represents the zero element.
Definition: coeffs.h:468
void Print()
IO: simply prints the matrix to the current output (screen?)
Definition: bigintmat.cc:446
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:757
static FORCE_INLINE number n_Div(number a, number b, const coeffs r)
return the quotient of &#39;a&#39; and &#39;b&#39;, i.e., a/b; raises an error if &#39;b&#39; is not invertible in r exceptio...
Definition: coeffs.h:619
b *CanonicalForm B
Definition: facBivar.cc:51
coeffs basecoeffs() const
Definition: bigintmat.h:147
bool copy(bigintmat *b)
Kopiert Einträge von b auf Bigintmat.
Definition: bigintmat.cc:1269
static FORCE_INLINE void n_Delete(number *p, const coeffs r)
delete &#39;p&#39;
Definition: coeffs.h:459

§ solveAx()

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 d is returned. Currently available for Z, Q and Z/nZ (and possibly for all fields: d=1 there) Beware that the internal functions can find the kernel as well - but the interface is lacking.

Definition at line 2440 of file bigintmat.cc.

2441 {
2442 #if 0
2443  PrintS("Solve Ax=b for A=\n");
2444  A->Print();
2445  PrintS("\nb = \n");
2446  b->Print();
2447  PrintS("\nx = \n");
2448  x->Print();
2449  PrintLn();
2450 #endif
2451 
2452  coeffs R = A->basecoeffs();
2453  assume (R == b->basecoeffs());
2454  assume (R == x->basecoeffs());
2455  assume ((x->cols() == b->cols()) && (x->rows() == A->cols()) && (A->rows() == b->rows()));
2456 
2457  switch (getCoeffType(R))
2458  {
2459  #ifdef HAVE_RINGS
2460  case n_Z:
2461  return solveAx_dixon(A, b, x, NULL);
2462  case n_Zn:
2463  case n_Znm:
2464  case n_Z2m:
2465  return solveAx_howell(A, b, x, NULL);
2466  #endif
2467  case n_Zp:
2468  case n_Q:
2469  case n_GF:
2470  case n_algExt:
2471  case n_transExt:
2472  WarnS("have field, should use Gauss or better");
2473  break;
2474  default:
2475  if (R->cfXExtGcd && R->cfAnn)
2476  { //assume it's Euclidean
2477  return solveAx_howell(A, b, x, NULL);
2478  }
2479  WerrorS("have no solve algorithm");
2480  break;
2481  }
2482  return NULL;
2483 }
static number solveAx_dixon(bigintmat *A, bigintmat *B, bigintmat *x, bigintmat *kern)
Definition: bigintmat.cc:2118
void PrintLn()
Definition: reporter.cc:310
only used if HAVE_RINGS is defined
Definition: coeffs.h:44
only used if HAVE_RINGS is defined
Definition: coeffs.h:46
used for all transcendental extensions, i.e., the top-most extension in an extension tower is transce...
Definition: coeffs.h:39
int rows() const
Definition: bigintmat.h:146
rational (GMP) numbers
Definition: coeffs.h:31
{p < 2^31}
Definition: coeffs.h:30
void WerrorS(const char *s)
Definition: feFopen.cc:24
#define WarnS
Definition: emacs.cc:81
only used if HAVE_RINGS is defined
Definition: coeffs.h:45
#define assume(x)
Definition: mod2.h:403
The main handler for Singular numbers which are suitable for Singular polynomials.
const ring R
Definition: DebugPrint.cc:36
int cols() const
Definition: bigintmat.h:145
only used if HAVE_RINGS is defined
Definition: coeffs.h:43
void PrintS(const char *s)
Definition: reporter.cc:284
static number solveAx_howell(bigintmat *A, bigintmat *b, bigintmat *x, bigintmat *kern)
Definition: bigintmat.cc:2308
static FORCE_INLINE n_coeffType getCoeffType(const coeffs r)
Returns the type of coeffs domain.
Definition: coeffs.h:425
void Print()
IO: simply prints the matrix to the current output (screen?)
Definition: bigintmat.cc:446
#define NULL
Definition: omList.c:10
{p^n < 2^16}
Definition: coeffs.h:33
used for all algebraic extensions, i.e., the top-most extension in an extension tower is algebraic ...
Definition: coeffs.h:36
coeffs basecoeffs() const
Definition: bigintmat.h:147

§ solveAx_dixon()

static number solveAx_dixon ( bigintmat A,
bigintmat B,
bigintmat x,
bigintmat kern 
)
static

Definition at line 2118 of file bigintmat.cc.

2118  {
2119  coeffs R = A->basecoeffs();
2120 
2121  assume(getCoeffType(R) == n_Z);
2122 
2123  number p = n_Init(536870909, R); // PreviousPrime(2^29); not clever
2124  coeffs Rp = numbercoeffs(p, R); // R/pR
2125  bigintmat *Ap = bimChangeCoeff(A, Rp),
2126  *m = prependIdentity(Ap),
2127  *Tp, *Hp;
2128  delete Ap;
2129 
2130  m->howell();
2131  Hp = new bigintmat(A->rows(), A->cols(), Rp);
2132  Hp->copySubmatInto(m, A->cols()+1, 1, A->rows(), A->cols(), 1, 1);
2133  Tp = new bigintmat(A->cols(), A->cols(), Rp);
2134  Tp->copySubmatInto(m, 1, 1, A->cols(), A->cols(), 1, 1);
2135 
2136  int i, j;
2137 
2138  for(i=1; i<= A->cols(); i++)
2139  {
2140  for(j=m->rows(); j>A->cols(); j--)
2141  {
2142  if (!n_IsZero(m->view(j, i), Rp)) break;
2143  }
2144  if (j>A->cols()) break;
2145  }
2146 // Print("Found nullity (kern dim) of %d\n", i-1);
2147  bigintmat * kp = new bigintmat(A->cols(), i-1, Rp);
2148  kp->copySubmatInto(Tp, 1, 1, A->cols(), i-1, 1, 1);
2149  kp->howell();
2150 
2151  delete m;
2152 
2153  //Hp is the mod-p howell form
2154  //Tp the transformation, mod p
2155  //kp a basis for the kernel, in howell form, mod p
2156 
2157  bigintmat * eps_p = new bigintmat(B->rows(), B->cols(), Rp),
2158  * x_p = new bigintmat(A->cols(), B->cols(), Rp),
2159  * fps_p = new bigintmat(kp->cols(), B->cols(), Rp);
2160 
2161  //initial solution
2162 
2163  number zero = n_Init(0, R);
2164  x->skalmult(zero, R);
2165  n_Delete(&zero, R);
2166 
2167  bigintmat * b = new bigintmat(B);
2168  number pp = n_Init(1, R);
2169  i = 1;
2170  do
2171  {
2172  bigintmat * b_p = bimChangeCoeff(b, Rp), * s;
2173  bigintmat * t1, *t2;
2174  reduce_mod_howell(Hp, b_p, eps_p, x_p);
2175  delete b_p;
2176  if (!eps_p->isZero())
2177  {
2178  PrintS("no solution, since no modular solution\n");
2179 
2180  delete eps_p;
2181  delete x_p;
2182  delete Hp;
2183  delete kp;
2184  delete Tp;
2185  delete b;
2186  n_Delete(&pp, R);
2187  n_Delete(&p, R);
2188  nKillChar(Rp);
2189 
2190  return NULL;
2191  }
2192  t1 = bimMult(Tp, x_p);
2193  delete x_p;
2194  x_p = t1;
2195  reduce_mod_howell(kp, x_p, x_p, fps_p); //we're not all interested in fps_p
2196  s = bimChangeCoeff(x_p, R);
2197  t1 = bimMult(A, s);
2198  t2 = bimSub(b, t1);
2199  t2->skaldiv(p);
2200  delete b;
2201  delete t1;
2202  b = t2;
2203  s->skalmult(pp, R);
2204  t1 = bimAdd(x, s);
2205  delete s;
2206  x->swapMatrix(t1);
2207  delete t1;
2208 
2209  if(kern && i==1)
2210  {
2211  bigintmat * ker = bimChangeCoeff(kp, R);
2212  t1 = bimMult(A, ker);
2213  t1->skaldiv(p);
2214  t1->skalmult(n_Init(-1, R), R);
2215  b->appendCol(t1);
2216  delete t1;
2217  x->appendCol(ker);
2218  delete ker;
2219  x_p->extendCols(kp->cols());
2220  eps_p->extendCols(kp->cols());
2221  fps_p->extendCols(kp->cols());
2222  }
2223 
2224  n_InpMult(pp, p, R);
2225 
2226  if (b->isZero())
2227  {
2228  //exact solution found, stop
2229  delete eps_p;
2230  delete fps_p;
2231  delete x_p;
2232  delete Hp;
2233  delete kp;
2234  delete Tp;
2235  delete b;
2236  n_Delete(&pp, R);
2237  n_Delete(&p, R);
2238  nKillChar(Rp);
2239 
2240  return n_Init(1, R);
2241  }
2242  else
2243  {
2244  bigintmat *y = new bigintmat(x->rows(), x->cols(), R);
2245  number d = bimFarey(x, pp, y);
2246  if (d)
2247  {
2248  bigintmat *c = bimMult(A, y);
2249  bigintmat *bd = new bigintmat(B);
2250  bd->skalmult(d, R);
2251  if (kern)
2252  {
2253  bd->extendCols(kp->cols());
2254  }
2255  if (*c == *bd)
2256  {
2257  x->swapMatrix(y);
2258  delete y;
2259  delete c;
2260  if (kern)
2261  {
2262  y = new bigintmat(x->rows(), B->cols(), R);
2263  c = new bigintmat(x->rows(), kp->cols(), R);
2264  x->splitcol(y, c);
2265  x->swapMatrix(y);
2266  delete y;
2267  kern->swapMatrix(c);
2268  delete c;
2269  }
2270 
2271  delete bd;
2272 
2273  delete eps_p;
2274  delete fps_p;
2275  delete x_p;
2276  delete Hp;
2277  delete kp;
2278  delete Tp;
2279  delete b;
2280  n_Delete(&pp, R);
2281  n_Delete(&p, R);
2282  nKillChar(Rp);
2283 
2284  return d;
2285  }
2286  delete c;
2287  delete bd;
2288  n_Delete(&d, R);
2289  }
2290  delete y;
2291  }
2292  i++;
2293  } while (1);
2294  delete eps_p;
2295  delete fps_p;
2296  delete x_p;
2297  delete Hp;
2298  delete kp;
2299  delete Tp;
2300  n_Delete(&pp, R);
2301  n_Delete(&p, R);
2302  nKillChar(Rp);
2303  return NULL;
2304 }
void skaldiv(number b)
Macht Ganzzahldivision aller Matrixeinträge mit b.
Definition: bigintmat.cc:1871
void splitcol(bigintmat *a, bigintmat *b)
... linken ... rechten ...
Definition: bigintmat.cc:1179
const CanonicalForm int s
Definition: facAbsFact.cc:55
const CanonicalForm int const CFList const Variable & y
Definition: facAbsFact.cc:57
bigintmat * bimSub(bigintmat *a, bigintmat *b)
Definition: bigintmat.cc:219
static bigintmat * prependIdentity(bigintmat *A)
Definition: bigintmat.cc:2046
static FORCE_INLINE void n_InpMult(number &a, number b, const coeffs r)
multiplication of &#39;a&#39; and &#39;b&#39;; replacement of &#39;a&#39; by the product a*b
Definition: coeffs.h:645
return P p
Definition: myNF.cc:203
Matrices of numbers.
Definition: bigintmat.h:51
void appendCol(bigintmat *a)
horizontally join the matrices, m <- m|a
Definition: bigintmat.cc:1093
int rows() const
Definition: bigintmat.h:146
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:542
bigintmat * bimAdd(bigintmat *a, bigintmat *b)
Matrix-Add/-Sub/-Mult so oder mit operator+/-/* ? : NULL as a result means an error (non-compatible m...
Definition: bigintmat.cc:183
poly pp
Definition: myNF.cc:296
static coeffs numbercoeffs(number n, coeffs c)
create Z/nA of type n_Zn
Definition: bigintmat.cc:22
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...
Definition: bigintmat.cc:1297
int j
Definition: myNF.cc:70
bigintmat * bimMult(bigintmat *a, bigintmat *b)
Definition: bigintmat.cc:256
static number bimFarey(bigintmat *A, number N, bigintmat *L)
Definition: bigintmat.cc:2058
static void reduce_mod_howell(bigintmat *A, bigintmat *b, bigintmat *eps, bigintmat *x)
Definition: bigintmat.cc:1960
void extendCols(int i)
append i zero-columns to the matrix
Definition: bigintmat.cc:1086
#define assume(x)
Definition: mod2.h:403
void swapMatrix(bigintmat *a)
Definition: bigintmat.cc:1576
The main handler for Singular numbers which are suitable for Singular polynomials.
bool skalmult(number b, coeffs c)
Multipliziert zur Matrix den Skalar b hinzu.
Definition: bigintmat.cc:948
const ring R
Definition: DebugPrint.cc:36
int cols() const
Definition: bigintmat.h:145
int m
Definition: cfEzgcd.cc:119
only used if HAVE_RINGS is defined
Definition: coeffs.h:43
int i
Definition: cfEzgcd.cc:123
void PrintS(const char *s)
Definition: reporter.cc:284
static FORCE_INLINE BOOLEAN n_IsZero(number n, const coeffs r)
TRUE iff &#39;n&#39; represents the zero element.
Definition: coeffs.h:468
bigintmat * bimChangeCoeff(bigintmat *a, coeffs cnew)
Liefert Kopier von Matrix a zurück, mit coeffs cnew statt den ursprünglichen.
Definition: bigintmat.cc:1814
static FORCE_INLINE n_coeffType getCoeffType(const coeffs r)
Returns the type of coeffs domain.
Definition: coeffs.h:425
#define NULL
Definition: omList.c:10
coeffs basecoeffs() const
Definition: bigintmat.h:147
static FORCE_INLINE void n_Delete(number *p, const coeffs r)
delete &#39;p&#39;
Definition: coeffs.h:459
int isZero()
Definition: bigintmat.cc:1373
const poly b
Definition: syzextra.cc:213
void howell()
dito, but Howell form (only different for zero-divsors)
Definition: bigintmat.cc:1595
void nKillChar(coeffs r)
undo all initialisations
Definition: numbers.cc:496

§ solveAx_howell()

static number solveAx_howell ( bigintmat A,
bigintmat b,
bigintmat x,
bigintmat kern 
)
static

Definition at line 2308 of file bigintmat.cc.

2309 {
2310  // try to solve Ax=b, more precisely, find
2311  // number d
2312  // bigintmat x
2313  // sth. Ax=db
2314  // where d is small-ish (divides the determinant of A if this makes sense)
2315  // return 0 if there is no solution.
2316  //
2317  // if kern is non-NULL, return a basis for the kernel
2318 
2319  //Algo: we do row-howell (triangular matrix). The idea is
2320  // Ax = b <=> AT T^-1x = b
2321  // y := T^-1 x, solve AT y = b
2322  // and return Ty.
2323  //Howell does not compute the trafo, hence we need to cheat:
2324  //B := (I_n | A^t)^t, then the top part of the Howell form of
2325  //B will give a useful trafo
2326  //Then we can find x by back-substitution and lcm/gcd to find the denominator
2327  //The defining property of Howell makes this work.
2328 
2329  coeffs R = A->basecoeffs();
2330  bigintmat *m = prependIdentity(A);
2331  m->howell(); // since m contains the identity, we'll have A->cols()
2332  // many cols.
2333  number den = n_Init(1, R);
2334 
2335  bigintmat * B = new bigintmat(A->rows(), 1, R);
2336  for(int i=1; i<= b->cols(); i++)
2337  {
2338  int A_col = A->cols();
2339  b->getcol(i, B);
2340  B->skalmult(den, R);
2341  for(int j = B->rows(); j>0; j--)
2342  {
2343  number Ai = m->view(m->rows()-B->rows() + j, A_col);
2344  if (n_IsZero(Ai, R) &&
2345  n_IsZero(B->view(j, 1), R))
2346  {
2347  continue; //all is fine: 0*x = 0
2348  }
2349  else if (n_IsZero(B->view(j, 1), R))
2350  {
2351  x->rawset(x->rows() - B->rows() + j, i, n_Init(0, R));
2352  A_col--;
2353  }
2354  else if (n_IsZero(Ai, R))
2355  {
2356  delete m;
2357  delete B;
2358  n_Delete(&den, R);
2359  return 0;
2360  }
2361  else
2362  {
2363  // solve ax=db, possibly enlarging d
2364  // so x = db/a
2365  number Bj = B->view(j, 1);
2366  number g = n_Gcd(Bj, Ai, R);
2367  number xi;
2368  if (n_Equal(Ai, g, R))
2369  { //good: den stable!
2370  xi = n_Div(Bj, Ai, R);
2371  }
2372  else
2373  { //den <- den * (a/g), so old sol. needs to be adjusted
2374  number inc_d = n_Div(Ai, g, R);
2375  n_InpMult(den, inc_d, R);
2376  x->skalmult(inc_d, R);
2377  B->skalmult(inc_d, R);
2378  xi = n_Div(Bj, g, R);
2379  n_Delete(&inc_d, R);
2380  } //now for the back-substitution:
2381  x->rawset(x->rows() - B->rows() + j, i, xi);
2382  for(int k=j; k>0; k--)
2383  {
2384  //B[k] = B[k] - x[k]A[k][j]
2385  number s = n_Mult(xi, m->view(m->rows()-B->rows() + k, A_col), R);
2386  B->rawset(k, 1, n_Sub(B->view(k, 1), s, R));
2387  n_Delete(&s, R);
2388  }
2389  n_Delete(&g, R);
2390  A_col--;
2391  }
2392  if (!A_col)
2393  {
2394  if (B->isZero()) break;
2395  else
2396  {
2397  delete m;
2398  delete B;
2399  n_Delete(&den, R);
2400  return 0;
2401  }
2402  }
2403  }
2404  }
2405  delete B;
2406  bigintmat *T = new bigintmat(A->cols(), A->cols(), R);
2407  T->copySubmatInto(m, 1, 1, A->cols(), A->cols(), 1, 1);
2408  if (kern)
2409  {
2410  int i, j;
2411  for(i=1; i<= A->cols(); i++)
2412  {
2413  for(j=m->rows(); j>A->cols(); j--)
2414  {
2415  if (!n_IsZero(m->view(j, i), R)) break;
2416  }
2417  if (j>A->cols()) break;
2418  }
2419  Print("Found nullity (kern dim) of %d\n", i-1);
2420  bigintmat * ker = new bigintmat(A->rows(), i-1, R);
2421  ker->copySubmatInto(T, 1, 1, A->rows(), i-1, 1, 1);
2422  kern->swapMatrix(ker);
2423  delete ker;
2424  }
2425  delete m;
2426  bigintmat * y = bimMult(T, x);
2427  x->swapMatrix(y);
2428  delete y;
2429  x->simplifyContentDen(&den);
2430 #if 0
2431  PrintS("sol = 1/");
2432  n_Print(den, R);
2433  PrintS(" *\n");
2434  x->Print();
2435  PrintLn();
2436 #endif
2437  return den;
2438 }
static FORCE_INLINE number n_Sub(number a, number b, const coeffs r)
return the difference of &#39;a&#39; and &#39;b&#39;, i.e., a-b
Definition: coeffs.h:673
static FORCE_INLINE number n_Gcd(number a, number b, const coeffs r)
in Z: return the gcd of &#39;a&#39; and &#39;b&#39; in Z/nZ, Z/2^kZ: computed as in the case Z in Z/pZ...
Definition: coeffs.h:690
const CanonicalForm int s
Definition: facAbsFact.cc:55
const CanonicalForm int const CFList const Variable & y
Definition: facAbsFact.cc:57
void PrintLn()
Definition: reporter.cc:310
#define Print
Definition: emacs.cc:83
static bigintmat * prependIdentity(bigintmat *A)
Definition: bigintmat.cc:2046
void simplifyContentDen(number *den)
ensures that Gcd(den, content)=1 < enden hier wieder
Definition: bigintmat.cc:2698
static FORCE_INLINE void n_InpMult(number &a, number b, const coeffs r)
multiplication of &#39;a&#39; and &#39;b&#39;; replacement of &#39;a&#39; by the product a*b
Definition: coeffs.h:645
Matrices of numbers.
Definition: bigintmat.h:51
int rows() const
Definition: bigintmat.h:146
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:542
g
Definition: cfModGcd.cc:4031
int k
Definition: cfEzgcd.cc:93
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:197
static FORCE_INLINE number n_Mult(number a, number b, const coeffs r)
return the product of &#39;a&#39; and &#39;b&#39;, i.e., a*b
Definition: coeffs.h:640
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...
Definition: bigintmat.cc:1297
int j
Definition: myNF.cc:70
bigintmat * bimMult(bigintmat *a, bigintmat *b)
Definition: bigintmat.cc:256
void swapMatrix(bigintmat *a)
Definition: bigintmat.cc:1576
The main handler for Singular numbers which are suitable for Singular polynomials.
bool skalmult(number b, coeffs c)
Multipliziert zur Matrix den Skalar b hinzu.
Definition: bigintmat.cc:948
const ring R
Definition: DebugPrint.cc:36
number view(int i, int j) const
view an entry an entry. NOTE: starts at [1,1]
Definition: bigintmat.cc:128
int cols() const
Definition: bigintmat.h:145
int m
Definition: cfEzgcd.cc:119
int i
Definition: cfEzgcd.cc:123
void PrintS(const char *s)
Definition: reporter.cc:284
static FORCE_INLINE BOOLEAN n_IsZero(number n, const coeffs r)
TRUE iff &#39;n&#39; represents the zero element.
Definition: coeffs.h:468
void Print()
IO: simply prints the matrix to the current output (screen?)
Definition: bigintmat.cc:446
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:757
CanonicalForm den(const CanonicalForm &f)
static FORCE_INLINE number n_Div(number a, number b, const coeffs r)
return the quotient of &#39;a&#39; and &#39;b&#39;, i.e., a/b; raises an error if &#39;b&#39; is not invertible in r exceptio...
Definition: coeffs.h:619
b *CanonicalForm B
Definition: facBivar.cc:51
coeffs basecoeffs() const
Definition: bigintmat.h:147
static FORCE_INLINE BOOLEAN n_Equal(number a, number b, const coeffs r)
TRUE iff &#39;a&#39; and &#39;b&#39; represent the same number; they may have different representations.
Definition: coeffs.h:464
static FORCE_INLINE void n_Delete(number *p, const coeffs r)
delete &#39;p&#39;
Definition: coeffs.h:459
static jList * T
Definition: janet.cc:37
int isZero()
Definition: bigintmat.cc:1373
void howell()
dito, but Howell form (only different for zero-divsors)
Definition: bigintmat.cc:1595
void n_Print(number &a, const coeffs r)
print a number (BEWARE of string buffers!) mostly for debugging
Definition: numbers.cc:568