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) CanonicalForm uniSqrfPart(const CanonicalForm &F)
 
CanonicalForm Norm (const CanonicalForm &F, const Variable &alpha)
 
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

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 367 of file facAlgExt.cc.

368 {
369  ASSERT (F.isUnivariate(), "univariate input expected");
370  ASSERT (getCharacteristic() == 0, "characteristic 0 expected");
371 
372 
373  if (F.inCoeffDomain())
374  return CFFList (CFFactor (F, 1));
375 
376  bool save_rat=!isOn (SW_RATIONAL);
377  On (SW_RATIONAL);
378  TIMING_START (fac_alg_sqrf);
379  CFFList sqrf= sqrFreeZ (F);
380  TIMING_END_AND_PRINT (fac_alg_sqrf, "time for sqrf factors in Q(a)[x]: ");
381  CFList factorsSqrf;
382  CFFList factors;
384 
385  CanonicalForm lcinv;
386  for (CFFListIterator i= sqrf; i.hasItem(); i++)
387  {
388  if (i.getItem().factor().inCoeffDomain()) continue;
389  TIMING_START (fac_alg_factor_sqrf);
390  factorsSqrf= AlgExtSqrfFactorize (i.getItem().factor(), alpha);
391  TIMING_END_AND_PRINT (fac_alg_factor_sqrf,
392  "time to factor sqrf factors in Q(a)[x]: ");
393  for (j= factorsSqrf; j.hasItem(); j++)
394  {
395  lcinv= 1/Lc (j.getItem());
396  factors.append (CFFactor (j.getItem()*lcinv, i.getItem().exp()));
397  }
398  }
399 
400  factors.insert (CFFactor (Lc(F), 1));
401  if (save_rat) Off(SW_RATIONAL);
402  return factors;
403 }
void Off(int sw)
switches
bool inCoeffDomain() const
#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:144
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
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
bool isUnivariate() const
T & getItem() const
Definition: ftmpl_list.cc:431
#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
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 144 of file facAlgExt.cc.

145 {
146  ASSERT (F.isUnivariate(), "univariate input expected");
147  ASSERT (getCharacteristic() == 0, "characteristic 0 expected");
148 
149  bool save_rat=!isOn (SW_RATIONAL);
150  On (SW_RATIONAL);
151  CanonicalForm f= F*bCommonDen (F);
152  Variable y= f.mvar();
153  int shift= 0, k= 0, count= 0;
154  CanonicalForm norm, buf, factor, oldF;
155  CFFList normFactors;
156  bool save_sort= !isOn (SW_USE_NTL_SORT);
157  CFList factors, tmp, tmp2;
160  bool shiftBuf= false;
161 
162  tmp.append (f);
163  do
164  {
165  tmp2= CFList();
166  for (iter= tmp; iter.hasItem(); iter++)
167  {
168  oldF= iter.getItem()*bCommonDen (iter.getItem());
169  if (shift == 0)
170  f= oldF;
171  else
172  {
173  f= oldF (y - shift*alpha, y);
174  f *= bCommonDen (f);
175  }
176  TIMING_START (fac_alg_norm);
177  norm= Norm (f, alpha);
178  TIMING_END_AND_PRINT (fac_alg_norm, "time to compute sqrf norm: ");
179  ASSERT (degree (norm, alpha) <= 0, "wrong norm computed");
180 
181  TIMING_START (fac_alg_factor_norm);
183  normFactors= factorize (norm);
184  if (save_sort)
186  TIMING_END_AND_PRINT (fac_alg_factor_norm, "time to factor norm: ");
187 
188  if (normFactors.getFirst().factor().inCoeffDomain())
189  normFactors.removeFirst();
190  if (normFactors.length() < 2 && normFactors.getLast().exp() == 1)
191  {
192  factors.append (oldF);
193  continue;
194  }
195 
196  i= normFactors;
197  shiftBuf= false;
198  if (!(normFactors.length() == 2 &&
199  degree (i.getItem().factor()) <= degree (f)))
200  {
201  TIMING_START (fac_alg_time_shift);
202  if (shift != 0)
203  buf= f;
204  else
205  buf= oldF;
206  shiftBuf= true;
207  TIMING_END_AND_PRINT (fac_alg_time_shift, "time to shift: ");
208  }
209  else
210  buf= oldF;
211 
212  count= 0;
213  for (; i.hasItem(); i++)
214  {
215  TIMING_START (fac_alg_gcd);
216  if (shiftBuf)
217  factor= gcd (buf, i.getItem().factor());
218  else
219  {
220  if (shift == 0)
221  factor= gcd (buf, i.getItem().factor());
222  else
223  factor= gcd (buf, i.getItem().factor() (y + shift*alpha, y));
224  }
225  buf /= factor;
226  if (shiftBuf)
227  {
228  if (shift != 0)
229  factor= factor (y + shift*alpha, y);
230  }
231  TIMING_END_AND_PRINT (fac_alg_gcd, "time to recover factors: ");
232  if (i.getItem().exp() == 1 || degree (factor) == 1)
233  factors.append (factor);
234  else
235  tmp2.append (factor);
236  if (buf.inCoeffDomain())
237  break;
238  count++;
239  if (normFactors.length() - 1 == count)
240  {
241  if (shiftBuf)
242  {
243  if (normFactors.getLast().exp() == 1)
244  factors.append (buf (y + shift*alpha, y));
245  else
246  tmp2.append (buf (y + shift*alpha, y));
247  }
248  else
249  {
250  if (normFactors.getLast().exp() == 1)
251  factors.append (buf);
252  else
253  tmp2.append (buf);
254  }
255  buf= 1;
256  break;
257  }
258  }
259  }
260  k++;
261  if (shift == 0)
262  {
263  shift++;
264  k= 1;
265  }
266  if (k == 2)
267  shift= -shift;
268  if (k == 3)
269  {
270  shift= -shift;
271  shift++;
272  k= 1;
273  }
274  tmp= tmp2;
275  }
276  while (!tmp.isEmpty());
277 
278  if (save_rat) Off(SW_RATIONAL);
279  return factors;
280 }
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
Variable mvar() const
mvar() returns the main variable of CO or Variable() if CO is in a base domain.
void Off(int sw)
switches
bool inCoeffDomain() const
#define TIMING_END_AND_PRINT(t, msg)
Definition: timing.h:89
factory&#39;s class for variables
Definition: variable.h:32
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
int isEmpty() const
Definition: ftmpl_list.cc:267
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
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
T getFirst() const
Definition: ftmpl_list.cc:279
FILE * f
Definition: checklibs.c:7
int length() const
Definition: ftmpl_list.cc:273
int i
Definition: cfEzgcd.cc:123
CanonicalForm factor
Definition: facAbsFact.cc:101
CFList tmp2
Definition: facFqBivar.cc:70
CanonicalForm bCommonDen(const CanonicalForm &f)
CanonicalForm bCommonDen ( const CanonicalForm & f )
bool isUnivariate() const
T & getItem() const
Definition: ftmpl_list.cc:431
int gcd(int a, int b)
Definition: walkSupport.cc:839
#define TIMING_START(t)
Definition: timing.h:87
T getLast() const
Definition: ftmpl_list.cc:309
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)
CanonicalForm Norm(const CanonicalForm &F, const Variable &alpha)
Definition: facAlgExt.cc:50
CanonicalForm Norm ( const CanonicalForm F,
const Variable alpha 
)

Definition at line 50 of file facAlgExt.cc.

51 {
52  Variable x= Variable (F.level() + 1);
53  Variable y= F.mvar();
54  CanonicalForm g= F (x, alpha);
55  CanonicalForm mipo= getMipo (alpha);
56  mipo= mipo (x, alpha);
57  mipo *= bCommonDen (mipo);
58 
59  int degg= degree (g);
60  int degmipo= degree (mipo);
62  TIMING_START (fac_alg_resultant);
63 #ifdef HAVE_NTL
64  if (degg >= 8 || degmipo >= 8)
65  norm= resultantZ (g, mipo, x);
66  else
67 #endif
68  norm= resultant (g, mipo, x);
69  TIMING_END_AND_PRINT (fac_alg_resultant, "time to compute resultant0: ");
70  return norm;
71 }
const CanonicalForm int const CFList const Variable & y
Definition: facAbsFact.cc:57
Variable mvar() const
mvar() returns the main variable of CO or Variable() if CO is in a base domain.
#define TIMING_END_AND_PRINT(t, msg)
Definition: timing.h:89
factory&#39;s class for variables
Definition: variable.h:32
factory&#39;s main class
Definition: canonicalform.h:75
g
Definition: cfModGcd.cc:4031
int level() const
level() returns the level of CO.
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
CanonicalForm getMipo(const Variable &alpha, const Variable &x)
Definition: variable.cc:207
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 ) ...
CanonicalForm sqrfNorm ( const CanonicalForm F,
const Variable alpha,
int &  i 
)

Definition at line 74 of file facAlgExt.cc.

75 {
76  Variable x= Variable (F.level() + 1);
77  Variable y= F.mvar();
78  CanonicalForm g= F (x, alpha);
79  CanonicalForm mipo= getMipo (alpha);
80  mipo= mipo (x, alpha);
81  mipo *= bCommonDen (mipo);
82 
83  int degg= degree (g);
84  int degmipo= degree (mipo);
86  TIMING_START (fac_alg_resultant);
87 #ifdef HAVE_NTL
88  if (degg >= 8 || degmipo >= 8)
89  norm= resultantZ (g, mipo, x);
90  else
91 #endif
92  norm= resultant (g, mipo, x);
93  TIMING_END_AND_PRINT (fac_alg_resultant, "time to compute resultant0: ");
94 
95  i= 0;
96  int k;
97  if (degree (gcd (deriv (norm, y), norm)) <= 0)
98  return norm;
99  i= 1;
100  do
101  {
102  k= 1;
103  while (k < 3)
104  {
105  if (k == 1)
106  {
107  g= F (y - i*alpha, y);
108  g *= bCommonDen (g);
109  TIMING_START (fac_alg_resultant);
110 #ifdef HAVE_NTL
111  if (degg >= 8 || degmipo >= 8)
112  norm= resultantZ (g (x, alpha), mipo, x);
113  else
114 #endif
115  norm= resultant (g (x, alpha), mipo, x);
116  TIMING_END_AND_PRINT (fac_alg_resultant,"time to compute resultant1: ");
117  }
118  else
119  {
120  g= F (y + i*alpha, y);
121  g *= bCommonDen (g);
122  TIMING_START (fac_alg_resultant);
123 #ifdef HAVE_NTL
124  if (degg >= 8 || degmipo >= 8)
125  norm= resultantZ (g (x, alpha), mipo, x);
126  else
127 #endif
128  norm= resultant (g (x, alpha), mipo, x);
129  TIMING_END_AND_PRINT (fac_alg_resultant,"time to compute resultant2: ");
130  }
131  if (degree (gcd (deriv (norm, y), norm)) <= 0)
132  {
133  if (k == 2)
134  i= -i;
135  return norm;
136  }
137  k++;
138  }
139  i++;
140  } while (1);
141 }
const CanonicalForm int const CFList const Variable & y
Definition: facAbsFact.cc:57
Variable mvar() const
mvar() returns the main variable of CO or Variable() if CO is in a base domain.
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: variable.h:32
factory&#39;s main class
Definition: canonicalform.h:75
g
Definition: cfModGcd.cc:4031
int k
Definition: cfEzgcd.cc:93
int level() const
level() returns the level of CO.
int i
Definition: cfEzgcd.cc:123
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
CanonicalForm getMipo(const Variable &alpha, const Variable &x)
Definition: variable.cc:207
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 ( fac_alg_resultant  ) const

Definition at line 31 of file facAlgExt.cc.

42 {
43  ASSERT (F.isUnivariate(), "univariate input expected");
44  ASSERT (getCharacteristic() == 0, "characteristic 0 expected");
45  CanonicalForm G= deriv (F, F.mvar());
46  G= gcd (F, G);
47  return F/G;
48 }
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