  The translation of linear algebra computations into efficient sequences of
library calls is a non-trivial task that requires expertise in both linear
algebra and high-performance computing. Almost all high-level languages and
libraries for matrix computations (e.g., Matlab, Eigen) internally use
optimized kernels such as those provided by BLAS and LAPACK; however, their
translation algorithms are often too simplistic and thus lead to a suboptimal
use of said kernels, resulting in significant performance losses. In order to
combine the productivity offered by high-level languages, and the performance
of low-level kernels, we are developing Linnea, a code generator for linear
algebra problems. As input, Linnea takes a high-level description of a linear
algebra problem; as output, it returns an efficient sequence of calls to
high-performance kernels. Linnea uses a custom best-first search algorithm to
find a first solution in less than a second, and increasingly better solutions
when given more time. In 125 test problems, the code generated by Linnea almost
always outperforms Matlab, Julia, Eigen and Armadillo, with speedups up to and
exceeding 10x.
