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
82mpz_class IdealFacade::computeDimension(const BigIdeal& bigIdeal,
83 bool codimension,
84 bool squareFreeAndMinimal) {
85 beginAction("Computing dimension of ideal.");
86
87 size_t varCount = bigIdeal.getVarCount();
88 size_t genCount = bigIdeal.getGeneratorCount();
89
90 Ideal radical(varCount);
91 Term tmp(varCount);
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
105 if (!squareFreeAndMinimal)
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
120void IdealFacade::takeProducts(const vector<BigIdeal*>& ideals,
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())) {
129 FrobbyStringStream errorMsg;
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
141 reportError(errorMsg);
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
171void IdealFacade::projectVar(BigIdeal& bigIdeal, size_t var) {
172 beginAction("Projecting a variable away.");
173
174 ASSERT(var < bigIdeal.getVarCount());
175
176 bigIdeal.projectVar(var);
177
178 endAction();
179}
180#include <iostream>
181void IdealFacade::trimVariables(const vector<BigIdeal*>& ideals,
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
253void IdealFacade::printAnalysis(FILE* out, BigIdeal& bigIdeal) {
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
278 IOHandler* handler,
279 FILE* out) {
280 beginAction("Computing lcm");
281
282 vector<mpz_class> lcm;
283 ideal.getLcm(lcm);
284
285 IOFacade ioFacade(isPrintingActions());
286 ioFacade.writeTerm(lcm, ideal.getNames(), handler, out);
287 fputc('\n', out);
288
289 endAction();
290}
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
bool contains(const vector< mpz_class > &term) const
Definition BigIdeal.cpp:207
void deform()
Definition BigIdeal.cpp:257
size_t getVarCount() const
Definition BigIdeal.h:148
void clear()
Definition BigIdeal.cpp:218
void insert(const Ideal &ideal)
Definition BigIdeal.cpp:60
const VarNames & getNames() const
Definition BigIdeal.cpp:253
size_t getGeneratorCount() const
Definition BigIdeal.h:144
void projectVar(size_t var)
Definition BigIdeal.cpp:158
void sortVariables()
Definition BigIdeal.cpp:298
void takeRadical()
Definition BigIdeal.cpp:264
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
void writeTerm(const vector< mpz_class > &term, const VarNames &names, IOHandler *handler, FILE *out)
Definition IOFacade.cpp:218
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
void insert(const Exponent *term)
Definition Ideal.cpp:455
bool isWeaklyGeneric() const
Definition Ideal.cpp:121
bool isStronglyGeneric()
Definition Ideal.cpp:106
bool isMinimallyGenerated() const
Definition Ideal.cpp:81
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.
mpz_class getMaxIndepSetSize()
Returns the largest size over all independent sets of the hypergraph passed to run.
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
size_t getVarCount() const
Returns the current number of variables.
Definition VarNames.h:113
void projectVar(size_t index)
Definition VarNames.cpp:161
void toString(string &str) const
Definition VarNames.cpp:171
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...
#define ASSERT(X)
Definition stdinc.h:86