POPL 2027
Sun 10 - Sat 16 January 2027 Mexico City, Mexico

Recurrences are ubiquitous in signal and image processing, bioinformatics, numerical computing, combinatorial optimization, and many other domains. Because recurrences seem inherently sequential, they are often implemented serially and thus do not leverage vector instructions in modern hardware. This leaves much of the available, often highly parallel, hardware underutilized.

In this paper, we present an algebra of recurrences over semirings and study algebraic identities that enable vectorization. Using our algebraic framework, we present a number of vectorizing transformations that yield efficient, vectorized implementations across various settings. These transformations naturally extend to 2D and mutually recursive recurrences.

We implement the recurrence algebra and the vectorizing transformations into a compiler called VecRec. VecRec compiles recurrence programs to efficient vectorized C++ implementations. The generated kernels achieve up to an order of magnitude speedup over serial implementations across a wide variety of recurrences, and are faster than existing libraries with manually-crafted vectorization in signal processing and bioinformatics