Changeset dad0bc5 in git

Timestamp:

Dec 9, 2005, 9:35:38 AM (18 years ago)

Author:

Hans Schönemann <hannes@…>

Branches:

(u'spielwiese', 'a7324b6e0b44a1a8ed3fa4d9ca3e2ff210ddd52c')

Children:

172b7ae49955a6c96c685cbe68ee3f257d89bd46

Parents:

1b82a2e051a986276fd759237c823aecfb97b2be

Message:

*hannes: factorization of homog.polys, SORT for factorize


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

Location:

factory

Files:

• NTLconvert.cc (modified) (9 diffs)
• canonicalform.cc (modified) (3 diffs)
• canonicalform.h (modified) (2 diffs)
• cf_algorithm.cc (modified) (2 diffs)
• cf_algorithm.h (modified) (2 diffs)
• cf_factor.cc (modified) (3 diffs)
• fac_cantzass.cc (modified) (2 diffs)

factory/NTLconvert.cc

@@ -1 @@
-/* $Id: NTLconvert.cc,v 1.13 2004-01-19 11:26:19 Singular Exp $ */
+/* $Id: NTLconvert.cc,v 1.14 2005-12-09 08:35:37 Singular Exp $ */
 #include <config.h>
 
@@ -419 +419 @@
 }
 
-int NTLcmpCF( const CFFactor & f, const CFFactor & g )
-{
-  if (f.exp() > g.exp()) return 1;
-  if (f.exp() < g.exp()) return 0;
-  if (f.factor() > g.factor()) return 1;
-  return 0;
-}
-
 ////////////////////////////////////////////////////////////////////////////////
 // NAME: convertNTLvec_pair_ZZpX_long2FacCFFList                              //
@@ -468 +460 @@
     rueckgabe.append(CFFactor(convertNTLZZpX2CF(e[i].a,x),e[i].b));
   }
-  if(isOn(SW_USE_NTL_SORT)) rueckgabe.sort(NTLcmpCF);
   // the multiplicity at pos 1
   if (!IsOne(multi))
@@ -495 +486 @@
     rueckgabe.append(CFFactor(convertNTLzzpX2CF(e[i].a,x),e[i].b));
   }
-  if(isOn(SW_USE_NTL_SORT)) rueckgabe.sort(NTLcmpCF);
   // the multiplicity at pos 1
   if (!IsOne(multi))
@@ -556 +546 @@
     rueckgabe.append(CFFactor(bigone,exponent));
   }
-  if(isOn(SW_USE_NTL_SORT)) rueckgabe.sort(NTLcmpCF);
   return rueckgabe;
 }
@@ -777 +766 @@
     rueckgabe.append(CFFactor(bigone,exponent));
   }
-  if(isOn(SW_USE_NTL_SORT)) rueckgabe.sort(NTLcmpCF);
   // the multiplicity at pos 1
   //if (!IsOne(multi))
@@ -869 +857 @@
     rueckgabe.append(CFFactor(bigone,exponent));
   }
-  if(isOn(SW_USE_NTL_SORT)) rueckgabe.sort(NTLcmpCF);
   // Start by appending the multiplicity
   if (!IsOne(multi))
@@ -914 +901 @@
     rueckgabe.append(CFFactor(bigone,exponent));
   }
-  if(isOn(SW_USE_NTL_SORT)) rueckgabe.sort(NTLcmpCF);
   // Start by appending the multiplicity
   if (!IsOne(multi))
@@ -1007 +993 @@
 
   }
-  if(isOn(SW_USE_NTL_SORT)) rueckgabe.sort(NTLcmpCF);
   // return the computed CFFList
   return rueckgabe;

factory/canonicalform.cc

@@ -1 +1 @@
 /* emacs edit mode for this file is -*- C++ -*- */
-/* $Id: canonicalform.cc,v 1.35 2005-10-18 12:33:00 Singular Exp $ */
+/* $Id: canonicalform.cc,v 1.36 2005-12-09 08:35:37 Singular Exp $ */
 
 #include <config.h>
@@ -12 +12 @@
 #include "int_cf.h"
 #include "cf_factory.h"
+#include "cf_algorithm.h"
 #include "imm.h"
 #include "gfops.h"
@@ -181 +182 @@
         return value->isUnivariate();
 }
