Changeset 686ce3 in git

Timestamp:

Jan 17, 2011, 4:35:50 PM (13 years ago)

Author:

Martin Lee <martinlee84@…>

Branches:

(u'spielwiese', 'fe61d9c35bf7c61f2b6cbf1b56e25e2f08d536cc')

Children:

da2bd09796fb2e16163e9e0cdb0c34e541a200de

Parents:

54667770cf90dd8ee3b56fbe6b4116e50118c921

Message:

added substitution of x^n->x


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

Location:

factory

Files:

• facFqBivar.cc (modified) (1 diff)
• facFqBivarUtil.cc (modified) (1 diff)
• facFqBivarUtil.h (modified) (1 diff)

factory/facFqBivar.cc

@@ -1007 +1007 @@
     }
 
+    if (i == 0)
+    {
+      int subCheck= substituteCheck (bufUniFactors);
+
+      if (subCheck > 1)
+      {
+        CanonicalForm bufA= A;
+        subst (bufA, bufA, subCheck, x);
+        factors= biFactorize (bufA, info);
+        reverseSubst (factors, subCheck, x);
+        appendSwapDecompress (factors, contentAxFactors, contentAyFactors,
+                              swap, swap2, N);
+        normalize (factors);
+        return factors;
+      }
+
+      if (!derivXZero && !fail2)
+      {
+        subCheck= substituteCheck (bufUniFactors2);
+        if (subCheck > 1)
+        {
+          CanonicalForm bufA= A;
+          subst (bufA, bufA, subCheck, y);
+          factors= biFactorize (bufA, info);
+          reverseSubst (factors, subCheck, x);
+          appendSwapDecompress (factors, contentAxFactors, contentAyFactors,
+                                swap, swap2, N);
+          normalize (factors);
+          return factors;
+        }
+      }
+    }
+
     // degree analysis
     bufDegs = DegreePattern (bufUniFactors);

factory/facFqBivarUtil.cc

@@ -389 +389 @@
 }
 
