Package edu.jas.ufd

Class GreatestCommonDivisorAbstract<C extends GcdRingElem<C>>

java.lang.Object

edu.jas.ufd.GreatestCommonDivisorAbstract<C>

All Implemented Interfaces:

GreatestCommonDivisor<C>, java.io.Serializable

Direct Known Subclasses:

GCDProxy, GreatestCommonDivisorFake, GreatestCommonDivisorHensel, GreatestCommonDivisorModEval, GreatestCommonDivisorModular, GreatestCommonDivisorPrimitive, GreatestCommonDivisorSimple, GreatestCommonDivisorSubres

public abstract class GreatestCommonDivisorAbstract<C extends GcdRingElem<C>>
extends java.lang.Object
implements GreatestCommonDivisor<C>

Greatest common divisor algorithms.

Author:

Heinz Kredel

See Also:

Serialized Form

Constructor Summary

Constructors

Constructor	Description
GreatestCommonDivisorAbstract()

Method Summary

Modifier and Type	Method	Description
C	baseContent(GenPolynomial<C> P)	GenPolynomial base coefficient content.
GenPolynomial<C>[]	baseExtendedGcd(GenPolynomial<C> P, GenPolynomial<C> S)	Univariate GenPolynomial extended greatest common divisor.
abstract GenPolynomial<C>	baseGcd(GenPolynomial<C> P, GenPolynomial<C> S)	Univariate GenPolynomial greatest common divisor.
GenPolynomial<C>[]	baseGcdDiophant(GenPolynomial<C> P, GenPolynomial<C> S, GenPolynomial<C> c)	Univariate GenPolynomial greatest common divisor diophantine version.
GenPolynomial<C>[]	baseHalfExtendedGcd(GenPolynomial<C> P, GenPolynomial<C> S)	Univariate GenPolynomial half extended greatest common divisor.
java.util.List<GenPolynomial<C>>	basePartialFraction(GenPolynomial<C> A, GenPolynomial<C> P, int e)	Univariate GenPolynomial partial fraction decomposition.
GenPolynomial<C>[]	basePartialFraction(GenPolynomial<C> A, GenPolynomial<C> P, GenPolynomial<C> S)	Univariate GenPolynomial partial fraction decomposition.
java.util.List<GenPolynomial<C>>	basePartialFraction(GenPolynomial<C> A, java.util.List<GenPolynomial<C>> D)	Univariate GenPolynomial partial fraction decomposition.
GenPolynomial<C>	basePartialFractionValue(GenPolynomial<C> P, int e, java.util.List<GenPolynomial<C>> F)	Test for Univariate GenPolynomial partial fraction decomposition.
GenPolynomial<C>	basePrimitivePart(GenPolynomial<C> P)	GenPolynomial base coefficient primitive part.
java.util.List<GenPolynomial<C>>	basePrimitivePart(java.util.List<GenPolynomial<C>> F)	List of GenPolynomial base coefficient primitive part.
C	baseRecursiveContent(GenPolynomial<GenPolynomial<C>> P)	GenPolynomial base recursive content.
GenPolynomial<GenPolynomial<C>>	baseRecursivePrimitivePart(GenPolynomial<GenPolynomial<C>> P)	GenPolynomial base recursive primitive part.
GenPolynomial<C>	baseResultant(GenPolynomial<C> P, GenPolynomial<C> S)	Univariate GenPolynomial resultant.
GenPolynomial<C>	content(GenPolynomial<C> P)	GenPolynomial content.
GenPolynomial<C>[]	contentPrimitivePart(GenPolynomial<C> P)	GenPolynomial content and primitive part.
java.util.List<GenPolynomial<C>>	coPrime(GenPolynomial<C> a, java.util.List<GenPolynomial<C>> P)	GenPolynomial co-prime list.
java.util.List<GenPolynomial<C>>	coPrime(java.util.List<GenPolynomial<C>> A)	GenPolynomial co-prime list.
java.util.List<GenPolynomial<C>>	coPrimeRec(java.util.List<GenPolynomial<C>> A)	GenPolynomial co-prime list.
GenPolynomial<C>	divide(GenPolynomial<C> a, C b)	GenPolynomial division.
C	gcd(C a, C b)	Coefficient greatest common divisor.
GenPolynomial<C>	gcd(GenPolynomial<C> P, GenPolynomial<C> S)	GenPolynomial greatest common divisor.
GenPolynomial<C>	gcd(java.util.List<GenPolynomial<C>> A)	List of GenPolynomials greatest common divisor.
boolean	isBasePartialFraction(GenPolynomial<C> A, GenPolynomial<C> P, int e, java.util.List<GenPolynomial<C>> F)	Test for Univariate GenPolynomial partial fraction decomposition.
boolean	isBasePartialFraction(GenPolynomial<C> A, java.util.List<GenPolynomial<C>> D, java.util.List<GenPolynomial<C>> F)	Test for Univariate GenPolynomial partial fraction decomposition.
boolean	isCoPrime(java.util.List<GenPolynomial<C>> A)	GenPolynomial test for co-prime list.
boolean	isCoPrime(java.util.List<GenPolynomial<C>> P, java.util.List<GenPolynomial<C>> A)	GenPolynomial test for co-prime list of given list.
GenPolynomial<C>	lcm(GenPolynomial<C> P, GenPolynomial<C> S)	GenPolynomial least common multiple.
GenPolynomial<C>	primitivePart(GenPolynomial<C> P)	GenPolynomial primitive part.
GenPolynomial<C>	recursiveContent(GenPolynomial<GenPolynomial<C>> P)	GenPolynomial recursive content.
GenPolynomial<GenPolynomial<C>>	recursiveGcd(GenPolynomial<GenPolynomial<C>> P, GenPolynomial<GenPolynomial<C>> S)	GenPolynomial recursive greatest common divisor.
GenPolynomial<GenPolynomial<C>>	recursivePrimitivePart(GenPolynomial<GenPolynomial<C>> P)	GenPolynomial recursive primitive part.
java.util.List<GenPolynomial<GenPolynomial<C>>>	recursivePrimitivePart(java.util.List<GenPolynomial<GenPolynomial<C>>> F)	List of recursive GenPolynomial base coefficient primitive part.
GenPolynomial<GenPolynomial<C>>	recursiveResultant(GenPolynomial<GenPolynomial<C>> P, GenPolynomial<GenPolynomial<C>> S)	GenPolynomial recursive resultant.
abstract GenPolynomial<GenPolynomial<C>>	recursiveUnivariateGcd(GenPolynomial<GenPolynomial<C>> P, GenPolynomial<GenPolynomial<C>> S)	Univariate GenPolynomial recursive greatest common divisor.
GenPolynomial<GenPolynomial<C>>	recursiveUnivariateResultant(GenPolynomial<GenPolynomial<C>> P, GenPolynomial<GenPolynomial<C>> S)	Univariate GenPolynomial recursive resultant.
GenPolynomial<C>	resultant(GenPolynomial<C> P, GenPolynomial<C> S)	GenPolynomial resultant.
java.lang.String	toString()	Get the String representation.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Constructor Detail

