5 ms·

Perhaps it is possible to go backwards from solving to matrix multiplication. Your example Ax = b can be solved using a matrix multiplication with the inverse m

Perhaps it is possible to go backwards from solving to matrix multiplication. Your example Ax = b can be solved using a matrix multiplication with the inverse matrix: x = A^-1 b. So if one can solve a linear system faster than by matrix multiplication, one could try to use the same algorithm for matrix multiplication.

FartyMcFarter 6y ago
When solving a linear system, x and b only have one column. So unless the algorithm is general enough to not have that limitation, it won't be applicable to general matrix multiplication.
- rightbyte 6y ago
  > When solving a linear system, x and b only have one column Isn't it linear for whatever amount of columns?
- conjectures 6y ago
  The extension to matrix-matrix is trivial, since a matrix is just a concatenation of columns.
  - FartyMcFarter 6y ago
    A matrix is a concatenation of columns yes, but how does that help us multiply matrices by using a sparse linear-system solver? Perhaps it's trivial but I don't see it.
rightbyte 6y ago
A Monte Carlo(?) method surely has no advantage for multiplication. I assume they use it for solving a overdetermined linear system. E.g. least square fit. The article was not very clear.
derangedHorse 6y ago
But even that would be limited since not all matrices have inverses. They do have 'pseudo-inverse's (also called the Moore–Penrose inverse) but he applicability there might be limited
yorwba 6y ago
If you want A^-1 b, where A^-1 is a known n×n matrix and b an n-dimensional column vector, you can just use the naive method, which takes O(n^2) steps. If you use the new linear solver, you'll need O(n^2.332) steps just for that, and additionally you'll have to find A somehow. So matrix-vector multiplication is faster. In the article, they're comparing it to multiplication of square matrices, which is slower, but only slower than solving a single system of equations. If you wanted to multiply square matrices with the new linear solver, you'd have to solve n different systems of equations with shared coefficients, which would end up slower than the naive O(n^3) method, unless you can share work across instances somehow.

FartyMcFarter 6y ago

When solving a linear system, x and b only have one column. So unless the algorithm is general enough to not have that limitation, it won't be applicable to general matrix multiplication.

rightbyte 6y ago
> When solving a linear system, x and b only have one column Isn't it linear for whatever amount of columns?
conjectures 6y ago
The extension to matrix-matrix is trivial, since a matrix is just a concatenation of columns.
- FartyMcFarter 6y ago
  A matrix is a concatenation of columns yes, but how does that help us multiply matrices by using a sparse linear-system solver? Perhaps it's trivial but I don't see it.

rightbyte 6y ago

A Monte Carlo(?) method surely has no advantage for multiplication. I assume they use it for solving a overdetermined linear system. E.g. least square fit. The article was not very clear.

derangedHorse 6y ago

But even that would be limited since not all matrices have inverses. They do have 'pseudo-inverse's (also called the Moore–Penrose inverse) but he applicability there might be limited

yorwba 6y ago

If you want A^-1 b, where A^-1 is a known n×n matrix and b an n-dimensional column vector, you can just use the naive method, which takes O(n^2) steps. If you use the new linear solver, you'll need O(n^2.332) steps just for that, and additionally you'll have to find A somehow. So matrix-vector multiplication is faster. In the article, they're comparing it to multiplication of square matrices, which is slower, but only slower than solving a single system of equations. If you wanted to multiply square matrices with the new linear solver, you'd have to solve n different systems of equations with shared coefficients, which would end up slower than the naive O(n^3) method, unless you can share work across instances somehow.