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)
 
#define MAX(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

#define MAX (   a,
  b 
)    (a > b ? a : b)
#define MIN (   a,
  b 
)    (a < b ? a : b)
#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

intvec* bim2iv ( bigintmat b)

Definition at line 341 of file bigintmat.cc.

342 {
343  intvec * iv = new intvec(b->rows(), b->cols(), 0);
344  for (int i=0; i<(b->rows())*(b->cols()); i++)
345  (*iv)[i] = n_Int((*b)[i], b->basecoeffs()); // Geht das so?
346  return iv;
347 }
Definition: intvec.h:16
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:548
int i
Definition: cfEzgcd.cc:123
int cols() const
Definition: bigintmat.h:128
int rows() const
Definition: bigintmat.h:129
coeffs basecoeffs() const
Definition: bigintmat.h:130
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 180 of file bigintmat.cc.

181 {
182  if (a->cols() != b->cols()) return NULL;
183  if (a->rows() != b->rows()) return NULL;
184  if (a->basecoeffs() != b->basecoeffs()) { return NULL; }
185 
186  const coeffs basecoeffs = a->basecoeffs();
187 
188  int i;
189 
190  bigintmat * bim = new bigintmat(a->rows(), a->cols(), basecoeffs);
191 
192  for (i=a->rows()*a->cols()-1;i>=0; i--)
193  bim->rawset(i, n_Add((*a)[i], (*b)[i], basecoeffs), basecoeffs);
194 
195  return bim;
196 }
Matrices of numbers.
Definition: bigintmat.h:32
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:180
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 'a' and 'b', i.e., a+b
Definition: coeffs.h:655
int i
Definition: cfEzgcd.cc:123
int cols() const
Definition: bigintmat.h:128
int rows() const
Definition: bigintmat.h:129
#define NULL
Definition: omList.c:10
coeffs basecoeffs() const
Definition: bigintmat.h:130
bigintmat* bimAdd ( bigintmat a,
int  b 
)

Definition at line 197 of file bigintmat.cc.

198 {
199 
200  const int mn = a->rows()*a->cols();
201 
202  const coeffs basecoeffs = a->basecoeffs();
203  number bb=n_Init(b,basecoeffs);
204 
205  int i;
206 
207  bigintmat * bim = new bigintmat(a->rows(),a->cols() , basecoeffs);
208 
209  for (i=0; i<mn; i++)
210  bim->rawset(i, n_Add((*a)[i], bb, basecoeffs), basecoeffs);
211 
212  n_Delete(&bb,basecoeffs);
213  return bim;
214 }
Matrices of numbers.
Definition: bigintmat.h:32
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
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:180
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 'a' and 'b', i.e., a+b
Definition: coeffs.h:655
int i
Definition: cfEzgcd.cc:123
int cols() const
Definition: bigintmat.h:128
int rows() const
Definition: bigintmat.h:129
coeffs basecoeffs() const
Definition: bigintmat.h:130
static FORCE_INLINE void n_Delete(number *p, const coeffs r)
delete 'p'
Definition: coeffs.h:456
const poly b
Definition: syzextra.cc:213
bigintmat* bimChangeCoeff ( bigintmat a,
coeffs  cnew 
)

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

Definition at line 1706 of file bigintmat.cc.

1707 {
1708  coeffs cold = a->basecoeffs();
1709  bigintmat *b = new bigintmat(a->rows(), a->cols(), cnew);
1710  // Erzeugt Karte von alten coeffs nach neuen
1711  nMapFunc f = n_SetMap(cold, cnew);
1712  number t1;
1713  number t2;
1714  // apply map to all entries.
1715  for (int i=1; i<=a->rows(); i++)
1716  {
1717  for (int j=1; j<=a->cols(); j++)
1718  {
1719  t1 = a->get(i, j);
1720  t2 = f(t1, cold, cnew);
1721  b->set(i, j, t2);
1722  n_Delete(&t1, cold);
1723  n_Delete(&t2, cnew);
1724  }
1725  }
1726  return b;
1727 }
Matrices of numbers.
Definition: bigintmat.h:32
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
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:72
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:720
int cols() const
Definition: bigintmat.h:128
int rows() const
Definition: bigintmat.h:129
coeffs basecoeffs() const
Definition: bigintmat.h:130
static FORCE_INLINE void n_Delete(number *p, const coeffs r)
delete 'p'
Definition: coeffs.h:456
const poly b
Definition: syzextra.cc:213
number get(int i, int j) const
get a copy of an entry. NOTE: starts at [1,1]
Definition: bigintmat.cc:117
bigintmat* bimCopy ( const bigintmat b)

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

Definition at line 405 of file bigintmat.cc.

406 {
407  if (b == NULL)
408  return NULL;
409 
410  return new bigintmat(b);
411 }
Matrices of numbers.
Definition: bigintmat.h:32
#define NULL
Definition: omList.c:10
static number bimFarey ( bigintmat A,
number  N,
bigintmat L 
)
static

Definition at line 1935 of file bigintmat.cc.

1935  {
1936  coeffs Z = A->basecoeffs(),
1937  Q = nInitChar(n_Q, 0);
1938  number den = n_Init(1, Z);
1939  nMapFunc f = n_SetMap(Q, Z);
1940 
1941  for(int i=1; i<= A->rows(); i++) {
1942  for(int j=1; j<= A->cols(); j++) {
1943  number ad = n_Mult(den, A->view(i, j), Z);
1944  number re = n_IntMod(ad, N, Z);
1945  n_Delete(&ad, Z);
1946  number q = n_Farey(re, N, Z);
1947  n_Delete(&re, Z);
1948  if (!q) {
1949  n_Delete(&ad, Z);
1950  n_Delete(&den, Z);
1951  return NULL;
1952  }
1953 
1954  number d = n_GetDenom(q, Q),
1955  n = n_GetNumerator(q, Q);
1956 
1957  n_Delete(&q, Q);
1958  n_Delete(&ad, Z);
1959  number dz = f(d, Q, Z),
1960  nz = f(n, Q, Z);
1961  n_Delete(&d, Q);
1962  n_Delete(&n, Q);
1963 
1964  if (!n_IsOne(dz, Z)) {
1965  L->skalmult(dz, Z);
1966  n_InpMult(den, dz, Z);
1967 #if 0
1968  Print("den increasing to ");
1969  n_Print(den, Z);
1970  Print("\n");
1971 #endif
1972  }
1973  n_Delete(&dz, Z);
1974  L->rawset(i, j, nz);
1975  }
1976  }
1977 
1978  nKillChar(Q);
1979  Print("bimFarey worked\n");
1980 #if 0
1981  L->Print();
1982  Print("\n * 1/");
1983  n_Print(den, Z);
1984  Print("\n");
1985 #endif
1986  return den;
1987 }
number view(int i, int j) const
view an entry an entry. NOTE: starts at [1,1]
Definition: bigintmat.cc:125
static FORCE_INLINE number n_IntMod(number a, number b, const coeffs r)
for r a field, return n_Init(0,r) otherwise: n_Div(a,b,r)*b+n_IntMod(a,b,r)==a
Definition: coeffs.h:627
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:609
#define Print
Definition: emacs.cc:83
static FORCE_INLINE void n_InpMult(number &a, number b, const coeffs r)
multiplication of 'a' and 'b'; replacement of 'a' by the product a*b
Definition: coeffs.h:640
static FORCE_INLINE BOOLEAN n_IsOne(number n, const coeffs r)
TRUE iff 'n' represents the one element.
Definition: coeffs.h:469
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:539
const CanonicalForm CFMap CFMap int &both_non_zero int n
Definition: cfEzgcd.cc:52
#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:180
static FORCE_INLINE number n_Mult(number a, number b, const coeffs r)
return the product of 'a' and 'b', i.e., a*b
Definition: coeffs.h:635
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:72
bool skalmult(number b, coeffs c)
Multipliziert zur Matrix den Skalar b hinzu.
Definition: bigintmat.cc:906
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:720
int cols() const
Definition: bigintmat.h:128
void Print()
IO: simply prints the matrix to the current output (screen?)
Definition: bigintmat.cc:440
static FORCE_INLINE number n_Farey(number a, number b, const coeffs r)
Definition: coeffs.h:785
int rows() const
Definition: bigintmat.h:129
#define NULL
Definition: omList.c:10
CanonicalForm den(const CanonicalForm &f)
coeffs basecoeffs() const
Definition: bigintmat.h:130
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:604
static FORCE_INLINE void n_Delete(number *p, const coeffs r)
delete 'p'
Definition: coeffs.h:456
void nKillChar(coeffs r)
undo all initialisations
Definition: numbers.cc:488
void n_Print(number &a, const coeffs r)
print a number (BEWARE of string buffers!) mostly for debugging
Definition: numbers.cc:549
coeffs nInitChar(n_coeffType t, void *parameter)
one-time initialisations for new coeffs in case of an error return NULL
Definition: numbers.cc:327
bigintmat* bimMult ( bigintmat a,
bigintmat b 
)

