groebner

package
v0.8.0 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Jul 19, 2026 License: MIT Imports: 7 Imported by: 0

Documentation

Overview

Package groebner implements exact computer algebra over sparse multivariate polynomials with rational coefficients (math/big.Rat).

The package provides a full toolkit for ideal theory in the polynomial ring Q[x_1, ..., x_n]: monomials as integer exponent vectors, configurable monomial orders (lexicographic, graded lexicographic, graded reverse lexicographic, weighted and block/elimination orders), polynomial arithmetic (addition, subtraction, multiplication, powers, scalar and monomial multiplication), evaluation over the rationals and over the complex numbers, formal derivatives, multivariate division with remainder, S-polynomials, and Buchberger's algorithm (with the coprime-leading-term and chain criteria) for computing Gröbner bases.

On top of Gröbner bases the package computes reduced and minimal Gröbner bases, decides ideal membership, and performs the standard ideal operations: sum, product, intersection, quotient (colon ideal), and elimination ideals. For zero-dimensional systems it can decide finiteness of the variety and numerically approximate all complex solutions by triangular back-solving combined with a self-contained Durand–Kerner univariate root finder.

All arithmetic on coefficients is exact. Only the numerical variety solver works with floating point (complex128) and it takes a caller-supplied random seed so results are reproducible.

Index

Examples

Constants

This section is empty.

Variables

View Source 
var ErrNotZeroDimensional = errors.New("groebner: system is not zero-dimensional")

ErrNotZeroDimensional is returned by the variety solver when the ideal has infinitely many solutions (positive-dimensional) and cannot be solved by finite back-substitution.

Functions

func CloneRat 

func CloneRat(r *big.Rat) *big.Rat

CloneRat returns an independent copy of r.

func CompareGrevlex 

func CompareGrevlex(a, b Monomial) int

CompareGrevlex compares two monomials by the graded reverse lexicographic order: first by total degree, breaking ties by the reverse lexicographic rule (the monomial with the smaller exponent in the last variable where they differ is greater).

func CompareGrlex 

func CompareGrlex(a, b Monomial) int

CompareGrlex compares two monomials by the graded lexicographic order: first by total degree, breaking ties with the lexicographic order.

func CompareLex 

func CompareLex(a, b Monomial) int

CompareLex compares two monomials by the lexicographic order: the monomial with the larger exponent in the first variable where they differ is greater.

func Divides 

func Divides(g, f Poly, o Order) bool

Divides reports whether g divides f exactly (the remainder of f divided by g is zero) with respect to the order o.

func InIdeal 

func InIdeal(f Poly, gens []Poly, o Order) bool

InIdeal reports whether f belongs to the ideal generated by gens, by checking that its normal form modulo a Gröbner basis is zero.

Example 
x := Var(2, 0)
y := Var(2, 1)
gens := []Poly{x.Mul(x).Sub(y), x.Mul(y).Sub(x)}
// x^2*y - y^2 = y*(x^2 - y) is in the ideal.
f := x.Mul(x).Mul(y).Sub(y.Mul(y))
fmt.Println(InIdeal(f, gens, GrevlexOrder()))

Output:
true

func IsGroebnerBasis 

func IsGroebnerBasis(g []Poly, o Order) bool

IsGroebnerBasis reports whether the set g is a Gröbner basis with respect to o, by verifying that every S-polynomial reduces to zero modulo g (Buchberger's criterion).

func IsReducible 

func IsReducible(f Poly, divisors []Poly, o Order) bool

IsReducible reports whether some monomial of f is divisible by the leading monomial of one of the divisors, i.e. whether a division step is possible.

func MonomialLess 

func MonomialLess(o Order, a, b Monomial) bool

MonomialLess reports whether a is strictly smaller than b under the order o.

func NewRat 

func NewRat(a, b int64) *big.Rat

NewRat returns the rational number a/b as a *big.Rat. It panics only if b is zero, matching the behaviour of big.NewRat.

func RatFromInt 

func RatFromInt(a int64) *big.Rat

RatFromInt returns the integer a as a *big.Rat.

func RatFromString 

func RatFromString(s string) (*big.Rat, bool)

RatFromString parses a rational number from its decimal or fractional string representation (for example "3/4", "-2", or "1.5"). The boolean result is false when the string cannot be parsed.

func RatIsOne 

func RatIsOne(r *big.Rat) bool

RatIsOne reports whether the rational r equals 1.

func RatIsZero 

func RatIsZero(r *big.Rat) bool

RatIsZero reports whether the rational r is zero.

func RatToFloat 

func RatToFloat(r *big.Rat) float64

RatToFloat returns the nearest float64 to the rational r.

func RealSolutions 

func RealSolutions(sols [][]complex128, imagTol float64) [][]float64

RealSolutions filters a set of complex solutions, returning the real parts of those solutions whose imaginary parts are all below the tolerance imagTol.

func SolveUnivariate 

func SolveUnivariate(coeffs []complex128, seed int64) []complex128

SolveUnivariate returns the complex roots of a univariate polynomial given by its coefficient slice, where coeffs[k] is the coefficient of x^k. It uses the Durand–Kerner (Weierstrass) iteration seeded by the supplied random seed so results are reproducible. Trailing (high-degree) near-zero coefficients are dropped. A constant nonzero polynomial has no roots; the zero polynomial returns no roots as well.

func SolveZeroDimensional 

func SolveZeroDimensional(gens []Poly, seed int64, tol float64) ([][]complex128, error)

SolveZeroDimensional numerically approximates all complex solutions of the zero-dimensional system defined by gens. It computes a lexicographic Gröbner basis (which for a zero-dimensional ideal has triangular shape), solves the univariate polynomial in the last variable, and back-substitutes recursively. Candidate tuples are verified against every generator within the given tolerance. The seed makes the underlying root finder reproducible. It returns ErrNotZeroDimensional if the system has infinitely many solutions and the unit ideal (no solutions) yields an empty slice.

Types

type DivisionResult 

type DivisionResult struct {
	Quotients []Poly
	Remainder Poly
}

DivisionResult holds the outcome of multivariate division of a dividend by an ordered list of divisors: the quotient polynomials (one per divisor) and the remainder.

func MultivariateDivide 

func MultivariateDivide(f Poly, divisors []Poly, o Order) DivisionResult

MultivariateDivide performs the multivariate division algorithm, dividing f by the ordered list of divisors with respect to the monomial order o. It returns quotients q_i and a remainder r such that 

f = q_1*g_1 + ... + q_s*g_s + r,

where no monomial of r is divisible by the leading monomial of any divisor. The result depends on the order of the divisors. Zero divisors are skipped.

type Ideal 

type Ideal struct {
	// contains filtered or unexported fields
}

Ideal represents a polynomial ideal by a list of generators in a fixed number of variables together with a default monomial order used by its methods.

func NewIdeal 

func NewIdeal(o Order, gens ...Poly) Ideal

NewIdeal builds the ideal generated by gens with the given default monomial order. The number of variables is taken from the first generator; if gens is empty the ideal is the zero ideal in zero variables (callers usually supply at least one generator).

func NewIdealN 

func NewIdealN(n int, o Order, gens ...Poly) Ideal

NewIdealN builds the ideal generated by gens in n variables with order o, allowing an explicit variable count (needed for the zero ideal).

func (Ideal) Contains 

func (id Ideal) Contains(f Poly) bool

Contains reports whether the polynomial f is a member of the ideal.

func (Ideal) Eliminate 

func (id Ideal) Eliminate(k int) Ideal

Eliminate returns the elimination ideal obtained by eliminating the first k variables, i.e. I ∩ Q[x_{k+1}, ..., x_n], still embedded in the original ring (the eliminated variables simply do not occur). It uses an elimination order.

func (Ideal) Equal 

func (id Ideal) Equal(other Ideal) bool

Equal reports whether two ideals are equal, by comparing their reduced Gröbner bases under a common order (the receiver's order).

func (Ideal) Generators 

func (id Ideal) Generators() []Poly

Generators returns a copy of the ideal's generating set.

func (Ideal) GroebnerBasis 

func (id Ideal) GroebnerBasis() []Poly

GroebnerBasis returns a (reduced) Gröbner basis of the ideal with respect to its default order.

func (Ideal) Intersect 

func (id Ideal) Intersect(other Ideal) Ideal

Intersect returns the ideal intersection I ∩ J. It uses the standard elimination construction: in a ring with one extra variable t it forms the ideal generated by t*f_i and (1-t)*g_j and eliminates t.

func (Ideal) IsUnit 

func (id Ideal) IsUnit() bool

IsUnit reports whether the ideal is the whole ring, i.e. it contains the constant 1 (equivalently its reduced Gröbner basis is {1}).

func (Ideal) IsZero 

func (id Ideal) IsZero() bool

IsZero reports whether the ideal is the zero ideal.

func (Ideal) IsZeroDimensional 

func (id Ideal) IsZeroDimensional() bool

IsZeroDimensional reports whether the ideal is zero-dimensional, i.e. the quotient ring is a finite-dimensional vector space over Q, equivalently the variety over the algebraic closure is finite. It checks that for every variable some leading monomial of the reduced Gröbner basis is a pure power of that variable. The unit ideal (empty variety) is considered zero-dimensional.

func (Ideal) Nvars 

func (id Ideal) Nvars() int

Nvars returns the number of variables of the ambient ring.

func (Ideal) Order 

func (id Ideal) Order() Order

Order returns the ideal's default monomial order.

func (Ideal) Product 

func (id Ideal) Product(other Ideal) Ideal

Product returns the ideal product I*J, generated by all pairwise products of generators. It uses the receiver's order.

func (Ideal) Quotient 

func (id Ideal) Quotient(other Ideal) Ideal

Quotient returns the ideal quotient (colon ideal) I : J = { f : f*J ⊆ I }. It is computed as the intersection over the generators g of J of the single quotients I : (g).

func (Ideal) QuotientBasis 

func (id Ideal) QuotientBasis() ([]Monomial, bool)

QuotientBasis returns a monomial basis of the quotient ring Q[x]/I as a Q-vector space, valid when the ideal is zero-dimensional. These are exactly the standard monomials: the monomials not divisible by any leading monomial of the Gröbner basis. The boolean result is false when the ideal is not zero-dimensional.

func (Ideal) QuotientElem 

func (id Ideal) QuotientElem(h Poly) Ideal

QuotientElem returns the ideal quotient I : (h) for a single polynomial h, using the identity h*(I:h) = I ∩ (h): it intersects I with the principal ideal (h) and divides each resulting generator by h.

func (Ideal) ReducedGroebnerBasis 

func (id Ideal) ReducedGroebnerBasis() []Poly

ReducedGroebnerBasis returns the canonical reduced Gröbner basis of the ideal.

func (Ideal) Solve 

func (id Ideal) Solve(seed int64, tol float64) ([][]complex128, error)

Solve numerically approximates all complex solutions of the ideal's variety, assuming the ideal is zero-dimensional. It is a convenience wrapper around SolveZeroDimensional using the ideal's generators.

func (Ideal) Sum 

func (id Ideal) Sum(other Ideal) Ideal

Sum returns the ideal sum I + J, generated by the union of the two generating sets. It uses the receiver's order.

func (Ideal) VectorSpaceDimension 

func (id Ideal) VectorSpaceDimension() (int, bool)

VectorSpaceDimension returns the dimension of Q[x]/I as a Q-vector space for a zero-dimensional ideal, equal to the number of solutions counted with multiplicity over the algebraic closure. The boolean result is false when the ideal is not zero-dimensional.

func (Ideal) WithOrder 

func (id Ideal) WithOrder(o Order) Ideal

WithOrder returns a copy of the ideal using a different default monomial order.

type Monomial 

type Monomial []int

Monomial represents a power product x_1^e_1 * ... * x_n^e_n as its vector of non-negative integer exponents. The length of the slice is the number of variables in the ambient polynomial ring.

func MonomialMax 

func MonomialMax(o Order, a, b Monomial) Monomial

MonomialMax returns whichever of a and b is larger under the order o.

func NewMonomial 

func NewMonomial(exps ...int) Monomial

NewMonomial returns a copy of the given exponent vector as a Monomial. The input is not retained.

func VarMonomial 

func VarMonomial(n, i int) Monomial

VarMonomial returns the monomial x_i (the i-th variable to the first power) in a ring with n variables. It panics only if i is out of range.

func ZeroMonomial 

func ZeroMonomial(n int) Monomial

ZeroMonomial returns the constant monomial 1 in n variables, i.e. the vector of n zero exponents.

func (Monomial) Clone 

func (m Monomial) Clone() Monomial

Clone returns an independent copy of the monomial.

func (Monomial) Coprime 

func (m Monomial) Coprime(o Monomial) bool

Coprime reports whether two monomials have disjoint support, i.e. their GCD is 1. This is the condition used by Buchberger's first (coprime) criterion.

func (Monomial) Degree 

func (m Monomial) Degree() int

Degree returns the total degree of the monomial, the sum of its exponents.

func (Monomial) Div 

func (m Monomial) Div(o Monomial) (Monomial, bool)

Div returns the quotient o/m when m divides o. The boolean result is false (and the returned monomial nil) when the division is not exact.

func (Monomial) Divides 

func (m Monomial) Divides(o Monomial) bool

Divides reports whether m divides o, i.e. every exponent of m is at most the corresponding exponent of o.

func (Monomial) Equal 

func (m Monomial) Equal(o Monomial) bool

Equal reports whether two monomials have identical exponent vectors.

func (Monomial) Exp 

func (m Monomial) Exp(i int) int

Exp returns the exponent of the i-th variable.

func (Monomial) Format 

func (m Monomial) Format(vars []string) string

Format renders the monomial using the supplied variable names. The constant monomial is rendered as "1".

func (Monomial) GCD 

func (m Monomial) GCD(o Monomial) Monomial

GCD returns the greatest common divisor of two monomials, taking the componentwise minimum of the exponents.

func (Monomial) IsConstant 

func (m Monomial) IsConstant() bool

IsConstant reports whether the monomial equals 1, i.e. every exponent is zero.

func (Monomial) LCM 

func (m Monomial) LCM(o Monomial) Monomial

LCM returns the least common multiple of two monomials, taking the componentwise maximum of the exponents.

func (Monomial) Max 

func (m Monomial) Max(o Monomial) Monomial

Max returns the componentwise maximum of two monomials (identical to LCM); it is provided as a descriptive name for exponent-vector joins.

func (Monomial) Mul 

func (m Monomial) Mul(o Monomial) Monomial

Mul returns the product of two monomials, obtained by adding exponents componentwise.

func (Monomial) Nvars 

func (m Monomial) Nvars() int

Nvars returns the number of variables (the length of the exponent vector).

func (Monomial) Pow 

func (m Monomial) Pow(k int) Monomial

Pow returns the monomial raised to a non-negative integer power, multiplying every exponent by k.

func (Monomial) String 

func (m Monomial) String() string

String renders the monomial using the default variable names x1, x2, ....

func (Monomial) Support 

func (m Monomial) Support() []int

Support returns the sorted indices of variables that appear with a positive exponent in the monomial.

func (Monomial) TotalDegree 

func (m Monomial) TotalDegree() int

TotalDegree is an alias for Degree, the sum of all exponents.

type Order 

type Order func(a, b Monomial) int

Order is a monomial ordering: a function that compares two monomials and returns -1 if a < b, 0 if a == b, and +1 if a > b. A valid monomial order is a total order that is multiplicative and for which 1 is the smallest monomial. All monomials passed to an Order are assumed to have the same number of variables.

func BlockOrder 

func BlockOrder(sep int, first, second Order) Order

BlockOrder returns the product (block) order that compares the first sep variables using first and, on a tie, compares the remaining variables using second. Monomials involving any of the first sep variables are larger than those that do not, so BlockOrder eliminates the first sep variables.

func EliminationOrder 

func EliminationOrder(sep int) Order

EliminationOrder returns a monomial order suitable for eliminating the first sep variables from an ideal. It is a block order using graded reverse lexicographic within each block. The elements of a Gröbner basis with respect to this order that do not involve the first sep variables generate the corresponding elimination ideal.

func GrevlexOrder 

func GrevlexOrder() Order

GrevlexOrder is the graded reverse lexicographic monomial order, generally the most efficient order for Gröbner basis computation.

func GrlexOrder 

func GrlexOrder() Order

GrlexOrder is the graded lexicographic monomial order.

func LexOrder 

func LexOrder() Order

LexOrder is the lexicographic monomial order. It is an elimination order: the first variables dominate.

func ReverseOrder 

func ReverseOrder(o Order) Order

ReverseOrder returns the order obtained by reversing the given order. Note that the reverse of a monomial order is generally not itself a monomial order; this helper is intended for sorting and diagnostics.

func WeightOrder 

func WeightOrder(weights []int, tie Order) Order

WeightOrder returns a monomial order that first compares the dot product of the exponent vectors with the given non-negative integer weights, breaking ties with the supplied tie order. For a strictly positive weight vector any tie order yields a genuine monomial order.

type Poly 

type Poly struct {
	// contains filtered or unexported fields
}

Poly is a sparse multivariate polynomial with rational coefficients over a fixed number of variables. Internally the terms are kept in a canonical form: combined like terms, no zero coefficients, and sorted in descending lexicographic order of their monomials. This canonical form makes structural equality a simple term-by-term comparison; the leading term with respect to a particular monomial order is computed on demand.

func AddSlice 

func AddSlice(n int, ps []Poly) Poly

AddSlice returns the sum of a slice of polynomials in n variables.

func Buchberger 

func Buchberger(gens []Poly, o Order) []Poly

Buchberger computes a Gröbner basis of the ideal generated by gens with respect to the monomial order o, using Buchberger's algorithm with the coprime-leading-term criterion to discard trivial S-pairs. The returned basis is not necessarily reduced; use ReducedGroebnerBasis for the canonical form. Zero generators are ignored, and the empty generating set yields an empty basis.

func Constant 

func Constant(n int, c *big.Rat) Poly

Constant returns the constant polynomial equal to c in n variables.

func ConstantInt 

func ConstantInt(n int, c int64) Poly

ConstantInt returns the constant polynomial equal to the integer c.

func DivideOne 

func DivideOne(f, g Poly, o Order) (quotient, remainder Poly)

DivideOne divides f by a single polynomial g and returns the quotient and remainder with respect to o.

func EliminationIdeal 

func EliminationIdeal(gens []Poly, k int, o Order) []Poly

EliminationIdeal is the free-function form of Eliminate: it returns generators of the k-th elimination ideal of the given generators.

func ExactQuotient 

func ExactQuotient(f, g Poly, o Order) (Poly, bool)

ExactQuotient returns f/g when g divides f exactly. The boolean result is false when the division leaves a nonzero remainder.

func FromTerm 

func FromTerm(n int, t Term) Poly

FromTerm returns the one-term polynomial equal to t.

func GroebnerBasis 

func GroebnerBasis(gens []Poly, o Order) []Poly

GroebnerBasis is a convenience wrapper that returns the reduced Gröbner basis of the given generators with respect to o.

func MinimalGroebnerBasis 

func MinimalGroebnerBasis(g []Poly, o Order) []Poly

MinimalGroebnerBasis returns a minimal Gröbner basis obtained from g by making every element monic and discarding any element whose leading monomial is divisible by the leading monomial of another element.

func MonomialPoly 

func MonomialPoly(n int, m Monomial) Poly

Monomial returns the polynomial consisting of a single monomial m with coefficient 1.

func NewPoly 

func NewPoly(n int, terms ...Term) Poly

NewPoly builds a polynomial in n variables from the given terms, reducing it to canonical form. Terms with mismatched arity are padded or truncated to n variables.

func NormalForm 

func NormalForm(f Poly, g []Poly, o Order) Poly

NormalForm returns the normal form (unique remainder) of f modulo the ideal with Gröbner basis g under the order o. Two polynomials are congruent modulo the ideal if and only if they have the same normal form.

func One 

func One(n int) Poly

One returns the constant polynomial 1 in n variables.

func ReducedGroebnerBasis 

func ReducedGroebnerBasis(gens []Poly, o Order) []Poly

ReducedGroebnerBasis returns the unique reduced Gröbner basis of the ideal generated by gens with respect to o. Each element is monic and no monomial of any element is divisible by the leading monomial of any other. The basis is sorted in descending order of leading monomial, making it a canonical representative of the ideal.

Example 
// Compute the reduced Gröbner basis of <x^2 + y^2 - 1, x - y> under lex.
x := Var(2, 0)
y := Var(2, 1)
f := x.Mul(x).Add(y.Mul(y)).Sub(One(2))
g := x.Sub(y)
basis := ReducedGroebnerBasis([]Poly{f, g}, LexOrder())
for _, p := range basis {
	fmt.Println(p)
}

Output:
x1 - x2
x2^2 - 1/2

func Remainder 

func Remainder(f Poly, divisors []Poly, o Order) Poly

Remainder returns just the remainder of dividing f by the divisors with respect to o. It is the normal form of f modulo the divisor list.

func SPolynomial 

func SPolynomial(f, g Poly, o Order) Poly

SPolynomial returns the S-polynomial of f and g with respect to the order o: 

S(f,g) = (L/LT(f))*f - (L/LT(g))*g,

where L is the least common multiple of the leading monomials of f and g. The S-polynomial cancels the leading terms and is the central object of Buchberger's algorithm. It returns the zero polynomial if either input is zero.

func Var 

func Var(n, i int) Poly

Var returns the polynomial equal to the i-th variable x_i in n variables.

func Vars 

func Vars(n int) []Poly

Vars returns the polynomials x_1, ..., x_n in a ring with n variables.

func Zero 

func Zero(n int) Poly

Zero returns the zero polynomial in n variables.

func (Poly) Add 

func (p Poly) Add(o Poly) Poly

Add returns the sum of two polynomials.

func (Poly) Clone 

func (p Poly) Clone() Poly

Clone returns an independent deep copy of the polynomial.

func (Poly) Coeff 

func (p Poly) Coeff(m Monomial) *big.Rat

Coeff returns the coefficient of the monomial m in the polynomial, or 0 if it does not appear.

func (Poly) Coefficients 

func (p Poly) Coefficients() []*big.Rat

Coefficients returns the coefficients of the polynomial in canonical order.

func (Poly) ConstantTerm 

func (p Poly) ConstantTerm() *big.Rat

ConstantTerm returns the constant coefficient of the polynomial.

func (Poly) DegreeIn 

func (p Poly) DegreeIn(i int) int

DegreeIn returns the highest exponent of the i-th variable appearing in the polynomial, or 0 for the zero polynomial.

func (Poly) DependsOn 

func (p Poly) DependsOn(i int) bool

DependsOn reports whether the i-th variable appears with a positive exponent in some term of the polynomial.

func (Poly) Derivative 

func (p Poly) Derivative(i int) Poly

Derivative returns the formal partial derivative of the polynomial with respect to the i-th variable.

func (Poly) Equal 

func (p Poly) Equal(o Poly) bool

Equal reports whether two polynomials are equal as elements of the ring.

func (Poly) Eval 

func (p Poly) Eval(point []*big.Rat) *big.Rat

Eval evaluates the polynomial at the rational point (one value per variable) and returns the exact rational result.

func (Poly) EvalComplex 

func (p Poly) EvalComplex(point []complex128) complex128

EvalComplex evaluates the polynomial at a complex point and returns the complex result. It is used by the numerical variety solver.

func (Poly) EvalComplexAbs 

func (p Poly) EvalComplexAbs(point []complex128) float64

EvalComplexAbs returns the magnitude |p(point)| of the complex evaluation, used to test whether a candidate solution satisfies the polynomial.

func (Poly) Format 

func (p Poly) Format(vars []string) string

Format renders the polynomial with the supplied variable names, terms in descending lexicographic order. The zero polynomial renders as "0".

func (Poly) IsConstant 

func (p Poly) IsConstant() bool

IsConstant reports whether the polynomial is a constant (zero or a single term of degree 0).

func (Poly) IsOne 

func (p Poly) IsOne() bool

IsOne reports whether the polynomial equals the constant 1.

func (Poly) IsZero 

func (p Poly) IsZero() bool

IsZero reports whether the polynomial is identically zero.

func (Poly) LeadingCoeff 

func (p Poly) LeadingCoeff(o Order) *big.Rat

LeadingCoeff returns the coefficient of the leading term with respect to o.

func (Poly) LeadingMonomial 

func (p Poly) LeadingMonomial(o Order) Monomial

LeadingMonomial returns the monomial of the leading term with respect to o.

func (Poly) LeadingTerm 

func (p Poly) LeadingTerm(o Order) Term

LeadingTerm returns the term of the polynomial whose monomial is largest with respect to the order o. It returns the zero term for the zero polynomial.

func (Poly) Len 

func (p Poly) Len() int

Len returns the number of (nonzero) terms in the polynomial.

func (Poly) Monic 

func (p Poly) Monic(o Order) Poly

Monic returns the polynomial scaled so that its leading coefficient with respect to o is 1. The zero polynomial is returned unchanged.

func (Poly) Monomials 

func (p Poly) Monomials() []Monomial

Monomials returns the monomials of the polynomial in canonical order.

func (Poly) Mul 

func (p Poly) Mul(o Poly) Poly

Mul returns the product of two polynomials.

func (Poly) MulMonomial 

func (p Poly) MulMonomial(m Monomial) Poly

MulMonomial returns the polynomial multiplied by the monomial m (coefficient 1).

func (Poly) MulTerm 

func (p Poly) MulTerm(t Term) Poly

MulTerm returns the polynomial multiplied by the single term t.

func (Poly) Multidegree 

func (p Poly) Multidegree(o Order) Monomial

Multidegree returns the exponent vector of the leading monomial with respect to o.

func (Poly) Neg 

func (p Poly) Neg() Poly

Neg returns the polynomial with every coefficient negated.

func (Poly) Nvars 

func (p Poly) Nvars() int

Nvars returns the number of variables of the ambient ring.

func (Poly) Pow 

func (p Poly) Pow(k int) Poly

Pow returns the polynomial raised to the non-negative integer power k, using binary exponentiation. Pow(0) returns the constant 1.

func (Poly) ScalarMul 

func (p Poly) ScalarMul(c *big.Rat) Poly

ScalarMul returns the polynomial multiplied by the rational scalar c.

func (Poly) String 

func (p Poly) String() string

String renders the polynomial with default variable names x1, x2, ....

func (Poly) Sub 

func (p Poly) Sub(o Poly) Poly

Sub returns the difference p - o.

func (Poly) Subst 

func (p Poly) Subst(i int, val *big.Rat) Poly

Subst substitutes the constant rational value val for the i-th variable and returns the resulting polynomial (still in n variables, with that variable eliminated from every term).

func (Poly) Terms 

func (p Poly) Terms() []Term

Terms returns a copy of the polynomial's terms in canonical (descending lexicographic) order.

func (Poly) TotalDegree 

func (p Poly) TotalDegree() int

TotalDegree returns the maximum total degree among the polynomial's terms, or -1 for the zero polynomial.

func (Poly) UsedVars 

func (p Poly) UsedVars() []int

UsedVars returns the sorted indices of variables that appear in the polynomial.

type Ring 

type Ring struct {
	// contains filtered or unexported fields
}

Ring bundles the number of variables, their display names, and a default monomial order. It offers convenient constructors and operations so that callers do not have to repeat the variable count and order everywhere.

func NewNamedRing 

func NewNamedRing(names []string, o Order) Ring

NewNamedRing returns a ring whose variables carry the supplied names, in the given monomial order.

func NewRing 

func NewRing(n int, o Order) Ring

NewRing returns a ring in n variables with the given monomial order and the default variable names x1, ..., xn.

func (Ring) Constant 

func (r Ring) Constant(c *big.Rat) Poly

Constant returns the constant polynomial c of the ring.

func (Ring) ConstantInt 

func (r Ring) ConstantInt(c int64) Poly

ConstantInt returns the constant polynomial equal to the integer c.

func (Ring) Divide 

func (r Ring) Divide(f Poly, divisors []Poly) DivisionResult

Divide performs multivariate division under the ring's order.

func (Ring) Format 

func (r Ring) Format(p Poly) string

Format renders a polynomial using the ring's variable names.

func (Ring) GroebnerBasis 

func (r Ring) GroebnerBasis(gens []Poly) []Poly

GroebnerBasis returns the reduced Gröbner basis of the given generators under the ring's order.

func (Ring) Ideal 

func (r Ring) Ideal(gens ...Poly) Ideal

Ideal returns the ideal generated by gens with the ring's order.

func (Ring) LeadingTerm 

func (r Ring) LeadingTerm(p Poly) Term

LeadingTerm returns the leading term of p under the ring's order.

func (Ring) Names 

func (r Ring) Names() []string

Names returns a copy of the variable display names.

func (Ring) Nvars 

func (r Ring) Nvars() int

Nvars returns the number of variables of the ring.

func (Ring) One 

func (r Ring) One() Poly

One returns the constant polynomial 1 of the ring.

func (Ring) Order 

func (r Ring) Order() Order

Order returns the ring's default monomial order.

func (Ring) Remainder 

func (r Ring) Remainder(f Poly, divisors []Poly) Poly

Remainder returns the remainder of dividing f by the divisors under the ring's order.

func (Ring) SPolynomial 

func (r Ring) SPolynomial(f, g Poly) Poly

SPolynomial returns the S-polynomial of f and g under the ring's order.

func (Ring) Var 

func (r Ring) Var(i int) Poly

Var returns the i-th variable of the ring as a polynomial.

func (Ring) Vars 

func (r Ring) Vars() []Poly

Vars returns all variables of the ring as polynomials.

func (Ring) WithOrder 

func (r Ring) WithOrder(o Order) Ring

WithOrder returns a copy of the ring using a different default order.

func (Ring) Zero 

func (r Ring) Zero() Poly

Zero returns the zero polynomial of the ring.

type Term 

type Term struct {
	Coeff *big.Rat
	Mono  Monomial
}

Term is a single monomial with a rational coefficient, the building block of a polynomial.

func NewTerm 

func NewTerm(c *big.Rat, m Monomial) Term

NewTerm returns a term with the given coefficient and monomial. The coefficient is copied; the monomial is cloned.

func (Term) Clone 

func (t Term) Clone() Term

Clone returns an independent copy of the term.

func (Term) Degree 

func (t Term) Degree() int

Degree returns the total degree of the term's monomial.

func (Term) Div 

func (t Term) Div(o Term) (Term, bool)

Div returns the quotient o/t as a term when the monomial of t divides that of o. The boolean result is false when the monomial division is not exact.

func (Term) Divides 

func (t Term) Divides(o Term) bool

Divides reports whether term t divides term o, i.e. its monomial divides the monomial of o (coefficients are units in a field so are ignored).

func (Term) Equal 

func (t Term) Equal(o Term) bool

Equal reports whether two terms have equal coefficients and equal monomials.

func (Term) Format 

func (t Term) Format(vars []string) string

Format renders the term with the supplied variable names.

func (Term) IsZero 

func (t Term) IsZero() bool

IsZero reports whether the term's coefficient is zero.

func (Term) Mul 

func (t Term) Mul(o Term) Term

Mul returns the product of two terms: coefficients multiply and monomials combine by adding exponents.

func (Term) Neg 

func (t Term) Neg() Term

Neg returns the term with negated coefficient.

func (Term) String 

func (t Term) String() string

String renders the term with default variable names.

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.