Changeset d353551 in git

Timestamp:

Feb 18, 1998, 12:38:26 PM (26 years ago)

Author:

Thomas Siebert <siebert@…>

Branches:

(u'fieker-DuVal', '117eb8c30fc9e991c4decca4832b1d19036c4c65')(u'spielwiese', '38dfc5131670d387a89455159ed1e071997eec94')

Children:

5ae93aa2a4a8bf691b76d100c0f7289317d4dc57

Parents:

a28e0e917128c027c3071c68affbca085dcb3bd9

Message:

*** empty log message ***


git-svn-id: file:///usr/local/Singular/svn/trunk@1156 2c84dea3-7e68-4137-9b89-c4e89433aadc

Location:

Singular

Files:

• ideals.cc (modified) (2 diffs)
• matpol.cc (modified) (4 diffs)

Singular/ideals.cc

@@ -2 +2 @@
 *  Computer Algebra System SINGULAR     *
 ****************************************/
-/* $Id: ideals.cc,v 1.16 1998-01-12 18:59:47 obachman Exp $ */
+/* $Id: ideals.cc,v 1.17 1998-02-18 11:38:26 siebert Exp $ */
 /*
 * ABSTRACT - all basic methods to manipulate ideals
@@ -2270 +2270 @@
 }
 
+/*3
+* produces recursively the ideal of all arxar-minors of a
+*/
+static void idRecMin(matrix a,int ar,poly *barDiv,ideal result,
+              int * nextPlace, intvec * pfRows, intvec * iv)
+{
+Print("Level: %d\n",ar);
+/*--- there is no non-zero minor coming from a------------*/
+  if((ar<0) || (ar>min(a->ncols,a->nrows)-1))
+  {
+    return;
+  }
+
+/*--- initializing temporary structures-------------------*/
+  int i,j,r,c,newi,newp,k;
+  poly p=NULL,pp;
+  BOOLEAN justChosen=FALSE;
+
+  if (ar==0)
+  {
+/*--- ar is 0, the matrix-entres are minors---------------*/
+    for (i=a->nrows;i>0;i--)
+    {
+      for (j=a->ncols;j>0;j--)
+      {
+        p = MATELEM(a,i,j);
+        if (p!=NULL)
+        {
+          if (*nextPlace>=IDELEMS(result))
+          {
+            pEnlargeSet(&(result->m),IDELEMS(result),16);
+            IDELEMS(result) += 16;
+          }
+          MATELEM(a,i,j) = NULL;
+if ((*nextPlace==21) || (*nextPlace==37))
+{
+  Print("Hier sind sie!\n");
+}
+pWrite(p);
+          result->m[*nextPlace] = p;
+          (*nextPlace)++;
+        }
+      }
+    }
+    idDelete((ideal*)&a);
+    return;
+  }
+/*--- ar>0, we perform one step of the Bareiss algorithm--*/
+  p = pCopy(*barDiv);   //we had to store barDiv for the remaining loops
+  pp = pCopy(p);   //we had to store barDiv for the remaining loops
+  matrix nextStep = mpOneStepBareiss(a,barDiv,&r,&c);
+/*--- we compute the row-index of the chosen row r -------*/
+  newi = 0;
+  while ((newi<iv->length()) && ((*iv)[newi]!=0)) newi++;
+  k = (*iv)[newi] = r;
+  for (j=newi-1;j>0;j--)
+  {
+    if (k>=(*iv)[j]) k++;
+  }
+  newp = 0;
+  while ((newp<pfRows->length()) && ((*pfRows)[newp]!=0)) 
+  {
+    if ((*pfRows)[newp]==k) 
+    {
+      justChosen = TRUE;
+Print("just chosen\n");
+      break;
+    }
+    newp++;
+  }
+  if (!justChosen) (*pfRows)[newp] = k;
+Print("Chosen: ");pfRows->show();PrintLn();
+Print("Deleted: ");iv->show();PrintLn();
+/*--- we read out the r-1 x c-1 matrix for the next step--*/
+  if ((a->nrows-1)*(a->ncols-1)>0)
+  {
+    matrix next = mpNew(a->nrows-1,a->ncols-1);
+    for (i=a->nrows-1;i>0;i--)
+    {
+      for (j=a->ncols-1;j>0;j--)
+      {
+        MATELEM(next,i,j) = MATELEM(nextStep,i,j);
+        MATELEM(nextStep,i,j) =NULL;
+      }
+    }
+    idDelete((ideal*)&nextStep);
+/*--- we call the next Step------------------------------*/
+    idRecMin(next,ar-1,barDiv,result,nextPlace,pfRows,iv);
+    next = NULL;
+  }
+/*--- now we have to take out the r-th row...------------*/
+Print("back for rows on Level: %d\n",ar);
+Print("The actual row was %d\n",k);
+Print("Chosen: ");pfRows->show();PrintLn();
+Print("Deleted: ");iv->show();PrintLn();
+  if (((a->nrows)>1) && (!justChosen))
+  {
+    nextStep = mpNew(a->nrows-1,a->ncols);
+    for (i=r-1;i>0;i--)
+    {
+      for (j=a->ncols;j>0;j--)
+      {
+        MATELEM(nextStep,i,j) = pCopy(MATELEM(a,i,j));
+      }
+    }
+    for (i=a->nrows;i>r;i--)
+    {
+      for (j=a->ncols;j>0;j--)
+      {
+        MATELEM(nextStep,i-1,j) = pCopy(MATELEM(a,i,j));
+      }
+    }
+/*--- and to perform the algorithm with the rest---------*/
+    idRecMin(nextStep,ar,&p,result,nextPlace,pfRows,iv);
+    nextStep = NULL;
+  }
+/*--- now we have to take out the c-th col...------------*/
+Print("back for cols on Level: %d\n",ar);
+Print("Chosen: ");pfRows->show();PrintLn();
+Print("Deleted: ");iv->show();PrintLn();
+  if ((a->nrows)>1)
+  {
+    nextStep = mpNew(a->nrows,a->ncols-1);
+    for (i=a->nrows;i>0;i--)
+    {
+      for (j=c-1;j>0;j--)
+      {
+        MATELEM(nextStep,i,j) = MATELEM(a,i,j);
+        MATELEM(a,i,j) = NULL;
+      }
+    }
+    for (i=a->nrows;i>0;i--)
+    {
+      for (j=a->ncols;j>c;j--)
+      {
+        MATELEM(nextStep,i,j-1) = MATELEM(a,i,j);
+        MATELEM(a,i,j) = NULL;
+      }
+    }
+    idDelete((ideal*)&a);
+/*--- and to perform the algorithm with the rest---------*/
+    (*iv)[newi] = 0;
+    idRecMin(nextStep,ar,&p,result,nextPlace,pfRows,iv);
+    nextStep = NULL;
+  }
+/*--- deleting temporary structures and returns----------*/
+  if (!justChosen) (*pfRows)[newp] = 0;
+  pDelete(barDiv);
+  pDelete(&p);
+  pDelete(&pp);
+  return;
+}
+
+/*2
+* compute all ar-minors of the matrix a
+* the caller of idRecMin
+*/
+ideal idMinors1(matrix a, int ar)
+{
+  if((ar<=0) || (ar>min(a->ncols,a->nrows)))
+  {
+    Werror("%d-th minor ",ar);
+    return NULL;
+  }
+  int i=0;
+  intvec * iv=new intvec(a->nrows+1);
+  intvec * pv=new intvec(a->nrows+1);
+  poly barDiv=NULL;
+  ideal result=idInit(16,0);
+
+  idRecMin(mpCopy(a),ar-1,&barDiv,result,&i,pv,iv);
+  idSkipZeroes(result);
+  delete iv;
+  delete pv;
+  return result;
+}
+
 /*2
 *returns TRUE if p is a unit element in the current ring

Singular/matpol.cc

@@ -2 +2 @@
 *  Computer Algebra System SINGULAR     *
 ****************************************/
