Opened 7 years ago

Closed 2 years ago

#17405 closed defect (fixed)

solve_right with matrix right hand side fails over RDF and CDF

Reported by: fredrik.johansson Owned by: peterwicksstringfield
Priority: major Milestone: sage-9.1
Component: linear algebra Keywords:
Cc: Merged in:
Authors: Peter Wicks Stringfield, Jeroen Demeyer, Markus Wageringel Reviewers: Vincent Delecroix
Report Upstream: N/A Work issues:
Branch: 7b07a27 (Commits, GitHub, GitLab) Commit: 7b07a27d1b0f68f54b0cdbac6c1e5a40f129a127
Dependencies: Stopgaps:

Status badges

Description

Solving AX=B for a matrix B using solve_right or \ works over many rings, but not RDF or CDF. Example:

sage: MatrixSpace(QQ,10,10,).random_element() \ MatrixSpace(QQ,10,1).random_element()
[   -783/1145]
[ 15697/18320]
[ -4647/18320]
[  -2599/7328]
[ 20289/73280]
[ -3791/18320]
[-70107/36640]
[-12407/36640]
[  -1588/1145]
[  -7059/9160]
sage: MatrixSpace(RR,10,10,).random_element() \ MatrixSpace(RR,10,1).random_element()
[ 0.0620590489221758]
[ -0.584548090301576]
[ -0.106165379993850]
[   1.52004291094317]
[  -1.03573096808637]
[ 0.0822404955372452]
[ -0.145002162865055]
[  0.262055581969539]
[   1.35298542346484]
[-0.0727293754429877]
sage: MatrixSpace(RDF,10,10,).random_element() \ MatrixSpace(RDF,10,1).random_element()
---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
<ipython-input-16-0286e0222123> in <module>()
----> 1 MatrixSpace(RDF,Integer(10),Integer(10),).random_element()  * BackslashOperator() * MatrixSpace(RDF,Integer(10),Integer(1)).random_element()

/home/fredrik/sage-6.3/local/lib/python2.7/site-packages/sage/misc/preparser.pyc in __mul__(self, right)
   1413             (0.0, 0.5, 1.0, 1.5, 2.0)
   1414         """
-> 1415         return self.left._backslash_(right)
   1416 
   1417 

/home/fredrik/sage-6.3/local/lib/python2.7/site-packages/sage/matrix/matrix2.so in sage.matrix.matrix2.Matrix._backslash_ (build/cythonized/sage/matrix/matrix2.c:4193)()

/home/fredrik/sage-6.3/local/lib/python2.7/site-packages/sage/matrix/matrix_double_dense.so in sage.matrix.matrix_double_dense.Matrix_double_dense.solve_right (build/cythonized/sage/matrix/matrix_double_dense.c:11896)()

TypeError: vector of constants over Real Double Field incompatible with matrix over Real Double Field

Change History (12)

comment:1 Changed 7 years ago by peterwicksstringfield

  • Status changed from new to needs_review

I attached a patch to this ticket.

Following the pattern set by the solve_right and solve_left in src/sage/matrix/matrix2.pyx, I tweaked the code in src/sage/matrix/matrix_double_dense.pyx to make solve_right and solve_left for RDF and CDF matrices accept matrices for b. If b is given as a matrix, the answer x will be returned as a matrix.

Please note:

  1. The solve_left in matrix2 uses solve_right, to reduce redundancy; while the solve_left in matrix_double_dense does NOT use solve_right, and instead duplicates some code.
  2. The solve_left and solve_right in matrix_double_dense are now more lenient than those in matrix2, since they accept not just vectors and matrices for b, but also things that can be coerced into vectors (like Python lists).

I didn't try to fix either of those issues.

comment:2 Changed 7 years ago by fredrik.johansson

Why the restriction that the right hand side only has one column?

comment:3 Changed 7 years ago by peterwicksstringfield

  • Branch set to u/peterwicksstringfield/17405_solve_right
  • Owner changed from (none) to peterwicksstringfield

Because it did not even occur to me that the right hand side could have more than one. Thanks for pointing that out.

I let b, the right hand side, have more columns.

I fixed a bug that is in apparently dead code and wouldn't matter even if it wasn't.

I made a branch for this ticket because that seems to be the proper way to do things here.

Also it seems like for non-square matrices the RDF/CDF right_solve and left_solve could just lean on the generic right_solve and left_solve? (The scipy solver needs square matrices, so right now the RDF/CDF code rejects them.) Anyway that would be for a different ticket if it even matters.

EDIT: I think I may have made the branch wrong? Sorry :(. EDIT2: Figured it out. Branch is now correct.

Last edited 7 years ago by peterwicksstringfield (previous) (diff)

comment:4 Changed 7 years ago by git

  • Commit set to 5dde1c0f88abf7ec28e4048da02e76bbbe410ff1

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

453a126Fix minor typo.
89fb0afFix hidden bug in RDF/CDF matrix multiplication dead error-checking.
5dde1c0Change RDF/CDF matrix multiplication to accept matrices for B.

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

  • Milestone changed from sage-6.5 to sage-6.9
  • Reviewers set to Vincent Delecroix

Hello,

  1. You should not try to change the ring if it is already the good one as it performs a copy of the matrix
    sage: m = matrix(ZZ,3,4,range(12))
    sage: m.change_ring(ZZ) is m
    False
    sage: %timeit m.change_ring(ZZ)
    1000000 loops, best of 3: 988 ns per loop
    sage: m = matrix(ZZ,10,10,range(100))
    sage: %timeit m.change_ring(ZZ)
    100000 loops, best of 3: 1.51 µs per loop
    
    This is bad since linear system might involve huge matrices.
  1. In your example, there is no need to print the input matrices A and B (though it is not very bad).

Vincent

comment:6 Changed 6 years ago by vdelecroix

  • Status changed from needs_review to needs_work

comment:7 Changed 6 years ago by jdemeyer

  • Authors set to Peter Wicks Stringfield, Jeroen Demeyer
  • Milestone changed from sage-6.9 to sage-7.2

Having a look at this.

comment:8 Changed 6 years ago by jdemeyer

  • Branch changed from u/peterwicksstringfield/17405_solve_right to u/jdemeyer/17405_solve_right

comment:9 Changed 6 years ago by jdemeyer

  • Commit changed from 5dde1c0f88abf7ec28e4048da02e76bbbe410ff1 to fab2bcdbb57a58e84a9da3b3b7ed13ddc4b6c10d

New commits:

95e4157Fix minor typo.
8c41acfFix hidden bug in RDF/CDF matrix multiplication dead error-checking.
5844bbeChange RDF/CDF matrix multiplication to accept matrices for B.
fab2bcdImprove exceptions

comment:10 in reply to: ↑ 5 Changed 2 years ago by gh-mwageringel

  • Authors changed from Peter Wicks Stringfield, Jeroen Demeyer to Peter Wicks Stringfield, Jeroen Demeyer, Markus Wageringel
  • Branch changed from u/jdemeyer/17405_solve_right to u/gh-mwageringel/17405
  • Commit changed from fab2bcdbb57a58e84a9da3b3b7ed13ddc4b6c10d to 7b07a27d1b0f68f54b0cdbac6c1e5a40f129a127
  • Milestone changed from sage-7.2 to sage-9.1
  • Priority changed from minor to major
  • Status changed from needs_work to needs_review

Replying to vdelecroix:

Hello,

  1. You should not try to change the ring if it is already the good one as it performs a copy of the matrix

I have updated the branch to use the coercion framework to figure out a common parent for A and B and made some minor improvements to the documentation.

I also added a deprecation for the case in which the argument b is not a vector or matrix, which was undocumented behavior and just complicates things for little gain.

In the future, solve_right for RDF/CDF should be updated to also handle the case of a non-square matrix A, which is already supported by generic matrices.


New commits:

bd6e4fcMerge tag '9.1.beta4' into #17405
7b07a2717405: fix solve_right and solve_left over RDF and CDF

comment:11 Changed 2 years ago by vdelecroix

  • Status changed from needs_review to positive_review

comment:12 Changed 2 years ago by vbraun

  • Branch changed from u/gh-mwageringel/17405 to 7b07a27d1b0f68f54b0cdbac6c1e5a40f129a127
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.