Loading...
Searching...
No Matches
intvec.cc File Reference
`#include "misc/auxiliary.h"`
`#include "misc/intvec.h"`
`#include "misc/options.h"`
`#include "omalloc/omalloc.h"`

Go to the source code of this file.

## Macros

#define | INTVEC_CC

## Functions

intvec * | ivAdd (intvec *a, intvec *b)
intvec * | ivAddShift (intvec *a, intvec *b, int s)
intvec * | ivSub (intvec *a, intvec *b)
intvec * | ivTranp (intvec *o)
int | ivTrace (intvec *o)
intvec * | ivMult (intvec *a, intvec *b)
static int | ivColPivot (intvec *, int, int, int, int)
static void | ivNegRow (intvec *, int)
static void | ivSaveRow (intvec *, int)
static void | ivSetRow (intvec *, int, int)
static void | ivFreeRow (intvec *, int, int)
static void | ivReduce (intvec *, int, int, int, int)
static void | ivZeroElim (intvec *, int, int, int &)
static void | ivRowContent (intvec *, int, int)
static void | ivKernFromRow (intvec *, intvec *, intvec *, int, int, int)
static intvec * | ivOptimizeKern (intvec *)
static int | ivGcd (int, int)
static void | ivOptRecursive (intvec *, intvec *, intvec *, int &, int &, int)
static void | ivOptSolve (intvec *, intvec *, int &, int &)
static void | ivContent (intvec *)
static int | ivL1Norm (intvec *)
static int | ivCondNumber (intvec *, int)
void | ivTriangIntern (intvec *imat, int &ready, int &all)
intvec * | ivSolveKern (intvec *imat, int dimtr)
intvec * | ivConcat (intvec *a, intvec *b)
bigintmat * | iv2biv (intvec *hilb, const coeffs cf)

## Macro Definition Documentation

## INTVEC_CC

#define INTVEC_CC

Definition at line 8 of file intvec.cc.

## Function Documentation

## iv2biv()

bigintmat * iv2biv | ( | intvec * | hilb,
|  | const coeffs | cf )

Definition at line 851 of file intvec.cc.

{
bigintmat *hh=NULL;
if (hilb!=NULL)
{
int l=hilb->rows();
hh=new bigintmat(1,l,cf);
for(int i=0;i<l;i++)
{
number tp = n_Init((*hilb)[i], cf);
n_Delete(&BIMATELEM((*hh),1,i+1), cf);
BIMATELEM((*hh),1,i+1)=tp;
}
}
return hh;
}
BIMATELEM
#define BIMATELEM(M, I, J)
Definition bigintmat.h:133
l
int l
Definition cfEzgcd.cc:100
i
int i
Definition cfEzgcd.cc:132
cf
CanonicalForm cf
Definition cfModGcd.cc:4091
bigintmat
Matrices of numbers.
Definition bigintmat.h:51
intvec::rows
int rows() const
Definition intvec.h:97
n_Delete
static FORCE_INLINE void n_Delete(number *p, const coeffs r)
delete 'p'
Definition coeffs.h:461
n_Init
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:541
NULL
#define NULL
Definition omList.c:12

## ivAdd()

intvec * ivAdd | ( | intvec * | a,
|  | intvec * | b )

Definition at line 249 of file intvec.cc.

{
intvec * iv;
int mn, ma, i;
if (a->cols() != b->cols()) return NULL;
mn = si_min(a->rows(),b->rows());
ma = si_max(a->rows(),b->rows());
if (a->cols() == 1)
{
iv = new intvec(ma);
for (i=0; i<mn; i++) (*iv)[i] = (*a)[i] + (*b)[i];
if (ma > mn)
{
if (ma == a->rows())
{
for(i=mn; i<ma; i++) (*iv)[i] = (*a)[i];
}
else
{
for(i=mn; i<ma; i++) (*iv)[i] = (*b)[i];
}
}
return iv;
}
if (mn != ma) return NULL;
iv = new intvec(a);
for (i=0; i<mn*a->cols(); i++) { (*iv)[i] += (*b)[i]; }
return iv;
}
si_max
static int si_max(const int a, const int b)
Definition auxiliary.h:125
si_min
static int si_min(const int a, const int b)
Definition auxiliary.h:126
b
CanonicalForm b
Definition cfModGcd.cc:4111
intvec
Definition intvec.h:24
intvec::cols
int cols() const
Definition intvec.h:96

## ivAddShift()

