-
Notifications
You must be signed in to change notification settings - Fork 1
/
ideal.go
121 lines (103 loc) · 2.75 KB
/
ideal.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
package bivariate
import (
"fmt"
"strings"
"github.com/ReneBoedker/algobra/errors"
)
// Ideal is the implementation of a polynomial ideal.
type Ideal struct {
*ring
generators []*Polynomial
isGroebner int8 // 0=undecided, 1=true, -1=false
isMinimal int8 // 0=undecided, 1=true, -1=false
isReduced int8 // 0=undecided, 1=true, -1=false
}
// ShortString returns a short string description of id. More precisely, it
// returns the string representation of the generators.
func (id *Ideal) ShortString() string {
var sb strings.Builder
fmt.Fprint(&sb, "<")
for i, g := range id.generators {
if i > 0 {
fmt.Fprint(&sb, ", ")
}
fmt.Fprint(&sb, g)
}
fmt.Fprint(&sb, ">")
return sb.String()
}
// String returns the string representation of id. See also ShortString.
func (id *Ideal) String() string {
return fmt.Sprintf("Ideal %s of %v", id.ShortString(), id.ring)
}
// NewIdeal returns a new polynomial ideal over the given ring. If the
// generators are not defined over the given ring, the function returns an
// InputIncompatible-error.
func (r *QuotientRing) NewIdeal(generators ...*Polynomial) (*Ideal, error) {
const op = "Defining ideal"
id := &Ideal{
ring: r.ring,
generators: make([]*Polynomial, 0, len(generators)),
isGroebner: 0,
isMinimal: 0,
isReduced: 0,
}
for _, g := range generators {
if g.baseRing != r {
return nil, errors.New(
op, errors.InputIncompatible,
"Generators defined over different rings",
)
}
if g.IsZero() {
// Skip zero polynomials
continue
}
id.generators = append(id.generators, g.Copy())
}
if len(id.generators) == 0 {
return nil, errors.New(
op, errors.InputValue,
"Generators %v define an empty ideal", generators,
)
}
return id, nil
}
// Copy creates a copy of id.
func (id *Ideal) Copy() *Ideal {
generators := make([]*Polynomial, len(id.generators), len(id.generators))
for i, g := range id.generators {
generators[i] = g.Copy()
}
return &Ideal{
ring: id.ring,
generators: generators,
isGroebner: id.isGroebner,
isMinimal: id.isMinimal,
isReduced: id.isReduced,
}
}
// Generators returns a copy of the generators of id.
func (id *Ideal) Generators() []*Polynomial {
gens := make([]*Polynomial, len(id.generators), len(id.generators))
for i, g := range id.generators {
gens[i] = g.Copy()
}
return gens
}
// Reduce sets f to f modulo id.
//
// Note that when the generators of id do not form a Gröbner basis, such a basis
// will be computed. This alters the representation of id.
func (id *Ideal) Reduce(f *Polynomial) error {
const op = "Reducing polynomial"
if !id.IsGroebner() {
id = id.GroebnerBasis()
}
r, err := f.Rem(id.generators...)
if err != nil {
return errors.Wrap(op, errors.Inherit, err)
}
*f = *r
return nil
}