Frobby  0.9.1
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 
33 IdealFacade::IdealFacade(bool printActions):
34  Facade(printActions) {
35 }
36 
37 void IdealFacade::deform(BigIdeal& bigIdeal) {
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 
65 void IdealFacade::swap01(BigIdeal& bigIdeal) {
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 
82 mpz_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 
108  SizeMaxIndepSetAlg alg;
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 
120 void 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 
171 void 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>
181 void 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 
253 void 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 }
BigIdeal::takeRadical
void takeRadical()
Definition: BigIdeal.cpp:264
BigIdeal
Definition: BigIdeal.h:27
VarNames::toString
void toString(string &str) const
Definition: VarNames.cpp:171
IdealFacade::computeDimension
mpz_class computeDimension(const BigIdeal &ideal, bool codimension=false, bool squareFreeAndMinimal=false)
Compute the Krull dimension of ideal.
Definition: IdealFacade.cpp:82
stdinc.h
Ideal::minimize
void minimize()
Definition: Ideal.cpp:501
IOHandler.h
IdealFacade::takeProducts
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...
Definition: IdealFacade.cpp:120
BigIdeal::getNames
const VarNames & getNames() const
Definition: BigIdeal.cpp:253
CanonicalCoefTermConsumer.h
SizeMaxIndepSetAlg
Encapsulates an algorithm for computing size-maximal independent sets of a hypergraph.
Definition: SizeMaxIndepSetAlg.h:61
IOFacade::writeTerm
void writeTerm(const vector< mpz_class > &term, const VarNames &names, IOHandler *handler, FILE *out)
Definition: IOFacade.cpp:218
VarNames::projectVar
void projectVar(size_t index)
Definition: VarNames.cpp:161
IdealFacade::sortGenerators
void sortGenerators(BigIdeal &ideal)
Sorts the generators of ideal.
Definition: IdealFacade.cpp:237
IdealFacade::sortVariables
void sortVariables(BigIdeal &ideal)
Sorts the variables of ideal.
Definition: IdealFacade.cpp:245
IdealFacade::swap01
void swap01(BigIdeal &ideal)
Change all 0 exponents to 1 and vice versa.
Definition: IdealFacade.cpp:65
BigIdeal::newLastTerm
void newLastTerm()
Definition: BigIdeal.cpp:104
Facade::isPrintingActions
bool isPrintingActions() const
Returns true if printing actions.
Definition: Facade.cpp:66
TermTranslator
TermTranslator handles translation between terms whose exponents are infinite precision integers and ...
Definition: TermTranslator.h:41
FrobbyStringStream.h
BigIdeal::getLcm
void getLcm(vector< mpz_class > &lcm) const
Definition: BigIdeal.cpp:143
Macaulay2IOHandler.h
VarNames::getVarCount
size_t getVarCount() const
Returns the current number of variables.
Definition: VarNames.h:113
Ideal::sortReverseLex
void sortReverseLex()
Definition: Ideal.cpp:510
Ideal::getGeneratorCount
size_t getGeneratorCount() const
Definition: Ideal.h:57
IdealFacade::printLcm
void printLcm(BigIdeal &ideal, IOHandler *handler, FILE *out)
Definition: IdealFacade.cpp:277
Ideal.h
BigIdeal::getLastTermExponentRef
mpz_class & getLastTermExponentRef(size_t var)
Definition: BigIdeal.h:126
BigIdeal::sortGeneratorsUnique
void sortGeneratorsUnique()
Definition: BigIdeal.cpp:273
BigIdeal::insert
void insert(const Ideal &ideal)
Definition: BigIdeal.cpp:60
Term
Term represents a product of variables which does not include a coefficient.
Definition: Term.h:49
error.h
IdealFacade.h
PivotEulerAlg.h
IdealFacade::printAnalysis
void printAnalysis(FILE *out, BigIdeal &ideal)
Definition: IdealFacade.cpp:253
Ideal::getVarCount
size_t getVarCount() const
Definition: Ideal.h:56
IdealFacade::projectVar
void projectVar(BigIdeal &bigIdeal, size_t var)
Remove the variable var from the ideal and ring by substituting it by 1.
Definition: IdealFacade.cpp:171
BigIdeal::sortVariables
void sortVariables()
Definition: BigIdeal.cpp:298
SizeMaxIndepSetAlg.h
IdealFacade::trimVariables
void trimVariables(const vector< BigIdeal * > &ideals, VarNames &names)
Remove those variables that do not appear in any generator.
Definition: IdealFacade.cpp:181
Frobby::codimension
void codimension(const Ideal &ideal, mpz_t codim)
Compute the codimension of a monomial ideal.
Definition: frobby.cpp:437
IdealFacade::sortAllAndMinimize
void sortAllAndMinimize(BigIdeal &bigIdeal)
Remove redundant generators from ideal.
Definition: IdealFacade.cpp:156
BigIdeal::deform
void deform()
Definition: BigIdeal.cpp:257
Facade::endAction
void endAction()
Prints to standard error the time since the last call to beginAction.
Definition: Facade.cpp:51
IdealFacade::takeRadical
void takeRadical(BigIdeal &ideal)
Takes the radical of the generators of ideal.
Definition: IdealFacade.cpp:51
SizeMaxIndepSetAlg::run
void run(Ideal &ideal)
Run the algorithm on ideal.
Definition: SizeMaxIndepSetAlg.cpp:23
BigIdeal::contains
bool contains(const vector< mpz_class > &term) const
Definition: BigIdeal.cpp:207
BigIdeal::sortGenerators
void sortGenerators()
Definition: BigIdeal.cpp:280
IOFacade.h
SquareFreeTermOps::lcm
void lcm(Word *res, const Word *resEnd, const Word *a, const Word *b)
Definition: RawSquareFreeTerm.cpp:251
Ideal::isMinimallyGenerated
bool isMinimallyGenerated() const
Definition: Ideal.cpp:81
IdealFacade::sortGeneratorsUnique
void sortGeneratorsUnique(BigIdeal &ideal)
Sorts the generators of ideal and removes duplicates.
Definition: IdealFacade.cpp:229
reportError
void reportError(const string &errorMsg)
Definition: error.cpp:23
Ideal::isWeaklyGeneric
bool isWeaklyGeneric() const
Definition: Ideal.cpp:121
IOHandler
An IOHandler implements input and output for some format in such a way that client code does not need...
Definition: IOHandler.h:41
SizeMaxIndepSetAlg::getMaxIndepSetSize
mpz_class getMaxIndepSetSize()
Returns the largest size over all independent sets of the hypergraph passed to run.
Definition: SizeMaxIndepSetAlg.cpp:67
TermTranslator.h
BigIdeal::clear
void clear()
Definition: BigIdeal.cpp:218
FrobbyStringStream
A replacement for stringstream.
Definition: FrobbyStringStream.h:26
Ideal::isStronglyGeneric
bool isStronglyGeneric()
Definition: Ideal.cpp:106
Ideal
Represents a monomial ideal with int exponents.
Definition: Ideal.h:27
HilbertBasecase.h
Ideal::insert
void insert(const Exponent *term)
Definition: Ideal.cpp:455
BigIdeal::projectVar
void projectVar(size_t var)
Definition: BigIdeal.cpp:158
IdealFacade::IdealFacade
IdealFacade(bool printActions)
Definition: IdealFacade.cpp:33
Facade::beginAction
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
VarNames
Defines the variables of a polynomial ring and facilities IO involving them.
Definition: VarNames.h:40
ASSERT
#define ASSERT(X)
Definition: stdinc.h:86
IdealFacade::addPurePowers
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...
Definition: IdealFacade.cpp:209
BigIdeal::getGeneratorCount
size_t getGeneratorCount() const
Definition: BigIdeal.h:144
BigIdeal.h
BigIdeal::getVarCount
size_t getVarCount() const
Definition: BigIdeal.h:148
IdealFacade::deform
void deform(BigIdeal &ideal)
Applies some generic deformation to the ideal.
Definition: IdealFacade.cpp:37
Facade
This is the super class of all facades.
Definition: Facade.h:32
IOFacade
A facade for input and output of mathematical objects.
Definition: IOFacade.h:39