My Project
Functions | Variables
facFactorize.h File Reference

multivariate factorization over Q(a) More...

#include "timing.h"
#include "facBivar.h"
#include "facFqBivarUtil.h"

Go to the source code of this file.

Functions

 TIMING_DEFINE_PRINT (fac_squarefree) TIMING_DEFINE_PRINT(fac_factor_squarefree) void factorizationWRTDifferentSecondVars(const CanonicalForm &A
 Factorization of A wrt. to different second vars. More...
 
CFList multiFactorize (const CanonicalForm &F, const Variable &v)
 Factorization over Q (a) More...
 
CFList ratSqrfFactorize (const CanonicalForm &G, const Variable &v=Variable(1))
 factorize a squarefree multivariate polynomial over $ Q(\alpha) $ More...
 
CFFList ratFactorize (const CanonicalForm &G, const Variable &v=Variable(1), bool substCheck=true)
 factorize a multivariate polynomial over $ Q(\alpha) $ More...
 

Variables

CFList *& Aeval
 <[in] poly More...
 
CFList int & minFactorsLength
 [in,out] minimal length of bivariate factors More...
 
CFList int bool & irred
 [in,out] Is A irreducible? More...
 
CFList int bool const Variablew
 <[in] alg. variable More...
 

Detailed Description

multivariate factorization over Q(a)

Author
Martin Lee

Definition in file facFactorize.h.

Function Documentation

◆ 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 &)
int degree(const CanonicalForm &f)
CanonicalForm swapvar(const CanonicalForm &, const Variable &, const Variable &)
swapvar() - swap variables x1 and x2 in f.
Definition: cf_ops.cc:168
List< CanonicalForm > CFList
CanonicalForm LC(const CanonicalForm &f)
const CanonicalForm CFMap CFMap & N
Definition: cfEzgcd.cc:56
int l
Definition: cfEzgcd.cc:100
int i
Definition: cfEzgcd.cc:132
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
factory's main class
Definition: canonicalform.h:86
Variable mvar() const
mvar() returns the main variable of CO or Variable() if CO is in a base domain.
bool inCoeffDomain() const
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
T getFirst() const
Definition: ftmpl_list.cc:279
void removeFirst()
Definition: ftmpl_list.cc:287
int length() const
Definition: ftmpl_list.cc:273
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
factory's class for variables
Definition: factory.h:134
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
const CanonicalForm & w
Definition: facAbsFact.cc:51
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
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
if(bad)
CFListIterator iter
Definition: facFactorize.cc:59
Variable x
Definition: facFactorize.cc:50
CFList Evaluation & E
Definition: facFactorize.cc:48
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)
return result
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
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
int j
Definition: facHensel.cc:110
fq_nmod_poly_t prod
Definition: facHensel.cc:100
void sortList(CFList &list, const Variable &x)
sort a list of polynomials by their degree in x.
Definition: facHensel.cc:449
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 CanonicalForm tmin(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
#define A
Definition: sirandom.c:24
static poly normalize(poly next_p, ideal add_generators, syStrategy syzstr, int *g_l, int *p_l, int crit_comp)
Definition: syz3.cc:1026

◆ ratFactorize()

CFFList ratFactorize ( const CanonicalForm G,
const Variable v = Variable (1),
bool  substCheck = true 
)
inline

factorize a multivariate polynomial over $ Q(\alpha) $

Returns
ratFactorize returns a list of monic factors with multiplicity, the first element is the leading coefficient.
Parameters
[in]Ga multivariate poly
[in]valgebraic variable
[in]substCheckenables substitute check

Definition at line 79 of file facFactorize.h.

83 {
84  if (getNumVars (G) == 2)
85  {
87  return result;
88  }
89  CanonicalForm F= G;
90 
91  if (substCheck)
92  {
93  bool foundOne= false;
94  int * substDegree= new int [F.level()];
95  for (int i= 1; i <= F.level(); i++)
96  {
97  if (degree (F, i) > 0)
98  {
99  substDegree[i-1]= substituteCheck (F, Variable (i));
100  if (substDegree [i-1] > 1)
101  {
102  foundOne= true;
103  subst (F, F, substDegree[i-1], Variable (i));
104  }
105  }
106  else
107  substDegree[i-1]= -1;
108  }
109  if (foundOne)
110  {
111  CFFList result= ratFactorize (F, v, false);
112  CFFList newResult, tmp;
114  newResult.insert (result.getFirst());
115  result.removeFirst();
116  for (CFFListIterator i= result; i.hasItem(); i++)
117  {
118  tmp2= i.getItem().factor();
119  for (int j= 1; j <= G.level(); j++)
120  {
121  if (substDegree[j-1] > 1)
122  tmp2= reverseSubst (tmp2, substDegree[j-1], Variable (j));
123  }
124  tmp= ratFactorize (tmp2, v, false);
125  tmp.removeFirst();
126  for (CFFListIterator j= tmp; j.hasItem(); j++)
127  newResult.append (CFFactor (j.getItem().factor(),
128  j.getItem().exp()*i.getItem().exp()));
129  }
130  delete [] substDegree;
131  return newResult;
132  }
133  delete [] substDegree;
134  }
135 
136  CanonicalForm LcF= Lc (F);
137  if (isOn (SW_RATIONAL))
138  F *= bCommonDen (F);
139 
140  CFFList result;
141  TIMING_START (fac_squarefree);
142  CFFList sqrfFactors= sqrFree (F);
143  TIMING_END_AND_PRINT (fac_squarefree,
144  "time for squarefree factorization over Q: ");
145 
146  CFList tmp;
147  for (CFFListIterator i= sqrfFactors; i.hasItem(); i++)
148  {
149  TIMING_START (fac_factor_squarefree);
150  tmp= ratSqrfFactorize (i.getItem().factor(), v);
151  TIMING_END_AND_PRINT (fac_factor_squarefree,
152  "time to factorize sqrfree factor over Q: ");
153  for (CFListIterator j= tmp; j.hasItem(); j++)
154  {
155  if (j.getItem().inCoeffDomain()) continue;
156  result.append (CFFactor (j.getItem(), i.getItem().exp()));
157  }
158  }
159  if (isOn (SW_RATIONAL))
160  {
161  normalize (result);
162  if (v.level() == 1)
163  {
164  for (CFFListIterator i= result; i.hasItem(); i++)
165  {
166  LcF /= power (bCommonDen (i.getItem().factor()), i.getItem().exp());
167  i.getItem()= CFFactor (i.getItem().factor()*
168  bCommonDen(i.getItem().factor()), i.getItem().exp());
169  }
170  }
171  result.insert (CFFactor (LcF, 1));
172  }
173  return result;
174 }
int getNumVars(const CanonicalForm &f)
int getNumVars ( const CanonicalForm & f )
Definition: cf_ops.cc:314
CanonicalForm Lc(const CanonicalForm &f)
Factor< CanonicalForm > CFFactor
CFFList FACTORY_PUBLIC sqrFree(const CanonicalForm &f, bool sort=false)
squarefree factorization
Definition: cf_factor.cc:946
void insert(const T &)
Definition: ftmpl_list.cc:193
CanonicalForm LcF
Definition: facAbsBiFact.cc:50
return result
Definition: facAbsBiFact.cc:75
CanonicalForm subst(const CanonicalForm &f, const CFList &a, const CFList &b, const CanonicalForm &Rstar, bool isFunctionField)
CFFList ratBiFactorize(const CanonicalForm &G, const Variable &v=Variable(1), bool substCheck=true)
factorize a bivariate polynomial over
Definition: facBivar.h:129
CFFList ratFactorize(const CanonicalForm &G, const Variable &v=Variable(1), bool substCheck=true)
factorize a multivariate polynomial over
Definition: facFactorize.h:79
CFList ratSqrfFactorize(const CanonicalForm &G, const Variable &v=Variable(1))
factorize a squarefree multivariate polynomial over
Definition: facFactorize.h:53
CanonicalForm reverseSubst(const CanonicalForm &F, const int d, const Variable &x)
reverse a substitution x^d->x
int substituteCheck(const CanonicalForm &F, const Variable &x)
check if a substitution x^n->x is possible
STATIC_VAR TreeM * G
Definition: janet.cc:31

◆ ratSqrfFactorize()

CFList ratSqrfFactorize ( const CanonicalForm G,
const Variable v = Variable (1) 
)
inline

factorize a squarefree multivariate polynomial over $ Q(\alpha) $

Returns
ratSqrfFactorize returns a list of monic factors, the first element is the leading coefficient.
Parameters
[in]Ga multivariate poly
[in]valgebraic variable

Definition at line 53 of file facFactorize.h.

56 {
57  if (getNumVars (G) == 2)
58  return ratBiSqrfFactorize (G, v);
59  CanonicalForm F= G;
60  if (isOn (SW_RATIONAL))
61  F *= bCommonDen (F);
63  if (isOn (SW_RATIONAL))
64  {
65  normalize (result);
66  result.insert (Lc(F));
67  }
68  return result;
69 }
CFList multiFactorize(const CanonicalForm &F, const Variable &v)
Factorization over Q (a)

◆ TIMING_DEFINE_PRINT()

TIMING_DEFINE_PRINT ( fac_squarefree  ) const &

Factorization of A wrt. to different second vars.

Variable Documentation

◆ Aeval

CFList*& Aeval

<[in] poly

[in,out] A evaluated wrt. different second vars returns bivariate factors

Definition at line 29 of file facFactorize.h.

◆ irred

CFList int bool& irred

[in,out] Is A irreducible?

Definition at line 34 of file facFactorize.h.

◆ minFactorsLength

CFList int& minFactorsLength

[in,out] minimal length of bivariate factors

Definition at line 32 of file facFactorize.h.

◆ w

CFList int bool const Variable& w

<[in] alg. variable

Definition at line 35 of file facFactorize.h.