facAbsFact.h File Reference

absolute multivariate factorization over Q More...

#include "facAbsBiFact.h"

Go to the source code of this file.

Functions
CFAFList	absFactorizeMain (const CanonicalForm &F)
	main absolute factorization routine, expects poly which is irreducible over Q More...
CFAFList FACTORY_PUBLIC	absFactorize (const CanonicalForm &G)
	absolute factorization of a multivariate poly over Q More...

Detailed Description

absolute multivariate factorization over Q

Author

Martin Lee

Definition in file facAbsFact.h.

Function Documentation

absFactorize()

CFAFList FACTORY_PUBLIC absFactorize

(

const CanonicalForm &

G

)

absolute factorization of a multivariate poly over Q

Returns

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 (note: in case the factor is already defined over Q[t]/(t), 1 is returned), and the multiplicity of the absolute irreducible factor

Parameters

[in]

G

poly over Q

Definition at line 262 of file facAbsFact.cc.

{
  //TODO handle homogeneous input, is already done in LIB interface but still...
  ASSERT (getCharacteristic() == 0, "expected poly over Q");
 
  CanonicalForm F= G;
 
  CanonicalForm LcF= Lc (F);
  bool isRat= isOn (SW_RATIONAL);
  if (isRat)
    F *= bCommonDen (F);
 
  Off (SW_RATIONAL);
  F /= icontent (F);
  if (isRat)
    On (SW_RATIONAL);
 
  CFFList rationalFactors= factorize (F);
 
  CFAFList result, resultBuf;
 
  CFAFListIterator iter;
  CFFListIterator i= rationalFactors;
  i++;
  for (; i.hasItem(); i++)
  {
    resultBuf= absFactorizeMain (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);
  }
 
  if (isRat)
    normalize (result);
  result.insert (CFAFactor (LcF, 1, 1));
 
  return result;
}

absFactorizeMain()

CFAFList absFactorizeMain

(

const CanonicalForm &

F

)

main absolute factorization routine, expects poly which is irreducible over Q

Returns

absFactorizeMain 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 (note: in case the factor is already defined over Q[t]/(t), 1 is returned as defining poly), and the multiplicity of the absolute irreducible factor

Parameters

[in]

F

irred poly over Q

Definition at line 303 of file facAbsFact.cc.

