Loading...
Searching...
No Matches
cf_resultant.cc File Reference

algorithms for calculating resultants. More...

`#include "config.h"`
`#include "cf_assert.h"`
`#include "canonicalform.h"`
`#include "variable.h"`
`#include "cf_algorithm.h"`

Go to the source code of this file.

## Functions

CFArray | subResChain (const CanonicalForm &f, const CanonicalForm &g, const Variable &x)
| CFArray subResChain ( const CanonicalForm & f, const CanonicalForm & g, const Variable & x ).
static CanonicalForm | trivialResultant (const CanonicalForm &f, const CanonicalForm &g, const Variable &x)
| static CanonicalForm trivialResultant ( const CanonicalForm & f, const CanonicalForm & g, const Variable & x )
CanonicalForm | resultant (const CanonicalForm &f, const CanonicalForm &g, const Variable &x)
| CanonicalForm resultant ( const CanonicalForm & f, const CanonicalForm & g, const Variable & x ).

## Detailed Description

algorithms for calculating resultants.

Header file: cf_algorithm.h

Definition in file cf_resultant.cc.

## Function Documentation

## resultant()

CanonicalForm resultant | ( | const CanonicalForm & | f,
|  | const CanonicalForm & | g,
|  | const Variable & | x )

CanonicalForm resultant ( const CanonicalForm & f, const CanonicalForm & g, const Variable & x ).

resultant() - return resultant of f and g with respect to x.

The chain is calculated from f and g with respect to variable x which should not be an algebraic variable. If f or q equals zero, zero is returned. If f is a coefficient with respect to x, f^degree(g, x) is returned, analogously for g.

This algorithm serves as a wrapper around other resultant algorithms which do the real work. Here we use standard properties of resultants only.

Definition at line 173 of file cf_resultant.cc.

