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>
,Serializable
- Direct Known Subclasses:
GreatestCommonDivisorFake
,GreatestCommonDivisorPrimitive
,GreatestCommonDivisorSimple
,GreatestCommonDivisorSyzygy
,SGCDParallelProxy
public abstract class GreatestCommonDivisorAbstract<C extends GcdRingElem<C>>
extends Object
implements GreatestCommonDivisor<C>
(Non-unique) factorization domain greatest common divisor common algorithms.
- See Also:
-
Field Summary
FieldsModifier and TypeFieldDescription(package private) final RingFactory
<C> Coefficient ring.private static final boolean
private static final org.apache.logging.log4j.Logger
(package private) final SolvableSyzygyAbstract
<C> Engine for syzygy computation, mainly for Ore conditions. -
Constructor Summary
ConstructorsConstructorDescriptionConstructor.Constructor. -
Method Summary
Modifier and TypeMethodDescriptionUnivariate GenSolvablePolynomial extended greatest common divisor.Univariate GenSolvablePolynomial greatest common divisor diophantine version.Univariate GenSolvablePolynomial half extended greatest common divisor.GenSolvablePolynomial base recursive content.GenSolvablePolynomial base recursive primitive part.divide
(GenSolvablePolynomial<C> a, C b) GenSolvablePolynomial division.Coefficient greatest common divisor.boolean
GenSolvablePolynomial test for co-prime list.boolean
GenSolvablePolynomial test for left co-prime list of given list.boolean
isLeftOreCond
(GenSolvablePolynomial<C> a, GenSolvablePolynomial<C> b, GenSolvablePolynomial<C> p, GenSolvablePolynomial<C> q) Is left Ore condition.boolean
isRightOreCond
(GenSolvablePolynomial<C> a, GenSolvablePolynomial<C> b, GenSolvablePolynomial<C> p, GenSolvablePolynomial<C> q) Is right Ore condition.GenSolvablePolynomial base coefficient content.abstract GenSolvablePolynomial
<C> Univariate GenSolvablePolynomial greatest common divisor.GenSolvablePolynomial base coefficient primitive part.GenSolvablePolynomial left content.GenSolvablePolynomial left co-prime list.GenSolvablePolynomial co-prime list.GenSolvablePolynomial left co-prime list.Coefficient greatest common divisor.GenSolvablePolynomial greatest common divisor.List of GenSolvablePolynomials left greatest common divisor.leftGcdCofactors
(GenSolvablePolynomialRing<C> r, GenSolvablePolynomial<C> n, GenSolvablePolynomial<C> d) Left greatest common divisor and cofactors.GenSolvablePolynomial left least common multiple.C[]
leftOreCond
(C a, C b) Coefficient left Ore condition.Left Ore condition.GenSolvablePolynomial left primitive part.GenSolvablePolynomial left recursive content.leftRecursiveGcd
(GenSolvablePolynomial<GenPolynomial<C>> P, GenSolvablePolynomial<GenPolynomial<C>> S) GenSolvablePolynomial left recursive greatest common divisor.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 commuting recursive content.GenSolvablePolynomial right base coefficient content.abstract GenSolvablePolynomial
<C> Univariate GenSolvablePolynomial right greatest common divisor.GenSolvablePolynomial right base coefficient primitive part.GenSolvablePolynomial right content.rightDivide
(GenSolvablePolynomial<C> a, C b) GenSolvablePolynomial right division.Coefficient greatest common divisor.GenSolvablePolynomial right greatest common divisor.rightGcdCofactors
(GenSolvablePolynomialRing<C> r, GenSolvablePolynomial<C> n, GenSolvablePolynomial<C> d) Right greatest common divisor and cofactors.GenSolvablePolynomial right least common multiple.C[]
rightOreCond
(C a, C b) Coefficient right Ore condition.Right Ore condition.GenSolvablePolynomial right primitive part.GenSolvablePolynomial right recursive content.rightRecursiveGcd
(GenSolvablePolynomial<GenPolynomial<C>> P, GenSolvablePolynomial<GenPolynomial<C>> S) GenSolvablePolynomial right recursive greatest common divisor.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.toString()
Get the String representation.
-
Field Details
-
logger
private static final org.apache.logging.log4j.Logger logger -
debug
private static final boolean debug -
syz
Engine for syzygy computation, mainly for Ore conditions. -
coFac
Coefficient ring.
-
-
Constructor Details
-
GreatestCommonDivisorAbstract
Constructor.- Parameters:
cf
- coefficient ring.
-
GreatestCommonDivisorAbstract
Constructor.- Parameters:
cf
- coefficient ring.s
- algorithm for SolvableSyzygy computation.
-
-
Method Details
-
toString
Get the String representation. -
leftBaseContent
GenSolvablePolynomial base coefficient content.- Parameters:
P
- GenSolvablePolynomial.- Returns:
- cont(P) with pp(P)*cont(P) = P.
-
rightBaseContent
GenSolvablePolynomial right base coefficient content.- Parameters:
P
- GenSolvablePolynomial.- Returns:
- cont(P) with cont(P)*pp(P) = P.
-
leftBasePrimitivePart
GenSolvablePolynomial base coefficient primitive part.- Parameters:
P
- GenSolvablePolynomial.- Returns:
- pp(P) with pp(P)*cont(P) = P.
-
rightBasePrimitivePart
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
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
GenSolvablePolynomial left recursive content.- Parameters:
P
- recursive GenSolvablePolynomial.- Returns:
- cont(P) with cont(P)*pp(P) = P.
-
rightRecursiveContent
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
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
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
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
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
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
GenSolvablePolynomial division. Indirection to GenSolvablePolynomial method.- Parameters:
a
- GenSolvablePolynomial.b
- coefficient.- Returns:
- a' = a/b with a = a'*b.
-
rightDivide
GenSolvablePolynomial right division. Indirection to GenSolvablePolynomial method.- Parameters:
a
- GenSolvablePolynomial.b
- coefficient.- Returns:
- a' = a/b with a = b*a'.
-
gcd
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
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
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
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
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
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
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
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
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
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 List<GenSolvablePolynomial<C>> leftCoPrime(GenSolvablePolynomial<C> a, 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
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
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
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
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 ]
-