facAlgExt.cc
Go to the documentation of this file.
1 // -*- c++ -*-
2 //*****************************************************************************
3 /** @file facAlgExt.cc
4  *
5  * Univariate factorization over algebraic extension of Q using Trager's
6  * algorithm
7  *
8  * @par Copyright:
9  * (c) by The SINGULAR Team, see LICENSE file
10  *
11  * @author Martin Lee
12 **/
13 //*****************************************************************************
14 
15 
16 #include "config.h"
17 
18 
19 #include "cf_assert.h"
20 #include "debug.h"
21 #include "timing.h"
22 
23 #include "canonicalform.h"
24 #include "cf_random.h"
25 #include "cf_algorithm.h"
26 #include "facFqBivarUtil.h"
27 #include "facAlgExt.h"
28 #include "cfModResultant.h"
29 #include "fac_sqrfree.h"
30 
31 TIMING_DEFINE_PRINT(fac_alg_resultant)
32 TIMING_DEFINE_PRINT(fac_alg_norm)
33 TIMING_DEFINE_PRINT(fac_alg_factor_norm)
34 TIMING_DEFINE_PRINT(fac_alg_gcd)
35 TIMING_DEFINE_PRINT(fac_alg_sqrf)
36 TIMING_DEFINE_PRINT(fac_alg_factor_sqrf)
37 TIMING_DEFINE_PRINT(fac_alg_time_shift)
38 
39 // squarefree part of F
40 static CanonicalForm uniSqrfPart (const CanonicalForm& F)
41 {
42  ASSERT (F.isUnivariate(), "univariate input expected");
43  ASSERT (getCharacteristic() == 0, "characteristic 0 expected");
44  CanonicalForm G= deriv (F, F.mvar());
45  G= gcd (F, G);
46  return F/G;
47 }
48 
49 static CanonicalForm Norm (const CanonicalForm& F, const Variable& alpha)
50 {
51  Variable x= Variable (F.level() + 1);
52  Variable y= F.mvar();
53  CanonicalForm g= F (x, alpha);
54  CanonicalForm mipo= getMipo (alpha);
55  mipo= mipo (x, alpha);
56  mipo *= bCommonDen (mipo);
57 
58  int degg= degree (g);
59  int degmipo= degree (mipo);
61  TIMING_START (fac_alg_resultant);
62 #ifdef HAVE_NTL
63  if (degg >= 8 || degmipo >= 8)
64  norm= resultantZ (g, mipo, x);
65  else
66 #endif
67  norm= resultant (g, mipo, x);
68  TIMING_END_AND_PRINT (fac_alg_resultant, "time to compute resultant0: ");
69  return norm;
70 }
71 
72 // i is an integer such that Norm (F (x-i*alpha)) is squarefree
73 static CanonicalForm sqrfNorm (const CanonicalForm& F, const Variable& alpha, int& i)
74 {
75  Variable x= Variable (F.level() + 1);
76  Variable y= F.mvar();
77  CanonicalForm g= F (x, alpha);
78  CanonicalForm mipo= getMipo (alpha);
79  mipo= mipo (x, alpha);
80  mipo *= bCommonDen (mipo);
81 
82  int degg= degree (g);
83  int degmipo= degree (mipo);
85  TIMING_START (fac_alg_resultant);
86 #ifdef HAVE_NTL
87  if (degg >= 8 || degmipo >= 8)
88  norm= resultantZ (g, mipo, x);
89  else
90 #endif
91  norm= resultant (g, mipo, x);
92  TIMING_END_AND_PRINT (fac_alg_resultant, "time to compute resultant0: ");
93 
94  i= 0;
95  int k;
96  if (degree (gcd (deriv (norm, y), norm)) <= 0)
97  return norm;
98  i= 1;
99  do
100  {
101  k= 1;
102  while (k < 3)
103  {
104  if (k == 1)
105  {
106  g= F (y - i*alpha, y);
107  g *= bCommonDen (g);
108  TIMING_START (fac_alg_resultant);
109 #ifdef HAVE_NTL
110  if (degg >= 8 || degmipo >= 8)
111  norm= resultantZ (g (x, alpha), mipo, x);
112  else
113 #endif
114  norm= resultant (g (x, alpha), mipo, x);
115  TIMING_END_AND_PRINT (fac_alg_resultant,"time to compute resultant1: ");
116  }
117  else
118  {
119  g= F (y + i*alpha, y);
120  g *= bCommonDen (g);
121  TIMING_START (fac_alg_resultant);
122 #ifdef HAVE_NTL
123  if (degg >= 8 || degmipo >= 8)
124  norm= resultantZ (g (x, alpha), mipo, x);
125  else
126 #endif
127  norm= resultant (g (x, alpha), mipo, x);
128  TIMING_END_AND_PRINT (fac_alg_resultant,"time to compute resultant2: ");
129  }
130  if (degree (gcd (deriv (norm, y), norm)) <= 0)
131  {
132  if (k == 2)
133  i= -i;
134  return norm;
135  }
136  k++;
137  }
138  i++;
139  } while (1);
140 }
141 
143 {
144  ASSERT (F.isUnivariate(), "univariate input expected");
145  ASSERT (getCharacteristic() == 0, "characteristic 0 expected");
146 
147  bool save_rat=!isOn (SW_RATIONAL);
148  On (SW_RATIONAL);
149  CanonicalForm f= F*bCommonDen (F);
150  Variable y= f.mvar();
151  int shift= 0, k= 0, count= 0;
152  CanonicalForm norm, buf, factor, oldF;
153  CFFList normFactors;
154  bool save_sort= !isOn (SW_USE_NTL_SORT);
155  CFList factors, tmp, tmp2;
158  bool shiftBuf= false;
159 
160  tmp.append (f);
161  do
162  {
163  tmp2= CFList();
164  for (iter= tmp; iter.hasItem(); iter++)
165  {
166  oldF= iter.getItem()*bCommonDen (iter.getItem());
167  if (shift == 0)
168  f= oldF;
169  else
170  {
171  f= oldF (y - shift*alpha, y);
172  f *= bCommonDen (f);
173  }
174  TIMING_START (fac_alg_norm);
175  norm= Norm (f, alpha);
176  TIMING_END_AND_PRINT (fac_alg_norm, "time to compute sqrf norm: ");
177  ASSERT (degree (norm, alpha) <= 0, "wrong norm computed");
178 
179  TIMING_START (fac_alg_factor_norm);
181  normFactors= factorize (norm);
182  if (save_sort)
184  TIMING_END_AND_PRINT (fac_alg_factor_norm, "time to factor norm: ");
185 
186  if (normFactors.getFirst().factor().inCoeffDomain())
187  normFactors.removeFirst();
188  if (normFactors.length() < 2 && normFactors.getLast().exp() == 1)
189  {
190  factors.append (oldF);
191  continue;
192  }
193 
194  i= normFactors;
195  shiftBuf= false;
196  if (!(normFactors.length() == 2 &&
197  degree (i.getItem().factor()) <= degree (f)))
198  {
199  TIMING_START (fac_alg_time_shift);
200  if (shift != 0)
201  buf= f;
202  else
203  buf= oldF;
204  shiftBuf= true;
205  TIMING_END_AND_PRINT (fac_alg_time_shift, "time to shift: ");
206  }
207  else
208  buf= oldF;
209 
210  count= 0;
211  for (; i.hasItem(); i++)
212  {
213  TIMING_START (fac_alg_gcd);
214  if (shiftBuf)
215  factor= gcd (buf, i.getItem().factor());
216  else
217  {
218  if (shift == 0)
219  factor= gcd (buf, i.getItem().factor());
220  else
221  factor= gcd (buf, i.getItem().factor() (y + shift*alpha, y));
222  }
223  buf /= factor;
224  if (shiftBuf)
225  {
226  if (shift != 0)
227  factor= factor (y + shift*alpha, y);
228  }
229  TIMING_END_AND_PRINT (fac_alg_gcd, "time to recover factors: ");
230  if (i.getItem().exp() == 1 || degree (factor) == 1)
231  factors.append (factor);
232  else
233  tmp2.append (factor);
234  if (buf.inCoeffDomain())
235  break;
236  count++;
237  if (normFactors.length() - 1 == count)
238  {
239  if (shiftBuf)
240  {
241  if (normFactors.getLast().exp() == 1)
242  factors.append (buf (y + shift*alpha, y));
243  else
244  tmp2.append (buf (y + shift*alpha, y));
245  }
246  else
247  {
248  if (normFactors.getLast().exp() == 1)
249  factors.append (buf);
250  else
251  tmp2.append (buf);
252  }
253  buf= 1;
254  break;
255  }
256  }
257  }
258  k++;
259  if (shift == 0)
260  {
261  shift++;
262  k= 1;
263  }
264  if (k == 2)
265  shift= -shift;
266  if (k == 3)
267  {
268  shift= -shift;
269  shift++;
270  k= 1;
271  }
272  tmp= tmp2;
273  }
274  while (!tmp.isEmpty());
275 
276  if (save_rat) Off(SW_RATIONAL);
277  return factors;
278 }
279 
280 
281 /*CFList
282 AlgExtSqrfFactorize (const CanonicalForm& F, const Variable& alpha)
283 {
284  ASSERT (F.isUnivariate(), "univariate input expected");
285  ASSERT (getCharacteristic() == 0, "characteristic 0 expected");
286 
287  bool save_rat=!isOn (SW_RATIONAL);
288  On (SW_RATIONAL);
289  CanonicalForm f= F*bCommonDen (F);
290  int shift;
291  TIMING_START (fac_alg_norm);
292  CanonicalForm norm= sqrfNorm (f, alpha, shift);
293  TIMING_END_AND_PRINT (fac_alg_norm, "time to compute sqrf norm: ");
294  ASSERT (degree (norm, alpha) <= 0, "wrong norm computed");
295  TIMING_START (fac_alg_factor_norm);
296  bool save_sort= !isOn (SW_USE_NTL_SORT);
297  On (SW_USE_NTL_SORT);
298  CFFList normFactors= factorize (norm);
299  if (save_sort)
300  Off (SW_USE_NTL_SORT);
301  TIMING_END_AND_PRINT (fac_alg_factor_norm, "time to factor norm: ");
302  CFList factors;
303  if (normFactors.length() <= 2)
304  {
305  if (save_rat) Off(SW_RATIONAL);
306  return CFList (F);
307  }
308 
309  normFactors.removeFirst();
310  CFFListIterator i= normFactors;
311  CanonicalForm buf;
312  bool shiftBuf= false;
313  if (!(normFactors.length() == 2 && degree (i.getItem().factor()) <= degree (f)))
314  {
315  TIMING_START (fac_alg_time_shift);
316  if (shift != 0)
317  buf= f (f.mvar() - shift*alpha, f.mvar());
318  else
319  buf= f;
320  shiftBuf= true;
321  TIMING_END_AND_PRINT (fac_alg_time_shift, "time to shift: ");
322  }
323  else
324  buf= f;
325  CanonicalForm factor;
326  int count= 0;
327  for (; i.hasItem(); i++)
328  {
329  ASSERT (i.getItem().exp() == 1, "norm not squarefree");
330  TIMING_START (fac_alg_gcd);
331  if (shiftBuf)
332  factor= gcd (buf, i.getItem().factor());
333  else
334  {
335  if (shift == 0)
336  factor= gcd (buf, i.getItem().factor());
337  else
338  factor= gcd (buf, i.getItem().factor() (f.mvar() + shift*alpha, f.mvar()));
339  }
340  buf /= factor;
341  if (shiftBuf)
342  {
343  if (shift != 0)
344  factor= factor (f.mvar() + shift*alpha, f.mvar());
345  }
346  TIMING_END_AND_PRINT (fac_alg_gcd, "time to recover factors: ");
347  factors.append (factor);
348  count++;
349  if (normFactors.length() - 1 == count)
350  {
351  if (shiftBuf)
352  factors.append (buf (f.mvar() + shift*alpha, f.mvar()));
353  else
354  factors.append (buf);
355  buf= 1;
356  break;
357  }
358  }
359  ASSERT (degree (buf) <= 0, "incomplete factorization");
360  if (save_rat) Off(SW_RATIONAL);
361  return factors;
362 }*/
363 
365 {
366  ASSERT (F.isUnivariate(), "univariate input expected");
367  ASSERT (getCharacteristic() == 0, "characteristic 0 expected");
368 
369 
370  if (F.inCoeffDomain())
371  return CFFList (CFFactor (F, 1));
372 
373  bool save_rat=!isOn (SW_RATIONAL);
374  On (SW_RATIONAL);
375  TIMING_START (fac_alg_sqrf);
376  CFFList sqrf= sqrFreeZ (F);
377  TIMING_END_AND_PRINT (fac_alg_sqrf, "time for sqrf factors in Q(a)[x]: ");
378  CFList factorsSqrf;
379  CFFList factors;
381 
382  CanonicalForm lcinv;
383  for (CFFListIterator i= sqrf; i.hasItem(); i++)
384  {
385  if (i.getItem().factor().inCoeffDomain()) continue;
386  TIMING_START (fac_alg_factor_sqrf);
387  factorsSqrf= AlgExtSqrfFactorize (i.getItem().factor(), alpha);
388  TIMING_END_AND_PRINT (fac_alg_factor_sqrf,
389  "time to factor sqrf factors in Q(a)[x]: ");
390  for (j= factorsSqrf; j.hasItem(); j++)
391  {
392  lcinv= 1/Lc (j.getItem());
393  factors.append (CFFactor (j.getItem()*lcinv, i.getItem().exp()));
394  }
395  }
396 
397  factors.insert (CFFactor (Lc(F), 1));
398  if (save_rat) Off(SW_RATIONAL);
399  return factors;
400 }
401 
int status int void size_t count
Definition: si_signals.h:59
List< CanonicalForm > CFList
const CanonicalForm int const CFList const Variable & y
Definition: facAbsFact.cc:57
static CanonicalForm Norm(const CanonicalForm &F, const Variable &alpha)
Definition: facAlgExt.cc:49
int isEmpty() const
Definition: ftmpl_list.cc:267
void Off(int sw)
switches
functions to print debug output
CanonicalForm deriv(const CanonicalForm &f, const Variable &x)
#define TIMING_END_AND_PRINT(t, msg)
Definition: timing.h:89
Univariate factorization over algebraic extension of Q using Trager&#39;s algorithm.
CFFList sqrFreeZ(const CanonicalForm &a)
Definition: fac_sqrfree.cc:45
factory&#39;s class for variables
Definition: factory.h:115
CFFListIterator iter
Definition: facAbsBiFact.cc:54
static const int SW_USE_NTL_SORT
set to 1 to sort factors in a factorization
Definition: cf_defs.h:36
factory&#39;s main class
Definition: canonicalform.h:75
assertions for Factory
g
Definition: cfModGcd.cc:4031
int k
Definition: cfEzgcd.cc:93
Variable alpha
Definition: facAbsBiFact.cc:52
CFList AlgExtSqrfFactorize(const CanonicalForm &F, const Variable &alpha)
factorize a univariate squarefree polynomial over algebraic extension of Q
Definition: facAlgExt.cc:142
void insert(const T &)
Definition: ftmpl_list.cc:193
static TreeM * G
Definition: janet.cc:38
CanonicalForm Lc(const CanonicalForm &f)
CanonicalForm getMipo(const Variable &alpha, const Variable &x)
Definition: variable.cc:207
int getCharacteristic()
Definition: cf_char.cc:51
void removeFirst()
Definition: ftmpl_list.cc:287
T getFirst() const
Definition: ftmpl_list.cc:279
CFFList factorize(const CanonicalForm &f, bool issqrfree=false)
factorization over or
Definition: cf_factor.cc:390
CFFList AlgExtFactorize(const CanonicalForm &F, const Variable &alpha)
factorize a univariate polynomial over algebraic extension of Q
Definition: facAlgExt.cc:364
int j
Definition: myNF.cc:70
static CanonicalForm sqrfNorm(const CanonicalForm &F, const Variable &alpha, int &i)
Definition: facAlgExt.cc:73
int status int void * buf
Definition: si_signals.h:59
bool isUnivariate() const
T & getItem() const
Definition: ftmpl_list.cc:431
static const int SW_RATIONAL
set to 1 for computations over Q
Definition: cf_defs.h:28
bool isOn(int sw)
switches
void On(int sw)
switches
FILE * f
Definition: checklibs.c:7
int i
Definition: cfEzgcd.cc:123
T getLast() const
Definition: ftmpl_list.cc:309
generate random integers, random elements of finite fields
CanonicalForm factor
Definition: facAbsFact.cc:101
Variable mvar() const
mvar() returns the main variable of CO or Variable() if CO is in a base domain.
CFList tmp2
Definition: facFqBivar.cc:70
declarations of higher level algorithms.
CanonicalForm bCommonDen(const CanonicalForm &f)
CanonicalForm bCommonDen ( const CanonicalForm & f )
CanonicalForm resultantZ(const CanonicalForm &A, const CanonicalForm &B, const Variable &x, bool prob)
modular resultant algorihtm over Z
This file provides utility functions for bivariate factorization.
modular resultant algorithm as described by G.
int length() const
Definition: ftmpl_list.cc:273
int gcd(int a, int b)
Definition: walkSupport.cc:839
#define TIMING_START(t)
Definition: timing.h:87
Variable x
Definition: cfModGcd.cc:4023
static CFFList norm(const CanonicalForm &f, const CanonicalForm &PPalpha, CFGenerator &myrandom, CanonicalForm &s, CanonicalForm &g, CanonicalForm &R, bool proof)
compute the norm R of f over PPalpha, g= f (x-s*alpha) if proof==true, R is squarefree and if in addi...
Definition: facAlgFunc.cc:206
#define const
Definition: fegetopt.c:41
int level() const
level() returns the level of CO.
#define ASSERT(expression, message)
Definition: cf_assert.h:99
void append(const T &)
Definition: ftmpl_list.cc:256
int degree(const CanonicalForm &f)
TIMING_DEFINE_PRINT(fac_alg_resultant) TIMING_DEFINE_PRINT(fac_alg_norm) TIMING_DEFINE_PRINT(fac_alg_factor_norm) TIMING_DEFINE_PRINT(fac_alg_gcd) TIMING_DEFINE_PRINT(fac_alg_sqrf) TIMING_DEFINE_PRINT(fac_alg_factor_sqrf) TIMING_DEFINE_PRINT(fac_alg_time_shift) static CanonicalForm uniSqrfPart(const CanonicalForm &F)
Definition: facAlgExt.cc:31
CanonicalForm resultant(const CanonicalForm &f, const CanonicalForm &g, const Variable &x)
CanonicalForm resultant ( const CanonicalForm & f, const CanonicalForm & g, const Variable & x ) ...
squarefree part and factorization over Q, Q(a)
Header for factory&#39;s main class CanonicalForm.
bool inCoeffDomain() const