Opened 21 months ago

Last modified 3 months ago

#31548 needs_work enhancement

Create matrix class for FLINT's nmod_mat module

Reported by: David Roe Owned by:
Priority: major Milestone: sage-9.8
Component: linear algebra Keywords:
Cc: Edgar Costa 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:

Status badges

Description (last modified by David Roe)

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 composite N 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 a NotImplementedError before), and pivots 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 and right_kernel_matrix. There is also a new method minpoly_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 and augment 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 mod N 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 (38)

comment:1 Changed 21 months ago by David Roe

Branch: u/roed/nmod_mat

comment:2 Changed 21 months ago by git

Commit: 763533df7ba71d606038dac0983c5c24165f40f2

Branch pushed to git repo; I updated commit sha1. New commits:

763533dFix bug in cinit

comment:3 Changed 21 months ago by git

Commit: 763533df7ba71d606038dac0983c5c24165f40f28cdf9b16b1cd248f211a3d86eec61c30a6ef702b

Branch pushed to git repo; I updated commit sha1. New commits:

8cdf9b1Add some functions to Matrix_nmod_dense

comment:4 Changed 21 months ago by git

Commit: 8cdf9b16b1cd248f211a3d86eec61c30a6ef702b518a32f9a7b27b0c18d89a2873d6c0139c67efe9

Branch pushed to git repo; I updated commit sha1. New commits:

9c6e9d3level 1 and level 2
518a32fUpdating todos

comment:5 Changed 21 months ago by git

Commit: 518a32f9a7b27b0c18d89a2873d6c0139c67efe9936668af2821a939e4ae200f384611bf42bd00f5

Branch pushed to git repo; I updated commit sha1. New commits:

936668aAdd todos

comment:6 Changed 21 months ago by git

Commit: 936668af2821a939e4ae200f384611bf42bd00f5aaf0680040c96e439877eac471bd3e2cd4515a94

Branch pushed to git repo; I updated commit sha1. New commits:

aaf0680Update todo

comment:7 Changed 21 months ago by git

Commit: aaf0680040c96e439877eac471bd3e2cd4515a94fb023491c50c1097963987e007f5d088e9e73515

Branch pushed to git repo; I updated commit sha1. New commits:

fb02349Reorder todos

comment:8 Changed 21 months ago by git

Commit: fb023491c50c1097963987e007f5d088e9e73515cecbe3010e5438cdc77667507fe2dcfb2f170eb3

Branch pushed to git repo; I updated commit sha1. New commits:

31d05e4inverses, swap rows and columns
d69baffrichmp
ba439fcMerge branch 'u/roed/nmod_mat' of git://trac.sagemath.org/sage into nmod_mat
9285ed3Merge branch 'u/roed/nmod_mat' of git://trac.sagemath.org/sage into nmod_mat
6a3d32ajustifying flags
a90423aMerge branch 'u/roed/nmod_mat' of git://trac.sagemath.org/sage into nmod_mat
c7c68cdsome progress
61821e8fixing various things
cecbe30Merge branch 'u/edgarcosta/nmod_mat' of git://trac.sagemath.org/sage into t/31548/nmod_mat

comment:9 Changed 21 months ago by git

Commit: cecbe3010e5438cdc77667507fe2dcfb2f170eb3db33b05407674b601d914aa9e13deca6b1280cb2

Branch pushed to git repo; I updated commit sha1. New commits:

eb56a5eAdd all definitions to FLINT's ulong_extras, optimize matrix inversion, change default class for matrix mod n
db33b05Charpoly for Z/n

comment:10 Changed 21 months ago by Matthias Köppe

Milestone: sage-9.3sage-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 21 months ago by git

Commit: db33b05407674b601d914aa9e13deca6b1280cb23eb1cd4bd49e263e96d86c261d07afa2e7916275

Branch pushed to git repo; I updated commit sha1. Last 10 new commits:

33dd395comment
b922d8eMerge branch 'u/roed/nmod_mat' of git://trac.sagemath.org/sage into nmod_mat
c1961a2right kernel matrix
b1d5396Merge branch 'u/roed/nmod_mat' of git://trac.sagemath.org/sage into nmod_mat
b9965beremove comment
1045207touch up right kernel
fb619b0work around echenolize
45de1c8remove stack
bf8aaabMerge branch 'u/edgarcosta/nmod_mat' of git://trac.sagemath.org/sage into t/31548/nmod_mat
3eb1cd4Fix import

comment:12 Changed 21 months ago by David Roe

Dependencies: #31069

comment:13 Changed 21 months ago by git

Commit: 3eb1cd4bd49e263e96d86c261d07afa2e7916275aed23614745507fa84876489c00f5abc77990c72

Branch pushed to git repo; I updated commit sha1. New commits:

8c71a1c31069: flint version upgrade
a32be02Merge branch 'public/31069' of git://trac.sagemath.org/sage into t/31548/nmod_mat
aed2361Working on solve_right

comment:14 Changed 20 months ago by git

Commit: aed23614745507fa84876489c00f5abc77990c725e9b8a7b06100833a6dc3a1f9efdca7592fbdcb6

