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.