Opened 5 years ago

Closed 5 years ago

#22769 closed defect (fixed)

tensor_product fails when one of the matrices has 0 rows or columns

Reported by: jwiltshiregordon Owned by:
Priority: major Milestone: sage-8.0
Component: linear algebra Keywords: block_matrix, tensor_product
Cc: chapoton, vdelecroix Merged in:
Authors: Travis Scrimshaw Reviewers: Vincent Delecroix
Report Upstream: N/A Work issues:
Branch: cfa028d (Commits, GitHub, GitLab) Commit: cfa028dba188c396a39b77a303a4089fa5c8a38d
Dependencies: Stopgaps:

Status badges

Description

Here is a small example of the error

m1 = matrix(QQ, 1, 0, [])
m2 = matrix(QQ, 2, 2, [1, 2, 3, 4])
print m1.tensor_product(m2)

Of course, the correct tensor product of these two matrices should be given by

matrix(QQ, 2, 0, [])

It could be that the problem is coming from the block matrix structure.

Change History (20)

comment:1 Changed 5 years ago by tscrim

  • Authors changed from John Wiltshire-Gordon to Travis Scrimshaw
  • Branch set to public/linear_algebra/tensor_product_fixes-22769
  • Status changed from new to needs_review

I decided to just special case the tensor_product call to handle these cases.

comment:2 Changed 5 years ago by git

  • Commit set to ab2c200efd0cdb07997fb528ca753067a428774a

Branch pushed to git repo; I updated commit sha1. New commits:

ab2c200Fixing tensor product for 0 x m or m x 0 matrices.

comment:3 Changed 5 years ago by tscrim

  • Cc chapoton vdelecroix added

Green patchbot.

comment:4 follow-up: Changed 5 years ago by vdelecroix

Isn't it a problem with block_matrix

sage: block_matrix(0, 2, [])
Traceback (most recent call last):
...
ValueError: invalid nrows/ncols passed to block_matrix

EDIT: no! since block_matrix has no way to understand the size of the matrices in the empty list!

Note that the following does work

sage: block_matrix(2, 2, [[matrix(0,2), matrix(0,2)], [matrix(0,2), matrix(0,2)]])
[]
sage: parent(_)
Full MatrixSpace of 0 by 4 dense matrices over Integer Ring
Last edited 5 years ago by vdelecroix (previous) (diff)

comment:5 in reply to: ↑ 4 Changed 5 years ago by tscrim

Replying to vdelecroix:

Note that the following does work

sage: block_matrix(2, 2, [[matrix(0,2), matrix(0,2)], [matrix(0,2), matrix(0,2)]])
[]
sage: parent(_)
Full MatrixSpace of 0 by 4 dense matrices over Integer Ring

That should also work as those arguments are:

    -  ``nrows`` - the number of block rows

    -  ``ncols`` - the number of block cols

IMO, changing it so that it goes through that construction seems like overkill in trying to follow the definition exactly rather than equivalent code.

comment:6 follow-up: Changed 5 years ago by vdelecroix

With your patch it looks like the resulting matrix will always be defined over QQ. You would better use self.matrix_space.

comment:7 Changed 5 years ago by git

  • Commit changed from ab2c200efd0cdb07997fb528ca753067a428774a to 63c8f65e52c1684d7599ed86e947edb3b2b10f0d

Branch pushed to git repo; I updated commit sha1. New commits:

7b8fbf3Merge branch 'public/linear_algebra/tensor_product_fixes-22769' of git://trac.sagemath.org/sage into public/linear_algebra/tensor_product_fixes-22769
63c8f65Use matrix_space.

comment:8 in reply to: ↑ 6 ; follow-up: Changed 5 years ago by tscrim

Replying to vdelecroix:

With your patch it looks like the resulting matrix will always be defined over QQ. You would better use self.matrix_space.

That was really bad of me. Initially I should have used the base ring. However, I like the self.matrix_space() approach. I thought about having it return the .zero() element, but then I realized that having it sometimes return an immutable matrix could cause confusion.

comment:9 in reply to: ↑ 8 ; follow-up: Changed 5 years ago by vdelecroix