GreatestCommonDivisorAbstract

public GreatestCommonDivisorAbstract()

Method Detail

toString

public java.lang.String toString()

Get the String representation.

Overrides:

toString in class java.lang.Object

See Also:

Object.toString()

baseContent

public C baseContent(GenPolynomial<C> P)

GenPolynomial base coefficient content.

Parameters:

P - GenPolynomial.

Returns:

cont(P).

basePrimitivePart

public GenPolynomial<C> basePrimitivePart(GenPolynomial<C> P)

GenPolynomial base coefficient primitive part.

Parameters:

P - GenPolynomial.

Returns:

pp(P).

basePrimitivePart

public java.util.List<GenPolynomial<C>> basePrimitivePart(java.util.List<GenPolynomial<C>> F)

List of GenPolynomial base coefficient primitive part.

Parameters:

F - list of GenPolynomials.

Returns:

pp(F).

baseGcd

public abstract GenPolynomial<C> baseGcd(GenPolynomial<C> P,
                                         GenPolynomial<C> S)

Univariate GenPolynomial greatest common divisor. Uses sparse pseudoRemainder for remainder.

Parameters:

P - univariate GenPolynomial.

S - univariate GenPolynomial.

Returns:

gcd(P,S).

recursiveContent

public GenPolynomial<C> recursiveContent(GenPolynomial<GenPolynomial<C>> P)

GenPolynomial recursive content.

