edu.jas.fd

Class GreatestCommonDivisorAbstract<C extends GcdRingElem<C>>

java.lang.Object

edu.jas.fd.GreatestCommonDivisorAbstract<C>

Type Parameters:

C - coefficient type

All Implemented Interfaces:

GreatestCommonDivisor<C>, java.io.Serializable

Direct Known Subclasses:

GreatestCommonDivisorPrimitive, GreatestCommonDivisorSimple

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

(Non-unique) factorization domain greatest common divisor common algorithms.

Author:

Heinz Kredel

See Also:

Serialized Form

Constructor Summary

Constructors

Constructor and Description
GreatestCommonDivisorAbstract(RingFactory<C> cf) Constructor.

Method Summary

Modifier and Type	Method and Description
GenSolvablePolynomial<C>[]	baseExtendedGcd(GenSolvablePolynomial<C> P, GenSolvablePolynomial<C> S) Univariate GenSolvablePolynomial extended greatest common divisor.
GenSolvablePolynomial<C>[]	baseGcdDiophant(GenSolvablePolynomial<C> P, GenSolvablePolynomial<C> S, GenSolvablePolynomial<C> c) Univariate GenSolvablePolynomial greatest common divisor diophantine version.
GenSolvablePolynomial<C>[]	baseHalfExtendedGcd(GenSolvablePolynomial<C> P, GenSolvablePolynomial<C> S) Univariate GenSolvablePolynomial half extended greatest comon divisor.
C	baseRecursiveContent(GenSolvablePolynomial<GenPolynomial<C>> P) GenSolvablePolynomial base recursive content.
GenSolvablePolynomial<GenPolynomial<C>>	baseRecursivePrimitivePart(GenSolvablePolynomial<GenPolynomial<C>> P) GenSolvablePolynomial base recursive primitive part.
GenSolvablePolynomial<C>	divide(GenSolvablePolynomial<C> a, C b) GenSolvablePolynomial division.
C	gcd(C a, C b) Coefficient greatest common divisor.
boolean	isLeftCoPrime(java.util.List<GenSolvablePolynomial<C>> A) GenSolvablePolynomial test for co-prime list.
boolean	isLeftCoPrime(java.util.List<GenSolvablePolynomial<C>> P, java.util.List<GenSolvablePolynomial<C>> A) GenSolvablePolynomial test for left co-prime list of given list.
C	leftBaseContent(GenSolvablePolynomial<C> P) GenSolvablePolynomial base coefficient content.
abstract GenSolvablePolynomial<C>	leftBaseGcd(GenSolvablePolynomial<C> P, GenSolvablePolynomial<C> S) Univariate GenSolvablePolynomial greatest common divisor.
GenSolvablePolynomial<C>	leftBasePrimitivePart(GenSolvablePolynomial<C> P) GenSolvablePolynomial base coefficient primitive part.
GenSolvablePolynomial<C>	leftContent(GenSolvablePolynomial<C> P) GenSolvablePolynomial left content.
java.util.List<GenSolvablePolynomial<C>>	leftCoPrime(GenSolvablePolynomial<C> a, java.util.List<GenSolvablePolynomial<C>> P) GenSolvablePolynomial left co-prime list.
java.util.List<GenSolvablePolynomial<C>>	leftCoPrime(java.util.List<GenSolvablePolynomial<C>> A) GenSolvablePolynomial co-prime list.
java.util.List<GenSolvablePolynomial<C>>	leftCoPrimeRec(java.util.List<GenSolvablePolynomial<C>> A) GenSolvablePolynomial left co-prime list.
GenSolvablePolynomial<C>	leftGcd(GenSolvablePolynomial<C> P, GenSolvablePolynomial<C> S) GenSolvablePolynomial greatest common divisor.
GenSolvablePolynomial<C>	leftGcd(java.util.List<GenSolvablePolynomial<C>> A) List of GenSolvablePolynomials left greatest common divisor.
GenSolvablePolynomial<C>	leftLcm(GenSolvablePolynomial<C> P, GenSolvablePolynomial<C> S) GenSolvablePolynomial left least common multiple.
C[]	leftOreCond(C a, C b) Coefficient left Ore condition.
GenSolvablePolynomial<C>[]	leftOreCond(GenSolvablePolynomial<C> a, GenSolvablePolynomial<C> b) Left Ore condition.
GenSolvablePolynomial<C>	leftPrimitivePart(GenSolvablePolynomial<C> P) GenSolvablePolynomial left primitive part.
GenSolvablePolynomial<C>	leftRecursiveContent(GenSolvablePolynomial<GenPolynomial<C>> P) GenSolvablePolynomial left recursive content.
GenSolvablePolynomial<GenPolynomial<C>>	leftRecursiveGcd(GenSolvablePolynomial<GenPolynomial<C>> P, GenSolvablePolynomial<GenPolynomial<C>> S) GenSolvablePolynomial left recursive greatest common divisor.
GenSolvablePolynomial<GenPolynomial<C>>	leftRecursivePrimitivePart(GenSolvablePolynomial<GenPolynomial<C>> P) GenSolvablePolynomial left recursive primitive part.
abstract GenSolvablePolynomial<GenPolynomial<C>>	leftRecursiveUnivariateGcd(GenSolvablePolynomial<GenPolynomial<C>> P, GenSolvablePolynomial<GenPolynomial<C>> S) Univariate GenSolvablePolynomial recursive greatest common divisor.
GenSolvablePolynomial<C>	recursiveContent(GenSolvablePolynomial<GenPolynomial<C>> P) GenSolvablePolynomial commuting recursive content.
C	rightBaseContent(GenSolvablePolynomial<C> P) GenSolvablePolynomial right base coefficient content.
abstract GenSolvablePolynomial<C>	rightBaseGcd(GenSolvablePolynomial<C> P, GenSolvablePolynomial<C> S) Univariate GenSolvablePolynomial right greatest common divisor.
GenSolvablePolynomial<C>	rightBasePrimitivePart(GenSolvablePolynomial<C> P) GenSolvablePolynomial right base coefficient primitive part.
GenSolvablePolynomial<C>	rightContent(GenSolvablePolynomial<C> P) GenSolvablePolynomial right content.
GenSolvablePolynomial<C>	rightGcd(GenSolvablePolynomial<C> P, GenSolvablePolynomial<C> S) GenSolvablePolynomial right greatest common divisor.
GenSolvablePolynomial<C>	rightLcm(GenSolvablePolynomial<C> P, GenSolvablePolynomial<C> S) GenSolvablePolynomial right least common multiple.
C[]	rightOreCond(C a, C b) Coefficient rigth Ore condition.
GenSolvablePolynomial<C>[]	rightOreCond(GenSolvablePolynomial<C> a, GenSolvablePolynomial<C> b) Right Ore condition.
GenSolvablePolynomial<C>	rightPrimitivePart(GenSolvablePolynomial<C> P) GenSolvablePolynomial right primitive part.
GenSolvablePolynomial<C>	rightRecursiveContent(GenSolvablePolynomial<GenPolynomial<C>> P) GenSolvablePolynomial right recursive content.
GenSolvablePolynomial<GenPolynomial<C>>	rightRecursiveGcd(GenSolvablePolynomial<GenPolynomial<C>> P, GenSolvablePolynomial<GenPolynomial<C>> S) GenSolvablePolynomial right recursive greatest common divisor.
GenSolvablePolynomial<GenPolynomial<C>>	rightRecursivePrimitivePart(GenSolvablePolynomial<GenPolynomial<C>> P) GenSolvablePolynomial right recursive primitive part.
abstract GenSolvablePolynomial<GenPolynomial<C>>	rightRecursiveUnivariateGcd(GenSolvablePolynomial<GenPolynomial<C>> P, GenSolvablePolynomial<GenPolynomial<C>> S) Univariate GenSolvablePolynomial right recursive greatest common divisor.
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(RingFactory<C> cf)

