bigintmat.h File Reference

#include "coeffs/coeffs.h"

Go to the source code of this file.

Data Structures
class	bigintmat
	Matrices of numbers. More...

Macros
#define	BIMATELEM(M, I, J)   (M)[(I-1)*(M).cols()+J-1]

Functions
bool	operator== (const bigintmat &lhr, const bigintmat &rhr)
bool	operator!= (const bigintmat &lhr, const bigintmat &rhr)
bigintmat *	bimAdd (bigintmat *a, bigintmat *b)
	Matrix-Add/-Sub/-Mult so oder mit operator+/-/* ? @Note: NULL as a result means an error (non-compatible matrices?) More...
bigintmat *	bimAdd (bigintmat *a, long b)
bigintmat *	bimSub (bigintmat *a, bigintmat *b)
bigintmat *	bimSub (bigintmat *a, long b)
bigintmat *	bimMult (bigintmat *a, bigintmat *b)
bigintmat *	bimMult (bigintmat *a, long b)
bigintmat *	bimMult (bigintmat *a, number b, const coeffs cf)
bigintmat *	bimCopy (const bigintmat *b)
	same as copy constructor - apart from it being able to accept NULL as input More...
intvec *	bim2iv (bigintmat *b)
bigintmat *	iv2bim (intvec *b, const coeffs C)
bigintmat *	bimChangeCoeff (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...
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...
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)
void	diagonalForm (bigintmat *a, bigintmat **b, bigintmat **c)

Macro Definition Documentation

BIMATELEM

#define BIMATELEM	(		M,
			I,
			J
	)		(M)[(I-1)*(M).cols()+J-1]

Definition at line 133 of file bigintmat.h.

Function Documentation

bim2iv()

intvec * bim2iv

(

bigintmat *

b

)

Definition at line 341 of file bigintmat.cc.

{
  intvec * iv = new intvec(b->rows(), b->cols(), 0);
  for (int i=0; i<(b->rows())*(b->cols()); i++)
    (*iv)[i] = n_Int((*b)[i], b->basecoeffs()); // Geht das so?
  return iv;
}

bimAdd() [1/2]

bigintmat * bimAdd	(	bigintmat *	a,
		bigintmat *	b
	)

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

Definition at line 182 of file bigintmat.cc.

{
  if (a->cols() != b->cols()) return NULL;
  if (a->rows() != b->rows()) return NULL;
  if (a->basecoeffs() != b->basecoeffs()) { return NULL; }
 
  const coeffs basecoeffs = a->basecoeffs();
 
  int i;
 
  bigintmat * bim = new bigintmat(a->rows(), a->cols(), basecoeffs);
 
  for (i=a->rows()*a->cols()-1;i>=0; i--)
    bim->rawset(i, n_Add((*a)[i], (*b)[i], basecoeffs), basecoeffs);
 
  return bim;
}

bimAdd() [2/2]

bigintmat * bimAdd	(	bigintmat *	a,
		long	b
	)

Definition at line 199 of file bigintmat.cc.

{
 
  const int mn = si_min(a->rows(),a->cols());
 
  const coeffs basecoeffs = a->basecoeffs();
  number bb=n_Init(b,basecoeffs);
 
  int i;
 
  bigintmat * bim = new bigintmat(a->rows(),a->cols() , basecoeffs);
 
  for (i=1; i<=mn; i++)
    BIMATELEM(*bim,i,i)=n_Add(BIMATELEM(*a,i,i), bb, basecoeffs);
 
  n_Delete(&bb,basecoeffs);
  return bim;
}

bimChangeCoeff()

bigintmat * bimChangeCoeff	(	bigintmat *	a,
		coeffs	cnew
	)

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

Definition at line 1804 of file bigintmat.cc.

{
  coeffs cold = a->basecoeffs();
  bigintmat *b = new bigintmat(a->rows(), a->cols(), cnew);
  // Erzeugt Karte von alten coeffs nach neuen
  nMapFunc f = n_SetMap(cold, cnew);
  number t1;
  number t2;
  // apply map to all entries.
  for (int i=1; i<=a->rows(); i++)
  {
    for (int j=1; j<=a->cols(); j++)
    {
      t1 = a->get(i, j);
      t2 = f(t1, cold, cnew);
      b->set(i, j, t2);
      n_Delete(&t1, cold);
      n_Delete(&t2, cnew);
    }
  }
  return b;
}

bimCopy()

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.

{
  if (b == NULL)
    return NULL;
 
  return new bigintmat(b);
}

bimMult() [1/4]

bigintmat * bimMult	(	bigintmat *	a,
		bigintmat *	b
	)

Definition at line 255 of file bigintmat.cc.

{
  const int ca = a->cols();
  const int cb = b->cols();
 
  const int ra = a->rows();
  const int rb = b->rows();
 
  if (ca != rb)
  {
#ifndef SING_NDEBUG
    Werror("wrong bigintmat sizes at multiplication a * b: acols: %d != brows: %d\n", ca, rb);
#endif
    return NULL;
  }
 
  assume (ca == rb);
 
  if (a->basecoeffs() != b->basecoeffs()) { return NULL; }
 
  const coeffs basecoeffs = a->basecoeffs();
 
  int i, j, k;
 
  number sum;
 
  bigintmat * bim = new bigintmat(ra, cb, basecoeffs);
 
  for (i=1; i<=ra; i++)
    for (j=1; j<=cb; j++)
    {
      sum = n_Init(0, basecoeffs);
 
      for (k=1; k<=ca; k++)
      {
        number prod = n_Mult( BIMATELEM(*a, i, k), BIMATELEM(*b, k, j), basecoeffs);
 
        n_InpAdd(sum, prod, basecoeffs);
 
        n_Delete(&prod, basecoeffs);
      }
      bim->rawset(i, j, sum, basecoeffs);
    }
  return bim;
}

bimMult() [2/4]

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

Multipliziert Matrix a und b und speichert Ergebnis in c.

Definition at line 1932 of file bigintmat.cc.

{
  if (!nCoeffs_are_equal(a->basecoeffs(), b->basecoeffs()))
  {
    WerrorS("Error in bimMult. Coeffs do not agree!");
    return;
  }
  if ((a->rows() != c->rows()) || (b->cols() != c->cols()) || (a->cols() != b->rows()))
  {
    WerrorS("Error in bimMult. Dimensions do not agree!");
    return;
  }
  bigintmat *tmp = bimMult(a, b);
  c->copy(tmp);
 
  delete tmp;
}

bimMult() [3/4]

bigintmat * bimMult	(	bigintmat *	a,
		long	b
	)

Definition at line 301 of file bigintmat.cc.

{
 
  const int mn = a->rows()*a->cols();
 
  const coeffs basecoeffs = a->basecoeffs();
  number bb=n_Init(b,basecoeffs);
 
  int i;
 
  bigintmat * bim = new bigintmat(a->rows(),a->cols() , basecoeffs);
 
  for (i=0; i<mn; i++)
    bim->rawset(i, n_Mult((*a)[i], bb, basecoeffs), basecoeffs);
 
  n_Delete(&bb,basecoeffs);
  return bim;
}

bimMult() [4/4]

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

Definition at line 320 of file bigintmat.cc.

{
  if (cf!=a->basecoeffs()) return NULL;
 
  const int mn = a->rows()*a->cols();
 
  const coeffs basecoeffs = a->basecoeffs();
 
  int i;
 
  bigintmat * bim = new bigintmat(a->rows(),a->cols() , basecoeffs);
 
  for (i=0; i<mn; i++)
    bim->rawset(i, n_Mult((*a)[i], b, basecoeffs), basecoeffs);
 
  return bim;
}

bimSub() [1/2]

bigintmat * bimSub	(	bigintmat *	a,
		bigintmat *	b
	)

Definition at line 218 of file bigintmat.cc.

{
  if (a->cols() != b->cols()) return NULL;
  if (a->rows() != b->rows()) return NULL;
  if (a->basecoeffs() != b->basecoeffs()) { return NULL; }
 
  const coeffs basecoeffs = a->basecoeffs();
 
  int i;
 
  bigintmat * bim = new bigintmat(a->rows(), a->cols(), basecoeffs);
 
  for (i=a->rows()*a->cols()-1;i>=0; i--)
    bim->rawset(i, n_Sub((*a)[i], (*b)[i], basecoeffs), basecoeffs);
 
  return bim;
}

bimSub() [2/2]

bigintmat * bimSub	(	bigintmat *	a,
		long	b
	)

Definition at line 236 of file bigintmat.cc.

{
  const int mn = si_min(a->rows(),a->cols());
 
  const coeffs basecoeffs = a->basecoeffs();
  number bb=n_Init(b,basecoeffs);
 
  int i;
 
  bigintmat * bim = new bigintmat(a->rows(),a->cols() , basecoeffs);
 
  for (i=1; i<=mn; i++)
    BIMATELEM(*bim,i,i)=n_Sub(BIMATELEM(*a,i,i), bb, basecoeffs);
 
  n_Delete(&bb,basecoeffs);
  return bim;
}

diagonalForm()

void diagonalForm	(	bigintmat *	a,
		bigintmat **	b,
		bigintmat **	c
	)

Definition at line 2475 of file bigintmat.cc.

{
  bigintmat * t, *s, *a=A;
  coeffs R = a->basecoeffs();
  if (T)
  {
    *T = new bigintmat(a->cols(), a->cols(), R),
    (*T)->one();
    t = new bigintmat(*T);
  }
  else
  {
    t = *T;
  }
 
  if (S)
  {
    *S = new bigintmat(a->rows(), a->rows(), R);
    (*S)->one();
    s = new bigintmat(*S);
  }
  else
  {
    s = *S;
  }
 
  int flip=0;
  do
  {
    bigintmat * x, *X;
    if (flip)
    {
      x = s;
      X = *S;
    }
    else
    {
      x = t;
      X = *T;
    }
 
    if (x)
    {
      x->one();
      bigintmat * r = new bigintmat(a->rows()+a->cols(), a->cols(), R);
      bigintmat * rw = new bigintmat(1, a->cols(), R);
      for(int i=0; i<a->cols(); i++)
      {
        x->getrow(i+1, rw);
        r->setrow(i+1, rw);
      }
      for (int i=0; i<a->rows(); i++)
      {
        a->getrow(i+1, rw);
        r->setrow(i+a->cols()+1, rw);
      }
      r->hnf();
      for(int i=0; i<a->cols(); i++)
      {
        r->getrow(i+1, rw);
        x->setrow(i+1, rw);
      }
      for(int i=0; i<a->rows(); i++)
      {
        r->getrow(i+a->cols()+1, rw);
        a->setrow(i+1, rw);
      }
      delete rw;
      delete r;
 
#if 0
      Print("X: %ld\n", X);
      X->Print();
      Print("\nx: %ld\n", x);
      x->Print();
#endif
      bimMult(X, x, X);
#if 0
      Print("\n2:X: %ld %ld %ld\n", X, *S, *T);
      X->Print();
      Print("\n2:x: %ld\n", x);
      x->Print();
      PrintLn();
#endif
    }
    else
    {
      a->hnf();
    }
 
    int diag = 1;
    for(int i=a->rows(); diag && i>0; i--)
    {
      for(int j=a->cols(); j>0; j--)
      {
        if ((a->rows()-i)!=(a->cols()-j) && !n_IsZero(a->view(i, j), R))
        {
          diag = 0;
          break;
        }
      }
    }
#if 0
    PrintS("Diag ? %d\n", diag);
    a->Print();
    PrintLn();
#endif
    if (diag) break;
 
    a = a->transpose(); // leaks - I need to write inpTranspose
    flip = 1-flip;
  } while (1);
  if (flip)
    a = a->transpose();
 
  if (S) *S = (*S)->transpose();
  if (s) delete s;
  if (t) delete t;
  A->copy(a);
}

iv2bim()

bigintmat * iv2bim	(	intvec *	b,
		const coeffs	C
	)

Definition at line 349 of file bigintmat.cc.

{
  const int l = (b->rows())*(b->cols());
  bigintmat * bim = new bigintmat(b->rows(), b->cols(), C);
 
  for (int i=0; i < l; i++)
    bim->rawset(i, n_Init((*b)[i], C), C);
 
  return bim;
}

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 2600 of file bigintmat.cc.

{
#if 0
  PrintS("Kernel of ");
  a->Print();
  PrintS(" modulo ");
  n_Print(p, q);
  PrintLn();
#endif
 
  coeffs coe = numbercoeffs(p, q);
  bigintmat *m = bimChangeCoeff(a, coe), *U, *V;
  diagonalForm(m, &U, &V);
#if 0
  PrintS("\ndiag form: ");
  m->Print();
  PrintS("\nU:\n");
  U->Print();
  PrintS("\nV:\n");
  V->Print();
  PrintLn();
#endif
 
  int rg = 0;
#undef MIN
#define MIN(a,b) (a < b ? a : b)
  for(rg=0; rg<MIN(m->rows(), m->cols()) && !n_IsZero(m->view(m->rows()-rg,m->cols()-rg), coe); rg++);
 
  bigintmat * k = new bigintmat(m->cols(), m->rows(), coe);
  for(int i=0; i<rg; i++)
  {
    number A = n_Ann(m->view(m->rows()-i, m->cols()-i), coe);
    k->set(m->cols()-i, i+1, A);
    n_Delete(&A, coe);
  }
  for(int i=rg; i<m->cols(); i++)
  {
    k->set(m->cols()-i, i+1-rg, n_Init(1, coe));
  }
  bimMult(V, k, k);
  c->copy(bimChangeCoeff(k, q));
  return c->cols();
}

nCoeffs_are_equal()

bool nCoeffs_are_equal	(	coeffs	r,
		coeffs	s
	)

Definition at line 2645 of file bigintmat.cc.

{
  if ((r == NULL) || (s == NULL))
    return false;
  if (r == s)
    return true;
  if ((getCoeffType(r)==n_Z) && (getCoeffType(s)==n_Z))
    return true;
  if ((getCoeffType(r)==n_Zp) && (getCoeffType(s)==n_Zp))
  {
    if (r->ch == s->ch)
      return true;
    else
      return false;
  }
  // n_Zn stimmt wahrscheinlich noch nicht
  if ((getCoeffType(r)==n_Zn) && (getCoeffType(s)==n_Zn))
  {
    if (r->ch == s->ch)
      return true;
    else
      return false;
  }
  if ((getCoeffType(r)==n_Q) && (getCoeffType(s)==n_Q))
    return true;
  // FALL n_Zn FEHLT NOCH!
    //if ((getCoeffType(r)==n_Zn) && (getCoeffType(s)==n_Zn))
  return false;
}

operator!=()

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

Definition at line 176 of file bigintmat.cc.

{
  return !(lhr==rhr);
}

operator==()

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

Definition at line 159 of file bigintmat.cc.

{
  if (&lhr == &rhr) { return true; }
  if (lhr.cols() != rhr.cols()) { return false; }
  if (lhr.rows() != rhr.rows()) { return false; }
  if (lhr.basecoeffs() != rhr.basecoeffs()) { return false; }
 
  const int l = (lhr.rows())*(lhr.cols());
 
  for (int i=0; i < l; i++)
  {
    if (!n_Equal(lhr[i], rhr[i], lhr.basecoeffs())) { return false; }
  }
 
  return true;
}

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 2430 of file bigintmat.cc.

{
#if 0
  PrintS("Solve Ax=b for A=\n");
  A->Print();
  PrintS("\nb = \n");
  b->Print();
  PrintS("\nx = \n");
  x->Print();
  PrintLn();
#endif
 
  coeffs R = A->basecoeffs();
  assume (R == b->basecoeffs());
  assume (R == x->basecoeffs());
  assume ((x->cols() == b->cols()) && (x->rows() == A->cols()) && (A->rows() == b->rows()));
 
  switch (getCoeffType(R))
  {
  #ifdef HAVE_RINGS
    case n_Z:
      return solveAx_dixon(A, b, x, NULL);
    case n_Zn:
    case n_Znm:
    case n_Z2m:
      return solveAx_howell(A, b, x, NULL);
  #endif
    case n_Zp:
    case n_Q:
    case n_GF:
    case n_algExt:
    case n_transExt:
      WarnS("have field, should use Gauss or better");
      break;
    default:
      if (R->cfXExtGcd && R->cfAnn)
      { //assume it's Euclidean
        return solveAx_howell(A, b, x, NULL);
      }
      WerrorS("have no solve algorithm");
      break;
  }
  return NULL;
}