Groebner bases for exterior algebras native to Sage

[trevorkarn]

Add a native Sage implementation to compute a Groebner basis for an ideal of a Sage ExteriorAlgebra

Depends on #32369

CC: @tscrim @simon-king-jena

Component: algebra

Keywords: groebner basis, gsoc2022, f4

Author: Trevor K. Karn, Travis Scrimshaw

Branch/Commit: 36b6b20

Reviewer: Travis Scrimshaw, Trevor K. Karn

Issue created by migration from https://trac.sagemath.org/ticket/34138

[trevorkarn]

Last 10 new commits:

b2f9f50	Fix sign error
1550f9d	Fix coboundary on basis
b3ed980	Clean up code a bit
fff9062	Add doctest
9e19f79	All tests pass
001b3c7	Add doctest
1601588	Rewrite multiplication
a34ae96	Merge branch 'u/tkarn/32369-exterior-rewrite-v2' of trac.sagemath.org:sage into exterior-main
697104c	Fix merge error
d24c5fc	Initial commit of f4

[trevorkarn]

Commit: d24c5fc

[trevorkarn]

Branch: u/tkarn/exterior-gb-34138

[trevorkarn]

Dependencies: #32369

[tscrim]

Changed commit from d24c5fc to 9accac5

[tscrim]

Changed branch from u/tkarn/exterior-gb-34138 to public/algebras/exterior_groebner-34138

[tscrim]

New commits:

e94fc2f	Merge branch 'u/tkarn/exterior-gb-34138' of https://github.com/sagemath/sagetrac-mirror into u/tkarn/exterior-gb-34138
9accac5	Another implementation of Groebner bases for the exterior algebra.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. New commits:

71113fa

Fixing some little details.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 9accac5 to 71113fa

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. New commits:

b0f66e3	Cythonizing the element classes.
74490ce	Adding more type declarations and renaming the Groebner file.
04dc914	Initial version of GB strategy file for exterior algebra.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 71113fa to 04dc914

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 04dc914 to bf0e673

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. New commits:

bf0e673

Implementing different term orders for GB.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. New commits:

be68f0d

Fixing some things and tests.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from bf0e673 to be68f0d

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from be68f0d to 43045cc

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. New commits:

63787c4	Bringing more to the GB strategy classes.
43045cc	Implementing containment of ideals, mostly.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 43045cc to 6480faa

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. This was a forced push. Last 10 new commits:

7a79608	Another implementation of Groebner bases for the exterior algebra.
c8a3766	Fixing some little details.
b62d578	Cythonizing the element classes.
d91a556	Adding more type declarations and renaming the Groebner file.
3a9d790	Initial version of GB strategy file for exterior algebra.
368491c	Implementing different term orders for GB.
f2a25e3	Fixing some things and tests.
dba5089	Bringing more to the GB strategy classes.
2362a63	Implementing containment of ideals, mostly.
6480faa	Rebase off of 9.7.beta6 and fix merge conflicts

[trevorkarn]

comment:10

All tests still pass in clifford_algebra.py and clifford_algebra_element.pyx.

[trevorkarn]

comment:11

There appears to be a bug in the following example

sage: E.<x,y> = ExteriorAlgebra(QQ)
sage: I = E.ideal([x * y - 1, x * y - x])
sage: I.groebner_basis()

where it gets stuck in an infinite while loop on line 206 of exterior_algebra_groebner.pyx. For comparison,

i2 : QQ[x,y, SkewCommutative=>true]
o2 = QQ[x, y]
o2 : PolynomialRing, 2 skew commutative variables
i3 : I = ideal( x*y - 1, x*y - x)
o3 = ideal (x*y - 1, x*y - x)
o3 : Ideal of QQ[x, y]
i4 : groebnerBasis(I)
o4 = | 1 |
                      1                1
o4 : Matrix (QQ[x, y])  <--- (QQ[x, y])

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 6480faa to b3ef1f7

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. New commits:

e95c546	Add examples
b3ef1f7	Fix matrix indexing

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. New commits:

59a30c1	Merge branch 'public/algebras/exterior_groebner-34138' of https://github.com/sagemath/sagetrac-mirror into public/algebras/exterior_groebner-34138
b6174b4	Merge branch 'u/tkarn/32369-exterior-rewrite-v2' of https://github.com/sagemath/sagetrac-mirror into public/algebras/exterior_algebra_index_set-32369
a325339	Doing some reviewer changes.
47281fa	Merge branch 'public/algebras/exterior_algebra_index_set-32369' into public/algebras/exterior_groebner-34138
692f2f5	Fixing containment and reduction of exterior algebra ideals.
6c92f18	Implementing multiplication of exterior algebra ideals.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from b3ef1f7 to 6c92f18

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 6c92f18 to 698e051

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. New commits:

698e051

Some last details for pyflakes and full coverage.

[tscrim]

comment:15

I rebased this over my changes in #32369, fixed the comparison of ideals, and implemented multiplication of ideals. This is all of the low hanging fruit that I can see from a GB implementation. I think this is ready for review. I have looked at your changes, and I think they are good. All that remains is for you to check mine.

[tscrim]

Reviewer: Travis Scrimshaw, Trevor K. Karn

[tscrim]

Changed author from Trevor K. Karn to Trevor K. Karn, Travis Scrimshaw

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. New commits:

12d76e7

Revert change in morphisms

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 698e051 to 12d76e7

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 12d76e7 to eada96a

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. New commits:

ea9610d	Caching the leading support FrozenBitset and Integer.
eada96a	Merge branch 'public/algebras/exterior_groebner-34138' of https://github.com/sagemath/sagetrac-mirror into public/algebras/exterior_groebner-34138

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from eada96a to d21d2e8

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. New commits:

d21d2e8

Forgot to remove the Cython profiling directive.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from d21d2e8 to 5734555

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. New commits:

5734555

Fixing a number of small bugs and adding option for non-reduced GB.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. New commits:

c01586d	Revert with_basis/morphism.py.
8b777a0	Fixing up doctests and some other compatibility issues.
ae696db	Merge branch 'public/algebras/exterior_algebra_index_set-32369' into public/algebras/exterior_groebner-34138

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 5734555 to ae696db

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. New commits:

2637750	Small doc tweak.
da58876	Merge branch 'public/algebras/exterior_algebra_index_set-32369' into public/algebras/exterior_groebner-34138
140ac6c	Migration of RAAG cohomology to Cython.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from ae696db to 140ac6c

[tscrim]

comment:22

This should fix the remaining doctest failures in groups/raag.py. The issue was that we can't override cdef _mul_ with def _mul_. That cohomology ring has a simple description of an exterior algebra modulo relations of the form e_i ^ e_j = 0. So that implementation likely could be improved as well, but that can be done on a followup ticket.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 140ac6c to b227973

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. New commits:

b227973

Speeding up multiplication even further.

[tscrim]

comment:24

These changes now make this multiplication test twice as fast:

sage: E = ExteriorAlgebra(QQ, 'x', 10)
sage: r = sum(E.basis())
sage: %timeit r * r
57.2 ms ± 842 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)

versus before

129 ms ± 700 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. New commits:

e7e84b7

Special casing multiplication by a term.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from b227973 to e7e84b7

[tscrim]

comment:26

Here is an improvement to multiplication by a single term:

sage: %timeit a * r
2.4 µs ± 34.9 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)
sage: %timeit r * a
4.88 µs ± 76.6 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)
sage: %timeit E(2) * r
5.51 µs ± 41.2 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)
sage: %timeit r * E(2)
5.63 µs ± 63.1 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)
sage: %timeit E(0) * r
1.05 µs ± 7.86 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
sage: %timeit r * E(0)
1.02 µs ± 5.09 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)

versus b227973:

5.09 µs ± 64.5 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)
6.43 µs ± 19.7 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)
5.17 µs ± 19.9 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)
8.1 µs ± 33.9 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)
1.34 µs ± 6.96 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
1.76 µs ± 13.4 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)

The difference with the left versus right is because we do not choose which term to slide past the other. We can maybe address that here, along with removing the code duplication I have introduced.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. New commits:

36b6b20

Doing reduction in place; being careful about duplicates.