Opened 6 years ago

Closed 6 months ago

#13915 closed enhancement (wontfix)

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

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

Description (last modified by vdelecroix)

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 6 years ago by 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 5 years ago by jdemeyer

  • Milestone changed from sage-5.11 to sage-5.12

comment:3 Changed 5 years ago by vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:4 Changed 5 years ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:5 Changed 4 years ago by vbraun_spam

  • Milestone changed from sage-6.3 to sage-6.4

comment:6 Changed 3 years ago by cpernet

  • Cc cpernet added

comment:7 Changed 2 years ago by Bouillaguet

  • Keywords sd75 added
  • Milestone changed from sage-6.4 to sage-7.4

comment:8 Changed 7 months ago by tscrim

See #25257 for an initial attempt for rank.

comment:9 Changed 7 months ago by tscrim

  • Milestone changed from sage-7.4 to sage-8.2

comment:10 Changed 7 months ago by vdelecroix

  • Description modified (diff)
  • Milestone changed from sage-8.2 to sage-duplicate/invalid/wontfix

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

comment:11 Changed 7 months ago by tscrim

  • Reviewers set to Travis Scrimshaw
  • Status changed from new to needs_review

Concur.

comment:12 Changed 7 months ago by tscrim

  • Status changed from needs_review to positive_review

comment:13 Changed 6 months ago by vdelecroix

  • Resolution set to wontfix
  • Status changed from positive_review to closed

closing positively reviewed duplicates

Note: See TracTickets for help on using tickets.