Loading...
Searching...
No Matches
fac_multivar.cc
Go to the documentation of this file.
/* emacs edit mode for this file is -*- C++ -*- */
/* $Id: fac_multivar.cc 14377 2011-09-01 13:40:30Z mlee $ */
#include <config.h>
#include "assert.h"
#include "debug.h"
#include "timing.h"
#include "cf_defs.h"
#include "cf_algorithm.h"
#include "fac_multivar.h"
#include "fac_univar.h"
#include "cf_reval.h"
#include "cf_map.h"
#include "fac_util.h"
#include "cf_binom.h"
#include "cf_iter.h"
#include "cf_primes.h"
#include "fac_distrib.h"
#include "fac_multihensel.h"
#include "facBivar.h"
#ifndef HAVE_NTL
void out_cf(const char *s1,const CanonicalForm &f,const char *s2);
void out_cff(CFFList &L);
TIMING_DEFINE_PRINT(fac_content);
TIMING_DEFINE_PRINT(fac_findeval);
TIMING_DEFINE_PRINT(fac_distrib);
TIMING_DEFINE_PRINT(fac_hensel);
static CFArray
conv_to_factor_array( const CFFList & L )
{
int n;
CFFListIterator I = L;
bool negate = false;
if ( ! I.hasItem() )
n = 0;
else if ( I.getItem().factor().inBaseDomain() ) {
negate = I.getItem().factor().sign() < 0;
I++;
n = L.length();
}
else
n = L.length() + 1;
CFFListIterator J = I;
while ( J.hasItem() ) {
n += J.getItem().exp() - 1;
J++;
}
CFArray result( 1, n-1 );
int i, j, k;
i = 1;
while ( I.hasItem() ) {
k = I.getItem().exp();
for ( j = 1; j <= k; j++ ) {
result[i] = I.getItem().factor();
i++;
}
I++;
}
if ( negate )
result[1] = -result[1];
return result;
}
static modpk
coeffBound_old ( const CanonicalForm & f, int p )
{
int * degs = degrees( f );
int M = 0, i, k = f.level();
for ( i = 1; i <= k; i++ )
M += degs[i];
CanonicalForm b = 2 * maxNorm( f ) * power( CanonicalForm( 3 ), M );
CanonicalForm B = p;
k = 1;
while ( B < b ) {
B *= p;
k++;
}
return modpk( p, k );
}
// static bool
// nonDivisors ( CanonicalForm omega, CanonicalForm delta, const CFArray & F, CFArray & d )
// {
// DEBOUTLN( cerr, "nondivisors omega = " << omega );
// DEBOUTLN( cerr, "nondivisors delta = " << delta );
// DEBOUTLN( cerr, "nondivisors F = " << F );
// CanonicalForm q, r;
// int k = F.size();
// d = CFArray( 0, k );
// d[0] = delta * omega;
// for ( int i = 1; i <= k; i++ ) {
// q = abs(F[i]);
// for ( int j = i-1; j >= 0; j-- ) {
// r = d[j];
// do {
// r = gcd( r, q );
// q = q / r;
// } while ( r != 1 );
// if ( q == 1 )
// return false;
// }
// d[i] = q;
// }
// return true;
// }
static void
findEvaluation ( const CanonicalForm & U, const CanonicalForm & V, const CanonicalForm & omega, const CFFList & F, Evaluation & A, CanonicalForm & U0, CanonicalForm & delta, CFArray & D, int r )
{
DEBINCLEVEL( cerr, "findEvaluation" );
CanonicalForm Vn;
CFFListIterator I;
int j;
bool found = false;
CFArray FF = CFArray( 1, F.length() );
if ( r > 0 )
A.nextpoint();
while ( ! found )
{
Vn = A( V );
if ( Vn != 0 )
{
U0 = A( U );
DEBOUTLN( cerr, "U0 = " << U0 );
if ( isSqrFree( U0 ) )
{
delta = content( U0 );
DEBOUTLN( cerr, "content( U0 ) = " << delta );
for ( I = F, j = 1; I.hasItem(); I++, j++ )
FF[j] = A( I.getItem().factor() );
found = nonDivisors( omega, delta, FF, D );
}
else
{
DEBOUTLN( cerr, "not sqrfree : " << sqrFree( U0 ) );
}
}
if ( ! found )
A.nextpoint();
}
DEBDECLEVEL( cerr, "findEvaluation" );
}
static int prime_number=0;
void find_good_prime(const CanonicalForm &f, int &start)
{
if (! f.inBaseDomain() )
{
CFIterator i = f;
for(;;)
{
if ( i.hasTerms() )
{
find_good_prime(i.coeff(),start);
if (start==cf_getNumSmallPrimes()) return;
if((i.exp()!=0) && ((i.exp() % cf_getSmallPrime(start))==0))
{
start++;
if (start==cf_getNumSmallPrimes()) return;
i=f;
}
else i++;
}
else break;
}
}
else
{
if (f.inZ())
{
if (start==cf_getNumSmallPrimes()) return;
while((!f.isZero()) && (mod(f,cf_getSmallPrime(start))==0))
{
start++;
if (start==cf_getNumSmallPrimes()) return;
}
}
/* should not happen!
else if (f.inQ())
{
while((f.den()!=0) && (mod(f.den(),cf_getSmallPrime(start))==0))
{
start++;
}
while((f.num()!=0) && (mod(f.num(),cf_getSmallPrime(start))==0))
{
start++;
}
}
else
cout <<"??"<< f <<"\n";
*/
}
}
static CFArray ZFactorizeMulti ( const CanonicalForm & arg )
{
prime_number=0;
bool is_rat=isOn(SW_RATIONAL);
Off(SW_RATIONAL);
DEBINCLEVEL( cerr, "ZFactorizeMulti" );
CFMap M;
CanonicalForm UU, U = compress( arg, M );
CanonicalForm delta, omega, V = LC( U, 1 );
int t = U.level();
CFFList F = factorize( V );
CFFListIterator I, J;
CFArray G, lcG, D;
int i, j, r, maxdeg;
REvaluation A( 2, t, IntRandom( 50 ) );
CanonicalForm U0;
CanonicalForm ft, ut, gt, d;
modpk b;
bool negate = false;
DEBOUTLN( cerr, "-----------------------------------------------------" );
DEBOUTLN( cerr, "trying to factorize U = " << U );
DEBOUTLN( cerr, "U is a polynomial of level = " << arg.level() );
DEBOUTLN( cerr, "U will be factorized with respect to variable " << Variable(1) );
DEBOUTLN( cerr, "the leading coefficient of U with respect to that variable is " << V );
DEBOUTLN( cerr, "which is factorized as " << F );
maxdeg = 0;
for ( i = 2; i <= t; i++ )
{
j = U.degree( Variable( i ) );
if ( j > maxdeg ) maxdeg = j;
}
if ( F.getFirst().factor().inCoeffDomain() )
{
omega = F.getFirst().factor();
F.removeFirst();
if ( omega < 0 )
{
negate = true;
omega = -omega;
U = -U;
}
}
else
omega = 1;
bool goodeval = false;
r = 0;
// for ( i = 0; i < 10*t; i++ )
// A.nextpoint();
while ( ! goodeval )
{
TIMING_START(fac_findeval);
findEvaluation( U, V, omega, F, A, U0, delta, D, r );
TIMING_END(fac_findeval);
DEBOUTLN( cerr, "the evaluation point to reduce to an univariate problem is " << A );
DEBOUTLN( cerr, "corresponding delta = " << delta );
DEBOUTLN( cerr, " omega = " << omega );
DEBOUTLN( cerr, " D = " << D );
DEBOUTLN( cerr, "now factorize the univariate polynomial " << U0 );
G = conv_to_factor_array( factorize( U0, false ) );
DEBOUTLN( cerr, "which factorizes into " << G );
{
int i=prime_number;
find_good_prime(arg,i);
find_good_prime(U0,i);
find_good_prime(U,i);
int p;
if (i==cf_getNumSmallPrimes()) p=0;
else p=cf_getSmallPrime(i);
//printf("found:p=%d (%d)\n",p,i);
if (p==0)
{
return conv_to_factor_array(CFFactor(arg,1));
//printf("out of primes - switch to non-NTL\n");
}
else if (((i==0)||(i!=prime_number)))
{
b = coeffBound_old( U, p );
prime_number=i;
}
else prime_number++;
// p!=0:
modpk bb=coeffBound_old(U0,p);
if (bb.getk() > b.getk() ) b=bb;
bb=coeffBound_old(arg,p);
if (bb.getk() > b.getk() ) b=bb;
}
if ( getZFacModulus().getpk() > b.getpk() )
b = getZFacModulus();
//printf("p=%d, k=%d\n",b.getp(),b.getk());
DEBOUTLN( cerr, "the coefficient bound of the factors of U is " << b.getpk() );
r = G.size();
lcG = CFArray( 1, r );
UU = U;
DEBOUTLN( cerr, "now trying to distribute the leading coefficients ..." );
TIMING_START(fac_distrib);
goodeval = distributeLeadingCoeffs( UU, G, lcG, F, D, delta, omega, A, r );
TIMING_END(fac_distrib);
#ifdef DEBUGOUTPUT
if ( goodeval )
{
DEBOUTLN( cerr, "the univariate factors after distribution are " << G );
DEBOUTLN( cerr, "the distributed leading coeffs are " << lcG );
DEBOUTLN( cerr, "U may have changed and is now " << UU );
DEBOUTLN( cerr, "which has leading coefficient " << LC( UU, Variable(1) ) );
if ( LC( UU, Variable(1) ) != prod( lcG ) || A(UU) != prod( G ) )
{
DEBOUTLN( cerr, "!!! distribution was not correct !!!" );
DEBOUTLN( cerr, "product of leading coeffs is " << prod( lcG ) );
DEBOUTLN( cerr, "product of univariate factors is " << prod( G ) );
DEBOUTLN( cerr, "the new U is evaluated as " << A(UU) );
}
else
DEBOUTLN( cerr, "leading coeffs correct" );
}
else
{
DEBOUTLN( cerr, "we have found a bad evaluation point" );
}
#endif
if ( goodeval )
{
TIMING_START(fac_hensel);
goodeval = Hensel( UU, G, lcG, A, b, Variable(1) );
TIMING_END(fac_hensel);
}
}
for ( i = 1; i <= r; i++ )
{
G[i] /= icontent( G[i] );
G[i] = M(G[i]);
}
// negate noch beachten !
if ( negate )
G[1] = -G[1];
DEBDECLEVEL( cerr, "ZFactorMulti" );
if(is_rat) On(SW_RATIONAL);
return G;
}
CFFList ZFactorizeMultivariate ( const CanonicalForm & f, bool issqrfree )
{
CFFList G, F, R;
CFArray GG;
CFFListIterator i, j;
CFMap M;
CanonicalForm g, cont;
Variable v1, vm;
int k, m, n;
v1 = Variable(1);
if ( issqrfree )
F = CFFactor( f, 1 );
else
F = sqrFree( f );
for ( i = F; i.hasItem(); i++ )
{
if ( i.getItem().factor().inCoeffDomain() )
{
if ( ! i.getItem().factor().isOne() )
R.append( CFFactor( i.getItem().factor(), i.getItem().exp() ) );
}
else
{
TIMING_START(fac_content);
g = compress( i.getItem().factor(), M );
// now after compress g contains Variable(1)
vm = g.mvar();
g = swapvar( g, v1, vm );
cont = content( g );
g = swapvar( g / cont, v1, vm );
cont = swapvar( cont, v1, vm );
n = i.getItem().exp();
TIMING_END(fac_content);
DEBOUTLN( cerr, "now after content ..." );
if ( g.isUnivariate() )
{
G = factorize( g, true );
for ( j = G; j.hasItem(); j++ )
if ( ! j.getItem().factor().isOne() )
R.append( CFFactor( M( j.getItem().factor() ), n ) );
}
else
{
GG = ZFactorizeMulti( g );
m = GG.max();
for ( k = GG.min(); k <= m; k++ )
if ( ! GG[k].isOne() )
R.append( CFFactor( M( GG[k] ), n ) );
}
G = factorize( cont, true );
for ( j = G; j.hasItem(); j++ )
if ( ! j.getItem().factor().isOne() )
R.append( CFFactor( M( j.getItem().factor() ), n ) );
}
}
return R;
}
#endif
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
power
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
Definition canonicalform.cc:1896
content
CanonicalForm FACTORY_PUBLIC content(const CanonicalForm &)
CanonicalForm content ( const CanonicalForm & f ).
Definition cf_gcd.cc:603
icontent
CanonicalForm FACTORY_PUBLIC icontent(const CanonicalForm &f)
CanonicalForm icontent ( const CanonicalForm & f ).
Definition cf_gcd.cc:74
degrees
int * degrees(const CanonicalForm &f, int *degs=0)
int * degrees ( const CanonicalForm & f, int * degs )
Definition cf_ops.cc:493
mod
CF_NO_INLINE FACTORY_PUBLIC CanonicalForm mod(const CanonicalForm &, const CanonicalForm &)
CFArray
Array< CanonicalForm > CFArray
Definition canonicalform.h:397
CFFListIterator
ListIterator< CFFactor > CFFListIterator
Definition canonicalform.h:394
swapvar
CanonicalForm FACTORY_PUBLIC swapvar(const CanonicalForm &, const Variable &, const Variable &)
swapvar() - swap variables x1 and x2 in f.
Definition cf_ops.cc:168
CFFList
List< CFFactor > CFFList
Definition canonicalform.h:393
CFFactor
Factor< CanonicalForm > CFFactor
Definition canonicalform.h:392
LC
CanonicalForm LC(const CanonicalForm &f)
Definition canonicalform.h:310
m
int m
Definition cfEzgcd.cc:128
Hensel
static int Hensel(const CanonicalForm &UU, CFArray &G, const Evaluation &AA, const CFArray &LeadCoeffs)
Definition cfEzgcd.cc:302
i
int i
Definition cfEzgcd.cc:132
k
int k
Definition cfEzgcd.cc:99
p
int p
Definition cfModGcd.cc:4086
g
g
Definition cfModGcd.cc:4098
GG
const CanonicalForm & GG
Definition cfModGcd.cc:4084
b
CanonicalForm b
Definition cfModGcd.cc:4111
maxNorm
CanonicalForm maxNorm(const CanonicalForm &f)
bool fdivides ( const CanonicalForm & f, const CanonicalForm & g )
Definition cf_algorithm.cc:536
cf_algorithm.h
declarations of higher level algorithms.
sqrFree
CFFList FACTORY_PUBLIC sqrFree(const CanonicalForm &f, bool sort=false)
squarefree factorization
Definition cf_factor.cc:961
factorize
CFFList FACTORY_PUBLIC factorize(const CanonicalForm &f, bool issqrfree=false)
factorization over or
Definition cf_factor.cc:409
cf_binom.h
cf_defs.h
factory switches.
SW_RATIONAL
static const int SW_RATIONAL
set to 1 for computations over Q
Definition cf_defs.h:31
out_cff
void out_cff(CFFList &L)
Definition cf_factor.cc:206
cf_iter.h
Iterators for CanonicalForm's.
compress
CanonicalForm compress(const CanonicalForm &f, CFMap &m)
CanonicalForm compress ( const CanonicalForm & f, CFMap & m ).
Definition cf_map.cc:210
cf_map.h
map polynomials
cf_getNumSmallPrimes
int cf_getNumSmallPrimes()
Definition cf_primes.cc:34
cf_getSmallPrime
int cf_getSmallPrime(int i)
Definition cf_primes.cc:28
cf_primes.h
access to prime tables
cf_reval.h
generate random evaluation points
f
FILE * f
Definition checklibs.c:9
out_cf
void out_cf(const char *s1, const CanonicalForm &f, const char *s2)
Definition cf_factor.cc:103
CFIterator
class to iterate through CanonicalForm's
Definition cf_iter.h:44
CFMap
class CFMap
Definition cf_map.h:85
CanonicalForm
factory's main class
Definition canonicalform.h:86
CanonicalForm::degree
int degree() const
Returns -1 for the zero polynomial and 0 if CO is in a base domain.
Definition canonicalform.cc:414
CanonicalForm::sign
int sign() const
int CanonicalForm::sign () const
Definition canonicalform.cc:1360
CanonicalForm::inCoeffDomain
bool inCoeffDomain() const
Definition canonicalform.cc:122
CanonicalForm::level
int level() const
level() returns the level of CO.
Definition canonicalform.cc:576
CanonicalForm::inBaseDomain
bool inBaseDomain() const
Definition canonicalform.cc:104
Evaluation
class to evaluate a polynomial at points
Definition cf_eval.h:32
Factor::exp
int exp() const
Definition ftmpl_factor.h:31
Factor::factor
T factor() const
Definition ftmpl_factor.h:30
IntRandom
generate random integers
Definition cf_random.h:56
ListIterator::hasItem
int hasItem()
Definition ftmpl_list.cc:439
ListIterator::getItem
T & getItem() const
Definition ftmpl_list.cc:431
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
REvaluation
class to generate random evaluation points
Definition cf_reval.h:26
Variable
factory's class for variables
Definition factory.h:127
modpk
class to do operations mod p^k for int's p and k
Definition fac_util.h:23
modpk::getk
int getk() const
Definition fac_util.h:36
debug.h
functions to print debug output
DEBINCLEVEL
#define DEBINCLEVEL(stream, msg)
Definition debug.h:44
DEBOUTLN
#define DEBOUTLN(stream, objects)
Definition debug.h:49
DEBDECLEVEL
#define DEBDECLEVEL(stream, msg)
Definition debug.h:45
result
return result
Definition facAbsBiFact.cc:76
modpk
return modpk(p, k)
B
b *CanonicalForm B
Definition facBivar.cc:52
facBivar.h
bivariate factorization over Q(a)
found
bool found
Definition facFactorize.cc:55
j
int j
Definition facHensel.cc:110
prod
fq_nmod_poly_t prod
Definition facHensel.cc:100
fac_distrib.h
nonDivisors
bool nonDivisors(CanonicalForm omega, CanonicalForm delta, const CFArray &F, CFArray &d)
distributeLeadingCoeffs
bool distributeLeadingCoeffs(CanonicalForm &U, CFArray &G, CFArray &lcG, const CFFList &F, const CFArray &D, CanonicalForm &delta, CanonicalForm &omega, const Evaluation &A, int r)
fac_multihensel.h
fac_multivar.h
ZFactorizeMultivariate
CFFList ZFactorizeMultivariate(const CanonicalForm &f, bool issqrfree)
fac_univar.h
isSqrFree
bool isSqrFree(const CanonicalForm &f)
getZFacModulus
modpk getZFacModulus()
fac_util.h
operations mod p^k and some other useful functions for factorization
D
#define D(A)
Definition gentable.cc:128
G
STATIC_VAR TreeM * G
Definition janet.cc:31
CxxTest::delta
bool delta(X x, Y y, D d)
Definition TestSuite.h:160
R
#define R
Definition sirandom.c:27
A
#define A
Definition sirandom.c:24
M
#define M
Definition sirandom.c:25
timing.h
TIMING_DEFINE_PRINT
#define TIMING_DEFINE_PRINT(t)
Definition timing.h:95
TIMING_END
#define TIMING_END(t)
Definition timing.h:93
TIMING_START
#define TIMING_START(t)
Definition timing.h:92