facFactorize.h File Reference

multivariate factorization over Q(a) More...

#include "timing.h"
#include "facBivar.h"
#include "facFqBivarUtil.h"

Go to the source code of this file.

Functions
	TIMING_DEFINE_PRINT (fac_squarefree) TIMING_DEFINE_PRINT(fac_factor_squarefree) void factorizationWRTDifferentSecondVars(const CanonicalForm &A
	Factorization of A wrt. to different second vars. More...
CFList	multiFactorize (const CanonicalForm &F, const Variable &v)
	Factorization over Q (a) More...
CFList	ratSqrfFactorize (const CanonicalForm &G, const Variable &v=Variable(1))
	factorize a squarefree multivariate polynomial over More...
CFFList	ratFactorize (const CanonicalForm &G, const Variable &v=Variable(1), bool substCheck=true)
	factorize a multivariate polynomial over More...

Variables
CFList *&	Aeval
	<[in] poly More...
CFList int &	minFactorsLength
	[in,out] minimal length of bivariate factors More...
CFList int bool &	irred
	[in,out] Is A irreducible? More...
CFList int bool const Variable &	w
	<[in] alg. variable More...

Detailed Description

multivariate factorization over Q(a)

Author

Martin Lee

Definition in file facFactorize.h.

Function Documentation

multiFactorize()

CFList multiFactorize	(	const CanonicalForm &	F,
		const Variable &	v
	)

Factorization over Q (a)

Returns

multiFactorize returns a factorization of F

Parameters

[in]	F	sqrfree poly
[in]	v	some algebraic variable

Definition at line 198 of file facFactorize.cc.

{
  if (F.inCoeffDomain())
    return CFList (F);
 
  TIMING_START (fac_preprocess_and_content);
  // compress and find main Variable
  CFMap N;
  TIMING_START (fac_compress)
  CanonicalForm A= myCompress (F, N);
  TIMING_END_AND_PRINT (fac_compress, "time to compress poly over Q: ")
 
  //univariate case
  if (F.isUnivariate())
  {
    CFList result;
    if (v.level() != 1)
      result= conv (factorize (F, v));
    else
      result= conv (factorize (F,true));
    if (result.getFirst().inCoeffDomain())
      result.removeFirst();
    return result;
  }
 
  //bivariate case
  if (A.level() == 2)
  {
    CFList buf= ratBiSqrfFactorize (F, v);
    if (buf.getFirst().inCoeffDomain())
      buf.removeFirst();
    return buf;
  }
 
  Variable x= Variable (1);
  Variable y= Variable (2);
 
  // remove content
  TIMING_START (fac_content);
  CFList contentAi;
  CanonicalForm lcmCont= lcmContent (A, contentAi);
  A /= lcmCont;
  TIMING_END_AND_PRINT (fac_content, "time to extract content over Q: ");
 
  // trivial after content removal
  CFList contentAFactors;
  if (A.inCoeffDomain())
  {
    for (CFListIterator i= contentAi; i.hasItem(); i++)
    {
      if (i.getItem().inCoeffDomain())
        continue;
      else
      {
        lcmCont /= i.getItem();
        contentAFactors=
        Union (multiFactorize (lcmCont, v),
               multiFactorize (i.getItem(), v));
        break;
      }
    }
    decompress (contentAFactors, N);
    if (isOn (SW_RATIONAL))
      normalize (contentAFactors);
    return contentAFactors;
  }
 
  // factorize content
  TIMING_START (fac_content);
  contentAFactors= multiFactorize (lcmCont, v);
  TIMING_END_AND_PRINT (fac_content, "time to factor content over Q: ");
 
  // univariate after content removal
  CFList factors;
  if (A.isUnivariate ())
  {
    if (v.level() != 1)
      factors= conv (factorize (A, v));
    else
      factors= conv (factorize (A,true));
    append (factors, contentAFactors);
    decompress (factors, N);
    return factors;
  }
 
  A *= bCommonDen (A);
  CFList Aeval, list, evaluation, bufEvaluation, bufAeval;
  int factorNums= 2;
  //p is irreducible. But factorize does not recognizes this. However, if you
  //change factorNums to 2 at line 281 in facFactorize.cc it will. That change
  //might impair performance in some cases since you do twice as many
  //bivariate factorizations as before. Otherwise you need to change
  //precomputeLeadingCoeff to detect these cases and trigger more bivariate
  // factorizations.
  // (http://www.singular.uni-kl.de:8002/trac/ticket/666)
  CFList biFactors, bufBiFactors;
  CanonicalForm evalPoly;
  int lift, bufLift, lengthAeval2= A.level()-2;
  CFList* bufAeval2= new CFList [lengthAeval2];
  CFList* Aeval2= new CFList [lengthAeval2];
  int counter;
  int differentSecondVar= 0;
  CanonicalForm bufA;
  TIMING_END_AND_PRINT (fac_preprocess_and_content,
                       "time to preprocess poly and extract content over Q: ");
 
  // several bivariate factorizations
  TIMING_START (fac_bifactor_total);
  REvaluation E (2, A.level(), IntRandom (25));
  for (int i= 0; i < factorNums; i++)
  {
    counter= 0;
    bufA= A;
    bufAeval= CFList();
    TIMING_START (fac_evaluation);
    bufEvaluation= evalPoints (bufA, bufAeval, E);
    TIMING_END_AND_PRINT (fac_evaluation,
                          "time to find evaluation point over Q: ");
    E.nextpoint();
    evalPoly= 0;
 
    TIMING_START (fac_evaluation);
    evaluationWRTDifferentSecondVars (bufAeval2, bufEvaluation, A);
    TIMING_END_AND_PRINT (fac_evaluation,
                          "time to eval wrt diff second vars over Q: ");
 
    for (int j= 0; j < lengthAeval2; j++)
    {
      if (!bufAeval2[j].isEmpty())
        counter++;
    }
 
    bufLift= degree (A, y) + 1 + degree (LC(A, x), y);
 
    TIMING_START (fac_bi_factorizer);
    bufBiFactors= ratBiSqrfFactorize (bufAeval.getFirst(), v);
    TIMING_END_AND_PRINT (fac_bi_factorizer,
                          "time for bivariate factorization: ");
    bufBiFactors.removeFirst();
 
    if (bufBiFactors.length() == 1)
    {
      factors.append (A);
      appendSwapDecompress (factors, contentAFactors, N, 0, 0, x);
      if (isOn (SW_RATIONAL))
        normalize (factors);
      delete [] bufAeval2;
      delete [] Aeval2;
      return factors;
    }
 
    if (i == 0)
    {
      Aeval= bufAeval;
      evaluation= bufEvaluation;
      biFactors= bufBiFactors;
      lift= bufLift;
      for (int j= 0; j < lengthAeval2; j++)
        Aeval2 [j]= bufAeval2 [j];
      differentSecondVar= counter;
    }
    else
    {
      if (bufBiFactors.length() < biFactors.length() ||
          ((bufLift < lift) && (bufBiFactors.length() == biFactors.length())) ||
          counter > differentSecondVar)
      {
        Aeval= bufAeval;
        evaluation= bufEvaluation;
        biFactors= bufBiFactors;
        lift= bufLift;
        for (int j= 0; j < lengthAeval2; j++)
          Aeval2 [j]= bufAeval2 [j];
        differentSecondVar= counter;
      }
    }
    int k= 0;
    for (CFListIterator j= bufEvaluation; j.hasItem(); j++, k++)
      evalPoly += j.getItem()*power (x, k);
    list.append (evalPoly);
  }
 
  delete [] bufAeval2;
 
  sortList (biFactors, x);
 
  int minFactorsLength;
  bool irred= false;
  TIMING_START (fac_bi_factorizer);
  factorizationWRTDifferentSecondVars (A, Aeval2, minFactorsLength, irred, v);
  TIMING_END_AND_PRINT (fac_bi_factorizer,
             "time for bivariate factorization wrt diff second vars over Q: ");
 
  TIMING_END_AND_PRINT (fac_bifactor_total,
                        "total time for eval and bivar factors over Q: ");
  if (irred)
  {
    factors.append (A);
    appendSwapDecompress (factors, contentAFactors, N, 0, 0, x);
    if (isOn (SW_RATIONAL))
      normalize (factors);
    delete [] Aeval2;
    return factors;
  }
 
  if (minFactorsLength == 0)
    minFactorsLength= biFactors.length();
  else if (biFactors.length() > minFactorsLength)
    refineBiFactors (A, biFactors, Aeval2, evaluation, minFactorsLength);
  minFactorsLength= tmin (minFactorsLength, biFactors.length());
 
  CFList uniFactors= buildUniFactors (biFactors, evaluation.getLast(), y);
 
  sortByUniFactors (Aeval2, lengthAeval2, uniFactors, biFactors, evaluation);
 
  minFactorsLength= tmin (minFactorsLength, biFactors.length());
 
  if (minFactorsLength == 1)
  {
    factors.append (A);
    appendSwapDecompress (factors, contentAFactors, N, 0, 0, x);
    if (isOn (SW_RATIONAL))
      normalize (factors);
    delete [] Aeval2;
    return factors;
  }
 
  if (differentSecondVar == lengthAeval2)
  {
    bool zeroOccured= false;
    for (CFListIterator iter= evaluation; iter.hasItem(); iter++)
    {
      if (iter.getItem().isZero())
      {
        zeroOccured= true;
        break;
      }
    }
    if (!zeroOccured)
    {
      factors= sparseHeuristic (A, biFactors, Aeval2, evaluation,
                                minFactorsLength);
      if (factors.length() == biFactors.length())
      {
        appendSwapDecompress (factors, contentAFactors, N, 0, 0, x);
        normalize (factors);
        delete [] Aeval2;
        return factors;
      }
      else
        factors= CFList();
      //TODO case where factors.length() > 0
    }
  }
 
  CFList * oldAeval= new CFList [lengthAeval2];
  for (int i= 0; i < lengthAeval2; i++)
    oldAeval[i]= Aeval2[i];
 
  getLeadingCoeffs (A, Aeval2);
 
  CFList biFactorsLCs;
  for (CFListIterator i= biFactors; i.hasItem(); i++)
    biFactorsLCs.append (LC (i.getItem(), 1));
 
  Variable w;
  TIMING_START (fac_precompute_leadcoeff);
  CFList leadingCoeffs= precomputeLeadingCoeff (LC (A, 1), biFactorsLCs, x,
                                          evaluation, Aeval2, lengthAeval2, w);
 
  if (w.level() != 1)
    changeSecondVariable (A, biFactors, evaluation, oldAeval, lengthAeval2,
                          uniFactors, w);
 
  CanonicalForm oldA= A;
  CFList oldBiFactors= biFactors;
 
  CanonicalForm LCmultiplier= leadingCoeffs.getFirst();
  bool LCmultiplierIsConst= LCmultiplier.inCoeffDomain();
  leadingCoeffs.removeFirst();
 
  if (!LCmultiplierIsConst)
    distributeLCmultiplier (A, leadingCoeffs, biFactors, evaluation, LCmultiplier);
 
  //prepare leading coefficients
  CFList* leadingCoeffs2= new CFList [lengthAeval2];
  prepareLeadingCoeffs (leadingCoeffs2, A, Aeval, A.level(), leadingCoeffs,
                        biFactors, evaluation);
 
  CFListIterator iter;
  CFList bufLeadingCoeffs2= leadingCoeffs2[lengthAeval2-1];
  bufBiFactors= biFactors;
  bufA= A;
  CanonicalForm testVars, bufLCmultiplier= LCmultiplier;
  if (!LCmultiplierIsConst)
  {
    testVars= Variable (2);
    for (int i= 0; i < lengthAeval2; i++)
    {
      if (!oldAeval[i].isEmpty())
        testVars *= oldAeval[i].getFirst().mvar();
    }
  }
  TIMING_END_AND_PRINT(fac_precompute_leadcoeff,
                       "time to precompute LC over Q: ");
 
  TIMING_START (fac_luckswang);
  CFList bufFactors= CFList();
  bool LCheuristic= false;
  if (LucksWangSparseHeuristic (A, biFactors, 2, leadingCoeffs2[lengthAeval2-1],
                                factors))
  {
    int check= biFactors.length();
    int * index= new int [factors.length()];
    CFList oldFactors= factors;
    factors= recoverFactors (A, factors, index);
 
    if (check == factors.length())
    {
      if (w.level() != 1)
      {
        for (iter= factors; iter.hasItem(); iter++)
          iter.getItem()= swapvar (iter.getItem(), w, y);
      }
 
      appendSwapDecompress (factors, contentAFactors, N, 0, 0, x);
      normalize (factors);
      delete [] index;
      delete [] Aeval2;
      TIMING_END_AND_PRINT (fac_luckswang,
                            "time for successful LucksWang over Q: ");
      return factors;
    }
    else if (factors.length() > 0)
    {
      int oneCount= 0;
      CFList l;
      for (int i= 0; i < check; i++)
      {
        if (index[i] == 1)
        {
          iter=biFactors;
          for (int j=1; j <= i-oneCount; j++)
            iter++;
          iter.remove (1);
          for (int j= 0; j < lengthAeval2; j++)
          {
            l= leadingCoeffs2[j];
            iter= l;
            for (int k=1; k <= i-oneCount; k++)
              iter++;
            iter.remove (1);
            leadingCoeffs2[j]=l;
          }
          oneCount++;
        }
      }
      bufFactors= factors;
      factors= CFList();
    }
    else if (!LCmultiplierIsConst && factors.length() == 0)
    {
      LCheuristic= true;
      factors= oldFactors;
      CFList contents, LCs;
      bool foundTrueMultiplier= false;
      LCHeuristic2 (LCmultiplier, factors, leadingCoeffs2[lengthAeval2-1],
                    contents, LCs, foundTrueMultiplier);
      if (foundTrueMultiplier)
      {
          A= oldA;
          leadingCoeffs= leadingCoeffs2[lengthAeval2-1];
          for (int i= lengthAeval2-1; i > -1; i--)
            leadingCoeffs2[i]= CFList();
          prepareLeadingCoeffs (leadingCoeffs2, A, Aeval, A.level(),
                                leadingCoeffs, biFactors, evaluation);
      }
      else
      {
        bool foundMultiplier= false;
        LCHeuristic3 (LCmultiplier, factors, oldBiFactors, contents, oldAeval,
                      A, leadingCoeffs2, lengthAeval2, foundMultiplier);
        // coming from above: divide out more LCmultiplier if possible
        if (foundMultiplier)
        {
          foundMultiplier= false;
          LCHeuristic4 (oldBiFactors, oldAeval, contents, factors, testVars,
                        lengthAeval2, leadingCoeffs2, A, LCmultiplier,
                        foundMultiplier);
        }
        else
        {
          LCHeuristicCheck (LCs, contents, A, oldA,
                            leadingCoeffs2[lengthAeval2-1], foundMultiplier);
          if (!foundMultiplier && fdivides (getVars (LCmultiplier), testVars))
          {
            LCHeuristic (A, LCmultiplier, biFactors, leadingCoeffs2, oldAeval,
                         lengthAeval2, evaluation, oldBiFactors);
          }
        }
 
        // patch everything together again
        leadingCoeffs= leadingCoeffs2[lengthAeval2-1];
        for (int i= lengthAeval2-1; i > -1; i--)
          leadingCoeffs2[i]= CFList();
        prepareLeadingCoeffs (leadingCoeffs2, A, Aeval, A.level(),leadingCoeffs,
                              biFactors, evaluation);
      }
      factors= CFList();
      if (!fdivides (LC (oldA,1),prod (leadingCoeffs2[lengthAeval2-1])))
      {
        LCheuristic= false;
        A= bufA;
        biFactors= bufBiFactors;
        leadingCoeffs2[lengthAeval2-1]= bufLeadingCoeffs2;
        LCmultiplier= bufLCmultiplier;
      }
    }
    else
      factors= CFList();
    delete [] index;
  }
  TIMING_END_AND_PRINT (fac_luckswang, "time for LucksWang over Q: ");
 
  TIMING_START (fac_lcheuristic);
  if (!LCheuristic && !LCmultiplierIsConst && bufFactors.isEmpty()
      && fdivides (getVars (LCmultiplier), testVars))
  {
    LCheuristic= true;
    LCHeuristic (A, LCmultiplier, biFactors, leadingCoeffs2, oldAeval,
                 lengthAeval2, evaluation, oldBiFactors);
 
    leadingCoeffs= leadingCoeffs2[lengthAeval2-1];
    for (int i= lengthAeval2-1; i > -1; i--)
      leadingCoeffs2[i]= CFList();
    prepareLeadingCoeffs (leadingCoeffs2, A, Aeval, A.level(),leadingCoeffs,
                          biFactors, evaluation);
 
    if (!fdivides (LC (oldA,1),prod (leadingCoeffs2[lengthAeval2-1])))
    {
      LCheuristic= false;
      A= bufA;
      biFactors= bufBiFactors;
      leadingCoeffs2[lengthAeval2-1]= bufLeadingCoeffs2;
      LCmultiplier= bufLCmultiplier;
    }
  }
  TIMING_END_AND_PRINT (fac_lcheuristic, "time for Lc heuristic over Q: ");
 
tryAgainWithoutHeu:
  //shifting to zero
  TIMING_START (fac_shift_to_zero);
  CanonicalForm denA= bCommonDen (A);
  A *= denA;
  A= shift2Zero (A, Aeval, evaluation);
  A /= denA;
 
  for (iter= biFactors; iter.hasItem(); iter++)
    iter.getItem()= iter.getItem () (y + evaluation.getLast(), y);
 
  for (int i= 0; i < lengthAeval2-1; i++)
    leadingCoeffs2[i]= CFList();
  for (iter= leadingCoeffs2[lengthAeval2-1]; iter.hasItem(); iter++)
  {
    iter.getItem()= shift2Zero (iter.getItem(), list, evaluation);
    for (int i= A.level() - 4; i > -1; i--)
    {
      if (i + 1 == lengthAeval2-1)
        leadingCoeffs2[i].append (iter.getItem() (0, i + 4));
      else
        leadingCoeffs2[i].append (leadingCoeffs2[i+1].getLast() (0, i + 4));
    }
  }
  TIMING_END_AND_PRINT (fac_shift_to_zero,
                        "time to shift evaluation point to zero: ");
 
  CFArray Pi;
  CFList diophant;
  int* liftBounds= new int [A.level() - 1];
  int liftBoundsLength= A.level() - 1;
  for (int i= 0; i < liftBoundsLength; i++)
    liftBounds [i]= degree (A, i + 2) + 1;
 
  Aeval.removeFirst();
  bool noOneToOne= false;
 
  TIMING_START (fac_cleardenom);
  CFList commonDenominators;
  for (iter=biFactors; iter.hasItem(); iter++)
    commonDenominators.append (bCommonDen (iter.getItem()));
  CanonicalForm tmp1, tmp2, tmp3=1;
  CFListIterator iter2;
  for (int i= 0; i < lengthAeval2; i++)
  {
    iter2= commonDenominators;
    for (iter= leadingCoeffs2[i]; iter.hasItem(); iter++, iter2++)
    {
      tmp1= bCommonDen (iter.getItem());
      Off (SW_RATIONAL);
      iter2.getItem()= lcm (iter2.getItem(), tmp1);
      On (SW_RATIONAL);
    }
  }
  tmp1= prod (commonDenominators);
  for (iter= Aeval; iter.hasItem(); iter++)
  {
    tmp2= bCommonDen (iter.getItem()/denA);
    Off (SW_RATIONAL);
    tmp3= lcm (tmp2,tmp3);
    On (SW_RATIONAL);
  }
  CanonicalForm multiplier;
  multiplier= tmp3/tmp1;
  iter2= commonDenominators;
  for (iter=biFactors; iter.hasItem(); iter++, iter2++)
    iter.getItem() *= iter2.getItem()*multiplier;
 
  for (iter= Aeval; iter.hasItem(); iter++)
    iter.getItem() *= tmp3*power (multiplier, biFactors.length() - 1)/denA;
 
  for (int i= 0; i < lengthAeval2; i++)
  {
    iter2= commonDenominators;
    for (iter= leadingCoeffs2[i]; iter.hasItem(); iter++, iter2++)
      iter.getItem() *= iter2.getItem()*multiplier;
  }
  TIMING_END_AND_PRINT (fac_cleardenom, "time to clear denominators: ");
 
  TIMING_START (fac_hensel_lift);
  factors= nonMonicHenselLift (Aeval, biFactors, leadingCoeffs2, diophant,
                               Pi, liftBounds, liftBoundsLength, noOneToOne);
  TIMING_END_AND_PRINT (fac_hensel_lift,
                        "time for non monic hensel lifting over Q: ");
 
  if (!noOneToOne)
  {
    int check= factors.length();
    A= oldA;
    TIMING_START (fac_recover_factors);
    factors= recoverFactors (A, factors, evaluation);
    TIMING_END_AND_PRINT (fac_recover_factors,
                          "time to recover factors over Q: ");
    if (check != factors.length())
      noOneToOne= true;
    else
      factors= Union (factors, bufFactors);
  }
  if (noOneToOne)
  {
    if (!LCmultiplierIsConst && LCheuristic)
    {
      A= bufA;
      biFactors= bufBiFactors;
      leadingCoeffs2[lengthAeval2-1]= bufLeadingCoeffs2;
      delete [] liftBounds;
      LCheuristic= false;
      goto tryAgainWithoutHeu;
      //something probably went wrong in the heuristic
    }
 
    A= shift2Zero (oldA, Aeval, evaluation);
    biFactors= oldBiFactors;
    for (iter= biFactors; iter.hasItem(); iter++)
      iter.getItem()= iter.getItem () (y + evaluation.getLast(), y);
    CanonicalForm LCA= LC (Aeval.getFirst(), 1);
    CanonicalForm yToLift= power (y, lift);
    CFListIterator i= biFactors;
    lift= degree (i.getItem(), 2) + degree (LC (i.getItem(), 1)) + 1;
    i++;
 
    for (; i.hasItem(); i++)
      lift= tmax (lift, degree (i.getItem(), 2)+degree (LC (i.getItem(), 1))+1);
 
    lift= tmax (degree (Aeval.getFirst() , 2) + 1, lift);
 
    i= biFactors;
    yToLift= power (y, lift);
    CanonicalForm dummy;
    for (; i.hasItem(); i++)
    {
      LCA= LC (i.getItem(), 1);
      extgcd (LCA, yToLift, LCA, dummy);
      i.getItem()= mod (i.getItem()*LCA, yToLift);
    }
 
    liftBoundsLength= F.level() - 1;
    liftBounds= liftingBounds (A, lift);
 
    CFList MOD;
    bool earlySuccess;
    CFList earlyFactors;
    ExtensionInfo info= ExtensionInfo (false);
    CFList liftedFactors;
    TIMING_START (fac_hensel_lift);
    liftedFactors= henselLiftAndEarly
                   (A, MOD, liftBounds, earlySuccess, earlyFactors,
                    Aeval, biFactors, evaluation, info);
    TIMING_END_AND_PRINT (fac_hensel_lift, "time for hensel lifting: ");
 
    TIMING_START (fac_factor_recombination);
    factors= factorRecombination (A, liftedFactors, MOD);
    TIMING_END_AND_PRINT (fac_factor_recombination,
                          "time for factor recombination: ");
 
    if (earlySuccess)
      factors= Union (factors, earlyFactors);
 
    for (CFListIterator i= factors; i.hasItem(); i++)
    {
      int kk= Aeval.getLast().level();
      for (CFListIterator j= evaluation; j.hasItem(); j++, kk--)
      {
        if (i.getItem().level() < kk)
          continue;
       i.getItem()= i.getItem() (Variable (kk) - j.getItem(), kk);
      }
    }
  }
 
  if (w.level() != 1)
  {
    for (CFListIterator iter= factors; iter.hasItem(); iter++)
      iter.getItem()= swapvar (iter.getItem(), w, y);
  }
 
  append (factors, contentAFactors);
  decompress (factors, N);
  if (isOn (SW_RATIONAL))
    normalize (factors);
 
  delete [] leadingCoeffs2;
  delete [] oldAeval;
  delete [] Aeval2;
  delete[] liftBounds;
 
  return factors;
}

ratFactorize()

CFFList ratFactorize ( const CanonicalForm &  G, const Variable &  v = Variable (1), bool  substCheck = true  )

inline

factorize a multivariate polynomial over

Returns

ratFactorize returns a list of monic factors with multiplicity, the first element is the leading coefficient.

Parameters

[in]	G	a multivariate poly
[in]	v	algebraic variable
[in]	substCheck	enables substitute check

Definition at line 79 of file facFactorize.h.

{
  if (getNumVars (G) == 2)
  {
    CFFList result= ratBiFactorize (G,v);
    return result;
  }
  CanonicalForm F= G;
 
  if (substCheck)
  {
    bool foundOne= false;
    int * substDegree= new int [F.level()];
    for (int i= 1; i <= F.level(); i++)
    {
      if (degree (F, i) > 0)
      {
        substDegree[i-1]= substituteCheck (F, Variable (i));
        if (substDegree [i-1] > 1)
        {
          foundOne= true;
          subst (F, F, substDegree[i-1], Variable (i));
        }
      }
      else
        substDegree[i-1]= -1;
    }
    if (foundOne)
    {
      CFFList result= ratFactorize (F, v, false);
      CFFList newResult, tmp;
      CanonicalForm tmp2;
      newResult.insert (result.getFirst());
      result.removeFirst();
      for (CFFListIterator i= result; i.hasItem(); i++)
      {
        tmp2= i.getItem().factor();
        for (int j= 1; j <= G.level(); j++)
        {
          if (substDegree[j-1] > 1)
            tmp2= reverseSubst (tmp2, substDegree[j-1], Variable (j));
        }
        tmp= ratFactorize (tmp2, v, false);
        tmp.removeFirst();
        for (CFFListIterator j= tmp; j.hasItem(); j++)
          newResult.append (CFFactor (j.getItem().factor(),
                                      j.getItem().exp()*i.getItem().exp()));
      }
      delete [] substDegree;
      return newResult;
    }
    delete [] substDegree;
  }
 
  CanonicalForm LcF= Lc (F);
  if (isOn (SW_RATIONAL))
    F *= bCommonDen (F);
 
  CFFList result;
  TIMING_START (fac_squarefree);
  CFFList sqrfFactors= sqrFree (F);
  TIMING_END_AND_PRINT (fac_squarefree,
                        "time for squarefree factorization over Q: ");
 
  CFList tmp;
  for (CFFListIterator i= sqrfFactors; i.hasItem(); i++)
  {
    TIMING_START (fac_factor_squarefree);
    tmp= ratSqrfFactorize (i.getItem().factor(), v);
    TIMING_END_AND_PRINT (fac_factor_squarefree,
                          "time to factorize sqrfree factor over Q: ");
    for (CFListIterator j= tmp; j.hasItem(); j++)
    {
      if (j.getItem().inCoeffDomain()) continue;
      result.append (CFFactor (j.getItem(), i.getItem().exp()));
    }
  }
  if (isOn (SW_RATIONAL))
  {
    normalize (result);
    if (v.level() == 1)
    {
      for (CFFListIterator i= result; i.hasItem(); i++)
      {
        LcF /= power (bCommonDen (i.getItem().factor()), i.getItem().exp());
        i.getItem()= CFFactor (i.getItem().factor()*
                     bCommonDen(i.getItem().factor()), i.getItem().exp());
      }
    }
    result.insert (CFFactor (LcF, 1));
  }
  return result;
}

ratSqrfFactorize()

CFList ratSqrfFactorize ( const CanonicalForm &  G, const Variable &  v = Variable (1)  )

inline

factorize a squarefree multivariate polynomial over

Returns

ratSqrfFactorize returns a list of monic factors, the first element is the leading coefficient.

Parameters

[in]	G	a multivariate poly
[in]	v	algebraic variable

Definition at line 53 of file facFactorize.h.

{
  if (getNumVars (G) == 2)
    return ratBiSqrfFactorize (G, v);
  CanonicalForm F= G;
  if (isOn (SW_RATIONAL))
    F *= bCommonDen (F);
  CFList result= multiFactorize (F, v);
  if (isOn (SW_RATIONAL))
  {
    normalize (result);
    result.insert (Lc(F));
  }
  return result;
}

TIMING_DEFINE_PRINT()

TIMING_DEFINE_PRINT

(

fac_squarefree

)

const &

Factorization of A wrt. to different second vars.

Variable Documentation

Aeval

CFList*& Aeval

<[in] poly

[in,out] A evaluated wrt. different second vars returns bivariate factors

Definition at line 29 of file facFactorize.h.

irred

CFList int bool& irred

[in,out] Is A irreducible?

Definition at line 34 of file facFactorize.h.

minFactorsLength

CFList int& minFactorsLength

[in,out] minimal length of bivariate factors

Definition at line 32 of file facFactorize.h.

w

CFList int bool const Variable& w

<[in] alg. variable

Definition at line 35 of file facFactorize.h.