use flint fmpq_mat for rational dense matrices

[videlec]

The flint library has a builtin type for rational matrices: fmpq_mat_t. This ticket proposes to replace the current array of mpq_t wrapped by Matrix_rational_dense in favor of fmpq_mat_t.

(See also the related #22924 and #22872)

CC: @ClementPernet @mmasdeu

Component: linear algebra

Keywords: thursdaysbdx

Author: Vincent Delecroix

Branch/Commit: cb0dae1

Reviewer: Marc Masdeu

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

[videlec]

Branch: u/vdelecroix/22970

[videlec]

New commits:

f7d368f	22970: more flint declarations
fce2da5	22970: pari / fmpq_mat_t conversions
b52e2c3	22970: implement libs/flint/randomize.pxd
d5ea72b	22970: let rational dense matrix uses fmpq_mat_t
83e3a87	22970: adapt codes using rational dense matrices

[videlec]

Commit: 83e3a87

[videlec]

comment:2

For a discussion about an annoying segfault related to this ticket, see this thread.

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

3daa722	22970: more flint declarations
26822a2	22970: nonzero versions of gmp randomize functions
769d86c	22970: pari / fmpq_mat_t conversions
99cf141	22970: let rational dense matrix uses fmpq_mat_t
a254a43	22970: adapt codes using rational dense matrices

[sagetrac-git]

Changed commit from 83e3a87 to a254a43

[videlec]

Changed keywords from none to thursdaysbdx

[sagetrac-git]

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

1621ac1

22970: use flint by default in det/inverse

[sagetrac-git]

Changed commit from a254a43 to 1621ac1

[videlec]

New commits:

3daa722	22970: more flint declarations
26822a2	22970: nonzero versions of gmp randomize functions
769d86c	22970: pari / fmpq_mat_t conversions
99cf141	22970: let rational dense matrix uses fmpq_mat_t
a254a43	22970: adapt codes using rational dense matrices
1621ac1	22970: use flint by default in det/inverse

[sagetrac-git]

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

867ed56

29970: echelonize/echelon_form using flint

[sagetrac-git]

Changed commit from 1621ac1 to 867ed56

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

d1c8d52

29970: echelonize/echelon_form using flint

[sagetrac-git]

Changed commit from 867ed56 to d1c8d52

[mmasdeu]

comment:11

Thanks for the work Vincent! I think that it's my duty to review this one :-).

While I update my develop branch and check the ticket out, could you check that that the docstring in the determinant method is correct? In algorithm, I see None missing.

Also, do you happen to have timings? that compare with the previous implementation? Otherwise I can produce some...

[videlec]

comment:12

Hi Marc,

Thanks for proposing the review! I need some more work on my branch as I have strange failing doctests in sage/modular that I don't understand right now.

I will provide proper timings for the following methods (tell me if you have more in mind):

• determinant
• multiplication
• echelonize
• charpoly (not yet in flint, but can go through integer matrices)
• minpoly (not yet in flint, but can go through integer matrices)

[videlec]

Attachment: test_file.sage.gz

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

f01157c	22970: more flint declarations
acce30c	22970: nonzero versions of gmp randomize functions
be5ccb4	22970: pari / fmpq_mat_t conversions
9ba2c4d	22970: let rational dense matrix uses fmpq_mat_t
150631d	22970: adapt codes using rational dense matrices
a3b6b37	22970: use flint by default in det/inverse
10f6d8c	29970: echelonize/echelon_form using flint
aef538e	22970: derandomize tests in free_module_integer.py
edfa6f4	22970: various cleaning in matrix_rational_dense

[sagetrac-git]

Changed commit from d1c8d52 to edfa6f4

[videlec]

comment:14

At commit edfa6f46b5 using attachment: test_file.sage I obtain (within different session because of caching)

sage: %runfile test_file.sage
sage: test(seed=0)
f = q + 1/2*a1*q^3 + (4*a1 - 26)*q^5 + O(q^6)
K = Number Field in a1 with defining polynomial x^2 + 32*x - 9984
a = 1/2*a1
True
False

and

sage: %runfile test_file.sage
sage: test(seed=1)
f = q + 1/2*a1*q^3 + (4*a1 - 26)*q^5 + O(q^6)
K = Number Field in a1 with defining polynomial x^2 + 32*x - 9984
a = 1/2*a1
False
True

And it looks like a bug to me that this result depends on the seed of the random generator...

[videlec]

comment:15

Replying to comment:14: Discussed at
this sage-devel thread.

[videlec]

comment:16

Attachment: benchmark_matrices.py.gz

From attachment: benchmark_matrices.py

• echelonize: flint is better except when coefficients are huge in which case multimodular is best

nrows=5  ncols=5  rank=5, density=1.0000 nbits(height)=100
flint        0.0565
multimodular 0.3284
padic        0.5626

nrows=10  ncols=10  rank=5, density=1.0000 nbits(height)=37
flint        0.1063
multimodular 2.6420
padic        7.6511

nrows=100  ncols=100  rank=20, density=0.1799 nbits(height)=12
flint        9.1834
multimodular 12.2192
padic        74.8152

nrows=10  ncols=10  rank=10, density=1.0000 nbits(height)=200
flint        10.1606
multimodular 1.5586
padic        2.1540

• determinant

dim=3 density=0.7778 nbits(height)=3
flint        0.0092
integer      0.1334
pari         0.0017

dim=3 density=1.0000 nbits(height)=100
flint        0.0113
integer      0.1188
pari         0.0269

dim=30 density=1.0000 nbits(height)=5
flint        0.9006
integer      1.0754
pari         34.5452

dim=30 density=0.2544 nbits(height)=5
flint        0.4389
integer      0.9986
pari         179.9622

• charpoly

dim=3 density=0.7778 nbits(height)=2
flint        0.3875
linbox       1.3019
generic      0.0431

dim=4 density=0.5625 nbits(height)=2
flint        0.1776
linbox       1.2013
generic      0.0450

dim=5 density=0.6400 nbits(height)=2
flint        0.1737
linbox       1.2952
generic      0.0532

dim=6 density=0.6111 nbits(height)=2
flint        0.1850
linbox       1.2773
generic      0.0651

dim=10 density=0.4100 nbits(height)=2
flint        0.2343
linbox       1.4250
generic      0.1818

dim=10 density=1.0000 nbits(height)=2
flint        0.2521
linbox       1.4264
generic      0.4842

dim=30 density=1.0000 nbits(height)=2
flint        4.8531
linbox       3.4320
generic      50.0362

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

14d31c5	22970: better doctest in modular/hecke/module.py
0c8b2ce	22970: improved doc + simpler echelonize/echelon_form logic
c172064	22970: _new_matrix/from_columns/add_to_entry
5f2e1ba	22970: small optimization in modsym/ambient.py

[sagetrac-git]

Changed commit from b5f5600 to 5f2e1ba

[videlec]

comment:33

at commit b5f5600 I got

sage: %time m = CuspForms(31, 12).hecke_matrix(3)
CPU times: user 11.7 s, sys: 40 ms, total: 11.7 s
Wall time: 11.7 s

sage: %time c = CuspForms(51, 12).hecke_matrix(3)
CPU times: user 2min 52s, sys: 283 ms, total: 2min 52s
Wall time: 2min 52s

sage: %time c = CuspForms(101, 12).hecke_matrix(3)
CPU times: user 7min 17s, sys: 620 ms, total: 7min 18s
Wall time: 7min 18s

and at 5f2e1ba the even better

sage: %time m = CuspForms(31, 12).hecke_matrix(3)
CPU times: user 7.5 s, sys: 36.7 ms, total: 7.53 s
Wall time: 7.51 s

sage: %time c = CuspForms(51, 12).hecke_matrix(3)
CPU times: user 2min 10s, sys: 223 ms, total: 2min 10s
Wall time: 2min 10s

sage: %time c = CuspForms(101, 12).hecke_matrix(3)
CPU times: user 5min 9s, sys: 603 ms, total: 5min 10s
Wall time: 5min 10s

[videlec]

comment:35

And tests also pass on beta7!

[mmasdeu]

comment:36

This is definitely more than satisfying. The code looks very clean, and all tests pass. Thanks for the great work!

[mmasdeu]

Reviewer: Marc Masdeu

[vbraun]

comment:37

Merge conflict

[videlec]

comment:38

Too bad. The code is fine on beta7. Can I try to fix it by merging another ticket?

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. Last 10 new commits:

86a305b	22970: adapt codes using rational dense matrices
b5320ef	22970: use flint by default in det/inverse
fad1b0d	29970: echelonize/echelon_form using flint
b68993f	22970: derandomize tests in free_module_integer.py
91c5835	22970: various cleaning in matrix_rational_dense
9f83912	22970: fix doctests in sage/modular/
bcf6b7d	22970: better doctest in modular/hecke/module.py
14f3fdb	22970: improved doc + simpler echelonize/echelon_form logic
fceef50	22970: _new_matrix/from_columns/add_to_entry
cb0dae1	22970: small optimization in modsym/ambient.py

[sagetrac-git]

Changed commit from 5f2e1ba to cb0dae1

[videlec]

comment:40

rebased (I launched the patchbot)

[videlec]

comment:41

patchbot still happy!

[vbraun]

Changed branch from u/vdelecroix/22970 to cb0dae1