Frobby 0.9.5
IdealFacade.cpp
Go to the documentation of this file.
1/* Frobby: Software for monomial ideal computations.
2 Copyright (C) 2007 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 "IdealFacade.h"
19
20#include "BigIdeal.h"
21#include "Ideal.h"
22#include "TermTranslator.h"
23#include "IOHandler.h"
24#include "IOFacade.h"
25#include "Macaulay2IOHandler.h"
27#include "error.h"
28#include "FrobbyStringStream.h"
29#include "SizeMaxIndepSetAlg.h"
30#include "HilbertBasecase.h"
31#include "PivotEulerAlg.h"
32
33IdealFacade::IdealFacade(bool printActions):
34 Facade(printActions) {
35}
36
38 beginAction("Applying generic deformation to ideal.");
39
40 bigIdeal.deform();
41
42 // Reduce range of exponents
43 Ideal ideal(bigIdeal.getVarCount());
44 TermTranslator translator(bigIdeal, ideal, false);
45 bigIdeal.clear();
46 bigIdeal.insert(ideal);
47
48 endAction();
49}
50
52 beginAction("Taking radical of ideal.");
53
54 bigIdeal.takeRadical();
55
56 Ideal ideal(bigIdeal.getVarCount());
57 TermTranslator translator(bigIdeal, ideal, false);
58 bigIdeal.clear();
59
60 bigIdeal.insert(ideal, translator);
61
62 endAction();
63}
64
66 beginAction("Swapping 0 and 1 exponents.");
67
68 const size_t genCount = bigIdeal.getGeneratorCount();
69 const size_t varCount = bigIdeal.getVarCount();
70 for (size_t gen = 0; gen < genCount; ++gen) {
71 for (size_t var = 0; var < varCount; ++var) {
72 if (bigIdeal[gen][var] == 1)
73 bigIdeal[gen][var] = 0;
74 else if (bigIdeal[gen][var] == 0)
75 bigIdeal[gen][var] = 1;
76 }
77 }
78
79 endAction();
80}
81
83 bool codimension,
85 beginAction("Computing dimension of ideal.");
86
87 size_t varCount = bigIdeal.getVarCount();
88 size_t genCount = bigIdeal.getGeneratorCount();
89
92 for (size_t term = 0; term < genCount; ++term) {
93 for (size_t var = 0; var < varCount; ++var) {
94 ASSERT(!squareFreeAndMinimal || bigIdeal[term][var] <= 1);
95
96 if (bigIdeal[term][var] == 0)
97 tmp[var] = 0;
98 else
99 tmp[var] = 1;
100 }
101 radical.insert(tmp);
102 }
103 ASSERT(!squareFreeAndMinimal || radical.isMinimallyGenerated());
104
106 radical.minimize();
107
109 alg.run(radical);
110 mpz_class result = alg.getMaxIndepSetSize();
111
112 endAction();
113
114 if (codimension)
115 return varCount - result;
116 else
117 return result;
118}
119
121 BigIdeal& ideal) {
122 beginAction("Taking products.");
123
124 size_t idealCount = ideals.size();
125 for (size_t i = 0; i < idealCount; ++i) {
126 ASSERT(ideals[i] != 0);
127
128 if (!(ideal.getNames() == ideals[i]->getNames())) {
130 errorMsg <<
131 "Taking products of ideals in rings with different variable lists.\n";
132
133 string list;
134 ideal.getNames().toString(list);
135 errorMsg << "One ring has variables\n " << list << ",\n";
136
137 ideals[i]->getNames().toString(list);
138 errorMsg << "while another has variables\n " << list <<
139 ".\nContact the Frobby developers if you need this functionality.";
140
142 }
143
144 size_t genCount = ideals[i]->getGeneratorCount();
145 size_t varCount = ideals[i]->getVarCount();
146
147 ideal.newLastTerm();
148 for (size_t t = 0; t < genCount; ++t)
149 for (size_t var = 0; var < varCount; ++var)
150 ideal.getLastTermExponentRef(var) += (*ideals[i])[t][var];
151 }
152
153 endAction();
154}
155
157 beginAction("Minimizing ideal.");
158
159 Ideal ideal(bigIdeal.getVarCount());
160 TermTranslator translator(bigIdeal, ideal, false);
161 bigIdeal.clear();
162
163 ideal.minimize();
164 ideal.sortReverseLex();
165
166 bigIdeal.insert(ideal, translator);
167
168 endAction();
169}
170
172 beginAction("Projecting a variable away.");
173
174 ASSERT(var < bigIdeal.getVarCount());
175
176 bigIdeal.projectVar(var);
177
178 endAction();
179}
180#include <iostream>
182 VarNames& names) {
183 beginAction("Removing unused variables.");
184
185 vector<char> used(names.getVarCount());
186 for (size_t i = 0; i < ideals.size(); ++i) {
187 BigIdeal& ideal = *(ideals[i]);
188 ASSERT(ideal.getNames() == names);
189 for (size_t gen = 0; gen < ideal.getGeneratorCount(); ++gen)
190 for (size_t var = 0; var < ideal.getVarCount(); ++var)
191 if (ideal[gen][var] != 0)
192 used[var] = true;
193 }
194
195 // Go from high to low to avoid removing variable i interfering with
196 // the offset of variable j, as it would when i < j.
197 for (size_t var = names.getVarCount(); var > 0;) {
198 --var;
199 if (!used[var]) {
200 names.projectVar(var);
201 for (size_t i = 0; i < ideals.size(); ++i)
202 ideals[i]->projectVar(var);
203 }
204 }
205
206 endAction();
207}
208
210 beginAction("Adding pure powers.");
211
212 vector<mpz_class> lcm;
213 bigIdeal.getLcm(lcm);
214
215 vector<mpz_class> purePower(bigIdeal.getVarCount());
216 for (size_t var = 0; var < bigIdeal.getVarCount(); ++var) {
217 purePower[var] = lcm[var] + 1;
218 if (!bigIdeal.contains(purePower))
219 bigIdeal.insert(purePower);
220
221 ASSERT(bigIdeal.contains(purePower));
222
223 purePower[var] = 0;
224 }
225
226 endAction();
227}
228
230 beginAction("Sorting generators and removing duplicates.");
231
232 ideal.sortGeneratorsUnique();
233
234 endAction();
235}
236
238 beginAction("Sorting generators.");
239
240 ideal.sortGenerators();
241
242 endAction();
243}
244
246 beginAction("Sorting variables.");
247
248 ideal.sortVariables();
249
250 endAction();
251}
252
254 beginAction("Computing and printing analysis.");
255
256 Ideal ideal(bigIdeal.getVarCount());
257 TermTranslator translator(bigIdeal, ideal, false);
258
259 fprintf(stdout, "generators: %lu\n",
260 (unsigned long)ideal.getGeneratorCount());
261 fprintf(stdout, "variables: %lu\n",
262 (unsigned long)ideal.getVarCount());
263
264 size_t sizeBeforeMinimize = ideal.getGeneratorCount();
265 ideal.minimize();
266 fprintf(stdout, "minimally generated: %s\n",
267 ideal.getGeneratorCount() == sizeBeforeMinimize ? "yes" : "no");
268
269 fprintf(out, "strongly generic: %s\n",
270 ideal.isStronglyGeneric() ? "yes" : "no");
271 fprintf(out, "weakly generic: %s\n",
272 ideal.isWeaklyGeneric() ? "yes" : "no");
273
274 endAction();
275}
276
279 FILE* out) {
280 beginAction("Computing lcm");
281
282 vector<mpz_class> lcm;
283 ideal.getLcm(lcm);
284
286 ioFacade.writeTerm(lcm, ideal.getNames(), handler, out);
287 fputc('\n', out);
288
289 endAction();
290}
void nameFactoryRegister(NameFactory< AbstractProduct > &factory)
Registers the string returned by ConcreteProduct::getStaticName() to a function that default-construc...
void sortGenerators()
Definition BigIdeal.cpp:280
void newLastTerm()
Definition BigIdeal.cpp:104
void sortGeneratorsUnique()
Definition BigIdeal.cpp:273
mpz_class & getLastTermExponentRef(size_t var)
Definition BigIdeal.h:126
void getLcm(vector< mpz_class > &lcm) const
Definition BigIdeal.cpp:143
size_t getVarCount() const
Definition BigIdeal.h:148
const VarNames & getNames() const
Definition BigIdeal.cpp:253
size_t getGeneratorCount() const
Definition BigIdeal.h:144
void sortVariables()
Definition BigIdeal.cpp:298
This is the super class of all facades.
Definition Facade.h:32
void beginAction(const char *message)
Prints message to standard error if printing is turned on, and records the time when the action start...
Definition Facade.cpp:38
void endAction()
Prints to standard error the time since the last call to beginAction.
Definition Facade.cpp:51
bool isPrintingActions() const
Returns true if printing actions.
Definition Facade.cpp:66
A replacement for stringstream.
A facade for input and output of mathematical objects.
Definition IOFacade.h:39
An IOHandler implements input and output for some format in such a way that client code does not need...
Definition IOHandler.h:41
void sortAllAndMinimize(BigIdeal &bigIdeal)
Remove redundant generators from ideal.
void trimVariables(const vector< BigIdeal * > &ideals, VarNames &names)
Remove those variables that do not appear in any generator.
void addPurePowers(BigIdeal &bigIdeal)
Adds x_i^(l_i+1) to the ideal for each i where that will be a minimal generator, where x^l is the lcm...
void swap01(BigIdeal &ideal)
Change all 0 exponents to 1 and vice versa.
void sortGenerators(BigIdeal &ideal)
Sorts the generators of ideal.
mpz_class computeDimension(const BigIdeal &ideal, bool codimension=false, bool squareFreeAndMinimal=false)
Compute the Krull dimension of ideal.
void deform(BigIdeal &ideal)
Applies some generic deformation to the ideal.
void takeRadical(BigIdeal &ideal)
Takes the radical of the generators of ideal.
void printAnalysis(FILE *out, BigIdeal &ideal)
IdealFacade(bool printActions)
void sortVariables(BigIdeal &ideal)
Sorts the variables of ideal.
void projectVar(BigIdeal &bigIdeal, size_t var)
Remove the variable var from the ideal and ring by substituting it by 1.
void sortGeneratorsUnique(BigIdeal &ideal)
Sorts the generators of ideal and removes duplicates.
void takeProducts(const vector< BigIdeal * > &ideals, BigIdeal &ideal)
Take the product of the minimal generators of each ideal, and add the resulting monomials as generato...
void printLcm(BigIdeal &ideal, IOHandler *handler, FILE *out)
Represents a monomial ideal with int exponents.
Definition Ideal.h:27
void minimize()
Definition Ideal.cpp:501
size_t getGeneratorCount() const
Definition Ideal.h:57
void sortReverseLex()
Definition Ideal.cpp:510
bool isWeaklyGeneric() const
Definition Ideal.cpp:121
bool isStronglyGeneric()
Definition Ideal.cpp:106
size_t getVarCount() const
Definition Ideal.h:56
Encapsulates an algorithm for computing size-maximal independent sets of a hypergraph.
void run(Ideal &ideal)
Run the algorithm on ideal.
TermTranslator handles translation between terms whose exponents are infinite precision integers and ...
Term represents a product of variables which does not include a coefficient.
Definition Term.h:49
Defines the variables of a polynomial ring and facilities IO involving them.
Definition VarNames.h:40
void toString(string &str) const
Definition VarNames.cpp:171
void reportError(const string &errorMsg)
Definition error.cpp:23
#define ASSERT(X)
Definition stdinc.h:86