Changeset ec16f0 in git


Ignore:
Timestamp:
Dec 5, 2011, 3:43:07 PM (12 years ago)
Author:
Martin Lee <martinlee84@…>
Branches:
(u'spielwiese', '5b153614cbc72bfa198d75b1e9e33dab2645d9fe')
Children:
ce21bd8d333faf7c8f2fcdbd11fa57c0b6ec7776
Parents:
4fe8a30d668fa6f87de68f0c0207d54767119a52
git-author:
Martin Lee <martinlee84@web.de>2011-12-05 15:43:07+01:00
git-committer:
Oleksandr Motsak <motsak@mathematik.uni-kl.de>2011-12-12 18:00:42+01:00
Message:
chg: use sparse heuristic in precomputation of leading coefficients
Location:
factory
Files:
2 edited

Legend:

Unmodified
Added
Removed
  • factory/facFactorize.cc

    r4fe8a3 rec16f0  
    431431  }
    432432
     433  CFList interMedResult;
     434  CanonicalForm oldSqrfPartF= sqrfPartF;
    433435  sqrfPartF= shift2Zero (sqrfPartF, evalSqrfPartF, evaluation2, 1);
    434436  if (factors.length() > 1)
    435437  {
    436     CanonicalForm LC1= LC (evalSqrfPartF.getFirst(), 1);
    437 
    438     CFArray leadingCoeffs= CFArray (factors.length());
     438    CanonicalForm LC1= LC (oldSqrfPartF, 1);
     439    CFList leadingCoeffs;
    439440    for (int i= 0; i < factors.length(); i++)
    440       leadingCoeffs[i]= LC1;
    441     for (CFListIterator i= factors; i.hasItem(); i++)
    442     {
    443       i.getItem()= i.getItem() (x + evaluation2.getLast(), x);
    444       i.getItem() *= LC1 (0,2)/Lc (i.getItem());
    445     }
    446     factors.insert (1);
    447 
    448     CanonicalForm
    449     newSqrfPartF= evalSqrfPartF.getFirst()*power (LC1, factors.length() - 2);
    450 
    451     int liftBound= degree (newSqrfPartF,2) + 1;
    452 
    453     CFMatrix M= CFMatrix (liftBound, factors.length() - 1);
    454     CFArray Pi;
    455     CFList diophant;
    456     henselLift122 (newSqrfPartF, factors, liftBound, Pi, diophant, M,
    457                    leadingCoeffs, false);
    458 
    459     if (sqrfPartF.level() > 2)
    460     {
    461       int* liftBounds= new int [sqrfPartF.level() - 1];
    462       liftBounds [0]= liftBound;
    463       bool noOneToOne= false;
    464       CFList *leadingCoeffs2= new CFList [sqrfPartF.level()-2];
    465       LC1= LC (evalSqrfPartF.getLast(), 1);
    466       CFList LCs;
     441      leadingCoeffs.append (LC1);
     442
     443    CFList LC1eval= evaluateAtEval (LC1, evaluation2, 1);
     444    CFList oldFactors= factors;
     445    for (CFListIterator i= oldFactors; i.hasItem(); i++)
     446      i.getItem() *= LC1eval.getFirst()/Lc (i.getItem());
     447
     448    bool success= false;
     449    if (LucksWangSparseHeuristic (oldSqrfPartF*power (LC1, factors.length()-1),
     450                                  oldFactors, 1, leadingCoeffs, factors))
     451    {
     452      interMedResult= recoverFactors (oldSqrfPartF, factors);
     453      if (oldFactors.length() == interMedResult.length())
     454        success= true;
     455    }
     456    if (!success)
     457    {
     458      LC1= LC (evalSqrfPartF.getFirst(), 1);
     459
     460      CFArray leadingCoeffs= CFArray (factors.length());
    467461      for (int i= 0; i < factors.length(); i++)
    468         LCs.append (LC1);
    469       leadingCoeffs2 [sqrfPartF.level() - 3]= LCs;
    470       for (int i= sqrfPartF.level() - 1; i > 2; i--)
    471       {
    472         for (CFListIterator j= LCs; j.hasItem(); j++)
    473           j.getItem()= j.getItem() (0, i + 1);
    474         leadingCoeffs2 [i - 3]= LCs;
    475       }
    476       sqrfPartF= sqrfPartF*power (LC1, factors.length()-1);
    477 
    478       int liftBoundsLength= sqrfPartF.level() - 1;
    479       for (int i= 1; i < liftBoundsLength; i++)
    480         liftBounds [i]= degree (sqrfPartF, i + 2) + 1;
    481       evalSqrfPartF= evaluateAtZero (sqrfPartF);
    482       evalSqrfPartF.removeFirst();
    483       factors= nonMonicHenselLift (evalSqrfPartF, factors, leadingCoeffs2,
    484                diophant, Pi, liftBounds, sqrfPartF.level() - 1, noOneToOne);
    485       delete [] leadingCoeffs2;
    486       delete [] liftBounds;
     462        leadingCoeffs[i]= LC1;
     463
     464      for (CFListIterator i= factors; i.hasItem(); i++)
     465      {
     466        i.getItem()= i.getItem() (x + evaluation2.getLast(), x);
     467        i.getItem() *= LC1 (0,2)/Lc (i.getItem());
     468      }
     469      factors.insert (1);
     470
     471      CanonicalForm
     472      newSqrfPartF= evalSqrfPartF.getFirst()*power (LC1, factors.length() - 2);
     473
     474      int liftBound= degree (newSqrfPartF,2) + 1;
     475
     476      CFMatrix M= CFMatrix (liftBound, factors.length() - 1);
     477      CFArray Pi;
     478      CFList diophant;
     479      henselLift122 (newSqrfPartF, factors, liftBound, Pi, diophant, M,
     480                     leadingCoeffs, false);
     481
     482      if (sqrfPartF.level() > 2)
     483      {
     484        int* liftBounds= new int [sqrfPartF.level() - 1];
     485        liftBounds [0]= liftBound;
     486        bool noOneToOne= false;
     487        CFList *leadingCoeffs2= new CFList [sqrfPartF.level()-2];
     488        LC1= LC (evalSqrfPartF.getLast(), 1);
     489        CFList LCs;
     490        for (int i= 0; i < factors.length(); i++)
     491          LCs.append (LC1);
     492        leadingCoeffs2 [sqrfPartF.level() - 3]= LCs;
     493        for (int i= sqrfPartF.level() - 1; i > 2; i--)
     494        {
     495          for (CFListIterator j= LCs; j.hasItem(); j++)
     496            j.getItem()= j.getItem() (0, i + 1);
     497          leadingCoeffs2 [i - 3]= LCs;
     498        }
     499        sqrfPartF *= power (LC1, factors.length()-1);
     500
     501        int liftBoundsLength= sqrfPartF.level() - 1;
     502        for (int i= 1; i < liftBoundsLength; i++)
     503          liftBounds [i]= degree (sqrfPartF, i + 2) + 1;
     504        evalSqrfPartF= evaluateAtZero (sqrfPartF);
     505        evalSqrfPartF.removeFirst();
     506        factors= nonMonicHenselLift (evalSqrfPartF, factors, leadingCoeffs2,
     507                 diophant, Pi, liftBounds, sqrfPartF.level() - 1, noOneToOne);
     508        delete [] leadingCoeffs2;
     509        delete [] liftBounds;
     510      }
     511      for (CFListIterator iter= factors; iter.hasItem(); iter++)
     512        iter.getItem()= reverseShift (iter.getItem(), evaluation2, 1);
     513
     514      interMedResult=
     515      recoverFactors (reverseShift(evalSqrfPartF.getLast(),evaluation2,1),
     516                      factors);
    487517    }
    488518  }
    489519  else
    490     factors= evalSqrfPartF.getLast();
    491 
    492   for (CFListIterator iter= factors; iter.hasItem(); iter++)
    493     iter.getItem()= reverseShift (iter.getItem(), evaluation2, 1);
    494 
    495   CFList interMedResult=
    496   recoverFactors (reverseShift(evalSqrfPartF.getLast(),evaluation2,1), factors);
     520  {
     521    factors= CFList (oldSqrfPartF);
     522    interMedResult= recoverFactors (oldSqrfPartF, factors);
     523  }
    497524
    498525  CFList result;
  • factory/facFqFactorize.cc

    r4fe8a3 rec16f0  
    16051605  }
    16061606
     1607  CFList interMedResult;
     1608  CanonicalForm oldSqrfPartF= sqrfPartF;
    16071609  sqrfPartF= shift2Zero (sqrfPartF, evalSqrfPartF, evaluation2, 1);
    16081610  if (factors.length() > 1)
    16091611  {
    1610     CanonicalForm LC1= LC (evalSqrfPartF.getFirst(), 1);
    1611 
    1612     CFArray leadingCoeffs= CFArray (factors.length());
     1612    CanonicalForm LC1= LC (oldSqrfPartF, 1);
     1613    CFList leadingCoeffs;
    16131614    for (int i= 0; i < factors.length(); i++)
    1614       leadingCoeffs[i]= LC1;
    1615 
    1616     for (CFListIterator i= factors; i.hasItem(); i++)
    1617     {
    1618       i.getItem()= i.getItem() (x + evaluation2.getLast(), x);
    1619       i.getItem() *= LC1 (0,2)/Lc (i.getItem());
    1620     }
    1621     factors.insert (1);
    1622 
    1623     CanonicalForm
    1624     newSqrfPartF= evalSqrfPartF.getFirst()*power (LC1, factors.length() - 2);
    1625 
    1626     int liftBound= degree (newSqrfPartF,2) + 1;
    1627 
    1628     CFMatrix M= CFMatrix (liftBound, factors.length() - 1);
    1629     CFArray Pi;
    1630     CFList diophant;
    1631     henselLift122 (newSqrfPartF, factors, liftBound, Pi, diophant, M,
    1632                    leadingCoeffs, false);
    1633 
    1634     if (sqrfPartF.level() > 2)
    1635     {
    1636       int* liftBounds= new int [sqrfPartF.level() - 1];
    1637       liftBounds [0]= liftBound;
    1638       bool noOneToOne= false;
    1639       CFList *leadingCoeffs2= new CFList [sqrfPartF.level()-2];
    1640       LC1= LC (evalSqrfPartF.getLast(), 1);
    1641       CFList LCs;
     1615      leadingCoeffs.append (LC1);
     1616
     1617    CFList LC1eval= evaluateAtEval (LC1, evaluation2, 1);
     1618    CFList oldFactors= factors;
     1619    for (CFListIterator i= oldFactors; i.hasItem(); i++)
     1620      i.getItem() *= LC1eval.getFirst()/Lc (i.getItem());
     1621
     1622    bool success= false;
     1623    if (LucksWangSparseHeuristic (oldSqrfPartF*power (LC1, factors.length()-1),
     1624                                  oldFactors, 1, leadingCoeffs, factors))
     1625    {
     1626      interMedResult= recoverFactors (oldSqrfPartF, factors);
     1627      if (oldFactors.length() == interMedResult.length())
     1628        success= true;
     1629    }
     1630    if (!success)
     1631    {
     1632      LC1= LC (evalSqrfPartF.getFirst(), 1);
     1633
     1634      CFArray leadingCoeffs= CFArray (factors.length());
    16421635      for (int i= 0; i < factors.length(); i++)
    1643         LCs.append (LC1);
    1644       leadingCoeffs2 [sqrfPartF.level() - 3]= LCs;
    1645       for (int i= sqrfPartF.level() - 1; i > 2; i--)
    1646       {
    1647         for (CFListIterator j= LCs; j.hasItem(); j++)
    1648           j.getItem()= j.getItem() (0, i + 1);
    1649         leadingCoeffs2 [i - 3]= LCs;
    1650       }
    1651       sqrfPartF= sqrfPartF*power (LC1, factors.length()-1);
    1652 
    1653       int liftBoundsLength= sqrfPartF.level() - 1;
    1654       for (int i= 1; i < liftBoundsLength; i++)
    1655         liftBounds [i]= degree (sqrfPartF, i + 2) + 1;
    1656       evalSqrfPartF= evaluateAtZero (sqrfPartF);
    1657       evalSqrfPartF.removeFirst();
    1658       factors= nonMonicHenselLift (evalSqrfPartF, factors, leadingCoeffs2,
    1659                diophant, Pi, liftBounds, sqrfPartF.level() - 1, noOneToOne);
    1660       delete [] leadingCoeffs2;
    1661       delete [] liftBounds;
     1636        leadingCoeffs[i]= LC1;
     1637
     1638      for (CFListIterator i= factors; i.hasItem(); i++)
     1639      {
     1640        i.getItem()= i.getItem() (x + evaluation2.getLast(), x);
     1641        i.getItem() *= LC1 (0,2)/Lc (i.getItem());
     1642      }
     1643      factors.insert (1);
     1644
     1645      CanonicalForm
     1646      newSqrfPartF= evalSqrfPartF.getFirst()*power (LC1, factors.length() - 2);
     1647
     1648      int liftBound= degree (newSqrfPartF,2) + 1;
     1649
     1650      CFMatrix M= CFMatrix (liftBound, factors.length() - 1);
     1651      CFArray Pi;
     1652      CFList diophant;
     1653      henselLift122 (newSqrfPartF, factors, liftBound, Pi, diophant, M,
     1654                     leadingCoeffs, false);
     1655
     1656      if (sqrfPartF.level() > 2)
     1657      {
     1658        int* liftBounds= new int [sqrfPartF.level() - 1];
     1659        liftBounds [0]= liftBound;
     1660        bool noOneToOne= false;
     1661        CFList *leadingCoeffs2= new CFList [sqrfPartF.level()-2];
     1662        LC1= LC (evalSqrfPartF.getLast(), 1);
     1663        CFList LCs;
     1664        for (int i= 0; i < factors.length(); i++)
     1665          LCs.append (LC1);
     1666        leadingCoeffs2 [sqrfPartF.level() - 3]= LCs;
     1667        for (int i= sqrfPartF.level() - 1; i > 2; i--)
     1668        {
     1669          for (CFListIterator j= LCs; j.hasItem(); j++)
     1670            j.getItem()= j.getItem() (0, i + 1);
     1671          leadingCoeffs2 [i - 3]= LCs;
     1672        }
     1673        sqrfPartF *= power (LC1, factors.length()-1);
     1674
     1675        int liftBoundsLength= sqrfPartF.level() - 1;
     1676        for (int i= 1; i < liftBoundsLength; i++)
     1677          liftBounds [i]= degree (sqrfPartF, i + 2) + 1;
     1678        evalSqrfPartF= evaluateAtZero (sqrfPartF);
     1679        evalSqrfPartF.removeFirst();
     1680        factors= nonMonicHenselLift (evalSqrfPartF, factors, leadingCoeffs2,
     1681                 diophant, Pi, liftBounds, sqrfPartF.level() - 1, noOneToOne);
     1682        delete [] leadingCoeffs2;
     1683        delete [] liftBounds;
     1684      }
     1685      for (CFListIterator iter= factors; iter.hasItem(); iter++)
     1686        iter.getItem()= reverseShift (iter.getItem(), evaluation2, 1);
     1687
     1688      interMedResult=
     1689      recoverFactors (reverseShift(evalSqrfPartF.getLast(),evaluation2,1),
     1690                      factors);
    16621691    }
    16631692  }
    16641693  else
    1665     factors= evalSqrfPartF.getLast();
    1666 
    1667   for (CFListIterator iter= factors; iter.hasItem(); iter++)
    1668     iter.getItem()= reverseShift (iter.getItem(), evaluation2, 1);
    1669 
    1670   CFList interMedResult=
    1671   recoverFactors (reverseShift(evalSqrfPartF.getLast(),evaluation2,1), factors);
     1694  {
     1695    factors= CFList (oldSqrfPartF);
     1696    interMedResult= recoverFactors (oldSqrfPartF, factors);
     1697  }
    16721698
    16731699  CFList result;
Note: See TracChangeset for help on using the changeset viewer.