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.
To appear in proceedings from 3rd International Conference on Automatic Differentiation: From Simulation to Optimization June 19-23, 2000, Nice, France. Springer 2001