Definition at line 253 of file bigintmat.cc.

254 {
255  const int ca = a->cols();
256  const int cb = b->cols();
257 
258  const int ra = a->rows();
259  const int rb = b->rows();
260 
261  if (ca != rb)
262  {
263 #ifndef SING_NDEBUG
264  Werror("wrong bigintmat sizes at multiplication a * b: acols: %d != brows: %d\n", ca, rb);
265 #endif
266  return NULL;
267  }
268 
269  assume (ca == rb);
270 
271  if (a->basecoeffs() != b->basecoeffs()) { return NULL; }
272 
273  const coeffs basecoeffs = a->basecoeffs();
274 
275  int i, j, k;
276 
277  number sum;
278 
279  bigintmat * bim = new bigintmat(ra, cb, basecoeffs);
280 
281  for (i=1; i<=ra; i++)
282  for (j=1; j<=cb; j++)
283  {
284  sum = n_Init(0, basecoeffs);
285 
286  for (k=1; k<=ca; k++)
287  {
288  number prod = n_Mult( BIMATELEM(*a, i, k), BIMATELEM(*b, k, j), basecoeffs);
289 
290  number sum2 = n_Add(sum, prod, basecoeffs); // no inplace add :(
291 
292  n_Delete(&sum, basecoeffs); n_Delete(&prod, basecoeffs);
293 
294  sum = sum2;
295  }
296  bim->rawset(i, j, sum, basecoeffs);
297  }
298  return bim;
299 }
Matrices of numbers.
Definition: bigintmat.h:32
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
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:180
static FORCE_INLINE number n_Mult(number a, number b, const coeffs r)
return the product of 'a' and 'b', i.e., a*b
Definition: coeffs.h:635
int j
Definition: myNF.cc:70
#define assume(x)
Definition: mod2.h:405
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 'a' and 'b', i.e., a+b
Definition: coeffs.h:655
int i
Definition: cfEzgcd.cc:123
int cols() const
Definition: bigintmat.h:128
#define BIMATELEM(M, I, J)
Definition: bigintmat.h:117
int rows() const
Definition: bigintmat.h:129
#define NULL
Definition: omList.c:10
fq_nmod_poly_t prod
Definition: facHensel.cc:95
coeffs basecoeffs() const
Definition: bigintmat.h:130
static FORCE_INLINE void n_Delete(number *p, const coeffs r)
delete 'p'
Definition: coeffs.h:456
void Werror(const char *fmt,...)
Definition: reporter.cc:199
bigintmat* bimMult ( bigintmat a,
int  b 
)

Definition at line 301 of file bigintmat.cc.

302 {
303 
304  const int mn = a->rows()*a->cols();
305 
306  const coeffs basecoeffs = a->basecoeffs();
307  number bb=n_Init(b,basecoeffs);
308 
309  int i;
310 
311  bigintmat * bim = new bigintmat(a->rows(),a->cols() , basecoeffs);
312 
313  for (i=0; i<mn; i++)
314  bim->rawset(i, n_Mult((*a)[i], bb, basecoeffs), basecoeffs);
315 
316  n_Delete(&bb,basecoeffs);
317  return bim;
318 }
Matrices of numbers.
Definition: bigintmat.h:32
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
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:180
static FORCE_INLINE number n_Mult(number a, number b, const coeffs r)
return the product of 'a' and 'b', i.e., a*b
Definition: coeffs.h:635
The main handler for Singular numbers which are suitable for Singular polynomials.
int i
Definition: cfEzgcd.cc:123
int cols() const
Definition: bigintmat.h:128
int rows() const
Definition: bigintmat.h:129
coeffs basecoeffs() const
Definition: bigintmat.h:130
static FORCE_INLINE void n_Delete(number *p, const coeffs r)
delete 'p'
Definition: coeffs.h:456
const poly b
Definition: syzextra.cc:213
bigintmat* bimMult ( bigintmat a,
number  b,
const coeffs  cf 
)

Definition at line 320 of file bigintmat.cc.

321 {
322  if (cf!=a->basecoeffs()) return NULL;
323 
324  const int mn = a->rows()*a->cols();
325 
326  const coeffs basecoeffs = a->basecoeffs();
327 
328  int i;
329 
330  bigintmat * bim = new bigintmat(a->rows(),a->cols() , basecoeffs);
331 
332  for (i=0; i<mn; i++)
333  bim->rawset(i, n_Mult((*a)[i], b, basecoeffs), basecoeffs);
334 
335  return bim;
336 }
Matrices of numbers.
Definition: bigintmat.h:32
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:180
static FORCE_INLINE number n_Mult(number a, number b, const coeffs r)
return the product of 'a' and 'b', i.e., a*b
Definition: coeffs.h:635
The main handler for Singular numbers which are suitable for Singular polynomials.
int i
Definition: cfEzgcd.cc:123
int cols() const
Definition: bigintmat.h:128
int rows() const
Definition: bigintmat.h:129
#define NULL
Definition: omList.c:10
coeffs basecoeffs() const
Definition: bigintmat.h:130
const poly b
Definition: syzextra.cc:213
void bimMult ( bigintmat a,
bigintmat b,
bigintmat c 
)

Multipliziert Matrix a und b und speichert Ergebnis in c.

Definition at line 1834 of file bigintmat.cc.

