My Project
Loading...
Searching...
No Matches
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.
 
CFList multiFactorize (const CanonicalForm &F, const Variable &v)
 Factorization over Q (a)
 
CFList ratSqrfFactorize (const CanonicalForm &G, const Variable &v=Variable(1))
 factorize a squarefree multivariate polynomial over $ Q(\alpha) $
 
CFFList ratFactorize (const CanonicalForm &G, const Variable &v=Variable(1), bool substCheck=true)
 factorize a multivariate polynomial over $ Q(\alpha) $
 

Variables

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

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
204 // compress and find main Variable
205 CFMap N;
208 TIMING_END_AND_PRINT (fac_compress, "time to compress poly over Q: ")
209
210 //univariate case
211 if (F.isUnivariate())
212 {
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())
229 return buf;
230 }
231
232 Variable x= Variable (1);
233 Variable y= Variable (2);
234
235 // remove content
239 A /= lcmCont;
240 TIMING_END_AND_PRINT (fac_content, "time to extract content over Q: ");
241
242 // trivial after content removal
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();
255 multiFactorize (i.getItem(), v));
256 break;
257 }
258 }
260 if (isOn (SW_RATIONAL))
262 return contentAFactors;
263 }
264
265 // factorize content
268 TIMING_END_AND_PRINT (fac_content, "time to factor content over Q: ");
269
270 // univariate after content removal
272 if (A.isUnivariate ())
273 {
274 if (v.level() != 1)
275 factors= conv (factorize (A, v));
276 else
277 factors= conv (factorize (A,true));
280 return factors;
281 }
282
283 A *= bCommonDen (A);
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)
295 int lift, bufLift, lengthAeval2= A.level()-2;
298 int counter;
299 int differentSecondVar= 0;
302 "time to preprocess poly and extract content over Q: ");
303
304 // several bivariate factorizations
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();
315 "time to find evaluation point over Q: ");
316 E.nextpoint();
317 evalPoly= 0;
318
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
335 "time for bivariate factorization: ");
337
338 if (bufBiFactors.length() == 1)
339 {
340 factors.append (A);
342 if (isOn (SW_RATIONAL))
344 delete [] bufAeval2;
345 delete [] Aeval2;
346 return factors;
347 }
348
349 if (i == 0)
350 {
354 lift= bufLift;
355 for (int j= 0; j < lengthAeval2; j++)
356 Aeval2 [j]= bufAeval2 [j];
357 differentSecondVar= counter;
358 }
359 else
360 {
362 ((bufLift < lift) && (bufBiFactors.length() == biFactors.length())) ||
363 counter > differentSecondVar)
364 {
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
383
385 bool irred= false;
389 "time for bivariate factorization wrt diff second vars over Q: ");
390
392 "total time for eval and bivar factors over Q: ");
393 if (irred)
394 {
395 factors.append (A);
397 if (isOn (SW_RATIONAL))
399 delete [] Aeval2;
400 return factors;
401 }
402
403 if (minFactorsLength == 0)
405 else if (biFactors.length() > minFactorsLength)
408
410
412
414
415 if (minFactorsLength == 1)
416 {
417 factors.append (A);
419 if (isOn (SW_RATIONAL))
421 delete [] Aeval2;
422 return factors;
423 }
424
426 {
427 bool zeroOccured= false;
429 {
430 if (iter.getItem().isZero())
431 {
432 zeroOccured= true;
433 break;
434 }
435 }
436 if (!zeroOccured)
437 {
440 if (factors.length() == biFactors.length())
441 {
444 delete [] Aeval2;
445 return factors;
446 }
447 else
448 factors= CFList();
449 //TODO case where factors.length() > 0
450 }
451 }
452
454 for (int i= 0; i < lengthAeval2; i++)
455 oldAeval[i]= Aeval2[i];
456
458
460 for (CFListIterator i= biFactors; i.hasItem(); i++)
461 biFactorsLCs.append (LC (i.getItem(), 1));
462
463 Variable w;
467
468 if (w.level() != 1)
470 uniFactors, w);
471
474
476 bool LCmultiplierIsConst= LCmultiplier.inCoeffDomain();
478
481
482 //prepare leading coefficients
486
490 bufA= A;
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 }
502 "time to precompute LC over Q: ");
503
506 bool LCheuristic= false;
508 factors))
509 {
510 int check= biFactors.length();
511 int * index= new int [factors.length()];
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
525 delete [] index;
526 delete [] Aeval2;
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 {
540 for (int j=1; j <= i-oneCount; j++)
541 iter++;
542 iter.remove (1);
543 for (int j= 0; j < lengthAeval2; j++)
544 {
546 iter= l;
547 for (int k=1; k <= i-oneCount; k++)
548 iter++;
549 iter.remove (1);
551 }
552 oneCount++;
553 }
554 }
556 factors= CFList();
557 }
558 else if (!LCmultiplierIsConst && factors.length() == 0)
559 {
560 LCheuristic= true;
563 bool foundTrueMultiplier= false;
567 {
568 A= oldA;
570 for (int i= lengthAeval2-1; i > -1; i--)
574 }
575 else
576 {
577 bool foundMultiplier= false;
580 // coming from above: divide out more LCmultiplier if possible
581 if (foundMultiplier)
582 {
583 foundMultiplier= false;
587 }
588 else
589 {
593 {
596 }
597 }
598
599 // patch everything together again
601 for (int i= lengthAeval2-1; i > -1; i--)
605 }
606 factors= CFList();
608 {
609 LCheuristic= false;
610 A= bufA;
614 }
615 }
616 else
617 factors= CFList();
618 delete [] index;
619 }
620 TIMING_END_AND_PRINT (fac_luckswang, "time for LucksWang over Q: ");
621
625 {
626 LCheuristic= true;
629
631 for (int i= lengthAeval2-1; i > -1; i--)
635
637 {
638 LCheuristic= false;
639 A= bufA;
643 }
644 }
645 TIMING_END_AND_PRINT (fac_lcheuristic, "time for Lc heuristic over Q: ");
646
648 //shifting to zero
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++)
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
669 }
670 }
672 "time to shift evaluation point to zero: ");
673
674 CFArray Pi;
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
682 bool noOneToOne= false;
683
686 for (iter=biFactors; iter.hasItem(); iter++)
690 for (int i= 0; i < lengthAeval2; i++)
691 {
693 for (iter= leadingCoeffs2[i]; iter.hasItem(); iter++, iter2++)
694 {
697 iter2.getItem()= lcm (iter2.getItem(), tmp1);
698 On (SW_RATIONAL);
699 }
700 }
702 for (iter= Aeval; iter.hasItem(); iter++)
703 {
706 tmp3= lcm (tmp2,tmp3);
707 On (SW_RATIONAL);
708 }
712 for (iter=biFactors; iter.hasItem(); iter++, iter2++)
713 iter.getItem() *= iter2.getItem()*multiplier;
714
715 for (iter= Aeval; iter.hasItem(); iter++)
717
718 for (int i= 0; i < lengthAeval2; i++)
719 {
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
730 "time for non monic hensel lifting over Q: ");
731
732 if (!noOneToOne)
733 {
734 int check= factors.length();
735 A= oldA;
739 "time to recover factors over Q: ");
740 if (check != factors.length())
741 noOneToOne= true;
742 else
744 }
745 if (noOneToOne)
746 {
748 {
749 A= bufA;
752 delete [] liftBounds;
753 LCheuristic= false;
755 //something probably went wrong in the heuristic
756 }
757
760 for (iter= biFactors; iter.hasItem(); iter++)
761 iter.getItem()= iter.getItem () (y + evaluation.getLast(), y);
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);
776 for (; i.hasItem(); i++)
777 {
778 LCA= LC (i.getItem(), 1);
780 i.getItem()= mod (i.getItem()*LCA, yToLift);
781 }
782
783 liftBoundsLength= F.level() - 1;
785
786 CFList MOD;
787 bool earlySuccess;
795 TIMING_END_AND_PRINT (fac_hensel_lift, "time for hensel lifting: ");
796
800 "time for factor recombination: ");
801
802 if (earlySuccess)
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 {
820 iter.getItem()= swapvar (iter.getItem(), w, y);
821 }
822
825 if (isOn (SW_RATIONAL))
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 FACTORY_PUBLIC 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:92
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,...
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:409
static const int SW_RATIONAL
set to 1 for computations over Q
Definition cf_defs.h:31
class CFMap
Definition cf_map.h:85
factory's main class
bool inCoeffDomain() const
int level() const
level() returns the level of CO.
ExtensionInfo contains information about extension.
generate random integers
Definition cf_random.h:56
void remove(int moveright)
T & getItem() const
T getFirst() const
void removeFirst()
int length() const
void append(const T &)
T getLast() const
int isEmpty() const
class to generate random evaluation points
Definition cf_reval.h:26
factory's class for variables
Definition factory.h:127
int level() const
Definition factory.h:143
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
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
Variable x
CFList Evaluation & E
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
CFList *& Aeval
<[in] poly
CFList int bool & irred
[in,out] Is A irreducible?
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:75
CFList tmp2
Definition facFqBivar.cc:75
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
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...
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...
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)
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 > &)
#define info
Definition libparse.cc:1256
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)
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:1027
#define TIMING_START(t)
Definition timing.h:92
#define TIMING_END_AND_PRINT(t, msg)
Definition timing.h:94

◆ 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 }
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 {
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);
114 newResult.insert (result.getFirst());
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)
123 }
124 tmp= ratFactorize (tmp2, v, false);
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
144 "time for squarefree factorization over Q: ");
145
146 CFList tmp;
147 for (CFFListIterator i= sqrfFactors; i.hasItem(); i++)
148 {
150 tmp= ratSqrfFactorize (i.getItem().factor(), v);
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 {
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:961
void insert(const T &)
CanonicalForm LcF
return result
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
CFList ratSqrfFactorize(const CanonicalForm &G, const Variable &v=Variable(1))
factorize a squarefree multivariate polynomial over
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);
60 if (isOn (SW_RATIONAL))
61 F *= bCommonDen (F);
63 if (isOn (SW_RATIONAL))
64 {
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

<[in] alg. variable

Definition at line 35 of file facFactorize.h.