Opened 9 years ago

Last modified 5 years ago

## #12103 closed defect

# Use MeatAxe as an optional back end for dense matrices over `GF(p^n)`, p odd, n>1, `p^n<255` — at Initial Version

Reported by: | SimonKing | Owned by: | jason, was |
---|---|---|---|

Priority: | major | Milestone: | sage-7.0 |

Component: | packages: optional | Keywords: | linear algebra, MeatAxe |

Cc: | malb, jdemeyer, vbraun | Merged in: | |

Authors: | Simon King | Reviewers: | |

Report Upstream: | Reported upstream. No feedback yet. | Work issues: | |

Branch: | Commit: | ||

Dependencies: | #9562 #4260 | Stopgaps: |

### Description

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) <type 'sage.matrix.matrix_generic_dense.Matrix_generic_dense'> 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) <type 'sage.matrix.matrix_modpn_dense.Matrix_modpn_dense'> 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 the optional libmeataxe spkg
- Apply either attachment or attachment, depending on whether or not you have #11900 applied.

**Note:**See TracTickets for help on using tickets.