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: https://github.com/marizee/sage
Updated the value of
- (Merged) PR #35752: Clarification on the
MAX_MODULUSof float matrices modulo
- (Merged) PR #35855: Extend
- Issue #35365: Misleading maximum
nvalue in docstring of
- Issue #35806: Extend
matrix_modn_dense_double.pyxfrom 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
- 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
- (Merged) PR #36059: Speed up the creation of submatrices of
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.
Internship report: contains detailed descriptions of the enhancements listed above. (added on Oct. 30, 2023)