Replying to tscrim:

Replying to vdelecroix:

With your patch it looks like the resulting matrix will always be defined over QQ. You would better use self.matrix_space.

That was really bad of me. Initially I should have used the base ring. However, I like the self.matrix_space() approach. I thought about having it return the .zero() element, but then I realized that having it sometimes return an immutable matrix could cause confusion.

Can still use .zero().__copy__().

comment:10 in reply to: ↑ 9 Changed 5 years ago by vdelecroix

And note that the empty list is not even needed

sage: MatrixSpace(QQ, 3, 4)()
[0 0 0 0]
[0 0 0 0]
[0 0 0 0]

comment:11 Changed 5 years ago by vdelecroix

There is no need to import matrix anymore. And you would better import block_matrix only if it is needed.

comment:12 Changed 5 years ago by vdelecroix

And it would be good to have a check for parent of the result (not only dimensions)

sage: m1 = MatrixSpace(GF(5), 3, 2).an_element()
sage: m2 = MatrixSpace(GF(5), 0, 4).an_element()
sage: m1.tensor_product(m2).parent()
WHOIAM?

comment:13 Changed 5 years ago by vdelecroix

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

comment:14 Changed 5 years ago by git

  • Commit changed from 63c8f65e52c1684d7599ed86e947edb3b2b10f0d to d573cc2b4c91c65f8ececbea78a256a8d355d478

Branch pushed to git repo; I updated commit sha1. New commits:

d573cc2Taking care of reviewer suggestions.

comment:15 Changed 5 years ago by tscrim

  • Status changed from needs_work to needs_review

Somewhat surprising, it is faster to pass nothing than to make a copy:

sage: MS = MatrixSpace(QQ, 4, 3)
sage: %timeit MS.zero().__copy__()
The slowest run took 18.18 times longer than the fastest. This could mean that an intermediate result is being cached.
100000 loops, best of 3: 5.32 µs per loop
sage: %timeit MS()
The slowest run took 25.40 times longer than the fastest. This could mean that an intermediate result is being cached.
1000000 loops, best of 3: 1.27 µs per loop

I've also taken case of comment:12 and comment:13.

comment:16 Changed 5 years ago by vdelecroix

It is not the copy that takes time. I think that .zero() would better be cached.

sage: MS = MatrixSpace(QQ, 4, 3)
sage: %timeit MS.zero()
100000 loops, best of 3: 4.13 µs per loop
sage: z = MS.zero()
sage: %timeit z.__copy__()
1000000 loops, best of 3: 788 ns per loop
sage: %timeit MS()
1000000 loops, best of 3: 1.07 µs per loop

comment:17 Changed 5 years ago by vdelecroix

  • Status changed from needs_review to positive_review

comment:18 Changed 5 years ago by git

  • Commit changed from d573cc2b4c91c65f8ececbea78a256a8d355d478 to cfa028dba188c396a39b77a303a4089fa5c8a38d
  • Status changed from positive_review to needs_review

Branch pushed to git repo; I updated commit sha1 and set ticket back to needs_review. New commits:

cfa028dUse zero_matrix().__copy__().

comment:19 Changed 5 years ago by tscrim

  • Status changed from needs_review to positive_review

So zero() is cached, but @cached_method does not optimize for aliases that well:

sage: MS = MatrixSpace(QQ, 4, 3)
sage: %timeit MS.zero_matrix()
The slowest run took 1624.29 times longer than the fastest. This could mean that an intermediate result is being cached.
10000000 loops, best of 3: 61.6 ns per loop
sage: %timeit MS.zero()
The slowest run took 10.05 times longer than the fastest. This could mean that an intermediate result is being cached.
100000 loops, best of 3: 4.58 µs per loop

So I converted to use MS.zero_matrix().__copy__(), which ends up being the same path that MS() uses, but is more direct.

I'm allowing myself a change back to positive review since it is essentially a trivial change and tests pass.

comment:20 Changed 5 years ago by vbraun

  • Branch changed from public/linear_algebra/tensor_product_fixes-22769 to cfa028dba188c396a39b77a303a4089fa5c8a38d
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.