Opened 12 years ago
Last modified 5 years ago
#11161 new enhancement
New classes for matrices and vectors over Z/NZ with N >= 46341
Reported by: | David Roe | Owned by: | jason, was |
---|---|---|---|
Priority: | major | Milestone: | sage-6.4 |
Component: | linear algebra | Keywords: | padics, modular arithmetic |
Cc: | Jason Grout, Clément Pernet | Merged in: | |
Authors: | David Roe | Reviewers: | |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description
Sage currently has specialized classes for matrices and vectors over Z/nZ with n < 46341, used for multi-modular algorithms over Z. Once this boundary is passed, performance drops off.
This ticket aims to implement an analogous class for larger N, using an array of mpz_t's as the underlying representation.
One of the benefits is speed: determinants in particular should show a big speedup.
Change History (7)
comment:1 Changed 12 years ago by
Cc: | Jason Grout added |
---|
comment:2 Changed 9 years ago by
Milestone: | sage-5.11 → sage-5.12 |
---|
comment:3 Changed 9 years ago by
Milestone: | sage-6.1 → sage-6.2 |
---|
comment:4 Changed 9 years ago by
Milestone: | sage-6.2 → sage-6.3 |
---|
comment:5 Changed 8 years ago by
Milestone: | sage-6.3 → sage-6.4 |
---|
comment:6 Changed 7 years ago by
Cc: | Clément Pernet added |
---|
comment:7 Changed 5 years ago by
Note: See
TracTickets for help on using
tickets.
Diging out this outdated ticket. Things have changed many times since then, so it might be relevant to close it. However, there still remain an issue at the border when fflas-ffpack being used for matrix_modn_dense.
In the following experiments:
one sees the threshold near 8 bits for the switch from float to double, and the threshold of 23bits when the generic implementation gets used. There is a 40x slowdown there, which is a shame.
To smooth things out, one could consider,