  Recurrence equations lie at the heart of many computational paradigms
including dynamic programming, graph analysis, and linear solvers. These
equations are often expensive to compute and much work has gone into optimizing
them for different situations. The set of recurrence implementations is a large
design space across the set of all recurrences (e.g., the Viterbi and
Floyd-Warshall algorithms), the choice of data structures (e.g., dense and
sparse matrices), and the set of different loop orders. Optimized library
implementations do not exist for most points in this design space, and
developers must therefore often manually implement and optimize recurrences. We
present a general framework for compiling recurrence equations into native code
corresponding to any valid point in this general design space. In this
framework, users specify a system of recurrences, the type of data structures
for storing the input and outputs, and a set of scheduling primitives for
optimization. A greedy algorithm then takes this specification and lowers it
into a native program that respects the dependencies inherent to the recurrence
equation. We describe the compiler transformations necessary to lower this
high-level specification into native parallel code for either sparse and dense
data structures and provide an algorithm for determining whether the recurrence
system is solvable with the provided scheduling primitives. We evaluate the
performance and correctness of the generated code on various computational
tasks from domains including dense and sparse matrix solvers, dynamic
programming, graph problems, and sparse tensor algebra. We demonstrate that
generated code has competitive performance to handwritten implementations in
libraries.
