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<Ccopy()
        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<CgetZERO()
        Get the zero ideal.
        Returns:
        ideal(0)
      • getONE

        public Ideal<CgetONE()
        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<CGB()
        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<Csum​(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<Csum​(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<Csum​(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<Cproduct​(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<Cproduct​(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<Cintersect​(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<Cintersect​(Ideal<C> B)
        Intersection. Generators for the intersection of ideals.
        Parameters:
        B - ideal
        Returns:
        ideal(this \cap B), a Groebner base
      • intersect

        public Ideal<Cintersect​(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<Celiminate​(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<Celiminate​(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<Cquotient​(GenPolynomial<C> h)
        Quotient. Generators for the ideal quotient.
        Parameters:
        h - polynomial
        Returns:
        ideal(this : h), a Groebner base
      • quotient

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

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

        public Ideal<CinfiniteQuotient​(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<CinfiniteQuotientOld​(GenPolynomial<C> h)
        Infinite quotient. Generators for the infinite ideal quotient.
        Parameters:
        h - polynomial
        Returns:
        ideal(this : hs), a Groebner base
      • infiniteQuotient

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

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

        public Ideal<Cpower​(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<Cannihilator​(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<Cannihilator​(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<Cinverse​(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<Csquarefree()
        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<CconstructUnivariate​(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<CnormalPositionFor​(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<CprimaryIdeal​(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<Cradical()
        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