Frobby 0.10.0
Loading...
Searching...
No Matches
LatticeAlgs.h
1/* Frobby: Software for monomial ideal computations.
2 Copyright (C) 2011 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#ifndef LATTICE_ALGS_GUARD
18#define LATTICE_ALGS_GUARD
19
20#include "SatBinomIdeal.h"
21#include "IOFacade.h"
22#include "Scanner.h"
23#include "IOHandler.h"
24#include "DataType.h"
25#include "BigIdeal.h"
26#include "MsmStrategy.h"
27#include "TermTranslator.h"
28#include "TranslatingTermConsumer.h"
29#include "DebugStrategy.h"
30#include "Matrix.h"
31#include "BigTermRecorder.h"
32#include "SliceParams.h"
33#include "SliceFacade.h"
34
35#include <algorithm>
36#include <set>
37#include <sstream>
38#include <limits>
39#include <fstream>
40#include <map>
41
42// Computations and data structures on lattices.
43// Support for LatticeAnalyzeAction.
44
45#include <iostream>
46
47// wrapped in do .. while(false) to make it act like a single statement.
48#define CHECK(X) \
49 do { \
50 if (!(X)) { \
51 cout << "Check condition on line " \
52 << __LINE__ << " of file " << __FILE__ \
53 << " not satisfied:\n "#X << endl; \
54 exit(1); \
55 } \
56 } while (false)
57
58enum NeighborPlace {
59 InPlane,
60 UnderPlane,
61 OverPlane,
62 NoPlace
63};
64
65char getPlaceCode(NeighborPlace place);
66
67class Mlfb;
68
69struct SeqPos {
70 SeqPos();
71 SeqPos(const Mlfb* mlfb, size_t nextFacet, size_t previousFacet);
72 size_t getForwardFacet() const;
73 size_t getBackFacet() const;
74 SeqPos getReverse() const;
75 void order();
76 bool operator<(const SeqPos& pos) const;
77
78 const Mlfb* mlfb;
79 size_t fixFacet1;
80 size_t fixFacet2;
81 size_t comingFromFacet;
82};
83
84class GrobLat;
85
86class Neighbor {
87 public:
88 Neighbor(); // invalid
89 Neighbor(const GrobLat& lat); // zero
90 Neighbor(const GrobLat& lat, const size_t row); // row of lat
91 Neighbor(const Neighbor&) = default;
92
93 Neighbor& operator=(const Neighbor& neighbor) {
94 _lat = neighbor._lat;
95 _row = neighbor._row;
96 return *this;
97 }
98
99 bool operator==(const Neighbor& neighbor) const {
100 return _lat == neighbor._lat && getRow() == neighbor.getRow();
101 }
102
103 const mpq_class& getH(size_t i) const;
104 size_t getHDim() const;
105
106 const mpq_class& getY(size_t i) const;
107 size_t getYDim() const;
108
109 size_t getRow() const {return _row;}
110
111 bool isZero() const;
112 bool isValid() const;
113 bool isSpecial() const;
114 bool isGenerator() const;
115
116 string getName() const;
117 const GrobLat& getGrobLat() const {return *_lat;}
118
119 private:
120 const GrobLat* _lat;
121 size_t _row;
122};
123
125class GrobLat {
126 public:
127 GrobLat(const Matrix& matrix, const SatBinomIdeal& ideal);
128
129 Neighbor getNeighbor(size_t row) const {
130 ASSERT(row < getNeighborCount());
131 return Neighbor(*this, row);
132 }
133
134 size_t getNeighborCount() const {
135 ASSERT(_h.getRowCount() == _y.getRowCount());
136 return _y.getRowCount();
137 }
138
139 const Matrix& getYMatrix() const {return _y;}
140 const Matrix& getHMatrix() const {return _h;}
141 const Matrix& getMatrix() const {return _mat;}
142
143 const SatBinomIdeal& getIdeal() const {return _ideal;}
144
145 Neighbor getSum(Neighbor a, Neighbor b) const {
146 vector<mpq_class> sum(getHDim());
147 for (size_t i = 0; i < getHDim(); ++i)
148 sum[i] = _h(a.getRow(), i) + _h(b.getRow(), i);
149 for (size_t row = 0; row < _h.getRowCount(); ++row) {
150 bool match = true;
151 for (size_t col = 0; col < _h.getColCount(); ++col)
152 if (sum[col] != _h(row, col))
153 match = false;
154 if (match)
155 return Neighbor(*this, row);
156 }
157 return Neighbor();
158 }
159
160 Neighbor getSum(size_t a, size_t b) const {
161 vector<mpq_class> sum(getHDim());
162 for (size_t i = 0; i < getHDim(); ++i)
163 sum[i] = _h(a, i) + _h(b, i);
164 for (size_t row = 0; row < _h.getRowCount(); ++row) {
165 bool match = true;
166 for (size_t col = 0; col < _h.getColCount(); ++col)
167 if (sum[col] != _h(row, col))
168 match = false;
169 if (match)
170 return Neighbor(*this, row);
171 }
172 return Neighbor();
173 }
174
175 size_t getYDim() const {
176 ASSERT(_y.getColCount() == _ideal.getVarCount());
177 return _y.getColCount();
178 }
179
180 size_t getHDim() const {
181 return _h.getColCount();
182 }
183
184 bool hasZeroEntryY() const {
185 return _ideal.hasZeroEntry();
186 }
187
188 void getInitialIdeal(BigIdeal& ideal) const {
189 _ideal.getInitialIdeal(ideal);
190 }
191
192 bool isSum(Neighbor n) const {
193 ASSERT(n.isValid());
194 ASSERT(&n.getGrobLat() == this);
195 ASSERT(n.getRow() < _isSumRow.size());
196 return _isSumRow[n.getRow()];
197 }
198 const vector<Neighbor>& getNonSums() const {return _nonSums;}
199 const mpq_class& getZero() const {return _zero;} // todo: remove
200
204 return _ideal.isPointFreeBody(_ideal.getGenerator(a.getRow()),
205 _ideal.getGenerator(b.getRow()));
206 }
207
211 return _ideal.isPointFreeBody(_ideal.getGenerator(a.getRow()),
212 _ideal.getGenerator(b.getRow()),
213 _ideal.getGenerator(c.getRow()));
214 }
215
216 bool isInterior(Neighbor a, Neighbor b) const {
217 if (!isPointFreeBody(a, b))
218 return false;
219 for (size_t var = 1; var < a.getYDim(); ++var)
220 if (a.getY(var) <= 0 && b.getY(var) <= 0)
221 return false;
222 return true;
223 }
224
225 private:
226 vector<bool> _isSumRow;
227 vector<Neighbor> _nonSums;
228
229 Matrix _y; // rows are neighbors in y-space
230 Matrix _h; // rows are neighbors in h-space
231 Matrix _mat; // matrix that defines lattice
232 SatBinomIdeal _ideal; // other representation of _y, necessary for now
233 mpq_class _zero;
234};
235
236class Tri {
237 public:
238 Tri(Neighbor a, Neighbor b, Neighbor sum,
239 const vector<Mlfb>& mlfbs, const GrobLat& lat);
240
241 Neighbor getA() const {return _a;}
242 Neighbor getB() const {return _b;}
243 Neighbor getSum() const {return _sum;}
244 const vector<const Mlfb*>& getASideMlfbs() const {return _aSideMlfbs;}
245 const vector<const Mlfb*>& getBSideMlfbs() const {return _bSideMlfbs;}
246 const vector<Neighbor>& getNeighborsOnBoundary() const {return _boundary;}
247 const vector<Neighbor>& getNeighborsInInterior() const {return _interior;}
248
249 private:
250 Neighbor _a;
251 Neighbor _b;
252 Neighbor _sum; // neighbor that is sum of a and b
253 vector<const Mlfb*> _aSideMlfbs; // MLFBs containing {0,a,sum}
254 vector<const Mlfb*> _bSideMlfbs; // MLFBs containing {0,b,sum}
255 vector<Neighbor> _interior; // neighbors on boundary of <0,a,b,sum>
256 vector<Neighbor> _boundary; // neighbors in interior of <0,a,b,sum>
257};
258
259class Plane {
260 public:
261Plane(Neighbor a, Neighbor b, Neighbor sum,
262 const vector<Mlfb>& mlfbs, const GrobLat& lat):
263 tri(a, b, sum, mlfbs, lat) {}
264
265 size_t getTypeCount(size_t type) const;
266 size_t getMaxType() const;
267 NeighborPlace getPlace(Neighbor neighbor) const;
268 bool inPlane(Neighbor neighbor) const;
269 bool isPivot(const Mlfb& mlfb) const;
270 bool isSidePivot(const Mlfb& mlfb) const;
271 bool isFlat(const Mlfb& mlfb) const;
272 bool is22(const Mlfb& mlfb) const;
273 size_t getType(const Mlfb& mlfb) const;
274
275 bool hasFlat() const {
276 return getTypeCount(4) > 0;
277 }
278
279 Matrix nullSpaceBasis;
280 Tri tri;
281 Matrix rowAB;
282 size_t flatIntervalCount;
283
284 map<size_t, size_t> typeCounts;
285 vector<NeighborPlace> neighborPlace;
286 vector<SeqPos> flatSeq;
287 vector<const Mlfb*> pivots;
288};
289
290class Mlfb {
291 public:
292 size_t getMinInitialFacet() const {
293 return minInitialFacet;
294 }
295
296 bool hasPoint(Neighbor n) const {
297 for (size_t i = 0; i < _points.size(); ++i)
298 if (_points[i] == n)
299 return true;
300 return false;
301 }
302
303 Neighbor getPoint(size_t offset) const {
304 ASSERT(offset < getPointCount());
305 return _points[offset];
306 }
307
308 size_t getPointCount() const {
309 return _points.size();
310 }
311
312 bool operator==(const Mlfb& mlfb) const {
313 return _offset == mlfb._offset;
314 }
315
316 size_t getOffset() const {
317 return _offset;
318 }
319
320 const vector<mpz_class>& getRhs() const {
321 return _rhs;
322 }
323
324 string getName() const {
325 ostringstream name;
326 name << 'm' << (getOffset() + 1);
327 return name.str();
328 }
329
330 string getName(const Plane& plane) const {
331 if (plane.isPivot(*this))
332 return getName() + 'P';
333 if (plane.isFlat(*this))
334 return getName() + 'F';
335 return getName();
336 }
337
338 Neighbor getHitsNeighbor(size_t indexParam) const {
339 ASSERT(indexParam < edgeHitsFacet.size());
340 return getPoint(getHitsFacet(indexParam));
341 }
342
343 size_t getHitsFacet(size_t indexParam) const {
344 ASSERT(indexParam < edgeHitsFacet.size());
345 return edgeHitsFacet[indexParam];
346 }
347
348 const Mlfb* getEdge(size_t indexParam) const {
349 ASSERT(indexParam < edges.size());
350 return edges[indexParam];
351 }
352
353 Mlfb* getEdge(size_t indexParam) {
354 ASSERT(indexParam < edges.size());
355 return edges[indexParam];
356 }
357
358 size_t getFacetOf(const Mlfb& adjacent) const {
359 for (size_t i = 0; i < 4; ++i)
360 if (*getEdge(i) == adjacent)
361 return i;
362 return 4;
363 }
364
365 bool isParallelogram() const {
366 return _isParallelogram;
367 }
368
369 mpq_class index;
370 mpz_class dotDegree;
371 vector<Mlfb*> edges;
372 vector<size_t> edgeHitsFacet;
373 size_t minInitialFacet;
374
375 void reset(size_t offset, const vector<Neighbor>& points);
376
377 private:
378 vector<mpz_class> _rhs;
379 vector<Neighbor> _points;
380 size_t _offset;
381 bool _isParallelogram;
382};
383
384class TriPlane {
385public:
386 TriPlane(Neighbor a, Neighbor b, Neighbor c):
387 _a(a), _b(b), _c(c) {
388
389 Matrix mat(2, 3);
390 for (size_t col = 0; col < 3; ++col) {
391 mat(0, col) = a.getH(col) - c.getH(col);
392 mat(1, col) = b.getH(col) - c.getH(col);
393 }
394
395 nullSpace(_normal, mat);
396 transpose(_normal, _normal);
397 _line = (_normal.getRowCount() != 1);
398 }
399
400 bool isLine() const {
401 return _line;
402 }
403
404 bool closeToPlane(Neighbor a) {
405 ASSERT(!isLine());
406 mpz_class dn = dotNormal(a);
407 return dn == 0 || dn == 1 || dn == -1;
408 }
409
410 bool inPlane(Neighbor a) const {
411 return dotNormal(a) == 0;
412 }
413
414 mpz_class dotNormal(Neighbor a) const {
415 mpz_class prod = 0;
416 for (size_t i = 0; i < 3; ++i)
417 prod += a.getH(i) * _normal(0, i);
418 return prod;
419 }
420
421 bool isParallel(const TriPlane& plane) const {
422 ASSERT(!isLine());
423 ASSERT(!plane.isLine());
424 mpz_class da = plane.dotNormal(_a);
425 return plane.dotNormal(_b) == da && plane.dotNormal(_c) == da;
426 }
427
428 bool isParallel(const Plane& plane) const {
429 ASSERT(!isLine());
430 return plane.nullSpaceBasis == getNormal();
431 }
432
434 const Matrix& getNormal() const {
435 return _normal;
436 }
437
438private:
439 Neighbor _a, _b, _c;
440 Matrix _normal;
441 bool _line;
442};
443
444void getThinPlanes(vector<TriPlane>& planes, const GrobLat& lat);
445void checkPlanes(const vector<TriPlane>& thinPlanes,
446 const vector<Plane>& dtPlanes);
447
448size_t pushOutFacetPositive(size_t facetPushOut,
449 const vector<mpz_class>& rhs,
450 const GrobLat& lat);
451
452size_t pushOutFacetZero(const vector<mpz_class>& rhs, const GrobLat& lat);
453
454void computeMlfbs(vector<Mlfb>& mlfbs, const GrobLat& lat);
455
456
457void computeSeqs(vector<vector<SeqPos> >& left,
458 vector<vector<SeqPos> >& right,
459 const vector<Mlfb>& mlfbs,
460 const Plane& plane);
461
464void computePivotSeqs(vector<vector<SeqPos> >& seqs, const Mlfb& pivot,
465 const Plane& plane);
466
467void checkSeqs(const vector<vector<SeqPos> >& left,
468 const vector<vector<SeqPos> >& right,
469 const Plane& plane,
470 const vector<Mlfb>& mlfbs);
471void checkMiddle(const Plane& plane,
472 const vector<Mlfb>& mlfbs);
473void checkDoubleTriangle(const Plane& plane,
474 const vector<Mlfb>& mlfbs);
475void checkGraph(const vector<Mlfb>& mlfbs);
476void checkGraphOnPlane(const Plane& plane,
477 const vector<Mlfb>& mlfbs);
478
479
482void checkPivotSeqs(vector<vector<SeqPos> >& pivotSeqs,
483 const Plane& plane,
484 const vector<Mlfb>& mlfbs,
485 const vector<SeqPos>& flatSeq);
486
487void checkPlaneTri(const GrobLat& lat,
488 const vector<Mlfb>& mlfbs,
489 const vector<const Mlfb*>& pivots,
490 const Plane& plane);
491
492void computePlanes(vector<Plane>& planes,
493 const GrobLat& lat,
494 vector<Mlfb>& mlfbs);
495
498void setupPlaneCountsAndOrder(vector<Mlfb>& mlfbs,
499 const Plane& plane,
500 map<size_t, size_t>& typeCounts);
501
502bool disjointSeqs(const vector<SeqPos>& a, const vector<SeqPos>& b);
503
507void computePivots(vector<const Mlfb*>& pivots,
508 const vector<Mlfb>& mlfbs,
509 const Plane& plane,
510 const vector<SeqPos>& flatSeq);
511
512void checkNonSums(const GrobLat& lat);
513
514void checkFlatSeq(const vector<SeqPos>& flatSeq,
515 const GrobLat& lat,
516 const Plane& plane);
517
518const char* getEdgePos(size_t index);
519mpq_class getIndexSum(const vector<Mlfb>& mlfbs);
520
521void checkMlfbs(const vector<Mlfb>& mlfbs, const GrobLat& lat);
522void checkDoubleTrianglePlanes(const vector<Plane>& planes,
523 const GrobLat& lat,
524 const vector<Mlfb>& mlfbs);
525void checkPlane(const Plane& plane, const vector<Mlfb>& mlfbs);
526
527#endif
Definition BigIdeal.h:27
Definition LatticeAlgs.h:125
bool isPointFreeBody(Neighbor a, Neighbor b, Neighbor c) const
Definition LatticeAlgs.h:210
bool isPointFreeBody(Neighbor a, Neighbor b) const
Definition LatticeAlgs.h:203
Definition Matrix.h:26
Definition LatticeAlgs.h:290
Definition LatticeAlgs.h:86
Definition LatticeAlgs.h:259
Represents a saturated binomial ideal.
Definition SatBinomIdeal.h:28
const Matrix & getNormal() const
returns the normal of the plane as the row of a matrix.
Definition LatticeAlgs.h:434
Definition LatticeAlgs.h:236