Orbital library

orbital.math
Class AlgebraicAlgorithms

java.lang.Object
  extended by orbital.math.AlgebraicAlgorithms

public final class AlgebraicAlgorithms
extends java.lang.Object

Algebraic algorithms and computer algebra.

Author:
André Platzer
See Also:
MathUtilities, Utility
Stereotype:
Utilities, Module

Field Summary
static java.util.Comparator DEGREE_LEXICOGRAPHIC
          Degree lexicographical order on monoid of monomials.
static java.util.Comparator DEGREE_REVERSE_LEXICOGRAPHIC
          Degree reverse-lexicographical order on monoid of monomials.
static BinaryFunction gcd
          Returns greatest common divisor (gcd) of two elements of an (Euclidean) ring.
static BinaryFunction lcm
          Returns least common multiple (lcm) of two elements of an (Euclidean) ring.
static java.util.Comparator LEXICOGRAPHIC
          Lexicographical order on monoid of monomials.
static java.util.Comparator REVERSE_LEXICOGRAPHIC
          Reverse lexicographical order on monoid of monomials.
 
Method Summary
static Quotient chineseRemainder(Arithmetic[] x, Arithmetic[] m)
          Simulatenously solve independent congruences.
static UnivariatePolynomial[] componentPolynomials(UnivariatePolynomial p)
          Converts a univariate polynomial with R-vectorial coefficients into an array of polynomials obtained by coordinate projections.
static java.util.Comparator DEGREE(java.util.Comparator monomialBaseOrder)
          Generalised degree-lexicographical order on monoid of monomials.
static Function dSolve(Matrix A, Vector b, Real tau, Vector eta)
          Symbolically solves ordinary differential equation system.
static Euclidean[] gcd(Euclidean[] elements)
          n-ary and extended gcd.
static Euclidean gcd(Euclidean a, Euclidean b)
          Returns greatest common divisor (gcd) of two elements of an (Euclidean) ring.
static java.util.Set groebnerBasis(java.util.Set g, java.util.Comparator monomialOrder)
          Get the reduced Gröbner basis of g.
static java.util.Comparator INDUCED(java.util.Comparator monomialOrder)
          The partial lexicographial order on polynomials induced by an admissible total order on monomials.
static Euclidean lcm(Euclidean a, Euclidean b)
          Returns least common multiple (lcm) of two ring elements.
static java.util.Comparator LEXICOGRAPHIC(int[] permutation)
          (Generalised) lexicographical order on monoid of monomials.
