Seminar: March 9

Andrew Lyons, Argonne National Lab

Tight Lower Bounds on the Complexity of Derivative Accumulation

We present results concerning the algebraic complexity of computing certain polynomials over the semiring of real numbers with multiplication and addition. The polynomials we consider are defined in terms of paths in directed acyclic graphs (DAGs) and represent partial derivative computations that are common in high-performance scientific computing. We give a complete characterization of the total and multiplicative complexity for some special classes of DAGs. Moreover, we show that, given such a DAG, an optimal arithmetic circuit computing the corresponding polynomial can be constructed in polynomial time.