Changeset 73c222 in git

Timestamp:

Jul 31, 2013, 4:59:25 PM (10 years ago)

Author:

Martin Lee <martinlee84@…>

Branches:

(u'jengelh-datetime', 'ceac47cbc86fe4a15902392bdbb9bd2ae0ea02c6')(u'spielwiese', 'a800fe4b3e9d37a38c5a10cc0ae9dfa0c15a4ee6')

Children:

091b25018851d6b7049240bf5eb739710e97cb1a

Parents:

c43ab090c8ddfd806239f1a22762fa741b0864e7

git-author:

Martin Lee <martinlee84@web.de>2013-07-31 16:59:25+02:00

git-committer:

Martin Lee <martinlee84@web.de>2013-08-30 13:48:23+02:00

Message:

chg: moved some code from .h to .cc
chg: absBiFactorizeMain now also returns other factors

Location:

factory

Files:

• facAbsFact.cc (modified) (4 diffs)
• facAbsFact.h (modified) (2 diffs)

factory/facAbsFact.cc

@@ -35 +35 @@
 TIMING_DEFINE_PRINT(fac_Qa_factorize)
 TIMING_DEFINE_PRINT(fac_evalpoint)
+
+CFAFList uniAbsFactorize (const CanonicalForm& F)
+{
+  CFFList rationalFactors= factorize (F);
+  CFFListIterator i= rationalFactors;
+  i++;
+  Variable alpha;
+  CFAFList result;
+  CFFList QaFactors;
+  CFFListIterator iter;
+  for (; i.hasItem(); i++)
+  {
+    if (degree (i.getItem().factor()) == 1)
+    {
+      result.append (CFAFactor (i.getItem().factor(), 1, i.getItem().exp()));
+      continue;
+    }
+    alpha= rootOf (i.getItem().factor());
+    QaFactors= factorize (i.getItem().factor(), alpha);
+    iter= QaFactors;
+    if (iter.getItem().factor().inCoeffDomain())
+      iter++;
+    for (;iter.hasItem(); iter++)
+    {
+      if (degree (iter.getItem().factor()) == 1)
+      {
+        result.append (CFAFactor (iter.getItem().factor(), getMipo (alpha),
+                                  i.getItem().exp()));
+        break;
+      }
+    }
+  }
+  result.insert (CFAFactor (rationalFactors.getFirst().factor(), 1, 1));
+  return result;
+}
+
+
+/// absolute factorization of bivariate poly over Q
+///
+/// @return absFactorize returns a list whose entries contain three entities:
+///         an absolute irreducible factor, an irreducible univariate polynomial
+///         that defines the minimal field extension over which the irreducible
+///         factor is defined and the multiplicity of the absolute irreducible
+///         factor
+CFAFList absBiFactorize (const CanonicalForm& G ///<[in] bivariate poly over Q
+                        )
+{
+  //TODO handle homogeneous input
+  ASSERT (getNumVars (G) <= 2, "expected bivariate input");
+  ASSERT (getCharacteristic() == 0, "expected poly over Q");
+
+  CFMap N;
+  CanonicalForm F= compress (G, N);
+  bool isRat= isOn (SW_RATIONAL);
+  if (isRat)
+    F *= bCommonDen (F);
+
+  Off (SW_RATIONAL);
+  F /= icontent (F);
+  if (isRat)
+    On (SW_RATIONAL);
+
+  CanonicalForm contentX= content (F, 1);
+  CanonicalForm contentY= content (F, 2);
+  F /= (contentX*contentY);
+  CFAFList contentXFactors, contentYFactors;
+  contentXFactors= uniAbsFactorize (contentX);
+  contentYFactors= uniAbsFactorize (contentY);
+
+  if (contentXFactors.getFirst().factor().inCoeffDomain())
+    contentXFactors.removeFirst();
+  if (contentYFactors.getFirst().factor().inCoeffDomain())
+    contentYFactors.removeFirst();
+  if (F.inCoeffDomain())
+  {
+    CFAFList result;
+    for (CFAFListIterator i= contentXFactors; i.hasItem(); i++)
+      result.append (CFAFactor (N (i.getItem().factor()), i.getItem().minpoly(),
+                                i.getItem().exp()));
+    for (CFAFListIterator i= contentYFactors; i.hasItem(); i++)
+      result.append (CFAFactor (N (i.getItem().factor()),i.getItem().minpoly(),
+                                i.getItem().exp()));
+    normalize (result);
+    result.insert (CFAFactor (Lc (G), 1, 1));
+    return result;
+  }
+  CFFList rationalFactors= factorize (F);
+
+  CFAFList result, resultBuf;
+
+  CFAFListIterator iter;
+  CFFListIterator i= rationalFactors;
+  i++;
+  for (; i.hasItem(); i++)
+  {
+    resultBuf= absBiFactorizeMain (i.getItem().factor());
+    for (iter= resultBuf; iter.hasItem(); iter++)
+      iter.getItem()= CFAFactor (iter.getItem().factor(),
+                                 iter.getItem().minpoly(), i.getItem().exp());
+    result= Union (result, resultBuf);
+  }
+
+  for (CFAFListIterator i= result; i.hasItem(); i++)
+    i.getItem()= CFAFactor (N (i.getItem().factor()), i.getItem().minpoly(),
+                            i.getItem().exp());
+  for (CFAFListIterator i= contentXFactors; i.hasItem(); i++)
+    result.append (CFAFactor (N(i.getItem().factor()), i.getItem().minpoly(),
+                              i.getItem().exp()));
+  for (CFAFListIterator i= contentYFactors; i.hasItem(); i++)
+    result.append (CFAFactor (N(i.getItem().factor()), i.getItem().minpoly(),
+                              i.getItem().exp()));
+  normalize (result);
+  result.insert (CFAFactor (Lc(G), 1, 1));
+
+  return result;
+}
 
 //TODO optimize choice of p -> choose p as large as possible (better than small p since factorization mod p does not require field extension, also less lifting)
