3 ms·
While solving a system of linear equations and multiplying matrices are different problems they are related. The straightforward algorithms use N^3 operations
by 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.