orbital.math
Class AlgebraicAlgorithms
java.lang.Object
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 reverselexicographical 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 Rvectorial coefficients
into an array of polynomials obtained by coordinate projections. 
static java.util.Comparator 
DEGREE(java.util.Comparator monomialBaseOrder)
Generalised degreelexicographical 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)
nary 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)
Reduce_{g}:K[X_{0},...,X_{n1}]→K[X_{0},...,X_{n1}]; 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 Rvectorial coefficients. 
Methods inherited from class java.lang.Object 
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait 
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.
X_{0}^{i0}⋅…⋅X_{n1}^{in1} ≤ X_{0}^{j0}⋅…⋅X_{n1}^{jn1}
:⇔ X_{0}^{i0}⋅…⋅X_{n1}^{in1}=X_{0}^{j0}⋅…⋅X_{n1}^{jn1}
∨ i_{k}<j_{k} for k := min{k ¦ i_{k}≠j_{k}}
Especially X_{0}^{2} > X_{0} > X_{1}^{2} > X_{1} > … > X_{n1} > 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.
X_{0}^{i0}⋅…⋅X_{n1}^{in1} ≤ X_{0}^{j0}⋅…⋅X_{n1}^{jn1}
:⇔ X_{0}^{i0}⋅…⋅X_{n1}^{in1}=X_{0}^{j0}⋅…⋅X_{n1}^{jn1}
∨ i_{k}<j_{k} for k := max{k ¦ i_{k}≠j_{k}}
Especially 1 < X_{0} < X_{0}^{2} < X_{1} < X_{1}^{2} < … < X_{n1}.
 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 reverselexicographical 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)
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
X_{0}^{i0}⋅…⋅X_{n1}^{in1} ≤ X_{0}^{j0}⋅…⋅X_{n1}^{jn1}
:⇔ X_{0}^{i0}⋅…⋅X_{n1}^{in1}=X_{0}^{j0}⋅…⋅X_{n1}^{jn1}
∨ i_{π(k)}<j_{π(k)} for k := min{k ¦ i_{π(k)}≠j_{π(k)}}
Elimination orders favouring to eliminate quantified variables over
nonquantifieds can be specified by a permutation.
 Parameters:
permutation
 the permutation π∈S_{n} specifying the order of relevance of the variables as
X_{π(0)} > X_{π(1)} > … > X_{π(n1)} 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 degreelexicographical 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.
X_{0}^{i0}⋅…⋅X_{n1}^{in1} ≤ X_{0}^{j0}⋅…⋅X_{n1}^{jn1}
:⇔ deg(X_{0}^{i0}⋅…⋅X_{n1}^{in1})<deg(X_{0}^{j0}⋅…⋅X_{n1}^{jn1})
∨ (deg(X_{0}^{i0}⋅…⋅X_{n1}^{in1})=deg(X_{0}^{j0}⋅…⋅X_{n1}^{jn1}) ∧ X_{0}^{i0}⋅…⋅X_{n1}^{in1} <_{base} X_{0}^{j0}⋅…⋅X_{n1}^{jn1})
 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 ≤ ⊆ M_{n} × M_{n} be a total order on the monoid of monomials
M_{n} := {X^{ν} := X_{1}^{ν1}⋅…⋅X_{n}^{νn} ¦ ν=(ν_{1},…,ν_{n}) ∈ N^{n}}.
 admissible
 ≤ is admissible, if
 ∀X^{ν},X^{μ}∈M_{n} X^{ν} ≤ X^{μ} ⇒ ∀X^{λ}∈M_{n} X^{ν}⋅X^{λ} ≤ X^{μ}⋅X^{λ}
 ∣ ⊆ ≤
(⇔ 1 = min M_{n})
⇒ M_{n} is wellordered 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
 ∀a∈R\{0} gcd(a, 0) = a
 ∀a∈R,b∈R\{0} gcd(a, b) = gcd(b, a mod b)
 Also see
Euclidean
 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, 351369, 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 FergusonForcade 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)
 nary and extended gcd.
This implementation uses the extended euclidian algorithm,
EuclidLagrangeBerlekamp Algorithm (ELBA).
 Parameters:
elements
 an array {a_{0},…,a_{n1}} ⊆ R whose gcd to determine.
 Returns:
 an array {s_{0},…,s_{n1}, d} ⊆ R with
cofactors s_{i} and greatest common divisor d,
where
d = gcd({a_{0},…,a_{n1}}) = ∑_{i=0,…,n1} s_{i}*a_{i}.
 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 ≡ x_{i} (mod m_{i}) for i=1,…,n
The Chinese Remainder Theorem guarantees a unique solution x
(modulo m_{1}*…*m_{n}), if the m_{i} are coprime,
i.e. (m_{i})+(m_{j})=(1).
The isomorphisms involved form the Chinese remainder algorithm
R/⋂_{ν=1,…,n} I_{ν} 
→̃ 
R/I_{1} × … × R/I_{n} 
x 
↦ 
(x (mod m_{1}),…,x (mod m_{n})) 
∑_{i=1,…,n} x_{i}((∏_{j≠i} m_{j})^{1} (mod m_{i}))∏_{j≠i} m_{j} 
↤ 
(x_{1},…,x_{n}) 
The incremental algorithm is
x := x_{1}
M := 1
for i := 2 to n do
M := M*m_{i1}
x := x + ((x_{i}  x)*(M^{1} mod m_{i}) mod m_{i}) * M
end for
return x
 Parameters:
