![]() |
#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.
CanonicalForm bCommonDen | ( | const CanonicalForm & | f | ) |
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 euclideanNorm | ( | const CanonicalForm & | f | ) |
CanonicalForm euclideanNorm ( const CanonicalForm & f )
euclideanNorm() - return Euclidean norm of `f'.
Returns the largest integer smaller or equal norm(`f') = sqrt(sum( `f'[i]^2 )).
f: UVPoly( Z )
Definition at line 563 of file cf_algorithm.cc.
bool fdivides | ( | const CanonicalForm & | f, |
const CanonicalForm & | g | ||
) |
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()'.
Definition at line 338 of file cf_algorithm.cc.
bool fdivides | ( | const CanonicalForm & | f, |
const CanonicalForm & | g, | ||
CanonicalForm & | quot | ||
) |
same as fdivides if true returns quotient quot of g by f otherwise quot == 0
Definition at line 388 of file cf_algorithm.cc.
|
static |
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 )
Definition at line 262 of file cf_algorithm.cc.
CanonicalForm maxNorm | ( | const CanonicalForm & | f | ) |
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 534 of file cf_algorithm.cc.
void out_cf | ( | const char * | s1, |
const CanonicalForm & | f, | ||
const char * | s2 | ||
) |
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.
Definition at line 90 of file cf_factor.cc.
CanonicalForm psq | ( | const CanonicalForm & | f, |
const CanonicalForm & | g, | ||
const Variable & | x | ||
) |
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.
void psqr | ( | const CanonicalForm & | f, |
const CanonicalForm & | g, | ||
CanonicalForm & | q, | ||
CanonicalForm & | r, | ||
const Variable & | x | ||
) |
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.
Definition at line 223 of file cf_algorithm.cc.
CanonicalForm psr | ( | const CanonicalForm & | rr, |
const CanonicalForm & | vv, | ||
const Variable & | x | ||
) |
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.
Definition at line 117 of file cf_algorithm.cc.
bool tryFdivides | ( | const CanonicalForm & | f, |
const CanonicalForm & | g, | ||
const CanonicalForm & | M, | ||
bool & | fail | ||
) |
same as fdivides but handles zero divisors in Z_p[t]/(f)[x1,...,xn] for reducible f
Definition at line 454 of file cf_algorithm.cc.