Opened 7 years ago

Closed 7 years ago

#12689 closed defect (fixed)

Segfault in solve_left for sparse matrices over ZZ

Reported by: davidloeffler Owned by: jason, was
Priority: critical Milestone: sage-5.0
Component: linear algebra Keywords: segfault
Cc: Merged in: sage-5.0.beta10
Authors: William Stein Reviewers: Douglas McNeil
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description

Calling solve_left on a sparse integer matrix results in an instant segfault:

sage: A = identity_matrix(ZZ, 2, sparse=True)
sage: B = identity_matrix(ZZ, 2, sparse=True)
sage: A.solve_left(B)
/storage/masiao/sage-5.0.beta8/spkg/bin/sage: line 308:  7843 Segmentation fault      sage-ipython "$@" -i

Attachments (1)

trac_12689.patch (1.8 KB) - added by was 7 years ago.

Download all attachments as: .zip

Change History (11)

comment:1 Changed 7 years ago by dsm

We can push the bug a bit farther back:

sage: A = identity_matrix(ZZ, 2, sparse=True)
sage: B = identity_matrix(ZZ, 2, sparse=True)
sage: A.augment(B)
[1 0 1 0]
[0 1 0 1]
sage: A.change_ring(QQ).augment(B.change_ring(QQ))
[1 0 1 0]
[0 1 0 1]
sage: A.change_ring(QQ).augment(B)
[  1   0 1/0   0]
[  0   1   0 1/0]

1/0 doesn't look right..

comment:2 Changed 7 years ago by dsm

Ah, okay. I think I see what's going on. In matrix_sparse.pyx's augment:

        cdef Matrix_sparse other = right.sparse_matrix()

    [...]

        if not (self._base_ring is right.base_ring()):
            right = right.change_ring(self._base_ring)

attemps to change the right base ring to agree, but during the insertion process, it still uses the old unchanged one:

        for i, j in right.nonzero_positions(copy=False):
            Z.set_unsafe(i, j + self._ncols, other.get_unsafe(i,j))

If we instead use

            other = other.change_ring(self._base_ring)

then everything seems to work:

sage: z = A.change_ring(QQ).augment(B)
[skipping debugging output]
sage: z
[1 0 1 0]
[0 1 0 1]

and

sage: A.solve_left(B)
[1 0]
[0 1]
sage: parent(_)
Full MatrixSpace of 2 by 2 sparse matrices over Rational Field

So I think the fix is a one-liner. Any takers?

comment:3 Changed 7 years ago by was

Any takes?

I'll post a patch if you'll review it :-)

comment:4 Changed 7 years ago by dsm

Deal. Should probably add tests both in augment for the incompatible-ring bug and in solve_left for the original.

comment:5 Changed 7 years ago by dsm

Although since uses Z._subdivide_on_augment(self, right) uses right too, maybe it's a two-liner. :)

Changed 7 years ago by was

comment:6 Changed 7 years ago by was

  • Status changed from new to needs_review

comment:7 follow-up: Changed 7 years ago by dsm

Running test suite now, but it looks fine. Don't forget that we have the new ":trac:12689" markup now, though!

comment:8 in reply to: ↑ 7 Changed 7 years ago by was

Replying to dsm:

Running test suite now, but it looks fine. Don't forget that we have the new ":trac:12689" markup now, though!

Cool. I've never heard of it.

comment:9 Changed 7 years ago by dsm

  • Authors set to William Stein
  • Reviewers set to Douglas McNeil
  • Status changed from needs_review to positive_review

Patch applies against 5.0.beta8 (and 4.8) and runs; fixes the OP's symptom; has a doctest; doesn't introduce new doctest failures (I have quite a few on beta8 but they came before, and it works cleanly against 4.8); and it's clear what the bug was and why this patch fixes it.

Positive review.

comment:10 Changed 7 years ago by jdemeyer

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