On the computation of Jacobian and Hessian matrices

Our research deals with efficient computation of large Jacobian and Hessian matrices. We are mainly concerned with the sparsity exploiting techniques in computing derivative information.

The computation of derivative information is fundamental to many numerical algorithms. When we want to minimize a function most algorithms will require the gradient and/or the Hessian of the function. When solving a system of nonlinear equations, most numerical methods require the Jacobian matrix. Computing the gradient for large optimization problems will, in the case of a sparse Hessian matrix, be formulated as computing a partially separable function.

Introductory talk on the subject: Graph coloring and Estimating the Jacobian matrix Postscript of the slides,

Publications

Exploiting sparsity in rows and columns

This paper describes how to take advantage of sparsity in both rows and columns in determining a Jacobian matrix. The technique described in this paper uses the forward and the reverse mode of automatic differentiation (AD) in an efficient way to compute the nonzero elements of the matrix.

Computing derivatives by direct determination

In a direct method such as the Curtis, Powell, and Reid (CPR) method or the column segments approachr the nonzeros of the derivative matrix can be obtained by solving a diagonal linear system (defined by the partition of columns into structurally orthogonal groups ) for the unknowns. The element isolation approach another example of a direct method. Here we make a precise definition of direct determination and characterize optimal direct determination.

Computing derivatives by substitution

In a direct method such as the Curtis, Powell, and Reid (CPR) method, or the column segments approch) the nonzeros of the derivative matrix can be obtained by solving a diagonal linear system (defined by the partition of columns into structurally orthogonal groups ) for the unknowns. We may save computational work by not requiring the ``structural orthogonal'' property for the columns (or (or the rows) in the group. Rather we find a grouping of columns such that there are fewer groups and the linear system in the unknowns is triangular. In our work, we demonstrate that under some sparsity restrictions we can obtain triangular systems with fewer groups and thereby requiring reduced computational work. Presented at 3rd International Conference on Automatic Differentiation: From Simulation to Optimization June 19-23, 2000, Nice, France

Computing derivatives by elimination

We suggest a new elimination scheme based on successive column merging. Similar to the other compressed matrix techniques, our method is optimal in terms of the number of AD passes. The nonzeros are solved for from banded systems for which efficient algorithms exist. We also demonstrate that the numerical accuracy of the computed values is comparable to other elimination methods. The compressed matrix is just the result from using the CPR tecnique.

Column segments approach

In the following paper we have proposed a graph coloring based technique to determine sparse Jacobian matrices efficiently. In this approach we compute a group of structurally orthogonal column segments by a single function evaluation.

On the computation of sparse Jacobian matrices and Newton steps

A. K. M. Shahadat Hossain defended on February 26, 1998 his doctoral thesis. On The Computation of Sparse Jacobian Matrices and Newton Steps (Appears as Technical Report 146, Department of Informatics, University of Bergen, March 1998.) PDF (0.7MB). (Postscript version of the thesis Compressed Postscript (gzip)(1.5MB) , Postscript(4.2MB))

Links of Interest