Loading...
Searching...
No Matches
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
CFFList | AlgExtFactorize (const CanonicalForm &F, const Variable &alpha)
| factorize a univariate polynomial over algebraic extension of Q

## 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

## 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] | F | a univariate polynomial
  [in] | alpha | an algebraic variable

Definition at line 370 of file facAlgExt.cc.

{
ASSERT (F.isUnivariate(), "univariate input expected");
ASSERT (getCharacteristic() == 0, "characteristic 0 expected");
if (F.inCoeffDomain())
return CFFList (CFFactor (F, 1));
bool save_rat=!isOn (SW_RATIONAL);
On (SW_RATIONAL);
TIMING_START (fac_alg_sqrf);
CFFList sqrf= sqrFreeZ (F);
TIMING_END_AND_PRINT (fac_alg_sqrf, "time for sqrf factors in Q(a)[x]: ");
CFList factorsSqrf;
CFFList factors;
CFListIterator j;
CanonicalForm lcinv;
for (CFFListIterator i= sqrf; i.hasItem(); i++)
{
if (i.getItem().factor().inCoeffDomain()) continue;
TIMING_START (fac_alg_factor_sqrf);
factorsSqrf= AlgExtSqrfFactorize (i.getItem().factor(), alpha);
TIMING_END_AND_PRINT (fac_alg_factor_sqrf,
"time to factor sqrf factors in Q(a)[x]: ");
for (j= factorsSqrf; j.hasItem(); j++)
{
lcinv= 1/Lc (j.getItem());
factors.append (CFFactor (j.getItem()*lcinv, i.getItem().exp()));
}
}
factors.insert (CFFactor (Lc(F), 1));
if (save_rat) Off(SW_RATIONAL);
return factors;
}
isOn
bool isOn(int sw)
switches
Definition canonicalform.cc:1971
On
void On(int sw)
switches
Definition canonicalform.cc:1957
Off
void Off(int sw)
switches
Definition canonicalform.cc:1964
CFFListIterator
ListIterator< CFFactor > CFFListIterator
Definition canonicalform.h:394
CFListIterator
ListIterator< CanonicalForm > CFListIterator
Definition canonicalform.h:396
CFFList
List< CFFactor > CFFList
Definition canonicalform.h:393
Lc
CanonicalForm Lc(const CanonicalForm &f)
Definition canonicalform.h:307
CFFactor
Factor< CanonicalForm > CFFactor
Definition canonicalform.h:392
CFList
List< CanonicalForm > CFList
Definition canonicalform.h:395
getCharacteristic
int FACTORY_PUBLIC getCharacteristic()
Definition cf_char.cc:70
i
int i
Definition cfEzgcd.cc:132
ASSERT
#define ASSERT(expression, message)
Definition cf_assert.h:99
SW_RATIONAL
static const int SW_RATIONAL
set to 1 for computations over Q
Definition cf_defs.h:31
CanonicalForm
factory's main class
Definition canonicalform.h:86
CanonicalForm::inCoeffDomain
bool inCoeffDomain() const
Definition canonicalform.cc:122
CanonicalForm::isUnivariate
bool isUnivariate() const
Definition canonicalform.cc:155
List::append
void append(const T &)
Definition ftmpl_list.cc:256
List::insert
void insert(const T &)
Definition ftmpl_list.cc:193
alpha
Variable alpha
Definition facAbsBiFact.cc:52
AlgExtSqrfFactorize
CFList AlgExtSqrfFactorize(const CanonicalForm &F, const Variable &alpha)
factorize a univariate squarefree polynomial over algebraic extension of Q
Definition facAlgExt.cc:148
j
int j
Definition facHensel.cc:110
sqrFreeZ
CFFList sqrFreeZ(const CanonicalForm &a)
Definition fac_sqrfree.cc:49
TIMING_START
#define TIMING_START(t)
Definition timing.h:92
TIMING_END_AND_PRINT
#define TIMING_END_AND_PRINT(t, msg)
Definition timing.h:94

## 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] | F | a univariate squarefree polynomial
  [in] | alpha | an algebraic variable

Definition at line 148 of file facAlgExt.cc.

{
ASSERT (F.isUnivariate(), "univariate input expected");
ASSERT (getCharacteristic() == 0, "characteristic 0 expected");
bool save_rat=!isOn (SW_RATIONAL);
On (SW_RATIONAL);
CanonicalForm f= F*bCommonDen (F);
Variable y= f.mvar();
int shift= 0, k= 0, count= 0;
CanonicalForm norm, buf, factor, oldF;
CFFList normFactors;
bool save_sort= !isOn (SW_USE_NTL_SORT);
CFList factors, tmp, tmp2;
CFFListIterator i;
CFListIterator iter;
bool shiftBuf= false;
tmp.append (f);
do
{
tmp2= CFList();
for (iter= tmp; iter.hasItem(); iter++)
{
oldF= iter.getItem()*bCommonDen (iter.getItem());
if (shift == 0)
f= oldF;
else
{
f= oldF (y - shift*alpha, y);
f *= bCommonDen (f);
}
TIMING_START (fac_alg_norm);
norm= Norm (f, alpha);
TIMING_END_AND_PRINT (fac_alg_norm, "time to compute sqrf norm: ");
ASSERT (degree (norm, alpha) <= 0, "wrong norm computed");
TIMING_START (fac_alg_factor_norm);
On (SW_USE_NTL_SORT);
normFactors= factorize (norm);
if (save_sort)
Off (SW_USE_NTL_SORT);
TIMING_END_AND_PRINT (fac_alg_factor_norm, "time to factor norm: ");
if (normFactors.getFirst().factor().inCoeffDomain())
normFactors.removeFirst();
if (normFactors.length() < 2 && normFactors.getLast().exp() == 1)
{
factors.append (oldF);
continue;
}
i= normFactors;
shiftBuf= false;
if (!(normFactors.length() == 2 &&
degree (i.getItem().factor()) <= degree (f)))
{
TIMING_START (fac_alg_time_shift);
if (shift != 0)
buf= f;
else
buf= oldF;
shiftBuf= true;
TIMING_END_AND_PRINT (fac_alg_time_shift, "time to shift: ");
}
else
buf= oldF;
count= 0;
for (; i.hasItem(); i++)
{
TIMING_START (fac_alg_gcd);
if (shiftBuf)
factor= gcd (buf, i.getItem().factor());
else
{
if (shift == 0)
factor= gcd (buf, i.getItem().factor());
else
factor= gcd (buf, i.getItem().factor() (y + shift*alpha, y));
}
buf /= factor;
if (shiftBuf)
{
if (shift != 0)
factor= factor (y + shift*alpha, y);
}
TIMING_END_AND_PRINT (fac_alg_gcd, "time to recover factors: ");
if (i.getItem().exp() == 1 || degree (factor) == 1)
factors.append (factor);
else
tmp2.append (factor);
if (buf.inCoeffDomain())
break;
count++;
if (normFactors.length() - 1 == count)
{
if (shiftBuf)
{
if (normFactors.getLast().exp() == 1)
factors.append (buf (y + shift*alpha, y));
else
tmp2.append (buf (y + shift*alpha, y));
}
else
{
if (normFactors.getLast().exp() == 1)
factors.append (buf);
else
tmp2.append (buf);
}
buf= 1;
break;
}
}
}
k++;
if (shift == 0)
{
shift++;
k= 1;
}
if (k == 2)
shift= -shift;
if (k == 3)
{
shift= -shift;
shift++;
k= 1;
}
tmp= tmp2;
}
while (!tmp.isEmpty());
if (save_rat) Off(SW_RATIONAL);
return factors;
}
degree
int degree(const CanonicalForm &f)
Definition canonicalform.h:316
k
int k
Definition cfEzgcd.cc:99
bCommonDen
CanonicalForm bCommonDen(const CanonicalForm &f)
void psqr ( const CanonicalForm & f, const CanonicalForm & g, CanonicalForm & q, CanonicalForm & r,...
Definition cf_algorithm.cc:293
factorize
CFFList FACTORY_PUBLIC factorize(const CanonicalForm &f, bool issqrfree=false)
factorization over or
Definition cf_factor.cc:409
SW_USE_NTL_SORT
static const int SW_USE_NTL_SORT
set to 1 to sort factors in a factorization
Definition cf_defs.h:39
f
FILE * f
Definition checklibs.c:9
Factor::exp
int exp() const
Definition ftmpl_factor.h:31
Factor::factor
T factor() const
Definition ftmpl_factor.h:30
List::getFirst
T getFirst() const
Definition ftmpl_list.cc:279
List::removeFirst
void removeFirst()
Definition ftmpl_list.cc:287
List::length
int length() const
Definition ftmpl_list.cc:273
List::getLast
T getLast() const
Definition ftmpl_list.cc:309
List::isEmpty
int isEmpty() const
Definition ftmpl_list.cc:267
Variable
factory's class for variables
Definition factory.h:127
iter
CFFListIterator iter
Definition facAbsBiFact.cc:54
y
const CanonicalForm int const CFList const Variable & y
Definition facAbsFact.cc:53
factor
CanonicalForm factor
Definition facAbsFact.cc:97
norm
mipo *CanonicalForm norm
Definition facAlgExt.cc:61
tmp2
CFList tmp2
Definition facFqBivar.cc:75
count
int status int void size_t count
Definition si_signals.h:69
buf
int status int void * buf
Definition si_signals.h:69
gcd
int gcd(int a, int b)
Definition walkSupport.cc:836