static java.util.Collection occurringMonomials(Polynomial f)
          Get a collection of those (exponents of) monomials that occur in f (i.e.
static Function reduce(java.util.Collection g, java.util.Comparator monomialOrder)
          Reduceg:K[X0,...,Xn-1]→K[X0,...,Xn-1]; f ↦ "f reduced with respect to g".
static Polynomial reduce(Polynomial f, java.util.Collection g, java.util.Comparator monomialOrder)
          Reduce f with respect to g.
static UnivariatePolynomial vectorialPolynomial(UnivariatePolynomial[] pi)
          Converts an array of coordinate polynomials to a polynomial with R-vectorial coefficients.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Field Detail

LEXICOGRAPHIC

public static final java.util.Comparator LEXICOGRAPHIC
Lexicographical order on monoid of monomials. This is an admissible total order. The monomials are expected to be encoded as their exponents in the form of int[]s.
X0i0⋅…⋅Xn-1in-1 ≤ X0j0⋅…⋅Xn-1jn-1 :⇔ X0i0⋅…⋅Xn-1in-1=X0j0⋅…⋅Xn-1jn-1
∨ ik<jk for k := min{k ¦ ik≠jk}
Especially X02 > X0 > X12 > X1 > … > Xn-1 > 1.

See Also:
LEXICOGRAPHIC(int[])
Note:
Reduced Gröbner bases w.r.t. lexicographic orders have triangular shape.

REVERSE_LEXICOGRAPHIC

public static final java.util.Comparator REVERSE_LEXICOGRAPHIC
Reverse lexicographical order on monoid of monomials. This is an admissible total order. The monomials are expected to be encoded as their exponents in the form of int[]s.
X0i0⋅…⋅Xn-1in-1 ≤ X0j0⋅…⋅Xn-1jn-1 :⇔ X0i0⋅…⋅Xn-1in-1=X0j0⋅…⋅Xn-1jn-1
∨ ik<jk for k := max{k ¦ ik≠jk}
Especially 1 < X0 < X02 < X1 < X12 < … < Xn-1.

See Also:
LEXICOGRAPHIC(int[])

DEGREE_LEXICOGRAPHIC

public static final java.util.Comparator DEGREE_LEXICOGRAPHIC
Degree lexicographical order on monoid of monomials.

See Also:
DEGREE(Comparator), LEXICOGRAPHIC

DEGREE_REVERSE_LEXICOGRAPHIC

public static final java.util.Comparator DEGREE_REVERSE_LEXICOGRAPHIC
Degree reverse-lexicographical order on monoid of monomials.

See Also:
DEGREE(Comparator), REVERSE_LEXICOGRAPHIC

gcd

public static final BinaryFunction gcd
Returns greatest common divisor (gcd) of two elements of an (Euclidean) ring.

See Also:
gcd(Euclidean,Euclidean)

lcm

public static final BinaryFunction lcm
Returns least common multiple (lcm) of two elements of an (Euclidean) ring.

See Also:
lcm(Euclidean,Euclidean)
Method Detail

LEXICOGRAPHIC

public static final java.util.Comparator LEXICOGRAPHIC(int[] permutation)
(Generalised) lexicographical order on monoid of monomials. This is an admissible total order. The monomials are expected to be encoded as their exponents in the form of int[]s. This
X0i0⋅…⋅Xn-1in-1 ≤ X0j0⋅…⋅Xn-1jn-1 :⇔ X0i0⋅…⋅Xn-1in-1=X0j0⋅…⋅Xn-1jn-1
∨ iπ(k)<jπ(k) for k := min{k ¦ iπ(k)≠jπ(k)}
Elimination orders favouring to eliminate quantified variables over non-quantifieds can be specified by a permutation.

Parameters:
permutation - the permutation π∈Sn specifying the order of relevance of the variables as Xπ(0) > Xπ(1) > … > Xπ(n-1)
See Also:
LEXICOGRAPHIC, REVERSE_LEXICOGRAPHIC
Preconditions:
π is a permutation
Note:
Reduced Gröbner bases w.r.t. lexicographic orders have triangular shape modulo permutation.

DEGREE

public static final java.util.Comparator DEGREE(java.util.Comparator monomialBaseOrder)
Generalised degree-lexicographical order on monoid of monomials. Thus compares for degree in favor of the specified order. In case of (reverse) lexicographic order as basis, this is an admissible total order. The monomials are expected to be encoded as their exponents in the form of int[]s.
X0i0⋅…⋅Xn-1in-1 ≤ X0j0⋅…⋅Xn-1jn-1 :⇔ deg(X0i0⋅…⋅Xn-1in-1)<deg(X0j0⋅…⋅Xn-1jn-1)
(deg(X0i0⋅…⋅Xn-1in-1)=deg(X0j0⋅…⋅Xn-1jn-1) ∧ X0i0⋅…⋅Xn-1in-1 <base X0j0⋅…⋅Xn-1jn-1)

Parameters:
monomialBaseOrder - the order base to use when degree order is equal.

INDUCED

public static final java.util.Comparator INDUCED(java.util.Comparator monomialOrder)
The partial lexicographial order on polynomials induced by an admissible total order on monomials. p>q iff the largest monomial which occurs in p or q but not both is in p.
Let ≤ ⊆ Mn × Mn be a total order on the monoid of monomials Mn := {Xν := X1ν1⋅…⋅Xnνn ¦ ν=(ν1,…,νn) ∈ Nn}.
admissible
≤ is admissible, if
  1. ∀Xν,Xμ∈Mn Xν ≤ Xμ ⇒ ∀Xλ∈Mn Xν⋅Xλ ≤ Xμ⋅Xλ
  2. ∣ ⊆ ≤
    (⇔ 1 = min Mn)
⇒ Mn is well-ordered with ≤.

Parameters:
monomialOrder - is the underlying admissible total order on the monoid of monomials to use. Such monomial orders include LEXICOGRAPHIC, REVERSE_LEXICOGRAPHIC, DEGREE_LEXICOGRAPHIC.
See Also:
LEXICOGRAPHIC, REVERSE_LEXICOGRAPHIC, DEGREE_LEXICOGRAPHIC, DEGREE(Comparator), LEXICOGRAPHIC(int[])

gcd

public static Euclidean gcd(Euclidean a,
                            Euclidean b)
Returns greatest common divisor (gcd) of two elements of an (Euclidean) ring. The gcd is the greatest element (with respect to divisibility) in the ring which divides both, a and b.

In an Euclidean ring R it is true that

Returns:
gcd(a,b) := inf(a,b) with divides (∣) as a partial order on R.
See Also:
"Ferguson, H. R. P.; Bailey, D. H.; and Arno, S. Analysis of PSLQ, An Integer Relation Finding Algorithm. Math. Comput. 68, 351-369, 1999."
Preconditions:
¬(a==0 ∧ b==0)
Note:
the father of all algorithms is Euclid., the mother of all data structures are Euclidean rings., There are even principal ideal rings which are not Euclidean but where one can define the equivalent of the Euclidean algorithm. The algorithm for rational numbers was given in Book VII of Euclid's Elements, and the algorithm for reals appeared in Book X, and is the earliest example of an integer relation algorithm (Ferguson et al. 1999, also see Ferguson-Forcade algorithm in Ferguson et al. 1999)., gcd and lcm also exist in factorial rings (unique factorization domains), although they do not possess the same properties and their computation is far more expensive then.

lcm

public static Euclidean lcm(Euclidean a,
                            Euclidean b)
Returns least common multiple (lcm) of two ring elements. The lcm is the smallest ring element (with respect to divisibility) which is a multiple of both.

This implementation uses a*b/gcd(a,b).

Returns:
lcm(a,b) := sup(a,b) with ∣ "divides" as a partial order on R.

gcd

public static Euclidean[] gcd(Euclidean[] elements)
n-ary and extended gcd.

This implementation uses the extended euclidian algorithm, Euclid-Lagrange-Berlekamp Algorithm (ELBA).

Parameters:
elements - an array {a0,…,an-1} ⊆ R whose gcd to determine.
Returns:
an array {s0,…,sn-1, d} ⊆ R with cofactors si and greatest common divisor d, where d = gcd({a0,…,an-1}) = ∑i=0,…,n-1 si*ai.
See Also:
gcd(Euclidean,Euclidean)
Preconditions:
¬∀i elements[i]=0

chineseRemainder

public static final Quotient chineseRemainder(Arithmetic[] x,
                                              Arithmetic[] m)
Simulatenously solve independent congruences.
x ≡ xi (mod mi) for i=1,…,n
The Chinese Remainder Theorem guarantees a unique solution x (modulo m1*…*mn), if the mi are coprime, i.e. (mi)+(mj)=(1).
The isomorphisms involved form the Chinese remainder algorithm
R/ν=1,…,n Iν →̃ R/I1 × … × R/In
x (x (mod m1),…,x (mod mn))
i=1,…,n xi((∏j≠i mj)-1 (mod mi))j≠i mj (x1,…,xn)

The incremental algorithm is

 x := x1
 M := 1
 for i := 2 to n do
     M := M*mi-1
     x := x + ((xi - x)*(M-1 mod mi) mod mi) * M
 end for
 return x
 

Parameters:
x - the array of congruence values x1,…,xn.
m - the array of corresponding moduli m1,…,mn.
Returns:
the unique solution x (modulo m1*…*mn).
Preconditions:
∀i≠j (m[i])+(m[j])=(1), i.e. gcd(m[i],m[j])=1 ∧ m[i] use compatible representatives.
Note:
Newton interpolation and especially Lagrange interpolation are just special cases of incremental Chinese Remainder Theorem.

reduce

public static final Polynomial reduce(Polynomial f,
                                      java.util.Collection g,
                                      java.util.Comparator monomialOrder)
Reduce f with respect to g.

Parameters:
g - the collection of multinomials for reducing f.
monomialOrder - the order of monomials, which is decisive for the time complexity.
Returns:
h if h is a reduced reduction of f with respect to g.
See Also:
reduce(Collection, Comparator)

reduce

public static final Function reduce(java.util.Collection g,
                                    java.util.Comparator monomialOrder)
Reduceg:K[X0,...,Xn-1]→K[X0,...,Xn-1]; f ↦ "f reduced with respect to g". Performs a division by multiple polynomials.

Iteratedly performs the following Buchberger-reduction for f=∑ν λν*Xν:

f →g h := f - λν/lc(g) * Xν/l(g) * g = f - λνXν / (lc(g) l(g)) * g
for some g∈G with l(g) being the leading monomial in g with leading coefficient lc(g) and For such a reduction, Xν no longer occurs in h and h<f or h=0.

Parameters:
g - the collection of multinomials for reducing polynomials.
monomialOrder - the order of monomials, which is decisive for the time complexity.
Returns:
a function that reduces polynomials with respect to g.
See Also:
ValueFactory.quotient(Polynomial,Set,Comparator)

groebnerBasis

public static final java.util.Set groebnerBasis(java.util.Set g,
                                                java.util.Comparator monomialOrder)
Get the reduced Gröbner basis of g.

Gröbner basis
A finite generating system G is a Gröbner basis of I⊴K[X1,…,Xn] if one of the following equivalent conditions is satisfied.
  1. L(I)=L(G) where L(A) := {l(a)Xν ¦ a∈A,Xν∈Mn} "⊴" Mn for A⊆Mn
  2. ∀f∈I\{0} ∃g∈G l(g) ∣ l(f)
  3. ∀f∈I f is reduced to 0 with respect to G
  4. (f∈I ⇔ ∃qg∈K[X1,…,Xn] f = ∑g∈G qgg ∧ l(f) = max{l(qgg) ¦ g∈G})
  5. each f∈K[X1,…,Xn] has a unique (reduced) reduction with respect to G
  6. the G-reduced polynomials form a system of representatives of K[X1,…,Xn]/I
  7. ∀f≠g∈G 0 is a reduction of the S(f,g) := 1∕lc(f)*Xν⋅f - 1∕lc(g)*Xμ⋅g
    where Xν,Xμ are coprime and such that l(Xν⋅f)=l(Xμ⋅g)
A Gröbner basis G of I ⊴ K[X1,…,Xn] is
minimal
∀g≠h∈G l(g) ∤ l(h)
reduced
∀g∈G g reduced with respect to G\{g}
⇒ G minimal
G unique (up to multiplication by constants)

Two minimal Gröbner bases have the same number of elements and the same leading monomials. There is a unique reduced Gröbner basis. Gröbner basis were developed as a canonical simplifier as a means for computation in factor polynomial rings.

Applications

Let V(I)={x∈Rn : ∀f∈I f(x)=0} be the vanishing ideal of ideal I and let G be the reduced Gröbner basis of the ideal I with respect to some monomial ordering.

Parameters:
g - the collection of multinomials that is a generating system of the ideal (g) for which to construct a Gröbner basis.
monomialOrder - the order of monomials, which is decisive for the time complexity.
See Also:
"Buchberger, Bruno. Ein Algorithmus zum Auffinden der Basiselemente des Restklassenrings nach einem nulldimensionalen Polynomideal. PhD thesis, Universität Innsbruck, 1965.", "Buchberger, Bruno. Gröbner bases: An algorithmic method in polynomial ideal theory. In Bose, N.K., editor, Recent Trends in Multidimensional Systems Theory. Reidel Publ.Co., 1985.", "Knuth, Donald E. and Bendix, P.B. Simple word problems in universal algebras. In Leech, J., editor, Computational Problems in Abstract Algebras. p263-297. Pergamon Press, Oxford, 1970."
Note:
The Buchberger algorithm used to construct a Gröbner basis is equivalent to gcd(Euclidean[]) in case of one variable, and to LUDecomposition in case of linear polynomials.

occurringMonomials

public static java.util.Collection occurringMonomials(Polynomial f)
Get a collection of those (exponents of) monomials that occur in f (i.e. with coefficient ≠0).

See Also:
Polynomial.indices()

dSolve

public static final Function dSolve(Matrix A,
                                    Vector b,
                                    Real tau,
                                    Vector eta)
Symbolically solves ordinary differential equation system. Solves (in)homogeneous ODE with constant coefficients.

Parameters:
A - the complex matrix of coefficients.
tau - the initial time τ of the initial values η.
eta - the complex vector η of initial values.
b - the inhomogeneous vector.
Returns:
The solution x of the initial value problem
x'(t)=A*x(t) + b(t)
x(τ)=η
which is
x(t)=eA(t-τ)η + ∫τt eA(t-s)b(s) ds
where
eAt = ∑n=0,... 1/n! Antn
See Also:
"Walter, W. Ordinary Differential Equations Springer, 1998"

componentPolynomials

public static final UnivariatePolynomial[] componentPolynomials(UnivariatePolynomial p)
Converts a univariate polynomial with R-vectorial coefficients into an array of polynomials obtained by coordinate projections.

Returns:
an array of the respective scalar polynomials Pi = a0,i+a1,iX+...+an,iXn
See Also:
vectorialPolynomial(UnivariatePolynomial[])

vectorialPolynomial

public static final UnivariatePolynomial vectorialPolynomial(UnivariatePolynomial[] pi)
Converts an array of coordinate polynomials to a polynomial with R-vectorial coefficients.

Returns:
a vectorial polynomial a0+a1X+...+anXn with vectorial coefficients ai=(ai,1,...,ai,k)
See Also:
componentPolynomials(UnivariatePolynomial)

Orbital library
1.3.0: 11 Apr 2009

Copyright © 1996-2009 André Platzer
All Rights Reserved.