id summary reporter owner description type status priority milestone component resolution keywords cc merged author reviewer upstream work_issues branch commit dependencies stopgaps
12103 Use MeatAxe as an optional back end for dense matrices over `GF(p^n)`, p odd, n>1, `p^n<255` SimonKing jason was "Sage has (or will soon have) fairly good implementations of dense matrices over `GF(2)`, over `GF(2^e)` (#9562) and over `GF(p)` (p prime, #4260). However, it uses generic code for dense matrices over `GF(p^n)`, p odd, n>1, `p^n<255`.
I suggest to use a major modification of `MeatAxe Release 2.2.4` instead of the basic implementation. More on the modifications and the reason for choosing an old release is explained in the comments.
This is awfully slow:
{{{
sage: MS = MatrixSpace(GF(5^3,'y'),2000)
sage: %time A = MS.random_element()
CPU times: user 6.36 s, sys: 0.02 s, total: 6.39 s
Wall time: 6.41 s
sage: type(A)
sage: B = MS.random_element()
sage: %time A*B # using 6.3% of my computer's memory
CPU times: user 744.20 s, sys: 1.18 s, total: 745.38 s
Wall time: 747.69 s
2000 x 2000 dense matrix over Finite Field in y of size 5^3
sage: %time ~A # using 10.4% of my computer's memory
CPU times: user 1096.74 s, sys: 1.30 s, total: 1098.05 s
Wall time: 1101.24 s
2000 x 2000 dense matrix over Finite Field in y of size 5^3
sage: %time A.echelon_form() # using 10.4% of my computer's memory
CPU times: user 378.62 s, sys: 0.33 s, total: 378.95 s
Wall time: 380.06 s
2000 x 2000 dense matrix over Finite Field in y of size 5^3
}}}
With the optional spkg and the patch, one gets a clear improvement.
{{{
sage: MS = MatrixSpace(GF(5^3,'y'),2000)
sage: %time A = MS.random_element()
CPU times: user 0.32 s, sys: 0.00 s, total: 0.32 s
Wall time: 0.33 s
sage: type(A)
sage: B = MS.random_element()
# The following uses Strassen-Winograd multiplication
sage: %time A*B # using 3.5% of my computer's memory
CPU times: user 7.68 s, sys: 0.01 s, total: 7.69 s
Wall time: 7.72 s
2000 x 2000 dense matrix over Finite Field in y of size 5^3
# The following is school book multiplication;
# that's more or less the original meataxe speed:
sage: %time A._multiply_classical(B) # using 3.6% of my computer's memory
CPU times: user 11.68 s, sys: 0.02 s, total: 11.70 s
Wall time: 11.73 s
2000 x 2000 dense matrix over Finite Field in y of size 5^3
# Strassen is not implemented for inversion and echelon form.
sage: %time ~A # using 3.8% of my computer's memory
CPU times: user 23.55 s, sys: 0.00 s, total: 23.55 s
Wall time: 23.62 s
2000 x 2000 dense matrix over Finite Field in y of size 5^3
sage: %time A.echelon_form() #using 3.9% of my computer's memory
CPU times: user 11.73 s, sys: 0.01 s, total: 11.74 s
Wall time: 11.78 s
2000 x 2000 dense matrix over Finite Field in y of size 5^3
}}}
I think the component is ""linear algebra"", even though it is about an optional package.
'''__How to install stuff__'''
* Apply the dependencies
* Install [http://sage.math.washington.edu/home/SimonKing/LibMeatAxe/libmeataxe-1.0.spkg the optional libmeataxe spkg]
* Apply either [attachment:trac12103_meataxe.patch] or [attachment:trac12103_meataxe_rel11900.patch], depending on whether or not you have #11900 applied." defect needs_review major sage-5.11 linear algebra linear algebra, MeatAxe mringe@… malb david.green@… Simon King None of the above - read trac for reasoning. #9562 #4260