+
+// is_homogeneous returns 1 iff f is homogeneous, 0 otherwise//
+bool
+CanonicalForm::isHomogeneous() const
+{
+  if (this->isZero()) return true;
+  else if (this->inCoeffDomain()) return true;
+  else
+  {
+#if 0
+    CFIterator i;
+    int cdeg = -2, dummy;
+    for ( i = *this; i.hasTerms(); i++ )
+    {
+      if (!(i.coeff().isHomogeneous())) return false;
+      if ( (dummy = totaldegree( i.coeff() ) + i.exp()) != cdeg )
+      {
+         if (cdeg == -2) cdeg = dummy;
+         else return false;
+      }
+    }
+    return true;
+#else
+    CFList termlist= get_Terms(*this);
+    CFListIterator i;
+    int deg= totaldegree(termlist.getFirst());
+
+    for ( i=termlist; i.hasItem(); i++ )
+      if ( totaldegree(i.getItem()) != deg ) return false;
+    return true;
+#endif
+  }
+}
+
 //}}}
 

factory/canonicalform.h

@@ -1 +1 @@
 /* emacs edit mode for this file is -*- C++ -*- */
-/* $Id: canonicalform.h,v 1.29 2005-10-18 13:16:14 Singular Exp $ */
+/* $Id: canonicalform.h,v 1.30 2005-12-09 08:35:37 Singular Exp $ */
 
 #ifndef INCL_CANONICALFORM_H
@@ -89 +89 @@
     bool isFFinGF() const;
     bool isUnivariate() const;
+    bool isHomogeneous() const;
 
     // conversion functions

factory/cf_algorithm.cc

@@ -1 +1 @@
 /* emacs edit mode for this file is -*- C++ -*- */
-/* $Id: cf_algorithm.cc,v 1.9 2003-05-31 12:35:05 Singular Exp $ */
+/* $Id: cf_algorithm.cc,v 1.10 2005-12-09 08:35:37 Singular Exp $ */
 
 //{{{ docu
@@ -119 +119 @@
   else { l = 1; }
   d= dr-dv+1;
