Reducing the number of AD passes for computing a sparse Jacobian matrix

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

Abstract: A reduction in the computational work is possible if we do not require that the nonzeros of a Jacobian matrix be determined directly. If a column or row partition is available, the proposed substitution technique can be used to reduce the number of groups in the partition further. In this chapter, we present a substitution method to determine the structure of sparse Jacobian matrices efficiently using forward, reverse, or a combination of forward and reverse modes of AD. Specifically, if it is true that the difference between the maximum number of nonzeros in a column or row and the number of groups in the corresponding partition is large, then the proposed method can save many AD passes. This assertion is supported by numerical examples.

Keywords: Sparse Jacobians, Indirect methods, Partition

Category 1: Nonlinear Optimization (Nonlinear Systems and Least-Squares )

Category 2: Combinatorial Optimization (Graphs and Matroids )

Citation: To appear in proceedings from 3rd International Conference on Automatic Differentiation: From Simulation to Optimization June 19-23, 2000, Nice, France. Springer 2001

Download: [Postscript]

Entry Submitted: 01/22/2001
Entry Accepted: 01/22/2001
Entry Last Modified: 01/22/2001

Modify/Update this entry