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 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 |
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)
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
- ∀Xν,Xμ∈Mn Xν ≤ Xμ ⇒ ∀Xλ∈Mn Xν⋅Xλ ≤ Xμ⋅Xλ
- ∣ ⊆ ≤
(⇔ 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
- ∀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, 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.
- L(I)=L(G)
where L(A) := {l(a)Xν ¦ a∈A,Xν∈Mn} "⊴" Mn for A⊆Mn
- ∀f∈I\{0} ∃g∈G l(g) ∣ l(f)
- ∀f∈I f is reduced to 0 with respect to G
- (f∈I ⇔ ∃qg∈K[X1,…,Xn] f = ∑g∈G qgg ∧ l(f) = max{l(qgg) ¦ g∈G})
- each f∈K[X1,…,Xn] has a unique (reduced) reduction with respect to G
- the G-reduced polynomials form a system of representatives of K[X1,…,Xn]/I
- ∀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.
- With respect to the lexicographic term ordering Xn>...>X1,
G has the elimination property, i.e.
(G)∩K[X1,…,Xi] = (G∩K[X1,…,Xn])
This relationship of "triangularisation" (in case V(I) is 0-dimensional) is important for successively solving systems of polynomial equations by backsubstitution.
- Implicitisation, i.e., converting parametric equations to implicit form.
For the parametrized surface x1=f1(t1,...,tm),...,xn=fn(t1,...,tm),
a Gröbner basis (with respect to a monomial order having parameters greater than variables)
of the
(x1-f1(t1,...,tm),...,xn-fn(t1,...,tm))
yields a basis of which the subset of polynomials without the parameters ti
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,(1-t)*H}
with respect to a t>x1,...,xn monomial order.
- V(I)=∅ iff G={1}, i.e., there are no solutions (when K is algebraically closed)
- V(I) is 0-dimensional iff for each Xi, G contains an f with a pure leading monomial l(f)=Xik, 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. 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)
Copyright © 1996-2009 André Platzer
All Rights Reserved.