@@ -104 +220 @@
 
 //G is assumed to be bivariate, irreducible over Q, primitive wrt x and y, compressed
-CFAFList absFactorizeMain (const CanonicalForm& G)
+CFAFList absBiFactorizeMain (const CanonicalForm& G, bool full)
 {
   CanonicalForm F= bCommonDen (G)*G;
@@ -519 +635 @@
               (F, earlySuccess, earlyFactors, degs, liftBound,
                uniFactors, dummy, evaluation, b, den);
+
   DEBOUTLN (cerr, "lifted factors= " << uniFactors);
 
@@ -549 +666 @@
   for (CFListIterator i= biFactors; i.hasItem(); i++)
   {
+    if (full)
+      result.append (CFAFactor (i.getItem(), getMipo (alpha), 1));
+
     if (totaldegree (i.getItem()) == minTdeg)
     {
-      result= CFAFList (CFAFactor (i.getItem(), getMipo (alpha), 1));
+      if (!full)
+        result= CFAFList (CFAFactor (i.getItem(), getMipo (alpha), 1));
       found= true;
-      break;
+
+      if (!full)
+        break;
     }
   }

factory/facAbsFact.h

@@ -29 +29 @@
 ///         factor is defined and the multiplicity of the absolute irreducible
 ///         factor
-CFAFList absFactorizeMain (const CanonicalForm& F ///<[in] s.a.
-                          );
+CFAFList absBiFactorizeMain (const CanonicalForm& F, ///<[in] s.a.
+                             bool full= false
+                            );
 #endif
 
@@ -49 +50 @@
 ///         factor is defined and the multiplicity of the absolute irreducible
 ///         factor
-static inline
 CFAFList uniAbsFactorize (const CanonicalForm& F ///<[in] univariate poly over Q
-                         )
-{
-  CFFList rationalFactors= factorize (F);
-  CFFListIterator i= rationalFactors;
-  i++;
-  Variable alpha;
-  CFAFList result;
-  CFFList QaFactors;
-  CFFListIterator iter;
-  for (; i.hasItem(); i++)
-  {
-    if (degree (i.getItem().factor()) == 1)
-    {
-      result.append (CFAFactor (i.getItem().factor(), 1, i.getItem().exp()));
-      continue;
-    }
-    alpha= rootOf (i.getItem().factor());
-    QaFactors= factorize (i.getItem().factor(), alpha);
-    iter= QaFactors;
-    if (iter.getItem().factor().inCoeffDomain())
-      iter++;
-    for (;iter.hasItem(); iter++)
-    {
-      if (degree (iter.getItem().factor()) == 1)
-      {
-        result.append (CFAFactor (iter.getItem().factor(), getMipo (alpha),
-                                  i.getItem().exp()));
-        break;
-      }
-    }
-  }
-  result.insert (CFAFactor (rationalFactors.getFirst().factor(), 1, 1));
-  return result;
-}
+                         );
 
 /*BEGINPUBLIC*/
 
 #ifdef HAVE_NTL
-CFAFList absFactorize (const CanonicalForm& G);
+CFAFList absBiFactorize (const CanonicalForm& G);
 #endif