Hacker News Reader

Comment by Fordec | Hacker News Reader

I'm super 100% out of my depth on this on the math side of things, so bear with me.

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.

View on HN

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.

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.

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.

> When solving a linear system, x and b only have one column

Isn't it linear for whatever amount of columns?

The extension to matrix-matrix is trivial, since a matrix is just a concatenation of columns.

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.

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.

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

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.

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?

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.

As others mentioned, this algorithm isn’t matrix multiplication.

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.

You are confusing the efficiency of an algorithm with its implementation. Worth repeating the famous Dijkstra's dictum here : “Computer Science is no more about computers than astronomy is about telescopes.”

I don't believe I am confused actually. I get this is just an algorithm hypothetical being answered right now. I just care about the telescopes way more than the astronomy and am thinking steps ahead about the meta game of the telescope market. Just as I personally would care far more about the real world implications of P=NP far more than the act of solving it.

I understand that the answer is no here. Because this method is only suitable for the class of linear system thats the equivalent of sparse matrices. GPUs on the other hand are more optimized for the general purpose matrix multiplication here. Unless it can be shown that there are certain economically high-usage scenarios of this class of problems (e.g. the usage magnitude of bitcoin mining), the investment into this specific research does not seem warranted.

Completely ridiculous.

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.

My question is why did GPGPU stuff take so long to take off then? Computer graphics is basically applied linear algebra aka matrix math

computer graphics is doing a lot of very small (4x4 matrices) linear algebra

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.

Ah interesting, that does make a lot of sense.

Reply on news.ycombinator.com