1835 {
1836  if (!nCoeffs_are_equal(a->basecoeffs(), b->basecoeffs())) {
1837  Werror("Error in bimMult. Coeffs do not agree!");
1838  return;
1839  }
1840  if ((a->rows() != c->rows()) || (b->cols() != c->cols()) || (a->cols() != b->rows())) {
1841  Werror("Error in bimMult. Dimensions do not agree!");
1842  return;
1843  }
1844  bigintmat *tmp = bimMult(a, b);
1845  c->copy(tmp);
1846 
1847  delete tmp;
1848 }
Matrices of numbers.
Definition: bigintmat.h:32
bigintmat * bimMult(bigintmat *a, bigintmat *b)
Definition: bigintmat.cc:253
int cols() const
Definition: bigintmat.h:128
int rows() const
Definition: bigintmat.h:129
coeffs basecoeffs() const
Definition: bigintmat.h:130
bool copy(bigintmat *b)
Kopiert Einträge von b auf Bigintmat.
Definition: bigintmat.cc:1178
void Werror(const char *fmt,...)
Definition: reporter.cc:199
bool nCoeffs_are_equal(coeffs r, coeffs s)
Definition: bigintmat.cc:2473
bigintmat* bimSub ( bigintmat a,
bigintmat b 
)

Definition at line 216 of file bigintmat.cc.

217 {
218  if (a->cols() != b->cols()) return NULL;
219  if (a->rows() != b->rows()) return NULL;
220  if (a->basecoeffs() != b->basecoeffs()) { return NULL; }
221 
222  const coeffs basecoeffs = a->basecoeffs();
223 
224  int i;
225 
226  bigintmat * bim = new bigintmat(a->rows(), a->cols(), basecoeffs);
227 
228  for (i=a->rows()*a->cols()-1;i>=0; i--)
229  bim->rawset(i, n_Sub((*a)[i], (*b)[i], basecoeffs), basecoeffs);
230 
231  return bim;
232 }
static FORCE_INLINE number n_Sub(number a, number b, const coeffs r)
return the difference of 'a' and 'b', i.e., a-b
Definition: coeffs.h:668
Matrices of numbers.
Definition: bigintmat.h:32
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:180
The main handler for Singular numbers which are suitable for Singular polynomials.
int i
Definition: cfEzgcd.cc:123
int cols() const
Definition: bigintmat.h:128
int rows() const
Definition: bigintmat.h:129
#define NULL
Definition: omList.c:10
coeffs basecoeffs() const
Definition: bigintmat.h:130
bigintmat* bimSub ( bigintmat a,
int  b 
)

Definition at line 234 of file bigintmat.cc.

235 {
236  const int mn = a->rows()*a->cols();
237 
238  const coeffs basecoeffs = a->basecoeffs();
239  number bb=n_Init(b,basecoeffs);
240 
241  int i;
242 
243  bigintmat * bim = new bigintmat(a->rows(),a->cols() , basecoeffs);
244 
245  for (i=0; i<mn; i++)
246  bim->rawset(i, n_Sub((*a)[i], bb, basecoeffs), basecoeffs);
247 
248  n_Delete(&bb,basecoeffs);
249  return bim;
250 }
static FORCE_INLINE number n_Sub(number a, number b, const coeffs r)
return the difference of 'a' and 'b', i.e., a-b
Definition: coeffs.h:668
Matrices of numbers.
Definition: bigintmat.h:32
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
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:180
The main handler for Singular numbers which are suitable for Singular polynomials.
int i
Definition: cfEzgcd.cc:123
int cols() const
Definition: bigintmat.h:128
int rows() const
Definition: bigintmat.h:129
coeffs basecoeffs() const
Definition: bigintmat.h:130
static FORCE_INLINE void n_Delete(number *p, const coeffs r)
delete 'p'
Definition: coeffs.h:456
const poly b
Definition: syzextra.cc:213
void diagonalForm ( bigintmat A,
bigintmat **  S,
bigintmat **  T 
)

Definition at line 2323 of file bigintmat.cc.

2324 {
2325  bigintmat * t, *s, *a=A;
2326  coeffs R = a->basecoeffs();
2327  if (T) {
2328  *T = new bigintmat(a->cols(), a->cols(), R),
2329  (*T)->one();
2330  t = new bigintmat(*T);
2331  } else {
2332  t = *T;
2333  }
2334 
2335  if (S) {
2336  *S = new bigintmat(a->rows(), a->rows(), R);
2337  (*S)->one();
2338  s = new bigintmat(*S);
2339  } else {
2340  s = *S;
2341  }
2342 
2343  int flip=0;
2344  do {
2345  bigintmat * x, *X;
2346  if (flip) {
2347  x = s;
2348  X = *S;
2349  } else {
2350  x = t;
2351  X = *T;
2352  }
2353 
2354  if (x) {
2355  x->one();
2356  bigintmat * r = new bigintmat(a->rows()+a->cols(), a->cols(), R);
2357  bigintmat * rw = new bigintmat(1, a->cols(), R);
2358  for(int i=0; i<a->cols(); i++) {
2359  x->getrow(i+1, rw);
2360  r->setrow(i+1, rw);
2361  }
2362  for (int i=0; i<a->rows(); i++) {
2363  a->getrow(i+1, rw);
2364  r->setrow(i+a->cols()+1, rw);
2365  }
2366  r->hnf();
2367  for(int i=0; i<a->cols(); i++) {
2368  r->getrow(i+1, rw);
2369  x->setrow(i+1, rw);
2370  }
2371  for(int i=0; i<a->rows(); i++) {
2372  r->getrow(i+a->cols()+1, rw);
2373  a->setrow(i+1, rw);
2374  }
2375  delete rw;
2376  delete r;
2377 
2378 #if 0
2379  Print("X: %ld\n", X);
2380  X->Print();
2381  Print("\nx: %ld\n", x);
2382  x->Print();
2383 #endif
2384  bimMult(X, x, X);
2385 #if 0
2386  Print("\n2:X: %ld %ld %ld\n", X, *S, *T);
2387  X->Print();
2388  Print("\n2:x: %ld\n", x);
2389  x->Print();
2390  Print("\n");
2391 #endif
2392  } else {
2393  a->hnf();
2394  }
2395 
2396  int diag = 1;
2397  for(int i=a->rows(); diag && i>0; i--) {
2398  for(int j=a->cols(); j>0; j--) {
2399  if ((a->rows()-i)!=(a->cols()-j) && !n_IsZero(a->view(i, j), R)) {
2400  diag = 0;
2401  break;
2402  }
2403  }
2404  }
2405 #if 0
2406  Print("Diag ? %d\n", diag);
2407  a->Print();
2408  Print("\n");
2409 #endif
2410  if (diag) break;
2411 
2412  a = a->transpose(); // leaks - I need to write inpTranspose
2413  flip = 1-flip;
2414  } while (1);
2415  if (flip)
2416  a = a->transpose();
2417 
2418  if (S) *S = (*S)->transpose();
2419  if (s) delete s;
2420  if (t) delete t;
2421  A->copy(a);
2422 }
bigintmat * transpose()
Definition: bigintmat.cc:38
number view(int i, int j) const
view an entry an entry. NOTE: starts at [1,1]
Definition: bigintmat.cc:125
const CanonicalForm int s
Definition: facAbsFact.cc:55
const poly a
Definition: syzextra.cc:212
#define Print
Definition: emacs.cc:83
void getrow(int i, bigintmat *a)
Schreibt i-te Zeile in Vektor (Matrix) a.
Definition: bigintmat.cc:781
Matrices of numbers.
Definition: bigintmat.h:32
void setrow(int i, bigintmat *m)
Setzt i-te Zeile gleich übergebenem Vektor (Matrix) m.
Definition: bigintmat.cc:841
const ring r
Definition: syzextra.cc:208
int j
Definition: myNF.cc:70
bigintmat * bimMult(bigintmat *a, bigintmat *b)
Definition: bigintmat.cc:253
The main handler for Singular numbers which are suitable for Singular polynomials.
#define A
Definition: sirandom.c:23
void hnf()
transforms INPLACE to HNF
Definition: bigintmat.cc:1562
int i
Definition: cfEzgcd.cc:123
static FORCE_INLINE BOOLEAN n_IsZero(number n, const coeffs r)
TRUE iff 'n' represents the zero element.
Definition: coeffs.h:465
int cols() const
Definition: bigintmat.h:128
void Print()
IO: simply prints the matrix to the current output (screen?)
Definition: bigintmat.cc:440
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:40
int rows() const
Definition: bigintmat.h:129
coeffs basecoeffs() const
Definition: bigintmat.h:130
#define R
Definition: sirandom.c:26
bool copy(bigintmat *b)
Kopiert Einträge von b auf Bigintmat.
Definition: bigintmat.cc:1178
Variable x
Definition: cfModGcd.cc:4023
static jList * T
Definition: janet.cc:37
void one()
Macht Matrix (Falls quadratisch) zu Einheitsmatrix.
Definition: bigintmat.cc:1238
static int findLongest ( int *  a,
int  length 
)
static

Definition at line 535 of file bigintmat.cc.

536 {
537  int l = 0;
538  int index;
539  for (int i=0; i<length; i++)
540  {
541  if (a[i] > l)
542  {
543  l = a[i];
544  index = i;
545  }
546  }
547  return index;
548 }
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:597
int l
Definition: cfEzgcd.cc:94
static int getShorter ( int *  a,
int  l,
int  j,
int  cols,
int  rows 
)
static

Definition at line 550 of file bigintmat.cc.

551 {
552  int sndlong = 0;
553  int min;
554  for (int i=0; i<rows; i++)
555  {
556  int index = cols*i+j;
557  if ((a[index] > sndlong) && (a[index] < l))
558  {
559  min = floor(log10((double)cols))+floor(log10((double)rows))+5;
560  if ((a[index] < min) && (min < l))
561  sndlong = min;
562  else
563  sndlong = a[index];
564  }
565  }
566  if (sndlong == 0)
567  {
568  min = floor(log10((double)cols))+floor(log10((double)rows))+5;
569  if (min < l)
570  sndlong = min;
571  else
572  sndlong = 1;
573  }
574  return sndlong;
575 }
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:597
int l
Definition: cfEzgcd.cc:94
static int intArrSum ( int *  a,
int  length 
)
static

Definition at line 527 of file bigintmat.cc.

528 {
529  int sum = 0;
530  for (int i=0; i<length; i++)
531  sum += a[i];
532  return sum;
533 }
const poly a
Definition: syzextra.cc:212
int i
Definition: cfEzgcd.cc:123
bigintmat* iv2bim ( intvec b,
const coeffs  C 
)

Definition at line 349 of file bigintmat.cc.

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

2428  {
2429 #if 0
2430  Print("Kernel of ");
2431  a->Print();
2432  Print(" modulo ");
2433  n_Print(p, q);
2434  Print("\n");
2435 #endif
2436 
2437  coeffs coe = numbercoeffs(p, q);
2438  bigintmat *m = bimChangeCoeff(a, coe), *U, *V;
2439  diagonalForm(m, &U, &V);
2440 #if 0
2441  Print("\ndiag form: ");
2442  m->Print();
2443  Print("\nU:\n");
2444  U->Print();
2445  Print("\nV:\n");
2446  V->Print();
2447  Print("\n");
2448 #endif
2449 
2450  int rg = 0;
2451 #undef MIN
2452 #define MIN(a,b) (a < b ? a : b)
2453  for(rg=0; rg<MIN(m->rows(), m->cols()) && !n_IsZero(m->view(m->rows()-rg,m->cols()-rg), coe); rg++);
2454 
2455 #undef MAX
2456 #define MAX(a,b) (a > b ? a : b)
2457  bigintmat * k = new bigintmat(m->cols(), m->rows(), coe);
2458  for(int i=0; i<rg; i++) {
2459  number A = n_Ann(m->view(m->rows()-i, m->cols()-i), coe);
2460  k->set(m->cols()-i, i+1, A);
2461  n_Delete(&A, coe);
2462  }
2463  for(int i=rg; i<m->cols(); i++) {
2464  k->set(m->cols()-i, i+1-rg, n_Init(1, coe));
2465  }
2466  bimMult(V, k, k);
2467  c->copy(bimChangeCoeff(k, q));
2468  return c->cols();
2469 }
number view(int i, int j) const
view an entry an entry. NOTE: starts at [1,1]
Definition: bigintmat.cc:125
#define Print
Definition: emacs.cc:83
return P p
Definition: myNF.cc:203
Matrices of numbers.
Definition: bigintmat.h:32
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
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:700
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
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:253
The main handler for Singular numbers which are suitable for Singular polynomials.
#define A
Definition: sirandom.c:23
int m
Definition: cfEzgcd.cc:119
int i
Definition: cfEzgcd.cc:123
static FORCE_INLINE BOOLEAN n_IsZero(number n, const coeffs r)
TRUE iff 'n' represents the zero element.
Definition: coeffs.h:465
bigintmat * bimChangeCoeff(bigintmat *a, coeffs cnew)
Liefert Kopier von Matrix a zurück, mit coeffs cnew statt den ursprünglichen.
Definition: bigintmat.cc:1706
int cols() const
Definition: bigintmat.h:128
void diagonalForm(bigintmat *A, bigintmat **S, bigintmat **T)
Definition: bigintmat.cc:2323
void Print()
IO: simply prints the matrix to the current output (screen?)
Definition: bigintmat.cc:440
int rows() const
Definition: bigintmat.h:129
bool copy(bigintmat *b)
Kopiert Einträge von b auf Bigintmat.
Definition: bigintmat.cc:1178
static FORCE_INLINE void n_Delete(number *p, const coeffs r)
delete 'p'
Definition: coeffs.h:456
void n_Print(number &a, const coeffs r)
print a number (BEWARE of string buffers!) mostly for debugging
Definition: numbers.cc:549
bool nCoeffs_are_equal ( coeffs  r,
coeffs  s 
)

Definition at line 2473 of file bigintmat.cc.

