My Project
Functions | Variables
facFactorize.cc File Reference

multivariate factorization over Q(a) More...

#include "config.h"
#include "cf_assert.h"
#include "debug.h"
#include "timing.h"
#include "cf_algorithm.h"
#include "facFqFactorizeUtil.h"
#include "facFactorize.h"
#include "facFqFactorize.h"
#include "cf_random.h"
#include "facHensel.h"
#include "cf_map_ext.h"
#include "cf_reval.h"
#include "facSparseHensel.h"
#include "cfUnivarGcd.h"

Go to the source code of this file.

Functions

 TIMING_DEFINE_PRINT (fac_bi_factorizer) TIMING_DEFINE_PRINT(fac_hensel_lift) TIMING_DEFINE_PRINT(fac_factor_recombination) TIMING_DEFINE_PRINT(fac_shift_to_zero) TIMING_DEFINE_PRINT(fac_precompute_leadcoeff) TIMING_DEFINE_PRINT(fac_evaluation) TIMING_DEFINE_PRINT(fac_recover_factors) TIMING_DEFINE_PRINT(fac_preprocess_and_content) TIMING_DEFINE_PRINT(fac_bifactor_total) TIMING_DEFINE_PRINT(fac_luckswang) TIMING_DEFINE_PRINT(fac_lcheuristic) TIMING_DEFINE_PRINT(fac_cleardenom) TIMING_DEFINE_PRINT(fac_content) TIMING_DEFINE_PRINT(fac_compress) CFList evalPoints(const CanonicalForm &F
 
LCFeval insert (LCF)
 
 for (int i=E.max();i >=E.min();i--)
 
 if (bad)
 
 if (degree(eval.getFirst()) !=degree(F, 1))
 
 if (degree(gcd_deriv) > 0)
 
 if (degree(contentx) > 0)
 
 while (!found)
 
 if (!eval.isEmpty()) eval.removeFirst()
 
void factorizationWRTDifferentSecondVars (const CanonicalForm &A, CFList *&Aeval, int &minFactorsLength, bool &irred, const Variable &w)
 
CFList multiFactorize (const CanonicalForm &F, const Variable &v)
 Factorization over Q (a) More...
 

Variables

CFListeval
 
CFList EvaluationE
 
Variable x = Variable (1)
 
CanonicalForm LCF =LC (F,x)
 
CFList LCFeval
 
bool found = false
 
bool allZero = true
 
bool foundZero = false
 
CanonicalForm deriv_x = deriv (eval.getFirst(), x)
 
CanonicalForm gcd_deriv = gcd (eval.getFirst(), deriv_x)
 
CFListIterator iter = eval
 
 do
 
bool bad = false
 
CanonicalForm contentx = content (iter.getItem(), x)
 
return result
 

Detailed Description

multivariate factorization over Q(a)

Author
Martin Lee

Definition in file facFactorize.cc.

Function Documentation

◆ factorizationWRTDifferentSecondVars()

void factorizationWRTDifferentSecondVars ( const CanonicalForm A,
CFList *&  Aeval,
int &  minFactorsLength,
bool &  irred,
const Variable w 
)

Definition at line 158 of file facFactorize.cc.

161 {
162  Variable x= Variable (1);
163  minFactorsLength= 0;
164  irred= false;
165  Variable v;
166  CFList factors;
167  CanonicalForm LCA= LC (A,1);
168  for (int j= 0; j < A.level() - 2; j++)
169  {
170  if (!Aeval[j].isEmpty())
171  {
172  v= Variable (Aeval[j].getFirst().level());
173 
174  factors= ratBiSqrfFactorize (Aeval[j].getFirst(), w);
175  if (factors.getFirst().inCoeffDomain())
176  factors.removeFirst();
177 
178  if (minFactorsLength == 0)
179  minFactorsLength= factors.length();
180  else
182 
183  if (factors.length() == 1)
184  {
185  irred= true;
186  return;
187  }
188  sortList (factors, x);
189  Aeval [j]= factors;
190  }
191  }
192 }
int level(const CanonicalForm &f)
CanonicalForm LC(const CanonicalForm &f)
factory's main class
Definition: canonicalform.h:86
bool inCoeffDomain() const
T getFirst() const
Definition: ftmpl_list.cc:279
void removeFirst()
Definition: ftmpl_list.cc:287
int length() const
Definition: ftmpl_list.cc:273
factory's class for variables
Definition: factory.h:134
const CanonicalForm & w
Definition: facAbsFact.cc:51
CFList ratBiSqrfFactorize(const CanonicalForm &G, const Variable &v=Variable(1))
factorize a squarefree bivariate polynomial over .
Definition: facBivar.h:47
const Variable & v
< [in] a sqrfree bivariate poly
Definition: facBivar.h:39
Variable x
Definition: facFactorize.cc:50
CFList int & minFactorsLength
[in,out] minimal length of bivariate factors
Definition: facFactorize.h:33
CFList *& Aeval
<[in] poly
Definition: facFactorize.h:31
CFList int bool & irred
[in,out] Is A irreducible?
Definition: facFactorize.h:34
int j
Definition: facHensel.cc:110
void sortList(CFList &list, const Variable &x)
sort a list of polynomials by their degree in x.
Definition: facHensel.cc:449
template CanonicalForm tmin(const CanonicalForm &, const CanonicalForm &)
#define A
Definition: sirandom.c:24

◆ for()

for ( int  i = E.max(); i >= E.min(); i--)

Definition at line 65 of file facFactorize.cc.

66  {
67  eval.insert (eval.getFirst()( E [i], i));
68  LCFeval.insert (LCFeval.getFirst() (E [i], i));
69  result.append (E[i]);
70  if (!E[i].isZero())
71  allZero= false;
72  else
73  foundZero= true;
74  if (!allZero && foundZero)
75  {
76  result= CFList();
77  eval= CFList();
78  LCFeval= CFList();
79  bad= true;
80  foundZero= false;
81  break;
82  }
83  if (degree (eval.getFirst(), i - 1) != degree (F, i - 1))
84  {
85  result= CFList();
86  eval= CFList();
87  LCFeval= CFList();
88  bad= true;
89  break;
90  }
91  if ((i != 2) && (degree (LCFeval.getFirst(), i-1) != degree (LCF, i-1)))
92  {
93  result= CFList();
94  eval= CFList();
95  LCFeval= CFList();
96  bad= true;
97  break;
98  }
99  }
int degree(const CanonicalForm &f)
List< CanonicalForm > CFList
int i
Definition: cfEzgcd.cc:132
void insert(const T &)
Definition: ftmpl_list.cc:193
CFList LCFeval
Definition: facFactorize.cc:53
CFList Evaluation & E
Definition: facFactorize.cc:48
CanonicalForm LCF
Definition: facFactorize.cc:52
bool bad
Definition: facFactorize.cc:64
bool allZero
Definition: facFactorize.cc:56
CFList & eval
Definition: facFactorize.cc:47
bool foundZero
Definition: facFactorize.cc:57
return result
bool isZero(const CFArray &A)
checks if entries of A are zero

◆ if() [1/5]

if ( !eval.  isEmpty())

◆ if() [2/5]

if ( bad  )

Definition at line 101 of file facFactorize.cc.

102  {
103  E.nextpoint();
104  continue;
105  }

◆ if() [3/5]

if ( degree(contentx ,
 
)

Definition at line 129 of file facFactorize.cc.

130  {
131  result= CFList();
132  eval= CFList();
133  LCFeval= CFList();
134  E.nextpoint();
135  continue;
136  }

◆ if() [4/5]

if ( degree(eval.getFirst()) !  = degree (F, 1))

Definition at line 107 of file facFactorize.cc.

108  {
109  result= CFList();
110  eval= CFList();
111  LCFeval= CFList();
112  E.nextpoint();
113  continue;
114  }

◆ if() [5/5]

if ( degree(gcd_deriv ,
 
)

Definition at line 118 of file facFactorize.cc.

119  {
120  result= CFList();
121  eval= CFList();
122  LCFeval= CFList();
123  E.nextpoint();
124  continue;
125  }

◆ insert()

LCFeval insert ( LCF  )

◆ multiFactorize()

CFList multiFactorize ( const CanonicalForm F,
const Variable v 
)

Factorization over Q (a)

Returns
multiFactorize returns a factorization of F
Parameters
[in]Fsqrfree poly
[in]vsome algebraic variable

Definition at line 198 of file facFactorize.cc.

199 {
200  if (F.inCoeffDomain())
201  return CFList (F);
202 
203  TIMING_START (fac_preprocess_and_content);
204  // compress and find main Variable
205  CFMap N;
206  TIMING_START (fac_compress)
207  CanonicalForm A= myCompress (F, N);
208  TIMING_END_AND_PRINT (fac_compress, "time to compress poly over Q: ")
209 
210  //univariate case
211  if (F.isUnivariate())
212  {
213  CFList result;
214  if (v.level() != 1)
215  result= conv (factorize (F, v));
216  else
217  result= conv (factorize (F,true));
218  if (result.getFirst().inCoeffDomain())
219  result.removeFirst();
220  return result;
221  }
222 
223  //bivariate case
224  if (A.level() == 2)
225  {
227  if (buf.getFirst().inCoeffDomain())
228  buf.removeFirst();
229  return buf;
230  }
231 
232  Variable x= Variable (1);
233  Variable y= Variable (2);
234 
235  // remove content
236  TIMING_START (fac_content);
237  CFList contentAi;
238  CanonicalForm lcmCont= lcmContent (A, contentAi);
239  A /= lcmCont;
240  TIMING_END_AND_PRINT (fac_content, "time to extract content over Q: ");
241 
242  // trivial after content removal
243  CFList contentAFactors;
244  if (A.inCoeffDomain())
245  {
246  for (CFListIterator i= contentAi; i.hasItem(); i++)
247  {
248  if (i.getItem().inCoeffDomain())
249  continue;
250  else
251  {
252  lcmCont /= i.getItem();
253  contentAFactors=
254  Union (multiFactorize (lcmCont, v),
255  multiFactorize (i.getItem(), v));
256  break;
257  }
258  }
259  decompress (contentAFactors, N);
260  if (isOn (SW_RATIONAL))
261  normalize (contentAFactors);
262  return contentAFactors;
263  }
264 
265  // factorize content
266  TIMING_START (fac_content);
267  contentAFactors= multiFactorize (lcmCont, v);
268  TIMING_END_AND_PRINT (fac_content, "time to factor content over Q: ");
269 
270  // univariate after content removal
271  CFList factors;
272  if (A.isUnivariate ())
273  {
274  if (v.level() != 1)
275  factors= conv (factorize (A, v));
276  else
277  factors= conv (factorize (A,true));
278  append (factors, contentAFactors);
279  decompress (factors, N);
280  return factors;
281  }
282 
283  A *= bCommonDen (A);
284  CFList Aeval, list, evaluation, bufEvaluation, bufAeval;
285  int factorNums= 2;
286  //p is irreducible. But factorize does not recognizes this. However, if you
287  //change factorNums to 2 at line 281 in facFactorize.cc it will. That change
288  //might impair performance in some cases since you do twice as many
289  //bivariate factorizations as before. Otherwise you need to change
290  //precomputeLeadingCoeff to detect these cases and trigger more bivariate
291  // factorizations.
292  // (http://www.singular.uni-kl.de:8002/trac/ticket/666)
293  CFList biFactors, bufBiFactors;
294  CanonicalForm evalPoly;
295  int lift, bufLift, lengthAeval2= A.level()-2;
296  CFList* bufAeval2= new CFList [lengthAeval2];
297  CFList* Aeval2= new CFList [lengthAeval2];
298  int counter;
299  int differentSecondVar= 0;
300  CanonicalForm bufA;
301  TIMING_END_AND_PRINT (fac_preprocess_and_content,
302  "time to preprocess poly and extract content over Q: ");
303 
304  // several bivariate factorizations
305  TIMING_START (fac_bifactor_total);
306  REvaluation E (2, A.level(), IntRandom (25));
307  for (int i= 0; i < factorNums; i++)
308  {
309  counter= 0;
310  bufA= A;
311  bufAeval= CFList();
312  TIMING_START (fac_evaluation);
313  bufEvaluation= evalPoints (bufA, bufAeval, E);
314  TIMING_END_AND_PRINT (fac_evaluation,
315  "time to find evaluation point over Q: ");
316  E.nextpoint();
317  evalPoly= 0;
318 
319  TIMING_START (fac_evaluation);
320  evaluationWRTDifferentSecondVars (bufAeval2, bufEvaluation, A);
321  TIMING_END_AND_PRINT (fac_evaluation,
322  "time to eval wrt diff second vars over Q: ");
323 
324  for (int j= 0; j < lengthAeval2; j++)
325  {
326  if (!bufAeval2[j].isEmpty())
327  counter++;
328  }
329 
330  bufLift= degree (A, y) + 1 + degree (LC(A, x), y);
331 
332  TIMING_START (fac_bi_factorizer);
333  bufBiFactors= ratBiSqrfFactorize (bufAeval.getFirst(), v);
334  TIMING_END_AND_PRINT (fac_bi_factorizer,
335  "time for bivariate factorization: ");
336  bufBiFactors.removeFirst();
337 
338  if (bufBiFactors.length() == 1)
339  {
340  factors.append (A);
341  appendSwapDecompress (factors, contentAFactors, N, 0, 0, x);
342  if (isOn (SW_RATIONAL))
343  normalize (factors);
344  delete [] bufAeval2;
345  delete [] Aeval2;
346  return factors;
347  }
348 
349  if (i == 0)
350  {
351  Aeval= bufAeval;
352  evaluation= bufEvaluation;
353  biFactors= bufBiFactors;
354  lift= bufLift;
355  for (int j= 0; j < lengthAeval2; j++)
356  Aeval2 [j]= bufAeval2 [j];
357  differentSecondVar= counter;
358  }
359  else
360  {
361  if (bufBiFactors.length() < biFactors.length() ||
362  ((bufLift < lift) && (bufBiFactors.length() == biFactors.length())) ||
363  counter > differentSecondVar)
364  {
365  Aeval= bufAeval;
366  evaluation= bufEvaluation;
367  biFactors= bufBiFactors;
368  lift= bufLift;
369  for (int j= 0; j < lengthAeval2; j++)
370  Aeval2 [j]= bufAeval2 [j];
371  differentSecondVar= counter;
372  }
373  }
374  int k= 0;
375  for (CFListIterator j= bufEvaluation; j.hasItem(); j++, k++)
376  evalPoly += j.getItem()*power (x, k);
377  list.append (evalPoly);
378  }
379 
380  delete [] bufAeval2;
381 
382  sortList (biFactors, x);
383 
384  int minFactorsLength;
385  bool irred= false;
386  TIMING_START (fac_bi_factorizer);
388  TIMING_END_AND_PRINT (fac_bi_factorizer,
389  "time for bivariate factorization wrt diff second vars over Q: ");
390 
391  TIMING_END_AND_PRINT (fac_bifactor_total,
392  "total time for eval and bivar factors over Q: ");
393  if (irred)
394  {
395  factors.append (A);
396  appendSwapDecompress (factors, contentAFactors, N, 0, 0, x);
397  if (isOn (SW_RATIONAL))
398  normalize (factors);
399  delete [] Aeval2;
400  return factors;
401  }
402 
403  if (minFactorsLength == 0)
404  minFactorsLength= biFactors.length();
405  else if (biFactors.length() > minFactorsLength)
406  refineBiFactors (A, biFactors, Aeval2, evaluation, minFactorsLength);
408 
409  CFList uniFactors= buildUniFactors (biFactors, evaluation.getLast(), y);
410 
411  sortByUniFactors (Aeval2, lengthAeval2, uniFactors, biFactors, evaluation);
412 
414 
415  if (minFactorsLength == 1)
416  {
417  factors.append (A);
418  appendSwapDecompress (factors, contentAFactors, N, 0, 0, x);
419  if (isOn (SW_RATIONAL))
420  normalize (factors);
421  delete [] Aeval2;
422  return factors;
423  }
424 
425  if (differentSecondVar == lengthAeval2)
426  {
427  bool zeroOccured= false;
429  {
430  if (iter.getItem().isZero())
431  {
432  zeroOccured= true;
433  break;
434  }
435  }
436  if (!zeroOccured)
437  {
438  factors= sparseHeuristic (A, biFactors, Aeval2, evaluation,
440  if (factors.length() == biFactors.length())
441  {
442  appendSwapDecompress (factors, contentAFactors, N, 0, 0, x);
443  normalize (factors);
444  delete [] Aeval2;
445  return factors;
446  }
447  else
448  factors= CFList();
449  //TODO case where factors.length() > 0
450  }
451  }
452 
453  CFList * oldAeval= new CFList [lengthAeval2];
454  for (int i= 0; i < lengthAeval2; i++)
455  oldAeval[i]= Aeval2[i];
456 
457  getLeadingCoeffs (A, Aeval2);
458 
459  CFList biFactorsLCs;
460  for (CFListIterator i= biFactors; i.hasItem(); i++)
461  biFactorsLCs.append (LC (i.getItem(), 1));
462 
463  Variable w;
464  TIMING_START (fac_precompute_leadcoeff);
465  CFList leadingCoeffs= precomputeLeadingCoeff (LC (A, 1), biFactorsLCs, x,
466  evaluation, Aeval2, lengthAeval2, w);
467 
468  if (w.level() != 1)
469  changeSecondVariable (A, biFactors, evaluation, oldAeval, lengthAeval2,
470  uniFactors, w);
471 
472  CanonicalForm oldA= A;
473  CFList oldBiFactors= biFactors;
474 
475  CanonicalForm LCmultiplier= leadingCoeffs.getFirst();
476  bool LCmultiplierIsConst= LCmultiplier.inCoeffDomain();
477  leadingCoeffs.removeFirst();
478 
479  if (!LCmultiplierIsConst)
480  distributeLCmultiplier (A, leadingCoeffs, biFactors, evaluation, LCmultiplier);
481 
482  //prepare leading coefficients
483  CFList* leadingCoeffs2= new CFList [lengthAeval2];
484  prepareLeadingCoeffs (leadingCoeffs2, A, Aeval, A.level(), leadingCoeffs,
485  biFactors, evaluation);
486 
488  CFList bufLeadingCoeffs2= leadingCoeffs2[lengthAeval2-1];
489  bufBiFactors= biFactors;
490  bufA= A;
491  CanonicalForm testVars, bufLCmultiplier= LCmultiplier;
492  if (!LCmultiplierIsConst)
493  {
494  testVars= Variable (2);
495  for (int i= 0; i < lengthAeval2; i++)
496  {
497  if (!oldAeval[i].isEmpty())
498  testVars *= oldAeval[i].getFirst().mvar();
499  }
500  }
501  TIMING_END_AND_PRINT(fac_precompute_leadcoeff,
502  "time to precompute LC over Q: ");
503 
504  TIMING_START (fac_luckswang);
505  CFList bufFactors= CFList();
506  bool LCheuristic= false;
507  if (LucksWangSparseHeuristic (A, biFactors, 2, leadingCoeffs2[lengthAeval2-1],
508  factors))
509  {
510  int check= biFactors.length();
511  int * index= new int [factors.length()];
512  CFList oldFactors= factors;
513  factors= recoverFactors (A, factors, index);
514 
515  if (check == factors.length())
516  {
517  if (w.level() != 1)
518  {
519  for (iter= factors; iter.hasItem(); iter++)
520  iter.getItem()= swapvar (iter.getItem(), w, y);
521  }
522 
523  appendSwapDecompress (factors, contentAFactors, N, 0, 0, x);
524  normalize (factors);
525  delete [] index;
526  delete [] Aeval2;
527  TIMING_END_AND_PRINT (fac_luckswang,
528  "time for successful LucksWang over Q: ");
529  return factors;
530  }
531  else if (factors.length() > 0)
532  {
533  int oneCount= 0;
534  CFList l;
535  for (int i= 0; i < check; i++)
536  {
537  if (index[i] == 1)
538  {
539  iter=biFactors;
540  for (int j=1; j <= i-oneCount; j++)
541  iter++;
542  iter.remove (1);
543  for (int j= 0; j < lengthAeval2; j++)
544  {
545  l= leadingCoeffs2[j];
546  iter= l;
547  for (int k=1; k <= i-oneCount; k++)
548  iter++;
549  iter.remove (1);
550  leadingCoeffs2[j]=l;
551  }
552  oneCount++;
553  }
554  }
555  bufFactors= factors;
556  factors= CFList();
557  }
558  else if (!LCmultiplierIsConst && factors.length() == 0)
559  {
560  LCheuristic= true;
561  factors= oldFactors;
562  CFList contents, LCs;
563  bool foundTrueMultiplier= false;
564  LCHeuristic2 (LCmultiplier, factors, leadingCoeffs2[lengthAeval2-1],
565  contents, LCs, foundTrueMultiplier);
566  if (foundTrueMultiplier)
567  {
568  A= oldA;
569  leadingCoeffs= leadingCoeffs2[lengthAeval2-1];
570  for (int i= lengthAeval2-1; i > -1; i--)
571  leadingCoeffs2[i]= CFList();
572  prepareLeadingCoeffs (leadingCoeffs2, A, Aeval, A.level(),
573  leadingCoeffs, biFactors, evaluation);
574  }
575  else
576  {
577  bool foundMultiplier= false;
578  LCHeuristic3 (LCmultiplier, factors, oldBiFactors, contents, oldAeval,
579  A, leadingCoeffs2, lengthAeval2, foundMultiplier);
580  // coming from above: divide out more LCmultiplier if possible
581  if (foundMultiplier)
582  {
583  foundMultiplier= false;
584  LCHeuristic4 (oldBiFactors, oldAeval, contents, factors, testVars,
585  lengthAeval2, leadingCoeffs2, A, LCmultiplier,
586  foundMultiplier);
587  }
588  else
589  {
590  LCHeuristicCheck (LCs, contents, A, oldA,
591  leadingCoeffs2[lengthAeval2-1], foundMultiplier);
592  if (!foundMultiplier && fdivides (getVars (LCmultiplier), testVars))
593  {
594  LCHeuristic (A, LCmultiplier, biFactors, leadingCoeffs2, oldAeval,
595  lengthAeval2, evaluation, oldBiFactors);
596  }
597  }
598 
599  // patch everything together again
600  leadingCoeffs= leadingCoeffs2[lengthAeval2-1];
601  for (int i= lengthAeval2-1; i > -1; i--)
602  leadingCoeffs2[i]= CFList();
603  prepareLeadingCoeffs (leadingCoeffs2, A, Aeval, A.level(),leadingCoeffs,
604  biFactors, evaluation);
605  }
606  factors= CFList();
607  if (!fdivides (LC (oldA,1),prod (leadingCoeffs2[lengthAeval2-1])))
608  {
609  LCheuristic= false;
610  A= bufA;
611  biFactors= bufBiFactors;
612  leadingCoeffs2[lengthAeval2-1]= bufLeadingCoeffs2;
613  LCmultiplier= bufLCmultiplier;
614  }
615  }
616  else
617  factors= CFList();
618  delete [] index;
619  }
620  TIMING_END_AND_PRINT (fac_luckswang, "time for LucksWang over Q: ");
621 
622  TIMING_START (fac_lcheuristic);
623  if (!LCheuristic && !LCmultiplierIsConst && bufFactors.isEmpty()
624  && fdivides (getVars (LCmultiplier), testVars))
625  {
626  LCheuristic= true;
627  LCHeuristic (A, LCmultiplier, biFactors, leadingCoeffs2, oldAeval,
628  lengthAeval2, evaluation, oldBiFactors);
629 
630  leadingCoeffs= leadingCoeffs2[lengthAeval2-1];
631  for (int i= lengthAeval2-1; i > -1; i--)
632  leadingCoeffs2[i]= CFList();
633  prepareLeadingCoeffs (leadingCoeffs2, A, Aeval, A.level(),leadingCoeffs,
634  biFactors, evaluation);
635 
636  if (!fdivides (LC (oldA,1),prod (leadingCoeffs2[lengthAeval2-1])))
637  {
638  LCheuristic= false;
639  A= bufA;
640  biFactors= bufBiFactors;
641  leadingCoeffs2[lengthAeval2-1]= bufLeadingCoeffs2;
642  LCmultiplier= bufLCmultiplier;
643  }
644  }
645  TIMING_END_AND_PRINT (fac_lcheuristic, "time for Lc heuristic over Q: ");
646 
647 tryAgainWithoutHeu:
648  //shifting to zero
649  TIMING_START (fac_shift_to_zero);
650  CanonicalForm denA= bCommonDen (A);
651  A *= denA;
653  A /= denA;
654 
655  for (iter= biFactors; iter.hasItem(); iter++)
656  iter.getItem()= iter.getItem () (y + evaluation.getLast(), y);
657 
658  for (int i= 0; i < lengthAeval2-1; i++)
659  leadingCoeffs2[i]= CFList();
660  for (iter= leadingCoeffs2[lengthAeval2-1]; iter.hasItem(); iter++)
661  {
663  for (int i= A.level() - 4; i > -1; i--)
664  {
665  if (i + 1 == lengthAeval2-1)
666  leadingCoeffs2[i].append (iter.getItem() (0, i + 4));
667  else
668  leadingCoeffs2[i].append (leadingCoeffs2[i+1].getLast() (0, i + 4));
669  }
670  }
671  TIMING_END_AND_PRINT (fac_shift_to_zero,
672  "time to shift evaluation point to zero: ");
673 
674  CFArray Pi;
675  CFList diophant;
676  int* liftBounds= new int [A.level() - 1];
677  int liftBoundsLength= A.level() - 1;
678  for (int i= 0; i < liftBoundsLength; i++)
679  liftBounds [i]= degree (A, i + 2) + 1;
680 
681  Aeval.removeFirst();
682  bool noOneToOne= false;
683 
684  TIMING_START (fac_cleardenom);
685  CFList commonDenominators;
686  for (iter=biFactors; iter.hasItem(); iter++)
687  commonDenominators.append (bCommonDen (iter.getItem()));
688  CanonicalForm tmp1, tmp2, tmp3=1;
689  CFListIterator iter2;
690  for (int i= 0; i < lengthAeval2; i++)
691  {
692  iter2= commonDenominators;
693  for (iter= leadingCoeffs2[i]; iter.hasItem(); iter++, iter2++)
694  {
696  Off (SW_RATIONAL);
697  iter2.getItem()= lcm (iter2.getItem(), tmp1);
698  On (SW_RATIONAL);
699  }
700  }
701  tmp1= prod (commonDenominators);
702  for (iter= Aeval; iter.hasItem(); iter++)
703  {
704  tmp2= bCommonDen (iter.getItem()/denA);
705  Off (SW_RATIONAL);
706  tmp3= lcm (tmp2,tmp3);
707  On (SW_RATIONAL);
708  }
709  CanonicalForm multiplier;
710  multiplier= tmp3/tmp1;
711  iter2= commonDenominators;
712  for (iter=biFactors; iter.hasItem(); iter++, iter2++)
713  iter.getItem() *= iter2.getItem()*multiplier;
714 
715  for (iter= Aeval; iter.hasItem(); iter++)
716  iter.getItem() *= tmp3*power (multiplier, biFactors.length() - 1)/denA;
717 
718  for (int i= 0; i < lengthAeval2; i++)
719  {
720  iter2= commonDenominators;
721  for (iter= leadingCoeffs2[i]; iter.hasItem(); iter++, iter2++)
722  iter.getItem() *= iter2.getItem()*multiplier;
723  }
724  TIMING_END_AND_PRINT (fac_cleardenom, "time to clear denominators: ");
725 
726  TIMING_START (fac_hensel_lift);
727  factors= nonMonicHenselLift (Aeval, biFactors, leadingCoeffs2, diophant,
728  Pi, liftBounds, liftBoundsLength, noOneToOne);
729  TIMING_END_AND_PRINT (fac_hensel_lift,
730  "time for non monic hensel lifting over Q: ");
731 
732  if (!noOneToOne)
733  {
734  int check= factors.length();
735  A= oldA;
736  TIMING_START (fac_recover_factors);
737  factors= recoverFactors (A, factors, evaluation);
738  TIMING_END_AND_PRINT (fac_recover_factors,
739  "time to recover factors over Q: ");
740  if (check != factors.length())
741  noOneToOne= true;
742  else
743  factors= Union (factors, bufFactors);
744  }
745  if (noOneToOne)
746  {
747  if (!LCmultiplierIsConst && LCheuristic)
748  {
749  A= bufA;
750  biFactors= bufBiFactors;
751  leadingCoeffs2[lengthAeval2-1]= bufLeadingCoeffs2;
752  delete [] liftBounds;
753  LCheuristic= false;
754  goto tryAgainWithoutHeu;
755  //something probably went wrong in the heuristic
756  }
757 
758  A= shift2Zero (oldA, Aeval, evaluation);
759  biFactors= oldBiFactors;
760  for (iter= biFactors; iter.hasItem(); iter++)
761  iter.getItem()= iter.getItem () (y + evaluation.getLast(), y);
762  CanonicalForm LCA= LC (Aeval.getFirst(), 1);
763  CanonicalForm yToLift= power (y, lift);
764  CFListIterator i= biFactors;
765  lift= degree (i.getItem(), 2) + degree (LC (i.getItem(), 1)) + 1;
766  i++;
767 
768  for (; i.hasItem(); i++)
769  lift= tmax (lift, degree (i.getItem(), 2)+degree (LC (i.getItem(), 1))+1);
770 
771  lift= tmax (degree (Aeval.getFirst() , 2) + 1, lift);
772 
773  i= biFactors;
774  yToLift= power (y, lift);
775  CanonicalForm dummy;
776  for (; i.hasItem(); i++)
777  {
778  LCA= LC (i.getItem(), 1);
779  extgcd (LCA, yToLift, LCA, dummy);
780  i.getItem()= mod (i.getItem()*LCA, yToLift);
781  }
782 
783  liftBoundsLength= F.level() - 1;
784  liftBounds= liftingBounds (A, lift);
785 
786  CFList MOD;
787  bool earlySuccess;
788  CFList earlyFactors;
790  CFList liftedFactors;
791  TIMING_START (fac_hensel_lift);
792  liftedFactors= henselLiftAndEarly
793  (A, MOD, liftBounds, earlySuccess, earlyFactors,
794  Aeval, biFactors, evaluation, info);
795  TIMING_END_AND_PRINT (fac_hensel_lift, "time for hensel lifting: ");
796 
797  TIMING_START (fac_factor_recombination);
798  factors= factorRecombination (A, liftedFactors, MOD);
799  TIMING_END_AND_PRINT (fac_factor_recombination,
800  "time for factor recombination: ");
801 
802  if (earlySuccess)
803  factors= Union (factors, earlyFactors);
804 
805  for (CFListIterator i= factors; i.hasItem(); i++)
806  {
807  int kk= Aeval.getLast().level();
808  for (CFListIterator j= evaluation; j.hasItem(); j++, kk--)
809  {
810  if (i.getItem().level() < kk)
811  continue;
812  i.getItem()= i.getItem() (Variable (kk) - j.getItem(), kk);
813  }
814  }
815  }
816 
817  if (w.level() != 1)
818  {
819  for (CFListIterator iter= factors; iter.hasItem(); iter++)
820  iter.getItem()= swapvar (iter.getItem(), w, y);
821  }
822 
823  append (factors, contentAFactors);
824  decompress (factors, N);
825  if (isOn (SW_RATIONAL))
826  normalize (factors);
827 
828  delete [] leadingCoeffs2;
829  delete [] oldAeval;
830  delete [] Aeval2;
831  delete[] liftBounds;
832 
833  return factors;
834 }
bool isOn(int sw)
switches
void On(int sw)
switches
void Off(int sw)
switches
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
CanonicalForm getVars(const CanonicalForm &f)
CanonicalForm getVars ( const CanonicalForm & f )
Definition: cf_ops.cc:350
CF_NO_INLINE FACTORY_PUBLIC CanonicalForm mod(const CanonicalForm &, const CanonicalForm &)
CanonicalForm swapvar(const CanonicalForm &, const Variable &, const Variable &)
swapvar() - swap variables x1 and x2 in f.
Definition: cf_ops.cc:168
const CanonicalForm CFMap CFMap & N
Definition: cfEzgcd.cc:56
int l
Definition: cfEzgcd.cc:100
int k
Definition: cfEzgcd.cc:99
int myCompress(const CanonicalForm &F, const CanonicalForm &G, CFMap &M, CFMap &N, bool topLevel)
compressing two polynomials F and G, M is used for compressing, N to reverse the compression
Definition: cfModGcd.cc:93
CanonicalForm decompress(const CanonicalForm &F, const mpz_t *inverseM, const mpz_t *A)
decompress a bivariate poly
CanonicalForm extgcd(const CanonicalForm &f, const CanonicalForm &g, CanonicalForm &a, CanonicalForm &b)
CanonicalForm extgcd ( const CanonicalForm & f, const CanonicalForm & g, CanonicalForm & a,...
Definition: cfUnivarGcd.cc:174
CanonicalForm bCommonDen(const CanonicalForm &f)
CanonicalForm bCommonDen ( const CanonicalForm & f )
bool fdivides(const CanonicalForm &f, const CanonicalForm &g)
bool fdivides ( const CanonicalForm & f, const CanonicalForm & g )
CFFList FACTORY_PUBLIC factorize(const CanonicalForm &f, bool issqrfree=false)
factorization over or
Definition: cf_factor.cc:405
static const int SW_RATIONAL
set to 1 for computations over Q
Definition: cf_defs.h:30
class CFMap
Definition: cf_map.h:85
Variable mvar() const
mvar() returns the main variable of CO or Variable() if CO is in a base domain.
int level() const
level() returns the level of CO.
ExtensionInfo contains information about extension.
Definition: ExtensionInfo.h:51
generate random integers
Definition: cf_random.h:56
void remove(int moveright)
Definition: ftmpl_list.cc:526
T & getItem() const
Definition: ftmpl_list.cc:431
void append(const T &)
Definition: ftmpl_list.cc:256
T getLast() const
Definition: ftmpl_list.cc:309
int isEmpty() const
Definition: ftmpl_list.cc:267
class to generate random evaluation points
Definition: cf_reval.h:26
int level() const
Definition: factory.h:150
const CanonicalForm int const CFList & evaluation
Definition: facAbsFact.cc:52
const CanonicalForm int const CFList const Variable & y
Definition: facAbsFact.cc:53
TIMING_END_AND_PRINT(fac_alg_resultant, "time to compute resultant0: ")
TIMING_START(fac_alg_resultant)
CFFList append(const CFFList &Inputlist, const CFFactor &TheFactor)
CFList conv(const CFFList &L)
convert a CFFList to a CFList by dropping the multiplicity
Definition: facBivar.cc:126
if(bad)
CFListIterator iter
Definition: facFactorize.cc:59
CFList multiFactorize(const CanonicalForm &F, const Variable &v)
Factorization over Q (a)
void factorizationWRTDifferentSecondVars(const CanonicalForm &A, CFList *&Aeval, int &minFactorsLength, bool &irred, const Variable &w)
void appendSwapDecompress(CFList &factors1, const CFList &factors2, const CFList &factors3, const bool swap1, const bool swap2, const CFMap &N)
first swap Variables in factors1 if necessary, then append factors2 and factors3 on factors1 and fina...
else L getLast()(0
CFList tmp1
Definition: facFqBivar.cc:72
CFList tmp2
Definition: facFqBivar.cc:72
CFList henselLiftAndEarly(CanonicalForm &A, bool &earlySuccess, CFList &earlyFactors, DegreePattern &degs, int &liftBound, const CFList &uniFactors, const ExtensionInfo &info, const CanonicalForm &eval, modpk &b, CanonicalForm &den)
hensel Lifting and early factor detection
Definition: facFqBivar.cc:1152
CFList factorRecombination(CFList &factors, CanonicalForm &F, const CanonicalForm &N, DegreePattern &degs, const CanonicalForm &eval, int s, int thres, const modpk &b, const CanonicalForm &den)
naive factor recombination as decribed in "Factoring multivariate polynomials over a finite field" by...
Definition: facFqBivar.cc:586
CFList recoverFactors(const CanonicalForm &F, const CFList &factors)
divides factors by their content wrt. Variable(1) and checks if these polys divide F
CanonicalForm shift2Zero(const CanonicalForm &F, CFList &Feval, const CFList &evaluation, int l)
shift evaluation point to zero
int * liftingBounds(const CanonicalForm &A, const int &bivarLiftBound)
compute lifting bounds
CFList precomputeLeadingCoeff(const CanonicalForm &LCF, const CFList &LCFFactors, const Variable &alpha, const CFList &evaluation, CFList *&differentSecondVarLCs, int lSecondVarLCs, Variable &y)
computes a list l of length length(LCFFactors)+1 of polynomials such that prod (l)=LCF,...
void LCHeuristicCheck(const CFList &LCs, const CFList &contents, CanonicalForm &A, const CanonicalForm &oldA, CFList &leadingCoeffs, bool &foundTrueMultiplier)
checks if prod(LCs)==LC (oldA,1) and if so divides elements of leadingCoeffs by elements in contents,...
void distributeLCmultiplier(CanonicalForm &A, CFList &leadingCoeffs, CFList &biFactors, const CFList &evaluation, const CanonicalForm &LCmultipler)
distributes a divisor LCmultiplier of LC(A,1) on the bivariate factors and the precomputed leading co...
void evaluationWRTDifferentSecondVars(CFList *&Aeval, const CFList &evaluation, const CanonicalForm &A)
evaluate a poly A with main variable at level 1 at an evaluation point in K^(n-1) wrt different secon...
void prepareLeadingCoeffs(CFList *&LCs, CanonicalForm &A, CFList &Aeval, int n, const CFList &leadingCoeffs, const CFList &biFactors, const CFList &evaluation)
normalize precomputed leading coefficients such that leading coefficients evaluated at evaluation in ...
void LCHeuristic4(const CFList &oldBiFactors, const CFList *oldAeval, const CFList &contents, const CFList &factors, const CanonicalForm &testVars, int lengthAeval, CFList *&leadingCoeffs, CanonicalForm &A, CanonicalForm &LCmultiplier, bool &foundMultiplier)
heuristic to remove factors of LCmultiplier from factors. More precisely checks if elements of conten...
void changeSecondVariable(CanonicalForm &A, CFList &biFactors, CFList &evaluation, CFList *&oldAeval, int lengthAeval2, const CFList &uniFactors, const Variable &w)
changes the second variable to be w and updates all relevant data
void sortByUniFactors(CFList *&Aeval, int AevalLength, CFList &uniFactors, CFList &biFactors, const CFList &evaluation)
sort bivariate factors in Aeval such that their corresponding univariate factors coincide with uniFac...
CanonicalForm lcmContent(const CanonicalForm &A, CFList &contentAi)
compute the LCM of the contents of A wrt to each variable occuring in A.
void getLeadingCoeffs(const CanonicalForm &A, CFList *&Aeval)
extract leading coefficients wrt Variable(1) from bivariate factors obtained from factorizations of A...
void LCHeuristic3(const CanonicalForm &LCmultiplier, const CFList &factors, const CFList &oldBiFactors, const CFList &contents, const CFList *oldAeval, CanonicalForm &A, CFList *&leadingCoeffs, int lengthAeval, bool &foundMultiplier)
heuristic to remove LCmultiplier from a factor based on the contents of factors. factors are assumed ...
void LCHeuristic(CanonicalForm &A, const CanonicalForm &LCmultiplier, CFList &biFactors, CFList *&leadingCoeffs, const CFList *oldAeval, int lengthAeval, const CFList &evaluation, const CFList &oldBiFactors)
heuristic to distribute LCmultiplier onto factors based on the variables that occur in LCmultiplier a...
void refineBiFactors(const CanonicalForm &A, CFList &biFactors, CFList *const &Aeval, const CFList &evaluation, int minFactorsLength)
refine a bivariate factorization of A with l factors to one with minFactorsLength if possible
void LCHeuristic2(const CanonicalForm &LCmultiplier, const CFList &factors, CFList &leadingCoeffs, CFList &contents, CFList &LCs, bool &foundTrueMultiplier)
heuristic to distribute LCmultiplier onto factors based on the contents of factors....
CFList buildUniFactors(const CFList &biFactors, const CanonicalForm &evalPoint, const Variable &y)
plug in evalPoint for y in a list of polys
CFList evalPoints(const CanonicalForm &F, CFList &eval, const Variable &alpha, CFList &list, const bool &GF, bool &fail)
evaluation point search for multivariate factorization, looks for a (F.level() - 1)-tuple such that t...
const ExtensionInfo & info
< [in] sqrfree poly
CFList nonMonicHenselLift(const CFList &F, const CFList &factors, const CFList &LCs, CFList &diophant, CFArray &Pi, CFMatrix &M, int lOld, int &lNew, const CFList &MOD, bool &noOneToOne)
Definition: facHensel.cc:2853
fq_nmod_poly_t prod
Definition: facHensel.cc:100
int LucksWangSparseHeuristic(const CanonicalForm &F, const CFList &factors, int level, const CFList &leadingCoeffs, CFList &result)
sparse heuristic lifting by Wang and Lucks
CFList sparseHeuristic(const CanonicalForm &A, const CFList &biFactors, CFList *&moreBiFactors, const CFList &evaluation, int minFactorsLength)
sparse heuristic which patches together bivariate factors of A wrt. different second variables by the...
template CanonicalForm tmax(const CanonicalForm &, const CanonicalForm &)
template List< Variable > Union(const List< Variable > &, const List< Variable > &)
VAR int check
Definition: libparse.cc:1106
ideal lift(const ideal J, const ring r, const ideal inI, const ring s)
Definition: lift.cc:26
int lcm(unsigned long *l, unsigned long *a, unsigned long *b, unsigned long p, int dega, int degb)
Definition: minpoly.cc:709
static int index(p_Length length, p_Ord ord)
Definition: p_Procs_Impl.h:592
int status int void * buf
Definition: si_signals.h:59
static poly normalize(poly next_p, ideal add_generators, syStrategy syzstr, int *g_l, int *p_l, int crit_comp)
Definition: syz3.cc:1026

◆ TIMING_DEFINE_PRINT()

TIMING_DEFINE_PRINT ( fac_bi_factorizer  ) const &

◆ while()

while ( found)

Variable Documentation

◆ allZero

bool allZero = true

Definition at line 56 of file facFactorize.cc.

◆ bad

bool bad = false

Definition at line 64 of file facFactorize.cc.

◆ contentx

contentx = content (iter.getItem(), x)

Definition at line 128 of file facFactorize.cc.

◆ deriv_x

deriv_x = deriv (eval.getFirst(), x)

Definition at line 58 of file facFactorize.cc.

◆ do

do
Initial value:
{

Definition at line 60 of file facFactorize.cc.

◆ E

Initial value:

Definition at line 47 of file facFactorize.cc.

◆ eval

CFList& eval

Definition at line 47 of file facFactorize.cc.

◆ found

found = false

Definition at line 55 of file facFactorize.cc.

◆ foundZero

bool foundZero = false

Definition at line 57 of file facFactorize.cc.

◆ gcd_deriv

gcd_deriv = gcd (eval.getFirst(), deriv_x)

Definition at line 58 of file facFactorize.cc.

◆ iter

iter = eval

Definition at line 59 of file facFactorize.cc.

◆ LCF

CanonicalForm LCF =LC (F,x)

Definition at line 52 of file facFactorize.cc.

◆ LCFeval

CFList LCFeval

Definition at line 53 of file facFactorize.cc.

◆ result

return result

Definition at line 152 of file facFactorize.cc.

◆ x

Variable x = Variable (1)

Definition at line 50 of file facFactorize.cc.