+static int
+substituteCheck (const CanonicalForm& F, const CanonicalForm& G)
+{
+  if (F.inCoeffDomain() || G.inCoeffDomain())
+    return 0;
+  Variable x= Variable (1);
+  if (degree (F, x) <= 1 || degree (G, x) <= 1)
+    return 0;
+  CanonicalForm f= swapvar (F, F.mvar(), x);
+  CanonicalForm g= swapvar (G, G.mvar(), x);
+  int sizef= 0;
+  int sizeg= 0;
+  for (CFIterator i= f; i.hasTerms(); i++, sizef++)
+  {
+    if (i.exp() == 1)
+      return 0;
+  }
+  for (CFIterator i= g; i.hasTerms(); i++, sizeg++)
+  {
+    if (i.exp() == 1)
+      return 0;
+  }
+  int * expf= new int [sizef];
+  int * expg= new int [sizeg];
+  int j= 0;
+  for (CFIterator i= f; i.hasTerms(); i++, j++)
+  {
+    expf [j]= i.exp();
+  }
+  j= 0;
+  for (CFIterator i= g; i.hasTerms(); i++, j++)
+  {
+    expg [j]= i.exp();
+  }
+
+  int indf= sizef - 1;
+  int indg= sizeg - 1;
+  if (expf[indf] == 0)
+    indf--;
+  if (expg[indg] == 0)
+    indg--;
+
+  if ((expg[indg]%expf [indf] != 0 && expf[indf]%expg[indg] != 0) ||
+      (expg[indg] == 1 && expf[indf] == 1))
+  {
+    delete [] expg;
+    delete [] expf;
+    return 0;
+  }
+
+  int result;
+  if (expg [indg]%expf [indf] == 0)
+    result= expf[indf];
+  else
+    result= expg[indg];
+  for (int i= indf - 1; i >= 0; i--)
+  {
+    if (expf [i]%result != 0)
+    {
+      delete [] expf;
+      delete [] expg;
+      return 0;
+    }
+  }
+
+  for (int i= indg - 1; i >= 0; i--)
+  {
+    if (expg [i]%result != 0)
+    {
+      delete [] expf;
+      delete [] expg;
+      return 0;
+    }
+  }
+
+  delete [] expg;
+  delete [] expf;
+  return result;
+}
+
+int recSubstituteCheck (const CanonicalForm& F, const int d)
+{
+  if (F.inCoeffDomain())
+    return 0;
+  Variable x= Variable (1);
+  if (degree (F, x) <= 1)
+    return 0;
+  CanonicalForm f= swapvar (F, F.mvar(), x);
+  int sizef= 0;
+  for (CFIterator i= f; i.hasTerms(); i++, sizef++)
+  {
+    if (i.exp() == 1)
+      return 0;
+  }
+  int * expf= new int [sizef];
+  int j= 0;
+  for (CFIterator i= f; i.hasTerms(); i++, j++)
+  {
+    expf [j]= i.exp();
+  }
+
+  int indf= sizef - 1;
+  if (expf[indf] == 0)
+    indf--;
+
+  if ((d%expf [indf] != 0 && expf[indf]%d != 0) || (expf[indf] == 1))
+  {
+    delete [] expf;
+    return 0;
+  }
+
+  int result;
+  if (d%expf [indf] == 0)
+    result= expf[indf];
+  else
+    result= d;
+  for (int i= indf - 1; i >= 0; i--)
+  {
+    if (expf [i]%result != 0)
+    {
+      delete [] expf;
+      return 0;
+    }
+  }
+
+  delete [] expf;
+  return result;
+}
+
+int substituteCheck (const CFList& L)
+{
+  ASSERT (L.length() > 1, "expected a list of at least two elements");
+  if (L.length() < 2)
+    return 0;
+  CFListIterator i= L;
+  i++;
+  int result= substituteCheck (L.getFirst(), i.getItem());
+  if (result <= 1)
+    return result;
+  i++;
+  for (;i.hasItem(); i++)
+  {
+    result= recSubstituteCheck (i.getItem(), result);
+    if (result <= 1)
+      return result;
+  }
+  return result;
+}
+
+void
+subst (const CanonicalForm& F, CanonicalForm& A, const int d, const Variable& x)
+{
+  if (d <= 1)
+  {
+    A= F;
+    return;
+  }
+  if (degree (F, x) <= 0)
+  {
+    A= F;
+    return;
+  }
+  CanonicalForm C= 0;
+  CanonicalForm f= swapvar (F, x, F.mvar());
+  for (CFIterator i= f; i.hasTerms(); i++)
+    C += i.coeff()*power (f.mvar(), i.exp()/ d);
+  A= swapvar (C, x, F.mvar());
+}
+
+CanonicalForm
+reverseSubst (const CanonicalForm& F, const int d, const Variable& x)
+{
+  if (d <= 1)
+    return F;
+  if (degree (F, x) <= 0)
+    return F;
+  CanonicalForm f= swapvar (F, x, F.mvar());
+  CanonicalForm result= 0;
+  for (CFIterator i= f; i.hasTerms(); i++)
+    result += i.coeff()*power (f.mvar(), d*i.exp());
+  return swapvar (result, x, F.mvar());
+}
+
+void
+reverseSubst (CFList& L, const int d, const Variable& x)
+{
+  for (CFListIterator i= L; i.hasItem(); i++)
+    i.getItem()= reverseSubst (i.getItem(), d, x);
+}
+

factory/facFqBivarUtil.h

@@ -158 +158 @@
                      );
 
+/// checks if a substitution x^n->x is possible
+///
+/// @return an integer n > 1, if a substitution described as above is possible
+///         else n <= 1
+int substituteCheck (const CFList& L ///< [in] a list of univariate polys
+                    );
+
+/// substitute x^d by x in F
+void
+subst (const CanonicalForm& F, ///< [in] a polynomial 
+       CanonicalForm& A,       ///< [in,out] returns F with x^d replaced by x
+       const int d,            ///< d > 1 such that a substitution x^d -> x
+                               ///< [in] is possible
+       const Variable& x       ///< [in] a Variable
+      );
+
+/// reverse a substitution x^d->x
+///
+/// @return a poly with x replaced by x^d
+CanonicalForm
+reverseSubst (const CanonicalForm& F, ///< [in] a poly
+              const int d,            ///< [in] an integer > 0
+              const Variable& x       ///< [in] a Variable
+             );
+
+/// reverse a substitution x^d->x
+void
+reverseSubst (CFList& L,        ///< [in,out] a list of polys, returns the 
+                                ///< given list with x replaced by x^d
+              const int d,      ///< [in] an integer > 0
+              const Variable& x ///< [in] a Variable
+             );
+
 #endif
 /* FAC_FQ_BIVAR_UTIL_H */