3rd European Workshop on Automatic Differentiation

Prof. Andreas Griewank (Berlin Humboldt  University)

Error Analysis for Sparse Matrix Reconstruction

Abstract:  For serveral decades row compression based on the column grouping scheme of Curtis Powell and Reid has been used to estimate sparse Jacobians on the basis of divided differences. It had been demonstrated by Newsam and Ramsdell that in general fewer differences or directional derivatives suffice if one uses more general seed matrices, rather than compressed identities as in the CPR case. However, these schemes were rarely employed for fear of catastrophic error propagation, especially when Vandermonde-like seed matrices are employed. We provide a detailed error analysis for the errors in the reconstructed Jacobians in case of divided differences and directional or adjoint derivatives. Naturally AD turns out to be far superior in terms of accuracy and computational efficiency.

Slides: GriewankJune06.pdf