nag

package module
v0.0.0-...-0a71033 Latest Latest
Warning

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

 Go to latest Published: Jan 1, 2026 License: BSD-3-Clause Imports: 14 Imported by: 0

README

Noncommutative algebraic geometry Go Reference

Documentation

Overview

Package nag implements algorithms in noncommutative algebraic geometry. In particular, this package provides functions to perform polynomial division and compute Gröbner bases. Applications of this package include simplifying expressions and solving equations containing noncommutative variables.

Example 
package main

import (
	"fmt"

	"github.com/fumin/nag"
)

func main() {
	// This example shows how to simplify the expression
	//
	//   bbaa - aabb + aba
	//
	// assuming
	//
	//   aba - b = 0
	//
	// where a, b are noncommutative variables.
	// Using Gröbner bases we will eventually see that bbaa-aabb+aba -> b.
	expr := "bbaa - aabb + aba"
	rules := []string{"aba - b"}

	// Compute the Gröbner basis using the Buchberger algorithm.
	variables := map[string]nag.Symbol{"a": 1, "b": 2}
	ideal := make([]*nag.Polynomial[*nag.Rat], len(rules))
	ideal[0], _ = nag.Parse(variables, nag.ElimOrder(), rules[0])
	basis, _ := nag.Buchberger(ideal, 50)
	// Print the Gröbner basis and notice that we have found an additional
	// useful relation: bba = abb
	fmt.Printf("Gröbner basis:\n")
	for _, b := range basis {
		fmt.Printf("  %v = 0\n", b)
	}
	fmt.Printf("\n")

	// Use the Gröbner basis to simplify the target expression.
	exprP, _ := nag.Parse(variables, nag.ElimOrder(), expr)
	_, simplified := nag.Divide(nil, exprP, basis)
	fmt.Printf("Simplified result: %v\n", simplified)

}

Output:

Gröbner basis:
  aba-b = 0
  b^2a-ab^2 = 0

Simplified result: b
Example (Equation_solving) 
package main

import (
	"fmt"

	"github.com/fumin/nag"
)

func main() {
	// This example shows solving a set of equations using Gröbner bases.
	//
	// Given the set of equations below, we want to obtain an expression for
	// the variable G in terms of other variables D, X, A, B,... etc.
	//
	// The context behind this example is about the boundary value problem of differential equations.
	// In fact, the variable G represents the Green's function operator.
	// For more details, please see:
	// Rosenkranz, M., Buchberger, B., & Engl, H. W. (2003). Solving linear boundary value problems via non-commutative Gröbner bases. Applicable Analysis, 82(7), 655-675.
	equations := []string{
		"D^2GD^2 - D^2",
		"GD^2G - G",
		"GD^2 - 1 + (1-X)L + XR",
		"D^2G - 1",
		"DX - XD - 1",
		"DA - 1",
		"AD - 1 + L",
		"DB + 1",
		"BD - R + 1",
		"RX - R",
		"LX",
	}

	variables := map[string]nag.Symbol{"D": 1, "L": 2, "X": 3, "A": 4, "B": 5, "R": 6, "G": 7}
	ideal := make([]*nag.Polynomial[*nag.Rat], len(equations))
	for i, eq := range equations {
		ideal[i], _ = nag.Parse(variables, nag.ElimOrder(), eq)
	}
	basis, _ := nag.Buchberger(ideal, 50)
	solution := basis[len(basis)-1]
	fmt.Printf("Solution: %v = 0\n", solution)

}

Output:

Solution: G-XBX+XB-XAX+AX = 0
Example (Minimal_polynomial) 
package main

import (
	"fmt"
	"math"

	"github.com/fumin/nag"
)

func main() {
	// This example shows how to find the minimal polynomial for α = √2+√3+√5.
	// The minimal polynomial, P(x), for an algebraic number α is one whose
	// coefficients are integers and which evaluates to zero when α is
	// passed in, i.e. P(α) = 0.
	ideal := []string{
		"x^2 - 2",
		"y^2 - 3",
		"z^2 - 5",
		"α - x - y - z",
		// Equations below express the fact that all variables commute.
		"xy - yx",
		"xz - zx",
		"xα - αx",
		"yz - zy",
		"yα - αy",
		"zα - αz",
	}

	// Compute the Gröbner basis.
	variables := map[string]nag.Symbol{"x": 4, "y": 3, "z": 2, "α": 1}
	idealP := make([]*nag.Polynomial[*nag.Rat], len(ideal))
	for i, p := range ideal {
		idealP[i], _ = nag.Parse(variables, nag.ElimOrder(), p)
	}
	basis, _ := nag.Buchberger(idealP, 50)
	fmt.Printf("Gröbner basis:\n")
	for _, b := range basis {
		fmt.Printf("  %v = 0\n", b)
	}
	fmt.Printf("\n")

	// The minimal polynomial for α is one that contains only α without other variables.
	// In this case, it is the first basis:
	//
	// α^8-40α^6+352α^4-960α^2+576
	//
	// Verify that the above polynomial is indeed zero when α = √2+√3+√5.
	minPoly := basis[0]
	α := math.Sqrt(2) + math.Sqrt(3) + math.Sqrt(5)
	var res float64
	for c, w := range minPoly.Terms() {
		cf, _ := c.Float64()
		pow := float64(len(w))
		res += cf * math.Pow(α, pow)
	}
	fmt.Printf("minPoly(α): %f\n", math.Abs(res))

}