Constructor.

Parameters:

cf - coefficient ring.

Method Detail

toString

public java.lang.String toString()

Get the String representation.

Overrides:

toString in class java.lang.Object

See Also:

Object.toString()

leftBaseContent

public C leftBaseContent(GenSolvablePolynomial<C> P)

GenSolvablePolynomial base coefficient content.

Parameters:

P - GenSolvablePolynomial.

Returns:

cont(P) with pp(P)*cont(P) = P.

rightBaseContent

public C rightBaseContent(GenSolvablePolynomial<C> P)

GenSolvablePolynomial right base coefficient content.

Parameters:

P - GenSolvablePolynomial.

Returns:

cont(P) with cont(P)*pp(P) = P.

leftBasePrimitivePart

public GenSolvablePolynomial<C> leftBasePrimitivePart(GenSolvablePolynomial<C> P)

GenSolvablePolynomial base coefficient primitive part.

Parameters:

P - GenSolvablePolynomial.

Returns:

pp(P) with pp(P)*cont(P) = P.

rightBasePrimitivePart

public GenSolvablePolynomial<C> rightBasePrimitivePart(GenSolvablePolynomial<C> P)

GenSolvablePolynomial right base coefficient primitive part.

Parameters:

P - GenSolvablePolynomial.

Returns:

pp(P) with cont(P)*pp(P) = P.

leftBaseGcd

public abstract GenSolvablePolynomial<C> leftBaseGcd(GenSolvablePolynomial<C> P,
                                                     GenSolvablePolynomial<C> S)

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

Parameters:

P - univariate GenSolvablePolynomial.

S - univariate GenSolvablePolynomial.

Returns:

gcd(P,S) with P = P'*gcd(P,S) and S = S'*gcd(P,S).

rightBaseGcd

public abstract GenSolvablePolynomial<C> rightBaseGcd(GenSolvablePolynomial<C> P,
                                                      GenSolvablePolynomial<C> S)

Univariate GenSolvablePolynomial right greatest common divisor. Uses sparse pseudoRemainder for remainder.

Parameters:

P - univariate GenSolvablePolynomial.

S - univariate GenSolvablePolynomial.

Returns:

gcd(P,S) with P = gcd(P,S)*P' and S = gcd(P,S)*S'.

recursiveContent

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

GenSolvablePolynomial commuting recursive content.

Parameters:

P - recursive GenSolvablePolynomial with commuting main and coefficient variables.

Returns:

cont(P) with cont(P)*pp(P) = pp(P)*cont(P).

rightRecursiveContent

public GenSolvablePolynomial<C> rightRecursiveContent(GenSolvablePolynomial<GenPolynomial<C>> P)

GenSolvablePolynomial right recursive content.

Parameters:

P - recursive GenSolvablePolynomial.

Returns:

cont(P) with pp(P)*cont(P) = P.

rightRecursivePrimitivePart

public GenSolvablePolynomial<GenPolynomial<C>> rightRecursivePrimitivePart(GenSolvablePolynomial<GenPolynomial<C>> P)

GenSolvablePolynomial right recursive primitive part.

Parameters:

P - recursive GenSolvablePolynomial.

Returns:

pp(P) with pp(P)*cont(P) = P.

leftRecursiveContent

public GenSolvablePolynomial<C> leftRecursiveContent(GenSolvablePolynomial<GenPolynomial<C>> P)

GenSolvablePolynomial left recursive content.

Parameters:

P - recursive GenSolvablePolynomial.

Returns:

cont(P) with cont(P)*pp(P) = P.

leftRecursivePrimitivePart

public GenSolvablePolynomial<GenPolynomial<C>> leftRecursivePrimitivePart(GenSolvablePolynomial<GenPolynomial<C>> P)

GenSolvablePolynomial left recursive primitive part.

Parameters:

P - recursive GenSolvablePolynomial.

Returns:

pp(P) with cont(P)*pp(P) = P.

baseRecursiveContent

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

GenSolvablePolynomial base recursive content.

Parameters:

P - recursive GenSolvablePolynomial.

Returns:

baseCont(P) with pp(P)*cont(P) = P.

baseRecursivePrimitivePart

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

GenSolvablePolynomial base recursive primitive part.

Parameters:

P - recursive GenSolvablePolynomial.

Returns:

basePP(P) with pp(P)*cont(P) = P.

leftRecursiveGcd

public GenSolvablePolynomial<GenPolynomial<C>> leftRecursiveGcd(GenSolvablePolynomial<GenPolynomial<C>> P,
                                                                GenSolvablePolynomial<GenPolynomial<C>> S)

GenSolvablePolynomial left recursive greatest common divisor. Uses pseudoRemainder for remainder.

Parameters:

P - recursive GenSolvablePolynomial.

S - recursive GenSolvablePolynomial.

Returns:

gcd(P,S) with P = P'*gcd(P,S)*p and S = S'*gcd(P,S)*s, where deg_main(p) = deg_main(s) == 0.

rightRecursiveGcd

public GenSolvablePolynomial<GenPolynomial<C>> rightRecursiveGcd(GenSolvablePolynomial<GenPolynomial<C>> P,
                                                                 GenSolvablePolynomial<GenPolynomial<C>> S)