-/* $Id: matpol.cc,v 1.8 1998-01-12 17:32:48 Singular Exp $ */
+/* $Id: matpol.cc,v 1.9 1998-02-18 11:35:31 siebert Exp $ */
 
 /*
@@ -331 +331 @@
   void mpElimBareiss(poly);
   int mpPivotBareiss(row_col_weight *);
+  int mpPivotRow(row_col_weight *, int);
   void mpToIntvec(intvec *);
   void mpRowReorder();
@@ -388 +389 @@
   mp_permmatrix *Bareiss = new mp_permmatrix(re);
   row_col_weight w(Bareiss->mpGetRdim(), Bareiss->mpGetCdim());
+  int row = *r;
 
   /* step of Bareiss */
-  if(Bareiss->mpPivotBareiss(&w))
+  if((row && Bareiss->mpPivotRow(&w,row-1)) || Bareiss->mpPivotBareiss(&w))
   {
     Bareiss->mpElimBareiss(div);
@@ -1112 +1114 @@
 }
 
+/*2
+* pivot strategy for Bareiss algorithm with defined row
+*/
+int mp_permmatrix::mpPivotRow(row_col_weight *C, int row)
+{
+  poly p, *a;
+  int j, iopt, jopt;
+  float sum, f1, f2, fo, r, ro, lp;
+  float *dr = C->wrow, *dc = C->wcol;
+
+  fo = 1.0e20;
+  ro = 0.0;
+  iopt = jopt = -1;
+  
+  s_n--;
+  s_m--;
+  if (s_m == 0)
+    return 0;
+  if (s_n == 0)
+  {
+    p = this->mpRowAdr(row)[qcol[0]];
+    if (p)
+    {
+      f1 = mpPolyWeight(p);
+      if (f1 < fo)
+      {
+        fo = f1;
+        if (iopt >= 0)
+        pDelete(&(this->mpRowAdr(iopt)[qcol[0]]));
+        iopt = row;
+      }
+      else
+        pDelete(&(this->mpRowAdr(row)[qcol[0]]));
+    }
+    if (iopt >= 0)
+      mpReplace(iopt, s_m, sign, qrow);
+    return 0;
+  }
+  this->mpRowWeight(dr);
+  this->mpColWeight(dc);
+  sum = 0.0;
+  for(j=s_m; j>=0; j--)
+    sum += dr[j];
+  r = dr[row];
+  a = this->mpRowAdr(row);
+  for(j=s_n; j>=0; j--)
+  {
+    p = a[qcol[j]];
+    if (p)
+    {
+      lp = mpPolyWeight(p);
+      ro = r - lp;
+      f1 = ro * (dc[j]-lp);
+      if (f1 != 0.0)
+      {
+        f2 = lp * (sum - ro - dc[j]);
+        f2 += f1;
+      }
+      else
+        f2 = lp-r-dc[j];
+      if (f2 < fo)
+      {
+        fo = f2;
+        iopt = row;
+        jopt = j;
+      }
+    }
+  }
+  if (iopt < 0)
+    return 0;
+  mpReplace(iopt, s_m, sign, qrow);
+  mpReplace(jopt, s_n, sign, qcol);
+  return 1;
+}
+
 void mp_permmatrix::mpToIntvec(intvec *v)
 {