Opened 13 years ago

Closed 13 years ago

#6553 closed defect (fixed)

[with patch, positive review] fast slicing of sparse matrices

Reported by: Jason Grout Owned by: William Stein
Priority: major Milestone: sage-4.1.1
Component: linear algebra Keywords:
Cc: Rob Beezer Merged in: Sage 4.1.1.alpha1
Authors: Jason Grout Reviewers: Rob Beezer
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

Description

Extracting a slice from a sparse matrix is insanely slow, as the code effectively treats the matrix as a dense matrix.

Attachments (1)

trac-6553-slicing-sparse-matrices.patch (4.2 KB) - added by Jason Grout 13 years ago.

Download all attachments as: .zip

Change History (10)

comment:1 Changed 13 years ago by Jason Grout

Summary: fast slicing of sparse matrices[with patch, needs review] fast slicing of sparse matrices

Before, I waited for several minutes before giving up.

AFTER:

sage: A=random_matrix(ZZ,100000,density=.00005,sparse=True)                  
sage: %time A[50000:,:50000]                                                 
CPU times: user 0.43 s, sys: 0.01 s, total: 0.44 s
Wall time: 0.47 s
50000 x 50000 sparse matrix over Integer Ring

Also:

BEFORE:

sage: A=random_matrix(ZZ,10000,density=.00005,sparse=True)     
sage: %time A[5000:,:5000]                                     
CPU times: user 8.32 s, sys: 0.02 s, total: 8.34 s
Wall time: 8.69 s
5000 x 5000 sparse matrix over Integer Ring

AFTER:

sage: A=random_matrix(ZZ,10000,density=.00005,sparse=True)
sage: %time A[5000:,:5000]                                
CPU times: user 0.04 s, sys: 0.00 s, total: 0.04 s
Wall time: 0.08 s
5000 x 5000 sparse matrix over Integer Ring

comment:2 Changed 13 years ago by Jason Grout

Cc: Rob Beezer added

comment:3 Changed 13 years ago by Rob Beezer

Summary: [with patch, needs review] fast slicing of sparse matrices[with patch, needs work] fast slicing of sparse matrices

Nicely done. Three comments before giving this a positive review.

  1. The last test behaves differently for me, and the result seems "more correct" according to the density specified. This is on 4.1.rc1 (which is the newest upgrade I could muster).
    sage: len(B.nonzero_positions())
Expected:
    14047
Got:
    100550
  1. Lists of non-integers (admittedly silly) fails silently and incorrectly. It would appear that no entry of the new matrix gets set properly, so the result is the zero matrix of the correct size.
sage: A = random_matrix(ZZ, 20, 20, x=10, sparse=True)
sage: len(A.nonzero_positions())
353
sage: A.matrix_from_rows_and_columns([1.1, 2.1, 3.1, 4.1], [5.1, 6.1, 7.1, 8.1])

[0 0 0 0]
[0 0 0 0]
[0 0 0 0]
[0 0 0 0]
  1. I'd think the doctests would be improved if there were tests for

(a) the condition in (2)
(b) the case of non-list input (raising the TypeError as implemented)

comment:4 Changed 13 years ago by Jason Grout

Summary: [with patch, needs work] fast slicing of sparse matrices[with patch, needs review] fast slicing of sparse matrices

Thanks for reviewing these so quickly!

  1. Are you on a 64-bit system (maybe you are getting a different random matrix)? That doctest quite definitely passes for me. I agree that your answer seems more correct, though.
  1. The error is in the sparse matrix indexing function, not in this function. I've opened up #6569 to address this issue, with a relevant example. I don't think that should hold back this code.
  1. The condition in (2) should be tested in #6569. I've updated the patch to include a doctest for (b).

comment:5 Changed 13 years ago by Jason Grout

Also, the problem (1) above might be related to #3436.

comment:6 Changed 13 years ago by Rob Beezer

Yes, I'm testing on a 64-bit system. What do you want to do with this doctest?

I think that is all that needs to be addressed now, since you are right that the non-integer index and density behavior belong elsewhere.

Solve one problem and expose two more? ;-)

Rob

Changed 13 years ago by Jason Grout

comment:7 Changed 13 years ago by Jason Grout

I've updated the patch again with both of our outputs. It should pass your doctests now too. Can you review it again?

Thanks!

comment:8 Changed 13 years ago by Rob Beezer

Reviewers: Rob Beezer
Summary: [with patch, needs review] fast slicing of sparse matrices[with patch, positive review] fast slicing of sparse matrices

The fix on the one doctest works. Passes tests for all of sage/matrix/*

Positive review.

PS The discrepancy here, and as illustrated in #3436, is troubling.

comment:9 Changed 13 years ago by Minh Van Nguyen

Merged in: Sage 4.1.1.alpha1
Resolution: fixed
Status: newclosed
Note: See TracTickets for help on using tickets.