My Project
Loading...
Searching...
No Matches
cfModResultant.cc File Reference

modular resultant algorithm More...

#include "config.h"
#include <math.h>
#include "cf_assert.h"
#include "timing.h"
#include "cfModResultant.h"
#include "cf_primes.h"
#include "templates/ftmpl_functions.h"
#include "cf_map.h"
#include "cf_algorithm.h"
#include "cf_iter.h"
#include "cf_irred.h"
#include "cf_generator.h"
#include "cf_random.h"
#include "cf_map_ext.h"
#include "facFqBivarUtil.h"
#include "NTLconvert.h"
#include "FLINTconvert.h"

Go to the source code of this file.

Functions

 TIMING_DEFINE_PRINT (fac_resultant_p) static inline void myCompress(const CanonicalForm &F
 
 for (int i=0;i<=n;i++) degsf[i]
 
 if (x.level() !=1)
 
 DELETE_ARRAY (degsg)
 
static CanonicalForm oneNorm (const CanonicalForm &F)
 
static CanonicalForm uniResultant (const CanonicalForm &F, const CanonicalForm &G)
 
static void evalPoint (const CanonicalForm &F, const CanonicalForm &G, CanonicalForm &FEval, CanonicalForm &GEval, CFGenerator &evalPoint)
 
static CanonicalForm newtonInterp (const CanonicalForm &alpha, const CanonicalForm &u, const CanonicalForm &newtonPoly, const CanonicalForm &oldInterPoly, const Variable &x)
 
CanonicalForm resultantFp (const CanonicalForm &A, const CanonicalForm &B, const Variable &x, bool prob)
 modular resultant algorihtm over Fp
 
static CanonicalForm balanceUni (const CanonicalForm &f, const CanonicalForm &q)
 
static CanonicalForm symmetricRemainder (const CanonicalForm &f, const CanonicalForm &q)
 
CanonicalForm resultantZ (const CanonicalForm &A, const CanonicalForm &B, const Variable &x, bool prob)
 modular resultant algorihtm over Z
 

Variables

const CanonicalFormG
 
const CanonicalForm CFMapM
 
const CanonicalForm CFMap CFMapN
 
const CanonicalForm CFMap CFMap const Variablex
 
int * degsf = NEW_ARRAY(int,n + 1)
 
int * degsg = NEW_ARRAY(int,n + 1)
 
int both_non_zero = 0
 
int f_zero = 0
 
int g_zero = 0
 
int both_zero = 0
 
int degsfx
 
int degsgx
 
int Flevel =F.level()
 
int Glevel =G.level()
 
 else
 

Detailed Description

modular resultant algorithm

Author
Martin Lee

Definition in file cfModResultant.cc.

Function Documentation

◆ balanceUni()

static CanonicalForm balanceUni ( const CanonicalForm & f,
const CanonicalForm & q )
inlinestatic

Definition at line 527 of file cfModResultant.cc.

528{
529 Variable x = f.mvar();
530 CanonicalForm result = 0, qh = q / 2;
533 for ( i = f; i.hasTerms(); i++ ) {
534 c = mod( i.coeff(), q );
535 if ( c > qh )
536 result += power( x, i.exp() ) * (c - q);
537 else
538 result += power( x, i.exp() ) * c;
539 }
540 return result;
541}
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
CF_NO_INLINE FACTORY_PUBLIC CanonicalForm mod(const CanonicalForm &, const CanonicalForm &)
int i
Definition cfEzgcd.cc:132
Variable x
Definition cfModGcd.cc:4090
FILE * f
Definition checklibs.c:9
class to iterate through CanonicalForm's
Definition cf_iter.h:44
factory's main class
factory's class for variables
Definition factory.h:127
return result

◆ DELETE_ARRAY()

DELETE_ARRAY ( degsg )

◆ evalPoint()

static void evalPoint ( const CanonicalForm & F,
const CanonicalForm & G,
CanonicalForm & FEval,
CanonicalForm & GEval,
CFGenerator & evalPoint )
inlinestatic

Definition at line 311 of file cfModResultant.cc.

314{
315 int degF, degG;
316 Variable x= Variable (1);
317 degF= degree (F, x);
318 degG= degree (G, x);
319 do
320 {
321 if (!evalPoint.hasItems())
322 break;
323 FEval= F (evalPoint.item(), 2);
324 GEval= G (evalPoint.item(), 2);
325 if (degree (FEval, 1) < degF || degree (GEval, 1) < degG)
326 {
327 evalPoint.next();
328 continue;
329 }
330 else
331 return;
332 }
333 while (evalPoint.hasItems());
334}
int degree(const CanonicalForm &f)
static void evalPoint(const CanonicalForm &F, const CanonicalForm &G, CanonicalForm &FEval, CanonicalForm &GEval, CFGenerator &evalPoint)
const CanonicalForm & G
STATIC_VAR TreeM * G
Definition janet.cc:31

◆ for()

for ( int i = 0;i<=n;i++)

Definition at line 72 of file cfEzgcd.cc.

73 {
74 if (degsf[i] != 0 && degsg[i] != 0)
75 {
77 continue;
78 }
79 if (degsf[i] == 0 && degsg[i] != 0 && i <= G.level())
80 {
81 f_zero++;
82 continue;
83 }
84 if (degsg[i] == 0 && degsf[i] && i <= F.level())
85 {
86 g_zero++;
87 continue;
88 }
89 }
int * degsf
Definition cfEzgcd.cc:59
int f_zero
Definition cfEzgcd.cc:69
const CanonicalForm CFMap CFMap int & both_non_zero
Definition cfEzgcd.cc:57
int g_zero
Definition cfEzgcd.cc:70
int * degsg
Definition cfEzgcd.cc:60

◆ if()

if ( x.level() ! = 1)

Definition at line 67 of file cfModResultant.cc.

68 {
69 int xlevel= x.level();
70
71 for (int i= 1; i <= n; i++)
72 {
73 if (degsf[i] != 0 && degsg[i] != 0)
74 {
76 continue;
77 }
78 if (degsf[i] == 0 && degsg[i] != 0 && i <= Glevel)
79 {
80 f_zero++;
81 continue;
82 }
83 if (degsg[i] == 0 && degsf[i] && i <= Flevel)
84 {
85 g_zero++;
86 continue;
87 }
88 }
89
90 M.newpair (Variable (xlevel), Variable (1));
91 N.newpair (Variable (1), Variable (xlevel));
92 degsfx= degsf [xlevel];
93 degsgx= degsg [xlevel];
94 degsf [xlevel]= 0;
95 degsg [xlevel]= 0;
96 if ((getNumVars (F) == 2 && getNumVars (G) == 1) ||
97 (getNumVars (G) == 2 && getNumVars (F) == 1) ||
98 (getNumVars (F) == 2 && getNumVars (F) == getNumVars (G)
99 && getVars (F) == getVars (G)))
100 {
101 int pos= 2;
102 for (int i= 1; i <= n; i++)
103 {
104 if (i != xlevel)
105 {
106 if (i != pos && (degsf[i] != 0 || degsg [i] != 0))
107 {
108 M.newpair (Variable (i), Variable (pos));
109 N.newpair (Variable (pos), Variable (i));
110 pos++;
111 }
112 }
113 }
116 return;
117 }
118
119 if (both_non_zero == 0)
120 {
123 return;
124 }
125
126 // map Variables which do not occur in both polynomials to higher levels
127 int k= 1;
128 int l= 1;
129 for (int i= 1; i <= n; i++)
130 {
131 if (i == xlevel)
132 continue;
133 if (degsf[i] != 0 && degsg[i] == 0 && i <= Flevel)
134 {
135 if (k + both_non_zero != i)
136 {
137 M.newpair (Variable (i), Variable (k + both_non_zero));
138 N.newpair (Variable (k + both_non_zero), Variable (i));
139 }
140 k++;
141 }
142 if (degsf[i] == 0 && degsg[i] != 0 && i <= Glevel)
143 {
144 if (l + g_zero + both_non_zero != i)
145 {
146 M.newpair (Variable (i), Variable (l + g_zero + both_non_zero));
147 N.newpair (Variable (l + g_zero + both_non_zero), Variable (i));
148 }
149 l++;
150 }
151 }
152
153 int m= n;
154 int min_max_deg;
156 l= 0;
157 int i= 1;
158 while (k > 0)
159 {
160 if (degsf [i] != 0 && degsg [i] != 0)
161 min_max_deg= degsgx*degsf[i] + degsfx*degsg[i];
162 else
163 min_max_deg= 0;
164 while (min_max_deg == 0 && i < m)
165 {
166 i++;
167 if (degsf [i] != 0 && degsg [i] != 0)
168 min_max_deg= degsgx*degsf[i] + degsfx*degsg[i];
169 else
170 min_max_deg= 0;
171 }
172 for (int j= i + 1; j <= m; j++)
173 {
174 if (degsgx*degsf[j] + degsfx*degsg[j] <= min_max_deg &&
175 degsf[j] != 0 && degsg [j] != 0)
176 {
177 min_max_deg= degsgx*degsf[j] + degsfx*degsg[j];
178 l= j;
179 }
180 }
181 if (l != 0)
182 {
183 if (l != k && l != xlevel && k != 1)
184 {
185 M.newpair (Variable (l), Variable(k));
186 N.newpair (Variable (k), Variable(l));
187 degsf[l]= 0;
188 degsg[l]= 0;
189 l= 0;
190 }
191 else if (l < m + 1)
192 {
193 degsf[l]= 0;
194 degsg[l]= 0;
195 l= 0;
196 }
197 }
198 else if (l == 0)
199 {
200 if (i != k && i != xlevel && k != 1)
201 {
202 M.newpair (Variable (i), Variable (k));
203 N.newpair (Variable (k), Variable (i));
204 degsf[i]= 0;
205 degsg[i]= 0;
206 }
207 else if (i < m + 1)
208 {
209 degsf[i]= 0;
210 degsg[i]= 0;
211 }
212 i++;
213 }
214 k--;
215 }
216 }
CanonicalForm getVars(const CanonicalForm &f)
CanonicalForm getVars ( const CanonicalForm & f )
Definition cf_ops.cc:350
int getNumVars(const CanonicalForm &f)
int getNumVars ( const CanonicalForm & f )
Definition cf_ops.cc:314
const CanonicalForm CFMap CFMap & N
Definition cfEzgcd.cc:56
int l
Definition cfEzgcd.cc:100
int m
Definition cfEzgcd.cc:128
int Flevel
Definition cfEzgcd.cc:101
int Glevel
Definition cfEzgcd.cc:102
int k
Definition cfEzgcd.cc:99
int degsgx
int degsfx
#define DELETE_ARRAY(P)
Definition cf_defs.h:65
int j
Definition facHensel.cc:110
#define M
Definition sirandom.c:25

◆ newtonInterp()

static CanonicalForm newtonInterp ( const CanonicalForm & alpha,
const CanonicalForm & u,
const CanonicalForm & newtonPoly,
const CanonicalForm & oldInterPoly,
const Variable & x )
inlinestatic

Definition at line 337 of file cfModResultant.cc.

340{
341 CanonicalForm interPoly;
342
343 interPoly= oldInterPoly+((u - oldInterPoly (alpha, x))/newtonPoly (alpha, x))
344 *newtonPoly;
345 return interPoly;
346}
Variable alpha

◆ oneNorm()

static CanonicalForm oneNorm ( const CanonicalForm & F)
inlinestatic

Definition at line 243 of file cfModResultant.cc.

244{
245 if (F.inZ())
246 return abs (F);
247
249 for (CFIterator i= F; i.hasTerms(); i++)
250 result += oneNorm (i.coeff());
251 return result;
252}
Rational abs(const Rational &a)
Definition GMPrat.cc:436
static CanonicalForm oneNorm(const CanonicalForm &F)
bool inZ() const
predicates

◆ resultantFp()

CanonicalForm resultantFp ( const CanonicalForm & A,
const CanonicalForm & B,
const Variable & x,
bool prob = true )

modular resultant algorihtm over Fp

Returns
resultantFp returns the resultant of A and B wrt. x
Parameters
[in]Asome poly
[in]Bsome poly
[in]xsome polynomial variable
[in]probif true use probabilistic algorithm

Definition at line 349 of file cfModResultant.cc.

351{
352 ASSERT (getCharacteristic() > 0, "characteristic > 0 expected");
353
354 if (A.isZero() || B.isZero())
355 return 0;
356
357 int degAx= degree (A, x);
358 int degBx= degree (B, x);
359 if (A.level() < x.level())
360 return power (A, degBx);
361 if (B.level() < x.level())
362 return power (B, degAx);
363
364 if (degAx == 0)
365 return power (A, degBx);
366 else if (degBx == 0)
367 return power (B, degAx);
368
369 if (A.isUnivariate() && B.isUnivariate() && A.level() == B.level())
370 return uniResultant (A, B);
371
372 CanonicalForm F= A;
374
375 CFMap M, N;
376 myCompress (F, G, M, N, x);
377
378 F= M (F);
379 G= M (G);
380
381 Variable y= Variable (2);
382
383 CanonicalForm GEval, FEval, recResult, H;
384 CanonicalForm newtonPoly= 1;
385 CanonicalForm modResult= 0;
386
387 Variable z= Variable (1);
388 int bound= degAx*degree (G, 2) + degree (F, 2)*degBx;
389
390 int p= getCharacteristic();
391 CanonicalForm minpoly;
392 Variable alpha= Variable (tmax (F.level(), G.level()) + 1);
393 bool algExt= hasFirstAlgVar (F, alpha) || hasFirstAlgVar (G, alpha);
394 CFGenerator * gen;
395 bool extOfExt= false;
397 CanonicalForm primElemAlpha, imPrimElemAlpha;
398 CFList source,dest;
399 if (!algExt && (p < (1 << 28)))
400 {
401 // pass to an extension of size at least 2^29
402 // for very very large input that is maybe too small though
403 int deg= ceil (29.0*((double) log (2)/log (p)))+1;
404 minpoly= randomIrredpoly (deg, z);
405 alpha= rootOf (minpoly);
406 AlgExtGenerator AlgExtGen (alpha);
407 gen= AlgExtGen.clone();
408 for (int i= 0; i < p; i++) // skip values from the prime field
409 (*gen).next();
410 }
411 else if (!algExt)
412 {
413 FFGenerator FFGen;
414 gen= FFGen.clone();
415 }
416 else
417 {
418 int deg= ceil (29.0*((double) log (2)/log (p)));
419 if (degree (getMipo (alpha)) < deg)
420 {
421 mpz_t field_size;
422 mpz_init (field_size);
423 mpz_ui_pow_ui (field_size, p,
424 deg + degree (getMipo (alpha)) - deg%degree (getMipo (alpha)));
425
426 // field_size needs to fit in an int because of mapUp, mapDown, length of lists etc.
427 if (mpz_fits_sint_p (field_size))
428 {
429 minpoly= randomIrredpoly (deg + degree (getMipo (alpha))
430 - deg%degree (getMipo (alpha)), z);
431 v= rootOf (minpoly);
432 Variable V_buf2;
433 bool primFail= false;
434 extOfExt= true;
435 primElemAlpha= primitiveElement (alpha, V_buf2, primFail);
436 ASSERT (!primFail, "failure in integer factorizer");
437 if (primFail)
438 ; //ERROR
439 else
440 imPrimElemAlpha= mapPrimElem (primElemAlpha, alpha, v);
441 F= mapUp (F, alpha, v, primElemAlpha, imPrimElemAlpha, source, dest);
442 G= mapUp (G, alpha, v, primElemAlpha, imPrimElemAlpha, source, dest);
443 }
444 else
445 {
446 deg= deg - deg % degree (getMipo (alpha));
447 mpz_ui_pow_ui (field_size, p, deg);
448 while (deg / degree (getMipo (alpha)) >= 2 && !mpz_fits_sint_p (field_size))
449 {
450 deg -= degree (getMipo (alpha));
451 mpz_ui_pow_ui (field_size, p, deg);
452 }
453 if (deg != degree (getMipo (alpha)))
454 {
455 minpoly= randomIrredpoly (deg, z);
456 v= rootOf (minpoly);
457 Variable V_buf2;
458 bool primFail= false;
459 extOfExt= true;
460 primElemAlpha= primitiveElement (alpha, V_buf2, primFail);
461 ASSERT (!primFail, "failure in integer factorizer");
462 if (primFail)
463 ; //ERROR
464 else
465 imPrimElemAlpha= mapPrimElem (primElemAlpha, alpha, v);
466 F= mapUp (F, alpha, v, primElemAlpha, imPrimElemAlpha, source, dest);
467 G= mapUp (G, alpha, v, primElemAlpha, imPrimElemAlpha, source, dest);
468 }
469 }
470 mpz_clear (field_size);
471 }
472 AlgExtGenerator AlgExtGen (v);
473 gen= AlgExtGen.clone();
474 for (int i= 0; i < p; i++)
475 (*gen).next();
476 }
477 int count= 0;
478 int equalCount= 0;
479 CanonicalForm point;
480 do
481 {
482 evalPoint (F, G, FEval, GEval, *gen);
483
484 recResult= resultantFp (FEval, GEval, z, prob);
485
486 H= newtonInterp ((*gen).item(), recResult, newtonPoly, modResult, y);
487
488 if (H == modResult)
489 equalCount++;
490 else
491 equalCount= 0;
492
493 count++;
494 if (count > bound || (prob && equalCount == 2 && !H.inCoeffDomain()))
495 {
496 if (!algExt && degree (H, alpha) <= 0)
497 break;
498 else if (algExt)
499 {
500 if (extOfExt && !isInExtension (H, imPrimElemAlpha, 1, primElemAlpha,
501 dest, source))
502 {
503 H= mapDown (H, primElemAlpha, imPrimElemAlpha, alpha, dest, source);
504 prune (v);
505 break;
506 }
507 else if (!extOfExt)
508 break;
509 }
510 }
511
512 modResult= H;
513 newtonPoly *= (y - (*gen).item());
514 if ((*gen).hasItems())
515 (*gen).next();
516 else
517 STICKYASSERT (0, "out of evaluation points");
518 } while (1);
519
520 delete gen;
521
522 return N (H);
523}
bool hasFirstAlgVar(const CanonicalForm &f, Variable &a)
check if poly f contains an algebraic variable a
Definition cf_ops.cc:679
List< CanonicalForm > CFList
int FACTORY_PUBLIC getCharacteristic()
Definition cf_char.cc:70
int myCompress(const CanonicalForm &F, const CanonicalForm &G, CFMap &M, CFMap &N, bool topLevel)
compressing two polynomials F and G, M is used for compressing, N to reverse the compression
Definition cfModGcd.cc:92
int p
Definition cfModGcd.cc:4086
const CanonicalForm CFMap CFMap & N
CanonicalForm resultantFp(const CanonicalForm &A, const CanonicalForm &B, const Variable &x, bool prob)
modular resultant algorihtm over Fp
static CanonicalForm uniResultant(const CanonicalForm &F, const CanonicalForm &G)
const CanonicalForm CFMap & M
static CanonicalForm newtonInterp(const CanonicalForm &alpha, const CanonicalForm &u, const CanonicalForm &newtonPoly, const CanonicalForm &oldInterPoly, const Variable &x)
#define STICKYASSERT(expression, message)
Definition cf_assert.h:64
#define ASSERT(expression, message)
Definition cf_assert.h:99
CanonicalForm randomIrredpoly(int i, const Variable &x)
computes a random monic irreducible univariate polynomial in x over Fp of degree i via NTL/FLINT
Definition cf_irred.cc:26
static CanonicalForm bound(const CFMatrix &M)
Definition cf_linsys.cc:460
CanonicalForm mapPrimElem(const CanonicalForm &primElem, const Variable &alpha, const Variable &beta)
compute the image of a primitive element of in . We assume .
CanonicalForm primitiveElement(const Variable &alpha, Variable &beta, bool &fail)
determine a primitive element of , is a primitive element of a field which is isomorphic to
static CanonicalForm mapDown(const CanonicalForm &F, const Variable &alpha, const CanonicalForm &G, CFList &source, CFList &dest)
the CanonicalForm G is the output of map_up, returns F considered as an element over ,...
static CanonicalForm mapUp(const Variable &alpha, const Variable &beta)
and is a primitive element, returns the image of
Definition cf_map_ext.cc:71
generate all elements in F_p(alpha) starting from 0
virtual class for generators
virtual CFGenerator * clone() const
virtual void next()
class CFMap
Definition cf_map.h:85
int level() const
level() returns the level of CO.
generate all elements in F_p starting from 0
CFGenerator * clone() const
const CanonicalForm int const CFList const Variable & y
Definition facAbsFact.cc:53
CanonicalForm H
Definition facAbsFact.cc:60
b *CanonicalForm B
Definition facBivar.cc:52
const Variable & v
< [in] a sqrfree bivariate poly
Definition facBivar.h:39
bool isInExtension(const CanonicalForm &F, const CanonicalForm &gamma, const int k, const CanonicalForm &delta, CFList &source, CFList &dest)
tests if F is not contained in a subfield defined by gamma (Fq case) or k (GF case)
Variable FACTORY_PUBLIC rootOf(const CanonicalForm &, char name='@')
returns a symbolic root of polynomial with name name Use it to define algebraic variables
Definition variable.cc:162
CanonicalForm getMipo(const Variable &alpha, const Variable &x)
Definition variable.cc:207
void FACTORY_PUBLIC prune(Variable &alpha)
Definition variable.cc:261
template CanonicalForm tmax(const CanonicalForm &, const CanonicalForm &)
gmp_float log(const gmp_float &a)
const signed long ceil(const ampf< Precision > &x)
Definition amp.h:788
int status int void size_t count
Definition si_signals.h:69
#define A
Definition sirandom.c:24

◆ resultantZ()

CanonicalForm resultantZ ( const CanonicalForm & A,
const CanonicalForm & B,
const Variable & x,
bool prob = true )

modular resultant algorihtm over Z

Returns
resultantZ returns the resultant of A and B wrt. x
Parameters
[in]Asome poly
[in]Bsome poly
[in]xsome polynomial variable
[in]probif true use probabilistic algorithm

Definition at line 560 of file cfModResultant.cc.

562{
563 ASSERT (getCharacteristic() == 0, "characteristic > 0 expected");
564#ifndef NOASSERT
565 bool isRat= isOn (SW_RATIONAL);
566 On (SW_RATIONAL);
567 ASSERT (bCommonDen (A).isOne(), "input A is rational");
568 ASSERT (bCommonDen (B).isOne(), "input B is rational");
569 if (!isRat)
571#endif
572
573 int degAx= degree (A, x);
574 int degBx= degree (B, x);
575 if (A.level() < x.level())
576 return power (A, degBx);
577 if (B.level() < x.level())
578 return power (B, degAx);
579
580 if (degAx == 0)
581 return power (A, degBx);
582 else if (degBx == 0)
583 return power (B, degAx);
584
585 CanonicalForm F= A;
587
588 Variable X= x;
589 if (F.level() != x.level() || G.level() != x.level())
590 {
591 if (F.level() > G.level())
592 X= F.mvar();
593 else
594 X= G.mvar();
595 F= swapvar (F, X, x);
596 G= swapvar (G, X, x);
597 }
598
599 // now X is the main variable
600
601 CanonicalForm d= 0;
602 CanonicalForm dd= 0;
604 for (CFIterator i= F; i.hasTerms(); i++)
605 {
606 buf= oneNorm (i.coeff());
607 d= (buf > d) ? buf : d;
608 }
609 CanonicalForm e= 0, ee= 0;
610 for (CFIterator i= G; i.hasTerms(); i++)
611 {
612 buf= oneNorm (i.coeff());
613 e= (buf > e) ? buf : e;
614 }
615 d= power (d, degBx);
616 e= power (e, degAx);
618 for (int i= degBx + degAx; i > 1; i--)
619 bound *= i;
620 bound *= d*e;
621 bound *= 2;
622
623 bool onRational= isOn (SW_RATIONAL);
624 if (onRational)
626 int i = cf_getNumBigPrimes() - 1;
627 int p;
628 CanonicalForm l= lc (F)*lc(G);
629 CanonicalForm resultModP, q (0), newResult, newQ;
631 int equalCount= 0;
632 CanonicalForm test, newTest;
633 int count= 0;
634 do
635 {
636 p = cf_getBigPrime( i );
637 i--;
638 while ( i >= 0 && mod( l, p ) == 0)
639 {
640 p = cf_getBigPrime( i );
641 i--;
642 }
643
644 if (i <= 0)
645 return resultant (A, B, x);
646
648
649 TIMING_START (fac_resultant_p);
650 resultModP= resultantFp (mapinto (F), mapinto (G), X, prob);
651 TIMING_END_AND_PRINT (fac_resultant_p, "time to compute resultant mod p: ");
652
654
655 count++;
656 if ( q.isZero() )
657 {
658 result= mapinto(resultModP);
659 q= p;
660 }
661 else
662 {
663 chineseRemainder( result, q, mapinto (resultModP), p, newResult, newQ );
664 q= newQ;
665 result= newResult;
667 if (test != newTest)
668 {
669 newTest= test;
670 equalCount= 0;
671 }
672 else
673 equalCount++;
674 if (newQ > bound || (prob && equalCount == 2))
675 {
676 result= test;
677 break;
678 }
679 }
680 } while (1);
681
682 if (onRational)
683 On (SW_RATIONAL);
684 return swapvar (result, X, x);
685}
bool isOn(int sw)
switches
void On(int sw)
switches
void Off(int sw)
switches
CanonicalForm mapinto(const CanonicalForm &f)
CanonicalForm lc(const CanonicalForm &f)
void FACTORY_PUBLIC setCharacteristic(int c)
Definition cf_char.cc:28
CanonicalForm FACTORY_PUBLIC swapvar(const CanonicalForm &, const Variable &, const Variable &)
swapvar() - swap variables x1 and x2 in f.
Definition cf_ops.cc:168
CanonicalForm test
Definition cfModGcd.cc:4104
static CanonicalForm symmetricRemainder(const CanonicalForm &f, const CanonicalForm &q)
CanonicalForm bCommonDen(const CanonicalForm &f)
CanonicalForm bCommonDen ( const CanonicalForm & f )
void FACTORY_PUBLIC chineseRemainder(const CanonicalForm &x1, const CanonicalForm &q1, const CanonicalForm &x2, const CanonicalForm &q2, CanonicalForm &xnew, CanonicalForm &qnew)
void chineseRemainder ( const CanonicalForm & x1, const CanonicalForm & q1, const CanonicalForm & x2,...
Definition cf_chinese.cc:57
CanonicalForm FACTORY_PUBLIC resultant(const CanonicalForm &f, const CanonicalForm &g, const Variable &x)
CanonicalForm resultant ( const CanonicalForm & f, const CanonicalForm & g, const Variable & x )
static const int SW_RATIONAL
set to 1 for computations over Q
Definition cf_defs.h:31
int cf_getBigPrime(int i)
Definition cf_primes.cc:39
int cf_getNumBigPrimes()
Definition cf_primes.cc:45
Variable mvar() const
mvar() returns the main variable of CO or Variable() if CO is in a base domain.
int status int void * buf
Definition si_signals.h:69
#define TIMING_START(t)
Definition timing.h:92
#define TIMING_END_AND_PRINT(t, msg)
Definition timing.h:94

◆ symmetricRemainder()

static CanonicalForm symmetricRemainder ( const CanonicalForm & f,
const CanonicalForm & q )
inlinestatic

Definition at line 545 of file cfModResultant.cc.

546{
548 if (f.isUnivariate() || f.inCoeffDomain())
549 return balanceUni (f, q);
550 else
551 {
552 Variable x= f.mvar();
553 for (CFIterator i= f; i.hasTerms(); i++)
554 result += power (x, i.exp())*symmetricRemainder (i.coeff(), q);
555 }
556 return result;
557}
static CanonicalForm balanceUni(const CanonicalForm &f, const CanonicalForm &q)

◆ TIMING_DEFINE_PRINT()

TIMING_DEFINE_PRINT ( fac_resultant_p ) const &

◆ uniResultant()

static CanonicalForm uniResultant ( const CanonicalForm & F,
const CanonicalForm & G )
inlinestatic

Definition at line 256 of file cfModResultant.cc.

257{
258 ASSERT (getCharacteristic() > 0, "characteristic > 0 expected");
259 if (F.inCoeffDomain() && G.inCoeffDomain())
260 return 1;
261 if (F.isZero() || G.isZero())
262 return 0;
264
265#ifdef HAVE_FLINT
266 if (!hasFirstAlgVar (F, alpha) && !hasFirstAlgVar (G,alpha))
267 {
268 nmod_poly_t FLINTF, FLINTG;
269 convertFacCF2nmod_poly_t (FLINTF, F);
270 convertFacCF2nmod_poly_t (FLINTG, G);
271 mp_limb_t FLINTresult= nmod_poly_resultant (FLINTF, FLINTG);
272 nmod_poly_clear (FLINTF);
273 nmod_poly_clear (FLINTG);
274 return CanonicalForm ((long) FLINTresult);
275 }
276 return resultant (F, G, F.mvar());
277#elif defined(HAVE_NTL)
278 if (!hasFirstAlgVar (F, alpha) && !hasFirstAlgVar (G,alpha))
279 {
281 {
283 zz_p::init (getCharacteristic());
284 }
285 zz_pX NTLF= convertFacCF2NTLzzpX (F);
286 zz_pX NTLG= convertFacCF2NTLzzpX (G);
287
288 zz_p NTLResult= resultant (NTLF, NTLG);
289
290 return CanonicalForm (to_long (rep (NTLResult)));
291 }
292 //at this point F or G has an algebraic var.
294 {
296 zz_p::init (getCharacteristic());
297 }
298 zz_pX NTLMipo= convertFacCF2NTLzzpX (getMipo (alpha));
299 zz_pE::init (NTLMipo);
300 zz_pEX NTLF= convertFacCF2NTLzz_pEX (F, NTLMipo);
301 zz_pEX NTLG= convertFacCF2NTLzz_pEX (G, NTLMipo);
302 zz_pE NTLResult= resultant (NTLF, NTLG);
303
304 return convertNTLzzpE2CF (NTLResult, alpha);
305#else
306 return resultant (F, G, F.mvar());
307#endif
308}
zz_pEX convertFacCF2NTLzz_pEX(const CanonicalForm &f, const zz_pX &mipo)
CanonicalForm convertNTLzzpE2CF(const zz_pE &coefficient, const Variable &x)
zz_pX convertFacCF2NTLzzpX(const CanonicalForm &f)
VAR long fac_NTL_char
Definition NTLconvert.cc:46
CF_NO_INLINE bool isZero() const
bool inCoeffDomain() const
convertFacCF2nmod_poly_t(FLINTmipo, M)
nmod_poly_clear(FLINTmipo)

Variable Documentation

◆ both_non_zero

int both_non_zero = 0

Definition at line 59 of file cfModResultant.cc.

◆ both_zero

int both_zero = 0

Definition at line 62 of file cfModResultant.cc.

◆ degsf

degsf = NEW_ARRAY(int,n + 1)

Definition at line 50 of file cfModResultant.cc.

◆ degsfx

int degsfx

Definition at line 63 of file cfModResultant.cc.

◆ degsg

degsg = NEW_ARRAY(int,n + 1)

Definition at line 51 of file cfModResultant.cc.

◆ degsgx

int degsgx

Definition at line 63 of file cfModResultant.cc.

◆ else

else
Initial value:
{
for (int i= 1; i <= n; i++)
{
if (degsf[i] == 0 && degsg[i] == 0)
{
continue;
}
else
{
if (both_zero != 0 && i != 1)
{
M.newpair (Variable (i), Variable (i - both_zero));
N.newpair (Variable (i - both_zero), Variable (i));
}
}
}
}
int both_zero

Definition at line 217 of file cfModResultant.cc.

218 {
219 //arrange Variables such that no gaps occur
220 for (int i= 1; i <= n; i++)
221 {
222 if (degsf[i] == 0 && degsg[i] == 0)
223 {
224 both_zero++;
225 continue;
226 }
227 else
228 {
229 if (both_zero != 0 && i != 1)
230 {
231 M.newpair (Variable (i), Variable (i - both_zero));
232 N.newpair (Variable (i - both_zero), Variable (i));
233 }
234 }
235 }
236 }

◆ f_zero

int f_zero = 0

Definition at line 60 of file cfModResultant.cc.

◆ Flevel

int Flevel =F.level()

Definition at line 64 of file cfModResultant.cc.

◆ G

Definition at line 46 of file cfModResultant.cc.

◆ g_zero

int g_zero = 0

Definition at line 61 of file cfModResultant.cc.

◆ Glevel

int Glevel =G.level()

Definition at line 65 of file cfModResultant.cc.

◆ M

Definition at line 46 of file cfModResultant.cc.

◆ N

Definition at line 47 of file cfModResultant.cc.

◆ x

Initial value:
{
int n= tmax (F.level(), G.level())

Definition at line 47 of file cfModResultant.cc.