intvec * ivAddShift | ( | intvec * | a,
|  | intvec * | b,
|  | int | s )

Definition at line 279 of file intvec.cc.

{
if (a->cols() != b->cols()) return NULL;
if (a->cols() == 1)
{
int i;
intvec * iv;
int ma = si_max(a->rows(),b->rows()+s);
iv=new intvec(ma);
for (i=a->rows()-1;i>=0;i--)
(*iv)[i] = (*a)[i];
for(i=b->rows()+s-1;i>=s;i--)
(*iv)[i] += (*b)[i-s];
return iv;
}
return NULL;
}
s
const CanonicalForm int s
Definition facAbsFact.cc:51

## ivColPivot()

int ivColPivot | ( | intvec * | imat,
|  | int | colpos,
|  | int | rowpos,
|  | int | ready,
|  | int | all )

static

Definition at line 484 of file intvec.cc.

{
int rpiv;
if (IMATELEM(*imat,rowpos,colpos)!=0)
return rowpos;
for (rpiv=ready+1;rpiv<=all;rpiv++)
{
if (IMATELEM(*imat,rpiv,colpos)!=0)
return rpiv;
}
return 0;
}
IMATELEM
#define IMATELEM(M, I, J)
Definition intvec.h:86

## ivConcat()

intvec * ivConcat | ( | intvec * | a,
|  | intvec * | b )

Definition at line 822 of file intvec.cc.

{
int ac=a->cols();
int c = ac + b->cols(); int r = si_max(a->rows(),b->rows());
intvec * ab = new intvec(r,c,0);
int i,j;
for (i=1; i<=a->rows(); i++)
{
for(j=1; j<=ac; j++)
IMATELEM(*ab,i,j) = IMATELEM(*a,i,j);
}
for (i=1; i<=b->rows(); i++)
{
for(j=1; j<=b->cols(); j++)
IMATELEM(*ab,i,j+ac) = IMATELEM(*b,i,j);
}
return ab;
}
j
int j
Definition facHensel.cc:110

## ivCondNumber()

int ivCondNumber | ( | intvec * | w,
|  | int | l )

static

Definition at line 764 of file intvec.cc.

{
int l0=0, i;
if (l<0)
{
for (i=w->rows()-1;i>=0;i--)
{
if ((*w)[i]<0) l0--;
}
if (l0==0)
{
for (i=w->rows()-1;i>=0;i--)
{
if ((*w)[i]>0) l0++;
}
}
return l0;
}
else
{
for (i=w->rows()-1;i>=0;i--)
{
if ((*w)[i]<0) return -1;
}
for (i=w->rows()-1;i>=0;i--)
{
if ((*w)[i]>0) l0++;
}
return l0;
}
}
w
const CanonicalForm & w
Definition facAbsFact.cc:51

## ivContent()

void ivContent | ( | intvec * | w | ) |

static

Definition at line 797 of file intvec.cc.

{
int tgcd, m;
int i=w->rows()-1;
loop
{
tgcd = (*w)[i--];
if (tgcd!=0) break;
if (i<0) return;
}
if (tgcd<0) tgcd = -tgcd;
if (tgcd==1) return;
loop
{
m = (*w)[i--];
if (m!=0) tgcd= ivGcd(tgcd, m);
if (tgcd==1) return;
if (i<0) break;
}
for (i=w->rows()-1;i>=0;i--)
(*w)[i] /= tgcd;
}
m
int m
Definition cfEzgcd.cc:128
ivGcd
static int ivGcd(int, int)
Definition intvec.cc:648
loop
#define loop
Definition structs.h:71

## ivFreeRow()

void ivFreeRow | ( | intvec * | imat,
|  | int | rowpos,
|  | int | rpiv )

static

Definition at line 522 of file intvec.cc.

{
int i, j;
for (j=rpiv-1;j>=rowpos;j--)
{
for (i=imat->cols();i!=0;i--)
IMATELEM(*imat,j+1,i) = IMATELEM(*imat,j,i);
}
}

## ivGcd()

int ivGcd | ( | int | a,
|  | int | b )

static

Definition at line 648 of file intvec.cc.

{
int x;
if (a<0) a=-a;
if (b<0) b=-b;
if (b>a)
{
x=b;
b=a;
a=x;
}
while (b!=0)
{
x = a % b;
a = b;
b = x;
}
return a;
}
x
Variable x
Definition cfModGcd.cc:4090

## ivKernFromRow()