2473  {
2474  if ((r == NULL) || (s == NULL))
2475  return false;
2476  if ((getCoeffType(r)==n_Z) && (getCoeffType(s)==n_Z))
2477  return true;
2478  if ((getCoeffType(r)==n_Zp) && (getCoeffType(s)==n_Zp)) {
2479  if (r->ch == s->ch)
2480  return true;
2481  else
2482  return false;
2483  }
2484  // n_Zn stimmt wahrscheinlich noch nicht
2485  if ((getCoeffType(r)==n_Zn) && (getCoeffType(s)==n_Zn)) {
2486  if (r->ch == s->ch)
2487  return true;
2488  else
2489  return false;
2490  }
2491  if ((getCoeffType(r)==n_Q) && (getCoeffType(s)==n_Q))
2492  return true;
2493  // FALL n_Zn FEHLT NOCH!
2494  //if ((getCoeffType(r)==n_Zn) && (getCoeffType(s)==n_Zn))
2495  return false;
2496 }
only used if HAVE_RINGS is defined: ?
Definition: coeffs.h:43
rational (GMP) numbers
Definition: coeffs.h:31
{p < 2^31}
Definition: coeffs.h:30
only used if HAVE_RINGS is defined: ?
Definition: coeffs.h:42
static FORCE_INLINE n_coeffType getCoeffType(const coeffs r)
Returns the type of coeffs domain.
Definition: coeffs.h:422
#define NULL
Definition: omList.c:10
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:18
only used if HAVE_RINGS is defined: ?
Definition: coeffs.h:43
return P p
Definition: myNF.cc:203
const CanonicalForm CFMap CFMap int &both_non_zero int n
Definition: cfEzgcd.cc:52
poly pp
Definition: myNF.cc:296
static FORCE_INLINE void number2mpz(number n, coeffs c, mpz_t m)
Definition: coeffs.h:991
The main handler for Singular numbers which are suitable for Singular polynomials.
unsigned long exp
Definition: rmodulon.h:18
coeffs nInitChar(n_coeffType t, void *parameter)
one-time initialisations for new coeffs in case of an error return NULL
Definition: numbers.cc:327
bool operator!= ( const bigintmat lhr,
const bigintmat rhr 
)

Definition at line 174 of file bigintmat.cc.

175 {
176  return !(lhr==rhr);
177 }
bool operator== ( const bigintmat lhr,
const bigintmat rhr 
)

Definition at line 157 of file bigintmat.cc.

158 {
159  if (&lhr == &rhr) { return true; }
160  if (lhr.cols() != rhr.cols()) { return false; }
161  if (lhr.rows() != rhr.rows()) { return false; }
162  if (lhr.basecoeffs() != rhr.basecoeffs()) { return false; }
163 
164  const int l = (lhr.rows())*(lhr.cols());
165 
166  for (int i=0; i < l; i++)
167  {
168  if (!n_Equal(lhr[i], rhr[i], lhr.basecoeffs())) { return false; }
169  }
170 
171  return true;
172 }
int i
Definition: cfEzgcd.cc:123
int cols() const
Definition: bigintmat.h:128
int rows() const
Definition: bigintmat.h:129
coeffs basecoeffs() const
Definition: bigintmat.h:130
static FORCE_INLINE BOOLEAN n_Equal(number a, number b, const coeffs r)
TRUE iff 'a' and 'b' represent the same number; they may have different representations.
Definition: coeffs.h:461
int l
Definition: cfEzgcd.cc:94
static bigintmat* prependIdentity ( bigintmat A)
static

Definition at line 1923 of file bigintmat.cc.

1924 {
1925  coeffs R = A->basecoeffs();
1926  bigintmat *m = new bigintmat(A->rows()+A->cols(), A->cols(), R);
1927  m->copySubmatInto(A, 1, 1, A->rows(), A->cols(), A->cols()+1, 1);
1928  number one = n_Init(1, R);
1929  for(int i=1; i<= A->cols(); i++)
1930  m->set(i,i,one);
1931  n_Delete(&one, R);
1932  return m;
1933 }
Matrices of numbers.
Definition: bigintmat.h:32
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
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
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:1204
The main handler for Singular numbers which are suitable for Singular polynomials.
int m
Definition: cfEzgcd.cc:119
int i
Definition: cfEzgcd.cc:123
int cols() const
Definition: bigintmat.h:128
int rows() const
Definition: bigintmat.h:129
coeffs basecoeffs() const
Definition: bigintmat.h:130
#define R
Definition: sirandom.c:26
static FORCE_INLINE void n_Delete(number *p, const coeffs r)
delete 'p'
Definition: coeffs.h:456
static void reduce_mod_howell ( bigintmat A,
bigintmat b,
bigintmat eps,
bigintmat x 
)
static

Definition at line 1850 of file bigintmat.cc.

1850  {
1851  //write b = Ax + eps where eps is "small" in the sense of bounded by the
1852  //pivot entries in H. H does not need to be Howell (or HNF) but need
1853  //to be triagonal in the same direction.
1854  //b can have multiple columns.
1855 #if 0
1856  Print("reduce_mod_howell: A:\n");
1857  A->Print();
1858  Print("\nb:\n");
1859  b->Print();
1860 #endif
1861 
1862  coeffs R = A->basecoeffs();
1863  assume(x->basecoeffs() == R);
1864  assume(b->basecoeffs() == R);
1865  assume(eps->basecoeffs() == R);
1866  if (!A->cols()) {
1867  x->zero();
1868  eps->copy(b);
1869 
1870 #if 0
1871  Print("\nx:\n");
1872  x->Print();
1873  Print("\neps:\n");
1874  eps->Print();
1875  Print("\n****************************************\n");
1876 #endif
1877  return;
1878  }
1879 
1880  bigintmat * B = new bigintmat(b->rows(), 1, R);
1881  for(int i=1; i<= b->cols(); i++) {
1882  int A_col = A->cols();
1883  b->getcol(i, B);
1884  for(int j = B->rows(); j>0; j--) {
1885  number Ai = A->view(A->rows() - B->rows() + j, A_col);
1886  if (n_IsZero(Ai, R) &&
1887  n_IsZero(B->view(j, 1), R)) {
1888  continue; //all is fine: 0*x = 0
1889  } else if (n_IsZero(B->view(j, 1), R)) {
1890  x->rawset(x->rows() - B->rows() + j, i, n_Init(0, R));
1891  A_col--;
1892  } else if (n_IsZero(Ai, R)) {
1893  A_col--;
1894  } else {
1895  // "solve" ax=b, possibly enlarging d
1896  number Bj = B->view(j, 1);
1897  number q = n_Div(Bj, Ai, R);
1898  x->rawset(x->rows() - B->rows() + j, i, q);
1899  for(int k=j; k>B->rows() - A->rows(); k--) {
1900  //B[k] = B[k] - x[k]A[k][j]
1901  number s = n_Mult(q, A->view(A->rows() - B->rows() + k, A_col), R);
1902  B->rawset(k, 1, n_Sub(B->view(k, 1), s, R));
1903  n_Delete(&s, R);
1904  }
1905  A_col--;
1906  }
1907  if (!A_col) {
1908  break;
1909  }
1910  }
1911  eps->setcol(i, B);
1912  }
1913  delete B;
1914 #if 0
1915  Print("\nx:\n");
1916  x->Print();
1917  Print("\neps:\n");
1918  eps->Print();
1919  Print("\n****************************************\n");
1920 #endif
1921 }
static FORCE_INLINE number n_Sub(number a, number b, const coeffs r)
return the difference of 'a' and 'b', i.e., a-b
Definition: coeffs.h:668
number view(int i, int j) const
view an entry an entry. NOTE: starts at [1,1]
Definition: bigintmat.cc:125
const CanonicalForm int s
Definition: facAbsFact.cc:55
#define Print
Definition: emacs.cc:83
Matrices of numbers.
Definition: bigintmat.h:32
void setcol(int j, bigintmat *m)
Setzt j-te Spalte gleich übergebenem Vektor (Matrix) m.
Definition: bigintmat.cc:812
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
void zero()
Setzt alle Einträge auf 0.
Definition: bigintmat.cc:1256
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:180
static FORCE_INLINE number n_Mult(number a, number b, const coeffs r)
return the product of 'a' and 'b', i.e., a*b
Definition: coeffs.h:635
int j
Definition: myNF.cc:70
#define assume(x)
Definition: mod2.h:405
The main handler for Singular numbers which are suitable for Singular polynomials.
int i
Definition: cfEzgcd.cc:123
static FORCE_INLINE BOOLEAN n_IsZero(number n, const coeffs r)
TRUE iff 'n' represents the zero element.
Definition: coeffs.h:465
int cols() const
Definition: bigintmat.h:128
void Print()
IO: simply prints the matrix to the current output (screen?)
Definition: bigintmat.cc:440
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:743
int rows() const
Definition: bigintmat.h:129
static FORCE_INLINE number n_Div(number a, number b, const coeffs r)
return the quotient of 'a' and 'b', i.e., a/b; raises an error if 'b' is not invertible in r exceptio...
Definition: coeffs.h:615
b *CanonicalForm B
Definition: facBivar.cc:51
coeffs basecoeffs() const
Definition: bigintmat.h:130
#define R
Definition: sirandom.c:26
bool copy(bigintmat *b)
Kopiert Einträge von b auf Bigintmat.
Definition: bigintmat.cc:1178
static FORCE_INLINE void n_Delete(number *p, const coeffs r)
delete 'p'
Definition: coeffs.h:456
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 2281 of file bigintmat.cc.

