Loading...
Searching...
No Matches
fac_distrib.cc
Go to the documentation of this file.
/* emacs edit mode for this file is -*- C++ -*- */
/* $Id: fac_distrib.cc 14344 2011-07-25 14:08:17Z mlee $ */
#include <config.h>
#include "assert.h"
#include "debug.h"
#include "cf_defs.h"
#include "canonicalform.h"
#include "cf_algorithm.h"
#include "cf_iter.h"
#include "fac_util.h"
#include "fac_multihensel.h"
#ifndef HAVE_NTL
bool
nonDivisors ( CanonicalForm omega, CanonicalForm delta, const CFArray & F, CFArray & d )
{
DEBINCLEVEL( cerr, "nonDivisors" );
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.isOne() );
if ( q == 1 )
{
DEBDECLEVEL( cerr, "nonDivisors" );
return false;
}
}
d[i] = q;
}
DEBDECLEVEL( cerr, "nonDivisors" );
return true;
}
bool
checkEvaluation ( const CanonicalForm & U, const CanonicalForm & lcU, const CanonicalForm & omega, const CFFList & F, const Evaluation & A, CanonicalForm & delta )
{
CanonicalForm Vn, U0 = A( U );
CFFListIterator I;
int j;
CFArray FF = CFArray( 1, F.length() );
CFArray D;
Vn = A( lcU );
if ( Vn.isZero() )
return false;
delta = content( U0 );
for ( I = F, j = 1; I.hasItem(); I++, j++ )
FF[j] = A( I.getItem().factor() );
return nonDivisors( omega, delta, FF, D );
}
bool
distributeLeadingCoeffs ( CanonicalForm & U, CFArray & G, CFArray & lcG, const CFFList & F, const CFArray & D, CanonicalForm & delta, CanonicalForm & omega, const Evaluation & A, int r )
{
DEBINCLEVEL( cerr, "distributeLeadingCoeffs" );
CanonicalForm ut, gt, d, ft;
CanonicalForm dd, quot;
CFFListIterator I;
int m, j, i;
lcG = CFArray( 1, r );
for ( j = 1; j <= r; j ++ )
lcG[j] = 1;
for ( I = F, i = 1; I.hasItem(); I++, i++ )
{
ft = I.getItem().factor();
m = I.getItem().exp();
DEBOUTLN( cerr, "trying to distribute " << ft );
DEBOUTLN( cerr, "which is tested with " << D[i] );
DEBOUTLN( cerr, "and contained to the power of " << m );
j = 1;
while ( m > 0 && j <= r )
{
ut = lc( G[j] );
DEBOUTLN( cerr, "checking with " << ut );
while ( m > 0 && fdivides( D[i], ut, quot ) )
{
DEBOUTLN( cerr, "match found" );
m--; ut= quot;
lcG[j] *= ft;
}
j++;
}
if (m != 0)
{
DEBDECLEVEL( cerr, "distributeLeadingCoeffs" );
return false;
}
}
DEBOUTLN( cerr, "the leading coeffs before omega and delta correction: " << lcG );
if ( !omega.isOne() )
{
for ( j = 1; j <= r; j++ )
{
// G[j] *= omega;
lcG[j] *= omega;
if(lc( G[j] ).isZero()) return false;
G[j] = G[j] * ( A( lcG[j] ) / lc( G[j] ) );
}
U *= power( omega, r-1 );
}
if ( !delta.isOne() )
{
for ( j = 1; j <= r; j++ )
{
lcG[j] *= delta;
if(lc( G[j] ).isZero()) return false;
G[j] = G[j] * ( A( lcG[j] ) / lc( G[j] ) );
}
U *= power( delta, r );
}
DEBDECLEVEL( cerr, "distributeLeadingCoeffs" );
return true;
}
static void
gfbAdjoin ( const CanonicalForm & F, CFList & L )
{
if ( F.isOne() )
return;
if ( L.isEmpty() )
{
L.append( F );
return;
}
CanonicalForm h, quot, f = F;
CFListIterator i, j;
for ( i = L; i.hasItem() && ! f.isOne(); )
{
h = gcd( f, i.getItem() );
if ( h.isOne() )
{
i++;
continue;
}
while ( fdivides( h, f, quot ) )
f= quot;
CFList D( h );
gfbAdjoin( i.getItem() / h, D );
for ( j = D; j.hasItem(); j++ )
i.append( j.getItem() );
i.remove( true );
}
if ( ! f.isOne() )
L.append( f );
}
CFList
gcdFreeBasis ( const CFList L )
{
CFListIterator i;
CFList R;
for ( i = L; i.hasItem(); i++ )
gfbAdjoin( i.getItem(), R );
return R;
}
bool
Univar2Bivar(const CanonicalForm & U, CFArray & G, const Evaluation & A, const modpk & bound, const Variable & x )
{
CanonicalForm l = LC( U, Variable(1) );
int n = G.size();
CFArray lcG(1,n);
for ( int i = 1; i <= n; i++ )
{
G[i] *= A(l)/lc(G[i]);
lcG[i] = l;
}
return Hensel( U * power( l, n-1 ), G, lcG, A, bound, x );
}
bool
Hensel2 ( const CanonicalForm & U, CFArray & G, const Evaluation & A, const modpk & bound, const Variable & x )
{
int i,n = G.size(); // n is number of factors of U
CFArray TrueLcs(1, n);
for (i=1; i <= n; i++)
TrueLcs[i] = 1;
Variable y;
CanonicalForm lcU = LC ( U, Variable(1) );
while (! lcU.inCoeffDomain())
{
y = lcU.mvar(); // should make a more intelligent choice
CanonicalForm BivariateU = A ( U, 2, y.level() - 1 );
CFArray BivariateFactors = G;
CFArray lcFactors(1,n);
Univar2Bivar(BivariateU, BivariateFactors, A, bound, y);
for (i = 1; i <= n; i++)
{
BivariateFactors[i] /= content(BivariateFactors[i]);
lcFactors[i] = LC(BivariateFactors[i],Variable(1));
}
// GFB = GcdFreeBasis(lcFactors); // this is not right... should probably make everything squarefree
// Hensel2(lcU, GFB, A, bound, y);
}
for (i = 1; i <= n; i++)
G[i] *= A(TrueLcs[i])/lc(G[i]);
return Hensel(U, G, TrueLcs, A, bound, x);
}
#endif
abs
Rational abs(const Rational &a)
Definition GMPrat.cc:436
power
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
Definition canonicalform.cc:1896
canonicalform.h
Header for factory's main class CanonicalForm.
content
CanonicalForm FACTORY_PUBLIC content(const CanonicalForm &)
CanonicalForm content ( const CanonicalForm & f ).
Definition cf_gcd.cc:603
lc
CanonicalForm lc(const CanonicalForm &f)
Definition canonicalform.h:304
CFArray
Array< CanonicalForm > CFArray
Definition canonicalform.h:397
CFFListIterator
ListIterator< CFFactor > CFFListIterator
Definition canonicalform.h:394
CFListIterator
ListIterator< CanonicalForm > CFListIterator
Definition canonicalform.h:396
CFFList
List< CFFactor > CFFList
Definition canonicalform.h:393
CFList
List< CanonicalForm > CFList
Definition canonicalform.h:395
LC
CanonicalForm LC(const CanonicalForm &f)
Definition canonicalform.h:310
l
int l
Definition cfEzgcd.cc:100
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
x
Variable x
Definition cfModGcd.cc:4090
cf_algorithm.h
declarations of higher level algorithms.
fdivides
bool fdivides(const CanonicalForm &f, const CanonicalForm &g)
cf_defs.h
factory switches.
cf_iter.h
Iterators for CanonicalForm's.
bound
static CanonicalForm bound(const CFMatrix &M)
Definition cf_linsys.cc:460
f
FILE * f
Definition checklibs.c:9
Array::size
int size() const
Definition ftmpl_array.cc:92
CanonicalForm
factory's main class
Definition canonicalform.h:86
CanonicalForm::isZero
CF_NO_INLINE bool isZero() const
CanonicalForm::mvar
Variable mvar() const
mvar() returns the main variable of CO or Variable() if CO is in a base domain.
Definition canonicalform.cc:593
CanonicalForm::isOne
CF_NO_INLINE bool isOne() const
CanonicalForm::inCoeffDomain
bool inCoeffDomain() const
Definition canonicalform.cc:122
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
ListIterator::hasItem
int hasItem()
Definition ftmpl_list.cc:439
ListIterator::getItem
T & getItem() const
Definition ftmpl_list.cc:431
List::length
int length() const
Definition ftmpl_list.cc:273
List::append
void append(const T &)
Definition ftmpl_list.cc:256
List::isEmpty
int isEmpty() const
Definition ftmpl_list.cc:267
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
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
y
const CanonicalForm int const CFList const Variable & y
Definition facAbsFact.cc:53
j
int j
Definition facHensel.cc:110
isZero
bool isZero(const CFArray &A)
checks if entries of A are zero
Definition facSparseHensel.h:468
gcdFreeBasis
CFList gcdFreeBasis(const CFList L)
nonDivisors
bool nonDivisors(CanonicalForm omega, CanonicalForm delta, const CFArray &F, CFArray &d)
checkEvaluation
bool checkEvaluation(const CanonicalForm &U, const CanonicalForm &lcU, const CanonicalForm &omega, const CFFList &F, const Evaluation &A, CanonicalForm &delta)
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_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
h
STATIC_VAR Poly * h
Definition janet.cc:971
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
gcd
int gcd(int a, int b)
Definition walkSupport.cc:836