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))
Links of Interest