2281  {
2282 #if 0
2283  Print("Solve Ax=b for A=\n");
2284  A->Print();
2285  Print("\nb = \n");
2286  b->Print();
2287  Print("\nx = \n");
2288  x->Print();
2289  Print("\n");
2290 #endif
2291 
2292  coeffs R = A->basecoeffs();
2293  assume (R == b->basecoeffs());
2294  assume (R == x->basecoeffs());
2295  assume ((x->cols() == b->cols()) && (x->rows() == A->cols()) && (A->rows() == b->rows()));
2296 
2297  switch (getCoeffType(R))
2298  {
2299  #ifdef HAVE_RINGS
2300  case n_Z:
2301  return solveAx_dixon(A, b, x, NULL);
2302  case n_Zn:
2303  case n_Znm:
2304  case n_Z2m:
2305  return solveAx_howell(A, b, x, NULL);
2306  #endif
2307  case n_Zp:
2308  case n_Q:
2309  case n_GF:
2310  case n_algExt:
2311  case n_transExt:
2312  Warn("have field, should use Gauss or better");
2313  default:
2314  if (R->cfXExtGcd && R->cfAnn)
2315  { //assume it's Euclidean
2316  return solveAx_howell(A, b, x, NULL);
2317  }
2318  Werror("have no solve algorithm");
2319  }
2320  return NULL;
2321 }
static number solveAx_dixon(bigintmat *A, bigintmat *B, bigintmat *x, bigintmat *kern)
Definition: bigintmat.cc:1990
#define Print
Definition: emacs.cc:83
only used if HAVE_RINGS is defined: ?
Definition: coeffs.h:43
only used if HAVE_RINGS is defined: ?
Definition: coeffs.h:45
used for all transcendental extensions, i.e., the top-most extension in an extension tower is transce...
Definition: coeffs.h:38
rational (GMP) numbers
Definition: coeffs.h:31
{p < 2^31}
Definition: coeffs.h:30
only used if HAVE_RINGS is defined: ?
Definition: coeffs.h:44
#define assume(x)
Definition: mod2.h:405
The main handler for Singular numbers which are suitable for Singular polynomials.
only used if HAVE_RINGS is defined: ?
Definition: coeffs.h:42
static number solveAx_howell(bigintmat *A, bigintmat *b, bigintmat *x, bigintmat *kern)
Definition: bigintmat.cc:2168
int cols() const
Definition: bigintmat.h:128
static FORCE_INLINE n_coeffType getCoeffType(const coeffs r)
Returns the type of coeffs domain.
Definition: coeffs.h:422
void Print()
IO: simply prints the matrix to the current output (screen?)
Definition: bigintmat.cc:440
int rows() const
Definition: bigintmat.h:129
#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:35
coeffs basecoeffs() const
Definition: bigintmat.h:130
#define R
Definition: sirandom.c:26
void Werror(const char *fmt,...)
Definition: reporter.cc:199
#define Warn
Definition: emacs.cc:80
static number solveAx_dixon ( bigintmat A,
bigintmat B,
bigintmat x,
bigintmat kern 
)
static

Definition at line 1990 of file bigintmat.cc.

