Dept. of Geophysics Colloquium: On the Algebra of Moving Window Calculations

Zoom: https://tau-ac-il.zoom.us/j/85032703038

Abstract:

Moving window calculations arise throughout applied mathematics, computer science, and engineering. Familiar examples include moving sums, maxima, and filters, as well as general windowed recurrences. In this talk, we show that a large class of such calculations admits a common algebraic formulation. When associativity of the underlying operation obtains moving window calculations can be recast as exponentiation in a semidirect product, bringing efficient powering algorithms to bear. In more general settings, the algebraic property of semi-associativity provides the right framework for representing compositions of updates and understanding when efficient computation is still possible. This point of view not only unifies a broad family of examples, but also leads naturally to compact vectorized implementations, making the methods well suited to modern GPU architectures. This is joint work with David Maslen.

A more detailed discussion is available in this monograph.

Event Organizer: Dr. Lior Rubanenko