Google Summer of Code 2023

Final submission

Project description

Enhancements in linear algebra in SageMath

Mentor: M. Vincent NEIGER (Sorbonne Université)

SageMath incorporates state-of-the-art libraries for exact linear algebra computations, such as matrix multiplication, reduced echelon form, linear system solving, when the coefficients are in an exact domain such as the integers or finite fields.

However, several aspects make the integration of these libraries not yet fully satisfactory. For example, working over a prime field with a prime below about 20 bits, the mere creation of a zero matrix in SageMath takes roughly as long as the call of the underlying fast reduced echelon form procedure (performed by LinBox / FFLAS-FFPACK in this case). Still about FFLAS-FFPACK: several available tools in this library are not offered through the SageMath interface, constraining the user experience; for example, some pivoting strategies are not available, despite their usefulness in some situations e.g. when one is interested in the preservation of some rank profile properties. Finally, the integration of linear algebra implementations from Flint has been initiated, with a good amount of work already done, but is not fully finalized and has not been merged into SageMath.

This project aims to make this kind of enhancements, which would lead to more efficient and more versatile finite field linear algebra operations in SageMath.


Link to the forked repository:

Updated the value of MAX_MODULUS of Matrix_modn_dense_template matrices

Related issues:

Accelerated the zero matrix creation

Related issues:

Speeded-up the creation of submatrices of Matrix_modn_dense_template matrices

What is left to do

The matrix creation issue took longer than expected. Although we are satisfied with the amount of enhancements done this summer, there are remaining issues to be treated given the original project proposal.

Additional content

Internship report: contains detailed descriptions of the enhancements listed above. (added on Oct. 30, 2023)