Class GreatestCommonDivisorAbstract<C extends GcdRingElem<C>>

java.lang.Object
edu.jas.ufd.GreatestCommonDivisorAbstract<C>
All Implemented Interfaces:
GreatestCommonDivisor<C>, Serializable
Direct Known Subclasses:
GCDProxy, GreatestCommonDivisorFake, GreatestCommonDivisorHensel, GreatestCommonDivisorModEval, GreatestCommonDivisorModular, GreatestCommonDivisorPrimitive, GreatestCommonDivisorSimple, GreatestCommonDivisorSubres
public abstract class GreatestCommonDivisorAbstract<C extends GcdRingElem<C>> extends Object implements GreatestCommonDivisor<C>
Greatest common divisor algorithms.
See Also:

  • Field Details

    • logger

      private static final org.apache.logging.log4j.Logger logger

    • debug

      private static final boolean debug

  • Constructor Details

    • GreatestCommonDivisorAbstract

      public GreatestCommonDivisorAbstract()

  • Method Details

    • toString

      public String toString()
      Get the String representation.
      Overrides:
      toString in class Object
      See Also:

    • 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 List<GenPolynomial<C>> basePrimitivePart(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 List<GenPolynomial<GenPolynomial<C>>> recursivePrimitivePart(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(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:
      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:
      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:
      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:
      UnsupportedOperationException - if there is no implementation in the sub-class.
      See Also:

    • coPrime

      public List<GenPolynomial<C>> coPrime(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 List<GenPolynomial<C>> coPrimeRec(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 List<GenPolynomial<C>> coPrime(GenPolynomial<C> a, 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(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(List<GenPolynomial<C>> P, List<GenPolynomial<C>> A)
      GenPolynomial test for co-prime list of given list.
      Parameters:
      P - list of co-prime GenPolynomials.
      A - list of 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 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 List<GenPolynomial<C>> basePartialFraction(GenPolynomial<C> A, 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, List<GenPolynomial<C>> D, 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, 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, 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.