 |
My Project
|
Loading...
Searching...
No Matches
|
My Project
|
#include "config.h"#include "cf_assert.h"#include "cf_factory.h"#include "cf_defs.h"#include "canonicalform.h"#include "cf_algorithm.h"#include "variable.h"#include "cf_iter.h"#include "templates/ftmpl_functions.h"#include "cfGcdAlgExt.h"Go to the source code of this file.
Functions | |
| CanonicalForm | psq (const CanonicalForm &f, const CanonicalForm &g, const Variable &x) |
| cf_algorithm.cc - simple mathematical algorithms. | |
| CanonicalForm | bCommonDen (const CanonicalForm &f) |
| void psqr ( const CanonicalForm & f, const CanonicalForm & g, CanonicalForm & q, CanonicalForm & r, const Variable & x ) | |
| CanonicalForm | maxNorm (const CanonicalForm &f) |
| bool fdivides ( const CanonicalForm & f, const CanonicalForm & g ) | |
| CanonicalForm bCommonDen | ( | const CanonicalForm & | f | ) |
void psqr ( const CanonicalForm & f, const CanonicalForm & g, CanonicalForm & q, CanonicalForm & r, const Variable & x )
psqr() - calculate pseudo quotient and remainder of f' and g' with respect to `x'.
Returns the pseudo quotient of f' and g' in q', the pseudo remainder in r'. `g' must not equal zero.
See `psr()' for more detailed information.
f, g: Current q, r: Anything x: Polynomial
This is not an optimal implementation. Better would have been an implementation in InternalPoly' avoiding the exponentiation of the leading coefficient of g'. It seemed not worth to do so.
**/ void psqr ( const CanonicalForm & f, const CanonicalForm & g, CanonicalForm & q, CanonicalForm & r, const Variable& x ) { ASSERT( x.level() > 0, "type error: polynomial variable expected" ); ASSERT( ! g.isZero(), "math error: division by zero" );
swap variables such that x's level is larger or equal than both f's and g's levels. Variable X = tmax( tmax( f.mvar(), g.mvar() ), x ); CanonicalForm F = swapvar( f, x, X ); CanonicalForm G = swapvar( g, x, X );
now, we have to calculate the pseudo remainder of F and G w.r.t. X int fDegree = degree( F, X ); int gDegree = degree( G, X ); if ( fDegree < 0 || fDegree < gDegree ) { q = 0; r = f; } else { divrem( power( LC( G, X ), fDegree-gDegree+1 ) * F, G, q, r ); q = swapvar( q, x, X ); r = swapvar( r, x, X ); } }
/** static CanonicalForm internalBCommonDen ( const CanonicalForm & f )
internalBCommonDen() - recursively calculate multivariate common denominator of coefficients of `f'.
Used by: bCommonDen()
f: Poly( Q ) Switches: isOff( SW_RATIONAL )
**/ static CanonicalForm internalBCommonDen ( const CanonicalForm & f ) { if ( f.inBaseDomain() ) return f.den(); else { CanonicalForm result = 1; for ( CFIterator i = f; i.hasTerms(); i++ ) result = blcm( result, internalBCommonDen( i.coeff() ) ); return result; } }
/** CanonicalForm bCommonDen ( const CanonicalForm & f )
bCommonDen() - calculate multivariate common denominator of coefficients of `f'.
The common denominator is calculated with respect to all coefficients of f' which are in a base domain. In other words, common_den( f' ) * `f' is guaranteed to have integer coefficients only. The common denominator of zero is one.
Returns something non-trivial iff the current domain is Q.
f: CurrentPP
Definition at line 293 of file cf_algorithm.cc.
| CanonicalForm maxNorm | ( | const CanonicalForm & | f | ) |
bool fdivides ( const CanonicalForm & f, const CanonicalForm & g )
fdivides() - check whether f' divides g'.
Returns true iff f' divides g'. Uses some extra heuristic to avoid polynomial division. Without the heuristic, the test essentialy looks like `divremt(g, f, q, r) && r.isZero()'.
f, g: Current
Elements from prime power domains (or polynomials over such domains) are admissible if f' (or lc(f'), resp.) is not a zero divisor. This is a slightly stronger precondition than mathematically necessary since divisibility is a well-defined notion in arbitrary rings. Hence, we decided not to declare the weaker type `CurrentPP'.
One may consider the the test fdivides( f.LC(), g.LC() )' in the main if'-test superfluous since divremt()' in the if'-body repeats the test. However, `divremt()' does not use any heuristic to do so.
It seems not reasonable to call fdivides()' from divremt()' to check divisibility of leading coefficients. fdivides()' is on a relatively high level compared to divremt()'.
**/ bool fdivides ( const CanonicalForm & f, const CanonicalForm & g ) { trivial cases if ( g.isZero() ) return true; else if ( f.isZero() ) return false;
if ( (f.inCoeffDomain() || g.inCoeffDomain()) && ((getCharacteristic() == 0 && isOn( SW_RATIONAL )) || (getCharacteristic() > 0) )) { if we are in a field all elements not equal to zero are units if ( f.inCoeffDomain() ) return true; else g.inCoeffDomain() return false; }
we may assume now that both levels either equal LEVELBASE or are greater zero int fLevel = f.level(); int gLevel = g.level(); if ( (gLevel > 0) && (fLevel == gLevel) ) f and g are polynomials in the same main variable if ( degree( f ) <= degree( g ) && fdivides( f.tailcoeff(), g.tailcoeff() ) && fdivides( f.LC(), g.LC() ) ) { CanonicalForm q, r; return divremt( g, f, q, r ) && r.isZero(); } else return false; else if ( gLevel < fLevel ) g is a coefficient w.r.t. f return false; else { either f is a coefficient w.r.t. polynomial g or both f and g are from a base domain (should be Z or Z/p^n, then) CanonicalForm q, r; return divremt( g, f, q, r ) && r.isZero(); } }
/ same as fdivides if true returns quotient quot of g by f otherwise quot == 0 bool fdivides ( const CanonicalForm & f, const CanonicalForm & g, CanonicalForm& quot ) { quot= 0; trivial cases if ( g.isZero() ) return true; else if ( f.isZero() ) return false;
if ( (f.inCoeffDomain() || g.inCoeffDomain()) && ((getCharacteristic() == 0 && isOn( SW_RATIONAL )) || (getCharacteristic() > 0) )) { if we are in a field all elements not equal to zero are units if ( f.inCoeffDomain() ) { quot= g/f; return true; } else g.inCoeffDomain() return false; }
we may assume now that both levels either equal LEVELBASE or are greater zero int fLevel = f.level(); int gLevel = g.level(); if ( (gLevel > 0) && (fLevel == gLevel) ) f and g are polynomials in the same main variable if ( degree( f ) <= degree( g ) && fdivides( f.tailcoeff(), g.tailcoeff() ) && fdivides( f.LC(), g.LC() ) ) { CanonicalForm q, r; if (divremt( g, f, q, r ) && r.isZero()) { quot= q; return true; } else return false; } else return false; else if ( gLevel < fLevel ) g is a coefficient w.r.t. f return false; else { either f is a coefficient w.r.t. polynomial g or both f and g are from a base domain (should be Z or Z/p^n, then) CanonicalForm q, r; if (divremt( g, f, q, r ) && r.isZero()) { quot= q; return true; } else return false; } }
/ same as fdivides but handles zero divisors in Z_p[t]/(f)[x1,...,xn] for reducible f bool tryFdivides ( const CanonicalForm & f, const CanonicalForm & g, const CanonicalForm& M, bool& fail ) { fail= false; trivial cases if ( g.isZero() ) return true; else if ( f.isZero() ) return false;
if (f.inCoeffDomain() || g.inCoeffDomain()) { if we are in a field all elements not equal to zero are units if ( f.inCoeffDomain() ) { CanonicalForm inv; tryInvert (f, M, inv, fail); return !fail; } else { return false; } }
we may assume now that both levels either equal LEVELBASE or are greater zero int fLevel = f.level(); int gLevel = g.level(); if ( (gLevel > 0) && (fLevel == gLevel) ) { if (degree( f ) > degree( g )) return false; bool dividestail= tryFdivides (f.tailcoeff(), g.tailcoeff(), M, fail);
if (fail || !dividestail) return false; bool dividesLC= tryFdivides (f.LC(),g.LC(), M, fail); if (fail || !dividesLC) return false; CanonicalForm q,r; bool divides= tryDivremt (g, f, q, r, M, fail); if (fail || !divides) return false; return r.isZero(); } else if ( gLevel < fLevel ) { g is a coefficient w.r.t. f return false; } else { either f is a coefficient w.r.t. polynomial g or both f and g are from a base domain (should be Z or Z/p^n, then) CanonicalForm q, r; bool divides= tryDivremt (g, f, q, r, M, fail); if (fail || !divides) return false; return r.isZero(); } }
/** CanonicalForm maxNorm ( const CanonicalForm & f )
maxNorm() - return maximum norm of `f'.
That is, the base coefficient of `f' with the largest absolute value.
Valid for arbitrary polynomials over arbitrary domains, but most useful for multivariate polynomials over Z.
f: CurrentPP
Definition at line 536 of file cf_algorithm.cc.
| CanonicalForm psq | ( | const CanonicalForm & | f, |
| const CanonicalForm & | g, | ||
| const Variable & | x ) |
cf_algorithm.cc - simple mathematical algorithms.
Hierarchy: mathematical algorithms on canonical forms
A "mathematical" algorithm is an algorithm which calculates some mathematical function in contrast to a "structural" algorithm which gives structural information on polynomials.
Compare these functions to the functions in `cf_ops.cc', which are structural algorithms.
**/
void out_cf(const char *s1,const CanonicalForm &f,const char *s2);
/** CanonicalForm psr ( const CanonicalForm & f, const CanonicalForm & g, const Variable & x )
psr() - return pseudo remainder of f' and g' with respect to `x'.
`g' must not equal zero.
For f and g in R[x], R an arbitrary ring, g != 0, there is a representation
LC(g)^s*f = g*q + r
with r = 0 or deg(r) < deg(g) and s = 0 if f = 0 or s = max( 0, deg(f)-deg(g)+1 ) otherwise. r = psr(f, g) and q = psq(f, g) are called "pseudo remainder" and "pseudo quotient", resp. They are uniquely determined if LC(g) is not a zero divisor in R.
See H.-J. Reiffen/G. Scheja/U. Vetter - "Algebra", 2nd ed., par. 15, for a reference.
f, g: Current x: Polynomial
Polynomials over prime power domains are admissible if lc(LC(g',x')) is not a zero divisor. This is a slightly stronger precondition than mathematically necessary since pseudo remainder and quotient are well-defined if LC(g',x') is not a zero divisor.
For example, psr(y^2, (13*x+1)*y) is well-defined in (Z/13^2[x])[y] since (13*x+1) is not a zero divisor. But calculating it with Factory would fail since 13 is a zero divisor in Z/13^2.
Due to this inconsistency with mathematical notion, we decided not to declare type CurrentPP' for f' and `g'.
This is not an optimal implementation. Better would have been an implementation in InternalPoly' avoiding the exponentiation of the leading coefficient of g'. In contrast to psq()' and psqr()' it definitely seems worth to implement the pseudo remainder on the internal level.
psr ( const CanonicalForm &rr, const CanonicalForm &vv, const Variable & x ) { CanonicalForm r=rr, v=vv, l, test, lu, lv, t, retvalue; int dr, dv, d,n=0;
dr = degree( r, x ); if (dr>0) { dv = degree( v, x ); if (dv <= dr) {l=LC(v,x); v = v -l*power(x,dv);} else { l = 1; } d= dr-dv+1; out_cf("psr(",rr," "); out_cf("",vv," "); printf(" var=%d\n",x.level()); while ( ( dv <= dr ) && ( !r.isZero()) ) { test = power(x,dr-dv)*v*LC(r,x); if ( dr == 0 ) { r= CanonicalForm(0); } else { r= r - LC(r,x)*power(x,dr); } r= l*r -test; dr= degree(r,x); n+=1; } r= power(l, d-n)*r; } return r; }
/** CanonicalForm psq ( const CanonicalForm & f, const CanonicalForm & g, const Variable & x )
psq() - return pseudo quotient of f' and g' with respect to `x'.
`g' must not equal zero.
f, g: Current x: Polynomial
This is not an optimal implementation. Better would have been an implementation in InternalPoly' avoiding the exponentiation of the leading coefficient of g'. It seemed not worth to do so.
Definition at line 172 of file cf_algorithm.cc.