source: git/factory/facFqFactorize.h @ 08a955

spielwiese
Last change on this file since 08a955 was bbcc98, checked in by Martin Lee <martinlee84@…>, 11 years ago
chg: more docu
  • Property mode set to 100644
File size: 34.9 KB
Line 
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
28TIMING_DEFINE_PRINT (fac_fq_squarefree)
29TIMING_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()
35CFList
36multiFactorize (const CanonicalForm& F,    ///< [in] poly to be factored
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
46inline
47CFList FpSqrfFactorize (const CanonicalForm & F ///< [in] a multivariate poly
48                       )
49{
50  if (getNumVars (F) == 2)
51    return FpBiSqrfFactorize (F);
52  ExtensionInfo info= ExtensionInfo (false);
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()
63inline
64CFList 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()
81inline
82CFList GFSqrfFactorize (const CanonicalForm & F ///< [in] a multivariate poly
83                       )
84{
85  ASSERT (CFFactory::gettype() == GaloisFieldDomain,
86          "GF as base field expected");
87  if (getNumVars (F) == 2)
88    return GFBiSqrfFactorize (F);
89  ExtensionInfo info= ExtensionInfo (getGFDegree(), gf_name, false);
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()
100inline
101CFFList 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 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;
131      CanonicalForm tmp2;
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 [] substDegree;
149      return newResult;
150    }
151    delete [] substDegree;
152  }
153
154  ExtensionInfo info= ExtensionInfo (false);
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();
164  CFListIterator i;
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()
183inline
184CFFList 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 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;
215      CanonicalForm tmp2;
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 [] substDegree;
233      return newResult;
234    }
235    delete [] 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();
247  CFListIterator i;
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()
266inline
267CFFList GFFactorize (const CanonicalForm& G, ///< [in] a multivariate poly
268                     bool substCheck= true   ///< [in] enables substitute check
269                    )
270{
271  ASSERT (CFFactory::gettype() == GaloisFieldDomain,
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 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;
299      CanonicalForm tmp2;
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 [] substDegree;
317      return newResult;
318    }
319    delete [] substDegree;
320  }
321
322  Variable a= Variable (1);
323  ExtensionInfo info= ExtensionInfo (getGFDegree(), gf_name, false);
324  CanonicalForm LcF= Lc (F);
325  CFFList sqrf= GFSqrf (F, false);
326  CFFList result;
327  CFList bufResult;
328  sqrf.removeFirst();
329  CFListIterator i;
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()
348CFList
349extFactorRecombination (
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()
364CFList
365factorRecombination (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
374CFList
375recombination (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()
391int
392liftBoundAdaption (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()
409int
410extLiftBoundAdaption (
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()
430CFList
431earlyFactorDetect (
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()
453CFList
454extEarlyFactorDetect (
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.
480CFList
481evalPoints (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()
499CFList
500henselLiftAndEarly (
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()
521CFList
522extFactorize (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.
531CanonicalForm
532lcmContent (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
543CanonicalForm 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
552void
553evaluationWRTDifferentSecondVars (
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
568void
569refineBiFactors (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
583CFList
584buildUniFactors (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
592void sortByUniFactors (CFList*& Aeval,          ///< [in,out] array of bivariate
593                                                ///< factors
594                       int AevalLength,         ///< [in] length of Aeval
595                       const CFList& uniFactors,///< [in] univariate factors
596                       const CFList& evaluation ///< [in] evaluation point
597                      );
598
599/// extract leading coefficients wrt Variable(1) from bivariate factors obtained
600/// from factorizations of A wrt different second variables
601void
602getLeadingCoeffs (const CanonicalForm& A,  ///< [in] some poly
603                  CFList*& Aeval           ///< [in,out] array of bivariate
604                                           ///< factors, returns the leading
605                                           ///< coefficients of these factors
606                 );
607
608/// normalize precomputed leading coefficients such that leading coefficients
609/// evaluated at @a evaluation in K^(n-2) equal the leading coeffs wrt
610/// Variable(1) of bivariate factors and change @a A and @a Aeval accordingly
611void
612prepareLeadingCoeffs (CFList*& LCs,               ///<[in,out]
613                      CanonicalForm& A,           ///<[in,out]
614                      CFList& Aeval,              ///<[in,out]
615                      int n,                      ///<[in] level of poly to be
616                                                  ///< factored
617                      const CFList& leadingCoeffs,///<[in] precomputed leading
618                                                  ///< coeffs
619                      const CFList& biFactors,    ///<[in] bivariate factors
620                      const CFList& evaluation    ///<[in] evaluation point
621                     );
622
623/// obtain factors of F by reconstructing their leading coeffs
624///
625/// @return returns the reconstructed factors
626/// @sa factorRecombination()
627CFList
628leadingCoeffReconstruction (const CanonicalForm& F,///<[in] poly to be factored
629                            const CFList& factors, ///<[in] factors of f monic
630                                                   ///< wrt Variable (1)
631                            const CFList& M        ///<[in] a list of powers of
632                                                   ///< Variables
633                           );
634
635/// distribute content
636///
637/// @return returns a list result of polys such that prod (result)= prod (L)
638/// but the first entry of L may be (partially) factorized and these factors
639/// are distributed onto other entries in L
640CFList
641distributeContent (
642          const CFList& L,                        ///<[in] list of polys, first
643                                                  ///< entry the content to be
644                                                  ///< distributed
645          const CFList* differentSecondVarFactors,///<[in] factorization wrt
646                                                  ///< different second vars
647          int length                              ///<[in] length of
648                                                  ///<differentSecondVarFactors
649                  );
650
651/// gcd free basis of two lists of factors
652void
653gcdFreeBasis (CFFList& factors1, ///< [in,out] list of factors, returns gcd free
654                                 ///< factors
655              CFFList& factors2  ///< [in,out] list of factors, returns gcd free
656                                 ///< factors
657             );
658
659/// computes a list l of length length(LCFFactors)+1 of polynomials such that
660/// prod (l)=LCF, note that the first entry of l may be non constant. Intended
661/// to be used to precompute coefficients of a polynomial f from its bivariate
662/// factorizations.
663///
664/// @return see above
665CFList
666precomputeLeadingCoeff (const CanonicalForm& LCF,       ///<[in] a multivariate
667                                                        ///< poly
668                        const CFList& LCFFactors,       ///<[in] a list of
669                                                        ///< univariate factors
670                                                        ///< of LCF of level 2
671                        const Variable& alpha,          ///<[in] algebraic var.
672                        const CFList& evaluation,       ///<[in] an evaluation
673                                                        ///< point having
674                                                        ///< lSecondVarLCs+1
675                                                        ///< components
676                        CFList* & differentSecondVarLCs,///<[in] LCs of factors
677                                                        ///< of f wrt different
678                                                        ///< second variables
679                        int lSecondVarLCs,              ///<[in] length of the
680                                                        ///< above
681                        Variable& y                     ///<[in,out] if y.level()
682                                                        ///< is not 1 on output
683                                                        ///< the second variable
684                                                        ///< has been changed to
685                                                        ///< y
686                       );
687
688/// changes the second variable to be @a w and updates all relevant data
689void
690changeSecondVariable (CanonicalForm& A,        ///<[in,out] a multivariate poly
691                      CFList& biFactors,       ///<[in,out] bivariate factors
692                      CFList& evaluation,      ///<[in,out] evaluation point
693                      CFList*& oldAeval,       ///<[in,out] old bivariate factors
694                                               ///< wrt. different second vars
695                      int lengthAeval2,        ///<[in] length of oldAeval
696                      const CFList& uniFactors,///<[in] univariate factors
697                      const Variable& w        ///<[in] some variable
698                     );
699
700/// distributes a divisor LCmultiplier of LC(A,1) on the bivariate factors and
701/// the precomputed leading coefficients
702void
703distributeLCmultiplier (CanonicalForm& A,               ///<[in,out] some poly
704                        CFList& leadingCoeffs,          ///<[in,out] leading
705                                                        ///< coefficients
706                        CFList& biFactors,              ///<[in,out] bivariate
707                                                        ///< factors
708                        const CFList& evaluation,       ///<[in] eval. point
709                        const CanonicalForm& LCmultipler///<[in] multiplier
710                       );
711
712/// heuristic to distribute @a LCmultiplier onto factors based on the variables
713/// that occur in @a LCmultiplier and in the leading coeffs of bivariate factors
714void
715LCHeuristic (CanonicalForm& A,                 ///<[in,out] a poly
716             const CanonicalForm& LCmultiplier,///<[in,out] divisor of LC (A,1)
717             CFList& biFactors,                ///<[in,out] bivariate factors
718             CFList*& leadingCoeffs,           ///<[in,out] leading coeffs
719             const CFList* oldAeval,           ///<[in] bivariate factors wrt.
720                                               ///< different second vars
721             int lengthAeval,                  ///<[in] length of oldAeval
722             const CFList& evaluation,         ///<[in] evaluation point
723             const CFList& oldBiFactors        ///<[in] bivariate factors
724                                               ///< without LCmultiplier
725                                               ///< distributed on them
726            );
727
728/// checks if prod(LCs)==LC (oldA,1) and if so divides elements of leadingCoeffs
729/// by elements in contents, sets A to oldA and sets foundTrueMultiplier to true
730void
731LCHeuristicCheck (const CFList& LCs,        ///<[in] leading coeffs computed
732                  const CFList& contents,   ///<[in] content of factors
733                  CanonicalForm& A,         ///<[in,out] oldA*LCmultiplier^m
734                  const CanonicalForm& oldA,///<[in] some poly
735                  CFList& leadingCoeffs,    ///<[in,out] leading coefficients
736                  bool& foundTrueMultiplier ///<[in,out] success?
737                 );
738
739/// heuristic to distribute @a LCmultiplier onto factors based on the contents
740/// of @a factors. @a factors are assumed to come from LucksWangSparseHeuristic.
741/// If not successful @a contents will contain the content of each element of @a
742/// factors and @a LCs will contain the LC of each element of @a factors divided
743/// by its content
744void
745LCHeuristic2 (const CanonicalForm& LCmultiplier,///<[in] divisor of LC (A,1)
746              const CFList& factors,            ///<[in] result of
747                                                ///< LucksWangSparseHeuristic
748              CFList& leadingCoeffs,            ///<[in,out] leading coeffs
749              CFList& contents,                 ///<[in,out] content of factors
750              CFList& LCs,                      ///<[in,out] LC of factors
751                                                ///< divided by content of
752                                                ///< factors
753              bool& foundTrueMultiplier         ///<[in,out] success?
754             );
755
756/// heuristic to remove @a LCmultiplier from a factor based on the contents
757/// of @a factors. @a factors are assumed to come from LucksWangSparseHeuristic.
758void
759LCHeuristic3 (const CanonicalForm& LCmultiplier,///<[in] divisor of LC (A,1)
760              const CFList& factors,            ///<[in] result of
761                                                ///< LucksWangSparseHeuristic
762              const CFList& oldBiFactors,       ///<[in] bivariate factors
763                                                ///< without LCmultiplier
764                                                ///< distributed on them
765              const CFList& contents,           ///<[in] content of factors
766              const CFList* oldAeval,           ///<[in] bivariate factors wrt.
767                                                ///< different second vars
768              CanonicalForm& A,                 ///<[in,out] poly
769              CFList*& leadingCoeffs,           ///<[in,out] leading coeffs
770              int lengthAeval,                  ///<[in] length of oldAeval
771              bool& foundMultiplier             ///<[in,out] success?
772             );
773
774/// heuristic to remove factors of @a LCmultiplier from @a factors.
775/// More precisely checks if elements of @a contents divide @a LCmultiplier.
776/// Assumes LCHeuristic3 is run before it and was successful.
777void
778LCHeuristic4 (const CFList& oldBiFactors,   ///<[in] bivariate factors
779                                            ///< without LCmultiplier
780                                            ///< distributed on them
781              const CFList* oldAeval,       ///<[in] bivariate factors wrt.
782                                            ///< different second vars
783              const CFList& contents,       ///<[in] content of factors
784              const CFList& factors,        ///<[in] result of
785                                            ///< LucksWangSparseHeuristic
786              const CanonicalForm& testVars,///<[in] product of second vars that
787                                            ///< occur among oldAeval
788              int lengthAeval,              ///<[in] length of oldAeval
789              CFList*& leadingCoeffs,       ///<[in,out] leading coeffs
790              CanonicalForm& A,             ///<[in,out] poly
791              CanonicalForm& LCmultiplier,  ///<[in,out] divisor of LC (A,1)
792              bool& foundMultiplier         ///<[in] success?
793             );
794
795#endif
796/* FAC_FQ_FACTORIZE_H */
797
Note: See TracBrowser for help on using the repository browser.