Algorithmic complexity of matrix multiplication in Julia

Julia uses a conservative choice of openBLAS / MKL for linear algebra. These don’t use fast (ie subcubic) matrix multiplication, and afaiu there are no plans to change that in the near future (neither on julia nor on openBLAS/MKL side).

There are alternative competitive libraries like https://github.com/flame/blis (doesn’t use fast matmul either, but afaiu serves as the base for most attempts to make strassen useful in real life), and there is active research to use fast matrix multiplication in real life.

Consider e.g. https://apps.cs.utexas.edu/apps/sites/default/files/tech_reports/GPUStrassen.pdf or https://arxiv.org/pdf/1605.01078.pdf : both papers report cross-overs on the order of 2k-10k square matrices.

So I guess it’s not too unrealistic to see BLIS as a third BLAS provider in julia that by then actually uses Strassen, in maybe 3-5 years.

2 Likes