Opened 13 years ago

Closed 13 years ago

#2155 closed enhancement (fixed)

[with patch; needs additional review] greatly speed up matrix inversion for 1x1 and 2x2 matrices over QQ by a factor of 20!; speed up changing base rings (architecture); hadamard bound

Reported by: was Owned by: was
Priority: major Milestone: sage-2.10.3
Component: linear algebra Keywords:
Cc: Merged in:
Authors: Reviewers:
Report Upstream: Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

Description

Before:

sage: a = matrix(QQ, 2, [1, 5, 17, 3]); a
[ 1  5]
[17  3]
sage: time for _ in xrange(10^4): b = a.invert()
CPU times: user 5.74 s, sys: 0.13 s, total: 5.87 s
Wall time: 5.94

After:

sage: time for _ in xrange(10^4): b = a.invert()
CPU times: user 0.22 s, sys: 0.04 s, total: 0.26 s
Wall time: 0.29

This also does not leak memory:

sage: get_memory_usage()
'122M+'
sage: time for _ in xrange(10^5): b = a.invert()
CPU times: user 2.33 s, sys: 0.36 s, total: 2.69 s
Wall time: 2.70
sage: get_memory_usage()
'122M+'

Attachments (2)

trac-2155.patch (4.5 KB) - added by was 13 years ago.
trac-2155-part2.patch (12.8 KB) - added by was 13 years ago.

Download all attachments as: .zip

Change History (7)

Changed 13 years ago by was

comment:1 Changed 13 years ago by robertwb

  • Summary changed from [with patch; needs review] greatly speed up matrix inversion for 1x1 and 2x2 matrices over QQ by a factor of 20! to [with patch; with almost-positive review] greatly speed up matrix inversion for 1x1 and 2x2 matrices over QQ by a factor of 20!

Works great for me. The doctest for invert() has some spurious code at the top of the examples block though.

Since you're going to have to be in there anyway, it might be a bit more readable if "t0" was renamed to "det."

Changed 13 years ago by was

comment:2 Changed 13 years ago by was

  • Summary changed from [with patch; with almost-positive review] greatly speed up matrix inversion for 1x1 and 2x2 matrices over QQ by a factor of 20! to [with patch; needs new review] greatly speed up matrix inversion for 1x1 and 2x2 matrices over QQ by a factor of 20!; speed up changing base rings (architecture); hadamard bound

I have addressed the referee's (Robert's) two complaints. I also added an architecture for fast change of base ring and computation of the Hadamard bound. This second thing is technically unrelated but it was too difficult to separate out safely.

This is now vastly faster than before

sage: a = random_matrix(ZZ,500)
sage: time a.change_ring(RDF)
CPU times: user 0.01 s, sys: 0.00 s, total: 0.02 s
Wall time: 0.02

comment:3 Changed 13 years ago by was

By the way, apply both patches, in order.

comment:4 Changed 13 years ago by robertwb

The code looks good to me, but I just tried to pull these two, in order, on a clean 2.10.1, and it's giving me errors:

robert$ sage -hg import ~/Desktop/patches/trac-2155-part2.patch applying /Users/robert/Desktop/patches/trac-2155-part2.patch patching file sage/matrix/matrix_integer_dense.pyx Hunk #2 FAILED at 1017 Hunk #3 FAILED at 2823 2 out of 3 hunks FAILED -- saving rejects to file sage/matrix/matrix_integer_dense.pyx.rej abort: patch failed to apply

You have a warning on the hadamard_bound function if the entries are too large--does it raise an error or give erroneous results?

comment:5 Changed 13 years ago by mabshoff

  • Resolution set to fixed
  • Status changed from new to closed
  • Summary changed from [with patch; needs new review] greatly speed up matrix inversion for 1x1 and 2x2 matrices over QQ by a factor of 20!; speed up changing base rings (architecture); hadamard bound to [with patch; needs additional review] greatly speed up matrix inversion for 1x1 and 2x2 matrices over QQ by a factor of 20!; speed up changing base rings (architecture); hadamard bound

Merged in Sage 2.10.3.rc1 (or earlier via #2053). It would be great if somebody could revisit this ticket.

Note: See TracTickets for help on using tickets.