Optimization Online


Optimal Direct Determination of Sparse Jacobian Matrices

Shahadat Hossain (shahadat.hossain***at***uleth.ca)
Trond Steihaug (Trond.Steihaug***at***ii.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

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society