> Now we do.
This is the part of computer science that I love. It's a branch of philosophy about what is possible with computing machines.
Now all that's left is the matter of making this practical.
But isn't matrix multiplication one of the core basis assumptions of GPU based computing architectures, in particular for AI? That doing math in parallel (which matrices fit into like a glove) gets the fastest result?
Does this imply that a new future architecture could be, at least in theory, get the natural advantage over what we have at the moment? Because if the answer is yes or even a "possibly, too early to tell, requires more R&D", then the existing GPU manufacturers suddenly have a long term problem and we're very likely about to see a decade of a new arms race in computing architecture.
Firstly, faster solutions in fundamental problems can eventually lead to hardware that supports it.
Secondly, this is already happening for sparse matrix multiplication: the nvidia A100 has some sparsity support, to allow making better use of pruned neutral networks, for example.
Thirdly, sparse enough systems, even without the A100, can run faster on cpu than gpu. If you find yourself with one of these problems, you can just choose the correct piece of hardware for the job. Without a sparse algorithm, you are still stuck with the slower dense solution.
Fourthly, giant sparse systems do indeed arise constantly. Just to make one up, consider weather measurements. Each row is a set of measurements from a specific weather station, but there are thousands of stations: it's a sparse set of observations, with some nearby dependencies. Evolving the state in time will often involve solving a giant linear system. (See other comments on the thread about pdes.)
It is absolutely worthwhile research, regardless of how applicable it is to fscking bitcoin.
GPGPU is often about doing few (or one) very big (10^9 x 10^9) matrix op.
You can split big matrix op into smaller ones, but with a big matrix you need to combine the results; with independent smaller matrices you don't.
Isn't it linear for whatever amount of columns?
I assume they use it for solving a overdetermined linear system. E.g. least square fit. The article was not very clear.
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.
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?
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.
Even if it were, as the article mentions, we don’t even know what the optimal (in terms of basic operations on numbers) algorithm for multiplying matrices is. See https://en.wikipedia.org/wiki/Strassen_algorithm for a starting point.
(“Optimal in time” is a different problem. For fixed-size matrices, as often used in computer graphics, that may be known, but even then, there’s the effect of caching, time needed to move data to and from the GPU, etc)
Also, Strassen multiplication and its improvements have a “somewhat reduced numerical stability, and the algorithm also requires significantly more memory compared to the naive algorithm” (https://en.wikipedia.org/wiki/Numerical_stability)
This algorithm may have some of the same problems.
Being random, it likely also will have varying running times. That can be bad for GPUs if they are used to generate real-time graphics.
In total, I don’t see GPU manufacturers being worried about this. They already live with the worry that somebody will discover an O(n²) matrix multiplication algorithm that’s implementable in hardware and more efficient for small n, and I don’t think they lose sleep over that.
> which made no sense at all
The way I made some kind of sense of it was as a variation of making your mouth water. But yeah "whet" makes a lot more sense now.
> This is the part of computer science that I love. It's a branch of philosophy about what is possible with computing machines.
Strictly speaking, if w=2 then their bound of n^{(5 w - 4)/(w + 1)} won't be better than n^w.
Since we can't rule out w=2 we still don't know for sure that solving sparse systems is strictly easier. However this is a good indication.
I think what is most fascinating when you compare it to more conventional philosophy is the fact that you can quantify your advances so easily and precise.