source: git/factory/facFqFactorize.h @ 667ba1

spielwiese
Last change on this file since 667ba1 was f9b796e, checked in by Martin Lee <martinlee84@…>, 12 years ago
chg: substitution in the top level routines
  • Property mode set to 100644
File size: 29.6 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 * @internal @version \$Id$
12 *
13 **/
14/*****************************************************************************/
15
16#ifndef FAC_FQ_FACTORIZE_H
17#define FAC_FQ_FACTORIZE_H
18
19// #include "config.h"
20
21#include "facFqBivar.h"
22#include "DegreePattern.h"
23#include "ExtensionInfo.h"
24#include "cf_util.h"
25#include "facFqSquarefree.h"
26#include "facFqBivarUtil.h"
27
28/// Factorization over a finite field
29///
30/// @return @a multiFactorize returns a factorization of F
31/// @sa biFactorize(), extFactorize()
32CFList
33multiFactorize (const CanonicalForm& F,    ///< [in] poly to be factored
34                const ExtensionInfo& info  ///< [in] info about extension
35               );
36
37/// factorize a squarefree multivariate polynomial over \f$ F_{p} \f$
38///
39/// @return @a FpSqrfFactorize returns a list of monic factors, the first
40///         element is the leading coefficient.
41/// @sa FqSqrfFactorize(), GFSqrfFactorize()
42#ifdef HAVE_NTL
43inline
44CFList FpSqrfFactorize (const CanonicalForm & F ///< [in] a multivariate poly
45                       )
46{
47  if (getNumVars (F) == 2)
48    return FpBiSqrfFactorize (F);
49  ExtensionInfo info= ExtensionInfo (false);
50  CFList result= multiFactorize (F, info);
51  result.insert (Lc(F));
52  return result;
53}
54
55/// factorize a squarefree multivariate polynomial over \f$ F_{p} (\alpha ) \f$
56///
57/// @return @a FqSqrfFactorize returns a list of monic factors, the first
58///         element is the leading coefficient.
59/// @sa FpSqrfFactorize(), GFSqrfFactorize()
60inline
61CFList FqSqrfFactorize (const CanonicalForm & F, ///< [in] a multivariate poly
62                        const Variable& alpha    ///< [in] algebraic variable
63                       )
64{
65  if (getNumVars (F) == 2)
66    return FqBiSqrfFactorize (F, alpha);
67  ExtensionInfo info= ExtensionInfo (alpha, false);
68  CFList result= multiFactorize (F, info);
69  result.insert (Lc(F));
70  return result;
71}
72
73/// factorize a squarefree multivariate polynomial over GF
74///
75/// @return @a GFSqrfFactorize returns a list of monic factors, the first
76///         element is the leading coefficient.
77/// @sa FpSqrfFactorize(), FqSqrfFactorize()
78inline
79CFList GFSqrfFactorize (const CanonicalForm & F ///< [in] a multivariate poly
80                       )
81{
82  ASSERT (CFFactory::gettype() == GaloisFieldDomain,
83          "GF as base field expected");
84  if (getNumVars (F) == 2)
85    return GFBiSqrfFactorize (F);
86  ExtensionInfo info= ExtensionInfo (getGFDegree(), gf_name, false);
87  CFList result= multiFactorize (F, info);
88  result.insert (Lc(F));
89  return result;
90}
91
92/// factorize a multivariate polynomial over \f$ F_{p} \f$
93///
94/// @return @a FpFactorize returns a list of monic factors with
95///         multiplicity, the first element is the leading coefficient.
96/// @sa FqFactorize(), GFFactorize()
97inline
98CFFList FpFactorize (const CanonicalForm& G,///< [in] a multivariate poly
99                     bool substCheck= true  ///< [in] enables substitute check
100                    )
101{
102  if (getNumVars (G) == 2)
103    return FpBiFactorize (G, substCheck);
104
105  CanonicalForm F= G;
106  if (substCheck)
107  {
108    bool foundOne= false;
109    int * substDegree= new int [F.level()];
110    for (int i= 1; i <= F.level(); i++)
111    {
112      if (degree (F, i) > 0)
113      {
114        substDegree[i-1]= substituteCheck (F, Variable (i));
115        if (substDegree [i-1] > 1)
116        {
117          foundOne= true;
118          subst (F, F, substDegree[i-1], Variable (i));
119        }
120      }
121      else
122        substDegree[i-1]= -1;
123    }
124    if (foundOne)
125    {
126      CFFList result= FpFactorize (F, false);
127      CFFList newResult, tmp;
128      CanonicalForm tmp2;
129      newResult.insert (result.getFirst());
130      result.removeFirst();
131      for (CFFListIterator i= result; i.hasItem(); i++)
132      {
133        tmp2= i.getItem().factor();
134        for (int j= 1; j <= G.level(); j++)
135        {
136          if (substDegree[j-1] > 1)
137            tmp2= reverseSubst (tmp2, substDegree[j-1], Variable (j));
138        }
139        tmp= FpFactorize (tmp2, false);
140        tmp.removeFirst();
141        for (CFFListIterator j= tmp; j.hasItem(); j++)
142          newResult.append (CFFactor (j.getItem().factor(),
143                                      j.getItem().exp()*i.getItem().exp()));
144      }
145      delete [] substDegree;
146      return newResult;
147    }
148    delete [] substDegree;
149  }
150
151  ExtensionInfo info= ExtensionInfo (false);
152  Variable a= Variable (1);
153  CanonicalForm LcF= Lc (F);
154  CanonicalForm pthRoot, A;
155  CanonicalForm sqrfP= sqrfPart (F/Lc(F), pthRoot, a);
156  CFList buf, bufRoot;
157  CFFList result, resultRoot;
158  int p= getCharacteristic();
159  int l;
160  if (degree (pthRoot) > 0)
161  {
162    pthRoot= maxpthRoot (pthRoot, p, l);
163    result= FpFactorize (pthRoot, false);
164    result.removeFirst();
165    for (CFFListIterator i= result; i.hasItem(); i++)
166      i.getItem()= CFFactor(i.getItem().factor(),i.getItem().exp()*ipower(p,l));
167    result.insert (CFFactor (LcF, 1));
168    return result;
169  }
170  else
171  {
172    buf= multiFactorize (sqrfP, info);
173    A= F/LcF;
174    result= multiplicity (A, buf);
175  }
176  if (degree (A) > 0)
177  {
178    resultRoot= FpFactorize (A, false);
179    resultRoot.removeFirst();
180    result= Union (result, resultRoot);
181  }
182  result.insert (CFFactor (LcF, 1));
183  return result;
184}
185
186/// factorize a multivariate polynomial over \f$ F_{p} (\alpha ) \f$
187///
188/// @return @a FqFactorize returns a list of monic factors with
189///         multiplicity, the first element is the leading coefficient.
190/// @sa FpFactorize(), GFFactorize()
191inline
192CFFList FqFactorize (const CanonicalForm& G, ///< [in] a multivariate poly
193                     const Variable& alpha,  ///< [in] algebraic variable
194                     bool substCheck= true   ///< [in] enables substitute check
195                    )
196{
197  if (getNumVars (G) == 2)
198    return FqBiFactorize (G, alpha, substCheck);
199
200  CanonicalForm F= G;
201  if (substCheck)
202  {
203    bool foundOne= false;
204    int * substDegree= new int [F.level()];
205    for (int i= 1; i <= F.level(); i++)
206    {
207      if (degree (F, i) > 0)
208      {
209        substDegree[i-1]= substituteCheck (F, Variable (i));
210        if (substDegree [i-1] > 1)
211        {
212          foundOne= true;
213          subst (F, F, substDegree[i-1], Variable (i));
214        }
215      }
216      else
217        substDegree[i-1]= -1;
218    }
219    if (foundOne)
220    {
221      CFFList result= FqFactorize (F, alpha, false);
222      CFFList newResult, tmp;
223      CanonicalForm tmp2;
224      newResult.insert (result.getFirst());
225      result.removeFirst();
226      for (CFFListIterator i= result; i.hasItem(); i++)
227      {
228        tmp2= i.getItem().factor();
229        for (int j= 1; j <= G.level(); j++)
230        {
231          if (substDegree[j-1] > 1)
232            tmp2= reverseSubst (tmp2, substDegree[j-1], Variable (j));
233        }
234        tmp= FqFactorize (tmp2, alpha, false);
235        tmp.removeFirst();
236        for (CFFListIterator j= tmp; j.hasItem(); j++)
237          newResult.append (CFFactor (j.getItem().factor(),
238                                      j.getItem().exp()*i.getItem().exp()));
239      }
240      delete [] substDegree;
241      return newResult;
242    }
243    delete [] substDegree;
244  }
245
246  ExtensionInfo info= ExtensionInfo (alpha, false);
247  CanonicalForm LcF= Lc (F);
248  CanonicalForm pthRoot, A;
249  CanonicalForm sqrfP= sqrfPart (F/Lc(F), pthRoot, alpha);
250  CFList buf, bufRoot;
251  CFFList result, resultRoot;
252  int p= getCharacteristic();
253  int q= ipower (p, degree (getMipo (alpha)));
254  int l;
255  if (degree (pthRoot) > 0)
256  {
257    pthRoot= maxpthRoot (pthRoot, q, l);
258    result= FqFactorize (pthRoot, alpha, false);
259    result.removeFirst();
260    for (CFFListIterator i= result; i.hasItem(); i++)
261      i.getItem()= CFFactor(i.getItem().factor(),i.getItem().exp()*ipower(p,l));
262    result.insert (CFFactor (LcF, 1));
263    return result;
264  }
265  else
266  {
267    buf= multiFactorize (sqrfP, info);
268    A= F/LcF;
269    result= multiplicity (A, buf);
270  }
271  if (degree (A) > 0)
272  {
273    resultRoot= FqFactorize (A, alpha, false);
274    resultRoot.removeFirst();
275    result= Union (result, resultRoot);
276  }
277  result.insert (CFFactor (LcF, 1));
278  return result;
279}
280
281/// factorize a multivariate polynomial over GF
282///
283/// @return @a GFFactorize returns a list of monic factors with
284///         multiplicity, the first element is the leading coefficient.
285/// @sa FpFactorize(), FqFactorize()
286inline
287CFFList GFFactorize (const CanonicalForm& G, ///< [in] a multivariate poly
288                     bool substCheck= true   ///< [in] enables substitute check
289                    )
290{
291  ASSERT (CFFactory::gettype() == GaloisFieldDomain,
292          "GF as base field expected");
293  if (getNumVars (G) == 2)
294    return GFBiFactorize (G, substCheck);
295
296  CanonicalForm F= G;
297  if (substCheck)
298  {
299    bool foundOne= false;
300    int * substDegree= new int [F.level()];
301    for (int i= 1; i <= F.level(); i++)
302    {
303      if (degree (F, i) > 0)
304      {
305        substDegree[i-1]= substituteCheck (F, Variable (i));
306        if (substDegree [i-1] > 1)
307        {
308          foundOne= true;
309          subst (F, F, substDegree[i-1], Variable (i));
310        }
311      }
312      else
313        substDegree[i-1]= -1;
314    }
315    if (foundOne)
316    {
317      CFFList result= GFFactorize (F, false);
318      CFFList newResult, tmp;
319      CanonicalForm tmp2;
320      newResult.insert (result.getFirst());
321      result.removeFirst();
322      for (CFFListIterator i= result; i.hasItem(); i++)
323      {
324        tmp2= i.getItem().factor();
325        for (int j= 1; j <= G.level(); j++)
326        {
327          if (substDegree[j-1] > 1)
328            tmp2= reverseSubst (tmp2, substDegree[j-1], Variable (j));
329        }
330        tmp= GFFactorize (tmp2, false);
331        tmp.removeFirst();
332        for (CFFListIterator j= tmp; j.hasItem(); j++)
333          newResult.append (CFFactor (j.getItem().factor(),
334                                      j.getItem().exp()*i.getItem().exp()));
335      }
336      delete [] substDegree;
337      return newResult;
338    }
339    delete [] substDegree;
340  }
341
342  Variable a= Variable (1);
343  ExtensionInfo info= ExtensionInfo (getGFDegree(), gf_name, false);
344  CanonicalForm LcF= Lc (F);
345  CanonicalForm pthRoot, A;
346  CanonicalForm sqrfP= sqrfPart (F/LcF, pthRoot, a);
347  CFList buf;
348  CFFList result, resultRoot;
349  int p= getCharacteristic();
350  int q= ipower (p, getGFDegree());
351  int l;
352  if (degree (pthRoot) > 0)
353  {
354    pthRoot= maxpthRoot (pthRoot, q, l);
355    result= GFFactorize (pthRoot, false);
356    result.removeFirst();
357    for (CFFListIterator i= result; i.hasItem(); i++)
358      i.getItem()= CFFactor(i.getItem().factor(),i.getItem().exp()*ipower(p,l));
359    result.insert (CFFactor (LcF, 1));
360    return result;
361  }
362  else
363  {
364    buf= multiFactorize (sqrfP, info);
365    A= F/LcF;
366    result= multiplicity (A, buf);
367  }
368  if (degree (A) > 0)
369  {
370    resultRoot= GFFactorize (A, false);
371    resultRoot.removeFirst();
372    result= Union (result, resultRoot);
373  }
374  result.insert (CFFactor (LcF, 1));
375  return result;
376}
377
378#endif
379
380/// Naive factor recombination for multivariate factorization over an extension
381/// of the initial field. No precomputed is used to exclude combinations.
382///
383/// @return @a extFactorRecombination returns a list of factors of @a F, whose
384///         shift to zero is reversed.
385/// @sa factorRecombination()
386CFList
387extFactorRecombination (
388                 const CFList& factors,     ///< [in] list of lifted factors
389                                            ///< that are monic wrt Variable (1)
390                 const CanonicalForm& F,    ///< [in] poly to be factored
391                 const CFList& M,           ///< [in] a list of powers of
392                                            ///< Variables
393                 const ExtensionInfo& info, ///< [in] info about extension
394                 const CFList& evaluation   ///< [in] evaluation point
395                       );
396
397/// Naive factor recombination for multivariate factorization.
398/// No precomputed is used to exclude combinations.
399///
400/// @return @a factorRecombination returns a list of factors of @a F
401/// @sa extFactorRecombination()
402CFList
403factorRecombination (const CanonicalForm& F,///< [in] poly to be factored
404                     const CFList& factors, ///< [in] list of lifted factors
405                                            ///< that are monic wrt Variable (1)
406                     const CFList& M        ///< [in] a list of powers of
407                                            ///< Variables
408                    );
409
410/// recombination of bivariate factors @a factors1 s. t. the result evaluated
411/// at @a evalPoint coincides with @a factors2
412CFList
413recombination (const CFList& factors1,        ///<[in] list of bivariate factors
414               const CFList& factors2,        ///<[in] list univariate factors
415               int s,                         ///<[in] algorithm starts checking
416                                              ///<  subsets of size s
417               int thres,                     ///<[in] threshold for the size of
418                                              ///<  subsets which are checked
419               const CanonicalForm& evalPoint,///<[in] evaluation point
420               const Variable& x              ///<[in] second variable of
421                                              ///< bivariate factors
422              );
423
424/// Lift bound adaption. Essentially an early factor detection but only the lift
425/// bound is adapted.
426///
427/// @return @a liftBoundAdaption returns an adapted lift bound.
428/// @sa earlyFactorDetect(), earlyFactorDetection()
429int
430liftBoundAdaption (const CanonicalForm& F, ///< [in] a poly
431                   const CFList& factors,  ///< [in] list of list of lifted
432                                           ///< factors that are monic wrt
433                                           ///< Variable (1)
434                   bool& success,          ///< [in,out] indicates that no
435                                           ///< further lifting is necessary
436                   const int deg,          ///< [in] stage of Hensel lifting
437                   const CFList& MOD,      ///< [in] a list of powers of
438                                           ///< Variables
439                   const int bound         ///< [in] initial lift bound
440                  );
441
442/// Lift bound adaption over an extension of the initial field. Essentially an
443///early factor detection but only the lift bound is adapted.
444///
445/// @return @a liftBoundAdaption returns an adapted lift bound.
446/// @sa earlyFactorDetect(), earlyFactorDetection()
447int
448extLiftBoundAdaption (
449            const CanonicalForm& F,    ///< [in] a poly
450            const CFList& factors,     ///< [in] list of list of lifted
451                                       ///< factors that are monic wrt
452            bool& success,             ///< [in,out] indicates that no further
453                                       ///< lifting is necessary
454            const ExtensionInfo& info, ///< [in] info about extension
455            const CFList& eval,        ///< [in] evaluation point
456            const int deg,             ///< [in] stage of Hensel lifting
457            const CFList& MOD,         ///< [in] a list of powers of
458                                       ///< Variables
459            const int bound            ///< [in] initial lift bound
460                     );
461
462/// detects factors of @a F at stage @a deg of Hensel lifting.
463/// No combinations of more than one factor are tested. Lift bound is adapted.
464///
465/// @return @a earlyFactorDetect returns a list of factors of F (possibly
466///         incomplete), in case of success. Otherwise an empty list.
467/// @sa factorRecombination(), extEarlyFactorDetect()
468CFList
469earlyFactorDetect (
470                CanonicalForm& F,      ///< [in,out] poly to be factored,
471                                       ///< returns poly divided by detected
472                                       ///< factors in case of success
473                CFList& factors,       ///< [in,out] list of factors lifted up
474                                       ///< to @a deg, returns a list of factors
475                                       ///< without detected factors
476                int& adaptedLiftBound, ///< [in,out] adapted lift bound
477                bool& success,         ///< [in,out] indicating success
478                const int deg,         ///< [in] stage of Hensel lifting
479                const CFList& MOD,     ///< [in] a list of powers of
480                                       ///< Variables
481                const int bound        ///< [in] initial lift bound
482                  );
483
484/// detects factors of @a F at stage @a deg of Hensel lifting.
485/// No combinations of more than one factor are tested. Lift bound is adapted.
486///
487/// @return @a extEarlyFactorDetect returns a list of factors of F (possibly
488///         incomplete), whose shift to zero is reversed, in case of success.
489///         Otherwise an empty list.
490/// @sa factorRecombination(), earlyFactorDetection()
491CFList
492extEarlyFactorDetect (
493            CanonicalForm& F,          ///< [in,out] poly to be factored,
494                                       ///< returns poly divided by detected
495                                       ///< factors in case of success
496            CFList& factors,           ///< [in,out] list of factors lifted up
497                                       ///< to @a deg, returns a list of factors
498                                       ///< without detected factors
499            int& adaptedLiftBound,     ///< [in,out] adapted lift bound
500            bool& success,             ///< [in,out] indicating succes
501            const ExtensionInfo& info, ///< [in] info about extension
502            const CFList& eval,        ///< [in] evaluation point
503            const int deg,             ///< [in] stage of Hensel lifting
504            const CFList& MOD,         ///< [in] a list of powers of Variables
505            const int bound            ///< [in] initial lift bound
506                     );
507
508/// evaluation point search for multivariate factorization,
509/// looks for a (F.level() - 1)-tuple such that the resulting univariate
510/// polynomial has main variable Variable (1), is squarefree and its degree
511/// coincides with degree(F) and the bivariate one is primitive wrt.
512/// Variable(1), and successively evaluated polynomials have the same degree in
513/// their main variable as F has, fails if there are no valid evaluation points,
514/// eval contains the intermediate evaluated polynomials.
515///
516/// @return @a evalPoints returns an evaluation point, which is valid if and
517///         only if fail == false.
518CFList
519evalPoints (const CanonicalForm& F,  ///< [in] a compressed poly
520            CFList & eval,           ///< [in,out] an empty list, returns @a F
521                                     ///< successive evaluated
522            const Variable& alpha,   ///< [in] algebraic variable
523            CFList& list,            ///< [in,out] a list of points already
524                                     ///< considered, a point is encoded as a
525                                     ///< poly of degree F.level()-1 in
526                                     ///< Variable(1)
527            const bool& GF,          ///< [in] GF?
528            bool& fail               ///< [in,out] indicates failure
529           );
530
531/// hensel Lifting and early factor detection
532///
533/// @return @a henselLiftAndEarly returns monic (wrt Variable (1)) lifted
534///         factors without factors which have been detected at an early stage
535///         of Hensel lifting
536/// @sa earlyFactorDetectn(), extEarlyFactorDetect()
537CFList
538henselLiftAndEarly (
539            CanonicalForm& A,         ///< [in,out] poly to be factored,
540                                      ///< returns poly divided by detected
541                                      ///< factors, in case of success
542            CFList& MOD,              ///< [in,out] a list of powers of
543                                      ///< Variables
544            int*& liftBounds,         ///< [in,out] initial lift bounds, returns
545                                      ///< adapted lift bounds
546            bool& earlySuccess,       ///< [in,out] indicating success
547            CFList& earlyFactors,     ///< [in,out] early factors
548            const CFList& Aeval,      ///< [in] @a A successively evaluated at
549                                      ///< elements of @a evaluation
550            const CFList& biFactors,  ///< [in] bivariate factors
551            const CFList& evaluation, ///< [in] evaluation point
552            const ExtensionInfo& info ///< [in] info about extension
553                   );
554
555/// Factorization over an extension of initial field
556///
557/// @return @a extFactorize returns factorization of F over initial field
558/// @sa extBiFactorize(), multiFactorize()
559CFList
560extFactorize (const CanonicalForm& F,   ///< [in] poly to be factored
561              const ExtensionInfo& info ///< [in] info about extension
562             );
563
564/// compute the LCM of the contents of @a A wrt to each variable occuring in @a
565/// A.
566///
567/// @return @a lcmContent returns the LCM of the contents of @a A wrt to each
568///         variable occuring in @a A.
569CanonicalForm
570lcmContent (const CanonicalForm& A, ///< [in] a compressed multivariate poly
571            CFList& contentAi       ///< [in,out] an empty list, returns a list
572                                    ///< of the contents of @a A wrt to each
573                                    ///< variable occuring in @a A starting from
574                                    ///< @a A.mvar().
575           );
576
577/// compress a polynomial s.t. \f$ deg_{x_{i}} (F) >= deg_{x_{i+1}} (F) \f$ and
578/// no gaps between the variables occur
579///
580/// @return a compressed poly with the above properties
581CanonicalForm myCompress (const CanonicalForm& F, ///< [in] a poly
582                          CFMap& N                ///< [in,out] a map to
583                                                  ///< decompress
584                         );
585
586/// evaluate a poly A with main variable at level 1 at an evaluation point in
587/// K^(n-1) wrt different second variables. If this evaluation is valid (see
588/// evalPoints) then Aeval contains A successively evaluated at this point,
589/// otherwise this entry is empty
590void
591evaluationWRTDifferentSecondVars (
592                    CFList*& Aeval,          ///<[in,out] an array of length n-2
593                                             ///< if variable at level i > 2
594                                             ///< admits a valid evaluation
595                                             ///< this entry contains A
596                                             ///< successively evaluated at this
597                                             ///< point otherwise an empty list
598                    const CFList& evaluation,///<[in] a valid evaluation point
599                                             ///< for main variable at level 1
600                                             ///< and second variable at level 2
601                    const CanonicalForm& A   ///<[in] some poly
602                                 );
603
604/// evaluate F successively n-2 at 0
605///
606/// @return returns a list of successive evaluations of F, ending with F
607CFList evaluateAtZero (const CanonicalForm& F ///< [in] some poly
608                      );
609
610/// divides factors by their content wrt. Variable(1) and checks if these polys
611/// divide F
612///
613/// @return returns factors of F
614CFList recoverFactors (const CanonicalForm& F, ///< [in] some poly F
615                       const CFList& factors   ///< [in] some list of
616                                               ///< factor candidates
617                      );
618
619/// divides factors shifted by evaluation by their content wrt. Variable(1) and
620/// checks if these polys divide F
621///
622/// @return returns factors of F
623CFList recoverFactors (const CanonicalForm& F,  ///< [in] some poly F
624                       const CFList& factors,   ///< [in] some list of
625                                                ///< factor candidates
626                       const CFList& evaluation
627                      );
628
629/// refine a bivariate factorization of A with l factors to one with
630/// minFactorsLength
631void
632refineBiFactors (const CanonicalForm& A,  ///< [in] some poly
633                 CFList& biFactors,       ///< [in,out] list of bivariate to be
634                                          ///< refined, returns refined factors
635                 CFList* const& factors,  ///< [in] list of bivariate
636                                          ///< factorizations of A wrt different
637                                          ///< second variables
638                 const CFList& evaluation,///< [in] the evaluation point
639                 int minFactorsLength     ///< [in] the minimal number of factors
640                );
641
642/// plug in evalPoint for y in a list of polys
643///
644/// @return returns a list of the evaluated polys, these evaluated polys are
645/// made monic
646CFList
647buildUniFactors (const CFList& biFactors,       ///< [in] a list of polys
648                 const CanonicalForm& evalPoint,///< [in] some evaluation point
649                 const Variable& y              ///< [in] some variable
650                );
651
652/// extract leading coefficients wrt Variable(1) from bivariate factors obtained
653/// from factorizations of A wrt different second variables
654void
655getLeadingCoeffs (const CanonicalForm& A,  ///< [in] some poly
656                  CFList*& Aeval,          ///< [in,out] array of bivariate
657                                           ///< factors, returns the leading
658                                           ///< coefficients of these factors
659                  const CFList& uniFactors,///< [in] univariate factors of A
660                  const CFList& evaluation ///< [in] evaluation point
661                 );
662
663/// normalize precomputed leading coefficients such that leading coefficients
664/// evaluated at @a evaluation in K^(n-2) equal the leading coeffs wrt
665/// Variable(1) of bivariate factors
666void
667prepareLeadingCoeffs (CFList*& LCs,               ///<[in,out]
668                      int n,                      ///<[in] level of poly to be
669                                                  ///< factored
670                      const CFList& leadingCoeffs,///<[in] precomputed leading
671                                                  ///< coeffs
672                      const CFList& biFactors,    ///<[in] bivariate factors
673                      const CFList& evaluation    ///<[in] evaluation point
674                     );
675
676/// obtain factors of F by reconstructing their leading coeffs
677///
678/// @return returns the reconstructed factors
679/// @sa factorRecombination()
680CFList
681leadingCoeffReconstruction (const CanonicalForm& F,///<[in] poly to be factored
682                            const CFList& factors, ///<[in] factors of f monic
683                                                   ///< wrt Variable (1)
684                            const CFList& M        ///<[in] a list of powers of
685                                                   ///< Variables
686                           );
687
688/// distribute content
689///
690/// @return returns a list result of polys such that prod (result)= prod (L)
691/// but the first entry of L may be (partially) factorized and these factors
692/// are distributed onto other entries in L
693CFList
694distributeContent (
695          const CFList& L,                        ///<[in] list of polys, first
696                                                  ///< entry the content to be
697                                                  ///< distributed
698          const CFList* differentSecondVarFactors,///<[in] factorization wrt
699                                                  ///< different second vars
700          int length                              ///<[in] length of
701                                                  ///<differentSecondVarFactors
702                  );
703
704/// gcd free basis of two lists of factors
705void
706gcdFreeBasis (CFFList& factors1, ///< [in,out] list of factors, returns gcd free
707                                 ///< factors
708              CFFList& factors2  ///< [in,out] list of factors, returns gcd free
709                                 ///< factors
710             );
711
712/// heuristic algorithm for lifting sparse polynomials
713///
714/// @return a list of factors of A, possibly incomplete
715CFList
716sparseHeuristic (const CanonicalForm& A,  ///<[in] polynomial to be factored
717                 const CFList& biFactors, ///<[in] list of bivariate factors wrt
718                                          ///< Variable 1 and 2
719                 CFList*& moreBiFactors,  ///<[in,out] more bivariate factors
720                                          ///< wrt different second variables.
721                                          ///< May be recombined s.t. there are
722                                          ///< only minFactorsLength factors and
723                                          ///< resorted s.t. the sequence of
724                                          ///< univariate factors in biFactors
725                                          ///< and moreBiFactors coincides
726                 const CFList& evaluation,///<[in] evaluation point
727                 int minFactorsLength     ///<[in] minimal number of factors
728                );
729
730/// evaluate @a F at @a evaluation
731///
732/// @return @a evaluateAtEval returns a list containing the successive
733/// evaluations of @a F, last entry is @a F again
734CFList
735evaluateAtEval (const CanonicalForm& F,   ///<[in] some poly
736                const CFArray& evaluation ///<[in] some evaluation point
737               );
738
739/// evaluate @a F at @a evaluation
740///
741/// @return @a evaluateAtEval returns a list containing the successive
742/// evaluations of @a F starting at level @a l, last entry is @a F again
743CFList
744evaluateAtEval (const CanonicalForm& F,  ///<[in] some poly
745                const CFList& evaluation,///<[in] some evaluation point
746                int l                    ///<[in] level to start at
747               );
748
749#endif
750/* FAC_FQ_FACTORIZE_H */
751
Note: See TracBrowser for help on using the repository browser.