Output:

Gröbner basis:
  α^8-40α^6+352α^4-960α^2+576 = 0
  z-5/576α^7+97/288α^5-95/36α^3+53/12α = 0
  y+1/96α^7-37/96α^5+61/24α^3-15/4α = 0
  x-1/576α^7+7/144α^5+7/72α^3-5/3α = 0

minPoly(α): 0.000000

Index

Examples

Constants

This section is empty.

Variables

This section is empty.

Functions

func Deglex 

func Deglex(x, y Monomial) int

Deglex compares x, y by first comparing their degrees, and in case of a tie applies the lexicographic order.

Example 
package main

import (
	"fmt"

	"github.com/fumin/nag"
)

func main() {
	fmt.Println(nag.Deglex(nag.Monomial{2, 2, 2}, nag.Monomial{2, 2, 1, 1}))
	fmt.Println(nag.Deglex(nag.Monomial{2, 2, 2}, nag.Monomial{2, 2, 1}))
	fmt.Println(nag.Deglex(nag.Monomial{2, 2, 2}, nag.Monomial{2, 3, 1}))

}

Output:

-1
1
-1

Types

type Field 

type Field[T any] interface {
	// NewZero returns the additive identity of the field.
	NewZero() T
	// NewOne returns the multiplicative identity of the field.
	NewOne() T

	// Equal reports whether x and y are equal, where x is the method receiver.
	Equal(y T) bool
	// Add sets z to the sum x+y and returns z, where z is the method receiver.
	Add(x, y T) T
	// Sub sets z to the difference x-y and returns z, where z is the method receiver.
	Sub(x, y T) T
	// Mul sets z to the product x*y and returns z, where z is the method receiver.
	Mul(x, y T) T
	// Div sets z to the quotient x/y and returns z, where z is the method receiver.
	Div(x, y T) T
	// Inv sets z to 1/x and returns z, where z is the method receiver.
	Inv(x T) T

	// String returns the string representation.
	String() string
}

A Field is an element whose addition and multiplication operations satisfy the field axioms.

type Monomial 

type Monomial []Symbol

A Monomial is a product of variables chained by multiplication.

type Order 

type Order func(x, y Monomial) int

An Order is a monomial order for comparing monomials. The meaning of the return value is the same as cmp.Compare.

func ElimOrder 

func ElimOrder() Order

ElimOrder returns a monomial order that first compares monomials as commutative words lexicographically, and in case of a tie applies noncommutative lexicographic order.

Example 
package main

import (
	"fmt"

	"github.com/fumin/nag"
)

func main() {
	order := nag.ElimOrder()
	fmt.Println(order(nag.Monomial{2, 2, 2}, nag.Monomial{2, 2, 1, 1}))
	fmt.Println(order(nag.Monomial{2, 2}, nag.Monomial{2, 2, 1, 1}))
	fmt.Println(order(nag.Monomial{1, 1, 2, 2}, nag.Monomial{2, 2, 1, 1}))

}

Output:

1
-1
-1

type Polynomial 

type Polynomial[K Field[K]] struct {
	// SymbolStringer specifies how a symbol in a monomial is formated when the polynomial is printed out.
	SymbolStringer func(s Symbol) string
	// contains filtered or unexported fields
}

A Polynomial is a polynomial of noncommutative variables.

func Buchberger 

func Buchberger[K Field[K]](g []*Polynomial[K], maxIter int) (basis []*Polynomial[K], complete bool)

Buchberger returns the Gröbner basis of the ideal g, using the Buchberger algorithm. For noncummutative algebras, a Gröbner basis may not be finite and therefore only a partial basis can be computed. In this case, upon reaching maxIter without a complete basis, Buchberger sets complete to false. For more details, please see Theorem 4.2.24, Xiu Xingqiang.

Xiu, Xingqiang. "Non-commutative Gröbner bases and applications." PhD diss., Universität Passau, 2012.

Example 
package main

import (
	"fmt"

	"github.com/fumin/nag"
)

func main() {
	ideal := []string{
		"aba - b",
		"bab - b",
	}

	// Run the Buchberger algorithm.
	variables := map[string]nag.Symbol{"a": 1, "b": 2}
	idealP := make([]*nag.Polynomial[*nag.Rat], len(ideal))
	idealP[0], _ = nag.Parse(variables, nag.Deglex, ideal[0])
	idealP[1], _ = nag.Parse(variables, nag.Deglex, ideal[1])
	basis, complete := nag.Buchberger(idealP, 10)

	// Print the computed Gröbner basis.
	fmt.Println("Gröbner basis:")
	fmt.Println("")
	for _, b := range basis {
		fmt.Println(" ", b)
	}
	fmt.Println("")
	fmt.Println("Basis is complete:", complete)

}

Output:

Gröbner basis:

  ba-ab
  b^2-ab
  a^2b-b

Basis is complete: true

func BuchbergerHomogeneous 

func BuchbergerHomogeneous[K Field[K]](g []*Polynomial[K], maxDeg int) (basis []*Polynomial[K], complete bool)

BuchbergerHomogeneous returns the Gröbner basis of the homogeneous ideal g, using the Buchberger algorithm. All basis polynomials with degree less or equal than maxDeg are returned. For more details, please see Theorem 4.3.16, Xiu Xingqiang.

Xiu, Xingqiang. "Non-commutative Gröbner bases and applications." PhD diss., Universität Passau, 2012.

Example 
package main

import (
	"fmt"

	"github.com/fumin/nag"
)

func main() {
	ideal := []string{
		"x^2 - 2y^2",
		"xy - 3z^2",
	}
	variables := map[string]nag.Symbol{"x": 1, "y": 2, "z": 3}
	idealP := make([]*nag.Polynomial[*nag.Rat], len(ideal))
	for i := range ideal {
		idealP[i], _ = nag.Parse(variables, nag.Deglex, ideal[i])
	}

	// Run the homogeneous Buchberger algorithm and truncate at degree 3.
	var maxDeg int = 3
	basis3, complete := nag.BuchbergerHomogeneous(idealP, maxDeg)
	fmt.Printf("Gröbner basis truncated at degree %d:\n", maxDeg)
	for _, b := range basis3 {
		fmt.Println(" ", b)
	}
	fmt.Println("Basis is complete:", complete)
	fmt.Println("")

	// Run Buchberger again and truncate at a higher degree.
	// We will get the full basis this time round, since maxDeg is higher than the basis' maximum degree.
	maxDeg = 5
	basis, complete := nag.BuchbergerHomogeneous(idealP, maxDeg)
	fmt.Printf("Gröbner basis truncated at degree %d:\n", maxDeg)
	// Skip printing bases that have been printed above.
	fmt.Printf("  ...\n")
	for _, b := range basis[len(basis3):] {
		fmt.Println(" ", b)
	}
	fmt.Println("Basis is complete:", complete)

}

Output:

Gröbner basis truncated at degree 3:
  y^2-1/2x^2
  z^2-1/3xy
  yx^2-x^2y
  zxy-xyz
Basis is complete: false

Gröbner basis truncated at degree 5:
  ...
  zx^3-2xyzy
Basis is complete: true

func Divide 

func Divide[K Field[K]](quotient [][]Quotient[K], f *Polynomial[K], g []*Polynomial[K]) (outQuotient [][]Quotient[K], remainder *Polynomial[K])

Divide divides the polynomial f by the ideal g, and returns the quotient and remainder. The polynomial f is modified upon return. For more details, please see Theorem 3.2.1, Xiu Xingqiang.

Xiu, Xingqiang. "Non-commutative Gröbner bases and applications." PhD diss., Universität Passau, 2012.

Example 
package main

import (
	"fmt"

	"github.com/fumin/nag"
)

func main() {
	variables := map[string]nag.Symbol{"x": 3, "y": 2, "z": 1}
	f, _ := nag.Parse(variables, nag.Deglex, "zx^2yx")
	g := make([]*nag.Polynomial[*nag.Rat], 2)
	g[0], _ = nag.Parse(variables, nag.Deglex, "xy + x")
	g[1], _ = nag.Parse(variables, nag.Deglex, "x^2 + xz")

	// Create a copy of f since nag.Divide modifies f upon return.
	fCopy := nag.NewPolynomial(nag.NewRat(0, 1), nag.Deglex).Set(f)
	var remainder *nag.Polynomial[*nag.Rat]
	quotient := make([][]nag.Quotient[*nag.Rat], 0)
	// Perfom the division.
	quotient, remainder = nag.Divide(quotient, fCopy, g)
	fmt.Println("remainder:", remainder)

	// Check that f = quotient*g + remainder.
	ff := nag.NewPolynomial(nag.NewRat(0, 1), nag.Deglex)
	ff.SymbolStringer = f.SymbolStringer
	cw := nag.NewPolynomial(nag.NewRat(0, 1), nag.Deglex)
	cwg := nag.NewPolynomial(nag.NewRat(0, 1), nag.Deglex)
	cwgw := nag.NewPolynomial(nag.NewRat(0, 1), nag.Deglex)
	for i := range quotient {
		for j := range quotient[i] {
			cij := nag.NewPolynomial(nag.NewRat(0, 1), nag.Deglex, nag.PolynomialTerm[*nag.Rat]{Coefficient: quotient[i][j].Coefficient})
			wij := nag.NewPolynomial(nag.NewRat(0, 1), nag.Deglex, nag.PolynomialTerm[*nag.Rat]{Monomial: quotient[i][j].Left})
			wPij := nag.NewPolynomial(nag.NewRat(0, 1), nag.Deglex, nag.PolynomialTerm[*nag.Rat]{Monomial: quotient[i][j].Right})
			cwgw.Mul(cwg.Mul(cw.Mul(cij, wij), g[i]), wPij)
			ff.Add(ff, cwgw)
		}
	}
	ff.Add(ff, remainder)
	fmt.Println("g*quotient + remainder:", ff, "==", f)

}

Output:

remainder: zxzx
g*quotient + remainder: zx^2yx == zx^2yx

func NewPolynomial 

func NewPolynomial[K Field[K]](field K, order Order, terms ...PolynomialTerm[K]) *Polynomial[K]

NewPolynomial returns a new polynomial containing the given terms.

func Parse 

func Parse(variables map[string]Symbol, order Order, input string) (*Polynomial[*Rat], error)

Parse parses input and returns the polynomial it represents.

Example 
package main

import (
	"fmt"

	"github.com/fumin/nag"
)

func main() {
	pStr := "-x^2y^3 + 5/3(y-x)x"

	variables := map[string]nag.Symbol{"x": 1, "y": 2}
	p, err := nag.Parse(variables, nag.Deglex, pStr)
	if err != nil {
		fmt.Println("error:", err)
		return
	}

	for coefficient, monomial := range p.Terms() {
		fmt.Printf("coefficient: %s, monomial: %v\n", coefficient.RatString(), monomial)
	}

}

Output:

coefficient: -1, monomial: [1 1 2 2 2]
coefficient: 5/3, monomial: [2 1]
coefficient: -5/3, monomial: [1 1]

func (*Polynomial[K]) Add 

func (z *Polynomial[K]) Add(x, y *Polynomial[K]) *Polynomial[K]

Add sets z to the sum x+y and returns z.

func (*Polynomial[K]) Equal 

func (x *Polynomial[K]) Equal(y *Polynomial[K]) bool

Equal reports whether x and y have the same coefficients and monomials.

func (*Polynomial[K]) Field 

func (x *Polynomial[K]) Field() K

Field returns the field of the coefficients in x.

func (*Polynomial[K]) LeadingTerm 

func (x *Polynomial[K]) LeadingTerm() PolynomialTerm[K]

LeadingTerm returns the polynomial term of the leading monomial. Note that the leading term depends on the monomial order employed by the polynomial.

Example 
package main

import (
	"fmt"

	"github.com/fumin/nag"
)

func main() {
	terms := []nag.PolynomialTerm[*nag.Rat]{
		{Coefficient: nag.NewRat(1, 2), Monomial: nag.Monomial{1, 1, 1}},
		{Coefficient: nag.NewRat(1, 3), Monomial: nag.Monomial{2, 2}},
	}

	p0 := nag.NewPolynomial(nag.NewRat(0, 1), nag.Deglex, terms...)
	fmt.Println(p0.LeadingTerm())

	p1 := nag.NewPolynomial(nag.NewRat(0, 1), nag.ElimOrder(), terms...)
	fmt.Println(p1.LeadingTerm())

}

Output:

{1/2 [1 1 1]}
{1/3 [2 2]}

func (*Polynomial[K]) Len 

func (x *Polynomial[K]) Len() int

Len reports the number of terms in x.

func (*Polynomial[K]) Mul 

func (z *Polynomial[K]) Mul(x, y *Polynomial[K]) *Polynomial[K]

Mul sets z to the product x*y and returns z.

func (*Polynomial[K]) Order 

func (x *Polynomial[K]) Order() Order

Order returns the monomial order employed by x.

func (*Polynomial[K]) Pow 

func (z *Polynomial[K]) Pow(x *Polynomial[K], y int) *Polynomial[K]

Pow sets z to the power x^y and returns z.

func (*Polynomial[K]) Set 

func (z *Polynomial[K]) Set(x *Polynomial[K]) *Polynomial[K]

Set sets z to x and returns z.

func (*Polynomial[K]) String 

func (x *Polynomial[K]) String() string

String returns the string representation of x. Symbols in x are formatted using x.SymbolStringer.

func (*Polynomial[K]) Terms 

func (x *Polynomial[K]) Terms() iter.Seq2[K, Monomial]

Terms iterates the terms in a polynomial.

Example 
package main

import (
	"fmt"

	"github.com/fumin/nag"
)

func main() {
	p := nag.NewPolynomial(
		nag.NewRat(0, 1), nag.Deglex,
		nag.PolynomialTerm[*nag.Rat]{Coefficient: nag.NewRat(3, 2), Monomial: nag.Monomial{1, 1, 1}},
		nag.PolynomialTerm[*nag.Rat]{Coefficient: nag.NewRat(-1, 1), Monomial: nag.Monomial{2, 2}},
		nag.PolynomialTerm[*nag.Rat]{Coefficient: nag.NewRat(5, 1), Monomial: nag.Monomial{1, 2}},
	)
	for coeffi, monomial := range p.Terms() {
		fmt.Printf("coefficient: %s, monomial: %v\n", coeffi.RatString(), monomial)
	}

}

Output:

coefficient: 3/2, monomial: [1 1 1]
coefficient: -1, monomial: [2 2]
coefficient: 5, monomial: [1 2]

type PolynomialTerm 

type PolynomialTerm[K Field[K]] struct {
	Coefficient K
	Monomial    Monomial
}

A PolynomialTerm is a term in a polynomial.

type Quotient 

type Quotient[K Field[K]] struct {
	// Coefficient is c_{ij} in Theorem 3.2.1, Xiu Xingqiang.
	Coefficient K
	// Coefficient is w_{ij} in Theorem 3.2.1, Xiu Xingqiang.
	Left Monomial
	// Coefficient is w'_{ij} in Theorem 3.2.1, Xiu Xingqiang.
	Right Monomial
}

A Quotient is the resulting quotient of a polynomial division. Let f be a polynomial and g an ideal, the result of f divided by g is: 

f = g*quotient + remainder

For the exact form of a quotient, see Theorem 3.2.1, Xiu Xingqiang.

Xiu, Xingqiang. "Non-commutative Gröbner bases and applications." PhD diss., Universität Passau, 2012.

type Rat 

type Rat struct{ *big.Rat }

A Rat represents a quotient of arbitrary precision.

func NewRat 

func NewRat(a, b int64) *Rat

NewRat creates a new Rat with numerator a and denominator b.

func (*Rat) Add 

func (z *Rat) Add(x, y *Rat) *Rat

Add sets z to the sum x+y and returns z.

func (*Rat) Div 

func (z *Rat) Div(x, y *Rat) *Rat

Div sets z to the quotient x/y and returns z. If y == 0, Div panics.

func (*Rat) Equal 

func (x *Rat) Equal(y *Rat) bool

Equal reports whether x and y are equal.

func (*Rat) Inv 

func (z *Rat) Inv(x *Rat) *Rat

Inv sets z to 1/x and returns z. If x == 0, Inv panics.

func (*Rat) Mul 

func (z *Rat) Mul(x, y *Rat) *Rat

Mul sets z to the product x*y and returns z.

func (*Rat) NewOne 

func (x *Rat) NewOne() *Rat

NewOne returns the multiplicative identity 1.

func (*Rat) NewZero 

func (x *Rat) NewZero() *Rat

NewZero returns the additive identity 0.

func (*Rat) String 

func (x *Rat) String() string

String returns a string representation of x in the form "a/b" if b != 1, and in the form "a" if b == 1.

func (*Rat) Sub 

func (z *Rat) Sub(x, y *Rat) *Rat

Sub sets z to the difference x-y and returns z.

type Symbol 

type Symbol = byte

A Symbol is a variable in a monomial. This definition implies that the maximum number of variables supported by this package is 256.

Source Files

View all Source files

Directories

Path Synopsis
Package field implements [finite field] arithmetic.
 Package field implements [finite field] arithmetic.
scan

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.