Changeset 6a0cc83 in git

Timestamp:

Oct 5, 2004, 6:43:06 PM (20 years ago)

Author:

Michael Brickenstein <bricken@…>

Branches:

(u'spielwiese', 'fe61d9c35bf7c61f2b6cbf1b56e25e2f08d536cc')

Children:

ecd2adc73320b43f7a1c71b146a67eebd2be1d7b

Parents:

4dac0e7b03a9dfa5b46417ef355c40c878b79770

Message:

*bricken: cache for gauss


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

File:

• Singular/tgb.cc (modified) (8 diffs)

Singular/tgb.cc

@@ -2428 +2428 @@
     return mp[row]->exp;
   }
+  else
+
  
   return columns;//error code
@@ -2480 +2482 @@
   assume(mat->mp[row]==NULL);
   mat->mp[row]=m;
+#ifdef TGB_DEBUG
+  mac_poly r=m;
+  while(r){
+    assume(r->exp<mat->columns);
+    r=r->next;
+  }
+#endif
 }
 poly free_row_to_poly(tgb_sparse_matrix* mat, int row, poly* monoms, int monom_index){
@@ -2500 +2509 @@
 void simple_gauss(tgb_sparse_matrix* mat){
   int col, row;
+  int* row_cache=(int*) omalloc(mat->get_rows()*sizeof(int));
   col=0;
   row=0;
   int i;
   int pn=mat->get_rows();
+  int matcol=mat->get_columns();
   assume(pn>0);
   //first clear zeroes
@@ -2511 +2522 @@
     {
       mat->perm_rows(i,pn-1);
+      row_cache[pn-1]=matcol;
       pn--;
       if(i!=pn){i--;}
     }
+    else
+      row_cache[i]=mat->min_col_not_zero_in_row(i);
   }
   while(row<pn-1){
@@ -2522 +2536 @@
     //select column
    
-    col=mat->min_col_not_zero_in_row(row);
-    assume(col!=mat->get_columns());
+    //col=mat->min_col_not_zero_in_row(row);
+    assume(row_cache[row]==mat->min_col_not_zero_in_row(row));
+    col=row_cache[row];
+
+    
+    assume(col!=matcol);
     int found_in_row;
     
@@ -2529 +2547 @@
     assume(pn<=mat->get_rows());
     for(i=row+1;i<pn;i++){
-      int first=mat->min_col_not_zero_in_row(i);
+      int first;//=mat->min_col_not_zero_in_row(i);
+      assume(row_cache[i]==mat->min_col_not_zero_in_row(i));
+      first=row_cache[i];
+      assume(first!=matcol);
       if(first<col)
       {
@@ -2538 +2559 @@
     //select pivot
     int act_l=mat->non_zero_entries(found_in_row);
-    for(i=row+1;i<pn;i++){
+    for(i=found_in_row+1;i<pn;i++){
       assume(mat->min_col_not_zero_in_row(i)>=col);
-      if((!(mat->is_zero_entry(i,col)))&&(mat->non_zero_entries(i)<act_l))
+      int first;
+      assume(row_cache[i]==mat->min_col_not_zero_in_row(i));
+      first=row_cache[i];
+      assume(first!=matcol);
+      //      if((!(mat->is_zero_entry(i,col)))&&(mat->non_zero_entries(i)<act_l))
+      int nz;
+      if((row_cache[i]==col)&&((nz=mat->non_zero_entries(i))<act_l))
       {
         found_in_row=i;
-        act_l=mat->non_zero_entries(i);//should be optimized here
-      }
-
-    }
+        act_l=nz;
+      }
+
+    }
+#ifdef TGB_DEBUG
+  {
+  int last=-1;
+  for(i=0;i<pn;i++)
+  {
+    int act=mat->min_col_not_zero_in_row(i);
+    assume(act>last);
+    
+  }
+  for(i=pn;i<mat->get_rows();i++)
+  {
+    assume(mat->zero_row(i));
+    
+  }
+  
+
+  }
+#endif
     mat->perm_rows(row,found_in_row);
-
-    
+    int h=row_cache[row];
+    row_cache[row]=row_cache[found_in_row];
+    row_cache[found_in_row]=h;
+#ifdef TGB_DEBUG
+  {
+  int last=-1;
+  for(i=0;i<pn;i++)
+  {
+    int act=mat->min_col_not_zero_in_row(i);
+    assume(act>last);
+    
+  }
+  for(i=pn;i<mat->get_rows();i++)
+  {
+    assume(mat->zero_row(i));
+    
+  }
+  
+
+  }
+#endif  
     //reduction
     for(i=row+1;i<pn;i++){
       assume(mat->min_col_not_zero_in_row(i)>=col);
-      if(!(mat->is_zero_entry(i,col)))
+      int first;
+      assume(row_cache[i]==mat->min_col_not_zero_in_row(i));
+      first=row_cache[i];
+      assume(first!=matcol);
+      if(row_cache[i]==col)
       {
         
@@ -2566 +2634 @@
         mat->add_lambda_times_row(i,row,n1);
         assume(mat->is_zero_entry(i,col));
+        row_cache[i]=mat->min_col_not_zero_in_row(i);
 
       } 
       assume(mat->min_col_not_zero_in_row(i)>col);
     }
+#ifdef TGB_DEBUG
+  {
+  int last=-1;
+  for(i=0;i<pn;i++)
+  {
+    int act=mat->min_col_not_zero_in_row(i);
+    assume(act>last);
+    
+  }
+  for(i=pn;i<mat->get_rows();i++)
+  {
+    assume(mat->zero_row(i));
+    
+  }
+  
+
+  }
+#endif
     for(i=row+1;i<pn;i++)
     {
-      if(mat->zero_row(i))
+      assume(mat->min_col_not_zero_in_row(i)==row_cache[i]);
+      // if(mat->zero_row(i))
+      assume(matcol==mat->get_columns());
+      if(row_cache[i]==matcol)
       {
+        assume(mat->zero_row(i));
         mat->perm_rows(i,pn-1);
+        row_cache[i]=row_cache[pn-1];
+        row_cache[pn-1]=matcol;
         pn--;
         if(i!=pn){i--;}
       }
     }
+#ifdef TGB_DEBUG
+  {
+  int last=-1;
+  for(i=0;i<pn;i++)
+  {
+    int act=mat->min_col_not_zero_in_row(i);
+    assume(act>last);
+    
+  }
+  for(i=pn;i<mat->get_rows();i++)
+  {
+    assume(mat->zero_row(i));
+    
+  }
+  
+
+  }
+#endif
     row++;
   }
+#ifdef TGB_DEBUG
+  {
+  int last=-1;
+  for(i=0;i<pn;i++)
+  {
+    int act=mat->min_col_not_zero_in_row(i);
+    assume(act>last);
+    
+  }
+  for(i=pn;i<mat->get_rows();i++)
+  {
+    assume(mat->zero_row(i));
+    
+  }
+  
+
+  }
+#endif
+  omfree(row_cache);
 }
 void simple_gauss2(tgb_matrix* mat){