Package 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:
GreatestCommonDivisorFake
,GreatestCommonDivisorPrimitive
,GreatestCommonDivisorSimple
,GreatestCommonDivisorSyzygy
,SGCDParallelProxy
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 Description GreatestCommonDivisorAbstract(RingFactory<C> cf)
Constructor.GreatestCommonDivisorAbstract(RingFactory<C> cf, SolvableSyzygyAbstract<C> s)
Constructor.
-
Method Summary
-
-
-
Constructor Detail
-
GreatestCommonDivisorAbstract
public GreatestCommonDivisorAbstract(RingFactory<C> cf)
Constructor.- Parameters:
cf
- coefficient ring.
-
GreatestCommonDivisorAbstract
public GreatestCommonDivisorAbstract(RingFactory<C> cf, SolvableSyzygyAbstract<C> s)
Constructor.- Parameters:
cf
- coefficient ring.s
- algorithm for SolvableSyzygy computation.
-
-
Method Detail
-
toString
public java.lang.String toString()
Get the String representation.- Overrides:
toString
in classjava.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).
-
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.
-
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.
-
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.
-
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.
-
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.
-
leftContent
public GenSolvablePolynomial<C> leftContent(GenSolvablePolynomial<C> P)
GenSolvablePolynomial left content.- Specified by:
leftContent
in interfaceGreatestCommonDivisor<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 interfaceGreatestCommonDivisor<C extends GcdRingElem<C>>
- Parameters:
P
- GenSolvablePolynomial.- Returns:
- pp(P) with cont(P)*pp(P) = P.
-
rightContent
public GenSolvablePolynomial<C> rightContent(GenSolvablePolynomial<C> P)
GenSolvablePolynomial right content.- Specified by:
rightContent
in interfaceGreatestCommonDivisor<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 interfaceGreatestCommonDivisor<C extends GcdRingElem<C>>
- Parameters:
P
- GenSolvablePolynomial.- Returns:
- pp(P) with pp(P)*cont(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' = a/b with a = a'*b.
-
rightDivide
public GenSolvablePolynomial<C> rightDivide(GenSolvablePolynomial<C> a, C b)
GenSolvablePolynomial right division. Indirection to GenSolvablePolynomial method.- Parameters:
a
- GenSolvablePolynomial.b
- coefficient.- Returns:
- a' = a/b with a = b*a'.
-
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 = gcd(a,b)*a' and b = gcd(a,b)*b'.
-
leftGcd
public C leftGcd(C a, C b)
Coefficient greatest common divisor. Indirection to coefficient method.- Parameters:
a
- coefficient.b
- coefficient.- Returns:
- gcd(a,b) with a = gcd(a,b)*a' and b = gcd(a,b)*b'.
-
leftGcd
public GenSolvablePolynomial<C> leftGcd(GenSolvablePolynomial<C> P, GenSolvablePolynomial<C> S)
GenSolvablePolynomial greatest common divisor.- Specified by:
leftGcd
in interfaceGreatestCommonDivisor<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 interfaceGreatestCommonDivisor<C extends GcdRingElem<C>>
- Parameters:
P
- GenSolvablePolynomial.S
- GenSolvablePolynomial.- Returns:
- lcm(P,S) with lcm(P,S) = P'*P = S'*S.
-
rightGcd
public C rightGcd(C a, C b)
Coefficient greatest common divisor. Indirection to coefficient method.- Parameters:
a
- coefficient.b
- coefficient.- Returns:
- gcd(a,b) with a = gcd(a,b)*a' and b = gcd(a,b)*b'.
-
rightGcd
public GenSolvablePolynomial<C> rightGcd(GenSolvablePolynomial<C> P, GenSolvablePolynomial<C> S)
GenSolvablePolynomial right greatest common divisor.- Specified by:
rightGcd
in interfaceGreatestCommonDivisor<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 interfaceGreatestCommonDivisor<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 interfaceGreatestCommonDivisor<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 interfaceGreatestCommonDivisor<C extends GcdRingElem<C>>
- Parameters:
A
- list of GenSolvablePolynomials.- Returns:
- true if gcd(b,c) = 1 for all b != c in A, 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:
P
- list of co-prime GenSolvablePolynomials.A
- list of 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 common 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 polynomialb
- solvable polynomial- Returns:
- [p,q] with p*a = q*b
-
rightOreCond
public C[] rightOreCond(C a, C b)
Coefficient right 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 polynomialb
- solvable polynomial- Returns:
- [p,q] with a*p = b*q
-
isLeftOreCond
public boolean isLeftOreCond(GenSolvablePolynomial<C> a, GenSolvablePolynomial<C> b, GenSolvablePolynomial<C> p, GenSolvablePolynomial<C> q)
Is left Ore condition. Test left Ore condition of two solvable polynomials.- Parameters:
a
- solvable polynomialb
- solvable polynomialp
- solvable polynomialq
- solvable polynomial- Returns:
- true, if p*a = q*b, else false
-
isRightOreCond
public boolean isRightOreCond(GenSolvablePolynomial<C> a, GenSolvablePolynomial<C> b, GenSolvablePolynomial<C> p, GenSolvablePolynomial<C> q)
Is right Ore condition. Test right Ore condition of two solvable polynomials.- Parameters:
a
- solvable polynomialb
- solvable polynomialp
- solvable polynomialq
- solvable polynomial- Returns:
- true, if a*p = b*q, else false
-
leftGcdCofactors
public GenSolvablePolynomial<C>[] leftGcdCofactors(GenSolvablePolynomialRing<C> r, GenSolvablePolynomial<C> n, GenSolvablePolynomial<C> d)
Left greatest common divisor and cofactors.- Parameters:
r
- solvable polynomial ring.n
- first solvable polynomial.d
- second solvable polynomial.- Returns:
- [ g=leftGcd(n,d), n/g, d/g ]
-
rightGcdCofactors
public GenSolvablePolynomial<C>[] rightGcdCofactors(GenSolvablePolynomialRing<C> r, GenSolvablePolynomial<C> n, GenSolvablePolynomial<C> d)
Right greatest common divisor and cofactors.- Parameters:
r
- solvable polynomial ring.n
- first solvable polynomial.d
- second solvable polynomial.- Returns:
- [ g=rightGcd(n,d), n/g, d/g ]
-
-