-
Notifications
You must be signed in to change notification settings - Fork 0
/
buchbergers.h
143 lines (115 loc) · 4.85 KB
/
buchbergers.h
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
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
// buchbergers.h
//////////////////////////////////////////////////////////////////////////////////////////////
// Implementation of methods with relation to computing the Groebner Basis of a given set
// of generators for an ideal in a polynomial ring, with respect to a given monomial ordering.
///////////////////////////////////////////////////////////////////////////////////////////////
#pragma once
#ifndef bachbergers_H__
#define bachbergers_H__
#include <deque>
#include <initializer_list>
#include "monomials.h"
#include "polynomials.h"
#include "division.h"
// Declarations
////////////////////////////////////////////////////////////////////////////
// Produces a S-Polynomial, which is the syzygy on the leading terms of two given polynomials (designed
// to produce cancellation of leading terms among polynomials of the same multidegree).
template<typename PolyRing, typename MonomialOrdering>
Polynomial<PolyRing, MonomialOrdering> makeSPolynomial(Polynomial<PolyRing, MonomialOrdering> const &f, Polynomial<PolyRing, MonomialOrdering> const &g);
// Produces a Groebner Basis for a given set of generators for an ideal in K[x1, x2. ,,,., xn]. This is the most naive
// implementation of Buchberger's algroithm.
template<typename GeneratorsContainer>
GeneratorsContainer runBuchbergers(GeneratorsContainer&& ideal_generators);
// Converts a given Groebner Basis into a Minimal Gorebner Basis (G with LC(p)=1 for all p in G, and
// G contains no p for which LT(p) is generated by the ideal of leading terms <LT(G-{p})>.
template<typename BasisContainer>
void makeMinimalGroebner(BasisContainer &groebner_basis);
// Converts a given Minimal Groebner Basis into the unique Reduced Groebner Basis (for which no p
// in G has terms that lies in <LT(G-{P})>).
template<typename BasisContainer>
void makeReducedGroebner(BasisContainer &minimal_groebner_basis);
// Utility wrapper for initializer-lists.
template<typename PolyRing, typename MonomialOrdering>
std::deque<Polynomial<PolyRing, MonomialOrdering>> runBuchbergers(std::initializer_list<Polynomial<PolyRing, MonomialOrdering>> ideal_generators);
// Definitions
////////////////////////////////////////////////////////////////////////////
template<typename PolyRing, typename MonomialOrdering>
Polynomial<PolyRing, MonomialOrdering> makeSPolynomial(Polynomial<PolyRing, MonomialOrdering> const &f, Polynomial<PolyRing, MonomialOrdering> const &g)
{
Polynomial<PolyRing, MonomialOrdering> res;
auto x_gamma = LCM(LM(f), LM(g));
res += (safelyDivide(LT(f), Term<PolyRing>(1, x_gamma))*f);
res -= (safelyDivide(LT(g), Term<PolyRing>(1, x_gamma))*g);
return res;
}
template<typename GeneratorsContainer>
GeneratorsContainer runBuchbergers(GeneratorsContainer&& ideal_generators)
{
GeneratorsContainer groebner_basis {std::forward<GeneratorsContainer>(ideal_generators)};
std::deque<typename std::decay_t<GeneratorsContainer>::value_type> newly_added;
do
{
newly_added.clear();
for (size_t i = 0; i < groebner_basis.size(); ++i)
{
for (size_t j = i+1; j < groebner_basis.size(); ++j)
{
auto reminder = std::get<0>(divide(makeSPolynomial(groebner_basis[i], groebner_basis[j]), groebner_basis));
if (reminder.terms() != 0)
newly_added.push_back(reminder);
}
}
std::copy(newly_added.begin(), newly_added.end(), std::back_inserter(groebner_basis));
} while(!newly_added.empty());
return groebner_basis;
}
template<typename BasisContainer>
void makeMinimalGroebner(BasisContainer &groebner_basis)
{
auto i = groebner_basis.begin();
while (i != groebner_basis.end())
{
bool removed = false;
for (auto j = i+1; (j != groebner_basis.end()) && (!removed); ++j)
{
if (divides(LT(*j), LT(*i)))
{
removed = true;
i = groebner_basis.erase(i);
}
}
if (!removed)
{
i->normalize();
++i;
}
}
}
template<typename BasisContainer>
void makeReducedGroebner(BasisContainer &minimal_groebner_basis)
{
for (auto i = minimal_groebner_basis.begin(); i != minimal_groebner_basis.end(); ++i)
{
for (auto j = minimal_groebner_basis.begin(); j != minimal_groebner_basis.end(); ++j)
{
if (i != j)
{
for (size_t term = 1; term < j->terms(); ++term)
{
if (divides(LT(*i), (*j)[term]))
{
auto factor = (*j)[term].getCoeff()/LT(*i).getCoeff();
(*j) -= factor*(*i);
}
}
}
}
}
}
template<typename PolyRing, typename MonomialOrdering>
std::deque<Polynomial<PolyRing, MonomialOrdering>> runBuchbergers(std::initializer_list<Polynomial<PolyRing, MonomialOrdering>> ideal_generators)
{
return runBuchbergers(std::deque<Polynomial<PolyRing, MonomialOrdering>>(ideal_generators));
}
#endif