[Colloquium] Talk by Andrew Lyons, ANL on March 9, 2010

[Katie Casey]

DEPARTMENT OF COMPUTER SCIENCE

UNIVERSITY OF CHICAGO

Date: Tuesday, March 9, 2010
Time: 3:00 p.m.
Place: Ryerson 251, 1100 E. 58th Street

----------------------------------------------------------

Speaker:	Andrew Lyons

From:		Argonne National Lab

Title: Tight Lower Bounds on the complexity of Derivative Accumulation

Abstract: 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.
Please note that refreshments will be served prior to the talk at 2:30 in RY 255.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20100224/832d6475/attachment.htm