Opened 5 years ago

Closed 5 years ago

#17658 closed defect (fixed)

Incorrect densification of polynomial matrix

Reported by: gagern Owned by:
Priority: critical Milestone: sage-6.5
Component: linear algebra Keywords:
Cc: Merged in:
Authors: Martin von Gagern Reviewers: Vincent Delecroix
Report Upstream: N/A Work issues:
Branch: 84f7248 (Commits) Commit: 84f7248720bb3ab274ed97ac00aa0bc56c072924
Dependencies: Stopgaps:

Description

I found this strange bug, trying to turn a sparse matrix into a dense one.

sage: R1.<a,b> = QQ[]
sage: R2.<c,d> = R1[]
sage: p = a*c+b*d
sage: d = dict(zip([i.degrees() for i in p.monomials()], p.coefficients()))
sage: m = matrix(R1, 2, 2, d)
sage: m
[0 b]
[a 0]
sage: m.dense_matrix()
[0 0]
[0 0]

For some reason the source of the matrix entries seems to play a role here as well: if I simply type in the dict d directly, the result works as expected. So I'm not at all sure what actual component is to blame for this behavior. Omitting the two levels of polynomials, and using QQ for the coefficients, doesn't exhibit this problem either.

Since this can lead to silent wrong answers, I consider this a critical problem.

Change History (9)

comment:1 follow-ups: Changed 5 years ago by pbruin

I wonder if there could be any link with #17527.

comment:2 in reply to: ↑ 1 Changed 5 years ago by gagern

Replying to pbruin:

I wonder if there could be any link with #17527.

I doubt it. loads(dumps(m)) works in my case. One thing which appears to be a factor here is the fact that i.degrees() returns an ETuple.

sage: R1.<a,b> = QQ[]
sage: m = matrix({ETuple((0, 1)): b, ETuple((1, 0)): a})
sage: m.dense_matrix()
[0 0]
[0 0]

But the underlying ring plays a role as well. Particularly, Matrix_generic_sparse seems to be affected while Matrix_integer_sparse or Matrix_modn_sparse are not. Other things which are handled by the generic implementation suffer as well:

sage: matrix(GF(5^2,"z"),{ETuple((1, 1)): 2}).dense_matrix()
[0 0]
[0 0]

comment:3 Changed 5 years ago by gagern

  • Branch set to u/gagern/ticket/17658

comment:4 Changed 5 years ago by gagern

  • Commit set to 84f7248720bb3ab274ed97ac00aa0bc56c072924

Found the problem: ETuple won't convert to regular tuple, and won't have the same hash either. For this reason, we should make sure that our dict keys are regular tuples. Preferably of Python integers.

I left the doctest with the method I used to observe this problem. If you would prefer it in the module-level docstring of the matrix_generic_sparse.pyx file, feel free to move it there or tell me that I should move it. If you have some other place to suggest, let me know.


New commits:

84f7248Convert keys of generic sparse matrix to pair of ints.

comment:5 Changed 5 years ago by gagern

  • Status changed from new to needs_review

comment:6 Changed 5 years ago by gagern

  • Authors set to Martin von Gagern

comment:7 in reply to: ↑ 1 Changed 5 years ago by gagern

Replying to pbruin:

I wonder if there could be any link with #17527.

Not fixed by my fix, so not related.

comment:8 Changed 5 years ago by vdelecroix

  • Reviewers set to Vincent Delecroix
  • Status changed from needs_review to positive_review

follow up: #17663

comment:9 Changed 5 years ago by vbraun

  • Branch changed from u/gagern/ticket/17658 to 84f7248720bb3ab274ed97ac00aa0bc56c072924
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.