Papers for

computational algebra software developers

Papers whose findings have a practical use for this group, as judged from the abstract. Open a paper to read what it means in practice.

Algorithm speeds up algebra calculations using parallel computing

Schreyer Resolutions over the Exterior Algebra

Abstract: Schreyer's algorithm is usually the fastest way to determine a (typically non-minimal) free resolution of a finitely presented module over a polynomial ring. We adapt a refined version of Schreyer's algorithm to compute free resolutions over the exterior algebra, relying on relative Groebner bases. We illustrate the use of our algorithm for the computation of cohomology of coherent sheaves over projective space, which by the BGG correspondence can be computed via free resolutions over the exterior algebra. Schreyer's method relies on a tree traversal and thus has the potential for parallel computations. We report on ongoing work on a massively parallel implementation, observing that Gnawali's parallel approach over polynomial rings can be carried over to our setting.

Tue 29 SeptSymbolic Computation
The gist
Calculating certain algebraic structures called free resolutions is important but can be slow. The authors adapted a known fast method, Schreyer's algorithm, to work for a different kind of algebra called the exterior algebra. They also explore ways to speed up the calculations by running parts in parallel on multiple processors. This helps compute properties connected to shapes and spaces studied in geometry.
Open → 2609.37610v1

Efficient test and factorization of small nonnegative integer matrices

Factorisability of Low Dimensional Non-Negative Integer Matrices

Abstract: We consider the problem of determining if a given two-dimensional nonnegative integer matrix $M$ is the product of two such matrices, excluding trivial units. A matrix $M$ with no such factorisation is called prime and therefore belongs to the minimal (infinite rank) generator of $2 \times 2$ matrices over the natural numbers, otherwise it is called composite. We also consider the problem of finding a (non-unique) factorisation of a composite matrix. Our results have applications in computational group theory and the theory of codes, where such matrices are called incidence matrices. We analyse the complexity of primality and finding a factorisation for a composite matrix, providing a first efficient algorithm.

Tue 22 SeptDiscrete MathematicsData Structures and AlgorithmsInformation Theory
The gist
This paper looks at how to tell if a grid of whole numbers can be split into the product of two smaller such grids, ignoring simple cases. If it can’t be split, it’s called prime; if it can, it’s composite. The authors also provide a way to find such a split when it exists. Their work is useful in areas like group theory and code design, where these grids represent connections or relationships. They also offer an efficient method to do these tests and factorizations.
Open → 2609.26033v1