Viewing matrices of algebraic numbers can take a long time

[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. attachment: trac_11544-avoid-hash-of-matrix-entries-v2.patch

Component: linear algebra

Author: Rob Beezer

Reviewer: Martin Raum

Merged: sage-4.7.2.alpha3

Issue created by migration from https://trac.sagemath.org/ticket/11544

[rbeezer]

comment:2

Attachment: trac_11544-avoid-hash-of-matrix-entries.patch.gz

[rbeezer]

comment:3

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.

[rbeezer]

Attachment: trac_11544-avoid-hash-of-matrix-entries-v2.patch.gz

[rbeezer]

comment:4

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.

[rbeezer]

Author: Rob Beezer

[rbeezer]

comment:5

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.

[sagetrac-mraum]

Reviewer: Martin Raum

[sagetrac-mraum]

comment:6

This gets a positive review as is.

[rbeezer]

comment:7

Thanks, again!

[nexttime]

Merged: sage-4.7.2.alpha3