Branch pushed to git repo; I updated commit sha1. New commits:

8b37863Working on minpoly
1541005int64
8a4b815import
1f40b95int64
2d157e1Merge branch 'u/edgarcosta/nmod_mat' of git://trac.sagemath.org/sage into t/31548/nmod_mat
5e9b8a7Minpoly

comment:15 Changed 20 months ago by git

Commit: 5e9b8a7b06100833a6dc3a1f9efdca7592fbdcb6fc48eca590a15e596660601f61c4eba80bf1b249

Branch pushed to git repo; I updated commit sha1. New commits:

fc48ecaWorking on documentation

comment:16 Changed 20 months ago by git

Commit: fc48eca590a15e596660601f61c4eba80bf1b24964e44fc055b8a7f2fb69207d5e145771e4e22847

Branch pushed to git repo; I updated commit sha1. New commits:

64e44fcFixing bugs and adding documentation to matrices mod n

comment:17 Changed 20 months ago by git

Commit: 64e44fc055b8a7f2fb69207d5e145771e4e22847e5c4c1e1b8dfda617f4b1e16f807ba42807a3387

Branch pushed to git repo; I updated commit sha1. New commits:

e5c4c1eWorking on documentation

comment:18 Changed 20 months ago by git

Commit: e5c4c1e1b8dfda617f4b1e16f807ba42807a33871a7bb38565f649d78c24122033a732b517d27f3f

Branch pushed to git repo; I updated commit sha1. New commits:

dad23f5Working on picking appropriate matrix types and fixing some bugs
1a7bb38Fixing some bugs

comment:19 Changed 20 months ago by git

Commit: 1a7bb38565f649d78c24122033a732b517d27f3f6f41da9cadc509baa5d221e354a7eaa797574bed

Branch pushed to git repo; I updated commit sha1. New commits:

6f41da9Fixing doctest problems from switching default implementation to flint for small matrices

comment:20 Changed 20 months ago by David Roe

Authors: David Roe, Edgar Costa
Status: newneeds_review

Marking for patchbot to test....

comment:21 Changed 20 months ago by git

Commit: 6f41da9cadc509baa5d221e354a7eaa797574bed9748ffc23e3e3b163ae65207f1790de020040dda

Branch pushed to git repo; I updated commit sha1. New commits:

d0507c4Working on fixing reduction matrix bug
9748ffcAdd deprecation warning to _reduction_matrix

comment:22 Changed 20 months ago by Travis Scrimshaw

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 Changed 20 months ago by David Roe

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!

Last edited 20 months ago by David Roe (previous) (diff)

comment:24 in reply to:  23 Changed 20 months ago by Travis Scrimshaw

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 and Matrix_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 20 months ago by git

Commit: 9748ffc23e3e3b163ae65207f1790de020040dda465f51de75fc202f7c5c9b636e39501e2dda3b0a

Branch pushed to git repo; I updated commit sha1. New commits:

cd1b853Merge branch 'u/roed/nmod_mat' of trac.sagemath.org:sage into t/31548/nmod_mat
6e2b75aMerge branch 'u/roed/nmod_mat' of trac.sagemath.org:sage into t/31548/nmod_mat
ee10b06Working on documentation and fixing tests
465f51dWorking on documentation

comment:26 in reply to:  22 Changed 20 months ago by David Roe

Replying to tscrim:

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.

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 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'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 the matrix_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 20 months ago by David Roe

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 20 months ago by git

Commit: 465f51de75fc202f7c5c9b636e39501e2dda3b0a760e0c9f68abda66b02dd96f7fd67f9ea9fabe23

Branch pushed to git repo; I updated commit sha1. New commits:

760e0c9Small fixes

comment:29 Changed 20 months ago by David Roe

(I accidentally made a comment instead of editing the ticket description)


New commits:

760e0c9Small fixes
Last edited 20 months ago by David Roe (previous) (diff)

comment:30 Changed 20 months ago by David Roe

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 20 months ago by David Roe

Description: modified (diff)

comment:32 Changed 20 months ago by Edgar Costa

Cc: Edgar Costa added

comment:33 Changed 18 months ago by Travis Scrimshaw

Reviewers: Travis Scrimshaw
Status: needs_reviewneeds_work

Needs rebase.

comment:34 Changed 18 months ago by git

Commit: 760e0c9f68abda66b02dd96f7fd67f9ea9fabe23a3c8e38bc674e3e7fa8c93ab04f71548fd28aac8

Branch pushed to git repo; I updated commit sha1. New commits:

a3c8e38Merge branch 'u/roed/nmod_mat' of git://trac.sagemath.org/sage into t/31548/nmod_mat

comment:35 Changed 17 months ago by Matthias Köppe

Milestone: sage-9.4sage-9.5

Setting a new milestone for this ticket based on a cursory review.

comment:36 Changed 12 months ago by Matthias Köppe

Milestone: sage-9.5sage-9.6

comment:37 Changed 8 months ago by Matthias Köppe

Milestone: sage-9.6sage-9.7

comment:38 Changed 3 months ago by Matthias Köppe

Milestone: sage-9.7sage-9.8
Note: See TracTickets for help on using tickets.