Parameters:

P - recursive GenPolynomial.

Returns:

cont(P).

recursivePrimitivePart

public GenPolynomial<GenPolynomial<C>> recursivePrimitivePart(GenPolynomial<GenPolynomial<C>> P)

GenPolynomial recursive primitive part.

Parameters:

P - recursive GenPolynomial.

Returns:

pp(P).

recursivePrimitivePart

public java.util.List<GenPolynomial<GenPolynomial<C>>> recursivePrimitivePart(java.util.List<GenPolynomial<GenPolynomial<C>>> F)

List of recursive GenPolynomial base coefficient primitive part.

Parameters:

F - list of recursive GenPolynomials.

Returns:

pp(F).

baseRecursiveContent

public C baseRecursiveContent(GenPolynomial<GenPolynomial<C>> P)

GenPolynomial base recursive content.

Parameters:

P - recursive GenPolynomial.

Returns:

baseCont(P).

baseRecursivePrimitivePart

public GenPolynomial<GenPolynomial<C>> baseRecursivePrimitivePart(GenPolynomial<GenPolynomial<C>> P)

GenPolynomial base recursive primitive part.

Parameters:

P - recursive GenPolynomial.

Returns:

basePP(P).

recursiveGcd

public GenPolynomial<GenPolynomial<C>> recursiveGcd(GenPolynomial<GenPolynomial<C>> P,
                                                    GenPolynomial<GenPolynomial<C>> S)

GenPolynomial recursive greatest common divisor. Uses pseudoRemainder for remainder.

Parameters:

P - recursive GenPolynomial.

S - recursive GenPolynomial.

Returns:

gcd(P,S).

recursiveUnivariateGcd

public abstract GenPolynomial<GenPolynomial<C>> recursiveUnivariateGcd(GenPolynomial<GenPolynomial<C>> P,
                                                                       GenPolynomial<GenPolynomial<C>> S)

Univariate GenPolynomial recursive greatest common divisor. Uses pseudoRemainder for remainder.

Parameters:

P - univariate recursive GenPolynomial.

S - univariate recursive GenPolynomial.

Returns:

gcd(P,S).

content

public GenPolynomial<C> content(GenPolynomial<C> P)

GenPolynomial content.

Specified by:

content in interface GreatestCommonDivisor<C extends GcdRingElem<C>>

Parameters:

P - GenPolynomial.

Returns:

cont(P).

primitivePart

public GenPolynomial<C> primitivePart(GenPolynomial<C> P)

GenPolynomial primitive part.

Specified by:

primitivePart in interface GreatestCommonDivisor<C extends GcdRingElem<C>>

Parameters:

P - GenPolynomial.

Returns:

pp(P).

contentPrimitivePart

public GenPolynomial<C>[] contentPrimitivePart(GenPolynomial<C> P)

GenPolynomial content and primitive part.

Parameters:

P - GenPolynomial.

Returns:

{ cont(P), pp(P) }

divide

public GenPolynomial<C> divide(GenPolynomial<C> a,
                               C b)

GenPolynomial division. Indirection to GenPolynomial method.

Parameters:

a - GenPolynomial.

b - coefficient.

Returns:

a/b.

gcd

public C gcd(C a,
             C b)

Coefficient greatest common divisor. Indirection to coefficient method.

Parameters:

a - coefficient.

b - coefficient.

Returns:

gcd(a,b).

gcd

public GenPolynomial<C> gcd(GenPolynomial<C> P,
                            GenPolynomial<C> S)

GenPolynomial greatest common divisor.

Specified by:

gcd in interface GreatestCommonDivisor<C extends GcdRingElem<C>>

Parameters:

P - GenPolynomial.

S - GenPolynomial.

Returns:

gcd(P,S).

lcm

public GenPolynomial<C> lcm(GenPolynomial<C> P,
                            GenPolynomial<C> S)

GenPolynomial least common multiple.

Specified by:

lcm in interface GreatestCommonDivisor<C extends GcdRingElem<C>>

Parameters:

P - GenPolynomial.

S - GenPolynomial.

Returns:

lcm(P,S).

gcd

public GenPolynomial<C> gcd(java.util.List<GenPolynomial<C>> A)

List of GenPolynomials greatest common divisor.

Parameters:

A - non empty list of GenPolynomials.