{
  CanonicalForm F= bCommonDen (G)*G;
 
  Off (SW_RATIONAL);
  F /= icontent (F);
  On (SW_RATIONAL);
 
  if (F.inCoeffDomain())
    return CFAFList (CFAFactor (F, 1, 1));
 
  // compress and find main Variable
  CFMap N;
  TIMING_START (abs_fac_compress)
  CanonicalForm A= myCompress (F, N);
  TIMING_END_AND_PRINT (abs_fac_compress,
                        "time to compress poly in abs fact: ")
 
  //univariate case
  if (F.isUnivariate())
  {
    CFAFList result;
    result= uniAbsFactorize (F);
    if (result.getFirst().factor().inCoeffDomain())
      result.removeFirst();
    return result;
  }
 
  //bivariate case
  if (A.level() == 2)
  {
    CFAFList result= absBiFactorizeMain (A);
    decompress (result, N);
    return result; //needs compressed input
  }
 
  Variable x= Variable (1);
  Variable y= Variable (2);
 
  CFAFList factors;
  A *= bCommonDen (A);
  CFList Aeval, list, evaluation, bufEvaluation, bufAeval;
  int factorNums= 1;
  CFAFList absBiFactors, absBufBiFactors;
  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;
 
  // several bivariate factorizations
  TIMING_START (abs_fac_bifactor_total);
  int absValue= 2;
  REvaluation E (2, A.level(), IntRandom (absValue));
  for (int i= 0; i < factorNums; i++)
  {
    counter= 0;
    bufA= A;
    bufAeval= CFList();
    TIMING_START (abs_fac_evaluation);
    bufEvaluation= evalPoints4AbsFact (bufA, bufAeval, E, absValue);
    TIMING_END_AND_PRINT (abs_fac_evaluation,
                          "time to find evaluation point in abs fact: ");
    E.nextpoint();
    evalPoly= 0;
 
    TIMING_START (abs_fac_evaluation);
    evaluationWRTDifferentSecondVars (bufAeval2, bufEvaluation, A);
    TIMING_END_AND_PRINT (abs_fac_evaluation,
                          "time to eval wrt diff second vars in abs fact: ");
 
    for (int j= 0; j < lengthAeval2; j++)
    {
      if (!bufAeval2[j].isEmpty())
        counter++;
    }
 
    bufLift= degree (A, y) + 1 + degree (LC(A, x), y);
 
    TIMING_START (abs_fac_bi_factorizer);
    absBufBiFactors= absBiFactorizeMain (bufAeval.getFirst(), true);
    TIMING_END_AND_PRINT (abs_fac_bi_factorizer,
                          "time for bivariate factorization in abs fact: ");
 
    if (absBufBiFactors.length() == 1)
    {
      factors.append (CFAFactor (A, 1, 1));
      decompress (factors, N);
      if (isOn (SW_RATIONAL))
        normalize (factors);
      delete [] bufAeval2;
      delete [] Aeval2;
      return factors;
    }
 
    if (i == 0)
    {
      Aeval= bufAeval;
      evaluation= bufEvaluation;
      absBiFactors= absBufBiFactors;
      lift= bufLift;
      for (int j= 0; j < lengthAeval2; j++)
        Aeval2 [j]= bufAeval2 [j];
      differentSecondVar= counter;
    }
    else
    {
      if (absBufBiFactors.length() < absBiFactors.length() ||
          ((bufLift < lift) &&
          (absBufBiFactors.length() == absBiFactors.length())) ||
          counter > differentSecondVar)
      {
        Aeval= bufAeval;
        evaluation= bufEvaluation;
        absBiFactors= absBufBiFactors;
        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;
 
  CFList rationalFactors;
  Variable v= mvar (absBiFactors.getFirst().minpoly());
 
  CFList biFactors;
  for (CFAFListIterator iter= absBiFactors; iter.hasItem(); iter++)
    biFactors.append (iter.getItem().factor());
 
  sortList (biFactors, x);
 
  int minFactorsLength;
  bool irred= false;
 
  TIMING_START (abs_fac_bi_factorizer);
  factorizationWRTDifferentSecondVars (A, Aeval2, minFactorsLength, irred, v);
  TIMING_END_AND_PRINT (abs_fac_bi_factorizer,
         "time for bivariate factorization wrt diff second vars in abs fact: ");
 
  TIMING_END_AND_PRINT (abs_fac_bifactor_total,
                        "total time for eval and bivar factors in abs fact: ");
  if (irred)
  {
    factors.append (CFAFactor (A, 1, 1));
    decompress (factors, N);
    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 (CFAFactor (A, 1, 1));
    decompress (factors, N);
    if (isOn (SW_RATIONAL))
      normalize (factors);
    delete [] Aeval2;
    return factors;
  }
 
  bool found= false;
  if (differentSecondVar == lengthAeval2)
  {
    bool zeroOccured= false;
    for (CFListIterator iter= evaluation; iter.hasItem(); iter++)
    {
      if (iter.getItem().isZero())
      {
        zeroOccured= true;
        break;
      }
    }
    if (!zeroOccured)
    {
      rationalFactors= sparseHeuristic (A, biFactors, Aeval2, evaluation,
                                       minFactorsLength);
      if (rationalFactors.length() == biFactors.length())
      {
        for (CFListIterator iter= rationalFactors; iter.hasItem(); iter++)
        {
          if (totaldegree(iter.getItem())*degree(getMipo(v)) == totaldegree (G))
          {
            factors= CFAFList (CFAFactor (iter.getItem(), getMipo (v), 1));
            found= true;
            break;
          }
        }
        // necessary since extension may be too large
        if (!found)
          factors= RothsteinTrager (A, rationalFactors, v, evaluation);
 
        decompress (factors, N);
        normalize (factors);
        delete [] Aeval2;
        return factors;
      }
      else
        rationalFactors= 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 (abs_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];
  CFList 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(abs_fac_precompute_leadcoeff,
                       "time to precompute LC in abs fact: ");
 
  TIMING_START (abs_fac_luckswang);
  CFList bufFactors= CFList();
  bool LCheuristic= false;
  if (LucksWangSparseHeuristic (A, biFactors, 2, leadingCoeffs2[lengthAeval2-1],
                                rationalFactors))
  {
    int check= biFactors.length();
    int * index= new int [factors.length()];
    CFList oldFactors= rationalFactors;
    rationalFactors= recoverFactors (A, rationalFactors, index);
 
    if (check == rationalFactors.length())
    {
      if (w.level() != 1)
      {
        for (iter= rationalFactors; iter.hasItem(); iter++)
          iter.getItem()= swapvar (iter.getItem(), w, y);
      }
 
      for (CFListIterator iter= rationalFactors; iter.hasItem(); iter++)
      {
        if (totaldegree(iter.getItem())*degree (getMipo (v)) == totaldegree (G))
        {
          factors= CFAFList (CFAFactor (iter.getItem(), getMipo (v), 1));
          found=true;
          break;
        }
      }
      // necessary since extension may be too large
      if (!found)
        factors= RothsteinTrager (A, rationalFactors, v, evaluation);
 
      decompress (factors, N);
      normalize (factors);
      delete [] index;
      delete [] Aeval2;
      TIMING_END_AND_PRINT (abs_fac_luckswang,
                            "time for successful LucksWang in abs fact: ");
      return factors;
    }
    else if (rationalFactors.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= rationalFactors;
      rationalFactors= CFList();
    }
    else if (!LCmultiplierIsConst && rationalFactors.length() == 0)
    {
      LCheuristic= true;
      rationalFactors= oldFactors;
      CFList contents, LCs;
      bool foundTrueMultiplier= false;
      LCHeuristic2 (LCmultiplier,rationalFactors,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, rationalFactors, oldBiFactors, contents,
                      oldAeval,A,leadingCoeffs2, lengthAeval2, foundMultiplier);
        // coming from above: divide out more LCmultiplier if possible
        if (foundMultiplier)
        {
          foundMultiplier= false;
          LCHeuristic4 (oldBiFactors, oldAeval, contents, rationalFactors,
                        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);
      }
      rationalFactors= CFList();
      if (!fdivides (LC (oldA,1),prod (leadingCoeffs2[lengthAeval2-1])))
      {
        LCheuristic= false;
        A= bufA;
        biFactors= bufBiFactors;
        leadingCoeffs2[lengthAeval2-1]= bufLeadingCoeffs2;
        LCmultiplier= bufLCmultiplier;
      }
    }
    else
      rationalFactors= CFList();
    delete [] index;
  }
  TIMING_END_AND_PRINT (abs_fac_luckswang, "time for LucksWang in abs fact: ");
 
  TIMING_START (abs_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 (abs_fac_lcheuristic,
                        "time for Lc heuristic in abs fact: ");
 
tryAgainWithoutHeu:
  //shifting to zero
  TIMING_START (abs_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 (abs_fac_shift_to_zero,
                        "time to shift evaluation point to zero in abs fact: ");
 
  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 (abs_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 (abs_fac_cleardenom,
                        "time to clear denominators in abs fact: ");
 
  TIMING_START (abs_fac_hensel_lift);
  rationalFactors= nonMonicHenselLift (Aeval, biFactors,leadingCoeffs2,diophant,
                               Pi, liftBounds, liftBoundsLength, noOneToOne);
  TIMING_END_AND_PRINT (abs_fac_hensel_lift,
                        "time for non monic hensel lifting in abs fact: ");
 
  if (!noOneToOne)
  {
    int check= rationalFactors.length();
    A= oldA;
    TIMING_START (abs_fac_recover_factors);
    rationalFactors= recoverFactors (A, rationalFactors, evaluation);
    TIMING_END_AND_PRINT (abs_fac_recover_factors,
                          "time to recover factors in abs fact: ");
    if (check != rationalFactors.length())
      noOneToOne= true;
    else
      rationalFactors= Union (rationalFactors, 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 (abs_fac_hensel_lift);
    liftedFactors= henselLiftAndEarly
                   (A, MOD, liftBounds, earlySuccess, earlyFactors,
                    Aeval, biFactors, evaluation, info);
    TIMING_END_AND_PRINT (abs_fac_hensel_lift,
                          "time for hensel lifting in abs fact: ");
 
    TIMING_START (abs_fac_factor_recombination);
    rationalFactors= factorRecombination (A, liftedFactors, MOD);
    TIMING_END_AND_PRINT (abs_fac_factor_recombination,
                          "time for factor recombination in abs fact: ");
 
    if (earlySuccess)
      rationalFactors= Union (rationalFactors, earlyFactors);
 
    for (CFListIterator i= rationalFactors; 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= rationalFactors; iter.hasItem(); iter++)
      iter.getItem()= swapvar (iter.getItem(), w, y);
  }
 
  for (CFListIterator iter= rationalFactors; iter.hasItem(); iter++)
  {
    if (totaldegree (iter.getItem())*degree (getMipo (v)) == totaldegree (G))
    {
      factors= CFAFList (CFAFactor (iter.getItem(), getMipo (v), 1));
      found= true;
      break;
    }
  }
 
  // necessary since extension may be too large
  if (!found)
    factors= RothsteinTrager (A, rationalFactors, v, evaluation);
 
  decompress (factors, N);
  if (isOn (SW_RATIONAL))
    normalize (factors);
 
  delete [] leadingCoeffs2;
  delete [] oldAeval;
  delete [] Aeval2;
  delete[] liftBounds;
 
  return factors;
}