Opened 10 years ago

Closed 10 years ago

#11544 closed defect (fixed)

Viewing matrices of algebraic numbers can take a long time

Reported by: rbeezer Owned by: jason, was
Priority: major Milestone: sage-4.7.2
Component: linear algebra Keywords:
Cc: Merged in: sage-4.7.2.alpha3
Authors: Rob Beezer Reviewers: Martin Raum
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

Description (last modified by rbeezer)

The following code leads to about a one minute hang for me (reproducibly in a fresh session). Keshav Kini (via IRC) had the same experience.

sage: A = matrix(QQ, 4, 4, [1, 2, -2, 2, 1, 0, -1, -1, 0, -1, 1, 1, -1, 2, 1/2, 0])
sage: e = A.eigenvalues()[3]
sage: K = (A-e).kernel()
sage: P = K.basis_matrix()
sage: x = P.list()[3]
sage: remap = {}
sage: remap.has_key(x)

This behavior hangs the creation of a string version of a matrix. If you comment-out sage/matrix/matrix0.pyx at lines 1695-1696, the problem goes away. To see the effect, run the first four lines of the code above and then just print P, with and without the two lines mentioned.

I have a workaround in mind that may solve the problem in many cases. Root issue is at #11543.

Apply:

  1. trac_11544-avoid-hash-of-matrix-entries-v2.patch

Attachments (2)

trac_11544-avoid-hash-of-matrix-entries.patch (2.1 KB) - added by rbeezer 10 years ago.
trac_11544-avoid-hash-of-matrix-entries-v2.patch (14.6 KB) - added by rbeezer 10 years ago.

Download all attachments as: .zip

Change History (10)

comment:1 Changed 10 years ago by rbeezer

  • Description modified (diff)

comment:2 Changed 10 years ago by rbeezer

  • Description modified (diff)
  • Status changed from new to needs_review

comment:3 Changed 10 years ago by rbeezer

  • Status changed from needs_review to needs_work

I tested this for speed, but forgot to do even minimal doctests.

It affects a lot of QQbar output in minor ways, so several doctests need fixing.

comment:4 Changed 10 years ago by rbeezer

  • Authors set to Rob Beezer
  • Description modified (diff)
  • Status changed from needs_work to needs_review

v2 patch includes doctest fixes.

Just one line of code changes in sage/matrix/matrix0.pyx, the rest is documentation.

Previous behavior was to hash entries while printing, this caused the precision of an entry to increase, thus slightly greater precision in subsequent computed (printed) results.

comment:5 Changed 10 years ago by rbeezer

This probably needs a bit more explanation.

One feature of #10627 is to replace specific matrix entries by a symbol. To look up this translation in a dictionary, entries of a matrix are hashed. For QQbar, this hash is expensive (#11543).

This patch prevents a look-up if the translation dictionary is empty.

comment:6 Changed 10 years ago by mraum

  • Reviewers set to Martin Raum
  • Status changed from needs_review to positive_review

This gets a positive review as is.

comment:7 Changed 10 years ago by rbeezer

Thanks, again!

comment:8 Changed 10 years ago by leif

  • Merged in set to sage-4.7.2.alpha3
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.