My Project
fac_distrib.cc
Go to the documentation of this file.
1 /* emacs edit mode for this file is -*- C++ -*- */
2 /* $Id: fac_distrib.cc 14344 2011-07-25 14:08:17Z mlee $ */
3 
4 #include <config.h>
5 
6 #include "assert.h"
7 #include "debug.h"
8 
9 #include "cf_defs.h"
10 #include "canonicalform.h"
11 #include "cf_algorithm.h"
12 #include "cf_iter.h"
13 #include "fac_util.h"
14 #include "fac_multihensel.h"
15 
16 #ifndef HAVE_NTL
17 
18 bool
20 {
21  DEBINCLEVEL( cerr, "nonDivisors" );
22  CanonicalForm q, r;
23  int k = F.size();
24  d = CFArray( 0, k );
25  d[0] = delta * omega;
26  for ( int i = 1; i <= k; i++ )
27  {
28  q = abs(F[i]);
29  for ( int j = i-1; j >= 0; j-- )
30  {
31  r = d[j];
32  do
33  {
34  r = gcd( r, q );
35  q = q / r;
36  } while ( !r.isOne() );
37  if ( q == 1 )
38  {
39  DEBDECLEVEL( cerr, "nonDivisors" );
40  return false;
41  }
42  }
43  d[i] = q;
44  }
45  DEBDECLEVEL( cerr, "nonDivisors" );
46  return true;
47 }
48 
49 bool
50 checkEvaluation ( const CanonicalForm & U, const CanonicalForm & lcU, const CanonicalForm & omega, const CFFList & F, const Evaluation & A, CanonicalForm & delta )
51 {
52  CanonicalForm Vn, U0 = A( U );
54  int j;
55  CFArray FF = CFArray( 1, F.length() );
56  CFArray D;
57  Vn = A( lcU );
58  if ( Vn.isZero() )
59  return false;
60  delta = content( U0 );
61  for ( I = F, j = 1; I.hasItem(); I++, j++ )
62  FF[j] = A( I.getItem().factor() );
63  return nonDivisors( omega, delta, FF, D );
64 }
65 
66 bool
67 distributeLeadingCoeffs ( CanonicalForm & U, CFArray & G, CFArray & lcG, const CFFList & F, const CFArray & D, CanonicalForm & delta, CanonicalForm & omega, const Evaluation & A, int r )
68 {
69  DEBINCLEVEL( cerr, "distributeLeadingCoeffs" );
70  CanonicalForm ut, gt, d, ft;
71  CanonicalForm dd, quot;
73  int m, j, i;
74  lcG = CFArray( 1, r );
75  for ( j = 1; j <= r; j ++ )
76  lcG[j] = 1;
77 
78  for ( I = F, i = 1; I.hasItem(); I++, i++ )
79  {
80  ft = I.getItem().factor();
81  m = I.getItem().exp();
82  DEBOUTLN( cerr, "trying to distribute " << ft );
83  DEBOUTLN( cerr, "which is tested with " << D[i] );
84  DEBOUTLN( cerr, "and contained to the power of " << m );
85  j = 1;
86  while ( m > 0 && j <= r )
87  {
88  ut = lc( G[j] );
89  DEBOUTLN( cerr, "checking with " << ut );
90  while ( m > 0 && fdivides( D[i], ut, quot ) )
91  {
92  DEBOUTLN( cerr, "match found" );
93  m--; ut= quot;
94  lcG[j] *= ft;
95  }
96  j++;
97  }
98  if (m != 0)
99  {
100  DEBDECLEVEL( cerr, "distributeLeadingCoeffs" );
101  return false;
102  }
103  }
104  DEBOUTLN( cerr, "the leading coeffs before omega and delta correction: " << lcG );
105  if ( !omega.isOne() )
106  {
107  for ( j = 1; j <= r; j++ )
108  {
109 // G[j] *= omega;
110  lcG[j] *= omega;
111  if(lc( G[j] ).isZero()) return false;
112  G[j] = G[j] * ( A( lcG[j] ) / lc( G[j] ) );
113  }
114  U *= power( omega, r-1 );
115  }
116  if ( !delta.isOne() )
117  {
118  for ( j = 1; j <= r; j++ )
119  {
120  lcG[j] *= delta;
121  if(lc( G[j] ).isZero()) return false;
122  G[j] = G[j] * ( A( lcG[j] ) / lc( G[j] ) );
123  }
124  U *= power( delta, r );
125  }
126  DEBDECLEVEL( cerr, "distributeLeadingCoeffs" );
127  return true;
128 }
129 
130 
131 static void
132 gfbAdjoin ( const CanonicalForm & F, CFList & L )
133 {
134  if ( F.isOne() )
135  return;
136  if ( L.isEmpty() )
137  {
138  L.append( F );
139  return;
140  }
141  CanonicalForm h, quot, f = F;
142  CFListIterator i, j;
143  for ( i = L; i.hasItem() && ! f.isOne(); )
144  {
145  h = gcd( f, i.getItem() );
146  if ( h.isOne() )
147  {
148  i++;
149  continue;
150  }
151  while ( fdivides( h, f, quot ) )
152  f= quot;
153  CFList D( h );
154  gfbAdjoin( i.getItem() / h, D );
155  for ( j = D; j.hasItem(); j++ )
156  i.append( j.getItem() );
157  i.remove( true );
158  }
159  if ( ! f.isOne() )
160  L.append( f );
161 }
162 
163 
164 CFList
165 gcdFreeBasis ( const CFList L )
166 {
168  CFList R;
169  for ( i = L; i.hasItem(); i++ )
170  gfbAdjoin( i.getItem(), R );
171  return R;
172 }
173 
174 bool
175 Univar2Bivar(const CanonicalForm & U, CFArray & G, const Evaluation & A, const modpk & bound, const Variable & x )
176 {
177  CanonicalForm l = LC( U, Variable(1) );
178  int n = G.size();
179  CFArray lcG(1,n);
180  for ( int i = 1; i <= n; i++ )
181  {
182  G[i] *= A(l)/lc(G[i]);
183  lcG[i] = l;
184  }
185  return Hensel( U * power( l, n-1 ), G, lcG, A, bound, x );
186 }
187 
188 bool
189 Hensel2 ( const CanonicalForm & U, CFArray & G, const Evaluation & A, const modpk & bound, const Variable & x )
190 {
191  int i,n = G.size(); // n is number of factors of U
192  CFArray TrueLcs(1, n);
193  for (i=1; i <= n; i++)
194  TrueLcs[i] = 1;
195  Variable y;
196  CanonicalForm lcU = LC ( U, Variable(1) );
197  while (! lcU.inCoeffDomain())
198  {
199  y = lcU.mvar(); // should make a more intelligent choice
200  CanonicalForm BivariateU = A ( U, 2, y.level() - 1 );
201  CFArray BivariateFactors = G;
202  CFArray lcFactors(1,n);
203  Univar2Bivar(BivariateU, BivariateFactors, A, bound, y);
204  for (i = 1; i <= n; i++)
205  {
206  BivariateFactors[i] /= content(BivariateFactors[i]);
207  lcFactors[i] = LC(BivariateFactors[i],Variable(1));
208  }
209 // GFB = GcdFreeBasis(lcFactors); // this is not right... should probably make everything squarefree
210 // Hensel2(lcU, GFB, A, bound, y);
211  }
212  for (i = 1; i <= n; i++)
213  G[i] *= A(TrueLcs[i])/lc(G[i]);
214  return Hensel(U, G, TrueLcs, A, bound, x);
215 }
216 #endif
Rational abs(const Rational &a)
Definition: GMPrat.cc:436
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
Header for factory's main class CanonicalForm.
CanonicalForm lc(const CanonicalForm &f)
Array< CanonicalForm > CFArray
CanonicalForm content(const CanonicalForm &)
CanonicalForm content ( const CanonicalForm & f )
Definition: cf_gcd.cc:603
CanonicalForm LC(const CanonicalForm &f)
int l
Definition: cfEzgcd.cc:100
int m
Definition: cfEzgcd.cc:128
int i
Definition: cfEzgcd.cc:132
int k
Definition: cfEzgcd.cc:99
Variable x
Definition: cfModGcd.cc:4084
bool fdivides(const CanonicalForm &f, const CanonicalForm &g)
bool fdivides ( const CanonicalForm & f, const CanonicalForm & g )
declarations of higher level algorithms.
factory switches.
Iterators for CanonicalForm's.
static CanonicalForm bound(const CFMatrix &M)
Definition: cf_linsys.cc:460
FILE * f
Definition: checklibs.c:9
int size() const
Definition: ftmpl_array.cc:92
factory's main class
Definition: canonicalform.h:86
CF_NO_INLINE bool isZero() const
Variable mvar() const
mvar() returns the main variable of CO or Variable() if CO is in a base domain.
CF_NO_INLINE bool isOne() const
bool inCoeffDomain() const
int level() const
level() returns the level of CO.
class to evaluate a polynomial at points
Definition: cf_eval.h:32
T & getItem() const
Definition: ftmpl_list.cc:431
int length() const
Definition: ftmpl_list.cc:273
void append(const T &)
Definition: ftmpl_list.cc:256
int isEmpty() const
Definition: ftmpl_list.cc:267
factory's class for variables
Definition: factory.h:134
class to do operations mod p^k for int's p and k
Definition: fac_util.h:23
functions to print debug output
#define DEBINCLEVEL(stream, msg)
Definition: debug.h:44
#define DEBOUTLN(stream, objects)
Definition: debug.h:49
#define DEBDECLEVEL(stream, msg)
Definition: debug.h:45
const CanonicalForm int const CFList const Variable & y
Definition: facAbsFact.cc:53
int j
Definition: facHensel.cc:110
bool isZero(const CFArray &A)
checks if entries of A are zero
CFList gcdFreeBasis(const CFList L)
bool nonDivisors(CanonicalForm omega, CanonicalForm delta, const CFArray &F, CFArray &d)
bool checkEvaluation(const CanonicalForm &U, const CanonicalForm &lcU, const CanonicalForm &omega, const CFFList &F, const Evaluation &A, CanonicalForm &delta)
bool distributeLeadingCoeffs(CanonicalForm &U, CFArray &G, CFArray &lcG, const CFFList &F, const CFArray &D, CanonicalForm &delta, CanonicalForm &omega, const Evaluation &A, int r)
bool Hensel(const CanonicalForm &U, CFArray &G, const CFArray &lcG, const Evaluation &A, const modpk &bound, const Variable &)
operations mod p^k and some other useful functions for factorization
#define D(A)
Definition: gentable.cc:131
STATIC_VAR TreeM * G
Definition: janet.cc:31
STATIC_VAR Poly * h
Definition: janet.cc:971
bool delta(X x, Y y, D d)
Definition: TestSuite.h:160
#define R
Definition: sirandom.c:27
#define A
Definition: sirandom.c:24
int gcd(int a, int b)
Definition: walkSupport.cc:836