Functions
facAlgExt.cc File Reference

Univariate factorization over algebraic extension of Q using Trager's algorithm. More...

#include "config.h"
#include "cf_assert.h"
#include "debug.h"
#include "timing.h"
#include "canonicalform.h"
#include "cf_random.h"
#include "cf_algorithm.h"
#include "facFqBivarUtil.h"
#include "facAlgExt.h"
#include "cfModResultant.h"
#include "fac_sqrfree.h"

Go to the source code of this file.

Functions

 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)
 
static CanonicalForm Norm (const CanonicalForm &F, const Variable &alpha)
 
static CanonicalForm sqrfNorm (const CanonicalForm &F, const Variable &alpha, int &i)
 
CFList AlgExtSqrfFactorize (const CanonicalForm &F, const Variable &alpha)
 factorize a univariate squarefree polynomial over algebraic extension of Q More...
 
CFFList AlgExtFactorize (const CanonicalForm &F, const Variable &alpha)
 factorize a univariate polynomial over algebraic extension of Q More...
 

Detailed Description

Univariate factorization over algebraic extension of Q using Trager's algorithm.

Copyright:
(c) by The SINGULAR Team, see LICENSE file
Author
Martin Lee

Definition in file facAlgExt.cc.

Function Documentation

§ AlgExtFactorize()

CFFList AlgExtFactorize ( const CanonicalForm F,
const Variable alpha 
)

factorize a univariate polynomial over algebraic extension of Q

Returns
AlgExtFactorize returns a list of factors of F with multiplicity
Parameters
[in]Fa univariate polynomial
[in]alphaan algebraic variable

Definition at line 364 of file facAlgExt.cc.

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 }
void Off(int sw)
switches
#define TIMING_END_AND_PRINT(t, msg)
Definition: timing.h:89
CFFList sqrFreeZ(const CanonicalForm &a)
Definition: fac_sqrfree.cc:45
factory's main class
Definition: canonicalform.h:75
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
CanonicalForm Lc(const CanonicalForm &f)
int getCharacteristic()
Definition: cf_char.cc:51
int j
Definition: myNF.cc:70
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
int i
Definition: cfEzgcd.cc:123
#define TIMING_START(t)
Definition: timing.h:87
#define ASSERT(expression, message)
Definition: cf_assert.h:99
void append(const T &)
Definition: ftmpl_list.cc:256
bool inCoeffDomain() const

§ AlgExtSqrfFactorize()

CFList AlgExtSqrfFactorize ( const CanonicalForm F,
const Variable alpha 
)

factorize a univariate squarefree polynomial over algebraic extension of Q

Returns
AlgExtSqrfFactorize returns a list of factors of F
Parameters
[in]Fa univariate squarefree polynomial
[in]alphaan algebraic variable

Definition at line 142 of file facAlgExt.cc.

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 }
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
#define TIMING_END_AND_PRINT(t, msg)
Definition: timing.h:89
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
int k
Definition: cfEzgcd.cc:93
Variable alpha
Definition: facAbsBiFact.cc:52
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
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
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
CanonicalForm bCommonDen(const CanonicalForm &f)
CanonicalForm bCommonDen ( const CanonicalForm & f )
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
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 ASSERT(expression, message)
Definition: cf_assert.h:99
void append(const T &)
Definition: ftmpl_list.cc:256
int degree(const CanonicalForm &f)
bool inCoeffDomain() const

§ Norm()

static CanonicalForm Norm ( const CanonicalForm F,
const Variable alpha 
)
static

Definition at line 49 of file facAlgExt.cc.

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 }
const CanonicalForm int const CFList const Variable & y
Definition: facAbsFact.cc:57
#define TIMING_END_AND_PRINT(t, msg)
Definition: timing.h:89
factory&#39;s class for variables
Definition: factory.h:115
factory&#39;s main class
Definition: canonicalform.h:75
g
Definition: cfModGcd.cc:4031
CanonicalForm getMipo(const Variable &alpha, const Variable &x)
Definition: variable.cc:207
Variable mvar() const
mvar() returns the main variable of CO or Variable() if CO is in a base domain.
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
#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
int level() const
level() returns the level of CO.
int degree(const CanonicalForm &f)
CanonicalForm resultant(const CanonicalForm &f, const CanonicalForm &g, const Variable &x)
CanonicalForm resultant ( const CanonicalForm & f, const CanonicalForm & g, const Variable & x ) ...

§ sqrfNorm()

static CanonicalForm sqrfNorm ( const CanonicalForm F,
const Variable alpha,
int &  i 
)
static

Definition at line 73 of file facAlgExt.cc.

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 }
const CanonicalForm int const CFList const Variable & y
Definition: facAbsFact.cc:57
CanonicalForm deriv(const CanonicalForm &f, const Variable &x)
#define TIMING_END_AND_PRINT(t, msg)
Definition: timing.h:89
factory&#39;s class for variables
Definition: factory.h:115
factory&#39;s main class
Definition: canonicalform.h:75
g
Definition: cfModGcd.cc:4031
int k
Definition: cfEzgcd.cc:93
CanonicalForm getMipo(const Variable &alpha, const Variable &x)
Definition: variable.cc:207
int i
Definition: cfEzgcd.cc:123
Variable mvar() const
mvar() returns the main variable of CO or Variable() if CO is in a base domain.
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
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
int level() const
level() returns the level of CO.
int degree(const CanonicalForm &f)
CanonicalForm resultant(const CanonicalForm &f, const CanonicalForm &g, const Variable &x)
CanonicalForm resultant ( const CanonicalForm & f, const CanonicalForm & g, const Variable & x ) ...

§ TIMING_DEFINE_PRINT()

TIMING_DEFINE_PRINT ( fac_alg_resultant  ) const

Definition at line 31 of file facAlgExt.cc.

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 }
CanonicalForm deriv(const CanonicalForm &f, const Variable &x)
factory&#39;s main class
Definition: canonicalform.h:75
static TreeM * G
Definition: janet.cc:38
int getCharacteristic()
Definition: cf_char.cc:51
int gcd(int a, int b)
Definition: walkSupport.cc:839
#define ASSERT(expression, message)
Definition: cf_assert.h:99