Opened 3 years ago

Closed 3 years ago

#28318 closed enhancement (fixed)

linbox for sparse integer matrix

Reported by: Vincent Delecroix Owned by:
Priority: major Milestone: sage-8.9
Component: linear algebra Keywords:
Cc: Clément Pernet Merged in:
Authors: Vincent Delecroix Reviewers: Travis Scrimshaw
Report Upstream: N/A Work issues:
Branch: 7df5ab4 (Commits, GitHub, GitLab) Commit: 7df5ab420d24462faffaeeb0bc1e38b700f08ad6
Dependencies: Stopgaps:

Status badges

Description (last modified by Vincent Delecroix)

The following now seems to work correctly (after #26932)

sage: m = diagonal_matrix(ZZ, [2] * 46)
sage: m._det_linbox()
70368744177664
sage: m = diagonal_matrix(ZZ, [3] * 100)
sage: m._det_linbox()
515377520732011331036461129765621272702107522001

This ticket stands for removing the #not tested directive and also put the appropriate sig_on/sig_off around linbox calls.

Note however, linbox is not doing great

sage: M = MatrixSpace(ZZ, 100, 100, sparse=True)
sage: m = M.random_element(density=0.1)
sage: %timeit m.__copy__().det()
100 loops, best of 5: 8.45 ms per loop
sage: %timeit m._det_linbox()
10 loops, best of 5: 43.4 ms per loop

And it gets worse as the dimension increases

sage: M = MatrixSpace(ZZ, 500, 500, sparse=True)
sage: m = M.random_element(density=0.1)
sage: %time d = m.__copy__().det()
CPU times: user 796 ms, sys: 3 µs, total: 796 ms
Wall time: 795 ms
sage: %time m._det_linbox()
CPU times: user 25.2 s, sys: 44 ms, total: 25.3 s
Wall time: 25.3 s

Change History (8)

comment:1 Changed 3 years ago by Vincent Delecroix

Description: modified (diff)

comment:2 Changed 3 years ago by Vincent Delecroix

Branch: u/vdelecroix/28318
Commit: 282192a227286364bfc44eb251d51fe829edcdd8
Status: newneeds_review

New commits:

282192aremove "not tested" flags in matrix_integer_sparse

comment:3 Changed 3 years ago by git

Commit: 282192a227286364bfc44eb251d51fe829edcdd8ab164da54b408b68f67e194b1403010d56e1fce1

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

ab164dafix rational constructor

comment:4 Changed 3 years ago by git

Commit: ab164da54b408b68f67e194b1403010d56e1fce1282192a227286364bfc44eb251d51fe829edcdd8

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

282192aremove "not tested" flags in matrix_integer_sparse

comment:5 Changed 3 years ago by Travis Scrimshaw

Just a quick note: speed is one thing, but memory usage is also important. Anyways, one little change and then a positive review:

-        NOTE: This method is much slower than converting to a dense matrix and
-        computing the determinant there. There is not much point in making it
-        available. See :trac:`28318`.
+        .. NOTE::
+
+            This method is much slower than converting to a dense matrix and
+            computing the determinant there. There is not much point in making
+            it available. See :trac:`28318`.

Thanks.

comment:6 Changed 3 years ago by git

Commit: 282192a227286364bfc44eb251d51fe829edcdd87df5ab420d24462faffaeeb0bc1e38b700f08ad6

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

7df5ab4fix documentation NOTE

comment:7 Changed 3 years ago by Travis Scrimshaw

Reviewers: Travis Scrimshaw
Status: needs_reviewpositive_review

Thanks.

comment:8 Changed 3 years ago by Volker Braun

Branch: u/vdelecroix/283187df5ab420d24462faffaeeb0bc1e38b700f08ad6
Resolution: fixed
Status: positive_reviewclosed
Note: See TracTickets for help on using tickets.