5 ms·
There has been an enormous amount of effort placed into optimizing matrix multiplication. The key here is that the methods have impracticably huge constant fac
by stochastic_monk 8y ago
There has been an enormous amount of effort placed into optimizing matrix multiplication.
The key here is that the methods have impracticably huge constant factors, such that for anything beyond Strassen would necessitate matrices larger than we could conceivably use to be more effective.
This comment also seems to suggest that legions of scientists and engineers aren't trying to optimize matrix multiplication. They are. Here are a few directions to pay attention to:
1. Specialized matrix multiplications for specific sizes and with reduced precision.
For example, Intel's libxsmm, methods for multiplying with reduced precision on [CGT]PU.
2. Structured matrix multiplication
Circulant and FFT-like matrices can be multiplied in linearithmic time. If you can set your problem up to use these instead (see Choromanski's Orthogonal Random Features [2016] or Smola's Deep-Fried Convnets [2015]/Fastfood [2014]), you can dramatically improve the speed and memory efficiency of your application.
3. Hardware-specific optimizations.
Optimizing algorithms by cache efficiency, using FMA (fused multiply-addition) and SIMD instructions, and prefetching all play a big part in improving these multiplications. I'm commenting specifically on CPUs, but similar issues and methods exist on all hardware backends.
In summary, many people are working very hard on improving matrix multiplication. Lower asymptotic complexity algorithms are not the answer for this due to the absurd constant factors they require.
- wbhart 8y agoIs it yet known what the optimal sequence is for 3x3 matrix multiplication (for noncommuting entries, of course)?
- wLMeOv2qjsFOjZG 8y agoNo!
- stochastic_monk 8y agoWouldn’t this be easy to explore exhaustively? 27! is ~1e26, but most of these orderings are obviously terrible ideas.
- wLMeOv2qjsFOjZG 8y agoFor 2x2 matrix multiplication, it is known that Strassen's algorithm is optimal in the sense that there exists no algebraic circuit that uses only 6 "scalar" multiplications. I took your question to ask whether for 3x3 matrix multiplication, the minimum number of scalar multiplications required was similarly known. It is not, and there are more options to take into account than just orderings.