void ivKernFromRow | ( | intvec * | kern,
|  | intvec * | imat,
|  | intvec * | perm,
|  | int | pos,
|  | int | r,
|  | int | c )

static

Definition at line 613 of file intvec.cc.

{
int piv, cp, g, i, j, k, s;
for (i=c;i>(*perm)[r];i--)
{
IMATELEM(*kern,pos,i) = 1;
for (j=r;j!=0;j--)
{
cp = (*perm)[j];
s=0;
for(k=c;k>cp;k--)
s += IMATELEM(*imat,j,k)*IMATELEM(*kern,pos,k);
if (s!=0)
{
piv = IMATELEM(*imat,j,cp);
g = ivGcd(piv,s);
if (g!=1)
{
s /= g;
piv /= g;
}
for(k=c;k>cp;k--)
IMATELEM(*kern,pos,k) *= piv;
IMATELEM(*kern,pos,cp) = -s;
ivRowContent(kern,pos,cp);
}
}
if (IMATELEM(*kern,pos,i)<0)
ivNegRow(kern,pos);
pos--;
}
}
k
int k
Definition cfEzgcd.cc:99
g
g
Definition cfModGcd.cc:4098
ivRowContent
static void ivRowContent(intvec *, int, int)
Definition intvec.cc:589
ivNegRow
static void ivNegRow(intvec *, int)
Definition intvec.cc:498

## ivL1Norm()

int ivL1Norm | ( | intvec * | w | ) |

static

Definition at line 749 of file intvec.cc.

{
int i, j, s = 0;
for (i=w->rows()-1;i>=0;i--)
{
j = (*w)[i];
if (j>0)
s += j;
else
s -= j;
}
return s;
}

## ivMult()

intvec * ivMult | ( | intvec * | a,
|  | intvec * | b )

Definition at line 349 of file intvec.cc.

{
int i, j, k, sum,
ra = a->rows(), ca = a->cols(),
rb = b->rows(), cb = b->cols();
intvec * iv;
if (ca != rb) return NULL;
iv = new intvec(ra, cb, 0);
for (i=0; i<ra; i++)
{
for (j=0; j<cb; j++)
{
sum = 0;
for (k=0; k<ca; k++)
sum += (*a)[i*ca+k]*(*b)[k*cb+j];
(*iv)[i*cb+j] = sum;
}
}
return iv;
}

## ivNegRow()

void ivNegRow | ( | intvec * | imat,
|  | int | rpiv )

static

Definition at line 498 of file intvec.cc.

{
int i;
for (i=imat->cols();i!=0;i--)
IMATELEM(*imat,rpiv,i) = -(IMATELEM(*imat,rpiv,i));
}

## ivOptimizeKern()

intvec * ivOptimizeKern | ( | intvec * | kern | ) |

static

Definition at line 669 of file intvec.cc.

{
int i,l,j,c=kern->cols(),r=kern->rows();
intvec *res=new intvec(c);
if (TEST_OPT_PROT)
Warn(" %d linear independent solutions\n",r);
for (i=r;i>1;i--)
{
for (j=c;j>0;j--)
{
(*res)[j-1] += IMATELEM(*kern,i,j);
}
}
ivContent(res);
if (r<11)
{
l = ivCondNumber(res,-c);
j = ivL1Norm(res);
ivOptRecursive(res, NULL, kern, l, j, r);
}
return res;
}
Warn
#define Warn
Definition emacs.cc:77
res
CanonicalForm res
Definition facAbsFact.cc:60
ivOptRecursive
static void ivOptRecursive(intvec *, intvec *, intvec *, int &, int &, int)
Definition intvec.cc:693
ivL1Norm
static int ivL1Norm(intvec *)
Definition intvec.cc:749
ivContent
static void ivContent(intvec *)
Definition intvec.cc:797
ivCondNumber
static int ivCondNumber(intvec *, int)
Definition intvec.cc:764
TEST_OPT_PROT
#define TEST_OPT_PROT
Definition options.h:105

## ivOptRecursive()

void ivOptRecursive | ( | intvec * | res,
|  | intvec * | w,
|  | intvec * | kern,
|  | int & | l,
|  | int & | j,
|  | int | pos )

static

Definition at line 693 of file intvec.cc.

