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 194 of file facFactorize.cc.

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

◆ 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 77 of file facFactorize.h.

81 {
82  if (getNumVars (G) == 2)
83  {
85  return result;
86  }
87  CanonicalForm F= G;
88 
89  if (substCheck)
90  {
91  bool foundOne= false;
92  int * substDegree= new int [F.level()];
93  for (int i= 1; i <= F.level(); i++)
94  {
95  if (degree (F, i) > 0)
96  {
97  substDegree[i-1]= substituteCheck (F, Variable (i));
98  if (substDegree [i-1] > 1)
99  {
100  foundOne= true;
101  subst (F, F, substDegree[i-1], Variable (i));
102  }
103  }
104  else
105  substDegree[i-1]= -1;
106  }
107  if (foundOne)
108  {
109  CFFList result= ratFactorize (F, v, false);
110  CFFList newResult, tmp;
112  newResult.insert (result.getFirst());
113  result.removeFirst();
114  for (CFFListIterator i= result; i.hasItem(); i++)
115  {
116  tmp2= i.getItem().factor();
117  for (int j= 1; j <= G.level(); j++)
118  {
119  if (substDegree[j-1] > 1)
120  tmp2= reverseSubst (tmp2, substDegree[j-1], Variable (j));
121  }
122  tmp= ratFactorize (tmp2, v, false);
123  tmp.removeFirst();
124  for (CFFListIterator j= tmp; j.hasItem(); j++)
125  newResult.append (CFFactor (j.getItem().factor(),
126  j.getItem().exp()*i.getItem().exp()));
127  }
128  delete [] substDegree;
129  return newResult;
130  }
131  delete [] substDegree;
132  }
133 
134  CanonicalForm LcF= Lc (F);
135  if (isOn (SW_RATIONAL))
136  F *= bCommonDen (F);
137 
138  CFFList result;
139  TIMING_START (fac_squarefree);
140  CFFList sqrfFactors= sqrFree (F);
141  TIMING_END_AND_PRINT (fac_squarefree,
142  "time for squarefree factorization over Q: ");
143 
144  CFList tmp;
145  for (CFFListIterator i= sqrfFactors; i.hasItem(); i++)
146  {
147  TIMING_START (fac_factor_squarefree);
148  tmp= ratSqrfFactorize (i.getItem().factor(), v);
149  TIMING_END_AND_PRINT (fac_factor_squarefree,
150  "time to factorize sqrfree factor over Q: ");
151  for (CFListIterator j= tmp; j.hasItem(); j++)
152  {
153  if (j.getItem().inCoeffDomain()) continue;
154  result.append (CFFactor (j.getItem(), i.getItem().exp()));
155  }
156  }
157  if (isOn (SW_RATIONAL))
158  {
159  normalize (result);
160  if (v.level() == 1)
161  {
162  for (CFFListIterator i= result; i.hasItem(); i++)
163  {
164  LcF /= power (bCommonDen (i.getItem().factor()), i.getItem().exp());
165  i.getItem()= CFFactor (i.getItem().factor()*
166  bCommonDen(i.getItem().factor()), i.getItem().exp());
167  }
168  }
169  result.insert (CFFactor (LcF, 1));
170  }
171  return result;
172 }
TIMING_END_AND_PRINT(fac_alg_resultant, "time to compute resultant0: ")
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
int j
Definition: facHensel.cc:105
static poly normalize(poly next_p, ideal add_generators, syStrategy syzstr, int *g_l, int *p_l, int crit_comp)
Definition: syz3.cc:1026
CFFList ratBiFactorize(const CanonicalForm &G, const Variable &v=Variable(1), bool substCheck=true)
factorize a bivariate polynomial over
Definition: facBivar.h:128
CFFList ratFactorize(const CanonicalForm &G, const Variable &v=Variable(1), bool substCheck=true)
factorize a multivariate polynomial over
Definition: facFactorize.h:77
TIMING_START(fac_alg_resultant)
factory&#39;s class for variables
Definition: factory.h:117
factory&#39;s main class
Definition: canonicalform.h:77
CFList ratSqrfFactorize(const CanonicalForm &G, const Variable &v=Variable(1))
factorize a squarefree multivariate polynomial over
Definition: facFactorize.h:53
void insert(const T &)
Definition: ftmpl_list.cc:193
CanonicalForm Lc(const CanonicalForm &f)
CanonicalForm LcF
Definition: facAbsBiFact.cc:51
void removeFirst()
Definition: ftmpl_list.cc:287
CanonicalForm subst(const CanonicalForm &f, const CFList &a, const CFList &b, const CanonicalForm &Rstar, bool isFunctionField)
T getFirst() const
Definition: ftmpl_list.cc:279
int level() const
Definition: factory.h:134
static const int SW_RATIONAL
set to 1 for computations over Q
Definition: cf_defs.h:29
bool isOn(int sw)
switches
int substituteCheck(const CanonicalForm &F, const Variable &x)
check if a substitution x^n->x is possible
int i
Definition: cfEzgcd.cc:125
CFList tmp2
Definition: facFqBivar.cc:70
CanonicalForm bCommonDen(const CanonicalForm &f)
CanonicalForm bCommonDen ( const CanonicalForm & f )
const Variable & v
< [in] a sqrfree bivariate poly
Definition: facBivar.h:37
int getNumVars(const CanonicalForm &f)
int getNumVars ( const CanonicalForm & f )
Definition: cf_ops.cc:314
Factor< CanonicalForm > CFFactor
CanonicalForm reverseSubst(const CanonicalForm &F, const int d, const Variable &x)
reverse a substitution x^d->x
int level() const
level() returns the level of CO.
void append(const T &)
Definition: ftmpl_list.cc:256
int degree(const CanonicalForm &f)
CFFList sqrFree(const CanonicalForm &f, bool sort=false)
squarefree factorization
Definition: cf_factor.cc:757
STATIC_VAR TreeM * G
Definition: janet.cc:31
return result
Definition: facAbsBiFact.cc:76

◆ 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 }
static poly normalize(poly next_p, ideal add_generators, syStrategy syzstr, int *g_l, int *p_l, int crit_comp)
Definition: syz3.cc:1026
factory&#39;s main class
Definition: canonicalform.h:77
void insert(const T &)
Definition: ftmpl_list.cc:193
CanonicalForm Lc(const CanonicalForm &f)
CFList multiFactorize(const CanonicalForm &F, const Variable &v)
Factorization over Q (a)
static const int SW_RATIONAL
set to 1 for computations over Q
Definition: cf_defs.h:29
bool isOn(int sw)
switches
CanonicalForm bCommonDen(const CanonicalForm &f)
CanonicalForm bCommonDen ( const CanonicalForm & f )
int getNumVars(const CanonicalForm &f)
int getNumVars ( const CanonicalForm & f )
Definition: cf_ops.cc:314
CFList ratBiSqrfFactorize(const CanonicalForm &G, const Variable &v=Variable(1))
factorize a squarefree bivariate polynomial over .
Definition: facBivar.h:46
STATIC_VAR TreeM * G
Definition: janet.cc:31
return result
Definition: facAbsBiFact.cc:76

◆ 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 31 of file facFactorize.h.

◆ irred

CFList int bool& irred

[in,out] Is A irreducible?

Definition at line 31 of file facFactorize.h.

◆ minFactorsLength

CFList int& minFactorsLength

[in,out] minimal length of bivariate factors

Definition at line 31 of file facFactorize.h.

◆ w

CFList int bool const Variable& w

<[in] alg. variable

Definition at line 31 of file facFactorize.h.