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 = "253264",
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 fillin 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, fillin.",
year = "1996",
ad_tools = "ADOLC",
ad_theotech = "Computational Graph, Sparsity"
}
