3 ms·
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 bas
by Someone 6y ago
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 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 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.