GenSolvablePolynomial right recursive greatest common divisor. Uses pseudoRemainder for remainder.

Parameters:

P - recursive GenSolvablePolynomial.

S - recursive GenSolvablePolynomial.

Returns:

gcd(P,S) with P = p*gcd(P,S)*P' and S = s*gcd(P,S)*S', where deg_main(p) = deg_main(s) == 0.

leftRecursiveUnivariateGcd

public abstract GenSolvablePolynomial<GenPolynomial<C>> leftRecursiveUnivariateGcd(GenSolvablePolynomial<GenPolynomial<C>> P,
                                                                                   GenSolvablePolynomial<GenPolynomial<C>> S)

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

Parameters:

P - univariate recursive GenSolvablePolynomial.

S - univariate recursive GenSolvablePolynomial.

Returns:

gcd(P,S) with P = P'*gcd(P,S)*p and S = S'*gcd(P,S)*s, where deg_main(p) = deg_main(s) == 0.

rightRecursiveUnivariateGcd

public abstract GenSolvablePolynomial<GenPolynomial<C>> rightRecursiveUnivariateGcd(GenSolvablePolynomial<GenPolynomial<C>> P,
                                                                                    GenSolvablePolynomial<GenPolynomial<C>> S)

Univariate GenSolvablePolynomial right recursive greatest common divisor. Uses pseudoRemainder for remainder.

Parameters:

P - univariate recursive GenSolvablePolynomial.

S - univariate recursive GenSolvablePolynomial.

Returns:

gcd(P,S) with P = p*gcd(P,S)*P' and S = s*gcd(P,S)*S', where deg_main(p) = deg_main(s) == 0.

rightContent

public GenSolvablePolynomial<C> rightContent(GenSolvablePolynomial<C> P)

GenSolvablePolynomial right content.

Specified by:

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

Parameters:

P - GenSolvablePolynomial.

Returns:

cont(P) with pp(P)*cont(P) = P.

rightPrimitivePart

public GenSolvablePolynomial<C> rightPrimitivePart(GenSolvablePolynomial<C> P)

GenSolvablePolynomial right primitive part.

Specified by:

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

Parameters:

P - GenSolvablePolynomial.

Returns:

pp(P) with pp(P)*cont(P) = P.

leftContent

public GenSolvablePolynomial<C> leftContent(GenSolvablePolynomial<C> P)

GenSolvablePolynomial left content.

Specified by:

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

Parameters:

P - GenSolvablePolynomial.

Returns:

cont(P) with cont(P)*pp(P) = P.

leftPrimitivePart

public GenSolvablePolynomial<C> leftPrimitivePart(GenSolvablePolynomial<C> P)

GenSolvablePolynomial left primitive part.

Specified by:

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

Parameters:

P - GenSolvablePolynomial.

Returns:

pp(P) with cont(P)*pp(P) = P.

divide

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

GenSolvablePolynomial division. Indirection to GenSolvablePolynomial method.

Parameters:

a - GenSolvablePolynomial.

b - coefficient.

Returns:

a/b with a = 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) with a = a'*gcd(a,b) and b = b'*gcd(a,b).

leftGcd

public GenSolvablePolynomial<C> leftGcd(GenSolvablePolynomial<C> P,
                                        GenSolvablePolynomial<C> S)

GenSolvablePolynomial greatest common divisor.

Specified by:

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

Parameters:

P - GenSolvablePolynomial.

S - GenSolvablePolynomial.

Returns:

gcd(P,S) with P = P'*gcd(P,S)*p and S = S'*gcd(P,S)*s, where deg_main(p) = deg_main(s) == 0.

leftLcm

public GenSolvablePolynomial<C> leftLcm(GenSolvablePolynomial<C> P,
                                        GenSolvablePolynomial<C> S)

GenSolvablePolynomial left least common multiple.

Specified by:

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

Parameters:

P - GenSolvablePolynomial.

S - GenSolvablePolynomial.

Returns:

lcm(P,S) with lcm(P,S) = P'*P = S'*S.

rightGcd

public GenSolvablePolynomial<C> rightGcd(GenSolvablePolynomial<C> P,
                                         GenSolvablePolynomial<C> S)

GenSolvablePolynomial right greatest common divisor.

Specified by:

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

Parameters:

P - GenSolvablePolynomial.

S - GenSolvablePolynomial.

Returns:

gcd(P,S) with P = p*gcd(P,S)*P' and S = s*gcd(P,S)*S', where deg_main(p) = deg_main(s) == 0.

