source: git/factory/facFactorize.h @ 3c702a

spielwiese
Last change on this file since 3c702a was 3c702a, checked in by Oleksandr Motsak <motsak@…>, 10 years ago
Public headers should not include private config.h
  • Property mode set to 100644
File size: 4.5 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 over Q (a)
26///
27/// @return @a multiFactorize returns a factorization of F
28CFList
29multiFactorize (const CanonicalForm& F,     ///< [in] poly to be factored
30                const Variable& v           ///< [in] some algebraic variable
31               );
32
33/// factorize a squarefree multivariate polynomial over \f$ Q(\alpha) \f$
34///
35/// @return @a ratSqrfFactorize returns a list of monic factors, the first
36///         element is the leading coefficient.
37#ifdef HAVE_NTL
38inline
39CFList
40ratSqrfFactorize (const CanonicalForm & G,        ///<[in] a multivariate poly
41                  const Variable& v= Variable (1) ///<[in] algebraic variable
42                 )
43{
44  if (getNumVars (G) == 2)
45    return ratBiSqrfFactorize (G, v);
46  CanonicalForm F= G;
47  if (isOn (SW_RATIONAL))
48    F *= bCommonDen (F);
49  CFList result= multiFactorize (F, v);
50  if (isOn (SW_RATIONAL))
51  {
52    normalize (result);
53    result.insert (Lc(F));
54  }
55  return result;
56}
57
58/// factorize a multivariate polynomial over \f$ Q(\alpha) \f$
59///
60/// @return @a ratFactorize returns a list of monic factors with
61///         multiplicity, the first element is the leading coefficient.
62inline
63CFFList
64ratFactorize (const CanonicalForm& G,          ///<[in] a multivariate poly
65              const Variable& v= Variable (1), ///<[in] algebraic variable
66              bool substCheck= true            ///<[in] enables substitute check
67             )
68{
69  if (getNumVars (G) == 2)
70  {
71    CFFList result= ratBiFactorize (G,v);
72    return result;
73  }
74  CanonicalForm F= G;
75
76  if (substCheck)
77  {
78    bool foundOne= false;
79    int * substDegree= new int [F.level()];
80    for (int i= 1; i <= F.level(); i++)
81    {
82      if (degree (F, i) > 0)
83      {
84        substDegree[i-1]= substituteCheck (F, Variable (i));
85        if (substDegree [i-1] > 1)
86        {
87          foundOne= true;
88          subst (F, F, substDegree[i-1], Variable (i));
89        }
90      }
91      else
92        substDegree[i-1]= -1;
93    }
94    if (foundOne)
95    {
96      CFFList result= ratFactorize (F, v, false);
97      CFFList newResult, tmp;
98      CanonicalForm tmp2;
99      newResult.insert (result.getFirst());
100      result.removeFirst();
101      for (CFFListIterator i= result; i.hasItem(); i++)
102      {
103        tmp2= i.getItem().factor();
104        for (int j= 1; j <= G.level(); j++)
105        {
106          if (substDegree[j-1] > 1)
107            tmp2= reverseSubst (tmp2, substDegree[j-1], Variable (j));
108        }
109        tmp= ratFactorize (tmp2, v, false);
110        tmp.removeFirst();
111        for (CFFListIterator j= tmp; j.hasItem(); j++)
112          newResult.append (CFFactor (j.getItem().factor(),
113                                      j.getItem().exp()*i.getItem().exp()));
114      }
115      delete [] substDegree;
116      return newResult;
117    }
118    delete [] substDegree;
119  }
120
121  CanonicalForm LcF= Lc (F);
122  if (isOn (SW_RATIONAL))
123    F *= bCommonDen (F);
124
125  CFFList result;
126  TIMING_START (fac_squarefree);
127  CFFList sqrfFactors= sqrFree (F);
128  TIMING_END_AND_PRINT (fac_squarefree,
129                        "time for squarefree factorization over Q: ");
130
131  CFList tmp;
132  for (CFFListIterator i= sqrfFactors; i.hasItem(); i++)
133  {
134    TIMING_START (fac_factor_squarefree);
135    tmp= ratSqrfFactorize (i.getItem().factor(), v);
136    TIMING_END_AND_PRINT (fac_factor_squarefree,
137                          "time to factorize sqrfree factor over Q: ");
138    for (CFListIterator j= tmp; j.hasItem(); j++)
139    {
140      if (j.getItem().inCoeffDomain()) continue;
141      result.append (CFFactor (j.getItem(), i.getItem().exp()));
142    }
143  }
144  if (isOn (SW_RATIONAL))
145  {
146    normalize (result);
147    if (v.level() == 1)
148    {
149      for (CFFListIterator i= result; i.hasItem(); i++)
150      {
151        LcF /= power (bCommonDen (i.getItem().factor()), i.getItem().exp());
152        i.getItem()= CFFactor (i.getItem().factor()*
153                     bCommonDen(i.getItem().factor()), i.getItem().exp());
154      }
155    }
156    result.insert (CFFactor (LcF, 1));
157  }
158  return result;
159}
160#endif
161
162#endif
163
Note: See TracBrowser for help on using the repository browser.