1990  {
1991  coeffs R = A->basecoeffs();
1992 
1993  assume(getCoeffType(R) == n_Z);
1994 
1995  number p = n_Init(536870909, R); // PreviousPrime(2^29); not clever
1996  coeffs Rp = numbercoeffs(p, R); // R/pR
1997  bigintmat *Ap = bimChangeCoeff(A, Rp),
1998  *m = prependIdentity(Ap),
1999  *Tp, *Hp;
2000  delete Ap;
2001 
2002  m->howell();
2003  Hp = new bigintmat(A->rows(), A->cols(), Rp);
2004  Hp->copySubmatInto(m, A->cols()+1, 1, A->rows(), A->cols(), 1, 1);
2005  Tp = new bigintmat(A->cols(), A->cols(), Rp);
2006  Tp->copySubmatInto(m, 1, 1, A->cols(), A->cols(), 1, 1);
2007 
2008  int i, j;
2009 
2010  for(i=1; i<= A->cols(); i++) {
2011  for(j=m->rows(); j>A->cols(); j--) {
2012  if (!n_IsZero(m->view(j, i), Rp)) break;
2013  }
2014  if (j>A->cols()) break;
2015  }
2016 // Print("Found nullity (kern dim) of %d\n", i-1);
2017  bigintmat * kp = new bigintmat(A->cols(), i-1, Rp);
2018  kp->copySubmatInto(Tp, 1, 1, A->cols(), i-1, 1, 1);
2019  kp->howell();
2020 
2021  delete m;
2022 
2023  //Hp is the mod-p howell form
2024  //Tp the transformation, mod p
2025  //kp a basis for the kernel, in howell form, mod p
2026 
2027  bigintmat * eps_p = new bigintmat(B->rows(), B->cols(), Rp),
2028  * x_p = new bigintmat(A->cols(), B->cols(), Rp),
2029  * fps_p = new bigintmat(kp->cols(), B->cols(), Rp);
2030 
2031  //initial solution
2032 
2033  number zero = n_Init(0, R);
2034  x->skalmult(zero, R);
2035  n_Delete(&zero, R);
2036 
2037  bigintmat * b = new bigintmat(B);
2038  number pp = n_Init(1, R);
2039  i = 1;
2040  do {
2041  bigintmat * b_p = bimChangeCoeff(b, Rp), * s;
2042  bigintmat * t1, *t2;
2043  reduce_mod_howell(Hp, b_p, eps_p, x_p);
2044  delete b_p;
2045  if (!eps_p->isZero()) {
2046  Print("no solution, since no modular solution\n");
2047 
2048  delete eps_p;
2049  delete x_p;
2050  delete Hp;
2051  delete kp;
2052  delete Tp;
2053  delete b;
2054  n_Delete(&pp, R);
2055  n_Delete(&p, R);
2056  nKillChar(Rp);
2057 
2058  return NULL;
2059  }
2060  t1 = bimMult(Tp, x_p);
2061  delete x_p;
2062  x_p = t1;
2063  reduce_mod_howell(kp, x_p, x_p, fps_p); //we're not all interested in fps_p
2064  s = bimChangeCoeff(x_p, R);
2065  t1 = bimMult(A, s);
2066  t2 = bimSub(b, t1);
2067  t2->skaldiv(p);
2068  delete b;
2069  delete t1;
2070  b = t2;
2071  s->skalmult(pp, R);
2072  t1 = bimAdd(x, s);
2073  delete s;
2074  x->swapMatrix(t1);
2075  delete t1;
2076 
2077  if(kern && i==1) {
2078  bigintmat * ker = bimChangeCoeff(kp, R);
2079  t1 = bimMult(A, ker);
2080  t1->skaldiv(p);
2081  t1->skalmult(n_Init(-1, R), R);
2082  b->appendCol(t1);
2083  delete t1;
2084  x->appendCol(ker);
2085  delete ker;
2086  x_p->extendCols(kp->cols());
2087  eps_p->extendCols(kp->cols());
2088  fps_p->extendCols(kp->cols());
2089  }
2090 
2091  n_InpMult(pp, p, R);
2092 
2093  if (b->isZero()) {
2094  //exact solution found, stop
2095  delete eps_p;
2096  delete fps_p;
2097  delete x_p;
2098  delete Hp;
2099  delete kp;
2100  delete Tp;
2101  delete b;
2102  n_Delete(&pp, R);
2103  n_Delete(&p, R);
2104  nKillChar(Rp);
2105 
2106  return n_Init(1, R);
2107  } else {
2108  bigintmat *y = new bigintmat(x->rows(), x->cols(), R);
2109  number d = bimFarey(x, pp, y);
2110  if (d) {
2111  bigintmat *c = bimMult(A, y);
2112  bigintmat *bd = new bigintmat(B);
2113  bd->skalmult(d, R);
2114  if (kern) {
2115  bd->extendCols(kp->cols());
2116  }
2117  if (*c == *bd) {
2118  x->swapMatrix(y);
2119  delete y;
2120  delete c;
2121  if (kern) {
2122  y = new bigintmat(x->rows(), B->cols(), R);
2123  c = new bigintmat(x->rows(), kp->cols(), R);
2124  x->splitcol(y, c);
2125  x->swapMatrix(y);
2126  delete y;
2127  kern->swapMatrix(c);
2128  delete c;
2129  }
2130 
2131  delete bd;
2132 
2133  delete eps_p;
2134  delete fps_p;
2135  delete x_p;
2136  delete Hp;
2137  delete kp;
2138  delete Tp;
2139  delete b;
2140  n_Delete(&pp, R);
2141  n_Delete(&p, R);
2142  nKillChar(Rp);
2143 
2144  return d;
2145  }
2146  delete c;
2147  delete bd;
2148  n_Delete(&d, R);
2149  }
2150  delete y;
2151  }
2152  i++;
2153  } while (1);
2154  delete eps_p;
2155  delete fps_p;
2156  delete x_p;
2157  delete Hp;
2158  delete kp;
2159  delete Tp;
2160  n_Delete(&pp, R);
2161  n_Delete(&p, R);
2162  nKillChar(Rp);
2163  return NULL;
2164 }
void skaldiv(number b)
Macht Ganzzahldivision aller Matrixeinträge mit b.
Definition: bigintmat.cc:1763
void splitcol(bigintmat *a, bigintmat *b)
... linken ... rechten ...
Definition: bigintmat.cc:1107
const CanonicalForm int s
Definition: facAbsFact.cc:55
const CanonicalForm int const CFList const Variable & y
Definition: facAbsFact.cc:57
#define Print
Definition: emacs.cc:83
bigintmat * bimSub(bigintmat *a, bigintmat *b)
Definition: bigintmat.cc:216
static bigintmat * prependIdentity(bigintmat *A)
Definition: bigintmat.cc:1923
static FORCE_INLINE void n_InpMult(number &a, number b, const coeffs r)
multiplication of 'a' and 'b'; replacement of 'a' by the product a*b
Definition: coeffs.h:640
return P p
Definition: myNF.cc:203
Matrices of numbers.
Definition: bigintmat.h:32
void appendCol(bigintmat *a)
horizontally join the matrices, m <- m|a
Definition: bigintmat.cc:1034
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
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:180
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:1204
int j
Definition: myNF.cc:70
bigintmat * bimMult(bigintmat *a, bigintmat *b)
Definition: bigintmat.cc:253
static number bimFarey(bigintmat *A, number N, bigintmat *L)
Definition: bigintmat.cc:1935
static void reduce_mod_howell(bigintmat *A, bigintmat *b, bigintmat *eps, bigintmat *x)
Definition: bigintmat.cc:1850
void extendCols(int i)
append i zero-columns to the matrix
Definition: bigintmat.cc:1029
#define assume(x)
Definition: mod2.h:405
void swapMatrix(bigintmat *a)
Definition: bigintmat.cc:1468
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:906
int m
Definition: cfEzgcd.cc:119
only used if HAVE_RINGS is defined: ?
Definition: coeffs.h:42
int i
Definition: cfEzgcd.cc:123
static FORCE_INLINE BOOLEAN n_IsZero(number n, const coeffs r)
TRUE iff 'n' represents the zero element.
Definition: coeffs.h:465
bigintmat * bimChangeCoeff(bigintmat *a, coeffs cnew)
Liefert Kopier von Matrix a zurück, mit coeffs cnew statt den ursprünglichen.
Definition: bigintmat.cc:1706
int cols() const
Definition: bigintmat.h:128
static FORCE_INLINE n_coeffType getCoeffType(const coeffs r)
Returns the type of coeffs domain.
Definition: coeffs.h:422
int rows() const
Definition: bigintmat.h:129
#define NULL
Definition: omList.c:10
coeffs basecoeffs() const
Definition: bigintmat.h:130
#define R
Definition: sirandom.c:26
static FORCE_INLINE void n_Delete(number *p, const coeffs r)
delete 'p'
Definition: coeffs.h:456
int isZero()
Definition: bigintmat.cc:1266
const poly b
Definition: syzextra.cc:213
void howell()
dito, but Howell form (only different for zero-divsors)
Definition: bigintmat.cc:1487
void nKillChar(coeffs r)
undo all initialisations
Definition: numbers.cc:488
static number solveAx_howell ( bigintmat A,
bigintmat b,
bigintmat x,
bigintmat kern 
)
static

Definition at line 2168 of file bigintmat.cc.

