-
Notifications
You must be signed in to change notification settings - Fork 0
/
betti.hpp
127 lines (116 loc) · 5.4 KB
/
betti.hpp
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
#ifndef __BETTI_HPP_
#define __BETTI_HPP_
#include <set>
using std::set;
#include <utility>
using std::pair;
/*****************************************************************************\
* This file is part of DynGB. *
* *
* DynGB is free software: you can redistribute it and/or modify *
* it under the terms of the GNU General Public License as published by *
* the Free Software Foundation, either version 2 of the License, or *
* (at your option) any later version. *
* *
* DynGB is distributed in the hope that it will be useful, *
* but WITHOUT ANY WARRANTY; without even the implied warranty of *
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the *
* GNU General Public License for more details. *
* *
* You should have received a copy of the GNU General Public License *
* along with DynGB. If not, see <http://www.gnu.org/licenses/>. *
\*****************************************************************************/
#include <list>
using std::list;
#include <map>
using std::map;
#include "system_constants.hpp"
#include "monomial.hpp"
/**
@ingroup commalg
@author John Perry
@date 2017
@brief Incremental Betti numbers for monomial ideals
@details Computes the 1st “incremental Betti” numbers obtained
when adding to the ideal generated by a set @f$ T @f$ its last monomial
@f$ u @f$.
(These are the degrees of the generators’ syzygies @cite KR05.)
It does not compute the full list of Betti numbers of @f$ T @f$;
rather, it computes the ones that involve @p u itself.
To use the weighted degrees rather than the standard degrees, give a valid
array of weights to @p grading.
@param T a list of Monomial that generate a monomial ideal
@param grading an optional list of weights, to use the weighted degrees of
exponents, rather than the standard degrees
@return a map wherein the key of any element is the degree of a syzygy, and
the value @f$ d @f$ is the number of @f$ t\in T @f$ whose lcm with @p u has
degree @f$ d @f$.
*/
map<DEG_TYPE, unsigned long> full_betti(
const list<Monomial>& T,
const WT_TYPE * grading = nullptr
);
/**
@ingroup commalg
@author John Perry
@date 2017
@brief Incremental Betti numbers for monomial ideals
@details Computes the 1st “incremental Betti” numbers obtained
when adding @p u to the ideal generated by a set @f$ T @f$
defined by the Monomials in the range from @p start to @p end.
(These are the degrees of the generators’ syzygies @cite KR05.)
Unlike @c incremental_betti, this procedure computes all the pairs of @p T
as well as those involving @p u. (This can take quite a bit of time!)
To use the weighted degrees rather than the standard degrees, give a valid
array of weights to @p grading.
@param T a list of Monomial that generate a monomial ideal
@param u a Monomial not in @p T (you can probably use one that is in @p T,
but this is an odd thing to do)
@param grading an optional list of weights, to use the weighted degrees of
exponents, rather than the standard degrees
@return a map wherein the key of any element is the degree of a syzygy, and
the value @f$ d @f$ is the number of @f$ t\in T @f$ whose lcm with @p u has
degree @f$ d @f$.
*/
inline map<DEG_TYPE, unsigned long> full_betti(
const list<Monomial> & T, const Monomial & u,
const WT_TYPE * grading = nullptr
) {
list<Monomial> U(T);
U.push_back(u);
return full_betti(U, grading);
}
/**
@ingroup commalg
@author John Perry
@date 2019
@brief Incremental Betti numbers for monomial ideals
@details Computes the 1st “incremental Betti” numbers obtained
when adding @p u to the ideal generated by a set @f$ T @f$
defined by the Monomials in the range from @p start to @p end.
(These are the degrees of the generators’ syzygies @cite KR05.)
Unlike @c full_betti, this requires as input a set of critical pairs
for @p T, which it will use rather than re-compute.
To use the weighted degrees rather than the standard degrees, give a valid
array of weights to @p grading.
This algorithm is based on @cite GM88.
@param T a list of Monomial that generate a monomial ideal
@param u a Monomial not in @p T (you can probably use one that is in @p T,
but this is an odd thing to do)
@param R a set of critical pairs of @p T, preferably the result of a previous
run of @c incremental_betti (to be sure you have the right set).
The algorithm will modify this, so be sure to send a copy if you need an
older version.
@param grading an optional list of weights, to use the weighted degrees of
exponents, rather than the standard degrees
@return a map wherein the key of any element is the degree of a syzygy, and
the value @f$ d @f$ is the number of @f$ t\in T @f$ whose lcm with @p u has
degree @f$ d @f$.
*/
map<DEG_TYPE, unsigned long> incremental_betti(
const vector<Monomial> & T,
const Monomial & u,
set< pair<int, int> > & R,
const WT_TYPE * grading = nullptr
);
#endif