Changeset f876a66 in git


Ignore:
Timestamp:
May 24, 2011, 5:48:25 PM (13 years ago)
Author:
Martin Lee <martinlee84@…>
Branches:
(u'spielwiese', '2a584933abf2a2d3082034c7586d38bb6de1a30a')
Children:
11bf82dfd2d328940589f0fb6131155b53e10f7a
Parents:
0415f923fdb78a69504a400113e65cd371cb2150
Message:
added convex dense factorization to bivariate factorization
added logarithmic derivative computation to facFqBivarUtil
changes to in extension test


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

Legend:

Unmodified
Added
Removed

  • factory/facFqBivar.cc

    r0415f9 rf876a66  
    336336            else
    337337            {
    338               if (!isInExtension (buf2, delta, k))
     338              if (!isInExtension (buf2, gamma, k, delta, source, dest))
    339339              {
    340340                buf /= g;
    … …  
    668668          else
    669669          {
    670             if (!isInExtension (buf2, delta, k))
     670            if (!isInExtension (buf2, gamma, k, delta, source, dest))
    671671            {
    672672              appendTestMapDown (result, buf2, info, source, dest);

  • factory/facFqBivar.h

    r0415f9 rf876a66  
    3030#include "cf_util.h"
    3131#include "facFqSquarefree.h"
     32#include "cf_map.h"
     33#include "cfNewtonPolygon.h"
    3234
    3335static const double log2exp= 1.442695041;
    … …  
    5355///         element is the leading coefficient.
    5456/// @sa FqBiSqrfFactorize(), GFBiSqrfFactorize()
     57#ifdef HAVE_NTL
    5558inline
    56 CFList FpBiSqrfFactorize (const CanonicalForm & F ///< [in] a bivariate poly
     59CFList FpBiSqrfFactorize (const CanonicalForm & G ///< [in] a bivariate poly
    5760                         )
    5861{
    5962  ExtensionInfo info= ExtensionInfo (false);
     63  CFMap N;
     64  CanonicalForm F= compress (G, N);
     65  CanonicalForm contentX= content (F, 1);
     66  CanonicalForm contentY= content (F, 2);
     67  F /= (contentX*contentY);
     68  CFFList contentXFactors, contentYFactors;
     69  contentXFactors= factorize (contentX);
     70  contentYFactors= factorize (contentY);
     71  if (contentXFactors.getFirst().factor().inCoeffDomain())
     72    contentXFactors.removeFirst();
     73  if (contentYFactors.getFirst().factor().inCoeffDomain())
     74    contentYFactors.removeFirst();
     75  if (F.inCoeffDomain())
     76  {
     77    CFList result;
     78    for (CFFListIterator i= contentXFactors; i.hasItem(); i++)
     79      result.append (N (i.getItem().factor()));
     80    for (CFFListIterator i= contentYFactors; i.hasItem(); i++)
     81      result.append (N (i.getItem().factor()));
     82    normalize (result);
     83    result.insert (Lc (G));
     84    return result;
     85  }
     86  mat_ZZ M;
     87  vec_ZZ S;
     88  F= compress (F, M, S);
    6089  CFList result= biFactorize (F, info);
    61   result.insert (Lc(F));
     90  for (CFListIterator i= result; i.hasItem(); i++)
     91    i.getItem()= N (decompress (i.getItem(), M, S));
     92  for (CFFListIterator i= contentXFactors; i.hasItem(); i++)
     93    result.append (N(i.getItem().factor()));
     94  for (CFFListIterator i= contentYFactors; i.hasItem(); i++)
     95    result.append (N (i.getItem().factor()));
     96  normalize (result);
     97  result.insert (Lc(G));
    6298  return result;
    6399}
    … …  
    69105/// @sa FpBiSqrfFactorize(), GFBiSqrfFactorize()
    70106inline
    71 CFList FqBiSqrfFactorize (const CanonicalForm & F, ///< [in] a bivariate poly
     107CFList FqBiSqrfFactorize (const CanonicalForm & G, ///< [in] a bivariate poly
    72108                          const Variable& alpha    ///< [in] algebraic variable
    73109                         )
    74110{
    75111  ExtensionInfo info= ExtensionInfo (alpha, false);
     112  CFMap N;
     113  CanonicalForm F= compress (G, N);
     114  CanonicalForm contentX= content (F, 1);
     115  CanonicalForm contentY= content (F, 2);
     116  F /= (contentX*contentY);
     117  CFFList contentXFactors, contentYFactors;
     118  contentXFactors= factorize (contentX);
     119  contentYFactors= factorize (contentY);
     120  if (contentXFactors.getFirst().factor().inCoeffDomain())
     121    contentXFactors.removeFirst();
     122  if (contentYFactors.getFirst().factor().inCoeffDomain())
     123    contentYFactors.removeFirst();
     124  if (F.inCoeffDomain())
     125  {
     126    CFList result;
     127    for (CFFListIterator i= contentXFactors; i.hasItem(); i++)
     128      result.append (N (i.getItem().factor()));
     129    for (CFFListIterator i= contentYFactors; i.hasItem(); i++)
     130      result.append (N (i.getItem().factor()));
     131    normalize (result);
     132    result.insert (Lc (G));
     133    return result;
     134  }
     135  mat_ZZ M;
     136  vec_ZZ S;
     137  F= compress (F, M, S);
    76138  CFList result= biFactorize (F, info);
    77   result.insert (Lc(F));
     139  for (CFListIterator i= result; i.hasItem(); i++)
     140    i.getItem()= N (decompress (i.getItem(), M, S));
     141  for (CFFListIterator i= contentXFactors; i.hasItem(); i++)
     142    result.append (N(i.getItem().factor()));
     143  for (CFFListIterator i= contentYFactors; i.hasItem(); i++)
     144    result.append (N (i.getItem().factor()));
     145  normalize (result);
     146  result.insert (Lc(G));
    78147  return result;
    79148}
    … …  
    85154/// @sa FpBiSqrfFactorize(), FqBiSqrfFactorize()
    86155inline
    87 CFList GFBiSqrfFactorize (const CanonicalForm & F ///< [in] a bivariate poly
     156CFList GFBiSqrfFactorize (const CanonicalForm & G ///< [in] a bivariate poly
    88157                         )
    89158{
    … …  
    91160          "GF as base field expected");
    92161  ExtensionInfo info= ExtensionInfo (getGFDegree(), gf_name, false);
     162  CFMap N;
     163  CanonicalForm F= compress (G, N);
     164  CanonicalForm contentX= content (F, 1);
     165  CanonicalForm contentY= content (F, 2);
     166  F /= (contentX*contentY);
     167  CFList contentXFactors, contentYFactors;
     168  contentXFactors= biFactorize (contentX, info);
     169  contentYFactors= biFactorize (contentY, info);
     170  if (contentXFactors.getFirst().inCoeffDomain())
     171    contentXFactors.removeFirst();
     172  if (contentYFactors.getFirst().inCoeffDomain())
     173    contentYFactors.removeFirst();
     174  if (F.inCoeffDomain())
     175  {
     176    CFList result;
     177    for (CFListIterator i= contentXFactors; i.hasItem(); i++)
     178      result.append (N (i.getItem()));
     179    for (CFListIterator i= contentYFactors; i.hasItem(); i++)
     180      result.append (N (i.getItem()));
     181    normalize (result);
     182    result.insert (Lc (G));
     183    return result;
     184  }
     185  mat_ZZ M;
     186  vec_ZZ S;
     187  F= compress (F, M, S);
    93188  CFList result= biFactorize (F, info);
    94   result.insert (Lc(F));
     189  for (CFListIterator i= result; i.hasItem(); i++)
     190    i.getItem()= N (decompress (i.getItem(), M, S));
     191  for (CFListIterator i= contentXFactors; i.hasItem(); i++)
     192    result.append (N(i.getItem()));
     193  for (CFListIterator i= contentYFactors; i.hasItem(); i++)
     194    result.append (N (i.getItem()));
     195  normalize (result);
     196  result.insert (Lc(G));
    95197  return result;
    96198}
    … …  
    102204/// @sa FqBiFactorize(), GFBiFactorize()
    103205inline
    104 CFFList FpBiFactorize (const CanonicalForm & F ///< [in] a bivariate poly
     206CFFList FpBiFactorize (const CanonicalForm & G ///< [in] a bivariate poly
    105207                      )
    106208{
    107209  ExtensionInfo info= ExtensionInfo (false);
    108210  bool GF= false;
     211  CFMap N;
     212  CanonicalForm F= compress (G, N);
    109213  CanonicalForm LcF= Lc (F);
     214  CanonicalForm contentX= content (F, 1);
     215  CanonicalForm contentY= content (F, 2);
     216  F /= (contentX*contentY);
     217  CFFList contentXFactors, contentYFactors;
     218  contentXFactors= factorize (contentX);
     219  contentYFactors= factorize (contentY);
     220  if (contentXFactors.getFirst().factor().inCoeffDomain())
     221    contentXFactors.removeFirst();
     222  if (contentYFactors.getFirst().factor().inCoeffDomain())
     223    contentYFactors.removeFirst();
     224  decompress (contentXFactors, N);
     225  decompress (contentYFactors, N);
     226  CFFList result, resultRoot;
     227  if (F.inCoeffDomain())
     228  {
     229    result= Union (contentXFactors, contentYFactors);
     230    normalize (result);
     231    result.insert (CFFactor (LcF, 1));
     232    return result;
     233  }
     234  mat_ZZ M;
     235  vec_ZZ S;
     236  F= compress (F, M, S);
    110237  CanonicalForm pthRoot, A;
    111238  CanonicalForm sqrfP= sqrfPart (F/Lc(F), pthRoot, info.getAlpha());
    112239  CFList buf, bufRoot;
    113   CFFList result, resultRoot;
    114240  int p= getCharacteristic();
    115241  int l;
    … …  
    120246    result.removeFirst();
    121247    for (CFFListIterator i= result; i.hasItem(); i++)
    122       i.getItem()= CFFactor(i.getItem().factor(),i.getItem().exp()*ipower(p,l));
     248      i.getItem()= CFFactor (N (decompress (i.getItem().factor(), M, S)),
     249                             i.getItem().exp()*ipower (p,l));
     250    result= Union (result, contentXFactors);
     251    result= Union (result, contentYFactors);
     252    normalize (result);
    123253    result.insert (CFFactor (LcF, 1));
    124254    return result;
    … …  
    129259    A= F/LcF;
    130260    result= multiplicity (A, buf);
     261    for (CFFListIterator i= result; i.hasItem(); i++)
     262      i.getItem()= CFFactor (N (decompress (i.getItem().factor(), M, S)),
     263                             i.getItem().exp());
    131264  }
    132265  if (degree (A) > 0)
    … …  
    134267    resultRoot= FpBiFactorize (A);
    135268    resultRoot.removeFirst();
     269    for (CFFListIterator i= resultRoot; i.hasItem(); i++)
     270      i.getItem()= CFFactor (N (decompress (i.getItem().factor(), M, S)),
     271                             i.getItem().exp());
    136272    result= Union (result, resultRoot);
    137273  }
     274  result= Union (result, contentXFactors);
     275  result= Union (result, contentYFactors);
     276  normalize (result);
    138277  result.insert (CFFactor (LcF, 1));
    139278  return result;
    … …  
    146285/// @sa FpBiFactorize(), FqBiFactorize()
    147286inline
    148 CFFList FqBiFactorize (const CanonicalForm & F, ///< [in] a bivariate poly
     287CFFList FqBiFactorize (const CanonicalForm & G, ///< [in] a bivariate poly
    149288                       const Variable & alpha   ///< [in] algebraic variable
    150289                      )
    … …  
    152291  ExtensionInfo info= ExtensionInfo (alpha, false);
    153292  bool GF= false;
     293  CFMap N;
     294  CanonicalForm F= compress (G, N);
    154295  CanonicalForm LcF= Lc (F);
    155   CanonicalForm pthRoot, A;
     296  CanonicalForm contentX= content (F, 1);
     297  CanonicalForm contentY= content (F, 2);
     298  F /= (contentX*contentY);
     299  CFFList contentXFactors, contentYFactors;
     300  contentXFactors= factorize (contentX);
     301  contentYFactors= factorize (contentY);
     302  if (contentXFactors.getFirst().factor().inCoeffDomain())
     303    contentXFactors.removeFirst();
     304  if (contentYFactors.getFirst().factor().inCoeffDomain())
     305    contentYFactors.removeFirst();
     306  decompress (contentXFactors, N);
     307  decompress (contentYFactors, N);
     308  CFFList result, resultRoot;
     309  if (F.inCoeffDomain())
     310  {
     311    result= Union (contentXFactors, contentYFactors);
     312    normalize (result);
     313    result.insert (CFFactor (LcF, 1));
     314    return result;
     315  }
     316  mat_ZZ M;
     317  vec_ZZ S;
     318  CanonicalForm oldF= F;
     319  F= compress (F, M, S);
     320  CanonicalForm pthRoot, A, tmp;
    156321  CanonicalForm sqrfP= sqrfPart (F/Lc(F), pthRoot, alpha);
    157322  CFList buf, bufRoot;
    158   CFFList result, resultRoot;
    159323  int p= getCharacteristic();
    160324  int q= ipower (p, degree (getMipo (alpha)));
    … …  
    166330    result.removeFirst();
    167331    for (CFFListIterator i= result; i.hasItem(); i++)
    168       i.getItem()= CFFactor(i.getItem().factor(),i.getItem().exp()*ipower(p,l));
     332      i.getItem()= CFFactor (N (decompress (i.getItem().factor(), M, S)),
     333                             i.getItem().exp()*ipower (p,l));
     334    result= Union (result, contentXFactors);
     335    result= Union (result, contentYFactors);
     336    normalize (result);
    169337    result.insert (CFFactor (LcF, 1));
    170338    return result;
    … …  
    175343    A= F/LcF;
    176344    result= multiplicity (A, buf);
     345    for (CFFListIterator i= result; i.hasItem(); i++)
     346      i.getItem()= CFFactor (N (decompress (i.getItem().factor(), M, S)),
     347                             i.getItem().exp());
    177348  }
    178349  if (degree (A) > 0)
    … …  
    180351    resultRoot= FqBiFactorize (A, alpha);
    181352    resultRoot.removeFirst();
     353    for (CFFListIterator i= resultRoot; i.hasItem(); i++)
     354      i.getItem()= CFFactor (N (decompress (i.getItem().factor(), M, S)),
     355                             i.getItem().exp());
    182356    result= Union (result, resultRoot);
    183357  }
     358  result= Union (result, contentXFactors);
     359  result= Union (result, contentYFactors);
     360  normalize (result);
    184361  result.insert (CFFactor (LcF, 1));
    185362  return result;
    … …  
    192369/// @sa FpBiFactorize(), FqBiFactorize()
    193370inline
    194 CFFList GFBiFactorize (const CanonicalForm & F ///< [in] a bivariate poly
     371CFFList GFBiFactorize (const CanonicalForm & G ///< [in] a bivariate poly
    195372                      )
    196373{
    … …  
    199376  ExtensionInfo info= ExtensionInfo (getGFDegree(), gf_name, false);
    200377  bool GF= true;
     378  CFMap N;
     379  CanonicalForm F= compress (G, N);
    201380  CanonicalForm LcF= Lc (F);
     381  CanonicalForm contentX= content (F, 1);
     382  CanonicalForm contentY= content (F, 2);
     383  F /= (contentX*contentY);
     384  CFFList contentXFactors, contentYFactors;
     385  contentXFactors= factorize (contentX);
     386  contentYFactors= factorize (contentY);
     387  if (contentXFactors.getFirst().factor().inCoeffDomain())
     388    contentXFactors.removeFirst();
     389  if (contentYFactors.getFirst().factor().inCoeffDomain())
     390    contentYFactors.removeFirst();
     391  decompress (contentXFactors, N);
     392  decompress (contentYFactors, N);
     393  CFFList result, resultRoot;
     394  if (F.inCoeffDomain())
     395  {
     396    result= Union (contentXFactors, contentYFactors);
     397    normalize (result);
     398    result.insert (CFFactor (LcF, 1));
     399    return result;
     400  }
     401  mat_ZZ M;
     402  vec_ZZ S;
     403  F= compress (F, M, S);
    202404  CanonicalForm pthRoot, A;
    203405  CanonicalForm sqrfP= sqrfPart (F/LcF, pthRoot, info.getAlpha());
    204406  CFList buf;
    205   CFFList result, resultRoot;
    206407  int p= getCharacteristic();
    207408  int q= ipower (p, getGFDegree());
    … …  
    213414    result.removeFirst();
    214415    for (CFFListIterator i= result; i.hasItem(); i++)
    215       i.getItem()= CFFactor(i.getItem().factor(),i.getItem().exp()*ipower(p,l));
     416      i.getItem()= CFFactor (N (decompress (i.getItem().factor(), M, S)),
     417                             i.getItem().exp()*ipower (p,l));
     418    result= Union (result, contentXFactors);
     419    result= Union (result, contentYFactors);
     420    normalize (result);
    216421    result.insert (CFFactor (LcF, 1));
    217422    return result;
    … …  
    222427    A= F/LcF;
    223428    result= multiplicity (A, buf);
     429    for (CFFListIterator i= result; i.hasItem(); i++)
     430      i.getItem()= CFFactor (N (decompress (i.getItem().factor(), M, S)),
     431                             i.getItem().exp());
    224432  }
    225433  if (degree (A) > 0)
    … …  
    227435    resultRoot= GFBiFactorize (A);
    228436    resultRoot.removeFirst();
     437    for (CFFListIterator i= resultRoot; i.hasItem(); i++)
     438      i.getItem()= CFFactor (N (decompress (i.getItem().factor(), M, S)),
     439                             i.getItem().exp());
    229440    result= Union (result, resultRoot);
    230441  }
     442  result= Union (result, contentXFactors);
     443  result= Union (result, contentYFactors);
     444  normalize (result);
    231445  result.insert (CFFactor (LcF, 1));
    232446  return result;
    233447}
     448
     449#endif
    234450
    235451/// \f$ \prod_{f\in L} {f (0, x)} \ mod\ M \f$ via divide-and-conquer

  • factory/facFqBivarUtil.cc

    r0415f9 rf876a66  
    2525#include "cf_iter.h"
    2626#include "facFqBivarUtil.h"
     27#include "cfNewtonPolygon.h"
     28#include "facHensel.h"
    2729
    2830
    … …  
    4143  for (CFListIterator i= factors; i.hasItem(); i++)
    4244    i.getItem()= N (i.getItem());
    43   return;
     45}
     46
     47void decompress (CFFList& factors, const CFMap& N)
     48{
     49  for (CFFListIterator i= factors; i.hasItem(); i++)
     50    i.getItem()= CFFactor (N (i.getItem().factor()), i.getItem().exp());
    4451}
    4552
    … …  
    113120
    114121static inline
    115 bool FqInExtensionHelper (const CanonicalForm& F, const CanonicalForm& gamma)
     122bool FqInExtensionHelper (const CanonicalForm& F, const CanonicalForm& gamma,
     123                          const CanonicalForm& delta, CFList& source,
     124                          CFList& dest)
    116125{
    117126  bool result= false;
    … …  
    123132      return true;
    124133    else
    125       return result;
     134    {
     135      int pos= findItem (source, F);
     136      if (pos > 0)
     137        return false;
     138      Variable a;
     139      hasFirstAlgVar (F, a);
     140      int bound= ipower (getCharacteristic(), degree (getMipo (a)));
     141      CanonicalForm buf= 1;
     142      for (int i= 1; i < bound; i++)
     143      {
     144        buf *= gamma;
     145        if (buf == F)
     146        {
     147          source.append (buf);
     148          dest.append (power (delta, i));
     149          return false;
     150        }
     151      }
     152      return true;
     153    }
    126154  }
    127155  else
    … …  
    129157    for (CFIterator i= F; i.hasTerms(); i++)
    130158    {
    131       result= FqInExtensionHelper (i.coeff(), gamma);
     159      result= FqInExtensionHelper (i.coeff(), gamma, delta, source, dest);
    132160      if (result == true)
    133161        return result;
    … …  
    138166
    139167bool isInExtension (const CanonicalForm& F, const CanonicalForm& gamma,
    140                     const int k)
     168                    const int k, const CanonicalForm& delta,
     169                    CFList& source, CFList& dest)
    141170{
    142171  bool result;
    … …  
    152181  else
    153182  {
    154     result= FqInExtensionHelper (F, gamma);
     183    result= FqInExtensionHelper (F, gamma, delta, source, dest);
    155184    return result;
    156185  }
    … …  
    191220  if (k > 1)
    192221  {
    193     if (!isInExtension (g, delta, k))
     222    if (!isInExtension (g, gamma, k, delta, source, dest))
    194223    {
    195224      g= GFMapDown (g, k);
    … …  
    199228  else if (k == 1)
    200229  {
    201     if (!isInExtension (g, delta, k));
     230    if (!isInExtension (g, gamma, k, delta, source, dest));
    202231      factors.append (g);
    203232  }
    … …  
    209238  else if (!k && beta != Variable (1))
    210239  {
    211     if (!isInExtension (g, delta, k))
     240    if (!isInExtension (g, gamma, k, delta, source, dest))
    212241    {
    213242      g= mapDown (g, delta, gamma, alpha, source, dest);
    … …  
    245274}
    246275
     276void normalize (CFFList& factors)
     277{
     278  for (CFFListIterator i= factors; i.hasItem(); i++)
     279    i.getItem()= CFFactor (i.getItem().factor()/Lc(i.getItem().factor()),
     280                           i.getItem().exp());
     281  return;
     282}
     283
    247284CFList subset (int index [], const int& s, const CFArray& elements,
    248285               bool& noSubset)
    … …  
    392429}
    393430
     431CFArray
     432logarithmicDerivative (const CanonicalForm& F, const CanonicalForm& G, int l,
     433                       CanonicalForm& Q
     434                      )
     435{
     436  Variable x= Variable (2);
     437  Variable y= Variable (1);
     438  CanonicalForm xToL= power (x, l);
     439  CanonicalForm q,r;
     440  CanonicalForm logDeriv;
     441
     442  q= newtonDiv (F, G, xToL);
     443
     444  logDeriv= mulMod2 (q, deriv (G, y), xToL);
     445
     446  logDeriv= swapvar (logDeriv, x, y);
     447  int j= degree (logDeriv) + 1;
     448  CFArray result= CFArray (j);
     449  for (CFIterator i= logDeriv; i.hasTerms() && !logDeriv.isZero(); i++)
     450  {
     451    if (i.exp() == j - 1)
     452    {
     453      result [j - 1]= swapvar (i.coeff(), x, y);
     454      j--;
     455    }
     456    else
     457    {
     458      for (; i.exp() < j - 1; j--)
     459        result [j - 1]= 0;
     460      result [j - 1]= swapvar (i.coeff(), x, y);
     461      j--;
     462    }
     463  }
     464  for (; j > 0; j--)
     465    result [j - 1]= 0;
     466  Q= q;
     467  return result;
     468}
     469
     470CFArray
     471logarithmicDerivative (const CanonicalForm& F, const CanonicalForm& G, int l,
     472                       int oldL, const CanonicalForm& oldQ, CanonicalForm& Q
     473                      )
     474{
     475  Variable x= Variable (2);
     476  Variable y= Variable (1);
     477  CanonicalForm xToL= power (x, l);
     478  CanonicalForm xToOldL= power (x, oldL);
     479  CanonicalForm xToLOldL= power (x, l-oldL);
     480  CanonicalForm q,r;
     481  CanonicalForm logDeriv;
     482
     483  CanonicalForm bufF= mod (F, xToL);
     484  CanonicalForm oldF= mulMod2 (G, oldQ, xToL);
     485  bufF -= oldF;
     486  bufF= div (bufF, xToOldL);
     487
     488  q= newtonDiv (bufF, G, xToLOldL);
     489  q *= xToOldL;
     490  q += oldQ;
     491
     492  logDeriv= mulMod2 (q, deriv (G, y), xToL);
     493
     494  logDeriv= swapvar (logDeriv, x, y);
     495  int j= degree (logDeriv) + 1;
     496  CFArray result= CFArray (j);
     497  for (CFIterator i= logDeriv; i.hasTerms() && !logDeriv.isZero(); i++)
     498  {
     499    if (i.exp() == j - 1)
     500    {
     501      result [j - 1]= swapvar (i.coeff(), x, y);
     502      j--;
     503    }
     504    else
     505    {
     506      for (; i.exp() < j - 1; j--)
     507        result [j - 1]= 0;
     508      result [j - 1]= swapvar (i.coeff(), x, y);
     509      j--;
     510    }
     511  }
     512  for (; j > 0; j--)
     513    result [j - 1]= 0;
     514  Q= q;
     515  return result;
     516}
     517
     518void
     519writeInMatrix (CFMatrix& M, const CFArray& A, const int column,
     520               const int startIndex
     521              )
     522{
     523  ASSERT (A.size () - startIndex > 0, "wrong starting index");
     524  ASSERT (A.size () - startIndex == M.rows(), "wrong starting index");
     525  ASSERT (column > 0 && column <= M.columns(), "wrong column");
     526  if (A.size() - startIndex <= 0) return;
     527  int j= 1;
     528  for (int i= startIndex; i < A.size(); i++, j++)
     529    M (j, column)= A [i];
     530}
     531
     532CFArray getCoeffs (const CanonicalForm& F, const int k)
     533{
     534  ASSERT (F.isUnivariate(), "univariate input expected");
     535  if (degree (F, 2) < k)
     536    return CFArray();
     537
     538  CFArray result= CFArray (degree (F) - k + 1);
     539  CFIterator j= F;
     540  for (int i= degree (F); i >= k; i--)
     541  {
     542    if (j.exp() == i)
     543    {
     544      result [i - k]= j.coeff();
     545      j++;
     546      if (!j.hasTerms())
     547        return result;
     548    }
     549    else
     550      result[i - k]= 0;
     551  }
     552  return result;
     553}
     554
     555CFArray getCoeffs (const CanonicalForm& F, const int k, const Variable& alpha)
     556{
     557  ASSERT (F.isUnivariate(), "univariate input expected");
     558  if (degree (F, 2) < k)
     559    return CFArray ();
     560
     561  int d= degree (getMipo (alpha));
     562  CFArray result= CFArray ((degree (F) - k + 1)*d);
     563  CFIterator j= F;
     564  CanonicalForm buf;
     565  CFIterator iter;
     566  for (int i= degree (F); i >= k; i--)
     567  {
     568    if (j.exp() == i)
     569    {
     570      iter= j.coeff();
     571      for (int l= degree (j.coeff(), alpha); l >= 0; l--)
     572      {
     573        if (iter.exp() == l)
     574        {
     575          result [(i - k)*d + l]= iter.coeff();
     576          iter++;
     577          if (!iter.hasTerms())
     578            break;
     579        }
     580      }
     581      j++;
     582      if (!j.hasTerms())
     583        return result;
     584    }
     585    else
     586    {
     587      for (int l= 0; l < d; l++)
     588        result[(i - k)*d + l]= 0;
     589    }
     590  }
     591  return result;
     592}
     593
     594#ifdef HAVE_NTL
     595CFArray
     596getCoeffs (const CanonicalForm& G, const int k, const int l, const int degMipo,
     597           const Variable& alpha, const CanonicalForm& evaluation,
     598           const mat_zz_p& M)
     599{
     600  ASSERT (G.isUnivariate(), "univariate input expected");
     601  CanonicalForm F= G (G.mvar() - evaluation, G.mvar());
     602  if (F.isZero())
     603    return CFArray ();
     604
     605  Variable y= Variable (2);
     606  F= F (power (y, degMipo), y);
     607  F= F (y, alpha);
     608  zz_pX NTLF= convertFacCF2NTLzzpX (F);
     609  NTLF.rep.SetLength (l*degMipo);
     610  NTLF.rep= M*NTLF.rep;
     611  NTLF.normalize();
     612  F= convertNTLzzpX2CF (NTLF, y);
     613  int d= degMipo;
     614
     615  if (degree (F, 2) < k)
     616    return CFArray();
     617
     618  CFArray result= CFArray (degree (F) - k + 1);
     619
     620  CFIterator j= F;
     621  for (int i= degree (F); i >= k; i--)
     622  {
     623    if (j.exp() == i)
     624    {
     625      result [i - k]= j.coeff();
     626      j++;
     627      if (!j.hasTerms())
     628        return result;
     629    }
     630    else
     631      result[i - k]= 0;
     632  }
     633  return result;
     634}
     635#endif
     636
     637int * computeBounds (const CanonicalForm& F, int& n)
     638{
     639  n= degree (F, 1);
     640  int* result= new int [n];
     641  int sizeOfNewtonPolygon;
     642  int** newtonPolyg= newtonPolygon (F, sizeOfNewtonPolygon);
     643
     644  int minXIndex= 0, minYIndex= 0, maxXIndex= 0, maxYIndex= 0;
     645  int minX, minY, maxX, maxY;
     646  minX= newtonPolyg [0] [0];
     647  minY= newtonPolyg [0] [1];
     648  maxX= minX;
     649  maxY= minY;
     650  for (int i= 1; i < sizeOfNewtonPolygon; i++)
     651  {
     652    if (minX > newtonPolyg [i] [0])
     653    {
     654      minX= newtonPolyg [i] [0];
     655      minXIndex= i;
     656    }
     657    if (maxX < newtonPolyg [i] [0])
     658    {
     659      maxX= newtonPolyg [i] [0];
     660      maxXIndex= i;
     661    }
     662    if (minY > newtonPolyg [i] [1])
     663    {
     664      minY= newtonPolyg [i] [1];
     665      minYIndex= i;
     666    }
     667    if (maxY < newtonPolyg [i] [1])
     668    {
     669      maxY= newtonPolyg [i] [1];
     670      maxYIndex= i;
     671    }
     672  }
     673
     674  int k= maxX;
     675  bool hitMaxX= false;
     676  for (int i= 0; i < n; i++)
     677  {
     678    if (i + 1 > maxY || i + 1 < minY)
     679    {
     680      result [i]= 0;
     681      continue;
     682    }
     683    int* point= new int [2];
     684    point [0]= k;
     685    point [1]= i + 1;
     686    while (!isInPolygon (newtonPolyg, sizeOfNewtonPolygon, point) && k > 0)
     687    {
     688      k--;
     689      point [0]= k;
     690    }
     691    result [i]= k;
     692    k= maxX;
     693    delete [] point;
     694  }
     695
     696  return result;
     697}
     698
    394699int
    395700substituteCheck (const CanonicalForm& F, const Variable& x)

  • factory/facFqBivarUtil.h

    r0415f9 rf876a66  
    2121#include "ExtensionInfo.h"
    2222
     23#ifdef HAVE_NTL
     24#include "NTLconvert.h"
     25#endif
     26
    2327/// append @a factors2 on @a factors1
    2428void append (CFList& factors1,       ///< [in,out] a list of polys
    … …  
    2933void decompress (CFList& factors, ///< [in,out] a list of polys
    3034                 const CFMap& N   ///< [in] a map
     35                );
     36
     37/// as above
     38void decompress (CFFList& factors, ///< [in,out] a list of factors
     39                 const CFMap& N    ///< [in] a map
    3140                );
    3241
    … …  
    6170                                                 ///< Fq if we are not over some
    6271                                                 ///< GF
    63                     const int k                  ///< some int k such that k
     72                    const int k,                 ///< some int k such that k
    6473                                                 ///< divides l if we are not
    6574                                                 ///< over some Fq
     75                    const CanonicalForm& delta,  ///< [in] image of gamma
     76                    CFList& source,              ///< [in,out] list of preimages
     77                    CFList& dest                 ///< [in,out] list of images
    6678                   );
    6779
    … …  
    111123               );
    112124
     125/// as above
     126void normalize (CFFList& factors ///< [in,out] a list of factors
     127               );
     128
    113129/// extract a subset given by @a index of size @a s from @a elements, if there
    114130/// is no subset we have not yet considered noSubset is set to true. @a index
    … …  
    158174                     );
    159175
     176/// compute the coefficients of the logarithmic derivative of G mod
     177/// Variable (2)^l over Fq
     178///
     179/// @return an array of coefficients of the logarithmic derivative of G mod
     180///         Variable (2)^l
     181CFArray logarithmicDerivative (const CanonicalForm& F,///<[in] a bivariate poly
     182                              const CanonicalForm& G, ///<[in] a factor of F
     183                              int l,                  ///<[in] lifting precision
     184                              CanonicalForm& Q        ///<[in,out] F/G
     185                              );
     186
     187/// compute the coefficients of the logarithmic derivative of G mod
     188/// Variable (2)^l over Fq with oldQ= F/G mod Variable (2)^oldL
     189///
     190/// @return an array of coefficients of the logarithmic derivative of G mod
     191///         Variable (2)^l
     192CFArray
     193logarithmicDerivative (const CanonicalForm& F,   ///< [in] bivariate poly
     194                       const CanonicalForm& G,   ///< [in] a factor of F
     195                       int l,                    ///< [in] lifting precision
     196                       int oldL,                 ///< [in] old precision
     197                       const CanonicalForm& oldQ,///< [in] F/G mod
     198                                                 ///< Variable(2)^oldL
     199                       CanonicalForm& Q          ///< [in, out] F/G
     200                      );
     201
     202/// compute bounds for logarithmic derivative as described in K. Belabas,
     203/// M. van Hoeij, J. KlÃŒners, and A. Steel, Factoring polynomials over global
     204/// fields
     205///
     206/// @return @a computeBounds returns bounds as described above
     207int *
     208computeBounds (const CanonicalForm& F,///< [in] compressed bivariate polynomial
     209               int& n                 ///< [in,out] length of output
     210              );
     211
     212/// extract coefficients of \f$ x^i \f$ for \f$i\geq k\f$ where \f$ x \f$ is
     213/// a variable of level 1
     214///
     215/// @return coefficients of \f$ x^i \f$ for \f$i\geq k\f$
     216/// @sa {getCoeffs (const CanonicalForm&, const int, const Variable&),
     217/// getCoeffs (const CanonicalForm&, const int, const int, const int,
     218/// const Variable&, const CanonicalForm&, const mat_zz_p&)}
     219CFArray
     220getCoeffs (const CanonicalForm& F,///< [in] compressed bivariate poly over F_p
     221           const int k            ///< [in] some int
     222          );
     223
     224/// extract coefficients of \f$ x^i \f$ for \f$i\geq k\f$ where \f$ x \f$ is
     225/// a variable of level 1
     226///
     227/// @return coefficients of \f$ x^i \f$ for \f$i\geq k\f$
     228/// @sa {getCoeffs (const CanonicalForm&, const int),
     229/// getCoeffs (const CanonicalForm&, const int, const int, const int,
     230/// const Variable&, const CanonicalForm&, const mat_zz_p&)}
     231CFArray
     232getCoeffs (const CanonicalForm& F,///< [in] compressed bivariate poly over
     233                                  ///< F_p(alpha)
     234           const int k,           ///< [in] some int
     235           const Variable& alpha  ///< [in] algebraic variable
     236          );
     237
     238#ifdef HAVE_NTL
     239/// extract coefficients of \f$ x^i \f$ for \f$i\geq k\f$ where \f$ x \f$ is
     240/// a variable of level 1
     241///
     242/// @return coefficients of \f$ x^i \f$ for \f$i\geq k\f$
     243/// @sa {getCoeffs (const CanonicalForm&, const int, const Variable& alpha),
     244/// getCoeffs (const CanonicalForm&, const int)}
     245CFArray
     246getCoeffs (const CanonicalForm& F,         ///< [in] compressed bivariate poly
     247           const int k,                    ///< [in] some int
     248           const int l,                    ///< [in] precision
     249           const int degMipo,              ///< [in] degree of minimal poly
     250           const Variable& alpha,          ///< [in] algebraic variable
     251           const CanonicalForm& evaluation,///< [in] evaluation point
     252           const mat_zz_p& M               ///< [in] bases change matrix
     253          );
     254#endif
     255
     256/// write A into M starting at row startIndex
     257void
     258writeInMatrix (CFMatrix& M,        ///< [in,out] some matrix
     259               const CFArray& A,   ///< [in] array of polys
     260               const int column,   ///< [in] column in which A is written
     261               const int startIndex///< [in] row in which to start
     262              );
     263
    160264/// checks if a substitution x^n->x is possible
    161265///

  • factory/facFqFactorize.cc

    r0415f9 rf876a66  
    696696        else
    697697        {
    698           if (!isInExtension (buf2, delta, k))
     698          if (!isInExtension (buf2, gamma, k, delta, source, dest))
    699699          {
    700700            appendTestMapDown (result, buf2, info, source, dest);
    … …  
    924924    degMipoBeta= degree (getMipo (beta));
    925925
     926  CFList source, dest;
    926927  for (CFListIterator i= factors; i.hasItem(); i++)
    927928  {
    … …  
    945946      else
    946947      {
    947         if (!isInExtension (gg, delta, k))
     948        if (!isInExtension (gg, gamma, k, delta, source, dest))
    948949        {
    949950          buf /= g;
    … …  
    10961097      else
    10971098      {
    1098         if (!isInExtension (gg, delta, k))
     1099        if (!isInExtension (gg, gamma, k, delta, source, dest))
    10991100        {
    11001101          appendTestMapDown (result, gg, info, source, dest);
Note: See TracChangeset for help on using the changeset viewer.