Changeset f9b796e in git


Ignore:
Timestamp:
Jan 24, 2012, 5:47:03 PM (11 years ago)
Author:
Martin Lee <martinlee84@…>
Branches:
(u'jengelh-datetime', 'ceac47cbc86fe4a15902392bdbb9bd2ae0ea02c6')(u'spielwiese', '0604212ebb110535022efecad887940825b97c3f')
Children:
6fd83c451371ff612e9c1323bb1f472466b5933c
Parents:
3af6b6d1da095923676c7d275f300a6c82b2f46d
git-author:
Martin Lee <martinlee84@web.de>2012-01-24 17:47:03+01:00
git-committer:
Oleksandr Motsak <motsak@mathematik.uni-kl.de>2012-02-10 14:16:43+01:00
Message:
chg: substitution in the top level routines
Location:
factory
Files:
4 edited

Legend:

Unmodified
Added
Removed

  • factory/facBivar.h

    r3af6b6 rf9b796e  
    4141#ifdef HAVE_NTL
    4242inline
    43 CFList ratBiSqrfFactorize (const CanonicalForm & G, ///< [in] a bivariate poly
    44                            const Variable& v
    45                          )
     43CFList
     44ratBiSqrfFactorize (const CanonicalForm & G, ///< [in] a bivariate poly
     45                    const Variable& v        ///< [in] algebraic variable
     46                   )
    4647{
    4748  CFMap N;
    … …  
    9495///         multiplicity, the first element is the leading coefficient.
    9596inline
    96 CFFList ratBiFactorize (const CanonicalForm & G, ///< [in] a bivariate poly
    97                         const Variable& v
    98                       )
     97CFFList
     98ratBiFactorize (const CanonicalForm & G, ///< [in] a bivariate poly
     99                const Variable& v,       ///< [in] algebraic variable
     100                bool substCheck= true    ///< [in] enables substitute check
     101               )
    99102{
    100103  CFMap N;
    101104  CanonicalForm F= compress (G, N);
     105
     106  if (substCheck)
     107  {
     108    bool foundOne= false;
     109    int * substDegree= new int [F.level()];
     110    for (int i= 1; i <= F.level(); i++)
     111    {
     112      substDegree[i-1]= substituteCheck (F, Variable (i));
     113      if (substDegree [i-1] > 1)
     114      {
     115        foundOne= true;
     116        subst (F, F, substDegree[i-1], Variable (i));
     117      }
     118    }
     119    if (foundOne)
     120    {
     121      CFFList result= ratBiFactorize (F, v, false);
     122      CFFList newResult, tmp;
     123      CanonicalForm tmp2;
     124      newResult.insert (result.getFirst());
     125      result.removeFirst();
     126      for (CFFListIterator i= result; i.hasItem(); i++)
     127      {
     128        tmp2= i.getItem().factor();
     129        for (int j= 1; j <= F.level(); j++)
     130        {
     131          if (substDegree[j-1] > 1)
     132            tmp2= reverseSubst (tmp2, substDegree[j-1], Variable (j));
     133        }
     134        tmp= ratBiFactorize (tmp2, v, false);
     135        tmp.removeFirst();
     136        for (CFFListIterator j= tmp; j.hasItem(); j++)
     137          newResult.append (CFFactor (j.getItem().factor(),
     138                                      j.getItem().exp()*i.getItem().exp()));
     139      }
     140      decompress (newResult, N);
     141      delete [] substDegree;
     142      return newResult;
     143    }
     144    delete [] substDegree;
     145  }
     146
    102147  CanonicalForm LcF= Lc (F);
    103148  CanonicalForm contentX= content (F, 1);

  • factory/facFactorize.h

    r3af6b6 rf9b796e  
    3535#ifdef HAVE_NTL
    3636inline
    37 CFList ratSqrfFactorize (const CanonicalForm & G, ///< [in] a multivariate poly
    38                          const Variable& v
    39                        )
     37CFList
     38ratSqrfFactorize (const CanonicalForm & G,       ///<[in] a multivariate poly
     39                  const Variable& v              ///<[in] algebraic variable
     40                 )
    4041{
    4142  if (getNumVars (G) == 2)
    … …  
    5859///         multiplicity, the first element is the leading coefficient.
    5960inline
    60 CFFList ratFactorize (const CanonicalForm& G, ///< [in] a multivariate poly
    61                       const Variable& v
    62                     )
     61CFFList
     62ratFactorize (const CanonicalForm& G,        ///<[in] a multivariate poly
     63              const Variable& v,             ///<[in] algebraic variable
     64              bool substCheck= true          ///<[in] enables substitute check
     65             )
    6366{
    6467  if (getNumVars (G) == 2)
    … …  
    6871  }
    6972  CanonicalForm F= G;
     73
     74  if (substCheck)
     75  {
     76    bool foundOne= false;
     77    int * substDegree= new int [F.level()];
     78    for (int i= 1; i <= F.level(); i++)
     79    {
     80      if (degree (F, i) > 0)
     81      {
     82        substDegree[i-1]= substituteCheck (F, Variable (i));
     83        if (substDegree [i-1] > 1)
     84        {
     85          foundOne= true;
     86          subst (F, F, substDegree[i-1], Variable (i));
     87        }
     88      }
     89      else
     90        substDegree[i-1]= -1;
     91    }
     92    if (foundOne)
     93    {
     94      CFFList result= ratFactorize (F, v, false);
     95      CFFList newResult, tmp;
     96      CanonicalForm tmp2;
     97      newResult.insert (result.getFirst());
     98      result.removeFirst();
     99      for (CFFListIterator i= result; i.hasItem(); i++)
     100      {
     101        tmp2= i.getItem().factor();
     102        for (int j= 1; j <= G.level(); j++)
     103        {
     104          if (substDegree[j-1] > 1)
     105            tmp2= reverseSubst (tmp2, substDegree[j-1], Variable (j));
     106        }
     107        tmp= ratFactorize (tmp2, v, false);
     108        tmp.removeFirst();
     109        for (CFFListIterator j= tmp; j.hasItem(); j++)
     110          newResult.append (CFFactor (j.getItem().factor(),
     111                                      j.getItem().exp()*i.getItem().exp()));
     112      }
     113      delete [] substDegree;
     114      return newResult;
     115    }
     116    delete [] substDegree;
     117  }
     118
    70119  CanonicalForm LcF= Lc (F);
    71120  if (isOn (SW_RATIONAL))

  • factory/facFqBivar.h

    r3af6b6 rf9b796e  
    200200/// @sa FqBiFactorize(), GFBiFactorize()
    201201inline
    202 CFFList FpBiFactorize (const CanonicalForm & G ///< [in] a bivariate poly
    203                       )
     202CFFList
     203FpBiFactorize (const CanonicalForm & G, ///< [in] a bivariate poly
     204               bool substCheck= true    ///< [in] enables substitute check
     205              )
    204206{
    205207  ExtensionInfo info= ExtensionInfo (false);
    206208  CFMap N;
    207209  CanonicalForm F= compress (G, N);
     210
     211  if (substCheck)
     212  {
     213    bool foundOne= false;
     214    int * substDegree= new int [F.level()];
     215    for (int i= 1; i <= F.level(); i++)
     216    {
     217      substDegree[i-1]= substituteCheck (F, Variable (i));
     218      if (substDegree [i-1] > 1)
     219      {
     220        foundOne= true;
     221        subst (F, F, substDegree[i-1], Variable (i));
     222      }
     223    }
     224    if (foundOne)
     225    {
     226      CFFList result= FpBiFactorize (F, false);
     227      CFFList newResult, tmp;
     228      CanonicalForm tmp2;
     229      newResult.insert (result.getFirst());
     230      result.removeFirst();
     231      for (CFFListIterator i= result; i.hasItem(); i++)
     232      {
     233        tmp2= i.getItem().factor();
     234        for (int j= 1; j <= F.level(); j++)
     235        {
     236          if (substDegree[j-1] > 1)
     237            tmp2= reverseSubst (tmp2, substDegree[j-1], Variable (j));
     238        }
     239        tmp= FpBiFactorize (tmp2, false);
     240        tmp.removeFirst();
     241        for (CFFListIterator j= tmp; j.hasItem(); j++)
     242          newResult.append (CFFactor (j.getItem().factor(),
     243                                      j.getItem().exp()*i.getItem().exp()));
     244      }
     245      decompress (newResult, N);
     246      delete [] substDegree;
     247      return newResult;
     248    }
     249    delete [] substDegree;
     250  }
     251
    208252  CanonicalForm LcF= Lc (F);
    209253  CanonicalForm contentX= content (F, 1);
    … …  
    238282  {
    239283    pthRoot= maxpthRoot (pthRoot, p, l);
    240     result= FpBiFactorize (pthRoot);
     284    result= FpBiFactorize (pthRoot, false);
    241285    result.removeFirst();
    242286    for (CFFListIterator i= result; i.hasItem(); i++)
    … …  
    260304  if (degree (A) > 0)
    261305  {
    262     resultRoot= FpBiFactorize (A);
     306    resultRoot= FpBiFactorize (A, false);
    263307    resultRoot.removeFirst();
    264308    for (CFFListIterator i= resultRoot; i.hasItem(); i++)
    … …  
    280324/// @sa FpBiFactorize(), FqBiFactorize()
    281325inline
    282 CFFList FqBiFactorize (const CanonicalForm & G, ///< [in] a bivariate poly
    283                        const Variable & alpha   ///< [in] algebraic variable
    284                       )
     326CFFList
     327FqBiFactorize (const CanonicalForm & G, ///< [in] a bivariate poly
     328               const Variable & alpha,  ///< [in] algebraic variable
     329               bool substCheck= true    ///< [in] enables substitute check
     330              )
    285331{
    286332  ExtensionInfo info= ExtensionInfo (alpha, false);
    287333  CFMap N;
    288334  CanonicalForm F= compress (G, N);
     335
     336  if (substCheck)
     337  {
     338    bool foundOne= false;
     339    int * substDegree= new int [F.level()];
     340    for (int i= 1; i <= F.level(); i++)
     341    {
     342      substDegree[i-1]= substituteCheck (F, Variable (i));
     343      if (substDegree [i-1] > 1)
     344      {
     345        foundOne= true;
     346        subst (F, F, substDegree[i-1], Variable (i));
     347      }
     348    }
     349    if (foundOne)
     350    {
     351      CFFList result= FqBiFactorize (F, alpha, false);
     352      CFFList newResult, tmp;
     353      CanonicalForm tmp2;
     354      newResult.insert (result.getFirst());
     355      result.removeFirst();
     356      for (CFFListIterator i= result; i.hasItem(); i++)
     357      {
     358        tmp2= i.getItem().factor();
     359        for (int j= 1; j <= F.level(); j++)
     360        {
     361          if (substDegree[j-1] > 1)
     362            tmp2= reverseSubst (tmp2, substDegree[j-1], Variable (j));
     363        }
     364        tmp= FqBiFactorize (tmp2, alpha, false);
     365        tmp.removeFirst();
     366        for (CFFListIterator j= tmp; j.hasItem(); j++)
     367          newResult.append (CFFactor (j.getItem().factor(),
     368                                      j.getItem().exp()*i.getItem().exp()));
     369      }
     370      decompress (newResult, N);
     371      delete [] substDegree;
     372      return newResult;
     373    }
     374    delete [] substDegree;
     375  }
     376
    289377  CanonicalForm LcF= Lc (F);
    290378  CanonicalForm contentX= content (F, 1);
    … …  
    321409  {
    322410    pthRoot= maxpthRoot (pthRoot, q, l);
    323     result= FqBiFactorize (pthRoot, alpha);
     411    result= FqBiFactorize (pthRoot, alpha, false);
    324412    result.removeFirst();
    325413    for (CFFListIterator i= result; i.hasItem(); i++)
    … …  
    343431  if (degree (A) > 0)
    344432  {
    345     resultRoot= FqBiFactorize (A, alpha);
     433    resultRoot= FqBiFactorize (A, alpha, false);
    346434    resultRoot.removeFirst();
    347435    for (CFFListIterator i= resultRoot; i.hasItem(); i++)
    … …  
    363451/// @sa FpBiFactorize(), FqBiFactorize()
    364452inline
    365 CFFList GFBiFactorize (const CanonicalForm & G ///< [in] a bivariate poly
    366                       )
     453CFFList
     454GFBiFactorize (const CanonicalForm & G, ///< [in] a bivariate poly
     455               bool substCheck= true    ///< [in] enables substitute check
     456              )
    367457{
    368458  ASSERT (CFFactory::gettype() == GaloisFieldDomain,
    … …  
    371461  CFMap N;
    372462  CanonicalForm F= compress (G, N);
     463
     464  if (substCheck)
     465  {
     466    bool foundOne= false;
     467    int * substDegree= new int [F.level()];
     468    for (int i= 1; i <= F.level(); i++)
     469    {
     470      substDegree[i-1]= substituteCheck (F, Variable (i));
     471      if (substDegree [i-1] > 1)
     472      {
     473        foundOne= true;
     474        subst (F, F, substDegree[i-1], Variable (i));
     475      }
     476    }
     477    if (foundOne)
     478    {
     479      CFFList result= GFBiFactorize (F, false);
     480      CFFList newResult, tmp;
     481      CanonicalForm tmp2;
     482      newResult.insert (result.getFirst());
     483      result.removeFirst();
     484      for (CFFListIterator i= result; i.hasItem(); i++)
     485      {
     486        tmp2= i.getItem().factor();
     487        for (int j= 1; j <= F.level(); j++)
     488        {
     489          if (substDegree[j-1] > 1)
     490            tmp2= reverseSubst (tmp2, substDegree[j-1], Variable (j));
     491        }
     492        tmp= GFBiFactorize (tmp2, false);
     493        tmp.removeFirst();
     494        for (CFFListIterator j= tmp; j.hasItem(); j++)
     495          newResult.append (CFFactor (j.getItem().factor(),
     496                                      j.getItem().exp()*i.getItem().exp()));
     497      }
     498      decompress (newResult, N);
     499      delete [] substDegree;
     500      return newResult;
     501    }
     502    delete [] substDegree;
     503  }
     504
    373505  CanonicalForm LcF= Lc (F);
    374506  CanonicalForm contentX= content (F, 1);
    … …  
    404536  {
    405537    pthRoot= maxpthRoot (pthRoot, q, l);
    406     result= GFBiFactorize (pthRoot);
     538    result= GFBiFactorize (pthRoot, false);
    407539    result.removeFirst();
    408540    for (CFFListIterator i= result; i.hasItem(); i++)
    … …  
    426558  if (degree (A) > 0)
    427559  {
    428     resultRoot= GFBiFactorize (A);
     560    resultRoot= GFBiFactorize (A, false);
    429561    resultRoot.removeFirst();
    430562    for (CFFListIterator i= resultRoot; i.hasItem(); i++)

  • factory/facFqFactorize.h

    r3af6b6 rf9b796e  
    9696/// @sa FqFactorize(), GFFactorize()
    9797inline
    98 CFFList FpFactorize (const CanonicalForm& F ///< [in] a multivariate poly
     98CFFList FpFactorize (const CanonicalForm& G,///< [in] a multivariate poly
     99                     bool substCheck= true  ///< [in] enables substitute check
    99100                    )
    100101{
    101   if (getNumVars (F) == 2)
    102     return FpBiFactorize (F);
     102  if (getNumVars (G) == 2)
     103    return FpBiFactorize (G, substCheck);
     104
     105  CanonicalForm F= G;
     106  if (substCheck)
     107  {
     108    bool foundOne= false;
     109    int * substDegree= new int [F.level()];
     110    for (int i= 1; i <= F.level(); i++)
     111    {
     112      if (degree (F, i) > 0)
     113      {
     114        substDegree[i-1]= substituteCheck (F, Variable (i));
     115        if (substDegree [i-1] > 1)
     116        {
     117          foundOne= true;
     118          subst (F, F, substDegree[i-1], Variable (i));
     119        }
     120      }
     121      else
     122        substDegree[i-1]= -1;
     123    }
     124    if (foundOne)
     125    {
     126      CFFList result= FpFactorize (F, false);
     127      CFFList newResult, tmp;
     128      CanonicalForm tmp2;
     129      newResult.insert (result.getFirst());
     130      result.removeFirst();
     131      for (CFFListIterator i= result; i.hasItem(); i++)
     132      {
     133        tmp2= i.getItem().factor();
     134        for (int j= 1; j <= G.level(); j++)
     135        {
     136          if (substDegree[j-1] > 1)
     137            tmp2= reverseSubst (tmp2, substDegree[j-1], Variable (j));
     138        }
     139        tmp= FpFactorize (tmp2, false);
     140        tmp.removeFirst();
     141        for (CFFListIterator j= tmp; j.hasItem(); j++)
     142          newResult.append (CFFactor (j.getItem().factor(),
     143                                      j.getItem().exp()*i.getItem().exp()));
     144      }
     145      delete [] substDegree;
     146      return newResult;
     147    }
     148    delete [] substDegree;
     149  }
     150
    103151  ExtensionInfo info= ExtensionInfo (false);
    104152  Variable a= Variable (1);
    … …  
    113161  {
    114162    pthRoot= maxpthRoot (pthRoot, p, l);
    115     result= FpFactorize (pthRoot);
     163    result= FpFactorize (pthRoot, false);
    116164    result.removeFirst();
    117165    for (CFFListIterator i= result; i.hasItem(); i++)
    … …  
    128176  if (degree (A) > 0)
    129177  {
    130     resultRoot= FpFactorize (A);
     178    resultRoot= FpFactorize (A, false);
    131179    resultRoot.removeFirst();
    132180    result= Union (result, resultRoot);
    … …  
    142190/// @sa FpFactorize(), GFFactorize()
    143191inline
    144 CFFList FqFactorize (const CanonicalForm& F, ///< [in] a multivariate poly
    145                      const Variable& alpha   ///< [in] algebraic variable
     192CFFList FqFactorize (const CanonicalForm& G, ///< [in] a multivariate poly
     193                     const Variable& alpha,  ///< [in] algebraic variable
     194                     bool substCheck= true   ///< [in] enables substitute check
    146195                    )
    147196{
    148   if (getNumVars (F) == 2)
    149     return FqBiFactorize (F, alpha);
     197  if (getNumVars (G) == 2)
     198    return FqBiFactorize (G, alpha, substCheck);
     199
     200  CanonicalForm F= G;
     201  if (substCheck)
     202  {
     203    bool foundOne= false;
     204    int * substDegree= new int [F.level()];
     205    for (int i= 1; i <= F.level(); i++)
     206    {
     207      if (degree (F, i) > 0)
     208      {
     209        substDegree[i-1]= substituteCheck (F, Variable (i));
     210        if (substDegree [i-1] > 1)
     211        {
     212          foundOne= true;
     213          subst (F, F, substDegree[i-1], Variable (i));
     214        }
     215      }
     216      else
     217        substDegree[i-1]= -1;
     218    }
     219    if (foundOne)
     220    {
     221      CFFList result= FqFactorize (F, alpha, false);
     222      CFFList newResult, tmp;
     223      CanonicalForm tmp2;
     224      newResult.insert (result.getFirst());
     225      result.removeFirst();
     226      for (CFFListIterator i= result; i.hasItem(); i++)
     227      {
     228        tmp2= i.getItem().factor();
     229        for (int j= 1; j <= G.level(); j++)
     230        {
     231          if (substDegree[j-1] > 1)
     232            tmp2= reverseSubst (tmp2, substDegree[j-1], Variable (j));
     233        }
     234        tmp= FqFactorize (tmp2, alpha, false);
     235        tmp.removeFirst();
     236        for (CFFListIterator j= tmp; j.hasItem(); j++)
     237          newResult.append (CFFactor (j.getItem().factor(),
     238                                      j.getItem().exp()*i.getItem().exp()));
     239      }
     240      delete [] substDegree;
     241      return newResult;
     242    }
     243    delete [] substDegree;
     244  }
     245
    150246  ExtensionInfo info= ExtensionInfo (alpha, false);
    151247  CanonicalForm LcF= Lc (F);
    … …  
    160256  {
    161257    pthRoot= maxpthRoot (pthRoot, q, l);
    162     result= FqFactorize (pthRoot, alpha);
     258    result= FqFactorize (pthRoot, alpha, false);
    163259    result.removeFirst();
    164260    for (CFFListIterator i= result; i.hasItem(); i++)
    … …  
    175271  if (degree (A) > 0)
    176272  {
    177     resultRoot= FqFactorize (A, alpha);
     273    resultRoot= FqFactorize (A, alpha, false);
    178274    resultRoot.removeFirst();
    179275    result= Union (result, resultRoot);
    … …  
    189285/// @sa FpFactorize(), FqFactorize()
    190286inline
    191 CFFList GFFactorize (const CanonicalForm& F ///< [in] a multivariate poly
     287CFFList GFFactorize (const CanonicalForm& G, ///< [in] a multivariate poly
     288                     bool substCheck= true   ///< [in] enables substitute check
    192289                    )
    193290{
    194291  ASSERT (CFFactory::gettype() == GaloisFieldDomain,
    195292          "GF as base field expected");
    196   if (getNumVars (F) == 2)
    197     return GFBiFactorize (F);
     293  if (getNumVars (G) == 2)
     294    return GFBiFactorize (G, substCheck);
     295
     296  CanonicalForm F= G;
     297  if (substCheck)
     298  {
     299    bool foundOne= false;
     300    int * substDegree= new int [F.level()];
     301    for (int i= 1; i <= F.level(); i++)
     302    {
     303      if (degree (F, i) > 0)
     304      {
     305        substDegree[i-1]= substituteCheck (F, Variable (i));
     306        if (substDegree [i-1] > 1)
     307        {
     308          foundOne= true;
     309          subst (F, F, substDegree[i-1], Variable (i));
     310        }
     311      }
     312      else
     313        substDegree[i-1]= -1;
     314    }
     315    if (foundOne)
     316    {
     317      CFFList result= GFFactorize (F, false);
     318      CFFList newResult, tmp;
     319      CanonicalForm tmp2;
     320      newResult.insert (result.getFirst());
     321      result.removeFirst();
     322      for (CFFListIterator i= result; i.hasItem(); i++)
     323      {
     324        tmp2= i.getItem().factor();
     325        for (int j= 1; j <= G.level(); j++)
     326        {
     327          if (substDegree[j-1] > 1)
     328            tmp2= reverseSubst (tmp2, substDegree[j-1], Variable (j));
     329        }
     330        tmp= GFFactorize (tmp2, false);
     331        tmp.removeFirst();
     332        for (CFFListIterator j= tmp; j.hasItem(); j++)
     333          newResult.append (CFFactor (j.getItem().factor(),
     334                                      j.getItem().exp()*i.getItem().exp()));
     335      }
     336      delete [] substDegree;
     337      return newResult;
     338    }
     339    delete [] substDegree;
     340  }
     341
    198342  Variable a= Variable (1);
    199343  ExtensionInfo info= ExtensionInfo (getGFDegree(), gf_name, false);
    … …  
    209353  {
    210354    pthRoot= maxpthRoot (pthRoot, q, l);
    211     result= GFFactorize (pthRoot);
     355    result= GFFactorize (pthRoot, false);
    212356    result.removeFirst();
    213357    for (CFFListIterator i= result; i.hasItem(); i++)
    … …  
    224368  if (degree (A) > 0)
    225369  {
    226     resultRoot= GFFactorize (A);
     370    resultRoot= GFFactorize (A, false);
    227371    resultRoot.removeFirst();
    228372    result= Union (result, resultRoot);
Note: See TracChangeset for help on using the changeset viewer.