Create matrix class for FLINT's nmod_mat module #31548

roed314 · 2021-03-24T15:54:33Z

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.

Depends on #31069

CC: @edgarcosta

Component: linear algebra

Author: David Roe, Edgar Costa

Branch/Commit: u/roed/nmod_mat @ a3c8e38

Reviewer: Travis Scrimshaw

Issue created by migration from https://trac.sagemath.org/ticket/31548

The text was updated successfully, but these errors were encountered:

roed314 · 2021-03-24T15:55:34Z

Branch: u/roed/nmod_mat

sagetrac-git · 2021-03-24T16:08:44Z

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

`763533d`	`Fix bug in cinit`

sagetrac-git · 2021-03-24T16:08:44Z

Commit: 763533d

sagetrac-git · 2021-03-24T18:28:36Z

Changed commit from 763533d to 8cdf9b1

sagetrac-git · 2021-03-24T18:28:36Z

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

`8cdf9b1`	`Add some functions to Matrix_nmod_dense`

sagetrac-git · 2021-03-24T19:03:25Z

Changed commit from 8cdf9b1 to 518a32f

sagetrac-git · 2021-03-24T19:03:25Z

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

`9c6e9d3`	`level 1 and level 2`
`518a32f`	`Updating todos`

sagetrac-git · 2021-03-24T19:45:16Z

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

`936668a`	`Add todos`

sagetrac-git · 2021-03-24T19:45:16Z

Changed commit from 518a32f to 936668a

sagetrac-git · 2021-03-24T19:47:45Z

Changed commit from 936668a to aaf0680

sagetrac-git · 2021-03-24T19:47:45Z

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

`aaf0680`	`Update todo`

sagetrac-git · 2021-03-24T19:49:07Z

Changed commit from aaf0680 to fb02349

sagetrac-git · 2021-03-24T19:49:07Z

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

`fb02349`	`Reorder todos`

sagetrac-git · 2021-03-25T16:41:33Z

Changed commit from fb02349 to cecbe30

sagetrac-git · 2021-03-25T16:41:33Z

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`

sagetrac-git · 2021-03-26T17:17:49Z

Changed commit from cecbe30 to db33b05

sagetrac-git · 2021-03-26T17:17:49Z

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

`eb56a5e`	`Add all definitions to FLINT's ulong_extras, optimize matrix inversion, change default class for matrix mod n`
`db33b05`	`Charpoly for Z/n`

mkoeppe · 2021-03-27T02:13:38Z

comment:10

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.

sagetrac-git · 2021-03-29T21:17:39Z

Changed commit from db33b05 to 3eb1cd4

sagetrac-git · 2021-03-29T21:17:39Z

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`

roed314 · 2021-03-30T06:00:45Z

Dependencies: #31069

sagetrac-git · 2021-03-30T17:51:55Z

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

`8c71a1c`	`31069: flint version upgrade`
`a32be02`	`Merge branch 'public/31069' of git://trac.sagemath.org/sage into t/31548/nmod_mat`
`aed2361`	`Working on solve_right`

sagetrac-git · 2021-03-30T17:51:55Z

Changed commit from 3eb1cd4 to aed2361

sagetrac-git · 2021-04-07T07:05:39Z

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

`8b37863`	`Working on minpoly`
`1541005`	`int64`
`8a4b815`	`import`
`1f40b95`	`int64`
`2d157e1`	`Merge branch 'u/edgarcosta/nmod_mat' of git://trac.sagemath.org/sage into t/31548/nmod_mat`
`5e9b8a7`	`Minpoly`

tscrim · 2021-04-23T01:40:23Z

comment:22

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.

roed314 · 2021-04-23T02:08:16Z

comment:23

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!

tscrim · 2021-04-23T02:16:31Z

comment:24

Replying to @roed314:

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.

