Opened 11 years ago

Closed 8 years ago

#6442 closed defect (fixed)

Random(?) index error with determinant method

Reported by: spancratz Owned by: somebody
Priority: major Milestone: sage-5.0
Component: linear algebra Keywords: det, determinant, IndexError, sd35.5
Cc: mjo Merged in: sage-5.0.beta2
Authors: Sebastian Pancratz, Michael Orlitzky Reviewers: Paul Zimmermann
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description

On some occasions, the call A.det() for a matrix A results in an error, namely:

IndexError?: list index out of range

The error occurs during the dictionary lookup. It seems that rather than finding no item (and hence creating a new one and then computing determinant), an empty item D is found and indexing into D results in the error.

If run into this strange problem twice during the SAGE Days 16. I've attached an example file to this email, which contains a saved matrix. The code

sage: A = load("DetBugMatrix?.sobj") sage: A.det()

should trigger the problem. If I recall correctly, I obtained the matrix from the following code

sage: R = Zp(p=5,prec=3,type="capped-abs",print_mode="series") sage: A = random_matrix(R, 10, 10)

Strangely enough (although perhaps not that strange after checking that the error happens during the lookup), the call A.copy().det() returns the determinant without any problems.

I have no clue as to how one could systematically reproduce the bug.

In case it may help, I downloaded SAGE 4.0.2 and built it locally. The machine used is a Lenovo T500 laptop with two intel centrino, running Ubuntu. If there's any further information that would help, please let me know.

Attachments (2)

DetBugMatrix.sobj (2.3 KB) - added by spancratz 11 years ago.
Matrix to trigger the IndexError?
sage-trac_6442.patch (2.2 KB) - added by mjo 8 years ago.
Updated patch with simpler test case and a better comment.

Download all attachments as: .zip

Change History (17)

Changed 11 years ago by spancratz

Matrix to trigger the IndexError?

comment:1 Changed 11 years ago by davidloeffler

  • Component changed from algebra to linear algebra

comment:2 Changed 8 years ago by mjo

  • Cc mjo added
  • Report Upstream set to N/A

We've got two charpoly() algorithms at the moment, but back when this bug was reported, I think the hessenberg algorithm was the default. If we try charpoly() on this matrix,

sage: A = load('/home/mjo/DetBugMatrix.sobj')
sage: A.charpoly(algorithm='hessenberg')
...
ValueError: element valuation cannot be negative.

If we look at the code for charpoly(), we see that the empty hash {} is cached before the attempt to compute charpoly(). In matrix2.pyx,

D = self.fetch('charpoly')

if not D is None:
    if D.has_key(var):
        return D[var]
else:
    D = {}
    self.cache('charpoly',D)

<compute the charpoly>

# Cache the result
D[var] = f
return f  

So if computation of charpoly() fails, we'll have {} cached, and det() will blow up. A full example:

sage: A = load('/home/mjo/DetBugMatrix.sobj')
sage: A.charpoly(algorithm='hessenberg')
...
ValueError: element valuation cannot be negative.
sage: A.det()
...
IndexError: list index out of range
sage: A.charpoly()
(1 + O(5^3))*x^10 + (2 + 4*5 + 2*5^2 + O(5^3))*x^9 + (4 + 4*5 + 4*5^2 + O(5^3))*x^8 + (4 + 5^2 + O(5^3))*x^7 + (4*5^2 + O(5^3))*x^6 + (3 + 5 + 5^2 + O(5^3))*x^5 + (1 + 3*5 + 5^2 + O(5^3))*x^4 + (1 + 4*5 + 4*5^2 + O(5^3))*x^3 + (1 + 4*5 + 4*5^2 + O(5^3))*x^2 + (2 + 4*5 + 4*5^2 + O(5^3))*x + (2*5 + 4*5^2 + O(5^3))
sage: A.det()
2*5 + 4*5^2 + O(5^3)

So the solution, I think, is to avoid caching the empty hash until we know we've got a charpoly.

comment:3 Changed 8 years ago by mjo

  • Authors changed from Sebastian Pancratz to Sebastian Pancratz, Michael Orlitzky
  • Status changed from new to needs_review

