My Project  debian-1:4.1.1-p2+ds-4
Functions | Variables
facAlgExt.cc File Reference
#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 Norm(const CanonicalForm &F
 
 TIMING_START (fac_alg_resultant)
 
 if (degg >=8||degmipo >=8) norm
 
 TIMING_END_AND_PRINT (fac_alg_resultant, "time to compute resultant0: ")
 
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...
 

Variables

const Variablealpha
 
Variable y = F.mvar()
 
CanonicalForm g = F (x, alpha)
 
CanonicalForm mipo = getMipo (alpha)
 
mipo *int degg = degree (g)
 
int degmipo = degree (mipo)
 
CanonicalForm norm = resultant (g, mipo, x)
 

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

371 {
372  ASSERT (F.isUnivariate(), "univariate input expected");
373  ASSERT (getCharacteristic() == 0, "characteristic 0 expected");
374 
375 
376  if (F.inCoeffDomain())
377  return CFFList (CFFactor (F, 1));
378 
379  bool save_rat=!isOn (SW_RATIONAL);
380  On (SW_RATIONAL);
381  TIMING_START (fac_alg_sqrf);
382  CFFList sqrf= sqrFreeZ (F);
383  TIMING_END_AND_PRINT (fac_alg_sqrf, "time for sqrf factors in Q(a)[x]: ");
384  CFList factorsSqrf;
385  CFFList factors;
387 
388  CanonicalForm lcinv;
389  for (CFFListIterator i= sqrf; i.hasItem(); i++)
390  {
391  if (i.getItem().factor().inCoeffDomain()) continue;
392  TIMING_START (fac_alg_factor_sqrf);
393  factorsSqrf= AlgExtSqrfFactorize (i.getItem().factor(), alpha);
394  TIMING_END_AND_PRINT (fac_alg_factor_sqrf,
395  "time to factor sqrf factors in Q(a)[x]: ");
396  for (j= factorsSqrf; j.hasItem(); j++)
397  {
398  lcinv= 1/Lc (j.getItem());
399  factors.append (CFFactor (j.getItem()*lcinv, i.getItem().exp()));
400  }
401  }
402 
403  factors.insert (CFFactor (Lc(F), 1));
404  if (save_rat) Off(SW_RATIONAL);
405  return factors;
406 }

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

149 {
150  ASSERT (F.isUnivariate(), "univariate input expected");
151  ASSERT (getCharacteristic() == 0, "characteristic 0 expected");
152 
153  bool save_rat=!isOn (SW_RATIONAL);
154  On (SW_RATIONAL);
155  CanonicalForm f= F*bCommonDen (F);
156  Variable y= f.mvar();
157  int shift= 0, k= 0, count= 0;
158  CanonicalForm norm, buf, factor, oldF;
159  CFFList normFactors;
160  bool save_sort= !isOn (SW_USE_NTL_SORT);
161  CFList factors, tmp, tmp2;
164  bool shiftBuf= false;
165 
166  tmp.append (f);
167  do
168  {
169  tmp2= CFList();
170  for (iter= tmp; iter.hasItem(); iter++)
171  {
172  oldF= iter.getItem()*bCommonDen (iter.getItem());
173  if (shift == 0)
174  f= oldF;
175  else
176  {
177  f= oldF (y - shift*alpha, y);
178  f *= bCommonDen (f);
179  }
180  TIMING_START (fac_alg_norm);
181  norm= Norm (f, alpha);
182  TIMING_END_AND_PRINT (fac_alg_norm, "time to compute sqrf norm: ");
183  ASSERT (degree (norm, alpha) <= 0, "wrong norm computed");
184 
185  TIMING_START (fac_alg_factor_norm);
187  normFactors= factorize (norm);
188  if (save_sort)
190  TIMING_END_AND_PRINT (fac_alg_factor_norm, "time to factor norm: ");
191 
192  if (normFactors.getFirst().factor().inCoeffDomain())
193  normFactors.removeFirst();
194  if (normFactors.length() < 2 && normFactors.getLast().exp() == 1)
195  {
196  factors.append (oldF);
197  continue;
198  }
199 
200  i= normFactors;
201  shiftBuf= false;
202  if (!(normFactors.length() == 2 &&
203  degree (i.getItem().factor()) <= degree (f)))
204  {
205  TIMING_START (fac_alg_time_shift);
206  if (shift != 0)
207  buf= f;
208  else
209  buf= oldF;
210  shiftBuf= true;
211  TIMING_END_AND_PRINT (fac_alg_time_shift, "time to shift: ");
212  }
213  else
214  buf= oldF;
215 
216  count= 0;
217  for (; i.hasItem(); i++)
218  {
219  TIMING_START (fac_alg_gcd);
220  if (shiftBuf)
221  factor= gcd (buf, i.getItem().factor());
222  else
223  {
224  if (shift == 0)
225  factor= gcd (buf, i.getItem().factor());
226  else
227  factor= gcd (buf, i.getItem().factor() (y + shift*alpha, y));
228  }
229  buf /= factor;
230  if (shiftBuf)
231  {
232  if (shift != 0)
233  factor= factor (y + shift*alpha, y);
234  }
235  TIMING_END_AND_PRINT (fac_alg_gcd, "time to recover factors: ");
236  if (i.getItem().exp() == 1 || degree (factor) == 1)
237  factors.append (factor);
238  else
239  tmp2.append (factor);
240  if (buf.inCoeffDomain())
241  break;
242  count++;
243  if (normFactors.length() - 1 == count)
244  {
245  if (shiftBuf)
246  {
247  if (normFactors.getLast().exp() == 1)
248  factors.append (buf (y + shift*alpha, y));
249  else
250  tmp2.append (buf (y + shift*alpha, y));
251  }
252  else
253  {
254  if (normFactors.getLast().exp() == 1)
255  factors.append (buf);
256  else
257  tmp2.append (buf);
258  }
259  buf= 1;
260  break;
261  }
262  }
263  }
264  k++;
265  if (shift == 0)
266  {
267  shift++;
268  k= 1;
269  }
270  if (k == 2)
271  shift= -shift;
272  if (k == 3)
273  {
274  shift= -shift;
275  shift++;
276  k= 1;
277  }
278  tmp= tmp2;
279  }
280  while (!tmp.isEmpty());
281 
282  if (save_rat) Off(SW_RATIONAL);
283  return factors;
284 }

