Changeset 73c222 in git


Ignore:
Timestamp:
Jul 31, 2013, 4:59:25 PM (11 years ago)
Author:
Martin Lee <martinlee84@…>
Branches:
(u'fieker-DuVal', '117eb8c30fc9e991c4decca4832b1d19036c4c65')(u'spielwiese', '4188d308699580d975efd0f6cca8dcb41c396f70')
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:
2 edited

Legend:

Unmodified
Added
Removed
  • factory/facAbsFact.cc

    rc43ab0 r73c222  
    3535TIMING_DEFINE_PRINT(fac_Qa_factorize)
    3636TIMING_DEFINE_PRINT(fac_evalpoint)
     37
     38CFAFList uniAbsFactorize (const CanonicalForm& F)
     39{
     40  CFFList rationalFactors= factorize (F);
     41  CFFListIterator i= rationalFactors;
     42  i++;
     43  Variable alpha;
     44  CFAFList result;
     45  CFFList QaFactors;
     46  CFFListIterator iter;
     47  for (; i.hasItem(); i++)
     48  {
     49    if (degree (i.getItem().factor()) == 1)
     50    {
     51      result.append (CFAFactor (i.getItem().factor(), 1, i.getItem().exp()));
     52      continue;
     53    }
     54    alpha= rootOf (i.getItem().factor());
     55    QaFactors= factorize (i.getItem().factor(), alpha);
     56    iter= QaFactors;
     57    if (iter.getItem().factor().inCoeffDomain())
     58      iter++;
     59    for (;iter.hasItem(); iter++)
     60    {
     61      if (degree (iter.getItem().factor()) == 1)
     62      {
     63        result.append (CFAFactor (iter.getItem().factor(), getMipo (alpha),
     64                                  i.getItem().exp()));
     65        break;
     66      }
     67    }
     68  }
     69  result.insert (CFAFactor (rationalFactors.getFirst().factor(), 1, 1));
     70  return result;
     71}
     72
     73
     74/// absolute factorization of bivariate poly over Q
     75///
     76/// @return absFactorize returns a list whose entries contain three entities:
     77///         an absolute irreducible factor, an irreducible univariate polynomial
     78///         that defines the minimal field extension over which the irreducible
     79///         factor is defined and the multiplicity of the absolute irreducible
     80///         factor
     81CFAFList absBiFactorize (const CanonicalForm& G ///<[in] bivariate poly over Q
     82                        )
     83{
     84  //TODO handle homogeneous input
     85  ASSERT (getNumVars (G) <= 2, "expected bivariate input");
     86  ASSERT (getCharacteristic() == 0, "expected poly over Q");
     87
     88  CFMap N;
     89  CanonicalForm F= compress (G, N);
     90  bool isRat= isOn (SW_RATIONAL);
     91  if (isRat)
     92    F *= bCommonDen (F);
     93
     94  Off (SW_RATIONAL);
     95  F /= icontent (F);
     96  if (isRat)
     97    On (SW_RATIONAL);
     98
     99  CanonicalForm contentX= content (F, 1);
     100  CanonicalForm contentY= content (F, 2);
     101  F /= (contentX*contentY);
     102  CFAFList contentXFactors, contentYFactors;
     103  contentXFactors= uniAbsFactorize (contentX);
     104  contentYFactors= uniAbsFactorize (contentY);
     105
     106  if (contentXFactors.getFirst().factor().inCoeffDomain())
     107    contentXFactors.removeFirst();
     108  if (contentYFactors.getFirst().factor().inCoeffDomain())
     109    contentYFactors.removeFirst();
     110  if (F.inCoeffDomain())
     111  {
     112    CFAFList result;
     113    for (CFAFListIterator i= contentXFactors; i.hasItem(); i++)
     114      result.append (CFAFactor (N (i.getItem().factor()), i.getItem().minpoly(),
     115                                i.getItem().exp()));
     116    for (CFAFListIterator i= contentYFactors; i.hasItem(); i++)
     117      result.append (CFAFactor (N (i.getItem().factor()),i.getItem().minpoly(),
     118                                i.getItem().exp()));
     119    normalize (result);
     120    result.insert (CFAFactor (Lc (G), 1, 1));
     121    return result;
     122  }
     123  CFFList rationalFactors= factorize (F);
     124
     125  CFAFList result, resultBuf;
     126
     127  CFAFListIterator iter;
     128  CFFListIterator i= rationalFactors;
     129  i++;
     130  for (; i.hasItem(); i++)
     131  {
     132    resultBuf= absBiFactorizeMain (i.getItem().factor());
     133    for (iter= resultBuf; iter.hasItem(); iter++)
     134      iter.getItem()= CFAFactor (iter.getItem().factor(),
     135                                 iter.getItem().minpoly(), i.getItem().exp());
     136    result= Union (result, resultBuf);
     137  }
     138
     139  for (CFAFListIterator i= result; i.hasItem(); i++)
     140    i.getItem()= CFAFactor (N (i.getItem().factor()), i.getItem().minpoly(),
     141                            i.getItem().exp());
     142  for (CFAFListIterator i= contentXFactors; i.hasItem(); i++)
     143    result.append (CFAFactor (N(i.getItem().factor()), i.getItem().minpoly(),
     144                              i.getItem().exp()));
     145  for (CFAFListIterator i= contentYFactors; i.hasItem(); i++)
     146    result.append (CFAFactor (N(i.getItem().factor()), i.getItem().minpoly(),
     147                              i.getItem().exp()));
     148  normalize (result);
     149  result.insert (CFAFactor (Lc(G), 1, 1));
     150
     151  return result;
     152}
    37153
    38154//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)
     
    104220
    105221//G is assumed to be bivariate, irreducible over Q, primitive wrt x and y, compressed
    106 CFAFList absFactorizeMain (const CanonicalForm& G)
     222CFAFList absBiFactorizeMain (const CanonicalForm& G, bool full)
    107223{
    108224  CanonicalForm F= bCommonDen (G)*G;
     
    519635              (F, earlySuccess, earlyFactors, degs, liftBound,
    520636               uniFactors, dummy, evaluation, b, den);
     637
    521638  DEBOUTLN (cerr, "lifted factors= " << uniFactors);
    522639
     
    549666  for (CFListIterator i= biFactors; i.hasItem(); i++)
    550667  {
     668    if (full)
     669      result.append (CFAFactor (i.getItem(), getMipo (alpha), 1));
     670
    551671    if (totaldegree (i.getItem()) == minTdeg)
    552672    {
    553       result= CFAFList (CFAFactor (i.getItem(), getMipo (alpha), 1));
     673      if (!full)
     674        result= CFAFList (CFAFactor (i.getItem(), getMipo (alpha), 1));
    554675      found= true;
    555       break;
     676
     677      if (!full)
     678        break;
    556679    }
    557680  }
  • factory/facAbsFact.h

    rc43ab0 r73c222  
    2929///         factor is defined and the multiplicity of the absolute irreducible
    3030///         factor
    31 CFAFList absFactorizeMain (const CanonicalForm& F ///<[in] s.a.
    32                           );
     31CFAFList absBiFactorizeMain (const CanonicalForm& F, ///<[in] s.a.
     32                             bool full= false
     33                            );
    3334#endif
    3435
     
    4950///         factor is defined and the multiplicity of the absolute irreducible
    5051///         factor
    51 static inline
    5252CFAFList uniAbsFactorize (const CanonicalForm& F ///<[in] univariate poly over Q
    53                          )
    54 {
    55   CFFList rationalFactors= factorize (F);
    56   CFFListIterator i= rationalFactors;
    57   i++;
    58   Variable alpha;
    59   CFAFList result;
    60   CFFList QaFactors;
    61   CFFListIterator iter;
    62   for (; i.hasItem(); i++)
    63   {
    64     if (degree (i.getItem().factor()) == 1)
    65     {
    66       result.append (CFAFactor (i.getItem().factor(), 1, i.getItem().exp()));
    67       continue;
    68     }
    69     alpha= rootOf (i.getItem().factor());
    70     QaFactors= factorize (i.getItem().factor(), alpha);
    71     iter= QaFactors;
    72     if (iter.getItem().factor().inCoeffDomain())
    73       iter++;
    74     for (;iter.hasItem(); iter++)
    75     {
    76       if (degree (iter.getItem().factor()) == 1)
    77       {
    78         result.append (CFAFactor (iter.getItem().factor(), getMipo (alpha),
    79                                   i.getItem().exp()));
    80         break;
    81       }
    82     }
    83   }
    84   result.insert (CFAFactor (rationalFactors.getFirst().factor(), 1, 1));
    85   return result;
    86 }
     53                         );
    8754
    8855/*BEGINPUBLIC*/
    8956
    9057#ifdef HAVE_NTL
    91 CFAFList absFactorize (const CanonicalForm& G);
     58CFAFList absBiFactorize (const CanonicalForm& G);
    9259#endif
    9360
Note: See TracChangeset for help on using the changeset viewer.