facFqFactorize.h
Go to the documentation of this file.
1 /*****************************************************************************\
2  * Computer Algebra System SINGULAR
3 \*****************************************************************************/
4 /** @file facFqFactorize.h
5  *
6  * This file provides functions for factorizing a multivariate polynomial over
7  * \f$ F_{p} \f$ , \f$ F_{p}(\alpha ) \f$ or GF.
8  *
9  * @author Martin Lee
10  *
11  **/
12 /*****************************************************************************/
13 
14 #ifndef FAC_FQ_FACTORIZE_H
15 #define FAC_FQ_FACTORIZE_H
16 
17 // #include "config.h"
18 #include "timing.h"
19 
20 #include "facFqBivar.h"
21 #include "DegreePattern.h"
22 #include "ExtensionInfo.h"
23 #include "cf_util.h"
24 #include "facFqSquarefree.h"
25 #include "facFqBivarUtil.h"
26 
27 
28 TIMING_DEFINE_PRINT (fac_fq_squarefree)
29 TIMING_DEFINE_PRINT (fac_fq_factor_squarefree)
30 
31 /// Factorization over a finite field
32 ///
33 /// @return @a multiFactorize returns a factorization of F
34 /// @sa biFactorize(), extFactorize()
35 CFList
36 multiFactorize (const CanonicalForm& F, ///< [in] sqrfree poly
37  const ExtensionInfo& info ///< [in] info about extension
38  );
39 
40 /// factorize a squarefree multivariate polynomial over \f$ F_{p} \f$
41 ///
42 /// @return @a FpSqrfFactorize returns a list of monic factors, the first
43 /// element is the leading coefficient.
44 /// @sa FqSqrfFactorize(), GFSqrfFactorize()
45 #ifdef HAVE_NTL
46 inline
47 CFList FpSqrfFactorize (const CanonicalForm & F ///< [in] a multivariate poly
48  )
49 {
50  if (getNumVars (F) == 2)
51  return FpBiSqrfFactorize (F);
53  CFList result= multiFactorize (F, info);
54  result.insert (Lc(F));
55  return result;
56 }
57 
58 /// factorize a squarefree multivariate polynomial over \f$ F_{p} (\alpha ) \f$
59 ///
60 /// @return @a FqSqrfFactorize returns a list of monic factors, the first
61 /// element is the leading coefficient.
62 /// @sa FpSqrfFactorize(), GFSqrfFactorize()
63 inline
64 CFList FqSqrfFactorize (const CanonicalForm & F, ///< [in] a multivariate poly
65  const Variable& alpha ///< [in] algebraic variable
66  )
67 {
68  if (getNumVars (F) == 2)
69  return FqBiSqrfFactorize (F, alpha);
70  ExtensionInfo info= ExtensionInfo (alpha, false);
71  CFList result= multiFactorize (F, info);
72  result.insert (Lc(F));
73  return result;
74 }
75 
76 /// factorize a squarefree multivariate polynomial over GF
77 ///
78 /// @return @a GFSqrfFactorize returns a list of monic factors, the first
79 /// element is the leading coefficient.
80 /// @sa FpSqrfFactorize(), FqSqrfFactorize()
81 inline
82 CFList GFSqrfFactorize (const CanonicalForm & F ///< [in] a multivariate poly
83  )
84 {
86  "GF as base field expected");
87  if (getNumVars (F) == 2)
88  return GFBiSqrfFactorize (F);
90  CFList result= multiFactorize (F, info);
91  result.insert (Lc(F));
92  return result;
93 }
94 
95 /// factorize a multivariate polynomial over \f$ F_{p} \f$
96 ///
97 /// @return @a FpFactorize returns a list of monic factors with
98 /// multiplicity, the first element is the leading coefficient.
99 /// @sa FqFactorize(), GFFactorize()
100 inline
101 CFFList FpFactorize (const CanonicalForm& G,///< [in] a multivariate poly
102  bool substCheck= true ///< [in] enables substitute check
103  )
104 {
105  if (getNumVars (G) == 2)
106  return FpBiFactorize (G, substCheck);
107 
108  CanonicalForm F= G;
109  if (substCheck)
110  {
111  bool foundOne= false;
112  int * substDegree= NEW_ARRAY(int,F.level());
113  for (int i= 1; i <= F.level(); i++)
114  {
115  if (degree (F, i) > 0)
116  {
117  substDegree[i-1]= substituteCheck (F, Variable (i));
118  if (substDegree [i-1] > 1)
119  {
120  foundOne= true;
121  subst (F, F, substDegree[i-1], Variable (i));
122  }
123  }
124  else
125  substDegree[i-1]= -1;
126  }
127  if (foundOne)
128  {
129  CFFList result= FpFactorize (F, false);
130  CFFList newResult, tmp;
132  newResult.insert (result.getFirst());
133  result.removeFirst();
134  for (CFFListIterator i= result; i.hasItem(); i++)
135  {
136  tmp2= i.getItem().factor();
137  for (int j= 1; j <= G.level(); j++)
138  {
139  if (substDegree[j-1] > 1)
140  tmp2= reverseSubst (tmp2, substDegree[j-1], Variable (j));
141  }
142  tmp= FpFactorize (tmp2, false);
143  tmp.removeFirst();
144  for (CFFListIterator j= tmp; j.hasItem(); j++)
145  newResult.append (CFFactor (j.getItem().factor(),
146  j.getItem().exp()*i.getItem().exp()));
147  }
148  DELETE_ARRAY(substDegree);
149  return newResult;
150  }
151  DELETE_ARRAY(substDegree);
152  }
153 
155  Variable a= Variable (1);
156  CanonicalForm LcF= Lc (F);
157  TIMING_START (fac_fq_squarefree);
158  CFFList sqrf= FpSqrf (F, false);
159  TIMING_END_AND_PRINT (fac_fq_squarefree,
160  "time for squarefree factorization over Fq: ");
161  CFFList result;
162  CFList bufResult;
163  sqrf.removeFirst();
165  for (CFFListIterator iter= sqrf; iter.hasItem(); iter++)
166  {
167  TIMING_START (fac_fq_factor_squarefree);
168  bufResult= multiFactorize (iter.getItem().factor(), info);
169  TIMING_END_AND_PRINT (fac_fq_factor_squarefree,
170  "time to factorize sqrfree factor over Fq: ");
171  for (i= bufResult; i.hasItem(); i++)
172  result.append (CFFactor (i.getItem(), iter.getItem().exp()));
173  }
174  result.insert (CFFactor (LcF, 1));
175  return result;
176 }
177 
178 /// factorize a multivariate polynomial over \f$ F_{p} (\alpha ) \f$
179 ///
180 /// @return @a FqFactorize returns a list of monic factors with
181 /// multiplicity, the first element is the leading coefficient.
182 /// @sa FpFactorize(), GFFactorize()
183 inline
184 CFFList FqFactorize (const CanonicalForm& G, ///< [in] a multivariate poly
185  const Variable& alpha, ///< [in] algebraic variable
186  bool substCheck= true ///< [in] enables substitute check
187  )
188 {
189  if (getNumVars (G) == 2)
190  return FqBiFactorize (G, alpha, substCheck);
191 
192  CanonicalForm F= G;
193  if (substCheck)
194  {
195  bool foundOne= false;
196  int * substDegree= NEW_ARRAY(int,F.level());
197  for (int i= 1; i <= F.level(); i++)
198  {
199  if (degree (F, i) > 0)
200  {
201  substDegree[i-1]= substituteCheck (F, Variable (i));
202  if (substDegree [i-1] > 1)
203  {
204  foundOne= true;
205  subst (F, F, substDegree[i-1], Variable (i));
206  }
207  }
208  else
209  substDegree[i-1]= -1;
210  }
211  if (foundOne)
212  {
213  CFFList result= FqFactorize (F, alpha, false);
214  CFFList newResult, tmp;
216  newResult.insert (result.getFirst());
217  result.removeFirst();
218  for (CFFListIterator i= result; i.hasItem(); i++)
219  {
220  tmp2= i.getItem().factor();
221  for (int j= 1; j <= G.level(); j++)
222  {
223  if (substDegree[j-1] > 1)
224  tmp2= reverseSubst (tmp2, substDegree[j-1], Variable (j));
225  }
226  tmp= FqFactorize (tmp2, alpha, false);
227  tmp.removeFirst();
228  for (CFFListIterator j= tmp; j.hasItem(); j++)
229  newResult.append (CFFactor (j.getItem().factor(),
230  j.getItem().exp()*i.getItem().exp()));
231  }
232  DELETE_ARRAY(substDegree);
233  return newResult;
234  }
235  DELETE_ARRAY(substDegree);
236  }
237 
238  ExtensionInfo info= ExtensionInfo (alpha, false);
239  CanonicalForm LcF= Lc (F);
240  TIMING_START (fac_fq_squarefree);
241  CFFList sqrf= FqSqrf (F, alpha, false);
242  TIMING_END_AND_PRINT (fac_fq_squarefree,
243  "time for squarefree factorization over Fq: ");
244  CFFList result;
245  CFList bufResult;
246  sqrf.removeFirst();
248  for (CFFListIterator iter= sqrf; iter.hasItem(); iter++)
249  {
250  TIMING_START (fac_fq_factor_squarefree);
251  bufResult= multiFactorize (iter.getItem().factor(), info);
252  TIMING_END_AND_PRINT (fac_fq_factor_squarefree,
253  "time to factorize sqrfree factor over Fq: ");
254  for (i= bufResult; i.hasItem(); i++)
255  result.append (CFFactor (i.getItem(), iter.getItem().exp()));
256  }
257  result.insert (CFFactor (LcF, 1));
258  return result;
259 }
260 
261 /// factorize a multivariate polynomial over GF
262 ///
263 /// @return @a GFFactorize returns a list of monic factors with
264 /// multiplicity, the first element is the leading coefficient.
265 /// @sa FpFactorize(), FqFactorize()
266 inline
267 CFFList GFFactorize (const CanonicalForm& G, ///< [in] a multivariate poly
268  bool substCheck= true ///< [in] enables substitute check
269  )
270 {
272  "GF as base field expected");
273  if (getNumVars (G) == 2)
274  return GFBiFactorize (G, substCheck);
275 
276  CanonicalForm F= G;
277  if (substCheck)
278  {
279  bool foundOne= false;
280  int * substDegree= NEW_ARRAY(int,F.level());
281  for (int i= 1; i <= F.level(); i++)
282  {
283  if (degree (F, i) > 0)
284  {
285  substDegree[i-1]= substituteCheck (F, Variable (i));
286  if (substDegree [i-1] > 1)
287  {
288  foundOne= true;
289  subst (F, F, substDegree[i-1], Variable (i));
290  }
291  }
292  else
293  substDegree[i-1]= -1;
294  }
295  if (foundOne)
296  {
297  CFFList result= GFFactorize (F, false);
298  CFFList newResult, tmp;
300  newResult.insert (result.getFirst());
301  result.removeFirst();
302  for (CFFListIterator i= result; i.hasItem(); i++)
303  {
304  tmp2= i.getItem().factor();
305  for (int j= 1; j <= G.level(); j++)
306  {
307  if (substDegree[j-1] > 1)
308  tmp2= reverseSubst (tmp2, substDegree[j-1], Variable (j));
309  }
310  tmp= GFFactorize (tmp2, false);
311  tmp.removeFirst();
312  for (CFFListIterator j= tmp; j.hasItem(); j++)
313  newResult.append (CFFactor (j.getItem().factor(),
314  j.getItem().exp()*i.getItem().exp()));
315  }
316  DELETE_ARRAY(substDegree);
317  return newResult;
318  }
319  DELETE_ARRAY(substDegree);
320  }
321 
322  Variable a= Variable (1);
324  CanonicalForm LcF= Lc (F);
325  CFFList sqrf= GFSqrf (F, false);
326  CFFList result;
327  CFList bufResult;
328  sqrf.removeFirst();
330  for (CFFListIterator iter= sqrf; iter.hasItem(); iter++)
331  {
332  bufResult= multiFactorize (iter.getItem().factor(), info);
333  for (i= bufResult; i.hasItem(); i++)
334  result.append (CFFactor (i.getItem(), iter.getItem().exp()));
335  }
336  result.insert (CFFactor (LcF, 1));
337  return result;
338 }
339 
340 #endif
341 
342 /// Naive factor recombination for multivariate factorization over an extension
343 /// of the initial field. No precomputed is used to exclude combinations.
344 ///
345 /// @return @a extFactorRecombination returns a list of factors of @a F, whose
346 /// shift to zero is reversed.
347 /// @sa factorRecombination()
348 CFList
350  const CFList& factors, ///< [in] list of lifted factors
351  ///< that are monic wrt Variable (1)
352  const CanonicalForm& F, ///< [in] poly to be factored
353  const CFList& M, ///< [in] a list of powers of
354  ///< Variables
355  const ExtensionInfo& info, ///< [in] info about extension
356  const CFList& evaluation ///< [in] evaluation point
357  );
358 
359 /// Naive factor recombination for multivariate factorization.
360 /// No precomputed is used to exclude combinations.
361 ///
362 /// @return @a factorRecombination returns a list of factors of @a F
363 /// @sa extFactorRecombination()
364 CFList
365 factorRecombination (const CanonicalForm& F,///< [in] poly to be factored
366  const CFList& factors, ///< [in] list of lifted factors
367  ///< that are monic wrt Variable (1)
368  const CFList& M ///< [in] a list of powers of
369  ///< Variables
370  );
371 
372 /// recombination of bivariate factors @a factors1 s. t. the result evaluated
373 /// at @a evalPoint coincides with @a factors2
374 CFList
375 recombination (const CFList& factors1, ///<[in] list of bivariate factors
376  const CFList& factors2, ///<[in] list univariate factors
377  int s, ///<[in] algorithm starts checking
378  ///< subsets of size s
379  int thres, ///<[in] threshold for the size of
380  ///< subsets which are checked
381  const CanonicalForm& evalPoint,///<[in] evaluation point
382  const Variable& x ///<[in] second variable of
383  ///< bivariate factors
384  );
385 
386 /// Lift bound adaption. Essentially an early factor detection but only the lift
387 /// bound is adapted.
388 ///
389 /// @return @a liftBoundAdaption returns an adapted lift bound.
390 /// @sa earlyFactorDetect(), earlyFactorDetection()
391 int
392 liftBoundAdaption (const CanonicalForm& F, ///< [in] a poly
393  const CFList& factors, ///< [in] list of list of lifted
394  ///< factors that are monic wrt
395  ///< Variable (1)
396  bool& success, ///< [in,out] indicates that no
397  ///< further lifting is necessary
398  const int deg, ///< [in] stage of Hensel lifting
399  const CFList& MOD, ///< [in] a list of powers of
400  ///< Variables
401  const int bound ///< [in] initial lift bound
402  );
403 
404 /// Lift bound adaption over an extension of the initial field. Essentially an
405 ///early factor detection but only the lift bound is adapted.
406 ///
407 /// @return @a liftBoundAdaption returns an adapted lift bound.
408 /// @sa earlyFactorDetect(), earlyFactorDetection()
409 int
411  const CanonicalForm& F, ///< [in] a poly
412  const CFList& factors, ///< [in] list of list of lifted
413  ///< factors that are monic wrt
414  bool& success, ///< [in,out] indicates that no further
415  ///< lifting is necessary
416  const ExtensionInfo& info, ///< [in] info about extension
417  const CFList& eval, ///< [in] evaluation point
418  const int deg, ///< [in] stage of Hensel lifting
419  const CFList& MOD, ///< [in] a list of powers of
420  ///< Variables
421  const int bound ///< [in] initial lift bound
422  );
423 
424 /// detects factors of @a F at stage @a deg of Hensel lifting.
425 /// No combinations of more than one factor are tested. Lift bound is adapted.
426 ///
427 /// @return @a earlyFactorDetect returns a list of factors of F (possibly
428 /// incomplete), in case of success. Otherwise an empty list.
429 /// @sa factorRecombination(), extEarlyFactorDetect()
430 CFList
432  CanonicalForm& F, ///< [in,out] poly to be factored,
433  ///< returns poly divided by detected
434  ///< factors in case of success
435  CFList& factors, ///< [in,out] list of factors lifted up
436  ///< to @a deg, returns a list of factors
437  ///< without detected factors
438  int& adaptedLiftBound, ///< [in,out] adapted lift bound
439  bool& success, ///< [in,out] indicating success
440  const int deg, ///< [in] stage of Hensel lifting
441  const CFList& MOD, ///< [in] a list of powers of
442  ///< Variables
443  const int bound ///< [in] initial lift bound
444  );
445 
446 /// detects factors of @a F at stage @a deg of Hensel lifting.
447 /// No combinations of more than one factor are tested. Lift bound is adapted.
448 ///
449 /// @return @a extEarlyFactorDetect returns a list of factors of F (possibly
450 /// incomplete), whose shift to zero is reversed, in case of success.
451 /// Otherwise an empty list.
452 /// @sa factorRecombination(), earlyFactorDetection()
453 CFList
455  CanonicalForm& F, ///< [in,out] poly to be factored,
456  ///< returns poly divided by detected
457  ///< factors in case of success
458  CFList& factors, ///< [in,out] list of factors lifted up
459  ///< to @a deg, returns a list of factors
460  ///< without detected factors
461  int& adaptedLiftBound, ///< [in,out] adapted lift bound
462  bool& success, ///< [in,out] indicating succes
463  const ExtensionInfo& info, ///< [in] info about extension
464  const CFList& eval, ///< [in] evaluation point
465  const int deg, ///< [in] stage of Hensel lifting
466  const CFList& MOD, ///< [in] a list of powers of Variables
467  const int bound ///< [in] initial lift bound
468  );
469 
470 /// evaluation point search for multivariate factorization,
471 /// looks for a (F.level() - 1)-tuple such that the resulting univariate
472 /// polynomial has main variable Variable (1), is squarefree and its degree
473 /// coincides with degree(F) and the bivariate one is primitive wrt.
474 /// Variable(1), and successively evaluated polynomials have the same degree in
475 /// their main variable as F has, fails if there are no valid evaluation points,
476 /// eval contains the intermediate evaluated polynomials.
477 ///
478 /// @return @a evalPoints returns an evaluation point, which is valid if and
479 /// only if fail == false.
480 CFList
481 evalPoints (const CanonicalForm& F, ///< [in] a compressed poly
482  CFList & eval, ///< [in,out] an empty list, returns @a F
483  ///< successive evaluated
484  const Variable& alpha, ///< [in] algebraic variable
485  CFList& list, ///< [in,out] a list of points already
486  ///< considered, a point is encoded as a
487  ///< poly of degree F.level()-1 in
488  ///< Variable(1)
489  const bool& GF, ///< [in] GF?
490  bool& fail ///< [in,out] indicates failure
491  );
492 
493 /// hensel Lifting and early factor detection
494 ///
495 /// @return @a henselLiftAndEarly returns monic (wrt Variable (1)) lifted
496 /// factors without factors which have been detected at an early stage
497 /// of Hensel lifting
498 /// @sa earlyFactorDetectn(), extEarlyFactorDetect()
499 CFList
501  CanonicalForm& A, ///< [in,out] poly to be factored,
502  ///< returns poly divided by detected
503  ///< factors, in case of success
504  CFList& MOD, ///< [in,out] a list of powers of
505  ///< Variables
506  int*& liftBounds, ///< [in,out] initial lift bounds, returns
507  ///< adapted lift bounds
508  bool& earlySuccess, ///< [in,out] indicating success
509  CFList& earlyFactors, ///< [in,out] early factors
510  const CFList& Aeval, ///< [in] @a A successively evaluated at
511  ///< elements of @a evaluation
512  const CFList& biFactors, ///< [in] bivariate factors
513  const CFList& evaluation, ///< [in] evaluation point
514  const ExtensionInfo& info ///< [in] info about extension
515  );
516 
517 /// Factorization over an extension of initial field
518 ///
519 /// @return @a extFactorize returns factorization of F over initial field
520 /// @sa extBiFactorize(), multiFactorize()
521 CFList
522 extFactorize (const CanonicalForm& F, ///< [in] poly to be factored
523  const ExtensionInfo& info ///< [in] info about extension
524  );
525 
526 /// compute the LCM of the contents of @a A wrt to each variable occuring in @a
527 /// A.
528 ///
529 /// @return @a lcmContent returns the LCM of the contents of @a A wrt to each
530 /// variable occuring in @a A.
532 lcmContent (const CanonicalForm& A, ///< [in] a compressed multivariate poly
533  CFList& contentAi ///< [in,out] an empty list, returns a list
534  ///< of the contents of @a A wrt to each
535  ///< variable occuring in @a A starting from
536  ///< @a A.mvar().
537  );
538 
539 /// compress a polynomial s.t. \f$ deg_{x_{i}} (F) >= deg_{x_{i+1}} (F) \f$ and
540 /// no gaps between the variables occur
541 ///
542 /// @return a compressed poly with the above properties
543 CanonicalForm myCompress (const CanonicalForm& F, ///< [in] a poly
544  CFMap& N ///< [in,out] a map to
545  ///< decompress
546  );
547 
548 /// evaluate a poly A with main variable at level 1 at an evaluation point in
549 /// K^(n-1) wrt different second variables. If this evaluation is valid (see
550 /// evalPoints) then Aeval contains A successively evaluated at this point,
551 /// otherwise this entry is empty
552 void
554  CFList*& Aeval, ///<[in,out] an array of length n-2
555  ///< if variable at level i > 2
556  ///< admits a valid evaluation
557  ///< this entry contains A
558  ///< successively evaluated at this
559  ///< point otherwise an empty list
560  const CFList& evaluation,///<[in] a valid evaluation point
561  ///< for main variable at level 1
562  ///< and second variable at level 2
563  const CanonicalForm& A ///<[in] some poly
564  );
565 
566 /// refine a bivariate factorization of A with l factors to one with
567 /// minFactorsLength if possible
568 void
569 refineBiFactors (const CanonicalForm& A, ///< [in] some poly
570  CFList& biFactors, ///< [in,out] list of bivariate to be
571  ///< refined, returns refined factors
572  CFList* const& factors, ///< [in] list of bivariate
573  ///< factorizations of A wrt different
574  ///< second variables
575  const CFList& evaluation,///< [in] the evaluation point
576  int minFactorsLength ///< [in] the minimal number of factors
577  );
578 
579 /// plug in evalPoint for y in a list of polys
580 ///
581 /// @return returns a list of the evaluated polys, these evaluated polys are
582 /// made monic
583 CFList
584 buildUniFactors (const CFList& biFactors, ///< [in] a list of polys
585  const CanonicalForm& evalPoint,///< [in] some evaluation point
586  const Variable& y ///< [in] some variable
587  );
588 
589 
590 /// sort bivariate factors in Aeval such that their corresponding univariate
591 /// factors coincide with uniFactors, uniFactors and biFactors may get
592 /// recombined if necessary
593 void sortByUniFactors (CFList*& Aeval, ///< [in,out] array of bivariate
594  ///< factors
595  int AevalLength, ///< [in] length of Aeval
596  CFList& uniFactors, ///< [in,out] univariate factors
597  CFList& biFactors, ///< [in,out] bivariate factors
598  const CFList& evaluation ///< [in] evaluation point
599  );
600 
601 /// extract leading coefficients wrt Variable(1) from bivariate factors obtained
602 /// from factorizations of A wrt different second variables
603 void
604 getLeadingCoeffs (const CanonicalForm& A, ///< [in] some poly
605  CFList*& Aeval ///< [in,out] array of bivariate
606  ///< factors, returns the leading
607  ///< coefficients of these factors
608  );
609 
610 /// normalize precomputed leading coefficients such that leading coefficients
611 /// evaluated at @a evaluation in K^(n-2) equal the leading coeffs wrt
612 /// Variable(1) of bivariate factors and change @a A and @a Aeval accordingly
613 void
614 prepareLeadingCoeffs (CFList*& LCs, ///<[in,out]
615  CanonicalForm& A, ///<[in,out]
616  CFList& Aeval, ///<[in,out]
617  int n, ///<[in] level of poly to be
618  ///< factored
619  const CFList& leadingCoeffs,///<[in] precomputed leading
620  ///< coeffs
621  const CFList& biFactors, ///<[in] bivariate factors
622  const CFList& evaluation ///<[in] evaluation point
623  );
624 
625 /// obtain factors of F by reconstructing their leading coeffs
626 ///
627 /// @return returns the reconstructed factors
628 /// @sa factorRecombination()
629 CFList
630 leadingCoeffReconstruction (const CanonicalForm& F,///<[in] poly to be factored
631  const CFList& factors, ///<[in] factors of f monic
632  ///< wrt Variable (1)
633  const CFList& M ///<[in] a list of powers of
634  ///< Variables
635  );
636 
637 /// distribute content
638 ///
639 /// @return returns a list result of polys such that prod (result)= prod (L)
640 /// but the first entry of L may be (partially) factorized and these factors
641 /// are distributed onto other entries in L
642 CFList
644  const CFList& L, ///<[in] list of polys, first
645  ///< entry the content to be
646  ///< distributed
647  const CFList* differentSecondVarFactors,///<[in] factorization wrt
648  ///< different second vars
649  int length ///<[in] length of
650  ///<differentSecondVarFactors
651  );
652 
653 /// gcd free basis of two lists of factors
654 void
655 gcdFreeBasis (CFFList& factors1, ///< [in,out] list of factors, returns gcd free
656  ///< factors
657  CFFList& factors2 ///< [in,out] list of factors, returns gcd free
658  ///< factors
659  );
660 
661 /// computes a list l of length length(LCFFactors)+1 of polynomials such that
662 /// prod (l)=LCF, note that the first entry of l may be non constant. Intended
663 /// to be used to precompute coefficients of a polynomial f from its bivariate
664 /// factorizations.
665 ///
666 /// @return see above
667 CFList
668 precomputeLeadingCoeff (const CanonicalForm& LCF, ///<[in] a multivariate
669  ///< poly
670  const CFList& LCFFactors, ///<[in] a list of
671  ///< univariate factors
672  ///< of LCF of level 2
673  const Variable& alpha, ///<[in] algebraic var.
674  const CFList& evaluation, ///<[in] an evaluation
675  ///< point having
676  ///< lSecondVarLCs+1
677  ///< components
678  CFList* & differentSecondVarLCs,///<[in] LCs of factors
679  ///< of f wrt different
680  ///< second variables
681  int lSecondVarLCs, ///<[in] length of the
682  ///< above
683  Variable& y ///<[in,out] if y.level()
684  ///< is not 1 on output
685  ///< the second variable
686  ///< has been changed to
687  ///< y
688  );
689 
690 /// changes the second variable to be @a w and updates all relevant data
691 void
692 changeSecondVariable (CanonicalForm& A, ///<[in,out] a multivariate poly
693  CFList& biFactors, ///<[in,out] bivariate factors
694  CFList& evaluation, ///<[in,out] evaluation point
695  CFList*& oldAeval, ///<[in,out] old bivariate factors
696  ///< wrt. different second vars
697  int lengthAeval2, ///<[in] length of oldAeval
698  const CFList& uniFactors,///<[in] univariate factors
699  const Variable& w ///<[in] some variable
700  );
701 
702 /// distributes a divisor LCmultiplier of LC(A,1) on the bivariate factors and
703 /// the precomputed leading coefficients
704 void
705 distributeLCmultiplier (CanonicalForm& A, ///<[in,out] some poly
706  CFList& leadingCoeffs, ///<[in,out] leading
707  ///< coefficients
708  CFList& biFactors, ///<[in,out] bivariate
709  ///< factors
710  const CFList& evaluation, ///<[in] eval. point
711  const CanonicalForm& LCmultipler///<[in] multiplier
712  );
713 
714 /// heuristic to distribute @a LCmultiplier onto factors based on the variables
715 /// that occur in @a LCmultiplier and in the leading coeffs of bivariate factors
716 void
717 LCHeuristic (CanonicalForm& A, ///<[in,out] a poly
718  const CanonicalForm& LCmultiplier,///<[in,out] divisor of LC (A,1)
719  CFList& biFactors, ///<[in,out] bivariate factors
720  CFList*& leadingCoeffs, ///<[in,out] leading coeffs
721  const CFList* oldAeval, ///<[in] bivariate factors wrt.
722  ///< different second vars
723  int lengthAeval, ///<[in] length of oldAeval
724  const CFList& evaluation, ///<[in] evaluation point
725  const CFList& oldBiFactors ///<[in] bivariate factors
726  ///< without LCmultiplier
727  ///< distributed on them
728  );
729 
730 /// checks if prod(LCs)==LC (oldA,1) and if so divides elements of leadingCoeffs
731 /// by elements in contents, sets A to oldA and sets foundTrueMultiplier to true
732 void
733 LCHeuristicCheck (const CFList& LCs, ///<[in] leading coeffs computed
734  const CFList& contents, ///<[in] content of factors
735  CanonicalForm& A, ///<[in,out] oldA*LCmultiplier^m
736  const CanonicalForm& oldA,///<[in] some poly
737  CFList& leadingCoeffs, ///<[in,out] leading coefficients
738  bool& foundTrueMultiplier ///<[in,out] success?
739  );
740 
741 /// heuristic to distribute @a LCmultiplier onto factors based on the contents
742 /// of @a factors. @a factors are assumed to come from LucksWangSparseHeuristic.
743 /// If not successful @a contents will contain the content of each element of @a
744 /// factors and @a LCs will contain the LC of each element of @a factors divided
745 /// by its content
746 void
747 LCHeuristic2 (const CanonicalForm& LCmultiplier,///<[in] divisor of LC (A,1)
748  const CFList& factors, ///<[in] result of
749  ///< LucksWangSparseHeuristic
750  CFList& leadingCoeffs, ///<[in,out] leading coeffs
751  CFList& contents, ///<[in,out] content of factors
752  CFList& LCs, ///<[in,out] LC of factors
753  ///< divided by content of
754  ///< factors
755  bool& foundTrueMultiplier ///<[in,out] success?
756  );
757 
758 /// heuristic to remove @a LCmultiplier from a factor based on the contents
759 /// of @a factors. @a factors are assumed to come from LucksWangSparseHeuristic.
760 void
761 LCHeuristic3 (const CanonicalForm& LCmultiplier,///<[in] divisor of LC (A,1)
762  const CFList& factors, ///<[in] result of
763  ///< LucksWangSparseHeuristic
764  const CFList& oldBiFactors, ///<[in] bivariate factors
765  ///< without LCmultiplier
766  ///< distributed on them
767  const CFList& contents, ///<[in] content of factors
768  const CFList* oldAeval, ///<[in] bivariate factors wrt.
769  ///< different second vars
770  CanonicalForm& A, ///<[in,out] poly
771  CFList*& leadingCoeffs, ///<[in,out] leading coeffs
772  int lengthAeval, ///<[in] length of oldAeval
773  bool& foundMultiplier ///<[in,out] success?
774  );
775 
776 /// heuristic to remove factors of @a LCmultiplier from @a factors.
777 /// More precisely checks if elements of @a contents divide @a LCmultiplier.
778 /// Assumes LCHeuristic3 is run before it and was successful.
779 void
780 LCHeuristic4 (const CFList& oldBiFactors, ///<[in] bivariate factors
781  ///< without LCmultiplier
782  ///< distributed on them
783  const CFList* oldAeval, ///<[in] bivariate factors wrt.
784  ///< different second vars
785  const CFList& contents, ///<[in] content of factors
786  const CFList& factors, ///<[in] result of
787  ///< LucksWangSparseHeuristic
788  const CanonicalForm& testVars,///<[in] product of second vars that
789  ///< occur among oldAeval
790  int lengthAeval, ///<[in] length of oldAeval
791  CFList*& leadingCoeffs, ///<[in,out] leading coeffs
792  CanonicalForm& A, ///<[in,out] poly
793  CanonicalForm& LCmultiplier, ///<[in,out] divisor of LC (A,1)
794  bool& foundMultiplier ///<[in] success?
795  );
796 
797 #endif
798 /* FAC_FQ_FACTORIZE_H */
TIMING_END_AND_PRINT(fac_alg_resultant, "time to compute resultant0: ")
const CanonicalForm int s
Definition: facAbsFact.cc:55
const CanonicalForm int const CFList const Variable & y
Definition: facAbsFact.cc:57
int j
Definition: facHensel.cc:105
CanonicalForm lcmContent(const CanonicalForm &A, CFList &contentAi)
compute the LCM of the contents of A wrt to each variable occuring in A.
void gcdFreeBasis(CFFList &factors1, CFFList &factors2)
gcd free basis of two lists of factors
static CanonicalForm bound(const CFMatrix &M)
Definition: cf_linsys.cc:460
CFList buildUniFactors(const CFList &biFactors, const CanonicalForm &evalPoint, const Variable &y)
plug in evalPoint for y in a list of polys
#define DELETE_ARRAY(P)
Definition: cf_defs.h:49
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.
CFFList FpSqrf(const CanonicalForm &F, bool sort=true)
squarefree factorization over . If input is not monic, the leading coefficient is dropped ...
CanonicalForm LCF
Definition: facFactorize.cc:53
TIMING_START(fac_alg_resultant)
factory&#39;s class for variables
Definition: factory.h:117
CFFList GFBiFactorize(const CanonicalForm &G, bool substCheck=true)
factorize a bivariate polynomial over GF
Definition: facFqBivar.h:432
CFList *& Aeval
<[in] poly
Definition: facFactorize.h:31
CFList distributeContent(const CFList &L, const CFList *differentSecondVarFactors, int length)
distribute content
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...
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...
CFFListIterator iter
Definition: facAbsBiFact.cc:54
CFList int & minFactorsLength
[in,out] minimal length of bivariate factors
Definition: facFactorize.h:31
CFList GFBiSqrfFactorize(const CanonicalForm &G)
factorize a squarefree bivariate polynomial over GF
Definition: facFqBivar.h:164
factory&#39;s main class
Definition: canonicalform.h:77
char gf_name
Definition: gfops.cc:52
CFFList FqSqrf(const CanonicalForm &F, const Variable &alpha, bool sort=true)
squarefree factorization over . If input is not monic, the leading coefficient is dropped ...
CFList henselLiftAndEarly(CanonicalForm &A, CFList &MOD, int *&liftBounds, bool &earlySuccess, CFList &earlyFactors, const CFList &Aeval, const CFList &biFactors, const CFList &evaluation, const ExtensionInfo &info)
hensel Lifting and early factor detection
CFList FpSqrfFactorize(const CanonicalForm &F)
factorize a squarefree multivariate polynomial over
const CanonicalForm int const CFList & evaluation
Definition: facAbsFact.cc:55
Variable alpha
Definition: facAbsBiFact.cc:52
CFList FqBiSqrfFactorize(const CanonicalForm &G, const Variable &alpha)
factorize a squarefree bivariate polynomial over .
Definition: facFqBivar.h:150
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 insert(const T &)
Definition: ftmpl_list.cc:193
CFList GFSqrfFactorize(const CanonicalForm &F)
factorize a squarefree multivariate polynomial over GF
const CFList & factors2
static TreeM * G
Definition: janet.cc:31
CanonicalForm Lc(const CanonicalForm &f)
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...
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)
CFFList FpFactorize(const CanonicalForm &G, bool substCheck=true)
factorize a multivariate polynomial over
void getLeadingCoeffs(const CanonicalForm &A, CFList *&Aeval)
extract leading coefficients wrt Variable(1) from bivariate factors obtained from factorizations of A...
T getFirst() const
Definition: ftmpl_list.cc:279
CFList extFactorize(const CanonicalForm &F, const ExtensionInfo &info)
Factorization over an extension of initial field.
This file provides functions for squarefrees factorizing over , or GF.
#define NEW_ARRAY(T, N)
Definition: cf_defs.h:48
#define M
Definition: sirandom.c:24
ExtensionInfo contains information about extension.
Definition: ExtensionInfo.h:50
CFFList GFSqrf(const CanonicalForm &F, bool sort=true)
squarefree factorization over GF. If input is not monic, the leading coefficient is dropped ...
int liftBoundAdaption(const CanonicalForm &F, const CFList &factors, bool &success, const int deg, const CFList &MOD, const int bound)
Lift bound adaption. Essentially an early factor detection but only the lift bound is adapted...
int extLiftBoundAdaption(const CanonicalForm &F, const CFList &factors, bool &success, const ExtensionInfo &info, const CFList &eval, const int deg, const CFList &MOD, const int bound)
Lift bound adaption over an extension of the initial field. Essentially an early factor detection but...
const CanonicalForm CFMap CFMap & N
Definition: cfEzgcd.cc:48
CFList multiFactorize(const CanonicalForm &F, const Variable &v)
Factorization over Q (a)
T & getItem() const
Definition: ftmpl_list.cc:431
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 ...
const ExtensionInfo & info
< [in] sqrfree poly
#define A
Definition: sirandom.c:23
CFFList FqFactorize(const CanonicalForm &G, const Variable &alpha, bool substCheck=true)
factorize a multivariate polynomial over
CFList & eval
Definition: facFactorize.cc:48
CFFList FpBiFactorize(const CanonicalForm &G, bool substCheck=true)
factorize a bivariate polynomial over
Definition: facFqBivar.h:180
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 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...
int substituteCheck(const CanonicalForm &F, const Variable &x)
check if a substitution x^n->x is possible
CFList FpBiSqrfFactorize(const CanonicalForm &G)
factorize a squarefree bivariate polynomial over .
Definition: facFqBivar.h:137
CFList FqSqrfFactorize(const CanonicalForm &F, const Variable &alpha)
factorize a squarefree multivariate polynomial over
int i
Definition: cfEzgcd.cc:125
CFFList FqBiFactorize(const CanonicalForm &G, const Variable &alpha, bool substCheck=true)
factorize a bivariate polynomial over
Definition: facFqBivar.h:305
CFFList GFFactorize(const CanonicalForm &G, bool substCheck=true)
factorize a multivariate polynomial over GF
CFList tmp2
Definition: facFqBivar.cc:70
void refineBiFactors(const CanonicalForm &A, CFList &biFactors, CFList *const &factors, const CFList &evaluation, int minFactorsLength)
refine a bivariate factorization of A with l factors to one with minFactorsLength if possible ...
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...
CFList leadingCoeffReconstruction(const CanonicalForm &F, const CFList &factors, const CFList &M)
obtain factors of F by reconstructing their leading coeffs
class CFMap
Definition: cf_map.h:84
This file provides utility functions for bivariate factorization.
int getNumVars(const CanonicalForm &f)
int getNumVars ( const CanonicalForm & f )
Definition: cf_ops.cc:314
CFList factorRecombination(const CanonicalForm &F, const CFList &factors, const CFList &M)
Naive factor recombination for multivariate factorization. No precomputed is used to exclude combinat...
static int gettype()
Definition: cf_factory.h:28
CFList extFactorRecombination(const CFList &factors, const CanonicalForm &F, const CFList &M, const ExtensionInfo &info, const CFList &evaluation)
Naive factor recombination for multivariate factorization over an extension of the initial field...
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 ...
static BOOLEAN length(leftv result, leftv arg)
Definition: interval.cc:263
const CanonicalForm & w
Definition: facAbsFact.cc:55
int getGFDegree()
Definition: cf_char.cc:56
TIMING_DEFINE_PRINT(fac_fq_squarefree) TIMING_DEFINE_PRINT(fac_fq_factor_squarefree) CFList multiFactorize(const CanonicalForm &F
Factorization over a finite field.
Variable x
Definition: cfModGcd.cc:4023
#define GaloisFieldDomain
Definition: cf_defs.h:22
CFList extEarlyFactorDetect(CanonicalForm &F, CFList &factors, int &adaptedLiftBound, bool &success, const ExtensionInfo &info, const CFList &eval, const int deg, const CFList &MOD, const int bound)
detects factors of F at stage deg of Hensel lifting. No combinations of more than one factor are test...
This file provides a class to handle degree patterns.
CanonicalForm reverseSubst(const CanonicalForm &F, const int d, const Variable &x)
reverse a substitution x^d->x
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
CFList recombination(const CFList &factors1, const CFList &factors2, int s, int thres, const CanonicalForm &evalPoint, const Variable &x)
recombination of bivariate factors factors1 s. t. the result evaluated at evalPoint coincides with fa...
int level() const
level() returns the level of CO.
CanonicalForm myCompress(const CanonicalForm &F, CFMap &N)
compress a polynomial s.t. and no gaps between the variables occur
#define ASSERT(expression, message)
Definition: cf_assert.h:99
This file provides functions for factorizing a bivariate polynomial over , or GF.
CFList earlyFactorDetect(CanonicalForm &F, CFList &factors, int &adaptedLiftBound, bool &success, const int deg, const CFList &MOD, const int bound)
detects factors of F at stage deg of Hensel lifting. No combinations of more than one factor are test...
void append(const T &)
Definition: ftmpl_list.cc:256
int degree(const CanonicalForm &f)
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...
static void evalPoint(const CanonicalForm &F, const CanonicalForm &G, CanonicalForm &FEval, CanonicalForm &GEval, CFGenerator &evalPoint)
return result
Definition: facAbsBiFact.cc:76
This file provides a class to store information about finite fields and extensions thereof...