4 ms·

You (and apparently a few of the other commenters here) have some misconceptions about what this article is about. The paper this article is based on is about s

You (and apparently a few of the other commenters here) have some misconceptions about what this article is about. The paper this article is based on is about solving a linear system (i.e. solve for x in the equation Ax = b), not matrix multiplication, which is completely different. From what I can tell, the authors of the paper just claim that their method for solving a certain class of linear systems is faster than the asymptotic cost of the fastest known matrix-matrix multiplication algorithm.

_nalply 6y ago
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.
dumb1224 6y ago
I don't know if it's an appropriate / relevant question to ask, but how does it impact on a majority of programmers / ML practitioners (if they are not into the mathematical details)? Don't get me wrong, solving linear systems with more efficient methods is very appreciated but in my experience the coder only needs to choose which solver to use in a wrapped up library unless you are implementing a very low-level algorithm yourself. For a real example, if the solver isn't good at yielding a solution in a practical time frame (say if I'm fitting models on large genomic dataset of tens of thousands of genes without narrowing down the set of interests), then I might be wrong to use it at all. Isn't that right? Or am I wrong as the article might suggest you could do that in the future?
adrian_b 6y ago
While solving a system of linear equations and multiplying matrices are different problems they are related. The straightforward algorithms use N^3 operations for matrix multiplication and (1/3)*N^3 operations for solving dense systems of linear equations (1 operation being a multiply-add). For both problems, there are more complex algorithms that reduce the value of the exponent from 3 to some lower value, but above 2. Methods that can accelerate matrix multiplication can also accelerate the solution of dense systems of linear equations (because the reduction of terms in the matrix of the coefficients of the system of equations can be done using matrix multiplications, of some sub-blocks of the complete matrix). So the paper demonstrates, as another poster already said, that if the system of equations is sparse, then solving it can always be done faster than if it were dense. In practice this was already usually true, so sparse systems are typically solved using a number of operations proportional with N^2, but there were cases when previous methods could fail. I assume that their contribution is to show a foolproof method, which is guaranteed to be better.

_nalply 6y ago

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.

dumb1224 6y ago

I don't know if it's an appropriate / relevant question to ask, but how does it impact on a majority of programmers / ML practitioners (if they are not into the mathematical details)? Don't get me wrong, solving linear systems with more efficient methods is very appreciated but in my experience the coder only needs to choose which solver to use in a wrapped up library unless you are implementing a very low-level algorithm yourself. For a real example, if the solver isn't good at yielding a solution in a practical time frame (say if I'm fitting models on large genomic dataset of tens of thousands of genes without narrowing down the set of interests), then I might be wrong to use it at all. Isn't that right? Or am I wrong as the article might suggest you could do that in the future?

adrian_b 6y ago

While solving a system of linear equations and multiplying matrices are different problems they are related. The straightforward algorithms use N^3 operations for matrix multiplication and (1/3)*N^3 operations for solving dense systems of linear equations (1 operation being a multiply-add). For both problems, there are more complex algorithms that reduce the value of the exponent from 3 to some lower value, but above 2. Methods that can accelerate matrix multiplication can also accelerate the solution of dense systems of linear equations (because the reduction of terms in the matrix of the coefficients of the system of equations can be done using matrix multiplications, of some sub-blocks of the complete matrix). So the paper demonstrates, as another poster already said, that if the system of equations is sparse, then solving it can always be done faster than if it were dense. In practice this was already usually true, so sparse systems are typically solved using a number of operations proportional with N^2, but there were cases when previous methods could fail. I assume that their contribution is to show a foolproof method, which is guaranteed to be better.