# 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.
• A.K.M. Shahadat Hossain and Trond Steihaug, "Computing a sparse Jacobian matrix by rows and columns , First published as a technical report, Department of Informatics, University of Bergen, 1995. Revised November 1997. Optimization Methods and Software, 10:33-48, 1998 . Abstract and download (HTML) .

### 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.
• Shahadat Hossain and Trond Steihaug, Optimal Direct Determination of Sparse Jacobian Matrices , Technical Report No 254, October 2003, Department of Informatics, University of Bergen, Bergen Norway. Postscript, PDF

### 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
• Shahadat Hossain and Trond Steihaug, "Reducing the Number of AD passes for computing a Sparse Jacobian Matrix, in Automatic Differentiation: From Simulation to Optimization , George Corliss, Christèle Faure, Andreas Griewank, Laurent Hascoët, and Uwe Naumann (eds.), Springer, 2002, Chapter 31, p. 263. Abstract (HTML) , Compressed (gzipped) Postscript, PDF
• Copy of the slides from AD2000 (Postscript of slides)
• Extensions of the results presented at SIAM Annual Meeting, July 9-13, 2001, San Diego, California, USA (Postscript of slides),
• and Optimization 2001, July 23-25, 2001, Aveiro, Portugal. Copy of the slides from Optimization 2001 (Postscript of slides)
• Corrections and further extensions presented at Nordic MPS, November 15-17, 2001 (Postscript of slides),

### 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.
• Trond Steihaug and A.K.M. Shahadat Hossain, "Graph coloring and the estimation of sparse Jacobian matrices with segmented columns , Revision of Report 72 (Revised May 1997), Department of Informatics, University of Bergen, 1992. Abstract (HTML) , Compressed Postscript, PDF
• Shahadat Hossain and Trond Steihaug, "Graph coloring in the estimation of mathematical derivatives" Extended abstract submitted to Computational Symposium: Graph Coloring and its Generalizations Coloring02 in conjunction with "Constraint Programming 2002" at Cornell University, Ithaca, NY USA September 7-8, 2002. Abstract (HTML) and download ,

### 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))