Changeset 7b5cb2 in git for factory/facSparseHensel.h


Ignore:
Timestamp:
Aug 8, 2012, 1:31:30 PM (10 years ago)
Author:
Martin Lee <martinlee84@…>
Branches:
(u'jengelh-datetime', 'ceac47cbc86fe4a15902392bdbb9bd2ae0ea02c6')(u'spielwiese', 'ad2543eab51733612ba7d118afc77edca719600e')
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
File:
1 edited

Legend:

Unmodified
Added
Removed
  • 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.