Implement custom matrix-type row reduction scheme for exterior algebra Gröbner basis

[tscrim]

This is the main bottleneck in the the Gröbner basis code implemented in #34138. Sage's implementation is very inefficient (at least over QQ) as it creates a dense copy (when sparse, which the implementation in #34138 uses) and then does the row reduction on that. Doing the row reduction on that matrix also produces a copy that is then entry-wise copied back into the original matrix!

We implement a custom version of row reduction tailored to the GB computation. We also become very careful about our data structure:

We realize the matrix as a dictionary of the leading supports whose elements are lists of elements of the exterior algebra with that leading support. This way we do not need to create a lot of transient elements. It also makes swapping rows much faster and makes it clear which rows should do the reduction. This effectively "triangularizes" the matrix too.

Depends on #34138

CC: @trevorkarn

Component: linear algebra

Keywords: Gröbner basis, exterior algebra

Author: Travis Scrimshaw

Branch/Commit: public/algebras/improve_gb_echelon-34437 @ c40f258

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

[tscrim]

Author: Travis Scrimshaw

[tscrim]

Commit: c40f258

[tscrim]

Branch: public/algebras/improve_gb_echelon-34437

[tscrim]

comment:1

Here is my first attempt, which does seem to improve the speed that it does the linear algebra. There probably are much smarter things that could be done here, but even a naïve version over QQ helps quite a bit, at least for the larger case from the ~7s in M2 test noted in #34138. At least I am getting to the 105 x 256 matrix much faster, but it still is taking ages to do the computation.

I suspect you are correct that a much smarter selection algorithm is the key to getting the speed close to M2 speed.

---

Last 10 new commits:

ae696db	Merge branch 'public/algebras/exterior_algebra_index_set-32369' into public/algebras/exterior_groebner-34138
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.
b227973	Speeding up multiplication even further.
e7e84b7	Special casing multiplication by a term.
36b6b20	Doing reduction in place; being careful about duplicates.
8d30012	Merge branch 'develop' into public/algebras/exterior_algebra_index_set-32369
f169b4e	Merge branch 'public/algebras/exterior_algebra_index_set-32369' into public/algebras/exterior_groebner-34138
c40f258	Initial custom matrix reduction implementation for exterior algebra GBs.

[tscrim]

F4 algorithm Peifer note

[tscrim]

comment:2

Attachment: math6140-2017a.pdf.gz

From Sectino 2.2.3 in the attached Peifer note, it seems like there is a much smarter algorithm that can be done. We can also reduce the computation to something involving more dense-like matrices too. So we have to pay some element conversions, but this seems small in comparison to the actual linear algebra involved.