◆ if()

if ( degg >=8||degmipo >=  8)

◆ TIMING_DEFINE_PRINT()

TIMING_DEFINE_PRINT ( fac_alg_resultant  ) const &

◆ TIMING_END_AND_PRINT()

TIMING_END_AND_PRINT ( fac_alg_resultant  ,
"time to compute resultant0: "   
)

◆ TIMING_START()

TIMING_START ( fac_alg_resultant  )

Variable Documentation

◆ alpha

const Variable& alpha
Initial value:
{
Variable x= Variable (F.level() + 1)

Definition at line 53 of file facAlgExt.cc.

◆ degg

mipo* int degg = degree (g)

Definition at line 61 of file facAlgExt.cc.

◆ degmipo

int degmipo = degree (mipo)

Definition at line 62 of file facAlgExt.cc.

◆ g

CanonicalForm g = F (x, alpha)

Definition at line 56 of file facAlgExt.cc.

◆ mipo

mipo = getMipo (alpha)

Definition at line 57 of file facAlgExt.cc.

◆ norm

return norm = resultant (g, mipo, x)

Definition at line 63 of file facAlgExt.cc.

◆ y

Definition at line 55 of file facAlgExt.cc.

AlgExtSqrfFactorize
CFList AlgExtSqrfFactorize(const CanonicalForm &F, const Variable &alpha)
factorize a univariate squarefree polynomial over algebraic extension of Q
Definition: facAlgExt.cc:148
SW_RATIONAL
static const int SW_RATIONAL
set to 1 for computations over Q
Definition: cf_defs.h:28
isOn
bool isOn(int sw)
switches
Definition: canonicalform.cc:1912
j
int j
Definition: facHensel.cc:105
f
FILE * f
Definition: checklibs.c:9
k
int k
Definition: cfEzgcd.cc:92
x
Variable x
Definition: cfModGcd.cc:4023
iter
CFFListIterator iter
Definition: facAbsBiFact.cc:54
getCharacteristic
int getCharacteristic()
Definition: cf_char.cc:51
sqrFreeZ
CFFList sqrFreeZ(const CanonicalForm &a)
Definition: fac_sqrfree.cc:45
CanonicalForm
factory's main class
Definition: canonicalform.h:77
alpha
const Variable & alpha
Definition: facAlgExt.cc:53
SW_USE_NTL_SORT
static const int SW_USE_NTL_SORT
set to 1 to sort factors in a factorization
Definition: cf_defs.h:36
i
int i
Definition: cfEzgcd.cc:125
Lc
CanonicalForm Lc(const CanonicalForm &f)
Definition: canonicalform.h:300
ASSERT
#define ASSERT(expression, message)
Definition: cf_assert.h:99
buf
int status int void * buf
Definition: si_signals.h:58
TIMING_START
TIMING_START(fac_alg_resultant)
List::isEmpty
int isEmpty() const
Definition: ftmpl_list.cc:267
norm
CanonicalForm norm
Definition: facAlgExt.cc:63
factorize
CFFList factorize(const CanonicalForm &f, bool issqrfree=false)
factorization over or
Definition: cf_factor.cc:390
ListIterator::hasItem
int hasItem()
Definition: ftmpl_list.cc:439
Off
void Off(int sw)
switches
Definition: canonicalform.cc:1905
List::removeFirst
void removeFirst()
Definition: ftmpl_list.cc:287
y
Variable y
Definition: facAlgExt.cc:55
List::getFirst
T getFirst() const
Definition: ftmpl_list.cc:279
Factor
Definition: ftmpl_factor.h:18
bCommonDen
CanonicalForm bCommonDen(const CanonicalForm &f)
CanonicalForm bCommonDen ( const CanonicalForm & f )
Definition: cf_algorithm.cc:293
CanonicalForm::inCoeffDomain
bool inCoeffDomain() const
Definition: canonicalform.cc:119
List::length
int length() const
Definition: ftmpl_list.cc:273
factor
CanonicalForm factor
Definition: facAbsFact.cc:101
TIMING_END_AND_PRINT
TIMING_END_AND_PRINT(fac_alg_resultant, "time to compute resultant0: ")
Variable
factory's class for variables
Definition: factory.h:117
ListIterator::getItem
T & getItem() const
Definition: ftmpl_list.cc:431
CanonicalForm::isUnivariate
bool isUnivariate() const
Definition: canonicalform.cc:152
gcd
int gcd(int a, int b)
Definition: walkSupport.cc:836
List
Definition: ftmpl_list.h:20
CFList
List< CanonicalForm > CFList
Definition: canonicalform.h:388
count
int status int void size_t count
Definition: si_signals.h:58
tmp2
CFList tmp2
Definition: facFqBivar.cc:70
List::append
void append(const T &)
Definition: ftmpl_list.cc:256
degree
int degree(const CanonicalForm &f)
Definition: canonicalform.h:309
List::insert
void insert(const T &)
Definition: ftmpl_list.cc:193
On
void On(int sw)
switches
Definition: canonicalform.cc:1898
List::getLast
T getLast() const
Definition: ftmpl_list.cc:309
ListIterator
Definition: ftmpl_list.h:17