Compiling General-size Linear Algebra Expressions using Equality Graphs

A general principle in programming language research is enhancing the productivity of humans by enabling us to code at high levels of abstraction without compromising on computer efficiency. This project focuses on linear algebra computations, which are ubiquitous in science and engineering.

It will offer a syntax that resembles mathematical notation (think Matlab) but with greatly improved quality of the compiled code. Many approaches exist, but they fail to generate efficient code even in simple cases. We have developed Linnea, a linear algebra compiler, that is now considered state-of-the-art.

Linnea is a sophisticated tool, yet it has one major shortcoming: All matrix sizes must be known at compile time.

Tools like Linnea generate code for one of many equivalent forms of each expression, but the optimal form actually depends on the matrix sizes (e.g., matrix chains). Thus, the limitation is inherent and further progress requires a new approach.

Our goal is to eliminate this limitation by developing new theory and algorithms that operate mostly at compile time (before the matrix sizes are known) and partially at run time.

Specifically, we will tackle the problem by adapting and extending so-called equality graphs and equality saturation (techniques developed for automated theorem provers and optimizing compilers).

Advancing research in this direction is highly important, since in most applications linear algebra expressions are not made concrete until runtime.