# source:git/factory/facFactorize.h@091b250

spielwiese
Last change on this file since 091b250 was 091b250, checked in by Martin Lee <martinlee84@…>, 10 years ago
• Property mode set to 100644
File size: 5.2 KB
Line
1/*****************************************************************************\
2 * Computer Algebra System SINGULAR
3\*****************************************************************************/
4/** @file facFactorize.h
5 *
6 * multivariate factorization over Q(a)
7 *
8 * @author Martin Lee
9 *
10 **/
11/*****************************************************************************/
12
13#ifndef FAC_FACTORIZE_H
14#define FAC_FACTORIZE_H
15
16// #include "config.h"
17#include "timing.h"
18
19#include "facBivar.h"
20#include "facFqBivarUtil.h"
21
22TIMING_DEFINE_PRINT (fac_squarefree)
23TIMING_DEFINE_PRINT (fac_factor_squarefree)
24
25/// Factorization of A wrt. to different second vars
26void
27factorizationWRTDifferentSecondVars (
28                          const CanonicalForm& A, ///<[in] poly
29                          CFList*& Aeval,         ///<[in,out] A evaluated wrt.
30                                                  ///< different second vars
31                                                  ///< returns bivariate factors
32                          int& minFactorsLength,  ///<[in,out] minimal length of
33                                                  ///< bivariate factors
34                          bool& irred,            ///<[in,out] Is A irreducible?
35                          const Variable& w       ///<[in] alg. variable
36                                    );
37
38/// Factorization over Q (a)
39///
40/// @return @a multiFactorize returns a factorization of F
41CFList
42multiFactorize (const CanonicalForm& F,     ///< [in] poly to be factored
43                const Variable& v           ///< [in] some algebraic variable
44               );
45
46/// factorize a squarefree multivariate polynomial over \f$Q(\alpha) \f$
47///
48/// @return @a ratSqrfFactorize returns a list of monic factors, the first
49///         element is the leading coefficient.
50#ifdef HAVE_NTL
51inline
52CFList
53ratSqrfFactorize (const CanonicalForm & G,        ///<[in] a multivariate poly
54                  const Variable& v= Variable (1) ///<[in] algebraic variable
55                 )
56{
57  if (getNumVars (G) == 2)
58    return ratBiSqrfFactorize (G, v);
59  CanonicalForm F= G;
60  if (isOn (SW_RATIONAL))
61    F *= bCommonDen (F);
62  CFList result= multiFactorize (F, v);
63  if (isOn (SW_RATIONAL))
64  {
65    normalize (result);
66    result.insert (Lc(F));
67  }
68  return result;
69}
70
71/// factorize a multivariate polynomial over \f$Q(\alpha) \f$
72///
73/// @return @a ratFactorize returns a list of monic factors with
74///         multiplicity, the first element is the leading coefficient.
75inline
76CFFList
77ratFactorize (const CanonicalForm& G,          ///<[in] a multivariate poly
78              const Variable& v= Variable (1), ///<[in] algebraic variable
79              bool substCheck= true            ///<[in] enables substitute check
80             )
81{
82  if (getNumVars (G) == 2)
83  {
84    CFFList result= ratBiFactorize (G,v);
85    return result;
86  }
87  CanonicalForm F= G;
88
89  if (substCheck)
90  {
91    bool foundOne= false;
92    int * substDegree= new int [F.level()];
93    for (int i= 1; i <= F.level(); i++)
94    {
95      if (degree (F, i) > 0)
96      {
97        substDegree[i-1]= substituteCheck (F, Variable (i));
98        if (substDegree [i-1] > 1)
99        {
100          foundOne= true;
101          subst (F, F, substDegree[i-1], Variable (i));
102        }
103      }
104      else
105        substDegree[i-1]= -1;
106    }
107    if (foundOne)
108    {
109      CFFList result= ratFactorize (F, v, false);
110      CFFList newResult, tmp;
111      CanonicalForm tmp2;
112      newResult.insert (result.getFirst());
113      result.removeFirst();
114      for (CFFListIterator i= result; i.hasItem(); i++)
115      {
116        tmp2= i.getItem().factor();
117        for (int j= 1; j <= G.level(); j++)
118        {
119          if (substDegree[j-1] > 1)
120            tmp2= reverseSubst (tmp2, substDegree[j-1], Variable (j));
121        }
122        tmp= ratFactorize (tmp2, v, false);
123        tmp.removeFirst();
124        for (CFFListIterator j= tmp; j.hasItem(); j++)
125          newResult.append (CFFactor (j.getItem().factor(),
126                                      j.getItem().exp()*i.getItem().exp()));
127      }
128      delete [] substDegree;
129      return newResult;
130    }
131    delete [] substDegree;
132  }
133
134  CanonicalForm LcF= Lc (F);
135  if (isOn (SW_RATIONAL))
136    F *= bCommonDen (F);
137
138  CFFList result;
139  TIMING_START (fac_squarefree);
140  CFFList sqrfFactors= sqrFree (F);
141  TIMING_END_AND_PRINT (fac_squarefree,
142                        "time for squarefree factorization over Q: ");
143
144  CFList tmp;
145  for (CFFListIterator i= sqrfFactors; i.hasItem(); i++)
146  {
147    TIMING_START (fac_factor_squarefree);
148    tmp= ratSqrfFactorize (i.getItem().factor(), v);
149    TIMING_END_AND_PRINT (fac_factor_squarefree,
150                          "time to factorize sqrfree factor over Q: ");
151    for (CFListIterator j= tmp; j.hasItem(); j++)
152    {
153      if (j.getItem().inCoeffDomain()) continue;
154      result.append (CFFactor (j.getItem(), i.getItem().exp()));
155    }
156  }
157  if (isOn (SW_RATIONAL))
158  {
159    normalize (result);
160    if (v.level() == 1)
161    {
162      for (CFFListIterator i= result; i.hasItem(); i++)
163      {
164        LcF /= power (bCommonDen (i.getItem().factor()), i.getItem().exp());
165        i.getItem()= CFFactor (i.getItem().factor()*
166                     bCommonDen(i.getItem().factor()), i.getItem().exp());
167      }
168    }
169    result.insert (CFFactor (LcF, 1));
170  }
171  return result;
172}
173#endif
174
175#endif
176
Note: See TracBrowser for help on using the repository browser.