www.Autodiff.org - Publication: Computing Sparse Jacobian Matrices Optimally

Computing Sparse Jacobian Matrices Optimally

- incollection -

Author(s)
Shahadat Hossain , Trond Steihaug

Published in
Automatic Differentiation: Applications, Theory, and Implementations

Editor(s)
H. Martin Bücker, George F. Corliss, Paul D. Hovland, Uwe Naumann, Boyana Norris

Year
2005

Publisher
Springer

Abstract
A restoration procedure based on a priori knowledge of sparsity patterns of the compressed Jacobian matrix rows is proposed. We show that if the rows of the compressed Jacobian matrix contain certain sparsity patterns the unknown entries can essentially be restored with cost at most proportional to substitution while the number of matrix-vector products to be calculated still remains optimal. We also show that the conditioning of the reduced linear system can be improved by employing a combination of direct and indirect methods of computation. Numerical test results are presented to demonstrate the effectiveness of our proposal.

Cross-References
Bucker2005ADA

AD Theory and Techniques
Sparsity

BibTeX
@INCOLLECTION{
         Hossain2005CSJ,
       author = "Shahadat Hossain and Trond Steihaug",
       title = "Computing Sparse {J}acobian Matrices Optimally",
       pages = "77--87",
       abstract = "A restoration procedure based on a priori knowledge of sparsity patterns of the
         compressed Jacobian matrix rows is proposed. We show that if the rows of the compressed Jacobian
         matrix contain certain sparsity patterns the unknown entries can essentially be restored with cost
         at most proportional to substitution while the number of matrix-vector products to be calculated
         still remains optimal. We also show that the conditioning of the reduced linear system can be
         improved by employing a combination of direct and indirect methods of computation. Numerical test
         results are presented to demonstrate the effectiveness of our proposal.",
       crossref = "Bucker2005ADA",
       booktitle = "Automatic Differentiation: {A}pplications, Theory, and Implementations",
       year = "2005",
       editor = "H. Martin B{\"u}cker and George F. Corliss and Paul D. Hovland and Uwe
         Naumann and Boyana Norris",
       publisher = "Springer",
       ad_theotech = "Sparsity",
       doi = "10.1007/3-540-28438-9_7"
}

back

autodiff.org
Username:
Password: