Functions
facAlgExt.h File Reference

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

#include "cf_assert.h"
#include "canonicalform.h"

Go to the source code of this file.

Functions

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.h.

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
f
Definition: cfModGcd.cc:4022
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
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