rightLcm

public GenSolvablePolynomial<C> rightLcm(GenSolvablePolynomial<C> P,
                                         GenSolvablePolynomial<C> S)

GenSolvablePolynomial right least common multiple.

Specified by:

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

Parameters:

P - GenSolvablePolynomial.

S - GenSolvablePolynomial.

Returns:

lcm(P,S) with lcm(P,S) = P*P' = S*S'.

leftGcd

public GenSolvablePolynomial<C> leftGcd(java.util.List<GenSolvablePolynomial<C>> A)

List of GenSolvablePolynomials left greatest common divisor.

Parameters:

A - non empty list of GenSolvablePolynomials.

Returns:

gcd(A_i) with A_i = A'_i*gcd(A_i)*a_i, where deg_main(a_i) == 0.

leftCoPrime

public java.util.List<GenSolvablePolynomial<C>> leftCoPrime(java.util.List<GenSolvablePolynomial<C>> A)

GenSolvablePolynomial co-prime list.

Specified by:

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

Parameters:

A - list of GenSolvablePolynomials.

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.

leftCoPrimeRec

public java.util.List<GenSolvablePolynomial<C>> leftCoPrimeRec(java.util.List<GenSolvablePolynomial<C>> A)

GenSolvablePolynomial left co-prime list.

Parameters:

A - list of GenSolvablePolynomials.

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.

leftCoPrime

public java.util.List<GenSolvablePolynomial<C>> leftCoPrime(GenSolvablePolynomial<C> a,
                                                            java.util.List<GenSolvablePolynomial<C>> P)

GenSolvablePolynomial left co-prime list.

Parameters:

a - GenSolvablePolynomial.

P - co-prime list of GenSolvablePolynomials.

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.

isLeftCoPrime

public boolean isLeftCoPrime(java.util.List<GenSolvablePolynomial<C>> A)

GenSolvablePolynomial test for co-prime list.

Specified by:

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

Parameters:

A - list of GenSolvablePolynomials.

Returns:

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

isLeftCoPrime

public boolean isLeftCoPrime(java.util.List<GenSolvablePolynomial<C>> P,
                             java.util.List<GenSolvablePolynomial<C>> A)

GenSolvablePolynomial test for left co-prime list of given list.

Parameters:

A - list of GenSolvablePolynomials.

P - list of co-prime GenSolvablePolynomials.

Returns:

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

baseExtendedGcd

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

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

Parameters:

P - univariate GenSolvablePolynomial.

S - univariate GenSolvablePolynomial.

Returns:

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

baseHalfExtendedGcd

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

Univariate GenSolvablePolynomial half extended greatest comon divisor. Uses sparse pseudoRemainder for remainder.

Parameters:

S - GenSolvablePolynomial.

Returns:

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

baseGcdDiophant

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

Univariate GenSolvablePolynomial greatest common divisor diophantine version.

Parameters:

P - univariate GenSolvablePolynomial.

S - univariate GenSolvablePolynomial.

c - univariate GenSolvablePolynomial.

Returns:

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

leftOreCond

public C[] leftOreCond(C a,
                       C b)

Coefficient left Ore condition. Generators for the left Ore condition of two coefficients.

Parameters:

a - coefficient.

b - coefficient.

Returns:

[oa, ob] = leftOreCond(a,b), with oa*a == ob*b.

leftOreCond

public GenSolvablePolynomial<C>[] leftOreCond(GenSolvablePolynomial<C> a,
                                              GenSolvablePolynomial<C> b)

Left Ore condition. Generators for the left Ore condition of two solvable polynomials.

Parameters:

a - solvable polynomial

b - solvable polynomial

Returns:

[p,q] with p*a = q*b

rightOreCond

public C[] rightOreCond(C a,
                        C b)

Coefficient rigth Ore condition. Generators for the right Ore condition of two coefficients.

Parameters:

a - coefficient.

b - coefficient.

Returns:

[oa, ob] = rightOreCond(a,b), with a*oa == b*ob.

rightOreCond

public GenSolvablePolynomial<C>[] rightOreCond(GenSolvablePolynomial<C> a,
                                               GenSolvablePolynomial<C> b)

Right Ore condition. Generators for the right Ore condition of two solvable polynomials.

Parameters:

a - solvable polynomial

b - solvable polynomial

Returns:

[p,q] with a*p = b*q