{
int m, k, d;
intvec *h;
d=kern->rows();
d=96/(d*d);
if (d<3) d=3;
if (w!=0)
h = new intvec(w);
else
h = new intvec(res->rows());
for (m=d;m>0;m--)
{
for(k=h->rows()-1;k>=0;k--)
(*h)[k] += IMATELEM(*kern,pos,k+1);
if(pos>1)
ivOptRecursive(res, h, kern, l, j, pos-1);
else
ivOptSolve(res, h, l, j);
}
delete h;
if (pos>1)
ivOptRecursive(res, w, kern, l, j, pos-1);
else if (w!=NULL)
ivOptSolve(res, w, l, j);
}
ivOptSolve
static void ivOptSolve(intvec *, intvec *, int &, int &)
Definition intvec.cc:722
h
STATIC_VAR Poly * h
Definition janet.cc:971

## ivOptSolve()

void ivOptSolve | ( | intvec * | res,
|  | intvec * | w,
|  | int & | l,
|  | int & | j )

static

Definition at line 722 of file intvec.cc.

{
int l0, j0, k;
l0 = ivCondNumber(w, l);
if (l0==l)
{
ivContent(w);
j0 = ivL1Norm(w);
if(j0<j)
{
j = j0;
for(k=w->rows()-1;k>=0;k--)
(*res)[k] = (*w)[k];
}
return;
}
if(l0>l)
{
l = l0;
ivContent(w);
j = ivL1Norm(w);
for(k=w->rows()-1;k>=0;k--)
(*res)[k] = (*w)[k];
}
}

## ivReduce()

void ivReduce | ( | intvec * | imat,
|  | int | rpiv,
|  | int | colpos,
|  | int | ready,
|  | int | all )

static

Definition at line 533 of file intvec.cc.

{
int tgcd, ce, m1, m2, j, i;
int piv = IMATELEM(*imat,rpiv,colpos);
for (j=all;j>ready;j--)
{
ivRowContent(imat, j, 1);
ce = IMATELEM(*imat,j,colpos);
if (ce!=0)
{
IMATELEM(*imat,j,colpos) = 0;
m1 = piv;
m2 = ce;
tgcd = ivGcd(m1, m2);
if (tgcd != 1)
{
m1 /= tgcd;
m2 /= tgcd;
}
for (i=imat->cols();i>colpos;i--)
{
IMATELEM(*imat,j,i) = IMATELEM(*imat,j,i)*m1-
IMATELEM(*imat,rpiv,i)*m2;
}
ivRowContent(imat, j, colpos+1);
}
}
}

## ivRowContent()

void ivRowContent | ( | intvec * | imat,
|  | int | rowpos,
|  | int | colpos )

static

Definition at line 589 of file intvec.cc.

{
int tgcd, m;
int i=imat->cols();
loop
{
tgcd = IMATELEM(*imat,rowpos,i--);
if (tgcd!=0) break;
if (i<colpos) return;
}
if (tgcd<0) tgcd = -tgcd;
if (tgcd==1) return;
loop
{
m = IMATELEM(*imat,rowpos,i--);
if (m!=0) tgcd= ivGcd(tgcd, m);
if (tgcd==1) return;
if (i<colpos) break;
}
for (i=imat->cols();i>=colpos;i--)
IMATELEM(*imat,rowpos,i) /= tgcd;
}

## ivSaveRow()

void ivSaveRow | ( | intvec * | imat,
|  | int | rpiv )

static

Definition at line 505 of file intvec.cc.

{
int i, j=imat->rows();
for (i=imat->cols();i!=0;i--)
IMATELEM(*imat,j,i) = IMATELEM(*imat,rpiv,i);
}

## ivSetRow()

void ivSetRow | ( | intvec * | imat,
|  | int | rowpos,
|  | int | colpos )

static

Definition at line 513 of file intvec.cc.

{
int i, j=imat->rows();
for (i=imat->cols();i!=0;i--)
IMATELEM(*imat,rowpos,i) = IMATELEM(*imat,j,i);
ivRowContent(imat, rowpos, colpos);
}

## ivSolveKern()

intvec * ivSolveKern | ( | intvec * | imat,
|  | int | dimtr )

Definition at line 442 of file intvec.cc.

