|
Size: 3666
Comment:
|
Size: 5267
Comment:
|
| Deletions are marked like this. | Additions are marked like this. |
| Line 3: | Line 3: |
| == Standard == | == Standard as of Version 5.0 == |
| Line 9: | Line 9: |
| ||<:> $\mathbb{Z}_p$, $2<p$ very small || [[http://www.linalg.org|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$, $2<p$ very small || [[http://www.linalg.org|LinBox]] || 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. || || || |
| Line 13: | Line 13: |
| ||<:> $\mathbb{Z}$ || [[http://www.linalg.org|LinBox]], [[http://pari.math.u-bordeaux.fr/|Pari]], [[http://www.cs.uwaterloo.ca/~astorjoh/iml.html|IML]], [[http://www.shoup.net/ntl/|NTL]], custom code || Generally decent. Fastest known Hermite Normal Form. || || || ||<:> $\mathbb{R}$ || NumPy || || || || ||<:> $\mathbb{C}$ || NumPy || || || || |
||<:> $\mathbb{Z}$ || [[http://www.linalg.org|LinBox]], [[http://pari.math.u-bordeaux.fr/|Pari]], [[http://www.cs.uwaterloo.ca/~astorjoh/iml.html|IML]], [[http://www.shoup.net/ntl/|NTL]], custom code || Decent. Fastest known Hermite Normal Form. || || || ||<:> $\mathbb{R}$, $\mathbb{C}$, 53-bit || `SciPy`, `NumPy` || Rings `RDF` and `CDF` in Sage are floating point doubles. Performance comes from standard underlying libraries through Sage wrappers of `SciPy`/`NumPy` wrappers and interfaces. || Not every desirable function has been implemented, but coverage is steadily increasing. || || ||<:> $\mathbb{R}$, $\mathbb{C}$, arbitrary precision || generic || Rings `RealField(prec)` and `ComplexField(prec)` in Sage support arbitrary precision, but default to 53-bit when used as `RR` and `CC`. Implementation often (always?) defaults to exact algorithms. || Using exact algorithms for approximate entries can provide misleading results if not interpreted properly. || || |
| Line 17: | Line 17: |
| ||<:> $\mathbb{K}[x]$ || Generic || || || || |
|||||||||| '''Symbolic Rings''' || ||<:> $\mathbb{K}[x]$ || generic || || || || ||<:> $\mathbb{K}[x_0,\dots,x_{n-1}]$ || generic,[[http://singular.uni-kil.de|Singular]] || Generic matrices with some routines ({{{det}}}, {{{echelon_form}}}) calling libSingular. Poor performance, but apparently comparable to what other systems offer. || This implementation is not a serious attempt to implement matrices over $\mathbb{K}[x_0,\dots,x_{n-1}]$. || || ||<:> Symbols || generic,[[http://maxima.sourceforge.net/|Maxima]] || Generic matrices with some routines calling Maxima. Poor performance, but apparently comparable to what other systems offer. || || || |
| Line 29: | Line 31: |
| ||<:> $\mathbb{Z_p}$ for $p < 2^{64}$ || [[http://www.flintlib.org/|FLINT 2.3]] || Decent, not fully optimised. || || || ||<:> $\mathbb{Z}[x]$ || [[http://www.flintlib.org/|FLINT 2.3]] || Decent, not fully optimised. || || || ||<:> $\mathbb{Z_p}[x]$ for $p < 2^{64}$ || [[http://www.flintlib.org/|FLINT 2.3]] || Decent, not fully optimised. || || || |
The state of dense linear algebra in Sage
Standard as of Version 5.0
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 |
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. |
|
|
Infinite Rings |
||||
\mathbb{Q} |
Decent |
|
|
|
\mathbb{Z} |
Decent. Fastest known Hermite Normal Form. |
|
|
|
\mathbb{R}, \mathbb{C}, 53-bit |
SciPy, NumPy |
Rings RDF and CDF in Sage are floating point doubles. Performance comes from standard underlying libraries through Sage wrappers of SciPy/NumPy wrappers and interfaces. |
Not every desirable function has been implemented, but coverage is steadily increasing. |
|
\mathbb{R}, \mathbb{C}, arbitrary precision |
generic |
Rings RealField(prec) and ComplexField(prec) in Sage support arbitrary precision, but default to 53-bit when used as RR and CC. Implementation often (always?) defaults to exact algorithms. |
Using exact algorithms for approximate entries can provide misleading results if not interpreted properly. |
|
\mathbb{Q}(\zeta_n) |
special code |
Optimized multi-modular algorithms for arithmetic, charpoly, echelon form over cyclotomic fields. |
|
|
Symbolic Rings |
||||
\mathbb{K}[x] |
generic |
|
|
|
\mathbb{K}[x_0,\dots,x_{n-1}] |
generic,Singular |
Generic matrices with some routines (det, echelon_form) calling libSingular. Poor performance, but apparently comparable to what other systems offer. |
This implementation is not a serious attempt to implement matrices over \mathbb{K}[x_0,\dots,x_{n-1}]. |
|
Symbols |
generic,Maxima |
Generic matrices with some routines calling Maxima. Poor performance, but apparently comparable to what other systems offer. |
|
|
Provided by Optional Packages
Base Ring |
Libraries |
Overview |
Known Limitations |
Tickets |
\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 |
In the Pipeline
Base Ring |
Libraries |
Overview |
Known Limitations |
Tickets |
\mathbb{F}_{p^k} |
Custom code |
Matrices over extension fields are represented as tuples of matrices over the prime subfield. Then, using polynomial multiplication with matrix coefficients allows to multiply matrices. Other algorithms are implemented by reducing to matrix-matrix multiplication. |
Only matrix-matrix multiplication is implemented so far. |
|
\mathbb{Z_p} for p < 2^{64} |
Decent, not fully optimised. |
|
|
|
\mathbb{Z}[x] |
Decent, not fully optimised. |
|
|
|
\mathbb{Z_p}[x] for p < 2^{64} |
Decent, not fully optimised. |
|
|