Opened 7 years ago

Closed 2 years ago

# solve_right with matrix right hand side fails over RDF and CDF

Reported by: Owned by: fredrik.johansson peterwicksstringfield major sage-9.1 linear algebra Peter Wicks Stringfield, Jeroen Demeyer, Markus Wageringel Vincent Delecroix N/A 7b07a27 7b07a27d1b0f68f54b0cdbac6c1e5a40f129a127

### 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
```

### 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.

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:

 ​453a126 `Fix minor typo.` ​89fb0af `Fix hidden bug in RDF/CDF matrix multiplication dead error-checking.` ​5dde1c0 `Change RDF/CDF matrix multiplication to accept matrices for B.`

### comment:5 follow-up: ↓ 10 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:

 ​95e4157 `Fix minor typo.` ​8c41acf `Fix hidden bug in RDF/CDF matrix multiplication dead error-checking.` ​5844bbe `Change RDF/CDF matrix multiplication to accept matrices for B.` ​fab2bcd `Improve 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

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:

 ​bd6e4fc `Merge tag '9.1.beta4' into #17405` ​7b07a27 `17405: 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.