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, 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

GreatestCommonDivisorAbstract()

Method Summary

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 comon divisor.
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, GenPolynomial<C> P, int e) 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.
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>	content(GenPolynomial<C> P) GenPolynomial content.
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.
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.
abstract GenPolynomial<GenPolynomial<C>>	recursiveUnivariateGcd(GenPolynomial<GenPolynomial<C>> P, GenPolynomial<GenPolynomial<C>> S) Univariate GenPolynomial recursive greatest common divisor.
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).

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).

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).

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).

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).

See Also:

GreatestCommonDivisorSubres.recursiveResultant(edu.jas.poly.GenPolynomial>, edu.jas.poly.GenPolynomial>)

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.

Specified by:

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

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.

Specified by:

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

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 comon 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.