Changeset f876a66 in git for factory/facFqBivar.h


Ignore:
Timestamp:
May 24, 2011, 5:48:25 PM (13 years ago)
Author:
Martin Lee <martinlee84@…>
Branches:
(u'fieker-DuVal', '117eb8c30fc9e991c4decca4832b1d19036c4c65')(u'spielwiese', '38077648e7239f98078663eb941c3c979511150a')
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
File:
1 edited

Legend:

Unmodified
Added
Removed

  • 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
Note: See TracChangeset for help on using the changeset viewer.