My Project  debian-1:4.1.1-p2+ds-4
Macros | Functions
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

intvecivAdd (intvec *a, intvec *b)
 
intvecivSub (intvec *a, intvec *b)
 
intvecivTranp (intvec *o)
 
int ivTrace (intvec *o)
 
intvecivMult (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 intvecivOptimizeKern (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)
 
intvecivSolveKern (intvec *imat, int dimtr)
 
intvecivConcat (intvec *a, intvec *b)
 

Macro Definition Documentation

◆ INTVEC_CC

#define INTVEC_CC

Definition at line 7 of file intvec.cc.

Function Documentation

◆ ivAdd()

intvec* ivAdd ( intvec a,
intvec b 
)

Definition at line 248 of file intvec.cc.

250 {
251  intvec * iv;
252  int mn, ma, i;
253  if (a->cols() != b->cols()) return NULL;
254  mn = si_min(a->rows(),b->rows());
255  ma = si_max(a->rows(),b->rows());
256  if (a->cols() == 1)
257  {
258  iv = new intvec(ma);
259  for (i=0; i<mn; i++) (*iv)[i] = (*a)[i] + (*b)[i];
260  if (ma > mn)
261  {
262  if (ma == a->rows())
263  {
264  for(i=mn; i<ma; i++) (*iv)[i] = (*a)[i];
265  }
266  else
267  {
268  for(i=mn; i<ma; i++) (*iv)[i] = (*b)[i];
269  }
270  }
271  return iv;
272  }
273  if (mn != ma) return NULL;
274  iv = new intvec(a);
275  for (i=0; i<mn*a->cols(); i++) { (*iv)[i] += (*b)[i]; }
276  return iv;

◆ ivColPivot()

static int ivColPivot ( intvec imat,
int  colpos,
int  rowpos,
int  ready,
int  all 
)
static

Definition at line 465 of file intvec.cc.

467 {
468  int rpiv;
469 
470  if (IMATELEM(*imat,rowpos,colpos)!=0)
471  return rowpos;
472  for (rpiv=ready+1;rpiv<=all;rpiv++)
473  {
474  if (IMATELEM(*imat,rpiv,colpos)!=0)
475  return rpiv;
476  }
477  return 0;

◆ ivConcat()

intvec* ivConcat ( intvec a,
intvec b 
)

Definition at line 803 of file intvec.cc.

805 {
806  int ac=a->cols();
807  int c = ac + b->cols(); int r = si_max(a->rows(),b->rows());
808  intvec * ab = new intvec(r,c,0);
809 
810  int i,j;
811  for (i=1; i<=a->rows(); i++)
812  {
813  for(j=1; j<=ac; j++)
814  IMATELEM(*ab,i,j) = IMATELEM(*a,i,j);
815  }
816  for (i=1; i<=b->rows(); i++)
817  {
818  for(j=1; j<=b->cols(); j++)
819  IMATELEM(*ab,i,j+ac) = IMATELEM(*b,i,j);
820  }
821  return ab;

◆ ivCondNumber()

static int ivCondNumber ( intvec w,
int  l 
)
static

Definition at line 745 of file intvec.cc.

747 {
748  int l0=0, i;
749 
750  if (l<0)
751  {
752  for (i=w->rows()-1;i>=0;i--)
753  {
754  if ((*w)[i]<0) l0--;
755  }
756  if (l0==0)
757  {
758  for (i=w->rows()-1;i>=0;i--)
759  {
760  if ((*w)[i]>0) l0++;
761  }
762  }
763  return l0;
764  }
765  else
766  {
767  for (i=w->rows()-1;i>=0;i--)
768  {
769  if ((*w)[i]<0) return -1;
770  }
771  for (i=w->rows()-1;i>=0;i--)
772  {
773  if ((*w)[i]>0) l0++;
774  }
775  return l0;
776  }

◆ ivContent()

static void ivContent ( intvec w)
static

Definition at line 778 of file intvec.cc.

780 {
781  int tgcd, m;
782  int i=w->rows()-1;
783 
784  loop
785  {
786  tgcd = (*w)[i--];
787  if (tgcd!=0) break;
788  if (i<0) return;
789  }
790  if (tgcd<0) tgcd = -tgcd;
791  if (tgcd==1) return;
792  loop
793  {
794  m = (*w)[i--];
795  if (m!=0) tgcd= ivGcd(tgcd, m);
796  if (tgcd==1) return;
797  if (i<0) break;
798  }
799  for (i=w->rows()-1;i>=0;i--)
800  (*w)[i] /= tgcd;

◆ ivFreeRow()

static void ivFreeRow ( intvec imat,
int  rowpos,
int  rpiv 
)
static

Definition at line 503 of file intvec.cc.

505 {
506  int i, j;
507 
508  for (j=rpiv-1;j>=rowpos;j--)
509  {
510  for (i=imat->cols();i!=0;i--)
511  IMATELEM(*imat,j+1,i) = IMATELEM(*imat,j,i);
512  }

◆ ivGcd()

static int ivGcd ( int  a,
int  b 
)
static

Definition at line 629 of file intvec.cc.

631 {
632  int x;
633 
634  if (a<0) a=-a;
635  if (b<0) b=-b;
636  if (b>a)
637  {
638  x=b;
639  b=a;
640  a=x;
641  }
642  while (b!=0)
643  {
644  x = a % b;
645  a = b;
646  b = x;
647  }
648  return a;

◆ ivKernFromRow()

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

Definition at line 594 of file intvec.cc.

597 {
598  int piv, cp, g, i, j, k, s;
599 
600  for (i=c;i>(*perm)[r];i--)
601  {
602  IMATELEM(*kern,pos,i) = 1;
603  for (j=r;j!=0;j--)
604  {
605  cp = (*perm)[j];
606  s=0;
607  for(k=c;k>cp;k--)
608  s += IMATELEM(*imat,j,k)*IMATELEM(*kern,pos,k);
609  if (s!=0)
610  {
611  piv = IMATELEM(*imat,j,cp);
612  g = ivGcd(piv,s);
613  if (g!=1)
614  {
615  s /= g;
616  piv /= g;
617  }
618  for(k=c;k>cp;k--)
619  IMATELEM(*kern,pos,k) *= piv;
620  IMATELEM(*kern,pos,cp) = -s;
621  ivRowContent(kern,pos,cp);
622  }
623  }
624  if (IMATELEM(*kern,pos,i)<0)
625  ivNegRow(kern,pos);
626  pos--;
627  }

◆ ivL1Norm()

static int ivL1Norm ( intvec w)
static

Definition at line 730 of file intvec.cc.

732 {
733  int i, j, s = 0;
734 
735  for (i=w->rows()-1;i>=0;i--)
736  {
737  j = (*w)[i];
738  if (j>0)
739  s += j;
740  else
741  s -= j;
742  }
743  return s;

◆ ivMult()

intvec* ivMult ( intvec a,
intvec b 
)

Definition at line 330 of file intvec.cc.

332 {
333  int i, j, k, sum,
334  ra = a->rows(), ca = a->cols(),
335  rb = b->rows(), cb = b->cols();
336  intvec * iv;
337  if (ca != rb) return NULL;
338  iv = new intvec(ra, cb, 0);
339  for (i=0; i<ra; i++)
340  {
341  for (j=0; j<cb; j++)
342  {
343  sum = 0;
344  for (k=0; k<ca; k++)
345  sum += (*a)[i*ca+k]*(*b)[k*cb+j];
346  (*iv)[i*cb+j] = sum;
347  }
348  }
349  return iv;

◆ ivNegRow()

static void ivNegRow ( intvec imat,
int  rpiv 
)
static

Definition at line 479 of file intvec.cc.

481 {
482  int i;
483  for (i=imat->cols();i!=0;i--)
484  IMATELEM(*imat,rpiv,i) = -(IMATELEM(*imat,rpiv,i));

◆ ivOptimizeKern()

static intvec * ivOptimizeKern ( intvec kern)
static

Definition at line 650 of file intvec.cc.

652 {
653  int i,l,j,c=kern->cols(),r=kern->rows();
654  intvec *res=new intvec(c);
655 
656  if (TEST_OPT_PROT)
657  Warn(" %d linear independent solutions\n",r);
658  for (i=r;i>1;i--)
659  {
660  for (j=c;j>0;j--)
661  {
662  (*res)[j-1] += IMATELEM(*kern,i,j);
663  }
664  }
665  ivContent(res);
666  if (r<11)
667  {
668  l = ivCondNumber(res,-c);
669  j = ivL1Norm(res);
670  ivOptRecursive(res, NULL, kern, l, j, r);
671  }
672  return res;

◆ ivOptRecursive()

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

Definition at line 674 of file intvec.cc.

677 {
678  int m, k, d;
679  intvec *h;
680 
681  d=kern->rows();
682  d=96/(d*d);
683  if (d<3) d=3;
684  if (w!=0)
685  h = new intvec(w);
686  else
687  h = new intvec(res->rows());
688  for (m=d;m>0;m--)
689  {
690  for(k=h->rows()-1;k>=0;k--)
691  (*h)[k] += IMATELEM(*kern,pos,k+1);
692  if(pos>1)
693  ivOptRecursive(res, h, kern, l, j, pos-1);
694  else
695  ivOptSolve(res, h, l, j);
696  }
697  delete h;
698  if (pos>1)
699  ivOptRecursive(res, w, kern, l, j, pos-1);
700  else if (w!=NULL)
701  ivOptSolve(res, w, l, j);

◆ ivOptSolve()

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

Definition at line 703 of file intvec.cc.

705 {
706  int l0, j0, k;
707 
708  l0 = ivCondNumber(w, l);
709  if (l0==l)
710  {
711  ivContent(w);
712  j0 = ivL1Norm(w);
713  if(j0<j)
714  {
715  j = j0;
716  for(k=w->rows()-1;k>=0;k--)
717  (*res)[k] = (*w)[k];
718  }
719  return;
720  }
721  if(l0>l)
722  {
723  l = l0;
724  ivContent(w);
725  j = ivL1Norm(w);
726  for(k=w->rows()-1;k>=0;k--)
727  (*res)[k] = (*w)[k];
728  }

◆ ivReduce()

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

Definition at line 514 of file intvec.cc.

517 {
518  int tgcd, ce, m1, m2, j, i;
519  int piv = IMATELEM(*imat,rpiv,colpos);
520 
521  for (j=all;j>ready;j--)
522  {
523  ivRowContent(imat, j, 1);
524  ce = IMATELEM(*imat,j,colpos);
525  if (ce!=0)
526  {
527  IMATELEM(*imat,j,colpos) = 0;
528  m1 = piv;
529  m2 = ce;
530  tgcd = ivGcd(m1, m2);
531  if (tgcd != 1)
532  {
533  m1 /= tgcd;
534  m2 /= tgcd;
535  }
536  for (i=imat->cols();i>colpos;i--)
537  {
538  IMATELEM(*imat,j,i) = IMATELEM(*imat,j,i)*m1-
539  IMATELEM(*imat,rpiv,i)*m2;
540  }
541  ivRowContent(imat, j, colpos+1);
542  }
543  }

◆ ivRowContent()

static void ivRowContent ( intvec imat,
int  rowpos,
int  colpos 
)
static

Definition at line 570 of file intvec.cc.

572 {
573  int tgcd, m;
574  int i=imat->cols();
575 
576  loop
577  {
578  tgcd = IMATELEM(*imat,rowpos,i--);
579  if (tgcd!=0) break;
580  if (i<colpos) return;
581  }
582  if (tgcd<0) tgcd = -tgcd;
583  if (tgcd==1) return;
584  loop
585  {
586  m = IMATELEM(*imat,rowpos,i--);
587  if (m!=0) tgcd= ivGcd(tgcd, m);
588  if (tgcd==1) return;
589  if (i<colpos) break;
590  }
591  for (i=imat->cols();i>=colpos;i--)
592  IMATELEM(*imat,rowpos,i) /= tgcd;

◆ ivSaveRow()

static void ivSaveRow ( intvec imat,
int  rpiv 
)
static

Definition at line 486 of file intvec.cc.

488 {
489  int i, j=imat->rows();
490 
491  for (i=imat->cols();i!=0;i--)
492  IMATELEM(*imat,j,i) = IMATELEM(*imat,rpiv,i);

◆ ivSetRow()

static void ivSetRow ( intvec imat,
int  rowpos,
int  colpos 
)
static

Definition at line 494 of file intvec.cc.

496 {
497  int i, j=imat->rows();
498 
499  for (i=imat->cols();i!=0;i--)
500  IMATELEM(*imat,rowpos,i) = IMATELEM(*imat,j,i);
501  ivRowContent(imat, rowpos, colpos);

◆ ivSolveKern()

intvec* ivSolveKern ( intvec imat,
int  dimtr 
)

Definition at line 423 of file intvec.cc.

425 {
426  int d=imat->cols();
427  int kdim=d-dimtr;
428  intvec *perm = new intvec(dimtr+1);
429  intvec *kern = new intvec(kdim,d,0);
430  intvec *res;
431  int c, cp, r, t;
432 
433  t = kdim;
434  c = 1;
435  for (r=1;r<=dimtr;r++)
436  {
437  while (IMATELEM(*imat,r,c)==0) c++;
438  (*perm)[r] = c;
439  c++;
440  }
441  c = d;
442  for (r=dimtr;r>0;r--)
443  {
444  cp = (*perm)[r];
445  if (cp!=c)
446  {
447  ivKernFromRow(kern, imat, perm, t, r, c);
448  t -= (c-cp);
449  if (t==0)
450  break;
451  c = cp-1;
452  }
453  else
454  c--;
455  }
456  if (kdim>1)
457  res = ivOptimizeKern(kern);
458  else
459  res = ivTranp(kern);
460  delete kern;
461  delete perm;
462  return res;

◆ ivSub()

intvec* ivSub ( intvec a,
intvec b 
)

Definition at line 278 of file intvec.cc.

280 {
281  intvec * iv;
282  int mn, ma, i;
283  if (a->cols() != b->cols()) return NULL;
284  mn = si_min(a->rows(),b->rows());
285  ma = si_max(a->rows(),b->rows());
286  if (a->cols() == 1)
287  {
288  iv = new intvec(ma);
289  for (i=0; i<mn; i++) (*iv)[i] = (*a)[i] - (*b)[i];
290  if (ma > mn)
291  {
292  if (ma == a->rows())
293  {
294  for(i=mn; i<ma; i++) (*iv)[i] = (*a)[i];
295  }
296  else
297  {
298  for(i=mn; i<ma; i++) (*iv)[i] = -(*b)[i];
299  }
300  }
301  return iv;
302  }
303  if (mn != ma) return NULL;
304  iv = new intvec(a);
305  for (i=0; i<mn*a->cols(); i++) { (*iv)[i] -= (*b)[i]; }
306  return iv;

◆ ivTrace()

int ivTrace ( intvec o)

Definition at line 320 of file intvec.cc.

322 {
323  int i, s = 0, m = si_min(o->rows(),o->cols()), c = o->cols();
324  for (i=0; i<m; i++)
325  {
326  s += (*o)[i*c+i];
327  }
328  return s;

◆ ivTranp()

intvec* ivTranp ( intvec o)

Definition at line 308 of file intvec.cc.

310 {
311  int i, j, r = o->rows(), c = o->cols();
312  intvec * iv= new intvec(c, r, 0);
313  for (i=0; i<r; i++)
314  {
315  for (j=0; j<c; j++)
316  (*iv)[j*r+i] = (*o)[i*c+j];
317  }
318  return iv;

◆ ivTriangIntern()

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

Definition at line 385 of file intvec.cc.

387 {
388  int rpiv, colpos=0, rowpos=0;
389  int ia=ready, ie=all;
390 
391  do
392  {
393  rowpos++;
394  do
395  {
396  colpos++;
397  rpiv = ivColPivot(imat, colpos, rowpos, ia, ie);
398  } while (rpiv==0);
399  if (rpiv>ia)
400  {
401  if (rowpos!=rpiv)
402  {
403  ivSaveRow(imat, rpiv);
404  ivFreeRow(imat, rowpos, rpiv);
405  ivSetRow(imat, rowpos, colpos);
406  rpiv = rowpos;
407  }
408  ia++;
409  if (ia==imat->cols())
410  {
411  ready = ia;
412  all = ie;
413  return;
414  }
415  }
416  ivReduce(imat, rpiv, colpos, ia, ie);
417  ivZeroElim(imat, colpos, ia, ie);
418  } while (ie>ia);
419  ready = ia;
420  all = ie;

◆ ivZeroElim()

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

Definition at line 545 of file intvec.cc.

548 {
549  int j, i, k, l;
550 
551  k = ready;
552  for (j=ready+1;j<=all;j++)
553  {
554  for (i=imat->cols();i>colpos;i--)
555  {
556  if (IMATELEM(*imat,j,i)!=0)
557  {
558  k++;
559  if (k<j)
560  {
561  for (l=imat->cols();l>colpos;l--)
562  IMATELEM(*imat,k,l) = IMATELEM(*imat,j,l);
563  }
564  break;
565  }
566  }
567  }
568  all = k;
si_min
static int si_min(const int a, const int b)
Definition: auxiliary.h:139
ivNegRow
static void ivNegRow(intvec *, int)
Definition: intvec.cc:479
ivOptimizeKern
static intvec * ivOptimizeKern(intvec *)
Definition: intvec.cc:650
j
int j
Definition: facHensel.cc:105
TEST_OPT_PROT
#define TEST_OPT_PROT
Definition: options.h:101
k
int k
Definition: cfEzgcd.cc:92
x
Variable x
Definition: cfModGcd.cc:4023
ivZeroElim
static void ivZeroElim(intvec *, int, int, int &)
Definition: intvec.cc:545
ivL1Norm
static int ivL1Norm(intvec *)
Definition: intvec.cc:730
ivGcd
static int ivGcd(int, int)
Definition: intvec.cc:629
g
g
Definition: cfModGcd.cc:4031
ivFreeRow
static void ivFreeRow(intvec *, int, int)
Definition: intvec.cc:503
loop
#define loop
Definition: structs.h:77
w
const CanonicalForm & w
Definition: facAbsFact.cc:55
b
CanonicalForm b
Definition: cfModGcd.cc:4044
ivTranp
intvec * ivTranp(intvec *o)
Definition: intvec.cc:308
ivSaveRow
static void ivSaveRow(intvec *, int)
Definition: intvec.cc:486
ivContent
static void ivContent(intvec *)
Definition: intvec.cc:778
i
int i
Definition: cfEzgcd.cc:125
res
CanonicalForm res
Definition: facAbsFact.cc:64
ivColPivot
static int ivColPivot(intvec *, int, int, int, int)
Definition: intvec.cc:465
h
static Poly * h
Definition: janet.cc:972
intvec
Definition: intvec.h:16
ivOptRecursive
static void ivOptRecursive(intvec *, intvec *, intvec *, int &, int &, int)
Definition: intvec.cc:674
ivReduce
static void ivReduce(intvec *, int, int, int, int)
Definition: intvec.cc:514
ivSetRow
static void ivSetRow(intvec *, int, int)
Definition: intvec.cc:494
IMATELEM
#define IMATELEM(M, I, J)
Definition: intvec.h:83
si_max
static int si_max(const int a, const int b)
Definition: auxiliary.h:138
intvec::cols
int cols() const
Definition: intvec.h:93
m
int m
Definition: cfEzgcd.cc:121
ivKernFromRow
static void ivKernFromRow(intvec *, intvec *, intvec *, int, int, int)
Definition: intvec.cc:594
NULL
#define NULL
Definition: omList.c:9
l
int l
Definition: cfEzgcd.cc:93
intvec::rows
int rows() const
Definition: intvec.h:94
Warn
#define Warn
Definition: emacs.cc:76
ivOptSolve
static void ivOptSolve(intvec *, intvec *, int &, int &)
Definition: intvec.cc:703
s
const CanonicalForm int s
Definition: facAbsFact.cc:55
ivRowContent
static void ivRowContent(intvec *, int, int)
Definition: intvec.cc:570
ivCondNumber
static int ivCondNumber(intvec *, int)
Definition: intvec.cc:745