Beyond sparsity-using AD to exploit hidden problem structure
by
Arun Verma
Cornell University and Financial Industry solutions center (FISC)
Coauthors: Thomas F. Coleman (Professor, Computer Science, Cornell University)

Many large scale optimization applications (e.g., inverse problems) are very complex in nature. It becomes impractical to consider the function evaluation of such problems as a ``black-box'' function, since the computation is structured. The problem structure could be in terms of sparsity or some other notion of structure, e.g. the computation can be seen as a set of defined structured steps. In this presentation we present some ideas on exploiting structure in problems beyond sparsity using AD:

• Super-sparsity. We recognize two types of super-sparsity structures in derivative matrices:

  • Copies. A set of nonzeros are copies if one of them completely determines all the rest of them in a set. A simple case of this is the symmetry structure in Hessians. In general element (i, j) of Jacobian J(x) is a copy of element (r, s) if J(i, j) and be deduced from J(r, s) and J(r, s) can be deduced from J(i, j).
  • Constants. These are the constant(known) non-zero entries in the Jacobian matrix.

  Super-sparsity is a very common structure, e.g. in finite element methods when many of the Jacobian entries are constants or all the sub-diagonal are the same (copies).

• Structure in Implicit cmputations.

http://www.tc.cornell.edu/~averma/extended.ps

Date received: December 14, 1999