{
ASSERT( x.level() > 0, "cannot calculate resultant with respect to algebraic variables" );
// some checks on triviality. We will not use degree( v )
// here because this may involve variable swapping.
if ( f.isZero() || g.isZero() )
return 0;
if ( f.mvar() < x )
return power( f, g.degree( x ) );
if ( g.mvar() < x )
return power( g, f.degree( x ) );
// make x main variale
CanonicalForm F, G;
Variable X;
if ( f.mvar() > x || g.mvar() > x ) {
if ( f.mvar() > g.mvar() )
X = f.mvar();
else
X = g.mvar();
F = swapvar( f, X, x );
G = swapvar( g, X, x );
}
else {
X = x;
F = f;
G = g;
}
// at this point, we have to calculate resultant( F, G, X )
// where X is equal to or greater than the main variables
// of F and G
int m = degree( F, X );
int n = degree( G, X );
// catch trivial cases
if ( m+n <= 2 || m == 0 || n == 0 )
return swapvar( trivialResultant( F, G, X ), X, x );
// exchange F and G if necessary
int flipFactor;
if ( m < n ) {
CanonicalForm swap = F;
F = G; G = swap;
int degswap = m;
m = n; n = degswap;
if ( m & 1 && n & 1 )
flipFactor = -1;
else
flipFactor = 1;
} else
flipFactor = 1;
// this is not an effective way to calculate the resultant!
CanonicalForm extFactor;
if ( m == n ) {
if ( n & 1 )
extFactor = -LC( G, X );
else
extFactor = LC( G, X );
} else
extFactor = power( LC( F, X ), m-n-1 );
CanonicalForm result;
result = subResChain( F, G, X )[0] / extFactor;
return swapvar( result, X, x ) * flipFactor;
}
swap
#define swap(_i, _j)
power
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
Definition canonicalform.cc:1896
degree
int degree(const CanonicalForm &f)
Definition canonicalform.h:316
swapvar
CanonicalForm FACTORY_PUBLIC swapvar(const CanonicalForm &, const Variable &, const Variable &)
swapvar() - swap variables x1 and x2 in f.
Definition cf_ops.cc:168
LC
CanonicalForm LC(const CanonicalForm &f)
Definition canonicalform.h:310
m
int m
Definition cfEzgcd.cc:128
x
Variable x
Definition cfModGcd.cc:4090
g
g
Definition cfModGcd.cc:4098
ASSERT
#define ASSERT(expression, message)
Definition cf_assert.h:99
subResChain
CFArray subResChain(const CanonicalForm &f, const CanonicalForm &g, const Variable &x)
CFArray subResChain ( const CanonicalForm & f, const CanonicalForm & g, const Variable & x ).
Definition cf_resultant.cc:42
trivialResultant
static CanonicalForm trivialResultant(const CanonicalForm &f, const CanonicalForm &g, const Variable &x)
static CanonicalForm trivialResultant ( const CanonicalForm & f, const CanonicalForm & g,...
Definition cf_resultant.cc:146
f
FILE * f
Definition checklibs.c:9
CanonicalForm
factory's main class
Definition canonicalform.h:86
Variable
factory's class for variables
Definition factory.h:127
result
return result
Definition facAbsBiFact.cc:76
G
STATIC_VAR TreeM * G
Definition janet.cc:31

## subResChain()

CFArray subResChain | ( | const CanonicalForm & | f,
|  | const CanonicalForm & | g,
|  | const Variable & | x )

CFArray subResChain ( const CanonicalForm & f, const CanonicalForm & g, const Variable & x ).

subResChain() - caculate extended subresultant chain.

The chain is calculated from f and g with respect to variable x which should not be an algebraic variable. If f or q equals zero, an array consisting of one zero entry is returned.

Note: this is not the standard subresultant chain but the extended chain!

This algorithm is from the article of R. Loos - 'Generalized Polynomial Remainder Sequences' in B. Buchberger - 'Computer Algebra - Symbolic and Algebraic Computation' with some necessary extensions concerning the calculation of the first step.

Definition at line 42 of file cf_resultant.cc.

{
ASSERT( x.level() > 0, "cannot calculate subresultant sequence with respect to algebraic variables" );
CFArray trivialResult( 0, 0 );
CanonicalForm F, G;
Variable X;
// some checks on triviality
if ( f.isZero() || g.isZero() ) {
trivialResult[0] = 0;
return trivialResult;
}
// make x main variable
if ( f.mvar() > x || g.mvar() > x ) {
if ( f.mvar() > g.mvar() )
X = f.mvar();
else
X = g.mvar();
F = swapvar( f, X, x );
G = swapvar( g, X, x );
}
else {
X = x;
F = f;
G = g;
}
// at this point, we have to calculate the sequence of F and
// G in respect to X where X is equal to or greater than the
// main variables of F and G
// initialization of chain
int m = degree( F, X );
int n = degree( G, X );
int j = (m <= n) ? n : m-1;
int r;
CFArray S( 0, j+1 );
CanonicalForm R;
S[j+1] = F; S[j] = G;
// make sure that S[j+1] is regular and j < n
if ( m == n && j > 0 ) {
S[j-1] = LC( S[j], X ) * psr( S[j+1], S[j], X );
j--;
} else if ( m < n ) {
S[j-1] = LC( S[j], X ) * LC( S[j], X ) * S[j+1];
j--;
} else if ( m > n && j > 0 ) {
// calculate first step
r = degree( S[j], X );
R = LC( S[j+1], X );
// if there was a gap calculate similar polynomial
if ( j > r && r >= 0 )
S[r] = power( LC( S[j], X ), j - r ) * S[j] * power( R, j - r );
if ( r > 0 ) {
// calculate remainder
S[r-1] = psr( S[j+1], S[j], X ) * power( -R, j - r );
j = r-1;
}
}
while ( j > 0 ) {
// at this point, 0 < j < n and S[j+1] is regular
r = degree( S[j], X );
R = LC( S[j+1], X );
// if there was a gap calculate similar polynomial
if ( j > r && r >= 0 )
S[r] = (power( LC( S[j], X ), j - r ) * S[j]) / power( R, j - r );
if ( r <= 0 ) break;
// calculate remainder
S[r-1] = psr( S[j+1], S[j], X ) / power( -R, j - r + 2 );
j = r-1;
// again 0 <= j < r <= jOld and S[j+1] is regular
}
for ( j = 0; j <= S.max(); j++ ) {
// reswap variables if necessary
if ( X != x ) {
S[j] = swapvar( S[j], X, x );
}
}
return S;
}
CFArray
Array< CanonicalForm > CFArray
Definition canonicalform.h:397
psr
CanonicalForm psr(const CanonicalForm &f, const CanonicalForm &g, const Variable &x)
j
int j
Definition facHensel.cc:110
R
#define R
Definition sirandom.c:27

## trivialResultant()

CanonicalForm trivialResultant | ( | const CanonicalForm & | f,
|  | const CanonicalForm & | g,
|  | const Variable & | x )

static

static CanonicalForm trivialResultant ( const CanonicalForm & f, const CanonicalForm & g, const Variable & x )

trivialResultant - calculate trivial resultants.

x's level should be larger than f's and g's levels. Either f or g should be constant or both linear.

Used by resultant().

Definition at line 146 of file cf_resultant.cc.

{
// f or g in R
if ( degree( f, x ) == 0 )
return power( f, degree( g, x ) );
if ( degree( g, x ) == 0 )
return power( g, degree( f, x ) );
// f and g are linear polynomials
return LC( f, x ) * g - LC( g, x ) * f;
}