8:45 AM / Tuesday, February 13, 1996

Invited Presentation 3
Structure and Efficient Jacobian Calculation

Large nonlinear systems of equations typically exhibit structure in their Jacobian matrices. Sparsity is often a symptom of uderlying structure, but not always. In this presentation, the speakers will discuss the efficient calculation of large structured Jacobian matrices (and gradients of scalar maps) using the techniques of automatic differentiation (AD) while exploiting sparsity and structure (at the user level).

The speaker will show how to use a "bi-coloring" technique to efficiently calcluate sparse Jacobian matrices using a combination of reverse and forward modes of AD, and will present some computational results. He will define a general notion of structure in Jacobian matrices that can often be exploited at the user level to greatly enhance the efficient calculation of Jacobians, even in the absence of sparsity. This view of structure includes the popular classes of partially separable and group partially separable functions. He will indicate why these latter classifications are limiting, and will specialize some of these ideas to the special case of gradient calculation and show that structure can often lead to efficient forward mode determination of the gradient.

Thomas F. Coleman
Cornell University

MEM, 12/29/95