-  while ( ( dv <= dr  ) && ( r != r.genZero()) ){
+  while ( ( dv <= dr  ) && ( r != r.genZero()) )
+  {
     test = power(x,dr-dv)*v*LC(r,x);
     if ( dr == 0 ) { r= CanonicalForm(0); }

factory/cf_algorithm.h

@@ -1 +1 @@
 /* emacs edit mode for this file is -*- C++ -*- */
-/* $Id: cf_algorithm.h,v 1.11 1998-06-30 16:31:24 schmidt Exp $ */
+/* $Id: cf_algorithm.h,v 1.12 2005-12-09 08:35:37 Singular Exp $ */
 
 #ifndef INCL_CF_ALGORITHM_H
@@ -61 +61 @@
 
 bool isSqrFree ( const CanonicalForm & f );
+
+CanonicalForm homogenize( const CanonicalForm & f, const Variable & x);
+Variable get_max_degree_Variable(const CanonicalForm & f);
+CFList get_Terms( const CanonicalForm & f );
+void getTerms( const CanonicalForm & f, const CanonicalForm & t, CFList & result );
+
+
 //}}}
 

factory/cf_factor.cc

@@ -1 +1 @@
 /* emacs edit mode for this file is -*- C++ -*- */
-/* $Id: cf_factor.cc,v 1.26 2005-08-22 17:24:01 Singular Exp $ */
+/* $Id: cf_factor.cc,v 1.27 2005-12-09 08:35:38 Singular Exp $ */
 
 //{{{ docu
@@ -172 +172 @@
 }
 
+///////////////////////////////////////////////////////////////
+// get_max_degree_Variable returns Variable with             //
+// highest degree. We assume f is *not* a constant!          //
+///////////////////////////////////////////////////////////////
+Variable
+get_max_degree_Variable(const CanonicalForm & f)
+{
+  ASSERT( ( ! f.inCoeffDomain() ), "no constants" );
+  int max=0, maxlevel=0, n=level(f);
+  for ( int i=1; i<=n; i++ )
+  {
+    if (degree(f,Variable(i)) >= max)
+    {
+      max= degree(f,Variable(i)); maxlevel= i;
+    }
+  }
+  return Variable(maxlevel);
+}
+
+///////////////////////////////////////////////////////////////
+// get_Terms: Split the polynomial in the containing terms.  //
+// getTerms: the real work is done here.                     //
+///////////////////////////////////////////////////////////////
+void
+getTerms( const CanonicalForm & f, const CanonicalForm & t, CFList & result )
+{
+  if ( getNumVars(f) == 0 ) result.append(f*t);
+  else{
+    Variable x(level(f));
+    for ( CFIterator i=f; i.hasTerms(); i++ )
+      getTerms( i.coeff(), t*power(x,i.exp()), result);
+  }
+}
+CFList
+get_Terms( const CanonicalForm & f ){
+  CFList result,dummy,dummy2;
+  CFIterator i;
+  CFListIterator j;
+
+  if ( getNumVars(f) == 0 ) result.append(f);
+  else{
+    Variable _x(level(f));
+    for ( i=f; i.hasTerms(); i++ ){
+      getTerms(i.coeff(), 1, dummy);
+      for ( j=dummy; j.hasItem(); j++ )
+        result.append(j.getItem() * power(_x, i.exp()));
+
+      dummy= dummy2; // have to initalize new
+    }
+  }
+  return result;
+}
+
+
+///////////////////////////////////////////////////////////////
+// homogenize homogenizes f with Variable x                  //
+///////////////////////////////////////////////////////////////
+
+CanonicalForm
+homogenize( const CanonicalForm & f, const Variable & x)
+{
+#if 0
+  int maxdeg=totaldegree(f), deg;
+  CFIterator i;
+  CanonicalForm elem, result=f.genZero();
+  
+  for (i=f; i.hasTerms(); i++)
+  {
+    elem= i.coeff()*power(f.mvar(),i.exp());
+    deg = totaldegree(elem);
+    if ( deg < maxdeg )
+      result += elem * power(x,maxdeg-deg);
+    else 
+      result+=elem;
+  }
+  return result;
+#else
+  CFList Newlist, Termlist= get_Terms(f);
+  int maxdeg=totaldegree(f), deg;
+  CFListIterator i;
+  CanonicalForm elem, result=f.genZero();
+
+  for (i=Termlist; i.hasItem(); i++){
+    elem= i.getItem();
+    deg = totaldegree(elem);
+    if ( deg < maxdeg )
+      Newlist.append(elem * power(x,maxdeg-deg));
+    else
+      Newlist.append(elem);
+  }
+  for (i=Newlist; i.hasItem(); i++) // rebuild
+    result += i.getItem();
+
+  return result;
+#endif
+}
+
+#ifdef SINGULAR
+extern int singular_homog_flag;
+#else
+#define singular_homog_flag 1
+#endif
+static int cmpCF( const CFFactor & f, const CFFactor & g )
+{
+  if (f.exp() > g.exp()) return 1;
+  if (f.exp() < g.exp()) return 0;
+  if (f.factor() > g.factor()) return 1;
+  return 0;
+}
+
 CFFList factorize ( const CanonicalForm & f, bool issqrfree )
 {
   if ( f.inCoeffDomain() )
         return CFFList( f );
-  //out_cf("factorize:",f,"==================================\n");
   int mv=f.level();
   int org_v=mv;
+  //out_cf("factorize:",f,"==================================\n");
   if (! f.isUnivariate() )
   {
+    if ( singular_homog_flag && f.isHomogeneous())
+    {
+      Variable xn = get_max_degree_Variable(f);
+      int d_xn = degree(f,xn);
+      CFMap n;
+      CanonicalForm F = compress(f(1,xn),n);
+      CFFList Intermediatelist;
+      Intermediatelist = factorize(F);
+      CFFList Homoglist;
+      CFFListIterator j;
+      for ( j=Intermediatelist; j.hasItem(); j++ )
+      {
+        Homoglist.append(
+            CFFactor( n(j.getItem().factor()), j.getItem().exp()) );
+      }
+      CFFList Unhomoglist;
+      CanonicalForm unhomogelem;
+      for ( j=Homoglist; j.hasItem(); j++ )
+      {
+        unhomogelem= homogenize(j.getItem().factor(),xn);
+        Unhomoglist.append(CFFactor(unhomogelem,j.getItem().exp()));
+        d_xn -= (degree(unhomogelem,xn)*j.getItem().exp());
+      }
+      if ( d_xn != 0 ) // have to append xn^(d_xn)
+        Unhomoglist.append(CFFactor(CanonicalForm(xn),d_xn));  
+      if(isOn(SW_USE_NTL_SORT)) Unhomoglist.sort(cmpCF); 
+      return Unhomoglist;
+    }
     mv=find_mvar(f);
     if ( getCharacteristic() == 0 )
@@ -365 +503 @@
   }
   //out_cff(F);
+  if(isOn(SW_USE_NTL_SORT)) F.sort(cmpCF); 
   return F;
 }

factory/fac_cantzass.cc

@@ -1 +1 @@
 /* emacs edit mode for this file is -*- C++ -*- */
-/* $Id: fac_cantzass.cc,v 1.7 2004-10-11 10:49:20 Singular Exp $ */
+/* $Id: fac_cantzass.cc,v 1.8 2005-12-09 08:35:38 Singular Exp $ */
 
 #include <config.h>
@@ -105 +105 @@
     if ( numext > 0 )
         mpz_clear( &qq );
-#ifdef HAVE_NTL
-    extern  int NTLcmpCF( const CFFactor & f, const CFFactor & g );
-    if(isOn(SW_USE_NTL_SORT)) H.sort(NTLcmpCF);
-#endif    
     return H;
 }