Changeset 327efa2 in git


Ignore:
Timestamp:
Sep 14, 2011, 2:38:38 PM (12 years ago)
Author:
Martin Lee <martinlee84@…>
Branches:
(u'jengelh-datetime', 'ceac47cbc86fe4a15902392bdbb9bd2ae0ea02c6')(u'spielwiese', '0604212ebb110535022efecad887940825b97c3f')
Children:
09723d9937585aae280f53597c2c61b2b3e6304a
Parents:
725e6002e0b07ad1474e14f72296c0c85a47ae4d
Message:
different lifting  in precomputeLeadingCoeff
extend henselLift122 to lift more than two factors


git-svn-id: file:///usr/local/Singular/svn/trunk@14382 2c84dea3-7e68-4137-9b89-c4e89433aadc
Location:
factory
Files:
3 edited

Legend:

Unmodified
Added
Removed

  • factory/facFactorize.cc

    r725e600 r327efa2  
    202202      for (iter= bufSqrfFactors [i]; iter.hasItem(); iter++)
    203203      {
     204        if (iter.getItem().factor().inCoeffDomain())
     205          continue;
    204206        iter.getItem()= CFFactor (iter.getItem().factor()/
    205207                                  Lc (iter.getItem().factor()),
    … …  
    212214      for (iter= bufSqrfFactors [i]; iter.hasItem(); iter++)
    213215      {
     216        if (iter.getItem().factor().inCoeffDomain())
     217          continue;
    214218        iter.getItem()= CFFactor (iter.getItem().factor()/
    215219                               Lc (iter.getItem().factor()),
    … …  
    388392    factors= bufFactors;
    389393
    390   int liftBound= degree (sqrfPartF,2) + degree (LC (sqrfPartF, 1), 2) + 1;
    391 
    392   int* liftBounds= liftingBounds (sqrfPartF, liftBound);
    393394
    394395  bufFactors= factors;
    395   factors.insert (LC (evalSqrfPartF.getFirst(), 1));
    396   CFMatrix M= CFMatrix (liftBound, factors.length() - 1);
    397   CFArray Pi;
    398   CFList diophant;
    399   henselLift12 (evalSqrfPartF.getFirst(), factors, liftBound, Pi, diophant, M,
    400                 false);
    401 
    402   if (sqrfPartF.level() > 2)
    403     factors= henselLift (evalSqrfPartF, factors, liftBounds,
    404                          sqrfPartF.level() - 1, false);
    405 
    406   CFList MOD;
    407   for (int i= 0; i < sqrfPartF.level() - 1; i++)
    408     MOD.append (power (Variable (i + 2), liftBounds [i]));
    409 
    410   CFList interMedResult= leadingCoeffReconstruction (evalSqrfPartF.getLast(),
    411                                                      factors, MOD);
     396
     397  if (factors.length() > 1)
     398  {
     399    CanonicalForm LC1= LC (evalSqrfPartF.getFirst(), 1);
     400
     401    CFArray leadingCoeffs= CFArray (factors.length());
     402    for (int i= 0; i < factors.length(); i++)
     403      leadingCoeffs[i]= LC1;
     404    for (CFListIterator i= factors; i.hasItem(); i++)
     405      i.getItem() *= LC1 (0,2)/Lc (i.getItem());
     406    factors.insert (1);
     407
     408    CanonicalForm
     409    newSqrfPartF= evalSqrfPartF.getFirst()*power (LC1, factors.length() - 2);
     410
     411    int liftBound= degree (newSqrfPartF,2) + 1;
     412
     413    CFMatrix M= CFMatrix (liftBound, factors.length() - 1);
     414    CFArray Pi;
     415    CFList diophant;
     416    henselLift122 (newSqrfPartF, factors, liftBound, Pi, diophant, M,
     417                   leadingCoeffs, false);
     418
     419    if (sqrfPartF.level() > 2)
     420    {
     421      int* liftBounds= new int [sqrfPartF.level() - 1];
     422      liftBounds [0]= liftBound;
     423      bool noOneToOne= false;
     424      CFList *leadingCoeffs2= new CFList [sqrfPartF.level()-2];
     425      LC1= LC (evalSqrfPartF.getLast(), 1);
     426      CFList LCs;
     427      for (int i= 0; i < factors.length(); i++)
     428        LCs.append (LC1);
     429      leadingCoeffs2 [sqrfPartF.level() - 3]= LCs;
     430      for (int i= sqrfPartF.level() - 1; i > 2; i--)
     431      {
     432        for (CFListIterator j= LCs; j.hasItem(); j++)
     433          j.getItem()= j.getItem() (0, i + 1);
     434        leadingCoeffs2 [i - 3]= LCs;
     435      }
     436      sqrfPartF= sqrfPartF*power (LC1, factors.length()-1);
     437
     438      int liftBoundsLength= sqrfPartF.level() - 1;
     439      for (int i= 1; i < liftBoundsLength; i++)
     440        liftBounds [i]= degree (sqrfPartF, i + 2) + 1;
     441      evalSqrfPartF= evaluateAtZero (sqrfPartF);
     442      evalSqrfPartF.removeFirst();
     443      factors= nonMonicHenselLift (evalSqrfPartF, factors, leadingCoeffs2,
     444               diophant, Pi, liftBounds, sqrfPartF.level() - 1, noOneToOne);
     445      delete [] leadingCoeffs2;
     446      delete [] liftBounds;
     447    }
     448  }
     449  else
     450    factors= evalSqrfPartF.getLast();
     451
     452  CFList interMedResult= recoverFactors (evalSqrfPartF.getLast(), factors);
    412453
    413454  CFList result;

  • factory/facFqFactorize.cc

    r725e600 r327efa2  
    13751375      for (iter= bufSqrfFactors [i]; iter.hasItem(); iter++)
    13761376      {
     1377        if (iter.getItem().factor().inCoeffDomain())
     1378          continue;
    13771379        iter.getItem()= CFFactor (iter.getItem().factor()/
    13781380                                  Lc (iter.getItem().factor()),
    … …  
    13851387      for (iter= bufSqrfFactors [i]; iter.hasItem(); iter++)
    13861388      {
     1389        if (iter.getItem().factor().inCoeffDomain())
     1390          continue;
    13871391        iter.getItem()= CFFactor (iter.getItem().factor()/
    13881392                                  Lc (iter.getItem().factor()),
    … …  
    15621566    factors= bufFactors;
    15631567
    1564   int liftBound= degree (sqrfPartF,2) + degree (LC (sqrfPartF, 1), 2) + 1;
    1565 
    1566   int* liftBounds= liftingBounds (sqrfPartF, liftBound);
    1567 
    15681568  bufFactors= factors;
    1569   factors.insert (LC (evalSqrfPartF.getFirst(), 1));
    1570   CFMatrix M= CFMatrix (liftBound, factors.length() - 1);
    1571   CFArray Pi;
    1572   CFList diophant;
    1573   henselLift12 (evalSqrfPartF.getFirst(), factors, liftBound, Pi, diophant, M, false);
    1574 
    1575   if (sqrfPartF.level() > 2)
    1576     factors= henselLift (evalSqrfPartF, factors, liftBounds,
    1577                          sqrfPartF.level() - 1, false);
    1578 
    1579   CFList MOD;
    1580   for (int i= 0; i < sqrfPartF.level() - 1; i++)
    1581     MOD.append (power (Variable (i + 2), liftBounds [i]));
    1582 
    1583   CFList interMedResult= leadingCoeffReconstruction (evalSqrfPartF.getLast(),
    1584                                                      factors, MOD);
     1569
     1570  if (factors.length() > 1)
     1571  {
     1572    CanonicalForm LC1= LC (evalSqrfPartF.getFirst(), 1);
     1573
     1574    CFArray leadingCoeffs= CFArray (factors.length());
     1575    for (int i= 0; i < factors.length(); i++)
     1576      leadingCoeffs[i]= LC1;
     1577    for (CFListIterator i= factors; i.hasItem(); i++)
     1578      i.getItem() *= LC1 (0,2)/Lc (i.getItem());
     1579    factors.insert (1);
     1580
     1581    CanonicalForm
     1582    newSqrfPartF= evalSqrfPartF.getFirst()*power (LC1, factors.length() - 2);
     1583
     1584    int liftBound= degree (newSqrfPartF,2) + 1;
     1585
     1586    CFMatrix M= CFMatrix (liftBound, factors.length() - 1);
     1587    CFArray Pi;
     1588    CFList diophant;
     1589    henselLift122 (newSqrfPartF, factors, liftBound, Pi, diophant, M,
     1590                   leadingCoeffs, false);
     1591
     1592    if (sqrfPartF.level() > 2)
     1593    {
     1594      int* liftBounds= new int [sqrfPartF.level() - 1];
     1595      liftBounds [0]= liftBound;
     1596      bool noOneToOne= false;
     1597      CFList *leadingCoeffs2= new CFList [sqrfPartF.level()-2];
     1598      LC1= LC (evalSqrfPartF.getLast(), 1);
     1599      CFList LCs;
     1600      for (int i= 0; i < factors.length(); i++)
     1601        LCs.append (LC1);
     1602      leadingCoeffs2 [sqrfPartF.level() - 3]= LCs;
     1603      for (int i= sqrfPartF.level() - 1; i > 2; i--)
     1604      {
     1605        for (CFListIterator j= LCs; j.hasItem(); j++)
     1606          j.getItem()= j.getItem() (0, i + 1);
     1607        leadingCoeffs2 [i - 3]= LCs;
     1608      }
     1609      sqrfPartF= sqrfPartF*power (LC1, factors.length()-1);
     1610
     1611      int liftBoundsLength= sqrfPartF.level() - 1;
     1612      for (int i= 1; i < liftBoundsLength; i++)
     1613        liftBounds [i]= degree (sqrfPartF, i + 2) + 1;
     1614      evalSqrfPartF= evaluateAtZero (sqrfPartF);
     1615      evalSqrfPartF.removeFirst();
     1616      factors= nonMonicHenselLift (evalSqrfPartF, factors, leadingCoeffs2,
     1617               diophant, Pi, liftBounds, sqrfPartF.level() - 1, noOneToOne);
     1618      delete [] leadingCoeffs2;
     1619      delete [] liftBounds;
     1620    }
     1621  }
     1622  else
     1623    factors= evalSqrfPartF.getLast();
     1624
     1625  CFList interMedResult= recoverFactors (evalSqrfPartF.getLast(), factors);
    15851626
    15861627  CFList result;

  • factory/facHensel.cc

    r725e600 r327efa2  
    27972797
    27982798  Pi [0] += tmp[0]*xToJ*F.mvar();
     2799
     2800  int degPi, degBuf;
     2801  for (int l= 1; l < factors.length() - 1; l++)
     2802  {
     2803    degPi= degree (Pi [l - 1], x);
     2804    degBuf= degree (bufFactors[l + 1], x);
     2805    if (degPi > 0 && degBuf > 0)
     2806    {
     2807      M (j + 1, l + 1)= mulNTL (Pi [l - 1] [j], bufFactors[l + 1] [j]);
     2808      if (j + 2 <= M.rows())
     2809        M (j + 2, l + 1)= mulNTL (Pi [l - 1][j + 1], bufFactors[l + 1] [j + 1]);
     2810    }
     2811
     2812    if (degPi > 0 && degBuf > 0)
     2813      uIZeroJ= mulNTL (Pi[l -1] [0], buf[l + 1]) +
     2814               mulNTL (uIZeroJ, bufFactors[l+1] [0]);
     2815    else if (degPi > 0)
     2816      uIZeroJ= mulNTL (uIZeroJ, bufFactors[l + 1]);
     2817    else if (degBuf > 0)
     2818      uIZeroJ= mulNTL (Pi[l - 1], buf[1]);
     2819    else
     2820      uIZeroJ= 0;
     2821
     2822    Pi [l] += xToJ*uIZeroJ;
     2823
     2824    one= bufFactors [l + 1];
     2825    two= Pi [l - 1];
     2826    if (degBuf > 0 && degPi > 0)
     2827    {
     2828      while (one.hasTerms() && one.exp() > j) one++;
     2829      while (two.hasTerms() && two.exp() > j) two++;
     2830      for (k= 1; k <= (int) ceil (j/2.0); k++)
     2831      {
     2832        if (k != j - k + 1)
     2833        {
     2834          if ((one.hasTerms() && one.exp() == j - k + 1) &&
     2835              (two.hasTerms() && two.exp() == j - k + 1))
     2836          {
     2837            tmp[l] += mulNTL ((bufFactors[l + 1] [k] + one.coeff()),
     2838                      (Pi[l - 1] [k] + two.coeff())) - M (k + 1, l + 1) -
     2839                      M (j - k + 2, l + 1);
     2840            one++;
     2841            two++;
     2842          }
     2843          else if (one.hasTerms() && one.exp() == j - k + 1)
     2844          {
     2845            tmp[l] += mulNTL ((bufFactors[l + 1] [k] + one.coeff()),
     2846                               Pi[l - 1] [k]) - M (k + 1, l + 1);
     2847            one++;
     2848          }
     2849          else if (two.hasTerms() && two.exp() == j - k + 1)
     2850          {
     2851            tmp[l] += mulNTL (bufFactors[l + 1] [k],
     2852                      (Pi[l - 1] [k] + two.coeff())) - M (k + 1, l + 1);
     2853            two++;
     2854           }
     2855        }
     2856        else
     2857          tmp[l] += M (k + 1, l + 1);
     2858      }
     2859    }
     2860
     2861    if (degPi >= j + 1 && degBuf >= j + 1)
     2862    {
     2863      if (j + 2 <= M.rows())
     2864        tmp [l] += mulNTL ((Pi [l - 1] [j + 1]+ Pi [l - 1] [0]),
     2865                           (bufFactors [l + 1] [j + 1] + bufFactors [l + 1] [0])
     2866                          ) - M(1,l+1) - M (j + 2,l+1);
     2867    }
     2868    else if (degPi >= j + 1)
     2869    {
     2870      if (degBuf > 0)
     2871        tmp[l] += mulNTL (Pi [l - 1] [j+1], bufFactors [l + 1] [0]);
     2872      else
     2873        tmp[l] += mulNTL (Pi [l - 1] [j+1], bufFactors [l + 1]);
     2874    }
     2875    else if (degBuf >= j + 1)
     2876    {
     2877      if (degPi > 0)
     2878        tmp[l] += mulNTL (Pi [l - 1] [0], bufFactors [l + 1] [j + 1]);
     2879      else
     2880        tmp[l] += mulNTL (Pi [l - 1], bufFactors [l + 1] [j + 1]);
     2881    }
     2882
     2883    Pi[l] += tmp[l]*xToJ*F.mvar();
     2884  }
    27992885  return;
    28002886}
    … …  
    28092895  CFList bufFactors2= factors;
    28102896  bufFactors2.removeFirst();
    2811   CanonicalForm s,t;
    2812   extgcd (bufFactors2.getFirst(), bufFactors2.getLast(), s, t);
    2813   diophant= CFList();
    2814   diophant.append (t);
    2815   diophant.append (s);
     2897  diophant= diophantine (F[0], bufFactors2);
    28162898  DEBOUTLN (cerr, "diophant= " << diophant);
    28172899
    … …  
    28462928  }
    28472929
     2930  for (i= 1; i < Pi.size(); i++)
     2931  {
     2932    if (degree (Pi[i-1], x) > 0 && degree (bufFactors [i+1], x) > 0)
     2933    {
     2934      M (1,i+1)= mulNTL (Pi[i-1] [0], bufFactors[i+1] [0]);
     2935      Pi [i]= M (1,i+1) + (mulNTL (Pi[i-1] [1], bufFactors[i+1] [0]) +
     2936                       mulNTL (Pi[i-1] [0], bufFactors [i+1] [1]))*x;
     2937    }
     2938    else if (degree (Pi[i-1], x) > 0)
     2939    {
     2940      M (1,i+1)= mulNTL (Pi[i-1] [0], bufFactors [i+1]);
     2941      Pi [i]=  M(1,i+1) + mulNTL (Pi[i-1] [1], bufFactors[i+1])*x;
     2942    }
     2943    else if (degree (bufFactors[i+1], x) > 0)
     2944    {
     2945      M (1,i+1)= mulNTL (Pi[i-1], bufFactors [i+1] [0]);
     2946      Pi [i]= M (1,i+1) + mulNTL (Pi[i-1], bufFactors[i+1] [1])*x;
     2947    }
     2948    else
     2949    {
     2950      M (1,i+1)= mulNTL (Pi [i-1], bufFactors [i+1]);
     2951      Pi [i]= M (1,i+1);
     2952    }
     2953  }
     2954
    28482955  for (i= 1; i < l; i++)
    28492956    henselStep122 (F, bufFactors2, bufFactors, diophant, M, Pi, i, LCs);
    … …  
    28542961  return;
    28552962}
     2963
    28562964
    28572965/// solve \f$ E=sum_{i= 1}^{r}{\sigma_{i}prod_{j=1, j\neq i}^{r}{f_{i}}}\f$
Note: See TracChangeset for help on using the changeset viewer.