2168  {
2169  // try to solve Ax=b, more precisely, find
2170  // number d
2171  // bigintmat x
2172  // sth. Ax=db
2173  // where d is small-ish (divides the determinant of A if this makes sense)
2174  // return 0 if there is no solution.
2175  //
2176  // if kern is non-NULL, return a basis for the kernel
2177 
2178  //Algo: we do row-howell (triangular matrix). The idea is
2179  // Ax = b <=> AT T^-1x = b
2180  // y := T^-1 x, solve AT y = b
2181  // and return Ty.
2182  //Howell does not compute the trafo, hence we need to cheat:
2183  //B := (I_n | A^t)^t, then the top part of the Howell form of
2184  //B will give a useful trafo
2185  //Then we can find x by back-substitution and lcm/gcd to find the denominator
2186  //The defining property of Howell makes this work.
2187 
2188  coeffs R = A->basecoeffs();
2189  bigintmat *m = prependIdentity(A);
2190  m->howell(); // since m contains the identity, we'll have A->cols()
2191  // many cols.
2192  number den = n_Init(1, R);
2193 
2194  bigintmat * B = new bigintmat(A->rows(), 1, R);
2195  for(int i=1; i<= b->cols(); i++) {
2196  int A_col = A->cols();
2197  b->getcol(i, B);
2198  B->skalmult(den, R);
2199  for(int j = B->rows(); j>0; j--) {
2200  number Ai = m->view(m->rows()-B->rows() + j, A_col);
2201  if (n_IsZero(Ai, R) &&
2202  n_IsZero(B->view(j, 1), R)) {
2203  continue; //all is fine: 0*x = 0
2204  } else if (n_IsZero(B->view(j, 1), R)) {
2205  x->rawset(x->rows() - B->rows() + j, i, n_Init(0, R));
2206  A_col--;
2207  } else if (n_IsZero(Ai, R)) {
2208  delete m;
2209  delete B;
2210  n_Delete(&den, R);
2211  return 0;
2212  } else {
2213  // solve ax=db, possibly enlarging d
2214  // so x = db/a
2215  number Bj = B->view(j, 1);
2216  number g = n_Gcd(Bj, Ai, R);
2217  number xi;
2218  if (n_Equal(Ai, g, R)) { //good: den stable!
2219  xi = n_Div(Bj, Ai, R);
2220  } else { //den <- den * (a/g), so old sol. needs to be adjusted
2221  number inc_d = n_Div(Ai, g, R);
2222  n_InpMult(den, inc_d, R);
2223  x->skalmult(inc_d, R);
2224  B->skalmult(inc_d, R);
2225  xi = n_Div(Bj, g, R);
2226  n_Delete(&inc_d, R);
2227  } //now for the back-substitution:
2228  x->rawset(x->rows() - B->rows() + j, i, xi);
2229  for(int k=j; k>0; k--) {
2230  //B[k] = B[k] - x[k]A[k][j]
2231  number s = n_Mult(xi, m->view(m->rows()-B->rows() + k, A_col), R);
2232  B->rawset(k, 1, n_Sub(B->view(k, 1), s, R));
2233  n_Delete(&s, R);
2234  }
2235  n_Delete(&g, R);
2236  A_col--;
2237  }
2238  if (!A_col) {
2239  if (B->isZero()) break;
2240  else {
2241  delete m;
2242  delete B;
2243  n_Delete(&den, R);
2244  return 0;
2245  }
2246  }
2247  }
2248  }
2249  delete B;
2250  bigintmat *T = new bigintmat(A->cols(), A->cols(), R);
2251  T->copySubmatInto(m, 1, 1, A->cols(), A->cols(), 1, 1);
2252  if (kern) {
2253  int i, j;
2254  for(i=1; i<= A->cols(); i++) {
2255  for(j=m->rows(); j>A->cols(); j--) {
2256  if (!n_IsZero(m->view(j, i), R)) break;
2257  }
2258  if (j>A->cols()) break;
2259  }
2260  Print("Found nullity (kern dim) of %d\n", i-1);
2261  bigintmat * ker = new bigintmat(A->rows(), i-1, R);
2262  ker->copySubmatInto(T, 1, 1, A->rows(), i-1, 1, 1);
2263  kern->swapMatrix(ker);
2264  delete ker;
2265  }
2266  delete m;
2267  bigintmat * y = bimMult(T, x);
2268  x->swapMatrix(y);
2269  delete y;
2270  x->simplifyContentDen(&den);
2271 #if 0
2272  Print("sol = 1/");
2273  n_Print(den, R);
2274  Print(" *\n");
2275  x->Print();
2276  Print("\n");
2277 #endif
2278  return den;
2279 }
static FORCE_INLINE number n_Sub(number a, number b, const coeffs r)
return the difference of 'a' and 'b', i.e., a-b
Definition: coeffs.h:668
number view(int i, int j) const
view an entry an entry. NOTE: starts at [1,1]
Definition: bigintmat.cc:125
static FORCE_INLINE number n_Gcd(number a, number b, const coeffs r)
in Z: return the gcd of 'a' and 'b' in Z/nZ, Z/2^kZ: computed as in the case Z in Z/pZ...
Definition: coeffs.h:685
const CanonicalForm int s
Definition: facAbsFact.cc:55
const CanonicalForm int const CFList const Variable & y
Definition: facAbsFact.cc:57
#define Print
Definition: emacs.cc:83
static bigintmat * prependIdentity(bigintmat *A)
Definition: bigintmat.cc:1923
void simplifyContentDen(number *den)
ensures that Gcd(den, content)=1 < enden hier wieder
Definition: bigintmat.cc:2510
static FORCE_INLINE void n_InpMult(number &a, number b, const coeffs r)
multiplication of 'a' and 'b'; replacement of 'a' by the product a*b
Definition: coeffs.h:640
Matrices of numbers.
Definition: bigintmat.h:32
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
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:180
static FORCE_INLINE number n_Mult(number a, number b, const coeffs r)
return the product of 'a' and 'b', i.e., a*b
Definition: coeffs.h:635
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:1204
int j
Definition: myNF.cc:70
bigintmat * bimMult(bigintmat *a, bigintmat *b)
Definition: bigintmat.cc:253
void swapMatrix(bigintmat *a)
Definition: bigintmat.cc:1468
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:906
int m
Definition: cfEzgcd.cc:119
int i
Definition: cfEzgcd.cc:123
static FORCE_INLINE BOOLEAN n_IsZero(number n, const coeffs r)
TRUE iff 'n' represents the zero element.
Definition: coeffs.h:465
int cols() const
Definition: bigintmat.h:128
void Print()
IO: simply prints the matrix to the current output (screen?)
Definition: bigintmat.cc:440
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:743
int rows() const
Definition: bigintmat.h:129
CanonicalForm den(const CanonicalForm &f)
static FORCE_INLINE number n_Div(number a, number b, const coeffs r)
return the quotient of 'a' and 'b', i.e., a/b; raises an error if 'b' is not invertible in r exceptio...
Definition: coeffs.h:615
b *CanonicalForm B
Definition: facBivar.cc:51
coeffs basecoeffs() const
Definition: bigintmat.h:130
#define R
Definition: sirandom.c:26
static FORCE_INLINE BOOLEAN n_Equal(number a, number b, const coeffs r)
TRUE iff 'a' and 'b' represent the same number; they may have different representations.
Definition: coeffs.h:461
static FORCE_INLINE void n_Delete(number *p, const coeffs r)
delete 'p'
Definition: coeffs.h:456
static jList * T
Definition: janet.cc:37
int isZero()
Definition: bigintmat.cc:1266
void howell()
dito, but Howell form (only different for zero-divsors)
Definition: bigintmat.cc:1487
void n_Print(number &a, const coeffs r)
print a number (BEWARE of string buffers!) mostly for debugging
Definition: numbers.cc:549