The state of dense linear algebra in Sage
Finite Rings |
||||
Base Ring |
Libraries |
Overview |
Known Limitations |
Tickets |
\mathbb{F}_2 |
Sage has the fastest known implementation. Matrix-matrix multiplication is either as fast as Magma 2.17 or slightly faster. Gaussian elimination is faster than Magma 2.17. |
Some functions might fall back to their generic implementations because M4RI either does not implement it or its implementation is not wrapped |
|
|
\mathbb{F}_{2^e} for 2 \leq e \leq 10 |
Sage has by far the fastest known implementation. |
Many functions might fall back to their generic implementations because M4RIE either does not implement it or its implementation is not wrapped. Sage uses M4RIE's mzed_t but using mzd_slice_t would be slightly faster and save memory. |
|
|
\mathbb{Z}_p, 2<p very small |
LinBox, custom code |
Sage achieves decent performance, but Magma 2.17 is faster for small values. Also, (experimental) specialised implementations exist which beat both by a large margin. |
|
|
\mathbb{Z}_p, p<2^{22} |
Sage achieves decent performance on par with Magma 2.17. Performance differences likely come down to the BLAS used in both systems. |
Some functions fall back to their generic implementations because LinBox either does not implement it, or the implementation was not wrapped yet. Also, echelonize uses way too much memory because it copies the matrix being worked on due to a function missing in LinBox. |
|
|
\mathbb{F}_{p^k}, p^k<255 |
MeatAxe fork |
The fork adds Winograd-Strassen multiplication to the original MeatAxe. The computation of echelon forms is not asymptotically fast, but is faster than the generic implementation in Sage. |
Patch needs review |
|
\mathbb{F}_{p^k} |
Generic |
Very poor performance |
|
|
Infinite Rings |
||||
\mathbb{Q} |
LinBox,Pari,IML |
Decent |
|
|
\mathbb{Z} |
LinBox,Pari,IML,NTL,Sage |
Decent. Fastest known Hermite Normal Form. |
|
|
\mathbb{R} |
|
|
|
|
\mathbb{C} |
|
|
|
|
\mathbb{Q}(\zeta_n) |
special code |
Optimized multi-modular algorithms for for arithmetic, charpoly, echelon form over cyclotomic fields. |
|
|
\mathbb{K}[x] |
Generic |
|
|
|