www.Autodiff.org - Publication: Efficient Newton Steps without Jacobians

Efficient Newton Steps without Jacobians

- incollection -

Published in
Computational Differentiation: Techniques, Applications, and Tools

Editor(s)
Martin Berz, Christian H. Bischof, George F. Corliss, Andreas Griewank

Year
1996

Publisher
SIAM

Abstract
The computation of Newton steps (NS) is a common subproblem in iterative numerical algorithms. The usual approach requires the calculation of the Jacobian and then the solution of a linear system. The automatic differentiation (ad) technique provides an efficient way to compute a Jacobian, in particular if it has a comparatively stable sparsity structure. In the more general case where Jacobians are dense or have a changing sparsity structure, the efficiency advantages of ad cannot be fully exploited by the usual approach. Because we actually need only the Newton step, not the Jacobian matrix, we introduce an ad method that generally avoids the accumulation of the Jacobian. To this end we perform not only the known node elimination steps on the computational graph but also arc elimination steps. This can reduce the complexity that is measured by the fill-in and makes the computation of Newton steps more efficient. The outline of the method to be introduced were first proposed by Griewank in 1990. Here we show extensions and certain refinements that make the method applicable in practical situations.

Cross-References
Berz1996CDT

AD Tools
ADOL-C

AD Theory and Techniques
Computational Graph, Sparsity

BibTeX
@INCOLLECTION{
         Utke1996ENS,
       author = "Jean Utke",
       editor = "Martin Berz and Christian H. Bischof and George F. Corliss and Andreas Griewank",
       title = "Efficient {N}ewton Steps without {J}acobians",
       booktitle = "Computational Differentiation: Techniques, Applications, and Tools",
       pages = "253--264",
       publisher = "SIAM",
       address = "Philadelphia, PA",
       key = "Utke1996ENS",
       crossref = "Berz1996CDT",
       abstract = "The computation of Newton steps ({\bf NS}) is a common subproblem in iterative
         numerical algorithms. The usual approach requires the calculation of the Jacobian and then the
         solution of a linear system. The automatic differentiation (AD) technique provides an efficient way
         to compute a Jacobian, in particular if it has a comparatively stable sparsity structure. In the
         more general case where Jacobians are dense or have a changing sparsity structure, the efficiency
         advantages of AD cannot be fully exploited by the usual approach. Because we actually need only the
         Newton step, not the Jacobian matrix, we introduce an AD method that generally avoids the
         accumulation of the Jacobian. To this end we perform not only the known node elimination steps on
         the computational graph but also arc elimination steps. This can reduce the complexity that is
         measured by the fill-in and makes the computation of Newton steps more efficient. The outline of the
         method to be introduced were first proposed by Griewank in 1990. Here we show extensions and certain
         refinements that make the method applicable in practical situations.",
       keywords = "Newton steps, arc elimination, Markovitz criterion, fill-in.",
       year = "1996",
       ad_tools = "ADOL-C",
       ad_theotech = "Computational Graph, Sparsity"
}

back

autodiff.org
Username:
Password: