Frobby 0.9.5
EulerAction.cpp
Go to the documentation of this file.
1/* Frobby: Software for monomial ideal computations.
2 Copyright (C) 2010 Bjarke Hammersholt Roune (www.broune.com)
3
4 This program is free software; you can redistribute it and/or modify
5 it under the terms of the GNU General Public License as published by
6 the Free Software Foundation; either version 2 of the License, or
7 (at your option) any later version.
8
9 This program is distributed in the hope that it will be useful,
10 but WITHOUT ANY WARRANTY; without even the implied warranty of
11 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 GNU General Public License for more details.
13
14 You should have received a copy of the GNU General Public License
15 along with this program. If not, see http://www.gnu.org/licenses/.
16*/
17#include "stdinc.h"
18#include "EulerAction.h"
19
20#include "DataType.h"
21#include "IOFacade.h"
22#include "Scanner.h"
23#include "BigIdeal.h"
24#include "BigTermConsumer.h"
25#include "error.h"
26#include "PivotEulerAlg.h"
27#include "Ideal.h"
28#include "HilbertBasecase.h"
29#include "PivotStrategy.h"
30#include "SquareFreeIdeal.h"
31#include "ActionPrinter.h"
32
33#include <algorithm>
34#include <cstdio>
35#include <limits>
36
38 Action
39(staticGetName(),
40 "Compute the Euler characteristic.",
41 "Compute the Euler characteristic of a monomial ideal I. This is defined as "
42 "the Euler characteristic of the simplicial complex D where I is the dual of "
43 "the Stanley-Reisner ideal of D. The translation between I and D is "
44 "computationally efficient. Define f by\n"
45 "\n"
46 " f(v) = product of all variables not in the set v\n"
47 "\n"
48 "Then f is a bijection from the facets of D to the minimal generators of I. "
49 "So this action can easily be used to compute Euler characteristics of "
50 "abstract simplicial complexes given by their facets. If you have an input "
51 "file where the 0-1 exponents are opposite of what you need for this "
52 "action, use the -swap01 option.",
53 false),
54
55 _pivot
56 ("pivot",
57 "Which kind of pivots to use. Options are\n"
58 " std: Use standard pivots only.\n"
59 " gen: Use generator pivots only.\n"
60 " hybrid: Use a heuristic to choose at each split.\n",
61 "gen"),
62
63 _stdPivot
64 ("stdPivot",
65 "Which kind of standard pivots to use. The options are\n"
66 " popvar: Use a popular variable as pivot.\n"
67 " rarevar: Use a rare variable as pivot.\n"
68 " popgcd: Use the gcd of 3 generators divisible by a popular variable.\n"
69 " any: Use some variable in a way that does not vary between runs.\n"
70 " random: Use a random variable. Choices may vary between runs.\n"
71 "A rare variable is a variable that divides a minimum number of "
72 "generators. A popular variable is a variable that divides a "
73 "maximum number of generators.\n"
74 "\n"
75 "In addition, widen_X where X is one of the strategies above will "
76 "compute a preliminary pivot according to X, and then select the actual "
77 "pivot to be the gcd of all generators that the preliminary pivot divides.",
78 "popvar"),
79
80 _genPivot
81 ("genPivot",
82 "Which kind of generator pivots to use. The options are\n"
83 " rarevar: Pick a generator divisible by a rare variable.\n"
84 " popvar: Pick a generator divisible by a popular variable.\n"
85 " maxsupp: Pick a generator with maximum support.\n"
86 " minsupp: Pick a generator with minimum support.\n"
87 " any: Pick some generator in a way that does not vary between runs.\n"
88 " random: Pick a random generator. Choices may vary between runs.\n"
89 " rarest: Pick a generator that is divisible by a maximum number of\n"
90 " rare variables. Break ties by picking the generator that is divisible\n"
91 " by the maximum number of second-most-rare variables and so on.\n"
92 " raremax: as rarevar_maxsupp.\n"
93 "A rare variable is a variable that divides a minimum number of "
94 "generators. A popular variable is a variable that divides a "
95 "maximum number of generators.\n"
96 "\n"
97 "All of these strategies except any and random can have ties. Combine "
98 "strategies A and B by writing A_B. If A has a tie then A_B will use "
99 "B to break the tie. For example rarevar_minsupp will pick some rare "
100 "variable "
101 "and select the generator with maximum support divisible by that variable. "
102 "For another example, rarevar_minsupp_random will do the same thing, but "
103 "if two generators divisible by the rare variable has the same "
104 "maximal support "
105 "then it will pick one at random instead of deterministically.\n"
106 "\n"
107 "All choices implicitly have _any appended to them, so any remaining "
108 "ties are broken arbitrarily in a deterministic way. If a strategy would "
109 "eliminate all candidates for a pivot it will instead preserve all the "
110 "candidates. This can happen for example in minsupp_rarevar where the "
111 "minsupp strategy might have eliminated all generators that are divisible "
112 "by the rare variable that rarevar selects. Then rarevar cannot make a "
113 "choice so it will refrain from doing so.",
114 "raremax"),
115
116 _autoTranspose
117 ("autotranspose",
118 "The two algorithms prefer more variables and more generators "
119 "respectively. Transposing the variable-generator divides "
120 "matrix swaps the number of variables and generators without "
121 "changing the Euler characteristic. If this option is on it "
122 "will transpose at each step if the preferred one of "
123 "variables and generators is not larger. If this option is "
124 "set to \"once\", it will do this but only at the first step. "
125 "If this option is off, no transposes are done.",
126 "on"),
127
128 _printDebug
129 ("debug",
130 "Print what the algorithm does at each step.",
131 false),
132
133 _printStatistics
134 ("stats",
135 "Print statistics on what the algorithm did.",
136 false),
137
138 _useUniqueDivSimplify
139 ("uniqueDiv",
140 "Simplify ideals at each step where a variable divides only one generator.",
141 true),
142
143 _useManyDivSimplify
144 ("manyDiv",
145 "Simplify ideals at each step where a variable divides all generators "
146 "except up to 2.",
147 true),
148
149 _useAllPairsSimplify
150 ("impliedDiv",
151 "Simplify ideals at each step with variables X and Y such that all "
152 "generators divisible by A are also divisible by B.",
153 false),
154
155 _swap01
156 ("swap01",
157 "Change all 0 exponents to 1 and vice versa.",
158 false),
159
160 _io(DataType::getMonomialIdealType(), DataType::getNullType()) {
161}
162
163void EulerAction::obtainParameters(vector<Parameter*>& parameters) {
164 _io.obtainParameters(parameters);
165 parameters.push_back(&_pivot);
166 parameters.push_back(&_stdPivot);
167 parameters.push_back(&_genPivot);
168 parameters.push_back(&_autoTranspose);
169 parameters.push_back(&_printDebug);
170 parameters.push_back(&_printStatistics);
171 parameters.push_back(&_useUniqueDivSimplify);
172 parameters.push_back(&_useManyDivSimplify);
173 parameters.push_back(&_useAllPairsSimplify);
174 parameters.push_back(&_swap01);
175 Action::obtainParameters(parameters);
176}
177
179 auto_ptr<PivotStrategy> stdStrat = newStdPivotStrategy(_stdPivot.getValue());
180 auto_ptr<PivotStrategy> genStrat = newGenPivotStrategy(_genPivot.getValue());
181 auto_ptr<PivotStrategy> strat;
182 if (_pivot == "std")
183 strat = stdStrat;
184 else if (_pivot == "gen")
185 strat = genStrat;
186 else if (_pivot == "hybrid")
187 strat = newHybridPivotStrategy(stdStrat, genStrat);
188 else
189 reportError("Unknown kind of pivot strategy \"" +
190 _pivot.getValue() + "\".");
191
192 if (_printDebug)
193 strat = newDebugPivotStrategy(strat, stderr);
195 strat = newStatisticsPivotStrategy(strat, stderr);
196
197 PivotEulerAlg alg;
198 alg.setPivotStrategy(strat);
202
203 IOFacade ioFacade(_printActions);
204 SquareFreeIdeal ideal;
205 {
206 Scanner in(_io.getInputFormat(), stdin);
209 ioFacade.readSquareFreeIdeal(in, ideal);
210 in.expectEOF();
211 }
212 if (_swap01) {
213 ActionPrinter pr(_printActions, "Inverting ideal.");
214 ideal.swap01Exponents();
215 }
216
217 {
218 ActionPrinter pr(_printActions, "Minimizing ideal.");
219 ideal.minimize();
220 }
221
222 if (_autoTranspose == "on") {
223 alg.setAutoTranspose(true);
224 alg.setInitialAutoTranspose(true);
225 } else if (_autoTranspose == "once") {
226 alg.setAutoTranspose(false);
227 alg.setInitialAutoTranspose(true);
228 } else if (_autoTranspose == "off") {
229 alg.setAutoTranspose(false);
230 alg.setInitialAutoTranspose(false);
231 } else
232 reportError("Unknown setting for -autoTranspose of \"" +
233 _autoTranspose.getValue() + "\".");
234
235 mpz_class euler;
236 {
237 ActionPrinter pr(_printActions, "Computing Euler characteristic.");
238 euler = alg.computeEulerCharacteristic(*ideal.getRawIdeal());
239 }
240 gmp_fprintf(stdout, "%Zd\n", euler.get_mpz_t());
241}
242
244 return "euler";
245}
auto_ptr< PivotStrategy > newStdPivotStrategy(const string &name)
auto_ptr< PivotStrategy > newHybridPivotStrategy(auto_ptr< PivotStrategy > stdStrat, auto_ptr< PivotStrategy > genStrat)
auto_ptr< PivotStrategy > newStatisticsPivotStrategy(auto_ptr< PivotStrategy > strat, FILE *out)
auto_ptr< PivotStrategy > newDebugPivotStrategy(auto_ptr< PivotStrategy > strat, FILE *out)
auto_ptr< PivotStrategy > newGenPivotStrategy(const string &name)
BoolParameter _printActions
Definition Action.h:68
virtual void obtainParameters(vector< Parameter * > &parameters)
Definition Action.cpp:133
The intention of this class is to describe the different kinds of mathematical structures that Frobby...
Definition DataType.h:29
StringParameter _stdPivot
Definition EulerAction.h:38
StringParameter _autoTranspose
Definition EulerAction.h:40
static const char * staticGetName()
BoolParameter _useManyDivSimplify
Definition EulerAction.h:44
StringParameter _genPivot
Definition EulerAction.h:39
BoolParameter _printStatistics
Definition EulerAction.h:42
IOParameters _io
Definition EulerAction.h:47
BoolParameter _printDebug
Definition EulerAction.h:41
virtual void obtainParameters(vector< Parameter * > &parameters)
BoolParameter _useAllPairsSimplify
Definition EulerAction.h:45
BoolParameter _useUniqueDivSimplify
Definition EulerAction.h:43
virtual void perform()
StringParameter _pivot
Definition EulerAction.h:37
BoolParameter _swap01
Definition EulerAction.h:46
A facade for input and output of mathematical objects.
Definition IOFacade.h:39
void readSquareFreeIdeal(Scanner &in, SquareFreeIdeal &ideal)
Read a square free ideal from in and place it in the parameter ideal.
Definition IOFacade.cpp:116
void autoDetectInputFormat(Scanner &in)
If using the input format, this must be called before validating the ideals, since the auto detect fo...
const string & getInputFormat() const
void validateFormats() const
void obtainParameters(vector< Parameter * > &parameters)
void setAutoTranspose(bool value)
void setUseUniqueDivSimplify(bool value)
void setPivotStrategy(auto_ptr< PivotStrategy > strategy)
const mpz_class & computeEulerCharacteristic(const Ideal &ideal)
void setUseManyDivSimplify(bool value)
void setUseAllPairsSimplify(bool value)
void setInitialAutoTranspose(bool value)
This class offers an input interface which is more convenient and for some purposes more efficient th...
Definition Scanner.h:50
void expectEOF()
Require that there is no more input.
Definition Scanner.cpp:77
const RawSquareFreeIdeal * getRawIdeal() const
void swap01Exponents()
Change 0 exponents into 1 and vice versa.
const string & getValue() const
void reportError(const string &errorMsg)
Definition error.cpp:23
This header file includes common definitions and is included as the first line of code in every imple...