{
int d=imat->cols();
int kdim=d-dimtr;
intvec *perm = new intvec(dimtr+1);
intvec *kern = new intvec(kdim,d,0);
intvec *res;
int c, cp, r, t;
t = kdim;
c = 1;
for (r=1;r<=dimtr;r++)
{
while (IMATELEM(*imat,r,c)==0) c++;
(*perm)[r] = c;
c++;
}
c = d;
for (r=dimtr;r>0;r--)
{
cp = (*perm)[r];
if (cp!=c)
{
ivKernFromRow(kern, imat, perm, t, r, c);
t -= (c-cp);
if (t==0)
break;
c = cp-1;
}
else
c--;
}
if (kdim>1)
res = ivOptimizeKern(kern);
else
res = ivTranp(kern);
delete kern;
delete perm;
return res;
}
ivOptimizeKern
static intvec * ivOptimizeKern(intvec *)
Definition intvec.cc:669
ivKernFromRow
static void ivKernFromRow(intvec *, intvec *, intvec *, int, int, int)
Definition intvec.cc:613
ivTranp
intvec * ivTranp(intvec *o)
Definition intvec.cc:327

## ivSub()

intvec * ivSub | ( | intvec * | a,
|  | intvec * | b )

Definition at line 297 of file intvec.cc.

{
intvec * iv;
int mn, ma, i;
if (a->cols() != b->cols()) return NULL;
mn = si_min(a->rows(),b->rows());
ma = si_max(a->rows(),b->rows());
if (a->cols() == 1)
{
iv = new intvec(ma);
for (i=0; i<mn; i++) (*iv)[i] = (*a)[i] - (*b)[i];
if (ma > mn)
{
if (ma == a->rows())
{
for(i=mn; i<ma; i++) (*iv)[i] = (*a)[i];
}
else
{
for(i=mn; i<ma; i++) (*iv)[i] = -(*b)[i];
}
}
return iv;
}
if (mn != ma) return NULL;
iv = new intvec(a);
for (i=0; i<mn*a->cols(); i++) { (*iv)[i] -= (*b)[i]; }
return iv;
}

## ivTrace()

int ivTrace | ( | intvec * | o | ) |

Definition at line 339 of file intvec.cc.

{
int i, s = 0, m = si_min(o->rows(),o->cols()), c = o->cols();
for (i=0; i<m; i++)
{
s += (*o)[i*c+i];
}
return s;
}

## ivTranp()

intvec * ivTranp | ( | intvec * | o | ) |

Definition at line 327 of file intvec.cc.

{
int i, j, r = o->rows(), c = o->cols();
intvec * iv= new intvec(c, r, 0);
for (i=0; i<r; i++)
{
for (j=0; j<c; j++)
(*iv)[j*r+i] = (*o)[i*c+j];
}
return iv;
}

## ivTriangIntern()

void ivTriangIntern | ( | intvec * | imat,
|  | int & | ready,
|  | int & | all )

Definition at line 404 of file intvec.cc.

{
int rpiv, colpos=0, rowpos=0;
int ia=ready, ie=all;
do
{
rowpos++;
do
{
colpos++;
rpiv = ivColPivot(imat, colpos, rowpos, ia, ie);
} while (rpiv==0);
if (rpiv>ia)
{
if (rowpos!=rpiv)
{
ivSaveRow(imat, rpiv);
ivFreeRow(imat, rowpos, rpiv);
ivSetRow(imat, rowpos, colpos);
rpiv = rowpos;
}
ia++;
if (ia==imat->cols())
{
ready = ia;
all = ie;
return;
}
}
ivReduce(imat, rpiv, colpos, ia, ie);
ivZeroElim(imat, colpos, ia, ie);
} while (ie>ia);
ready = ia;
all = ie;
}
ivColPivot
static int ivColPivot(intvec *, int, int, int, int)
Definition intvec.cc:484
ivSetRow
static void ivSetRow(intvec *, int, int)
Definition intvec.cc:513
ivFreeRow
static void ivFreeRow(intvec *, int, int)
Definition intvec.cc:522
ivZeroElim
static void ivZeroElim(intvec *, int, int, int &)
Definition intvec.cc:564
ivSaveRow
static void ivSaveRow(intvec *, int)
Definition intvec.cc:505
ivReduce
static void ivReduce(intvec *, int, int, int, int)
Definition intvec.cc:533

## ivZeroElim()

void ivZeroElim | ( | intvec * | imat,
|  | int | colpos,
|  | int | ready,
|  | int & | all )

static

Definition at line 564 of file intvec.cc.

{
int j, i, k, l;
k = ready;
for (j=ready+1;j<=all;j++)
{
for (i=imat->cols();i>colpos;i--)
{
if (IMATELEM(*imat,j,i)!=0)
{
k++;
if (k<j)
{
for (l=imat->cols();l>colpos;l--)
IMATELEM(*imat,k,l) = IMATELEM(*imat,j,l);
}
break;
}
}
}
all = k;
}