Opened 10 years ago

Closed 5 years ago

#13915 closed enhancement (wontfix)

wrapper for determinant, minpoly, etc. from linbox for sparse matrices

Reported by: Charles Bouillaguet Owned by: jason, was
Priority: major Milestone: sage-duplicate/invalid/wontfix
Component: linear algebra Keywords: linbox, sd75
Cc: Clément Pernet Merged in:
Authors: Reviewers: Travis Scrimshaw
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

Description (last modified by Vincent Delecroix)

Superseeded by #23214.


Currently, computing the determinant, minimum polynomial, characteristic polynomial, etc of sparse matrices over the integers and finite fields switch them to a dense representation, then runs the dense algorithm.

This works, but is quite suboptimal. Linbox packs a few algorithms tailored for sparse matrices, e.g. iterative methods for the determinant, minpoly, etc. These methods have the advantage that they only read the matrix, and are memory efficient.

The aim of this ticket is to make these algorithms available in Sage.

Change History (13)

comment:1 Changed 10 years ago by Charles Bouillaguet

Examples of things that are presently bad (where a sparse matrix is converted to a dense representation) :

  • kernel, determinant of sparse integers matrices
  • rank of integers matrices relies on echelonization, which very likely switch it to dense. Linbox has other ways of dealing with this.
  • elementary divisors and smith form of sparse integer matrices (idem).

comment:2 Changed 9 years ago by Jeroen Demeyer

Milestone: sage-5.11sage-5.12

comment:3 Changed 9 years ago by For batch modifications

Milestone: sage-6.1sage-6.2

comment:4 Changed 9 years ago by For batch modifications

Milestone: sage-6.2sage-6.3

comment:5 Changed 8 years ago by For batch modifications

Milestone: sage-6.3sage-6.4

comment:6 Changed 7 years ago by Clément Pernet

Cc: Clément Pernet added

comment:7 Changed 6 years ago by Charles Bouillaguet

Keywords: sd75 added
Milestone: sage-6.4sage-7.4

comment:8 Changed 5 years ago by Travis Scrimshaw

See #25257 for an initial attempt for rank.

comment:9 Changed 5 years ago by Travis Scrimshaw

Milestone: sage-7.4sage-8.2

comment:10 Changed 5 years ago by Vincent Delecroix

Description: modified (diff)
Milestone: sage-8.2sage-duplicate/invalid/wontfix

superseeded by #23214. I propose to close this as duplicate

comment:11 Changed 5 years ago by Travis Scrimshaw

Reviewers: Travis Scrimshaw
Status: newneeds_review

Concur.

comment:12 Changed 5 years ago by Travis Scrimshaw

Status: needs_reviewpositive_review

comment:13 Changed 5 years ago by Vincent Delecroix

Resolution: wontfix
Status: positive_reviewclosed

closing positively reviewed duplicates

Note: See TracTickets for help on using tickets.