source: git/factory/facFqSquarefree.cc @ 9752db

spielwiese
Last change on this file since 9752db was 6caa2a6, checked in by Martin Lee <martinlee84@…>, 12 years ago
chg: avoid adding of constant factors to squarefree factorization chg: divide out contents first in squarefree factorization
  • Property mode set to 100644
File size: 5.7 KB
Line 
1/*****************************************************************************\
2 * Computer Algebra System SINGULAR
3\*****************************************************************************/
4/** @file facFqSquarefree.cc
5 *
6 * This file provides functions for squarefrees factorizing over
7 * \f$ F_{p} \f$ , \f$ F_{p}(\alpha ) \f$ or GF, as decribed in "Factoring
8 * multivariate polynomials over a finite field" by L. Bernardin
9 *
10 * @author Martin Lee
11 *
12 * @internal @version \$Id$
13 *
14 **/
15/*****************************************************************************/
16
17#include "config.h"
18
19#include "canonicalform.h"
20
21#include "cf_gcd_smallp.h"
22#include "cf_iter.h"
23#include "cf_map.h"
24#include "cf_util.h"
25#include "cf_factory.h"
26#include "facFqSquarefree.h"
27
28static inline
29CanonicalForm
30pthRoot (const CanonicalForm & F, const int & q)
31{
32  CanonicalForm A= F;
33  int p= getCharacteristic ();
34  if (A.inCoeffDomain())
35  {
36    A= power (A, q/p);
37    return A;
38  }
39  else
40  {
41    CanonicalForm buf= 0;
42    for (CFIterator i= A; i.hasTerms(); i++)
43      buf= buf + power(A.mvar(), i.exp()/p)*pthRoot (i.coeff(), q);
44    return buf;
45  }
46}
47
48CanonicalForm
49maxpthRoot (const CanonicalForm & F, const int & q, int& l)
50{
51  CanonicalForm result= F;
52  bool derivZero= true;
53  l= 0;
54  while (derivZero)
55  {
56    for (int i= 1; i <= result.level(); i++)
57    {
58      if (!deriv (result, Variable (i)).isZero())
59      {
60        derivZero= false;
61        break;
62      }
63    }
64    if (!derivZero)
65      break;
66    result= pthRoot (result, q);
67    l++;
68  }
69  return result;
70}
71
72static inline
73CFFList
74sqrfPosDer (const CanonicalForm & F, const Variable & x,
75            CanonicalForm & c)
76{
77  CanonicalForm b= deriv (F, x);
78  c= gcd (F, b);
79  CanonicalForm w= F/c;
80  CanonicalForm v= b/c;
81  CanonicalForm u= v - deriv (w, x);
82  int j= 1;
83  int p= getCharacteristic();
84  CanonicalForm g;
85  CFFList result;
86  while (j < p - 1 && degree(u) >= 0)
87  {
88    g= gcd (w, u);
89    if (!g.inCoeffDomain())
90      result.append (CFFactor (g, j));
91    w= w/g;
92    c= c/w;
93    v= u/g;
94    u= v - deriv (w, x);
95    j++;
96  }
97  if (!w.inCoeffDomain())
98    result.append (CFFactor (w, j));
99  return result;
100}
101
102CFFList
103squarefreeFactorization (const CanonicalForm & F, const Variable & alpha)
104{
105  int p= getCharacteristic();
106  CanonicalForm A= F;
107  CFMap M;
108  A= compress (A, M);
109  Variable x= A.mvar();
110  int l= x.level();
111  int k;
112  if (CFFactory::gettype() == GaloisFieldDomain)
113    k= getGFDegree();
114  else if (alpha.level() != 1)
115    k= degree (getMipo (alpha));
116  else
117    k= 1;
118  Variable buf, buf2;
119  CanonicalForm tmp;
120
121  CFFList tmp1, tmp2;
122  bool found;
123  for (int i= l; i > 0; i--)
124  {
125    buf= Variable (i);
126    if (degree (deriv (A, buf)) >= 0)
127    {
128      tmp1= sqrfPosDer (A, buf, tmp);
129      A= tmp;
130      for (CFFListIterator j= tmp1; j.hasItem(); j++)
131      {
132        found= false;
133        CFFListIterator k= tmp2;
134        if (!k.hasItem() && !j.getItem().factor().inCoeffDomain()) tmp2.append (j.getItem());
135        else
136        {
137          for (; k.hasItem(); k++)
138          {
139            if (k.getItem().exp() == j.getItem().exp())
140            {
141              k.getItem()= CFFactor (k.getItem().factor()*j.getItem().factor(),
142                                     j.getItem().exp());
143              found= true;
144            }
145          }
146          if (found == false && !j.getItem().factor().inCoeffDomain())
147            tmp2.append(j.getItem());
148        }
149      }
150    }
151  }
152
153  bool degcheck= false;;
154  for (int i= l; i > 0; i--)
155  if (degree (A, Variable(i)) >= p)
156    degcheck= true;
157
158  if (degcheck == false && tmp1.isEmpty() && tmp2.isEmpty())
159    return CFFList (CFFactor (F/Lc(F), 1));
160
161  CanonicalForm buffer= pthRoot (A, ipower (p, k));
162
163  tmp1= squarefreeFactorization (buffer, alpha);
164
165  CFFList result;
166  buf= alpha;
167  for (CFFListIterator i= tmp2; i.hasItem(); i++)
168  {
169    for (CFFListIterator j= tmp1; j.hasItem(); j++)
170    {
171      tmp= gcd (i.getItem().factor(), j.getItem().factor());
172      i.getItem()= CFFactor (i.getItem().factor()/tmp, i.getItem().exp());
173      j.getItem()= CFFactor (j.getItem().factor()/tmp, j.getItem().exp());
174      if (!tmp.inCoeffDomain())
175      {
176        tmp= M (tmp);
177        result.append (CFFactor (tmp/Lc(tmp),
178                       j.getItem().exp()*p + i.getItem().exp()));
179      }
180    }
181  }
182  for (CFFListIterator i= tmp2; i.hasItem(); i++)
183  {
184    if (!i.getItem().factor().inCoeffDomain())
185    {
186      tmp= M (i.getItem().factor());
187      result.append (CFFactor (tmp/Lc(tmp), i.getItem().exp()));
188    }
189  }
190  for (CFFListIterator j= tmp1; j.hasItem(); j++)
191  {
192    if (!j.getItem().factor().inCoeffDomain())
193    {
194      tmp= M (j.getItem().factor());
195      result.append (CFFactor (tmp/Lc(tmp), j.getItem().exp()*p));
196    }
197  }
198  return result;
199}
200
201CanonicalForm
202sqrfPart (const CanonicalForm& F, CanonicalForm& pthPower,
203          const Variable& alpha)
204{
205  if (F.inCoeffDomain())
206  {
207    pthPower= 1;
208    return F;
209  }
210  CFMap M;
211  CanonicalForm A= compress (F, M);
212  Variable vBuf= alpha;
213  CanonicalForm w, v, b;
214  pthPower= 1;
215  CanonicalForm result;
216  int i= 1;
217  bool allZero= true;
218  for (; i <= A.level(); i++)
219  {
220    if (!deriv (A, Variable (i)).isZero())
221    {
222      allZero= false;
223      break;
224    }
225  }
226  if (allZero)
227  {
228    pthPower= F;
229    return 1;
230  }
231  w= gcd (A, deriv (A, Variable (i)));
232
233  b= A/w;
234  result= b;
235  if (degree (w) < 1)
236    return M (result);
237  i++;
238  for (; i <= A.level(); i++)
239  {
240    if (!deriv (w, Variable (i)).isZero())
241    {
242      b= w;
243      w= gcd (w, deriv (w, Variable (i)));
244      b /= w;
245      if (degree (b) < 1)
246        break;
247      CanonicalForm g;
248      g= gcd (b, result);
249      if (degree (g) > 0)
250        result *= b/g;
251      if (degree (g) <= 0)
252        result *= b;
253    }
254  }
255  result= M (result);
256  return result;
257}
258
Note: See TracBrowser for help on using the repository browser.