x
 the array of congruence values x_{1},…,x_{n}.m
 the array of corresponding moduli m_{1},…,m_{n}.
 Returns:
 the unique solution x (modulo m_{1}*…*m_{n}).
 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)
 Reduce_{g}:K[X_{0},...,X_{n1}]→K[X_{0},...,X_{n1}]; f ↦ "f reduced with respect to g".
Performs a division by multiple polynomials.
Iteratedly performs the following Buchbergerreduction for f=∑_{ν} λ_{ν}*X^{ν}:
f →_{g} h := f  λ_{ν}/l_{c}(g) * X^{ν}/l(g) * g = f  λ_{ν}X^{ν} / (l_{c}(g) l(g)) * g
for some g∈G with l(g) being the leading monomial in g with leading coefficient l_{c}(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[X_{1},…,X_{n}]
if one of the following equivalent conditions is satisfied.
 L(I)=L(G)
where L(A) := {l(a)X^{ν} ¦ a∈A,X^{ν}∈M_{n}} "⊴" M_{n} for A⊆M_{n}
 ∀f∈I\{0} ∃g∈G l(g) ∣ l(f)
 ∀f∈I f is reduced to 0 with respect to G
 (f∈I ⇔ ∃q_{g}∈K[X_{1},…,X_{n}] f = ∑_{g∈G} q_{g}g ∧ l(f) = max{l(q_{g}g) ¦ g∈G})
 each f∈K[X_{1},…,X_{n}] has a unique (reduced) reduction with respect to G
 the Greduced polynomials form a system of representatives of K[X_{1},…,X_{n}]/I
 ∀f≠g∈G 0 is a reduction of the
S(f,g) := 1∕l_{c}(f)*X^{ν}⋅f  1∕l_{c}(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[X_{1},…,X_{n}] 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∈R^{n} : ∀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.
 With respect to the lexicographic term ordering X_{n}>...>X_{1},
G has the elimination property, i.e.
(G)∩K[X_{1},…,X_{i}] = (G∩K[X_{1},…,X_{n}])
This relationship of "triangularisation" (in case V(I) is 0dimensional) is important for successively solving systems of polynomial equations by backsubstitution.
 Implicitisation, i.e., converting parametric equations to implicit form.
For the parametrized surface x_{1}=f_{1}(t_{1},...,t_{m}),...,x_{n}=f_{n}(t_{1},...,t_{m}),
a Gröbner basis (with respect to a monomial order having parameters greater than variables)
of the
(x_{1}f_{1}(t_{1},...,t_{m}),...,x_{n}f_{n}(t_{1},...,t_{m}))
yields a basis of which the subset of polynomials without the parameters t_{i}
describes the smallest affine variety containing the original surface.
 Deciding equality of ideals by equality of their
unique reduced Gröbner bases with respect to the same monomial ordering.
 Intersecting ideals I=(G) and J=(H)
as the restriction to polynomials without fresh variable t
of the Gröbner basis of
{t*G,(1t)*H}
with respect to a t>x_{1},...,x_{n} monomial order.
 V(I)=∅ iff G={1}, i.e., there are no solutions (when K is algebraically closed)
 V(I) is 0dimensional iff for each X_{i}, G contains an f with a pure leading monomial l(f)=X_{i}^{k}, which means "finitely many solutions" (when K is algebraically closed)
 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. p263297. 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)=e^{A(tτ)}η + ∫_{τ}^{t} e^{A(ts)}b(s) ds
where
e^{At} = ∑_{n=0,...} 1/n! A^{n}t^{n}
 See Also:
 "Walter, W. Ordinary Differential Equations Springer, 1998"
componentPolynomials
public static final UnivariatePolynomial[] componentPolynomials(UnivariatePolynomial p)
 Converts a univariate polynomial with Rvectorial coefficients
into an array of polynomials obtained by coordinate projections.
 Returns:
 an array of the respective scalar polynomials
P_{i} = a_{0,i}+a_{1,i}X+...+a_{n,i}X^{n}
 See Also:
vectorialPolynomial(UnivariatePolynomial[])
vectorialPolynomial
public static final UnivariatePolynomial vectorialPolynomial(UnivariatePolynomial[] pi)
 Converts an array of coordinate polynomials
to a polynomial with Rvectorial coefficients.
 Returns:
 a vectorial polynomial a_{0}+a_{1}X+...+a_{n}X^{n}
with vectorial coefficients a_{i}=(a_{i,1},...,a_{i,k})
 See Also:
componentPolynomials(UnivariatePolynomial)
Copyright © 19962009 André Platzer
All Rights Reserved.