Macaulay2 Engine
Loading...
Searching...
No Matches
NCGroebnerTest.cpp
Go to the documentation of this file.
1
31
32#include <iostream>
33#include <memory>
34#include <gtest/gtest.h>
35
36#include "MemoryBlock.hpp"
37#include "interface/ring.h"
38
39#include "poly.hpp"
40#include "aring-glue.hpp"
41#include "NCAlgebras/FreeAlgebra.hpp"
42#include "NCAlgebras/FreeAlgebraQuotient.hpp"
43#include "NCAlgebras/WordTable.hpp"
44#include "NCAlgebras/NCGroebner.hpp"
45#include "NCAlgebras/OverlapTable.hpp"
46#include "NCAlgebras/SuffixTree.hpp"
47#include "NCAlgebras/NCReduction.hpp"
48#include "monordering.hpp"
49#include "monoid.hpp"
50
51#include "util-polyring-creation.hpp"
52
55
56bool testMemoryBlock()
57{
58 MemoryBlock B;
59 for (size_t i = 0; i < 1000; ++i)
60 {
61 size_t sz = 4 + (32343 * i) % 10;
62 auto range = B.allocateArray<int>(sz);
63 for (int j = 0; j < sz; j++)
64 range.first[j] = 100 * i + j;
65 if (i % 93 == 0)
66 {
67 range = B.shrinkLastAllocate(range.first, range.second, range.first + 4);
68 for (int j = 0; j < 4; j++)
69 range.first[j] = 100 * i + j;
70 }
71 if ((range.second - range.first != sz) and (range.second - range.first != 4))
72 return false;
73 // std::cout << "i = " << i << " sz = " << sz << " elems = ";
74 // for (int* a = range.first; a != range.second; ++a)
75 // std::cout << *a << " ";
76 // std::cout << std::endl << "memory usage: " << B.getMemoryUsedInBytes() << std::endl;
77 }
78 return true;
79}
80
81TEST(MemoryBlock, tryit)
82{
83 EXPECT_TRUE(testMemoryBlock()); // TODO: this test is a bit lame currently
84}
85
88
89extern void tryOutMathicCode();
90
91std::vector<int> monom1 {2, 0, 1}; // cab
92std::vector<int> monom2 {2, 2}; // cc
93std::vector<int> monom3 {1, 0, 1, 0}; // baba
94std::vector<int> word {2, 0, 1, 2, 2, 1, 0, 1, 0}; // cabccbaba
95
96TEST(NCReduction, tryit)
97{
98 tryOutMathicCode();
99}
100
101TEST(NCReduction, TrivialPolynomialHeap)
102{
103 FreeAlgebra* A = FreeAlgebra::create(globalQQ,
104 { "x", "y", "z" },
105 degreeRing(1),
106 {1,1,1},
107 {},
108 {1}
109 );
110 FreeAlgebraElement x(A), y(A), z(A), f(A), g(A), h(A);
111 A->var(*x, 0);
112 A->var(*y, 1);
113 A->var(*z, 2);
114 f = x + y;
115 g = y + z;
116 h = x + y + y + z;
117
118 auto H { makePolynomialHeap(HeapType::Trivial, *A) };
119 H->addPolynomial(*f);
120 H->addPolynomial(*g);
121 EXPECT_TRUE(A->is_equal(* H->value(), *h));
122 EXPECT_TRUE(A->is_equal(* H->value(), *h));
123
124 H->removeLeadTerm();
125 EXPECT_FALSE(H->isZero());
126
127 H->removeLeadTerm();
128 EXPECT_FALSE(H->isZero());
129
130 H->removeLeadTerm();
131 EXPECT_TRUE(H->isZero());
132 EXPECT_TRUE(A->is_zero(* H->value()));
133}
134
135TEST(NCReduction, NaiveDedupPolynomialHeap)
136{
137 FreeAlgebra* A = FreeAlgebra::create(globalQQ,
138 { "x", "y", "z"},
139 degreeRing(1),
140 {1,1,1},
141 {},
142 {1}
143 );
144 FreeAlgebraElement x(A), y(A), z(A), f(A), g(A), h(A), mh(A);
145 FreeAlgebraElement F(A), G(A);
146 A->var(*x, 0);
147 A->var(*y, 1);
148 A->var(*z, 2);
149 f = x + y;
150 g = y + z;
151 h = x + y + y + z;
152 mh = -h;
153 // strangely enough, this doesn't give an error unless you use *all* the terms
154 // stopping F early will not cause the error.
155 F = y*z*x*z - y*z*y*y - y*z*z*x - z*x*y*z + z*x*z*y - z*y*y*y - z*z*x*y - z*z*y*x - z*z*z*z;
156 G = -y*z*x*z - y*z*y*y - y*z*z*x;
157
158 auto H { makePolynomialHeap(HeapType::NaiveDedupGeobucket, *A) };
159 std::cout << H->getName() << std::endl;
160 H->addPolynomial(*f);
161 H->addPolynomial(*g);
162 std::cout << "H->value() = " << FreeAlgebraElement(A, *H->value());
163 std::cout << " H->value() = " << FreeAlgebraElement(A, *H->value()) << std::endl;
164 EXPECT_TRUE(A->is_equal(* H->value(), *h));
165 EXPECT_TRUE(A->is_equal(* H->value(), *h));
166
167 H->removeLeadTerm();
168 EXPECT_FALSE(H->isZero());
169
170 H->removeLeadTerm();
171 EXPECT_FALSE(H->isZero());
172
173 H->removeLeadTerm();
174 EXPECT_TRUE(H->isZero());
175 EXPECT_TRUE(A->is_zero(* H->value()));
176 H->addPolynomial(*h);
177 H->addPolynomial(*mh);
178 EXPECT_TRUE(H->isZero());
179 EXPECT_TRUE(A->is_zero(* H->value()));
180
181 H->addPolynomial(*F);
182 H->addPolynomial(*G);
183 buffer o;
184 A->elem_text_out(o,* (H->value()), true, false, false);
185 std::cout << o.str() << std::endl;
186}
187
188TEST(NCReduction, NaivePolynomialHeap)
189{
190 FreeAlgebra* A = FreeAlgebra::create(globalQQ,
191 { "x", "y", "z"},
192 degreeRing(1),
193 {1,1,1},
194 {},
195 {1}
196 );
197 FreeAlgebraElement x(A), y(A), z(A), f(A), g(A), h(A), mh(A);
198 FreeAlgebraElement F(A), G(A);
199 A->var(*x, 0);
200 A->var(*y, 1);
201 A->var(*z, 2);
202 f = x + y;
203 g = y + z;
204 h = x + y + y + z;
205 mh = -h;
206 // strangely enough, this doesn't give an error unless you use *all* the terms
207 // stopping F early will not cause the error.
208 F = y*z*x*z - y*z*y*y - y*z*z*x - z*x*y*z + z*x*z*y - z*y*y*y - z*z*x*y - z*z*y*x - z*z*z*z;
209 G = -y*z*x*z - y*z*y*y - y*z*z*x;
210
211 auto H { makePolynomialHeap(HeapType::NaiveGeobucket, *A) };
212 std::cout << H->getName() << std::endl;
213 H->addPolynomial(*f);
214 std::cout << "H->value() = " << FreeAlgebraElement(A, *H->value()) << std::endl;
215 H->addPolynomial(*g);
216 std::cout << "H->value() = " << FreeAlgebraElement(A, *H->value()) << std::endl;
217 EXPECT_TRUE(A->is_equal(* H->value(), *h));
218 EXPECT_TRUE(A->is_equal(* H->value(), *h));
219
220 std::cout << "about to call removeLeadTerm" << std::endl;
221
222 H->removeLeadTerm();
223 EXPECT_FALSE(H->isZero());
224
225 H->removeLeadTerm();
226 EXPECT_FALSE(H->isZero());
227
228 H->removeLeadTerm();
229 EXPECT_TRUE(H->isZero());
230 EXPECT_TRUE(A->is_zero(* H->value()));
231 H->addPolynomial(*h);
232 H->addPolynomial(*mh);
233 EXPECT_TRUE(H->isZero());
234 EXPECT_TRUE(A->is_zero(* H->value()));
235
236 H->addPolynomial(*F);
237 H->addPolynomial(*G);
238 buffer o;
239 A->elem_text_out(o,* (H->value()), true, false, false);
240 std::cout << o.str() << std::endl;
241}
242
243TEST(MonomialOrdering, create)
244{
245 auto mo1 = MonomialOrderings::Lex(5);
246 auto mo2 = MonomialOrderings::GroupLex(4);
247 auto mo3 = MonomialOrderings::join({mo1, mo2});
248 std::string answer3 { "MonomialOrder => {\n Lex => 5,\n GroupLex => 4\n }" };
249 EXPECT_EQ(answer3, MonomialOrderings::toString(mo3));
250 EXPECT_EQ(9, rawNumberOfVariables(mo3));
251 EXPECT_TRUE(moIsLex(mo1));
252
253 auto mo4 = MonomialOrderings::GRevLex({3,2,5,7});
254 EXPECT_TRUE(moIsGRevLex(mo4));
255 auto mo5 = MonomialOrderings::GRevLex2({1,1,1,1});
256 EXPECT_TRUE(moIsGRevLex(mo5));
257 auto mo6 {
258 MonomialOrderings::join(
259 {
260 MonomialOrderings::GRevLex(3),
261 MonomialOrderings::GRevLex2(4),
262 MonomialOrderings::GRevLex4(5),
263 MonomialOrderings::GroupLex(3)
264 })};
265 (void)mo6;//force a use, suppress a warning
266}
267
268
269TEST(FreeAlgebra, create)
270{
271 if (degreeRing(1) == nullptr or error())
272 {
273 std::cout << "Error: " << error_message() << std::endl;
274 EXPECT_TRUE(false);
275 }
276
277 FreeAlgebra* A = FreeAlgebra::create(globalQQ,
278 { "x", "y", "z" },
279 degreeRing(1),
280 {1,2,3},
281 {},
282 {1}
283 );
284 EXPECT_TRUE(A != nullptr);
285}
286
287TEST(FreeAlgebra, polyarithmetic)
288{
289 FreeAlgebra* A = FreeAlgebra::create(globalQQ,
290 { "x", "y", "z" },
291 degreeRing(1),
292 {1,2,3},
293 {},
294 {1}
295 );
296 FreeAlgebraElement x(A), y(A), z(A), f(A), g(A), h(A);
297 A->var(*x, 0);
298 A->var(*y, 1);
299 A->var(*z, 2);
300 f = x + y;
301 g = y + z;
302 EXPECT_TRUE(x + y == y + x);
303 EXPECT_FALSE(f == g);
304 EXPECT_TRUE(x * (y + z) == x * y + x * z);
305 EXPECT_TRUE((f * g) * f == f * (g * f));
306 EXPECT_TRUE((f^2) == (f * f));
307
308 A->from_word(*h, {1,2,1,0,1});
309 EXPECT_TRUE(h == y * z * y * x * y);
310
311 A->setZero(*f);
312 A->subtract(*f,*x,*y);
313 EXPECT_TRUE(f == (x - y));
314
315 A->setZero(*f);
316 A->setZero(*g);
317 A->from_long(*f,1);
318 std::vector<int> gdata {};
319 A->from_word(*g, gdata);
320 // from_rational test? How to create an mpq_ptr?
321 EXPECT_TRUE(f == g);
322 EXPECT_TRUE(A->is_unit(*f));
323 EXPECT_TRUE((h^0) == f);
324
325 A->setZero(*f);
326 A->setZero(*g);
327 A->setZero(*h);
328 f = x + y;
329 A->from_long(*g,-1);
330 A->negate(*h,*f);
331 EXPECT_TRUE(h == f*g);
332 A->setZero(*h);
333 A->mult_by_coeff(*h,*f,A->coefficientRing()->from_long(-1));
334 EXPECT_TRUE(h == f*g);
335
336 A->setZero(*f);
337 A->setZero(*g);
338 A->setZero(*h);
339 EXPECT_TRUE(A->is_zero(*h));
340 f = x + y;
341 A->lead_term_as_poly(*g,*f);
342 EXPECT_TRUE(g == x);
343 A->add_to_end(*f,*z);
344 EXPECT_TRUE(f == (x + y + z));
345
346 A->subtract(*h,*f,*(x+y+z));
347 EXPECT_TRUE(A->is_zero(*h));
348
349 A->setZero(*f);
350 A->setZero(*g);
351 f = x + y;
352 A->mult_by_term_left(*g,*f,A->coefficientRing()->from_long(1),Word(monom2));
353 EXPECT_TRUE(g == z*z*f);
354 A->setZero(*g);
355 A->mult_by_term_right(*g,*f,A->coefficientRing()->from_long(1),Word(monom3));
356 EXPECT_TRUE(g == f*y*x*y*x);
357 A->setZero(*g);
358 A->mult_by_term_left_and_right(*g,*f,A->coefficientRing()->from_long(1),Word(monom2),Word(monom3));
359 EXPECT_TRUE(g == z*z*f*y*x*y*x);
360
361 // making polynomial monic test
362 A->setZero(*f);
363 A->setZero(*g);
364 A->setZero(*h);
365 A->from_long(*f,-1);
366 g = f*(x + y);
367 A->makeMonic(*h,*g);
368 EXPECT_TRUE(h == x + y);
369}
370
371TEST(FreeAlgebra, quotientArithmetic)
372{
373 FreeAlgebra* Q = FreeAlgebra::create(globalQQ,
374 { "x", "y", "z" },
375 degreeRing(1),
376 {1,2,3},
377 {},
378 {1}
379 );
380 FreeAlgebraElement X(Q), Y(Q), Z(Q), F(Q), G(Q), H(Q);
381 Q->var(*X,0);
382 Q->var(*Y,1);
383 Q->var(*Z,2);
384 F = X*Y + Y*X;
385 G = X*Z + Z*X;
386 H = Y*Z + Z*Y;
387
388 auto GB = std::unique_ptr<ConstPolyList> (new ConstPolyList);
389 //auto GB = new ConstPolyList;
390 GB->push_back(&*F);
391 GB->push_back(&*G);
392 GB->push_back(&*H);
393 EXPECT_TRUE(GB->size() == 3);
394
395 FreeAlgebraQuotient* A = new FreeAlgebraQuotient(*Q, *GB, -1); // are we transferring ownership of GB?
396
397 FreeAlgebraQuotientElement x(A), y(A), z(A), f(A), g(A), h(A);
398
399 // check if things reduce properly
400 A->var(*x,0);
401 A->var(*y,1);
402 A->var(*z,2);
403 A->setZero(*f);
404 A->setZero(*g);
405 A->setZero(*h);
406 f = x*y*x*z*x*y*x*z;
407 g = x*x*x*x*y*y*z*z;
408 A->negate(*h,*g);
409 EXPECT_TRUE(f == h);
410}
411
412TEST(FreeAlgebra, comparisons)
413{
414 FreeAlgebra* A = FreeAlgebra::create(globalQQ,
415 { "x", "y", "z" },
416 degreeRing(1),
417 {1,2,3},
418 {},
419 {1}
420 );
421 FreeAlgebraElement x(A), y(A), z(A), f(A), g(A), h(A);
422 A->var(*x, 0);
423 A->var(*y, 1);
424 A->var(*z, 2);
425 EXPECT_TRUE(A->compare_elems(*x,*y) == GT);
426 EXPECT_TRUE(A->compare_elems(*y,*x) == LT);
427 EXPECT_TRUE(A->compare_elems(*x,*x) == EQ);
428}
429
430TEST(FreeAlgebra, spairs)
431{
432 FreeAlgebra* A = FreeAlgebra::create(globalQQ,
433 { "x", "y", "z" },
434 degreeRing(1),
435 {3,2,1},
436 {3,2,1},
437 {1}
438 );
439 FreeAlgebraElement x(A), y(A), z(A), f(A), g(A), h(A);
440 A->var(*x, 0);
441 A->var(*y, 1);
442 A->var(*z, 2);
443 f = x*y*x + z*y*z;
444 Word leadWord = A->lead_word(*f);
445 Word leadWordPrefix = A->lead_word_prefix(*f,2);
446 Word leadWordSuffix = A->lead_word_suffix(*f,1);
447 // TODO: did the offset change on our recent heft changes?
448 EXPECT_TRUE((*f).cbegin().monom().begin() + 2 == leadWord.begin() && (*f).cbegin().monom().begin() + 5 == leadWord.end());
449 EXPECT_TRUE((*f).cbegin().monom().begin() + 2 == leadWordPrefix.begin() && (*f).cbegin().monom().begin() + 4 == leadWordPrefix.end());
450 EXPECT_TRUE((*f).cbegin().monom().begin() + 3 == leadWordSuffix.begin() && (*f).cbegin().monom().begin() + 5 == leadWordSuffix.end());
451
452 PolyList polyList {&*f};
453 *g = *(NCGroebner::createOverlapPoly(*A, polyList, 0, 2, 0));
454 h = f*y*x - x*y*f;
455 EXPECT_TRUE(g == h);
456}
457
458TEST(OverlapTable, insertion)
459{
460 OverlapTable overlapTable;
461 overlapTable.insert(3,false,std::make_tuple(1,2,3,true));
462 overlapTable.insert(3,false,std::make_tuple(1,2,1,true));
463 overlapTable.insert(2,false,std::make_tuple(1,1,1,true));
464 EXPECT_FALSE(overlapTable.isFinished());
465 EXPECT_TRUE(overlapTable.isFinished(1));
466 EXPECT_FALSE(overlapTable.isFinished(3));
467 EXPECT_TRUE(overlapTable.size() == 3);
468}
469
470TEST(NCGroebner, sorting)
471{
472 auto key1 = std::make_pair(1,false);
473 auto key2 = std::make_pair(1,true);
474 auto key3 = std::make_pair(2,false);
475 auto key4 = std::make_pair(2,true);
476 std::map<std::pair<int,bool>,int> myMap;
477 myMap.insert(std::make_pair(key1,0));
478 myMap.insert(std::make_pair(key2,0));
479 myMap.insert(std::make_pair(key3,0));
480 myMap.insert(std::make_pair(key4,0));
481 // TODO: Make this into a test
482 for (auto i : myMap)
483 {
484 std::cout << "[" << i.first.first << "," << i.first.second << "]" << std::endl;
485 }
486}
487
488TEST(WordTable, create)
489{
490 WordTable W;
491
492 EXPECT_EQ(monom1.size(), 3);
493 EXPECT_EQ(monom2.size(), 2);
494
495 W.insert(Word(monom1));
496 W.insert(Word(monom2));
497 W.insert(Word(monom3));
498
499 EXPECT_EQ(W.monomialCount(), 3);
500}
501
502TEST(WordTable, insert)
503{
504 WordTable W;
505
506 EXPECT_EQ(monom1.size(), 3);
507 EXPECT_EQ(monom2.size(), 2);
508
509 W.insert(Word(monom1));
510 W.insert(Word(monom2));
511 W.insert(Word(monom3));
512
513 std::vector<std::pair<int,int>> matches;
514 W.subwords(Word(word), matches);
515
516 EXPECT_EQ(matches.size(), 3);
517 EXPECT_EQ(matches[0], std::make_pair(0, 0));
518 EXPECT_EQ(matches[1], std::make_pair(1, 3));
519 EXPECT_EQ(matches[2], std::make_pair(2, 5));
520}
521
522
523#if 0
524TEST(WordTable, sizet)
525{
526 size_t a = 3;
527 size_t b = 5;
528 auto c = a-b;
529 std::cout << c << std::endl;
530}
531#endif
532
533TEST(WordTable, simpleSubwords)
534{
535 std::vector<int> monom1 {1, 1}; // yy
536 std::vector<int> word {1}; // y
537
538 WordTable W;
539 W.insert(Word(monom1));
540
541 std::vector<std::pair<int,int>> matches;
542 W.subwords(Word(word), matches);
543
544 EXPECT_EQ(matches.size(), 0);
545}
546
547TEST(WordTable, subwords)
548{
549 std::vector<int> monom1 {1, 0, 1, 2}; // babc
550 std::vector<int> monom2 {1, 0, 2, 2}; // bacc
551 std::vector<int> monom3 {1, 0, 1, 0}; // baba
552 std::vector<int> monom4 {1, 0}; // ba
553 std::vector<int> word {1, 0, 1, 0, 2, 2, 1, 0, 1, 2};
554
555 WordTable W;
556
557 EXPECT_EQ(monom1.size(), 4);
558 EXPECT_EQ(monom2.size(), 4);
559 EXPECT_EQ(monom3.size(), 4);
560 EXPECT_EQ(monom4.size(), 2);
561 EXPECT_EQ(word.size(), 10);
562
563 W.insert(Word(monom1));
564 W.insert(Word(monom2));
565 W.insert(Word(monom3));
566 W.insert(Word(monom4));
567
568 std::vector<std::pair<int,int>> matches;
569 W.subwords(Word(word), matches);
570
571 EXPECT_EQ(matches.size(), 6);
572 EXPECT_EQ(matches[0], std::make_pair(0, 6));
573 EXPECT_EQ(matches[1], std::make_pair(1, 2));
574 EXPECT_EQ(matches[2], std::make_pair(2, 0));
575 EXPECT_EQ(matches[3], std::make_pair(3, 0));
576 EXPECT_EQ(matches[4], std::make_pair(3, 2));
577 EXPECT_EQ(matches[5], std::make_pair(3, 6));
578}
579
580TEST(WordTable, prefix_suffix)
581{
582 std::vector<int> monom1 {1, 0, 1, 2}; // babc
583 std::vector<int> monom2 {1, 0, 2, 2}; // bacc
584 std::vector<int> monom3 {1, 0, 1, 0}; // baba
585 std::vector<int> word {1, 0, 1, 0, 2, 2, 1, 0, 1, 2};
586 std::vector<int> word2 {1, 0, 1, 1, 2, 2, 1, 1, 1, 2};
587
588 WordTable W;
589
590 EXPECT_EQ(monom1.size(), 4);
591 EXPECT_EQ(monom2.size(), 4);
592 EXPECT_EQ(monom3.size(), 4);
593 EXPECT_EQ(word.size(), 10);
594
595 W.insert(Word(monom1));
596 W.insert(Word(monom2));
597 W.insert(Word(monom3));
598
599 int ind = -1; // index of prefix solution, if any.
600 int ind2 = -1; // index of suffix solution, if any.
601 bool isprefix = W.isPrefix(Word(word), ind);
602 bool issuffix = W.isSuffix(Word(word), ind2);
603
604 EXPECT_TRUE(isprefix);
605 EXPECT_TRUE(issuffix);
606 EXPECT_EQ(2, ind);
607 EXPECT_EQ(0, ind2);
608
609 ind = -1;
610 ind2 = -1;
611 isprefix = W.isPrefix(Word(monom1), ind);
612 issuffix = W.isSuffix(Word(monom2), ind2);
613 EXPECT_TRUE(isprefix);
614 EXPECT_EQ(0,ind);
615 EXPECT_TRUE(issuffix);
616 EXPECT_EQ(1,ind2);
617
618
619 ind = -1;
620 ind2 = -1;
621 isprefix = W.isPrefix(Word(word2), ind);
622 issuffix = W.isSuffix(Word(word2), ind2);
623
624 EXPECT_FALSE(isprefix);
625 EXPECT_FALSE(issuffix);
626}
627
628std::ostream& operator<<(std::ostream& o, const std::vector<Overlap>& val)
629{
630 int count = 0;
631 for (auto a : val)
632 {
633 o << "[" << std::get<0>(a) << ","
634 << std::get<1>(a) << ","
635 << std::get<2>(a) << "]";
636 o << " ";
637 count++;
638 if (count % 10 == 0) o << std::endl;
639 }
640 o << std::endl;
641 return o;
642}
643
644std::ostream& operator<<(std::ostream& o, const std::vector<std::pair<int,int>>& val)
645{
646 int count = 0;
647 for (auto a : val)
648 {
649 o << "[" << std::get<0>(a) << ","
650 << std::get<1>(a) << "]";
651 o << " ";
652 count++;
653 if (count % 10 == 0) o << std::endl;
654 }
655 o << std::endl;
656 return o;
657}
658
659#if 0
660template<class T>
661std::ostream& operator<<(std::ostream& o, const std::vector<T>& val)
662{
663 int count = 0;
664 for (auto a : val)
665 {
666 o << "[";
667 int sz = std::tuple_size<T>::value;
668 for (auto i=0; i<sz; ++i)
669 {
670 o << std::get<i>(a) << ",";
671 }
672 o << "]";
673 o << " ";
674 count++;
675 if (count % 10 == 0) o << std::endl;
676 }
677 o << std::endl;
678 return o;
679}
680#endif
681
682TEST(WordTable, skylanin)
683{
684 // X,Y Z are the 3 variables
685#if 0
686 mons = {{Z, X}, {Z, Y}, {Z, Z}, {Y, Y, X}, {Y, Y, Z},
687 {Y, X, Y, Y}, {Y, Y, Y, Y}, {Y, X, Y, X, X},
688 {Y, X, Y, X, Y}, {Y, X, Y, X, Z},
689 {Y, X, X, Y, X, X}, {Y, X, X, Y, X, Z},
690 {Y, X, X, Y, Y, Y}}
691#endif
692
693 std::vector<int> m0 {2,0}; // ZX
694 std::vector<int> m1 {2,1}; // ZY
695 std::vector<int> m2 {2,2}; // ZZ
696 std::vector<int> m3 {1,1,0}; // YYX
697 std::vector<int> m4 {1,1,2}; // YYZ
698 std::vector<int> m5 {1,0,1,1}; // YXYY
699 std::vector<int> m6 {1,1,1,1}; // YYYY
700 std::vector<int> m7 {1,0,1,0,0}; // YXYXX
701 std::vector<int> m8 {1,0,1,0,1}; // YXYXY
702 std::vector<int> m9 {1,0,1,0,2}; // YXYXZ
703 std::vector<int> m10 {1,0,0,1,0,0}; // YXXYXX
704 std::vector<int> m11 {1,0,0,1,0,2}; // YXXYXZ
705 std::vector<int> m12 {1,0,0,1,1,1}; // YXXYYY
706
707 std::vector<Overlap> overlaps;
708 std::vector<std::pair<int,int>> matches;
709
710 WordTable W;
711 W.insert(Word(m0), overlaps);
712 EXPECT_EQ(0, overlaps.size());
713
714 W.insert(Word(m1), overlaps);
715 EXPECT_EQ(0, overlaps.size());
716
717 W.insert(Word(m2), overlaps);
718 std::vector<Overlap> ans {
719 std::make_tuple(2,1,0,true),
720 std::make_tuple(2,1,1,true),
721 std::make_tuple(2,1,2,true)
722 };
723 std::sort(ans.begin(),ans.end());
724 std::sort(overlaps.begin(),overlaps.end());
725
726 EXPECT_EQ(overlaps, ans);
727 overlaps.clear();
728 W.leftOverlaps(overlaps);
729 EXPECT_EQ(0, overlaps.size());
730
731 W.insert(Word(m3));
732 W.insert(Word(m4));
733 W.insert(Word(m5));
734 W.insert(Word(m6));
735 W.insert(Word(m7));
736 W.insert(Word(m8));
737 W.insert(Word(m9));
738 W.insert(Word(m10));
739 W.insert(Word(m11));
740 W.insert(Word(m12));
741
742 matches.clear();
743 W.superwords(Word(std::vector<int> {1, 1}), matches);
744 std::vector<std::pair<int,int>> ans2
745 {
746 std::make_pair(3,0),
747 std::make_pair(4,0),
748 std::make_pair(5,2),
749 std::make_pair(6,0),
750 std::make_pair(6,1),
751 std::make_pair(6,2),
752 std::make_pair(12,3),
753 std::make_pair(12,4)
754 };
755 std::sort(ans2.begin(),ans2.end());
756 std::sort(matches.begin(),matches.end());
757 EXPECT_EQ(ans2, matches);
758
759 matches.clear();
760 EXPECT_TRUE(W.isNontrivialSuperword(Word(std::vector<int> {1,2,1,1,2,1,1}), 6, 6));
761 EXPECT_TRUE(W.isNontrivialSuperword(Word(std::vector<int> {1,1,2,1,1,2,1,1,2}), 4, 4));
762
763 matches.clear();
764 W.subwords(Word(std::vector<int> {2,2,0,1,1,0,1,0,1,1}), matches); // ZZXYYXYXYY
765 std::vector<std::pair<int,int>> ans3
766 {
767 {0,1},
768 {2,0},
769 {3,3},
770 {5,6},
771 {8,4}
772 };
773 std::sort(ans3.begin(),ans3.end());
774 std::sort(matches.begin(),matches.end());
775 EXPECT_EQ(ans3, matches);
776
777}
778
779// Comment this out temporarily. Working on speeding up the suffix tree code.
780/*
781TEST(SuffixTree, suffixtree1)
782{
783 auto vec = std::vector<int> {};
784 EXPECT_TRUE(vec.size() == 0);
785 SuffixTree* suffixTree = new SuffixTree();
786 EXPECT_TRUE(suffixTree->numPatterns() == 0);
787
788 Label sLabel {1,2,3,2,1};
789 Label tLabel {1,2,3,4,1};
790 Label resultLabel {1,2,3};
791 Word sWord(sLabel);
792 Word tWord(tLabel);
793 Word resultWord(resultLabel);
794 EXPECT_TRUE(suffixTree->sharedPrefix(sWord,tWord) == Word(resultWord));
795
796 std::vector<Overlap> rightOverlaps {};
797
798 auto monList1 = std::vector<Label> { Label {2,2}, Label {2,0,1}, Label {1,0,1,0} };
799 suffixTree->insert(monList1, rightOverlaps);
800
801 Label xLabel {0};
802 Label yLabel {1};
803 Label zLabel {2};
804 Label yxLabel {1,0};
805 Word xWord(xLabel);
806 Word yWord(yLabel);
807 Word zWord(zLabel);
808 Word yxWord(yxLabel);
809 auto xNode = std::get<0>(suffixTree->extendedLocus(suffixTree->mRoot,xWord));
810 auto yNode = std::get<0>(suffixTree->extendedLocus(suffixTree->mRoot,yWord));
811 auto zNode = std::get<0>(suffixTree->extendedLocus(suffixTree->mRoot,zWord));
812 auto yxNode = std::get<0>(suffixTree->extendedLocus(suffixTree->mRoot,yxWord));
813 EXPECT_EQ(xNode->suffixLink(),suffixTree->mRoot);
814 EXPECT_EQ(yNode->suffixLink(),suffixTree->mRoot);
815 EXPECT_EQ(zNode->suffixLink(),suffixTree->mRoot);
816 EXPECT_EQ(yxNode->suffixLink(),xNode);
817 auto retval = std::vector<Overlap> { std::make_tuple(0,1,0), std::make_tuple(2,2,2) };
818 EXPECT_EQ(rightOverlaps, retval);
819
820 rightOverlaps.clear();
821 SuffixTree* suffixTree2 = new SuffixTree();
822 auto monList2 = std::vector<Label> {Label {2, 0},Label {2, 1},
823 Label {2, 2},Label {1, 1, 0},Label {1, 1, 2},
824 Label {1, 0, 1, 1},Label {1, 1, 1, 1},
825 Label {1, 0, 1, 0, 0},Label {1, 0, 1, 0, 1},
826 Label {1, 0, 1, 0, 2},Label {1, 0, 0, 1, 0, 0},
827 Label {1, 0, 0, 1, 0, 2},Label {1, 0, 0, 1, 1, 1},
828 Label {1, 0, 0, 0, 1, 0, 1},Label {1, 0, 0, 0, 1, 1, 1},
829 Label {1, 0, 0, 1, 0, 1, 0},Label {1, 0, 0, 1, 0, 1, 2},
830 Label {1, 0, 0, 0, 0, 1, 1, 1},Label {1, 0, 0, 0, 1, 0, 0, 0},
831 Label {1, 0, 0, 0, 1, 0, 0, 1},Label {1, 0, 0, 0, 1, 0, 0, 2},
832 Label {1, 0, 0, 0, 0, 0, 1, 1, 1},Label {1, 0, 0, 0, 0, 1, 0, 0, 0},
833 Label {1, 0, 0, 0, 0, 1, 0, 0, 2},Label {1, 0, 0, 0, 0, 1, 0, 1, 0},
834 Label {1, 0, 0, 0, 0, 1, 0, 1, 2},Label {1, 0, 0, 0, 0, 0, 1, 0, 0, 1},
835 Label {1, 0, 0, 0, 0, 0, 1, 0, 0, 2},Label {1, 0, 0, 0, 0, 0, 1, 0, 1, 0},
836 Label {1, 0, 0, 0, 0, 0, 1, 0, 1, 2},Label {1, 0, 0, 0, 0, 1, 0, 0, 1, 0},
837 Label {1, 0, 0, 0, 0, 1, 0, 0, 1, 1},Label {1, 0, 0, 0, 0, 1, 0, 0, 1, 2},
838 Label {1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 2},Label {1, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0},
839 Label {1, 0, 0, 0, 0, 0, 0, 1, 0, 1, 2},Label {1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0},
840 Label {1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1},Label {1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 2},
841 Label {1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 2},Label {1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 2},
842 Label {1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0},Label {1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1},
843 Label {1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 2},Label {1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0},
844 Label {1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 1},Label {1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 2}};
845 suffixTree2->insert(monList2, rightOverlaps);
846 EXPECT_EQ(596,rightOverlaps.size());
847 EXPECT_EQ(47,suffixTree2->numPatterns());
848
849 // auto subwordsOutput = std::vector<std::pair<int,int>> {};
850 // EXPECT_TRUE(suffixTree2->subwords(Label {2,2,0,1,1,0,1,0,1,1}, subwordsOutput));
851 // auto correctSubwords = std::vector<std::pair<int,int>> { std::make_pair(2,0),
852 // std::make_pair(0,1),
853 // std::make_pair(3,3),
854 // std::make_pair(8,4),
855 // std::make_pair(5,6) };
856 // std::sort(subwordsOutput.begin(),subwordsOutput.end());
857 // std::sort(correctSubwords.begin(),correctSubwords.end());
858 // EXPECT_EQ(subwordsOutput,correctSubwords);
859
860 // auto subwordOutput = std::make_pair(-1,-1);
861 // EXPECT_TRUE(suffixTree2->subword(Label {2,2,0,1,1,0,1,0,1,1}, subwordOutput));
862 // EXPECT_EQ(subwordOutput, std::make_pair(2,0));
863
864 auto superwordsOutput = std::vector<std::pair<int,int>> {};
865 Label yyLabel {1,1};
866 Word yyWord(yyLabel);
867 suffixTree2->superwords(yyWord, superwordsOutput);
868 auto correctSuperwords = std::vector<std::pair<int,int>> { std::make_pair(12,4),std::make_pair(45,10),
869 std::make_pair(14,5),std::make_pair(31,8),
870 std::make_pair(3,0),std::make_pair(17,6),
871 std::make_pair(4,0),std::make_pair(21,7),
872 std::make_pair(5,2),std::make_pair(17,5),
873 std::make_pair(6,0),std::make_pair(12,3),
874 std::make_pair(21,6),std::make_pair(14,4),
875 std::make_pair(6,1),std::make_pair(6,2) };
876 std::sort(superwordsOutput.begin(),superwordsOutput.end());
877 std::sort(correctSuperwords.begin(),correctSuperwords.end());
878 EXPECT_EQ(superwordsOutput,correctSuperwords);
879
880 auto leftOverlapsOutput = std::vector<std::pair<int,int>> {};
881 Label yyxLabel {1,1,0};
882 Word yyxWord(yyxLabel);
883 suffixTree2->leftOverlaps(yyxWord, leftOverlapsOutput);
884 auto correctLeftOverlaps = std::vector<std::pair<int,int>> { std::make_pair(1,1),std::make_pair(6,2),
885 std::make_pair(6,3),std::make_pair(5,3),
886 std::make_pair(5,2),std::make_pair(8,4),
887 std::make_pair(12,4),std::make_pair(12,5),
888 std::make_pair(14,5),std::make_pair(14,6),
889 std::make_pair(13,6),std::make_pair(19,7),
890 std::make_pair(17,6),std::make_pair(17,7),
891 std::make_pair(21,7),std::make_pair(21,8),
892 std::make_pair(31,8),std::make_pair(31,9),
893 std::make_pair(26,9),std::make_pair(37,10),
894 std::make_pair(45,10),std::make_pair(45,11),
895 std::make_pair(42,11) };
896 std::sort(leftOverlapsOutput.begin(),leftOverlapsOutput.end());
897 std::sort(correctLeftOverlaps.begin(),correctLeftOverlaps.end());
898 EXPECT_EQ(leftOverlapsOutput, correctLeftOverlaps);
899
900 rightOverlaps.clear();
901 SuffixTree* suffixTree3 = new SuffixTree();
902 auto monList3 = std::vector<Label> {Label {2, 0},Label {2, 1},
903 Label {2, 2}};
904 auto leftOverlapsOutput2 = std::vector<Overlap> {};
905 std::pair<int,int> o;
906 suffixTree3->insert(monList3,rightOverlaps);
907 suffixTree3->leftOverlaps(leftOverlapsOutput2);
908 EXPECT_EQ(leftOverlapsOutput2.size(),0);
909
910 std::cout << "Here0" << std::endl;
911 Label yyzLabel {1,1,2};
912 Word yyzWord(yyzLabel);
913 suffixTree3->insert(yyxWord, rightOverlaps);
914 std::cout << "Here1" << std::endl;
915 EXPECT_FALSE(suffixTree3->subword(yyzWord,o));
916 auto monList4 = std::vector<Label> {Label{0,0},Label{0,1},Label{0,2},Label{1,1,2},Label{1,1,0},
917 Label{1,1,1,1},Label{1,2,1,1},Label{1,2,1,2,1},Label{1,2,1,2,0},
918 Label{1,2,1,2,2},Label{1,2,2,1,1,1},Label{1,2,2,1,2,2},
919 Label{1,2,2,1,2,0},Label{1,2,2,1,2,1,0},Label{1,2,2,1,2,1,2},
920 Label{1,2,2,2,1,2,1},Label{1,2,2,2,1,1,1},Label{1,2,2,2,1,2,2,2},
921 Label{1,2,2,2,1,2,2,1},Label{1,2,2,2,1,2,2,0},Label{1,2,2,2,2,1,1,1}};
922 rightOverlaps.clear();
923 SuffixTree* suffixTree4 = new SuffixTree();
924 suffixTree4->insert(monList4, rightOverlaps);
925 std::cout << "Here2" << std::endl;
926 Label bigLabel {1,2,2,2,2,1,2,1,0};
927 Word bigWord(bigLabel);
928 suffixTree4->insert(bigWord, rightOverlaps);
929 std::cout << "Here3" << std::endl;
930 auto subwordsOutput2 = std::vector<std::pair<int,int>> {};
931 Label bigLabel2 {1,2,2,2,2,1,2,1,0,0};
932 Word bigWord2(bigLabel2);
933 suffixTree4->subwords(bigWord2, subwordsOutput2);
934 EXPECT_EQ(subwordsOutput2.size(),2);
935 std::cout << "Here4" << std::endl;
936
937 delete suffixTree;
938 delete suffixTree2;
939 delete suffixTree3;
940 delete suffixTree4;
941}
942
943TEST(SuffixTree,suffixtree2)
944{
945 // this test is identical to the one above for WordTable
946 // except for the line 'SuffixTree W' below.
947
948 std::vector<int> m0 {2,0}; // ZX
949 std::vector<int> m1 {2,1}; // ZY
950 std::vector<int> m2 {2,2}; // ZZ
951 std::vector<int> m3 {1,1,0}; // YYX
952 std::vector<int> m4 {1,1,2}; // YYZ
953 std::vector<int> m5 {1,0,1,1}; // YXYY
954 std::vector<int> m6 {1,1,1,1}; // YYYY
955 std::vector<int> m7 {1,0,1,0,0}; // YXYXX
956 std::vector<int> m8 {1,0,1,0,1}; // YXYXY
957 std::vector<int> m9 {1,0,1,0,2}; // YXYXZ
958 std::vector<int> m10 {1,0,0,1,0,0}; // YXXYXX
959 std::vector<int> m11 {1,0,0,1,0,2}; // YXXYXZ
960 std::vector<int> m12 {1,0,0,1,1,1}; // YXXYYY
961
962 std::vector<Overlap> overlaps;
963 std::vector<std::pair<int,int>> matches;
964
965 SuffixTree W;
966 W.insert(Word(m0), overlaps);
967 EXPECT_EQ(0, overlaps.size());
968
969 W.insert(Word(m1), overlaps);
970 EXPECT_EQ(0, overlaps.size());
971
972 W.insert(Word(m2), overlaps);
973 std::vector<Overlap> ans {
974 std::make_tuple(2,1,0),
975 std::make_tuple(2,1,1),
976 std::make_tuple(2,1,2)
977 };
978 std::sort(ans.begin(),ans.end());
979 std::sort(overlaps.begin(),overlaps.end());
980 EXPECT_EQ(overlaps, ans);
981
982 overlaps.clear();
983 W.leftOverlaps(overlaps);
984 EXPECT_EQ(0, overlaps.size());
985
986 W.insert(Word(m3));
987 W.insert(Word(m4));
988 W.insert(Word(m5));
989 W.insert(Word(m6));
990 W.insert(Word(m7));
991 W.insert(Word(m8));
992 W.insert(Word(m9));
993 W.insert(Word(m10));
994 W.insert(Word(m11));
995 W.insert(Word(m12));
996
997 matches.clear();
998 W.superwords(Word(Word(std::vector<int> {1, 1})), matches);
999 std::vector<std::pair<int,int>> ans2
1000 {
1001 std::make_tuple(3,0),
1002 std::make_tuple(4,0),
1003 std::make_tuple(5,2),
1004 std::make_tuple(6,0),
1005 std::make_tuple(6,1),
1006 std::make_tuple(6,2),
1007 std::make_tuple(12,3),
1008 std::make_tuple(12,4)
1009 };
1010 std::sort(ans2.begin(),ans2.end());
1011 std::sort(matches.begin(),matches.end());
1012 EXPECT_EQ(ans2, matches);
1013
1014 matches.clear();
1015 EXPECT_TRUE(W.isNontrivialSuperword(Word(std::vector<int> {1,2,1,1,2,1,1}), 6, 6));
1016 EXPECT_TRUE(W.isNontrivialSuperword(Word(std::vector<int> {1,1,2,1,1,2,1,1,2}), 4, 4));
1017
1018 matches.clear();
1019 W.subwords(Word(std::vector<int> {2,2,0,1,1,0,1,0,1,1}), matches); // ZZXYYXYXYY
1020 std::vector<std::pair<int,int>> ans3
1021 {
1022 {0,1},
1023 {2,0},
1024 {3,3},
1025 {5,6},
1026 {8,4}
1027 };
1028 std::sort(ans3.begin(),ans3.end());
1029 std::sort(matches.begin(),matches.end());
1030 EXPECT_EQ(ans3, matches);
1031}
1032*/
1033
1034// Local Variables:
1035// compile-command: "make -C $M2BUILDDIR/Macaulay2/e/unit-tests runNCGroebnerTest "
1036// indent-tabs-mode: nil
1037// End:
FreeAlgebra.hpp
Free associative algebra k<x_1,...,x_n> over an arbitrary coefficient ring.
FreeAlgebraQuotient.hpp
A FreeAlgebra modulo a two-sided ideal carried by an embedded NCGroebner.
MemoryBlock.hpp
Bump-pointer arena allocator for transient inner-loop allocations.
NCGroebner.hpp
NCGroebner — Buchberger-style two-sided Gröbner basis driver over a FreeAlgebra.
monom1
std::vector< int > monom1
Definition NCGroebnerTest.cpp:91
testMemoryBlock
bool testMemoryBlock()
Definition NCGroebnerTest.cpp:56
monom2
std::vector< int > monom2
Definition NCGroebnerTest.cpp:92
operator<<
std::ostream & operator<<(std::ostream &o, const std::vector< Overlap > &val)
Definition NCGroebnerTest.cpp:628
tryOutMathicCode
void tryOutMathicCode()
Definition NCReduction.cpp:1185
word
std::vector< int > word
Definition NCGroebnerTest.cpp:94
TEST
TEST(MemoryBlock, tryit)
Definition NCGroebnerTest.cpp:81
monom3
std::vector< int > monom3
Definition NCGroebnerTest.cpp:93
makePolynomialHeap
std::unique_ptr< PolynomialHeap > makePolynomialHeap(HeapType type, const FreeAlgebra &F)
Definition NCReduction.cpp:1162
HeapType::NaiveDedupGeobucket
@ NaiveDedupGeobucket
Definition NCReduction.hpp:100
NCReduction.hpp
PolynomialHeap abstract interface — batched-subtraction heap for non-commutative reduction.
OverlapTable.hpp
OverlapTable — degree-sorted queue of pending word overlaps for non-commutative GB drivers.
ConstPolyList
gc_vector< const Poly * > ConstPolyList
Definition Polynomial.hpp:340
PolyList
gc_vector< Poly * > PolyList
Definition Polynomial.hpp:339
SuffixTree.hpp
SuffixTree / SuffixTreeNode — experimental generalised suffix tree for non-commutative leading-word l...
WordTable.hpp
WordTable / WordWithDataTable — leading-word indices for non-commutative Gröbner basis lookup.
globalQQ
const RingQQ * globalQQ
Definition aring.cpp:24
aring-glue.hpp
ConcreteRing<RingType> — the templated bridge between aring and the legacy Ring API.
FreeAlgebra::coefficientRing
const Ring * coefficientRing() const
Definition FreeAlgebra.hpp:87
FreeAlgebra::negate
void negate(Poly &result, const Poly &f) const
Definition FreeAlgebra.cpp:303
FreeAlgebra::is_unit
bool is_unit(const Poly &f) const
Definition FreeAlgebra.cpp:253
FreeAlgebra::subtract
void subtract(Poly &result, const Poly &f, const Poly &g) const
Definition FreeAlgebra.cpp:413
FreeAlgebra::mult_by_term_right
void mult_by_term_right(Poly &result, const Poly &f, const ring_elem c, const Monom m) const
Definition FreeAlgebra.cpp:530
FreeAlgebra::add_to_end
void add_to_end(Poly &f, const Poly &g) const
Definition FreeAlgebra.cpp:678
FreeAlgebra::from_long
void from_long(Poly &result, long n) const
Definition FreeAlgebra.cpp:138
FreeAlgebra::mult_by_term_left
void mult_by_term_left(Poly &result, const Poly &f, const ring_elem c, const Monom m) const
Definition FreeAlgebra.cpp:563
FreeAlgebra::mult_by_coeff
void mult_by_coeff(Poly &result, const Poly &f, const ring_elem c) const
Definition FreeAlgebra.cpp:659
FreeAlgebra::var
void var(Poly &result, int v) const
Definition FreeAlgebra.cpp:184
FreeAlgebra::lead_word_prefix
Word lead_word_prefix(const Poly &f, int endIndex) const
Definition FreeAlgebra.cpp:888
FreeAlgebra::lead_word
Word lead_word(const Poly &f) const
Definition FreeAlgebra.cpp:881
FreeAlgebra::lead_term_as_poly
void lead_term_as_poly(Poly &result, const Poly &f) const
Definition FreeAlgebra.cpp:669
FreeAlgebra::is_zero
bool is_zero(const Poly &f) const
Definition FreeAlgebra.hpp:117
FreeAlgebra::create
static FreeAlgebra * create(const Ring *K, const std::vector< std::string > &names, const PolynomialRing *degreeRing, const std::vector< int > &degrees, const std::vector< int > &wtvecs, const std::vector< int > &heftVector)
Definition FreeAlgebra.cpp:91
FreeAlgebra::makeMonic
void makeMonic(Poly &result, Poly &f) const
Definition FreeAlgebra.cpp:761
FreeAlgebra::mult_by_term_left_and_right
void mult_by_term_left_and_right(Poly &result, const Poly &f, const ring_elem c, const Monom leftM, const Monom rightM) const
Definition FreeAlgebra.cpp:594
FreeAlgebra::from_word
void from_word(Poly &result, const Word &word) const
Definition FreeAlgebra.cpp:248
FreeAlgebra::elem_text_out
void elem_text_out(buffer &o, const Poly &f, bool p_one, bool p_plus, bool p_parens) const
Definition FreeAlgebra.cpp:780
FreeAlgebra::is_equal
bool is_equal(const Poly &f, const Poly &g) const
Definition FreeAlgebra.cpp:288
FreeAlgebra::compare_elems
int compare_elems(const Poly &f, const Poly &g) const
Definition FreeAlgebra.cpp:260
FreeAlgebra::lead_word_suffix
Word lead_word_suffix(const Poly &f, int beginIndex) const
Definition FreeAlgebra.cpp:895
FreeAlgebra::setZero
void setZero(Poly &f) const
Definition FreeAlgebra.cpp:120
FreeAlgebraElement
Owned Poly value paired with its FreeAlgebra*, providing natural operator-overloaded arithmetic.
Definition FreeAlgebra.hpp:270
FreeAlgebra
Free associative algebra over a coefficient ring: the non-commutative analogue of PolynomialRing.
Definition FreeAlgebra.hpp:69
FreeAlgebraQuotient::setZero
void setZero(Poly &f) const
Definition FreeAlgebraQuotient.cpp:38
FreeAlgebraQuotient::var
void var(Poly &result, int v) const
Definition FreeAlgebraQuotient.cpp:78
FreeAlgebraQuotient::negate
void negate(Poly &result, const Poly &f) const
Definition FreeAlgebraQuotient.cpp:110
FreeAlgebraQuotientElement
Owned Poly value paired with its FreeAlgebraQuotient*, providing operator-overloaded arithmetic for d...
Definition FreeAlgebraQuotient.hpp:164
FreeAlgebraQuotient
Quotient of a FreeAlgebra by a Groebner basis up to a fixed degree bound.
Definition FreeAlgebraQuotient.hpp:76
MemoryBlock::shrinkLastAllocate
std::pair< T *, T * > shrinkLastAllocate(T *begin, T *end, T *newtop)
Definition MemoryBlock.hpp:82
MemoryBlock::allocateArray
std::pair< T *, T * > allocateArray(size_t nelems)
Definition MemoryBlock.hpp:69
MemoryBlock
Thin RAII wrapper around memtailor::Arena providing bump-pointer array allocation with optional mutex...
Definition MemoryBlock.hpp:57
MonomialOrderings::GRevLex2
static MonomialOrdering * GRevLex2(int nvars)
Definition monomial-ordering.cpp:110
MonomialOrderings::GRevLex
static MonomialOrdering * GRevLex(int nvars)
Definition monomial-ordering.cpp:104
MonomialOrderings::GRevLex4
static MonomialOrdering * GRevLex4(int nvars)
Definition monomial-ordering.cpp:116
MonomialOrderings::GroupLex
static MonomialOrdering * GroupLex(int nvars)
Definition monomial-ordering.cpp:145
MonomialOrderings::Lex
static MonomialOrdering * Lex(int nvars)
Definition monomial-ordering.cpp:92
MonomialOrderings::toString
static std::string toString(const MonomialOrdering *mo)
Definition monomial-ordering.cpp:293
MonomialOrderings::join
static MonomialOrdering * join(const std::vector< MonomialOrdering * > &M)
Definition monomial-ordering.cpp:206
NCGroebner::createOverlapPoly
static auto createOverlapPoly(const FreeAlgebra &A, const PolyList &polyList, int polyIndex1, int polyIndex2, int overlapIndex) -> Poly *
Definition NCGroebner.cpp:351
NCGroebner
One-overlap-at-a-time Groebner basis driver for the free associative algebra (the "Naive" companion t...
Definition NCGroebner.hpp:69
OverlapTable::insert
auto insert(int deg, bool isGenerator, Overlap o) -> void
Definition OverlapTable.cpp:7
OverlapTable::isFinished
auto isFinished() const -> bool
Definition OverlapTable.cpp:27
OverlapTable::size
auto size() const -> size_t
Definition OverlapTable.cpp:50
OverlapTable
Per-degree FIFO queue of pending overlaps for the NC Groebner basis driver to process.
Definition OverlapTable.hpp:76
Ring::from_long
virtual ring_elem from_long(long n) const =0
TrivialPolynomialHeap
Baseline PolynomialHeap implementation that simply accumulates the pending sum in a single Poly and w...
Definition NCReduction.cpp:163
Word::begin
const int * begin() const
Definition Word.hpp:72
Word::end
const int * end() const
Definition Word.hpp:73
Word
Non-owning view of a non-commutative word: [begin, end) of int variable indices.
Definition Word.hpp:56
WordTable::monomialCount
size_t monomialCount() const
Definition WordTable.hpp:100
WordTable::superwords
void superwords(Word word, std::vector< std::pair< int, int > > &output) const
Definition WordTable.cpp:176
WordTable::isPrefix
bool isPrefix(Word word, int &output) const
Definition WordTable.cpp:133
WordTable::isSuffix
bool isSuffix(Word word, int &output) const
Definition WordTable.cpp:147
WordTable::subwords
void subwords(Word word, std::vector< std::pair< int, int > > &output) const
Definition WordTable.cpp:118
WordTable::isNontrivialSuperword
auto isNontrivialSuperword(Word word, int index1, int index2) const -> bool
Definition WordTable.cpp:191
WordTable::leftOverlaps
void leftOverlaps(std::vector< Overlap > &newLeftOverlaps) const
Definition WordTable.cpp:227
WordTable::insert
size_t insert(Word w)
Definition WordTable.cpp:17
WordTable
Index of Words (non-commutative monomials) with subword, prefix/suffix, and overlap lookup used by th...
Definition WordTable.hpp:89
buffer::str
char * str()
Definition buffer.hpp:72
error_message
const char * error_message()
Definition error.c:49
error
int error()
Definition error.c:48
monoid.hpp
Monoid — variable count, naming, grading, and monomial order of a polynomial ring.
moIsLex
int moIsLex(const MonomialOrdering *mo)
Definition monomial-ordering.cpp:374
moIsGRevLex
int moIsGRevLex(const MonomialOrdering *mo)
Definition monomial-ordering.cpp:401
rawNumberOfVariables
int rawNumberOfVariables(const MonomialOrdering *mo)
Definition monomial-ordering.cpp:431
monordering.hpp
MonomialOrderings — C++ factories for the declarative MonomialOrdering blocks.
x
volatile int x
Definition overflow-test.cpp:68
poly.hpp
Concrete commutative PolyRing — standard polynomial ring inheriting from PolyRingFlat.
G
tbb::flow::graph G
Definition res-tasking-example.cpp:46
ring.h
Engine-boundary C API for the legacy Ring hierarchy — coefficient, polynomial, and composite rings.
MonomialOrdering
Front-end-side description of a monomial ordering as a list of mon_part blocks.
Definition monomial-ordering.h:100
EQ
const int EQ
Definition style.hpp:40
GT
const int GT
Definition style.hpp:41
LT
const int LT
Definition style.hpp:39
degreeRing
const PolynomialRing * degreeRing(const std::vector< std::string > &names)
Definition util-polyring-creation.cpp:49
util-polyring-creation.hpp
One-line helpers for building degree monoids and polynomial rings inside gtest cases.