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.

Contribution

Link to the forked repository: https://github.com/marizee/sage

Updated the value of MAX_MODULUS of Matrix_modn_dense_template matrices

• (Merged) PR #35752: Clarification on the MAX_MODULUS of float matrices modulo n.
• (Merged) PR #35855: Extend MAX_MODULUS of matrix_modn_dense_double.pyx.

Related issues:

• Issue #35365: Misleading maximum n value in docstring of matrix_modn_dense_float.pyx. (Closed)
• Issue #35806: Extend MAX_MODULUS for matrix_modn_dense_double.pyx from 23 bits to 27 bits. (Closed)

Accelerated the zero matrix creation

• (Merged) PR #36068: Speed-up matrix construction by ensuring MatrixArgs type MA_ENTRIES_ZERO. submitted by my mentor
• (Merged) PR 36093: Speed-up the creation of a zero matrix of type Matrix_modn_dense_template.

Related issues:

• Issue #36065: Matrix creation from a scalar fails in some cases. (Closed)
• Issue #28432: Speed-up constructor of Matrix_modn_dense_template. (Closed)
• Issue #35961: Accelerating the construction of matrices of type Matrix_modn_dense. (Closed)
• Issue #36104: Matrix construction over prime field fails for some types of inputs. (Open)
  small bug detected during the study of zero matrix creation

Speeded-up the creation of submatrices of Matrix_modn_dense_template matrices

• (Merged) PR #36059: Speed 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.

• Handle the small bug in Issue #36104
• Resolve Issue #36146.
• Incorporate additional FFLAS-FFPACK or Flint routines/functionalities into SageMath, such as pivoting strategies.
• Improve sparse matrices computations.

Additional content

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