bigintmat.h File Reference

#include <omalloc/omalloc.h>
#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+/-/* ? : NULL as a result means an error (non-compatible matrices?) More...
bigintmat *	bimAdd (bigintmat *a, int b)
bigintmat *	bimSub (bigintmat *a, bigintmat *b)
bigintmat *	bimSub (bigintmat *a, int b)
bigintmat *	bimMult (bigintmat *a, bigintmat *b)
bigintmat *	bimMult (bigintmat *a, int 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

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

Definition at line 117 of file bigintmat.h.

Function Documentation

intvec* bim2iv

(

bigintmat *

b

)

Definition at line 339 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;
}

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 178 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;
}

bigintmat* bimAdd	(	bigintmat *	a,
		int	b
	)

Definition at line 195 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_Add((*a)[i], bb, basecoeffs), basecoeffs);

  n_Delete(&bb,basecoeffs);
  return bim;
}

bigintmat* bimChangeCoeff	(	bigintmat *	a,
		coeffs	cnew
	)

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

Definition at line 1688 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;
}

bigintmat* bimCopy

(

const bigintmat *

b

)

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

Definition at line 403 of file bigintmat.cc.

{
  if (b == NULL)
    return NULL;

  return new bigintmat(b);
}

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

Definition at line 251 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);

        number sum2 = n_Add(sum, prod, basecoeffs); // no inplace add :(

        n_Delete(&sum, basecoeffs); n_Delete(&prod, basecoeffs);

        sum = sum2;
      }
      bim->rawset(i, j, sum, basecoeffs);
    }
  return bim;
}

bigintmat* bimMult	(	bigintmat *	a,
		int	b
	)

Definition at line 299 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;
}

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

Definition at line 318 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;
}

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

Multipliziert Matrix a und b und speichert Ergebnis in c.

Definition at line 1818 of file bigintmat.cc.

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

  delete tmp;
}

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

Definition at line 214 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;
}

bigintmat* bimSub	(	bigintmat *	a,
		int	b
	)

Definition at line 232 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_Sub((*a)[i], bb, basecoeffs), basecoeffs);

  n_Delete(&bb,basecoeffs);
  return bim;
}

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

Definition at line 2301 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();
      Print("\n");
#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
    Print("Diag ? %d\n", diag);
    a->Print();
    Print("\n");
#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);
}

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

Definition at line 347 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;
}

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

                                                              {
#if 0
  Print("Kernel of ");
  a->Print();
  Print(" modulo ");
  n_Print(p, q);
  Print("\n");
#endif

  coeffs coe = numbercoeffs(p, q);
  bigintmat *m = bimChangeCoeff(a, coe), *U, *V;
  diagonalForm(m, &U, &V);
#if 0
  Print("\ndiag form: ");
  m->Print();
  Print("\nU:\n");
  U->Print();
  Print("\nV:\n");
  V->Print();
  Print("\n");
#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++);

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

bool nCoeffs_are_equal	(	coeffs	r,
		coeffs	s
	)

Definition at line 2449 of file bigintmat.cc.

                                           {
  if ((r == NULL) || (s == NULL))
    return false;
  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;
}

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

Definition at line 172 of file bigintmat.cc.

{
  return !(lhr==rhr);
}

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

Definition at line 155 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;
}

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

                                                         {
#if 0
  Print("Solve Ax=b for A=\n");
  A->Print();
  Print("\nb = \n");
  b->Print();
  Print("\nx = \n");
  x->Print();
  Print("\n");
#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)) {
    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);
    case n_Zp:
    case n_Q:
    case n_GF:
    case n_algExt:
    case n_transExt:
      Warn("have field, should use Gauss or better");
    default:
      if (R->cfXExtGcd && R->cfAnn) { //assume it's Euclidean
        return solveAx_howell(A, b, x, NULL);
      }
      Werror("have no solve algorithm");
  }
  return NULL;
}