Opened 23 months ago
Last modified 4 days ago
#31548 needs_work enhancement
Create matrix class for FLINT's nmod_mat module
Reported by: | roed | Owned by: | |
---|---|---|---|
Priority: | major | Milestone: | |
Component: | linear algebra | Keywords: | |
Cc: | edgarcosta | Merged in: | |
Authors: | David Roe, Edgar Costa | Reviewers: | Travis Scrimshaw |
Report Upstream: | N/A | Work issues: | |
Branch: | u/roed/nmod_mat (Commits, GitHub, GitLab) | Commit: | a3c8e38bc674e3e7fa8c93ab04f71548fd28aac8 |
Dependencies: | #31069 | Stopgaps: |
Description (last modified by )
This tickets adds a new class for dense matrices over Zmod(N)
implemented using FLINT's nmod_mat_t
type, along with some supporting ancillary changes:
- Changed echelon form over
Zmod(N)
for compositeN
to return the Howell form (see the introduction and Chapter 4 of Storjohann's thesis). Since this echelon form can have more rows than the input matrix, made some supporting changes including a new method_echelon_copy
. - Changed rank over
Zmod(N)
to return the number of leading 1s in Howell form (it raised aNotImplementedError
before), andpivots
to be the locations of these leading 1s. There is also a method_pivots
for accessing the columns where the leading entry is not 1. - Matrices modulo composite
N
have improved speed and functionality for inversion,charpoly
,det
,minpoly
,echelon_form
,solve_right
andright_kernel_matrix
. There is also a new methodminpoly_ideal
for the ideal vanishing on a matrix (the natural generalization of the minimal polynomial, which generates this ideal when it is principal). - Changed
stack
andaugment
to return a matrix over a common base ring of the two inputs, rather than just using the top/left matrix to determine the base ring. - A new method
_change_implementation
on matrices, together with rough heuristics for matrices on matrices modN
in determining when it's worth switching between FLINT and linbox (linbox is faster for large matrices, FLINT for smaller, and FLINT offers extra functionality for matrices modulo composite integers). - Support multiplication of matrices with different implementations
- Add FLINT's
ulong_extras
for number theoretic functions on longs - Add some iterators related to split primes in cyclotomic fields in support of changes to
matrix_cyclo_dense
(which uses a multimodular approach), and moved the_reduction_matrix
method to the base field which will yield better caching behavior. - Fix some doctests that relate to choosing different solutions in
solve_right
and getting different random matrices with a different implementation.
Change History (39)
comment:1 Changed 23 months ago by
Branch: | → u/roed/nmod_mat |
---|
comment:2 Changed 23 months ago by
Commit: | → 763533df7ba71d606038dac0983c5c24165f40f2 |
---|
comment:3 Changed 23 months ago by
Commit: | 763533df7ba71d606038dac0983c5c24165f40f2 → 8cdf9b16b1cd248f211a3d86eec61c30a6ef702b |
---|
Branch pushed to git repo; I updated commit sha1. New commits:
8cdf9b1 | Add some functions to Matrix_nmod_dense
|
comment:4 Changed 23 months ago by
Commit: | 8cdf9b16b1cd248f211a3d86eec61c30a6ef702b → 518a32f9a7b27b0c18d89a2873d6c0139c67efe9 |
---|
comment:5 Changed 23 months ago by
Commit: | 518a32f9a7b27b0c18d89a2873d6c0139c67efe9 → 936668af2821a939e4ae200f384611bf42bd00f5 |
---|
Branch pushed to git repo; I updated commit sha1. New commits:
936668a | Add todos
|
comment:6 Changed 23 months ago by
Commit: | 936668af2821a939e4ae200f384611bf42bd00f5 → aaf0680040c96e439877eac471bd3e2cd4515a94 |
---|
Branch pushed to git repo; I updated commit sha1. New commits:
aaf0680 | Update todo
|
comment:7 Changed 23 months ago by
Commit: | aaf0680040c96e439877eac471bd3e2cd4515a94 → fb023491c50c1097963987e007f5d088e9e73515 |
---|
Branch pushed to git repo; I updated commit sha1. New commits:
fb02349 | Reorder todos
|
comment:8 Changed 23 months ago by
Commit: | fb023491c50c1097963987e007f5d088e9e73515 → cecbe3010e5438cdc77667507fe2dcfb2f170eb3 |
---|
Branch pushed to git repo; I updated commit sha1. New commits:
31d05e4 | inverses, swap rows and columns
|
d69baff | richmp
|
ba439fc | Merge branch 'u/roed/nmod_mat' of git://trac.sagemath.org/sage into nmod_mat
|
9285ed3 | Merge branch 'u/roed/nmod_mat' of git://trac.sagemath.org/sage into nmod_mat
|
6a3d32a | justifying flags
|
a90423a | Merge branch 'u/roed/nmod_mat' of git://trac.sagemath.org/sage into nmod_mat
|
c7c68cd | some progress
|
61821e8 | fixing various things
|
cecbe30 | Merge branch 'u/edgarcosta/nmod_mat' of git://trac.sagemath.org/sage into t/31548/nmod_mat
|
comment:9 Changed 23 months ago by
Commit: | cecbe3010e5438cdc77667507fe2dcfb2f170eb3 → db33b05407674b601d914aa9e13deca6b1280cb2 |
---|
comment:10 Changed 23 months ago by
Milestone: | sage-9.3 → sage-9.4 |
---|
Sage development has entered the release candidate phase for 9.3. Setting a new milestone for this ticket based on a cursory review of ticket status, priority, and last modification date.
comment:11 Changed 23 months ago by
Commit: | db33b05407674b601d914aa9e13deca6b1280cb2 → 3eb1cd4bd49e263e96d86c261d07afa2e7916275 |
---|
Branch pushed to git repo; I updated commit sha1. Last 10 new commits:
33dd395 | comment
|
b922d8e | Merge branch 'u/roed/nmod_mat' of git://trac.sagemath.org/sage into nmod_mat
|
c1961a2 | right kernel matrix
|
b1d5396 | Merge branch 'u/roed/nmod_mat' of git://trac.sagemath.org/sage into nmod_mat
|
b9965be | remove comment
|
1045207 | touch up right kernel
|
fb619b0 | work around echenolize
|
45de1c8 | remove stack
|
bf8aaab | Merge branch 'u/edgarcosta/nmod_mat' of git://trac.sagemath.org/sage into t/31548/nmod_mat
|
3eb1cd4 | Fix import
|
comment:12 Changed 23 months ago by
Dependencies: | → #31069 |
---|
comment:13 Changed 22 months ago by
Commit: | 3eb1cd4bd49e263e96d86c261d07afa2e7916275 → aed23614745507fa84876489c00f5abc77990c72 |
---|
comment:14 Changed 22 months ago by
Commit: | aed23614745507fa84876489c00f5abc77990c72 → 5e9b8a7b06100833a6dc3a1f9efdca7592fbdcb6 |
---|
comment:15 Changed 22 months ago by
Commit: | 5e9b8a7b06100833a6dc3a1f9efdca7592fbdcb6 → fc48eca590a15e596660601f61c4eba80bf1b249 |
---|
Branch pushed to git repo; I updated commit sha1. New commits:
fc48eca | Working on documentation
|
comment:16 Changed 22 months ago by
Commit: | fc48eca590a15e596660601f61c4eba80bf1b249 → 64e44fc055b8a7f2fb69207d5e145771e4e22847 |
---|
Branch pushed to git repo; I updated commit sha1. New commits:
64e44fc | Fixing bugs and adding documentation to matrices mod n
|
comment:17 Changed 22 months ago by
Commit: | 64e44fc055b8a7f2fb69207d5e145771e4e22847 → e5c4c1e1b8dfda617f4b1e16f807ba42807a3387 |
---|
Branch pushed to git repo; I updated commit sha1. New commits:
e5c4c1e | Working on documentation
|
comment:18 Changed 22 months ago by
Commit: | e5c4c1e1b8dfda617f4b1e16f807ba42807a3387 → 1a7bb38565f649d78c24122033a732b517d27f3f |
---|
comment:19 Changed 22 months ago by
Commit: | 1a7bb38565f649d78c24122033a732b517d27f3f → 6f41da9cadc509baa5d221e354a7eaa797574bed |
---|
Branch pushed to git repo; I updated commit sha1. New commits:
6f41da9 | Fixing doctest problems from switching default implementation to flint for small matrices
|
comment:20 Changed 22 months ago by
Authors: | → David Roe, Edgar Costa |
---|---|
Status: | new → needs_review |
Marking for patchbot to test....
comment:21 Changed 22 months ago by
Commit: | 6f41da9cadc509baa5d221e354a7eaa797574bed → 9748ffc23e3e3b163ae65207f1790de020040dda |
---|
comment:22 follow-up: 26 Changed 22 months ago by
If you aren't yet ready for comments, I apologize. However, I made a quick skim over things before I realized you set this as needs review for the patchbot.
For def _change_implementation
, wouldn't it make more sense to be cdef
or cpdef
since it should be called entirely from internal stuff? Also, in that implementation, I don't think we should use self.list()
for spare matrices. I also generally find using sage.matrix.matrix_space.MatrixSpace
unstable and think it is better to have a direct import.
I know you said this is for the patchbot, but it would be good to have doctests for _solve_right_modn
. I would also add
cdef list X cdef Py_ssize_t n
change
- X = self.matrix_space(B.ncols(), self.ncols())(X) - return X.T + return self.matrix_space(B.ncols(), self.ncols())(X).T
(perhaps casting the result as a matrix too), and mark B
as a Matrix
.
I am not sure about the name of the files being matrix_nmod_dense
and the subsequently the name of the class. It conflicts with the matrix_modn_*
files and I feel it is too generic given that it is for a specific implementation.
Why is poly_crt
in the matrix file?
can't
-> cannot
as we want to make the writing formal.
It would be good to implement a get_is_zero_unsafe
method.
comment:23 follow-up: 24 Changed 22 months ago by
No problem! I'm still working on stuff, so comments are easily incorporated. I also realized that the patchbot won't test this since it relies on spkgs until #31069 is merged.
Do you think matrix_modn_flint
and Matrix_modn_flint
would be better?
The poly_crt
function is left over from an earlier implementation of charpoly
or minpoly
(I forget which). I will take care of it.
Thanks!
comment:24 Changed 22 months ago by
Replying to roed:
No problem! I'm still working on stuff, so comments are easily incorporated. I also realized that the patchbot won't test this since it relies on spkgs until #31069 is merged.
Yea, I didn't quite realize that either. ;;
Do you think
matrix_modn_flint
andMatrix_modn_flint
would be better?
The former for the name of the file, the latter for the name of the class considering the other matrix classes in Sage.
Let me know if there is anything I can do to help too.
comment:25 Changed 22 months ago by
Commit: | 9748ffc23e3e3b163ae65207f1790de020040dda → 465f51de75fc202f7c5c9b636e39501e2dda3b0a |
---|
Branch pushed to git repo; I updated commit sha1. New commits:
cd1b853 | Merge branch 'u/roed/nmod_mat' of trac.sagemath.org:sage into t/31548/nmod_mat
|
6e2b75a | Merge branch 'u/roed/nmod_mat' of trac.sagemath.org:sage into t/31548/nmod_mat
|
ee10b06 | Working on documentation and fixing tests
|
465f51d | Working on documentation
|
comment:26 Changed 22 months ago by
Replying to tscrim:
For
def _change_implementation
, wouldn't it make more sense to becdef
orcpdef
since it should be called entirely from internal stuff? Also, in that implementation, I don't think we should useself.list()
for spare matrices. I also generally find usingsage.matrix.matrix_space.MatrixSpace
unstable and think it is better to have a direct import.
Even for a 2 by 2 matrix where the calling overhead is most substantial, changing to cpdef
makes a negligible difference:
sage: A = random_matrix(Zmod(120), 2) sage: A [ 32 108] [ 2 112] sage: %time B = A._change_implementation("linbox") # using def CPU times: user 339 µs, sys: 8 µs, total: 347 µs Wall time: 350 µs
sage: A = random_matrix(Zmod(120), 2) # using cpdef sage: %time B = A._change_implementation("linbox") CPU times: user 334 µs, sys: 5 µs, total: 339 µs Wall time: 343 µs
I don't think it's worth the cost of recompiling everything depending on matrix0.pxd
, and the risk of developers accidentally using def
instead of cpdef
on a matrix class in the future.
I agree about sparse matrices, but currently in sage.matrix.matrix_space.get_matrix_class
we don't allow the implementation
keyword for sparse matrices, so the issue is moot. I'd be happy to have more sparse matrices in Sage eventually, but for now there's no way to even test a version of _change_implementation
in Matrix_sparse
.
I'm not sure what you mean by using sage.matrix.matrix_space.MatrixSpace
unstable. Do you mean switching to from sage.matrix.matrix_space import MatrixSpace
? I was just copying what's done a couple dozen lines above in matrix2.pyx
, but I'm happy to make this change if desired.
I know you said this is for the patchbot, but it would be good to have doctests for
_solve_right_modn
.
Agreed. I've added them.
I would also add
cdef list X cdef Py_ssize_t nchange
- X = self.matrix_space(B.ncols(), self.ncols())(X) - return X.T + return self.matrix_space(B.ncols(), self.ncols())(X).T(perhaps casting the result as a matrix too), and mark
B
as aMatrix
.
I've added the cdef Py_ssize_t n
since that can speed up the loop, and made the change you suggested in the diff. I don't think it's necessary to mark X
as a list or B
as a matrix, since I'm not calling any functions that will benefit from knowing the types (and the runtime is surely dominated by the call to Pari's matsolvemod
)
I am not sure about the name of the files being
matrix_nmod_dense
and the subsequently the name of the class. It conflicts with thematrix_modn_*
files and I feel it is too generic given that it is for a specific implementation.
Agreed. I've changed it to matrix_modn_dense_flint
.
Why is
poly_crt
in the matrix file?
I've created #31731 and removed it from this ticket.
can't
->cannot
as we want to make the writing formal.It would be good to implement a
get_is_zero_unsafe
method.
Both done.
comment:27 Changed 22 months ago by
All tests pass in matrix modules rings modular crypto
. I'm happy to run tests on all of Sage if people are happy with the changes in principle.
comment:28 Changed 22 months ago by
Commit: | 465f51de75fc202f7c5c9b636e39501e2dda3b0a → 760e0c9f68abda66b02dd96f7fd67f9ea9fabe23 |
---|
Branch pushed to git repo; I updated commit sha1. New commits:
760e0c9 | Small fixes
|
comment:29 Changed 22 months ago by
This tickets adds a new class for dense matrices over Zmod(N)
implemented using FLINT's nmod_mat_t
type, along with some supporting ancillary changes:
- Changed echelon form over
Zmod(N)
for compositeN
to return the Howell form (see the introduction and Chapter 4 of Storjohann's thesis). Since this echelon form can have more rows than the input matrix, made some supporting changes including a new method_echelon_copy
. - Changed rank over
Zmod(N)
to return the number of leading 1s in Howell form (it raised aNotImplementedError
before), andpivots
to be the locations of these leading 1s. There is also a method_pivots
for accessing the columns where the leading entry is not 1. - Matrices modulo composite
N
have improved speed and functionality for inversion,charpoly
,det
,minpoly
,echelon_form
,solve_right
andright_kernel_matrix
. There is also a new methodminpoly_ideal
for the ideal vanishing on a matrix (the natural generalization of the minimal polynomial, which generates this ideal when it is principal). - Changed
stack
andaugment
to return a matrix over a common base ring of the two inputs, rather than just using the top/left matrix to determine the base ring. - A new method
_change_implementation
on matrices, together with rough heuristics for matrices on matrices modN
in determining when it's worth switching between FLINT and linbox (linbox is faster for large matrices, FLINT for smaller, and FLINT offers extra functionality for matrices modulo composite integers). - Support multiplication of matrices with different implementations
- Add FLINT's
ulong_extras
for number theoretic functions on longs - Add some iterators related to split primes in cyclotomic fields in support of changes to
matrix_cyclo_dense
(which uses a multimodular approach), and moved the_reduction_matrix
method to the base field which will yield better caching behavior. - Fix some doctests that relate to choosing different solutions in
solve_right
and getting different random matrices with a different implementation.
New commits:
760e0c9 | Small fixes
|
comment:30 Changed 22 months ago by
This ticket is now actually ready for review, though the patchbot won't run currently (since it depends on #31069 which changes spkgs).
comment:31 Changed 22 months ago by
Description: | modified (diff) |
---|
comment:32 Changed 22 months ago by
Cc: | edgarcosta added |
---|
comment:33 Changed 20 months ago by
Reviewers: | → Travis Scrimshaw |
---|---|
Status: | needs_review → needs_work |
Needs rebase.
comment:34 Changed 20 months ago by
Commit: | 760e0c9f68abda66b02dd96f7fd67f9ea9fabe23 → a3c8e38bc674e3e7fa8c93ab04f71548fd28aac8 |
---|
Branch pushed to git repo; I updated commit sha1. New commits:
a3c8e38 | Merge branch 'u/roed/nmod_mat' of git://trac.sagemath.org/sage into t/31548/nmod_mat
|
comment:35 Changed 19 months ago by
Milestone: | sage-9.4 → sage-9.5 |
---|
Setting a new milestone for this ticket based on a cursory review.
comment:36 Changed 14 months ago by
Milestone: | sage-9.5 → sage-9.6 |
---|
comment:37 Changed 10 months ago by
Milestone: | sage-9.6 → sage-9.7 |
---|
comment:38 Changed 5 months ago by
Milestone: | sage-9.7 → sage-9.8 |
---|
comment:39 Changed 4 days ago by
Milestone: | sage-9.8 |
---|
Branch pushed to git repo; I updated commit sha1. New commits:
Fix bug in cinit