Returns:

gcd(A_i).

baseResultant

public GenPolynomial<C> baseResultant(GenPolynomial<C> P,
                                      GenPolynomial<C> S)

Univariate GenPolynomial resultant.

Parameters:

P - univariate GenPolynomial.

S - univariate GenPolynomial.

Returns:

res(P,S).

Throws:

java.lang.UnsupportedOperationException - if there is no implementation in the sub-class.

recursiveUnivariateResultant

public GenPolynomial<GenPolynomial<C>> recursiveUnivariateResultant(GenPolynomial<GenPolynomial<C>> P,
                                                                    GenPolynomial<GenPolynomial<C>> S)

Univariate GenPolynomial recursive resultant.

Parameters:

P - univariate recursive GenPolynomial.

S - univariate recursive GenPolynomial.

Returns:

res(P,S).

Throws:

java.lang.UnsupportedOperationException - if there is no implementation in the sub-class.

recursiveResultant

public GenPolynomial<GenPolynomial<C>> recursiveResultant(GenPolynomial<GenPolynomial<C>> P,
                                                          GenPolynomial<GenPolynomial<C>> S)

GenPolynomial recursive resultant.

Parameters:

P - univariate recursive GenPolynomial.

S - univariate recursive GenPolynomial.

Returns:

res(P,S).

Throws:

java.lang.UnsupportedOperationException - if there is no implementation in the sub-class.

resultant

public GenPolynomial<C> resultant(GenPolynomial<C> P,
                                  GenPolynomial<C> S)

GenPolynomial resultant. The input polynomials are considered as univariate polynomials in the main variable.

Specified by:

resultant in interface GreatestCommonDivisor<C extends GcdRingElem<C>>

Parameters:

P - GenPolynomial.

S - GenPolynomial.

Returns:

res(P,S).

Throws:

java.lang.UnsupportedOperationException - if there is no implementation in the sub-class.

See Also:

recursiveResultant(edu.jas.poly.GenPolynomial<edu.jas.poly.GenPolynomial<C>>, edu.jas.poly.GenPolynomial<edu.jas.poly.GenPolynomial<C>>)

coPrime

public java.util.List<GenPolynomial<C>> coPrime(java.util.List<GenPolynomial<C>> A)

GenPolynomial co-prime list.

Specified by:

coPrime in interface GreatestCommonDivisor<C extends GcdRingElem<C>>

Parameters:

A - list of GenPolynomials.

Returns:

B with gcd(b,c) = 1 for all b != c in B and for all non-constant a in A there exists b in B with b|a. B does not contain zero or constant polynomials.

coPrimeRec

public java.util.List<GenPolynomial<C>> coPrimeRec(java.util.List<GenPolynomial<C>> A)

GenPolynomial co-prime list.

Parameters:

A - list of GenPolynomials.

Returns:

B with gcd(b,c) = 1 for all b != c in B and for all non-constant a in A there exists b in B with b|a. B does not contain zero or constant polynomials.

coPrime

public java.util.List<GenPolynomial<C>> coPrime(GenPolynomial<C> a,
                                                java.util.List<GenPolynomial<C>> P)

GenPolynomial co-prime list.

Parameters:

a - GenPolynomial.

P - co-prime list of GenPolynomials.

Returns:

B with gcd(b,c) = 1 for all b != c in B and for non-constant a there exists b in P with b|a. B does not contain zero or constant polynomials.

isCoPrime

public boolean isCoPrime(java.util.List<GenPolynomial<C>> A)

GenPolynomial test for co-prime list.

Specified by:

isCoPrime in interface GreatestCommonDivisor<C extends GcdRingElem<C>>

Parameters:

A - list of GenPolynomials.

Returns:

true if gcd(b,c) = 1 for all b != c in B, else false.

isCoPrime

public boolean isCoPrime(java.util.List<GenPolynomial<C>> P,
                         java.util.List<GenPolynomial<C>> A)

GenPolynomial test for co-prime list of given list.

Parameters:

A - list of GenPolynomials.

P - list of co-prime GenPolynomials.

Returns:

true if isCoPrime(P) and for all a in A exists p in P with p | a, else false.

baseExtendedGcd

public GenPolynomial<C>[] baseExtendedGcd(GenPolynomial<C> P,
                                          GenPolynomial<C> S)

