Changeset 7b5cb2 in git


Ignore:
Timestamp:
Aug 8, 2012, 1:31:30 PM (10 years ago)
Author:
Martin Lee <martinlee84@…>
Branches:
(u'jengelh-datetime', 'ceac47cbc86fe4a15902392bdbb9bd2ae0ea02c6')(u'spielwiese', '96ce329119711a2b80858c8365abd29f8460bbfa')
Children:
8267b8f9ab43170a4026e7e570df48db4601a748
Parents:
97686ecde8614d72ee9d26e96dc9344df8a7da32
git-author:
Martin Lee <martinlee84@web.de>2012-08-08 13:31:30+02:00
git-committer:
Martin Lee <martinlee84@web.de>2012-09-04 18:01:07+02:00
Message:
chg: faster retrieval of terms
chg: LucksWangSparseHeuristic now returns also partial factors
Location:
factory
Files:
2 edited

Legend:

Unmodified
Added
Removed
  • factory/facSparseHensel.cc

    r97686e r7b5cb2  
    2121#include "facFqFactorize.h"
    2222
    23 bool
     23int
    2424LucksWangSparseHeuristic (const CanonicalForm& F, const CFList& factors,
    2525                          int level, const CFList& leadingCoeffs, CFList& result)
     
    6666  delete [] monomsLead;
    6767
    68   CFArray termsF= getTerms (F);
    69   sort (termsF);
     68  CFArray termsF= getBiTerms (F);
     69  if (termsF.size() > 450)
     70  {
     71    delete [] monoms;
     72    return 0;
     73  }
     74  sort (termsF, level);
    7075
    7176  CFList tmp;
     
    8085  CanonicalForm H= prod (tmp);
    8186  CFArray monomsH= getMonoms (H);
    82   sort (monomsH);
    83 
    84   groupTogether (termsF, level);
     87  sort (monomsH,F.level());
     88
    8589  groupTogether (monomsH, F.level());
    8690
     
    8892  {
    8993    delete [] stripped2;
    90     return false;
     94    return 0;
    9195  }
    9296
     
    99103  {
    100104    delete [] stripped2;
    101     return false;
     105    return 0;
    102106  }
    103107
    104108  CFArray A= getEquations (monomsH, termsF);
     109  CFArray startingSolution= solution;
    105110  CFArray newSolution= CFArray (solution.size());
    106111  do
     
    110115      break;
    111116    if (!simplify (A, newSolution, F.level() + 1))
    112     {
    113       delete [] stripped2;
    114       return false;
    115     }
     117      break;
    116118    if (isZero (newSolution))
    117     {
    118       delete [] stripped2;
    119       return false;
    120     }
     119      break;
    121120    if (!merge (solution, newSolution))
    122     {
    123       delete [] stripped2;
    124       return false;
    125     }
     121      break;
    126122  } while (1);
    127123
    128124
    129125  result= CFList();
     126  if (isEqual (startingSolution, solution))
     127  {
     128    delete [] stripped2;
     129    return 0;
     130  }
    130131  CanonicalForm factor;
    131132  num= 0;
     
    135136    factor= 0;
    136137    for (j= 0; j < k; j++, num++)
     138    {
     139      if (solution [num].isZero())
     140        continue;
    137141      factor += solution [num]*stripped2[i][j];
     142    }
    138143    result.append (factor);
    139144  }
    140145
    141146  delete [] stripped2;
    142   return true;
     147  if (result.length() > 0)
     148    return 1;
     149  return 0;
    143150}
    144151
  • factory/facSparseHensel.h

    r97686e r7b5cb2  
    1818#include "cf_iter.h"
    1919#include "templates/ftmpl_functions.h"
     20#include "cf_algorithm.h"
     21#include "cf_map.h"
    2022
    2123/// compare polynomials
     
    8183/// quick sort helper function
    8284inline
    83 void quickSort (int lo, int hi, CFArray& A)
     85void quickSort (int lo, int hi, CFArray& A, int l)
    8486{
    8587  int i= lo, j= hi;
     
    8789  while (i <= j)
    8890  {
    89     while (comp (A [i], tmp) < 0 && i < hi) i++;
    90     while (comp (tmp, A[j]) < 0 && j > lo) j--;
     91    if (l > 0)
     92    {
     93      while (comp (A [i], tmp, l) < 0 && i < hi) i++;
     94      while (comp (tmp, A[j], l) < 0 && j > lo) j--;
     95    }
     96    else
     97    {
     98      while (comp (A [i], tmp) < 0 && i < hi) i++;
     99      while (comp (tmp, A[j]) < 0 && j > lo) j--;
     100    }
    91101    if (i <= j)
    92102    {
     
    96106    }
    97107  }
    98   if (lo < j) quickSort (lo, j, A);
    99   if (i < hi) quickSort (i, hi, A);
     108  if (lo < j) quickSort (lo, j, A, l);
     109  if (i < hi) quickSort (i, hi, A, l);
    100110}
    101111
    102112/// quick sort @a A
    103113inline
    104 void sort (CFArray& A)
    105 {
    106   quickSort (0, A.size() - 1, A);
    107 }
     114void sort (CFArray& A, int l= 0)
     115{
     116  quickSort (0, A.size() - 1, A, l);
     117}
     118
    108119
    109120/// find normalizing factors for @a biFactors and build monic univariate factors
     
    187198}
    188199
     200/// helper function for getBiTerms
     201inline CFArray
     202getBiTerms_helper (const CanonicalForm& F, const CFMap& M)
     203{
     204  CFArray buf= CFArray (size (F));
     205  int k= 0, level= F.level() - 1;
     206  Variable x= F.mvar();
     207  Variable y= Variable (F.level() - 1);
     208  Variable one= Variable (1);
     209  Variable two= Variable (2);
     210  CFIterator j;
     211  for (CFIterator i= F; i.hasTerms(); i++)
     212  {
     213    if (i.coeff().level() < level)
     214    {
     215      buf[k]= M (i.coeff())*power (one,i.exp());
     216      k++;
     217      continue;
     218    }
     219    j= i.coeff();
     220    for (;j.hasTerms(); j++, k++)
     221      buf[k]= power (one,i.exp())*power (two,j.exp())*M (j.coeff());
     222  }
     223  CFArray result= CFArray (k);
     224  for (int i= 0; i < k; i++)
     225    result[i]= buf[i];
     226  return result;
     227}
     228
     229/// get terms of @a F where F is considered a bivariate poly in Variable(1),
     230/// Variable (2)
     231inline CFArray
     232getBiTerms (const CanonicalForm& F)
     233{
     234  if (F.inCoeffDomain())
     235  {
     236    CFArray result= CFArray (1);
     237    result [0]= F;
     238    return result;
     239  }
     240  if (F.isUnivariate())
     241  {
     242    CFArray result= CFArray (size(F));
     243    int j= 0;
     244    for (CFIterator i= F; i.hasTerms(); i++, j++)
     245      result[j]= i.coeff()*power (F.mvar(), i.exp());
     246    return result;
     247  }
     248
     249  CanonicalForm G= F;
     250
     251  CFMap M;
     252  M.newpair (Variable (1), F.mvar());
     253  M.newpair (Variable (2), Variable (F.level() - 1));
     254  G= swapvar (F, Variable (1), F.mvar());
     255  G= swapvar (G, Variable (2), Variable (F.level() - 1));
     256
     257  CFArray result= getBiTerms_helper (G, M);
     258  return result;
     259}
     260
    189261/// build a poly from entries in @a A
    190262inline CanonicalForm
     
    197269}
    198270
    199 /// group together elements in @a A, where entries in @a A are put put together
     271/// group together elements in @a A, where entries in @a A are put together
    200272/// if they coincide up to level @a level
    201273inline void
     
    213285    }
    214286  }
     287  if (A[n].isZero())
     288    k--;
    215289  CFArray B= CFArray (k);
    216290  n++;
     
    509583///
    510584/// @return @a LucksWangSparseHeuristic returns true if it was successful
    511 bool
     585int
    512586LucksWangSparseHeuristic (const CanonicalForm& F,     ///<[in] polynomial to be
    513587                                                      ///< factored
Note: See TracChangeset for help on using the changeset viewer.