There has been a lot of research on matrix multiplication algorithms in the recent past. For insight, one should read the second volume of Knuth’s wonderful set of books on algorithms [1].
In this paper, the author presents a novel algorithm that finds an approximation of the product of two n × n real matrices. The idea is to compress the matrix product into a polynomial and then use the Fourier transform. The algorithm takes the time O(N + nb) where N is the maximum number of nonzero entries and b is a parameter depicting the time-accuracy tradeoff.
The paper is interesting. Researchers and postgraduate students in computer science will definitely find it useful.
Note that Amir Schoor’s algorithm [2] on sparse matrices is also fast for dense matrices as (1) it is faster to work with rows only than both rows and columns, and (2) the statistical bound for this algorithm is O(n × n) as the n × n exact number of comparisons dominate over the O(d1d2n3) multiplications on average. d1 and d2 are the densities of pre- and post-factor matrices. It happens because when comparisons and multiplications are collectively taken (by weight-based analysis, for example, the time of an operation can be taken as its weight), the comparisons outweigh the “lighter” multiplications. It might be worth trying Pagh’s strategy on Schoor’s algorithm.