Univariate GenPolynomial extended greatest common divisor. Uses sparse pseudoRemainder for remainder.

Parameters:

P - univariate GenPolynomial.

S - univariate GenPolynomial.

Returns:

[ gcd(P,S), a, b ] with a*P + b*S = gcd(P,S).

baseHalfExtendedGcd

public GenPolynomial<C>[] baseHalfExtendedGcd(GenPolynomial<C> P,
                                              GenPolynomial<C> S)

Univariate GenPolynomial half extended greatest common divisor. Uses sparse pseudoRemainder for remainder.

Parameters:

S - GenPolynomial.

Returns:

[ gcd(P,S), a ] with a*P + b*S = gcd(P,S).

baseGcdDiophant

public GenPolynomial<C>[] baseGcdDiophant(GenPolynomial<C> P,
                                          GenPolynomial<C> S,
                                          GenPolynomial<C> c)

Univariate GenPolynomial greatest common divisor diophantine version.

Parameters:

P - univariate GenPolynomial.

S - univariate GenPolynomial.

c - univariate GenPolynomial.

Returns:

[ a, b ] with a*P + b*S = c and deg(a) < deg(S).

basePartialFraction

public GenPolynomial<C>[] basePartialFraction(GenPolynomial<C> A,
                                              GenPolynomial<C> P,
                                              GenPolynomial<C> S)

Univariate GenPolynomial partial fraction decomposition.

Parameters:

A - univariate GenPolynomial.

P - univariate GenPolynomial.

S - univariate GenPolynomial.

Returns:

[ A0, Ap, As ] with A/(P*S) = A0 + Ap/P + As/S with deg(Ap) < deg(P) and deg(As) < deg(S).

basePartialFraction

public java.util.List<GenPolynomial<C>> basePartialFraction(GenPolynomial<C> A,
                                                            GenPolynomial<C> P,
                                                            int e)

Univariate GenPolynomial partial fraction decomposition.

Parameters:

A - univariate GenPolynomial.

P - univariate GenPolynomial.

e - exponent for P.

Returns:

[ F0, F1, ..., Fe ] with A/(P^e) = sum( Fi / P^i ) with deg(Fi) < deg(P).

basePartialFraction

public java.util.List<GenPolynomial<C>> basePartialFraction(GenPolynomial<C> A,
                                                            java.util.List<GenPolynomial<C>> D)

Univariate GenPolynomial partial fraction decomposition.

Parameters:

A - univariate GenPolynomial.

D - list of co-prime univariate GenPolynomials.

Returns:

[ A0, A1,..., An ] with A/prod(D) = A0 + sum( Ai/Di ) with deg(Ai) < deg(Di).

isBasePartialFraction

public boolean isBasePartialFraction(GenPolynomial<C> A,
                                     java.util.List<GenPolynomial<C>> D,
                                     java.util.List<GenPolynomial<C>> F)

Test for Univariate GenPolynomial partial fraction decomposition.

Parameters:

A - univariate GenPolynomial.

D - list of (co-prime) univariate GenPolynomials.

F - list of univariate GenPolynomials from a partial fraction computation.

Returns:

true if A/prod(D) = F0 + sum( Fi/Di ) with deg(Fi) < deg(Di), Fi in F, else false.

isBasePartialFraction

public boolean isBasePartialFraction(GenPolynomial<C> A,
                                     GenPolynomial<C> P,
                                     int e,
                                     java.util.List<GenPolynomial<C>> F)

Test for Univariate GenPolynomial partial fraction decomposition.

Parameters:

A - univariate GenPolynomial.

P - univariate GenPolynomial.

e - exponent for P.

F - list of univariate GenPolynomials from a partial fraction computation.

Returns:

true if A/(P^e) = F0 + sum( Fi / P^i ) with deg(Fi) < deg(P), Fi in F, else false.

basePartialFractionValue

public GenPolynomial<C> basePartialFractionValue(GenPolynomial<C> P,
                                                 int e,
                                                 java.util.List<GenPolynomial<C>> F)

Test for Univariate GenPolynomial partial fraction decomposition.

Parameters:

P - univariate GenPolynomial.

e - exponent for P.

F - list of univariate GenPolynomials from a partial fraction computation.

Returns:

(F0 + sum( Fi / P^i )) * P^e.