sagetrac-git · 2021-04-26T18:11:59Z

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`

sagetrac-git · 2021-04-26T18:11:59Z

Changed commit from 9748ffc to 465f51d

roed314 · 2021-04-26T19:01:24Z

comment:26

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.

roed314 · 2021-04-26T19:11:33Z

comment:27

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.

sagetrac-git · 2021-04-26T19:40:43Z

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

`760e0c9`	`Small fixes`

sagetrac-git · 2021-04-26T19:40:43Z

Changed commit from 465f51d to 760e0c9

roed314 · 2021-04-26T19:42:15Z

comment:29

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

New commits:

`760e0c9`	`Small fixes`

roed314 · 2021-04-26T19:43:01Z

comment:30

This ticket is now actually ready for review, though the patchbot won't run currently (since it depends on #31069 which changes spkgs).

tscrim · 2021-06-24T23:20:47Z

comment:33

Needs rebase.

tscrim · 2021-06-24T23:20:47Z

Reviewer: Travis Scrimshaw

sagetrac-git · 2021-06-25T15:37:30Z

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`

sagetrac-git · 2021-06-25T15:37:30Z

Changed commit from 760e0c9 to a3c8e38

mkoeppe · 2021-07-19T00:44:56Z

comment:35

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

roed314 added this to the sage-9.3 milestone Mar 24, 2021

roed314 added c: linear algebra labels Mar 24, 2021

mkoeppe modified the milestones: sage-9.3, sage-9.4 Mar 27, 2021

This comment has been minimized.

Sign in to view

tscrim added s: needs work and removed s: needs review labels Jun 24, 2021

mkoeppe modified the milestones: sage-9.4, sage-9.5 Jul 19, 2021

mkoeppe modified the milestones: sage-9.5, sage-9.6 Dec 18, 2021

mkoeppe modified the milestones: sage-9.6, sage-9.7 Apr 2, 2022

mkoeppe modified the milestones: sage-9.7, sage-9.8 Aug 31, 2022

mkoeppe removed this from the sage-9.8 milestone Jan 29, 2023

kedlaya mentioned this issue Jan 29, 2023

prime_range should allow a step #29760

Open

roed314 mentioned this issue Jan 29, 2023

CRT for polynomials mod n #31731

Open

Create matrix class for FLINT's nmod_mat module #31548

Create matrix class for FLINT's nmod_mat module #31548

Comments

roed314 commented Mar 24, 2021

roed314 commented Mar 24, 2021

sagetrac-git mannequin commented Mar 24, 2021

sagetrac-git mannequin commented Mar 24, 2021

sagetrac-git mannequin commented Mar 24, 2021

sagetrac-git mannequin commented Mar 24, 2021

sagetrac-git mannequin commented Mar 24, 2021

sagetrac-git mannequin commented Mar 24, 2021

sagetrac-git mannequin commented Mar 24, 2021

sagetrac-git mannequin commented Mar 24, 2021

sagetrac-git mannequin commented Mar 24, 2021

sagetrac-git mannequin commented Mar 24, 2021

sagetrac-git mannequin commented Mar 24, 2021

sagetrac-git mannequin commented Mar 24, 2021

sagetrac-git mannequin commented Mar 25, 2021

sagetrac-git mannequin commented Mar 25, 2021

sagetrac-git mannequin commented Mar 26, 2021

sagetrac-git mannequin commented Mar 26, 2021

mkoeppe commented Mar 27, 2021

sagetrac-git mannequin commented Mar 29, 2021

sagetrac-git mannequin commented Mar 29, 2021

roed314 commented Mar 30, 2021

sagetrac-git mannequin commented Mar 30, 2021

sagetrac-git mannequin commented Mar 30, 2021

sagetrac-git mannequin commented Apr 7, 2021

tscrim commented Apr 23, 2021

roed314 commented Apr 23, 2021

tscrim commented Apr 23, 2021

sagetrac-git mannequin commented Apr 26, 2021

sagetrac-git mannequin commented Apr 26, 2021

roed314 commented Apr 26, 2021

roed314 commented Apr 26, 2021

sagetrac-git mannequin commented Apr 26, 2021

sagetrac-git mannequin commented Apr 26, 2021

roed314 commented Apr 26, 2021

roed314 commented Apr 26, 2021

This comment has been minimized.

tscrim commented Jun 24, 2021

tscrim commented Jun 24, 2021

sagetrac-git mannequin commented Jun 25, 2021

sagetrac-git mannequin commented Jun 25, 2021

mkoeppe commented Jul 19, 2021