Here's a patch that should prevent this problem in the future. I used the smallest matrix I could find for the doctest, but I was just creating them randomly. I'd be happy to replace it with a smaller example.

comment:4 Changed 8 years ago by zimmerma

  • Status changed from needs_review to needs_work
  • Work issues set to problem is not fixed

I tried the attached patch on top of 4.7.2 but the problem with the initial matrix still exists:

[zimmerma@coing tmp]$ sage
----------------------------------------------------------------------
| Sage Version 4.7.2, Release Date: 2011-10-29                       |
| Type notebook() for the GUI, and license() for information.        |
----------------------------------------------------------------------
Loading Sage library. Current Mercurial branch is: 6442
sage: A = load ("DetBugMatrix.sobj")
sage: A.det()
---------------------------------------------------------------------------
IndexError                                Traceback (most recent call last)

/tmp/<ipython console> in <module>()

/usr/local/sage-4.7.2/sage/local/lib/python2.6/site-packages/sage/matrix/matrix2.so in sage.matrix.matrix2.Matrix.det (sage/matrix/matrix2.c:8222)()

/usr/local/sage-4.7.2/sage/local/lib/python2.6/site-packages/sage/matrix/matrix2.so in sage.matrix.matrix2.Matrix.determinant (sage/matrix/matrix2.c:6889)()

IndexError: list index out of range

Paul

comment:5 Changed 8 years ago by zimmerma

  • Keywords sd35.5 added

comment:6 Changed 8 years ago by mjo

The bug wasn't in the saving/loading of matrices, only in the cache code. DetBugMatrix?.sobj contains a broken matrix -- one with an empty dictionary cached as the charpoly(). When you load it from file, it's still broken, so some operations won't work on it.

The patch prevents creating these matrices in the future by fixing the cache bug (hopefully).

The code from the doctest should work only after the patch, because prior to the patch, it would have created a matrix with the same problem as the one in DetBugMatrix?.sobj.

comment:7 Changed 8 years ago by zimmerma

the doctest example can be simplified to:

A = matrix(z, [ [3 + O(5^1), 4 + O(5^1), 4 + O(5^1)],
[2*5^2 + O(5^3), 2 + O(5^1), 1 + O(5^1)],
[5 + O(5^2), 1 + O(5^1), 1 + O(5^1)]])

Paul

comment:8 Changed 8 years ago by zimmerma

  • Status changed from needs_work to needs_review

The bug wasn't in the saving/loading of matrices, only in the cache code [...]

ok, I put it back to "needs review". However the summary is misleading.

Paul

comment:9 Changed 8 years ago by zimmerma

two minor points:

(1) the comment Cache the result on line 1465 should be in fact on line 1470. The code at line 1465 only initializes an empty cache.

(2) it seems to me that if charpoly is called with the same matrix but different variables, the computation is done twice, whereas it would suffice to substitute the first variable by the second one, no? Maybe this can be in a separate ticket.

Paul

comment:10 Changed 8 years ago by mjo

Thanks for the simplified test case, I'll be able to update the patch in a bit.

I think you're correct about (2), but I would do that in a separate ticket since it's unrelated to this problem.

Changed 8 years ago by mjo

Updated patch with simpler test case and a better comment.

comment:11 Changed 8 years ago by mjo

I just updated the patch with your test case.

I moved the "Cache the result" comment to where it belongs, but also added a comment above the code that creates the dictionary, explaining why it occurs near the end of the function.

comment:12 Changed 8 years ago by zimmerma

  • Reviewers set to Paul Zimmermann
  • Status changed from needs_review to positive_review
  • Work issues problem is not fixed deleted

thank you Michael for your changes. All doctests pass. I give a positive review.

Paul

comment:13 Changed 8 years ago by zimmerma

the efficiency issue with the cache is now ticket #12292.

Paul

comment:14 Changed 8 years ago by jdemeyer

  • Milestone set to sage-5.0

comment:15 Changed 8 years ago by jdemeyer

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