New Complexity Results for Jacobian Accumulation

Event Sponsor: 
LANS Informal Seminar
Start Date: 
Oct 23 2009 - 3:30pm to 4:30pm
Building/Room: 
TBA
Location: 
Argonne National Laboratory
Speaker(s): 
Andrew Lyons
Speaker(s) Title: 
MCS
Host: 

The optimal Jacobian accumulation problem is one of the original
combinatorial problems arising in automatic differentiation.
The vast majority of approaches to this problem have attempted to
exploit its similarity to the problem of minimizing fill during LU
factorization of sparse, unsymmetric matrices.
In this talk, we take a complexity-theoretic approach to Jacobian accumulation.
Specifically, we explore relationships between this problem and others
that occur in the context of algebraic and Boolean complexity,
as well as discuss the results that are implied by these relationships.

Miscellaneous Information: