Package edu.jas.application

Class Ideal<C extends GcdRingElem<C>>

  • All Implemented Interfaces:
    java.io.Serializable, java.lang.Comparable<Ideal<C>>
    public class Ideal<C extends GcdRingElem<C>>
extends java.lang.Object
implements java.lang.Comparable<Ideal<C>>, java.io.Serializable
    Ideal implements some methods for ideal arithmetic, for example intersection, quotient and zero and positive dimensional ideal decomposition.
    Author:
    Heinz Kredel
    See Also:
    Serialized Form

    • Constructor Detail

      • Ideal

        public Ideal​(GenPolynomialRing<C> ring,
             java.util.List<GenPolynomial<C>> F,
             boolean gb)
        Constructor.
        Parameters:
        ring - polynomial ring
        F - list of polynomials
        gb - true if F is known to be a Groebner Base, else false

      • Ideal

        public Ideal​(GenPolynomialRing<C> ring,
             java.util.List<GenPolynomial<C>> F,
             boolean gb,
             boolean topt)
        Constructor.
        Parameters:
        ring - polynomial ring
        F - list of polynomials
        gb - true if F is known to be a Groebner Base, else false
        topt - true if term order is optimized, else false

      • Ideal

        public Ideal​(PolynomialList<C> list,
             boolean gb)
        Constructor.
        Parameters:
        list - polynomial list
        gb - true if list is known to be a Groebner Base, else false

      • Ideal

        public Ideal​(PolynomialList<C> list,
             boolean gb,
             boolean topt)
        Constructor.
        Parameters:
        list - polynomial list
        gb - true if list is known to be a Groebner Base, else false
        topt - true if term order is optimized, else false

      • Ideal

        public Ideal​(PolynomialList<C> list,
             boolean gb,
             GroebnerBaseAbstract<C> bb,
             Reduction<C> red)
        Constructor.
        Parameters:
        list - polynomial list
        gb - true if list is known to be a Groebner Base, else false
        bb - Groebner Base engine
        red - Reduction engine

      • Ideal

        public Ideal​(PolynomialList<C> list,
             boolean gb,
             GroebnerBaseAbstract<C> bb)
        Constructor.
        Parameters:
        list - polynomial list
        gb - true if list is known to be a Groebner Base, else false
        bb - Groebner Base engine

      • Ideal

        public Ideal​(PolynomialList<C> list,
             boolean gb,
             boolean topt,
             GroebnerBaseAbstract<C> bb)
        Constructor.
        Parameters:
        list - polynomial list
        gb - true if list is known to be a Groebner Base, else false
        topt - true if term order is optimized, else false
        bb - Groebner Base engine

      • Ideal

        public Ideal​(PolynomialList<C> list,
             boolean gb,
             boolean topt,
             GroebnerBaseAbstract<C> bb,
             Reduction<C> red)
        Constructor.
        Parameters:
        list - polynomial list
        gb - true if list is known to be a Groebner Base, else false
        topt - true if term order is optimized, else false
        bb - Groebner Base engine
        red - Reduction engine

    • Method Detail

      • copy

        public Ideal<C> copy()
        Clone this.
        Returns:
        a copy of this.

      • getList

        public java.util.List<GenPolynomial<C>> getList()
        Get the List of GenPolynomials.
        Returns:
        list.list

      • getZERO

        public Ideal<C> getZERO()
        Get the zero ideal.
        Returns:
        ideal(0)

      • getONE

        public Ideal<C> getONE()
        Get the one ideal.
        Returns:
        ideal(1)

      • toString

        public java.lang.String toString()
        String representation of the ideal.
        Overrides:
        toString in class java.lang.Object
        See Also:
        Object.toString()

      • toScript

        public java.lang.String toScript()
        Get a scripting compatible string representation.
        Returns:
        script compatible representation for this Element.
        See Also:
        Element.toScript()

      • equals

        public boolean equals​(java.lang.Object b)
        Comparison with any other object. Note: If both ideals are not Groebner Bases, then false may be returned even the ideals are equal.
        Overrides:
        equals in class java.lang.Object
        See Also:
        Object.equals(java.lang.Object)

      • compareTo

        public int compareTo​(Ideal<C> L)
        Ideal list comparison.
        Specified by:
        compareTo in interface java.lang.Comparable<C extends GcdRingElem<C>>
        Parameters:
        L - other Ideal.
        Returns:
        compareTo() of polynomial lists.

      • hashCode

        public int hashCode()
        Hash code for this ideal.
        Overrides:
        hashCode in class java.lang.Object
        See Also:
        Object.hashCode()

      • isZERO

        public boolean isZERO()
        Test if ZERO ideal.
        Returns:
        true, if this is the 0 ideal, else false

      • isONE

        public boolean isONE()
        Test if ONE is contained in the ideal. To test for a proper ideal use ! id.isONE().
        Returns:
        true, if this is the 1 ideal, else false

      • doToptimize

        public void doToptimize()
        Optimize the term order.

      • isGB

        public boolean isGB()
        Test if this is a Groebner base.
        Returns:
        true, if this is a Groebner base, else false

      • doGB

        public void doGB()
        Do Groebner Base. compute the Groebner Base for this ideal.

      • GB

        public Ideal<C> GB()
        Groebner Base. Get a Groebner Base for this ideal.
        Returns:
        GB(this)

      • contains

        public boolean contains​(Ideal<C> B)
        Ideal containment. Test if B is contained in this ideal. Note: this is eventually modified to become a Groebner Base.
        Parameters:
        B - ideal
        Returns:
        true, if B is contained in this, else false

      • contains

        public boolean contains​(GenPolynomial<C> b)
        Ideal containment. Test if b is contained in this ideal. Note: this is eventually modified to become a Groebner Base.
        Parameters:
        b - polynomial
        Returns:
        true, if b is contained in this, else false

      • contains

        public boolean contains​(java.util.List<GenPolynomial<C>> B)
        Ideal containment. Test if each b in B is contained in this ideal. Note: this is eventually modified to become a Groebner Base.
        Parameters:
        B - list of polynomials
        Returns:
        true, if each b in B is contained in this, else false

      • sum

        public Ideal<C> sum​(Ideal<C> B)
        Summation. Generators for the sum of ideals. Note: if both ideals are Groebner bases, a Groebner base is returned.
        Parameters:
        B - ideal
        Returns:
        ideal(this+B)

      • sum

        public Ideal<C> sum​(GenPolynomial<C> b)
        Summation. Generators for the sum of ideal and a polynomial. Note: if this ideal is a Groebner base, a Groebner base is returned.
        Parameters:
        b - polynomial
        Returns:
        ideal(this+{b})

      • sum

        public Ideal<C> sum​(java.util.List<GenPolynomial<C>> L)
        Summation. Generators for the sum of this ideal and a list of polynomials. Note: if this ideal is a Groebner base, a Groebner base is returned.
        Parameters:
        L - list of polynomials
        Returns:
        ideal(this+L)

      • product

        public Ideal<C> product​(Ideal<C> B)
        Product. Generators for the product of ideals. Note: if both ideals are Groebner bases, a Groebner base is returned.
        Parameters:
        B - ideal
        Returns:
        ideal(this*B)

      • product

        public Ideal<C> product​(GenPolynomial<C> b)
        Product. Generators for the product this ideal by a polynomial. Note: if this ideal is a Groebner base, a Groebner base is returned.
        Parameters:
        b - polynomial
        Returns:
        ideal(this*b)

      • intersect

        public Ideal<C> intersect​(java.util.List<Ideal<C>> Bl)
        Intersection. Generators for the intersection of ideals. Using an iterative algorithm.
        Parameters:
        Bl - list of ideals
        Returns:
        ideal(cap_i B_i), a Groebner base

      • intersect

        public Ideal<C> intersect​(Ideal<C> B)
        Intersection. Generators for the intersection of ideals.
        Parameters:
        B - ideal
        Returns:
        ideal(this \cap B), a Groebner base

      • intersect

        public Ideal<C> intersect​(GenPolynomialRing<C> R)
        Intersection. Generators for the intersection of a ideal with a polynomial ring. The polynomial ring of this ideal must be a contraction of R and the TermOrder must be an elimination order.
        Parameters:
        R - polynomial ring
        Returns:
        ideal(this \cap R)

      • eliminate

        public Ideal<C> eliminate​(GenPolynomialRing<C> R)
        Eliminate. Generators for the intersection of a ideal with a polynomial ring. The polynomial rings must have variable names.
        Parameters:
        R - polynomial ring
        Returns:
        ideal(this \cap R)

      • eliminate

        public Ideal<C> eliminate​(java.lang.String... ename)
        Eliminate. Preparation of generators for the intersection of a ideal with a polynomial ring.
        Parameters:
        ename - variables for the elimination ring.
        Returns:
        ideal(this) in K[ename,{vars \ ename}])

      • quotient

        public Ideal<C> quotient​(GenPolynomial<C> h)
        Quotient. Generators for the ideal quotient.
        Parameters:
        h - polynomial
        Returns:
        ideal(this : h), a Groebner base

      • quotient

        public Ideal<C> quotient​(Ideal<C> H)
        Quotient. Generators for the ideal quotient.
        Parameters:
        H - ideal
        Returns:
        ideal(this : H), a Groebner base

      • infiniteQuotientRab

        public Ideal<C> infiniteQuotientRab​(GenPolynomial<C> h)
        Infinite quotient. Generators for the infinite ideal quotient.
        Parameters:
        h - polynomial
        Returns:
        ideal(this : hs), a Groebner base

      • infiniteQuotient

        public Ideal<C> infiniteQuotient​(GenPolynomial<C> h)
        Infinite quotient. Generators for the infinite ideal quotient.
        Parameters:
        h - polynomial
        Returns:
        ideal(this : hs), a Groebner base

      • isRadicalMember

        public boolean isRadicalMember​(GenPolynomial<C> h)
        Radical membership test.
        Parameters:
        h - polynomial
        Returns:
        true if h is contained in the radical of ideal(this), else false.

      • infiniteQuotientOld

        public Ideal<C> infiniteQuotientOld​(GenPolynomial<C> h)
        Infinite quotient. Generators for the infinite ideal quotient.
        Parameters:
        h - polynomial
        Returns:
        ideal(this : hs), a Groebner base

      • infiniteQuotient

        public Ideal<C> infiniteQuotient​(Ideal<C> H)
        Infinite Quotient. Generators for the ideal infinite quotient.
        Parameters:
        H - ideal
        Returns:
        ideal(this : Hs), a Groebner base

      • infiniteQuotientRab

        public Ideal<C> infiniteQuotientRab​(Ideal<C> H)
        Infinite Quotient. Generators for the ideal infinite quotient.
        Parameters:
        H - ideal
        Returns:
        ideal(this : Hs), a Groebner base

      • power

        public Ideal<C> power​(int d)
        Power. Generators for the power of this ideal. Note: if this ideal is a Groebner base, a Groebner base is returned.
        Parameters:
        d - integer
        Returns:
        ideal(this^d)

      • normalform

        public java.util.List<GenPolynomial<C>> normalform​(java.util.List<GenPolynomial<C>> L)
        Normalform for list of elements.
        Parameters:
        L - polynomial list
        Returns:
        list of normalforms of the elements of L with respect to this

      • annihilator

        public Ideal<C> annihilator​(GenPolynomial<C> h)
        Annihilator for element modulo this ideal.
        Parameters:
        h - polynomial
        Returns:
        annihilator of h with respect to this

      • isAnnihilator

        public boolean isAnnihilator​(GenPolynomial<C> h,
                             Ideal<C> A)
        Test for annihilator of element modulo this ideal.
        Parameters:
        h - polynomial
        A - ideal
        Returns:
        true, if A is the annihilator of h with respect to this

      • annihilator

        public Ideal<C> annihilator​(Ideal<C> H)
        Annihilator for ideal modulo this ideal.
        Parameters:
        H - ideal
        Returns:
        annihilator of H with respect to this

      • isAnnihilator

        public boolean isAnnihilator​(Ideal<C> H,
                             Ideal<C> A)
        Test for annihilator of ideal modulo this ideal.
        Parameters:
        H - ideal
        A - ideal
        Returns:
        true, if A is the annihilator of H with respect to this

      • inverse

        public GenPolynomial<C> inverse​(GenPolynomial<C> h)
        Inverse for element modulo this ideal.
        Parameters:
        h - polynomial
        Returns:
        inverse of h with respect to this, if defined

      • isUnit

        public boolean isUnit​(GenPolynomial<C> h)
        Test if element is a unit modulo this ideal.
        Parameters:
        h - polynomial
        Returns:
        true if h is a unit with respect to this, else false

      • squarefree

        public Ideal<C> squarefree()
        Radical approximation. Squarefree generators for the ideal.
        Returns:
        squarefree(this), a Groebner base

      • commonZeroTest

        public int commonZeroTest()
        Ideal common zero test.
        Returns:
        -1, 0 or 1 if dimension(this) &eq; -1, 0 or ≥ 1.

      • isMaximal

        public boolean isMaximal()
        Test if this ideal is maximal.
        Returns:
        true, if this is certainly maximal and not one, else false.

      • univariateDegrees

        public java.util.List<java.lang.Long> univariateDegrees()
        Univariate head term degrees.
        Returns:
        a list of the degrees of univariate head terms.

      • dimension

        public Dimension dimension()
        Ideal dimension.
        Returns:
        a dimension container (dim,maxIndep,list(maxIndep),vars).

      • dimension

        protected java.util.Set<java.util.Set<java.lang.Integer>> dimension​(java.util.Set<java.lang.Integer> S,
                                                                    java.util.Set<java.lang.Integer> U,
                                                                    java.util.Set<java.util.Set<java.lang.Integer>> M)
        Ideal dimension.
        Parameters:
        S - is a set of independent variables.
        U - is a set of variables of unknown status.
        M - is a list of maximal sets of independent variables.
        Returns:
        a list of maximal sets of independent variables, eventually containing S.

      • containsHT

        protected boolean containsHT​(java.util.Set<java.lang.Integer> H,
                             java.util.List<GenPolynomial<C>> G)
        Ideal head term containment test.
        Parameters:
        G - list of polynomials.
        H - index set.
        Returns:
        true, if the variables of the head terms of each polynomial in G are contained in H, else false.

      • contains

        protected boolean contains​(int[] v,
                           java.util.Set<java.lang.Integer> H)
        Set containment. is v \subset H.
        Parameters:
        v - index array.
        H - index set.
        Returns:
        true, if each element of v is contained in H, else false .

      • constructUnivariate

        public java.util.List<GenPolynomial<C>> constructUnivariate()
        Construct univariate polynomials of minimal degree in all variables in zero dimensional ideal(G).
        Returns:
        list of univariate polynomial of minimal degree in each variable in ideal(G)

      • constructUnivariate

        public GenPolynomial<C> constructUnivariate​(int i)
        Construct univariate polynomial of minimal degree in variable i in zero dimensional ideal(G).
        Parameters:
        i - variable index.
        Returns:
        univariate polynomial of minimal degree in variable i in ideal(G)

      • zeroDimRadicalDecomposition

        public java.util.List<IdealWithUniv<C>> zeroDimRadicalDecomposition()
        Zero dimensional radical decomposition. See Seidenbergs lemma 92, and BWK lemma 8.13.
        Returns:
        intersection of radical ideals G_i with ideal(this) subseteq cap_i( ideal(G_i) )

      • isZeroDimRadical

        public boolean isZeroDimRadical()
        Test for Zero dimensional radical. See Seidenbergs lemma 92, and BWK lemma 8.13.
        Returns:
        true if this is an zero dimensional radical ideal, else false

      • isRadical

        public boolean isRadical​(IdealWithUniv<C> ru)
        Test for radical ideal.
        Parameters:
        ru - ideal with univariate polynomials
        Returns:
        true if ru is a radical ideal, else false

      • zeroDimDecomposition

        public java.util.List<IdealWithUniv<C>> zeroDimDecomposition()
        Zero dimensional ideal irreducible decomposition. See algorithm DIRGZD of BGK 1986 and also PREDEC of the Gröbner bases book 1993.
        Returns:
        intersection H, of ideals G_i with ideal(this) subseteq cap_i( ideal(G_i) ) and each ideal G_i has only irreducible minimal univariate polynomials and the G_i are pairwise co-prime.

      • zeroDimDecompositionExtension

        public java.util.List<IdealWithUniv<C>> zeroDimDecompositionExtension​(java.util.List<GenPolynomial<C>> upol,
                                                                      java.util.List<GenPolynomial<C>> og)
        Zero dimensional ideal irreducible decomposition extension. One step decomposition via a minimal univariate polynomial in the lowest variable, used after each normalPosition step.
        Parameters:
        upol - list of univariate polynomials
        og - list of other generators for the ideal
        Returns:
        intersection of ideals G_i with ideal(this) subseteq cap_i( ideal(G_i) ) and all minimal univariate polynomials of all G_i are irreducible

      • isZeroDimDecomposition

        public boolean isZeroDimDecomposition​(java.util.List<IdealWithUniv<C>> L)
        Test for zero dimensional ideal decomposition.
        Parameters:
        L - intersection of ideals G_i with ideal(G) subseteq cap_i( ideal(G_i) ) and all minimal univariate polynomials of all G_i are irreducible
        Returns:
        true if L is a zero dimensional irreducible decomposition of this, else false

      • normalPositionFor

        public IdealWithUniv<C> normalPositionFor​(int i,
                                          int j,
                                          java.util.List<GenPolynomial<C>> og)
        Compute normal position for variables i and j.
        Parameters:
        i - first variable index
        j - second variable index
        og - other generators for the ideal
        Returns:
        this + (z - x_j - t x_i) in the ring C[z, x_1, ..., x_r]

      • isNormalPositionFor

        public boolean isNormalPositionFor​(int i,
                                   int j)
        Test if this ideal is in normal position for variables i and j.
        Parameters:
        i - first variable index
        j - second variable index
        Returns:
        true if this is in normal position with respect to i and j

      • zeroDimRootDecomposition

        public java.util.List<IdealWithUniv<C>> zeroDimRootDecomposition()
        Zero dimensional ideal decomposition for real roots. See algorithm mas.masring.DIPDEC0#DINTSR.
        Returns:
        intersection of ideals G_i with ideal(this) subseteq cap_i( ideal(G_i) ) and each G_i contains at most bi-variate polynomials and all univariate minimal polynomials are irreducible

      • zeroDimPrimeDecomposition

        public java.util.List<IdealWithUniv<C>> zeroDimPrimeDecomposition()
        Zero dimensional ideal prime decomposition. See algorithm mas.masring.DIPDEC0#DINTSS.
        Returns:
        intersection of ideals G_i with ideal(this) subseteq cap_i( ideal(G_i) ) and each G_i is a prime ideal

      • zeroDimPrimeDecompositionFE

        public java.util.List<IdealWithUniv<C>> zeroDimPrimeDecompositionFE()
        Zero dimensional ideal prime decomposition, with field extension. See algorithm mas.masring.DIPDEC0#DINTSS.
        Returns:
        intersection of ideals G_i with ideal(this) subseteq cap_i( ideal(G_i) ) and each G_i is a prime ideal with eventually containing field extension variables

      • primaryIdeal

        public Ideal<C> primaryIdeal​(Ideal<C> P)
        Zero dimensional ideal associated primary ideal. See algorithm mas.masring.DIPIDEAL#DIRLPI.
        Parameters:
        P - prime ideal associated to this
        Returns:
        primary ideal of this with respect to the associated pime ideal P

      • zeroDimPrimaryDecomposition

        public java.util.List<PrimaryComponent<C>> zeroDimPrimaryDecomposition()
        Zero dimensional ideal primary decomposition.
        Returns:
        list of primary components of primary ideals G_i (pairwise co-prime) with ideal(this) = cap_i( ideal(G_i) ) together with the associated primes

      • zeroDimElimination

        public java.util.List<IdealWithUniv<C>> zeroDimElimination​(java.util.List<IdealWithUniv<C>> pdec)
        Zero dimensional ideal elimination to original ring.
        Parameters:
        pdec - list of prime ideals G_i
        Returns:
        intersection of pairwise co-prime prime ideals G_i in the ring of this with ideal(this) = cap_i( ideal(G_i) )

      • zeroDimPrimaryDecomposition

        public java.util.List<PrimaryComponent<C>> zeroDimPrimaryDecomposition​(java.util.List<IdealWithUniv<C>> pdec)
        Zero dimensional ideal primary decomposition.
        Parameters:
        pdec - list of prime ideals G_i with no field extensions
        Returns:
        list of primary components of primary ideals G_i (pairwise co-prime) with ideal(this) = cap_i( ideal(G_i) ) together with the associated primes

      • isPrimaryDecomposition

        public boolean isPrimaryDecomposition​(java.util.List<PrimaryComponent<C>> L)
        Test for primary ideal decomposition.
        Parameters:
        L - list of primary components G_i
        Returns:
        true if ideal(this) == cap_i( ideal(G_i) )

      • extension

        public IdealWithUniv<Quotient<C>> extension​(java.lang.String... vars)
        Ideal extension.
        Parameters:
        vars - list of variables for a polynomial ring for extension
        Returns:
        ideal G, with coefficients in QuotientRing(GenPolynomialRing (vars))

      • radical

        public Ideal<C> radical()
        Ideal radical.
        Returns:
        the radical ideal of this

      • radicalDecomposition

        public java.util.List<IdealWithUniv<C>> radicalDecomposition()
        Ideal radical decomposition.
        Returns:
        intersection of ideals G_i with radical(this) eq cap_i( ideal(G_i) ) and each G_i is a radical ideal and the G_i are pairwise co-prime

      • decomposition

        public java.util.List<IdealWithUniv<C>> decomposition()
        Ideal irreducible decomposition.
        Returns:
        intersection of ideals G_i with ideal(this) subseteq cap_i( ideal(G_i) ) and each G_i is an ideal with irreducible univariate polynomials (after extension to a zero dimensional ideal) and the G_i are pairwise co-prime

      • primeDecomposition

        public java.util.List<IdealWithUniv<C>> primeDecomposition()
        Ideal prime decomposition.
        Returns:
        intersection of ideals G_i with ideal(this) subseteq cap_i( ideal(G_i) ) and each G_i is a prime ideal and the G_i are pairwise co-prime

      • isDecomposition

        public boolean isDecomposition​(java.util.List<IdealWithUniv<C>> L)
        Test for ideal decomposition.
        Parameters:
        L - intersection of ideals G_i with ideal(G) eq cap_i(ideal(G_i) )
        Returns:
        true if L is a decomposition of this, else false

      • primaryDecomposition

        public java.util.List<PrimaryComponent<C>> primaryDecomposition()
        Ideal primary decomposition.
        Returns:
        list of primary components of primary ideals G_i (pairwise co-prime) with ideal(this) = cap_i( ideal(G_i) ) together with the associated primes