Optimal Direct Determination of Sparse Jacobian Matrices

Shahadat Hossain (shahadat.hossainuleth.ca)
Trond Steihaug (Trond.Steihaugii.uib.no)

Abstract: It is well known that a sparse Jacobian matrix can be determined with fewer function evaluations or automatic differentiation \emph{passes} than the number of independent variables of the underlying function. In this paper we show that by grouping together rows into blocks one can reduce this number further. We propose a graph coloring technique for row partitioned Jacobian matrices to efficiently determine the nonzero entries using a direct method. We characterize \emph{optimal direct determination} and derive results on the optimality of any direct determination technique based on column computation. The computational results from coloring experiments on Harwell-Boeing test matrix collection demonstrate that our row partitioned direct determination approach can yields considerable savings in function evaluations or AD passes over methods based on the Curtis, Powell, and Reid technique.

Keywords: Jacobian matrix, graph coloring, row partitioning

Category 1: Nonlinear Optimization (Unconstrained Optimization )

Category 2: Combinatorial Optimization

Citation: Report N0. 254, Reports in Informatics, Department of Informatics, University of Bergen, Bergen, Norway

Download: [PDF]

Entry Submitted: 11/12/2003
Entry Accepted: 11/12/2003
Entry Last Modified: 11/12/2003

Modify/Update this entry