×

zbMATH — the first resource for mathematics

On the numerical stability of algorithmic differentiation. (English) Zbl 1238.65013
Summary: In contrast to integration, the differentiation of a function is an ill-conditioned process, if only an oracle is available for its pointwise evaluation. That is, unrelated small variations in the value of the composite function are allowed at nearly identical arguments. In contrast, we show here that, if the function is defined by an evaluation procedure as a composition of arithmetic operations and elementary functions, then automatic, or algorithmic differentiation is backward stable in the sense of Wilkinson. More specifically, the derivative values obtained are exact for a perturbation of the elementary components at the level of the machine precision. We also provide a forward error analysis for both the forward and reverse mode. The theoretical analysis is confirmed by numerical experiments.

MSC:
65D25 Numerical differentiation
65G50 Roundoff error
65Y04 Numerical algorithms for computer arithmetic, etc.
Software:
MAPM; Matlab; mctoolbox; XBLAS
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Berz M, Bischof C, Corliss G, Griewank A (eds) (1996) Computational differentiation: techniques, applications, and tools. Proceedings series. SIAM · Zbl 0857.00033
[2] Bücker M, Corliss G, Hovland P, Naumann U, Norris B (eds) (2005) Automatic differentiation: applications, theory, and tools. In: Lecture notes in computational science and engineering, vol 50. Springer, Berlin
[3] Cacuci D, Weber C, Oblow E, Marable J (1980) Sensitivity theory for general systems of nonlinear equations. Nucl Sci Eng 88: 88–110
[4] Christianson B (1991) Reverse accumulation and accurate rounding error estimate for Taylor series coefficients. Optim Method Softw 1: 81–94 · doi:10.1080/10556789208805508
[5] Corliss, G, Faure, C, Griewank, A, Hascoet, L, Naumann, U (eds) (2002) Automatic differentiation of algorithms–from simulation to optimization. Springer, Berlin · Zbl 0983.68001
[6] Corliss, G, Griewank, A (eds) (1991) Automatic differentiation: theory, implementation, and application. Proceedings series. SIAM, Philadelphia
[7] Griewank A, Utke J, Walther A (2000) Evaluating higher derivative tensors by forward propagation of univariate Taylor series. Math Comput 69(231): 1117–1130 · Zbl 0952.65028 · doi:10.1090/S0025-5718-00-01120-0
[8] Griewank A, Walther A (2008) Principles and techniques of algorithmic differentiation, 2nd edn. SIAM, Philadelphia · Zbl 1159.65026
[9] Higham NJ (2002) Accuracy and stability of numerical algorithms, 2nd edn. SIAM, Philadelphia · Zbl 1011.65010
[10] Iri M (1991) History of automatic differentiation and rounding error estimation. In: Griewank A, Corliss GF (eds) Automatic differentiation of algorithms: theory, implementation, and application. SIAM, Philadelphia, pp 1–16 · Zbl 0782.65028
[11] Iri M, Tsuchiya T, Hoshi M (1988) Automatic computation of partial derivatives and rounding error estimates with applications to large-scale systems of nonlinear equations. Comput Appl Math 24:365–392. Original Japanese version appeared in J Inf Process 26:1411–1420 (1985) · Zbl 0677.65015
[12] Lefèvre V, Muller JM, Tisserand A (1998) Toward correctly rounded transcendentals. IEEE Trans Comput 47(11): 1235–1243 · Zbl 05106162 · doi:10.1109/12.736435
[13] Li XS, Demmel JW, Bailey DH, Henry G, Hida Y, Iskandar J, Kahan W, Kapur A, Martin MC, Tung T, Yoo DJ (2002) Design, implementation and testing of extended and mixed precision blas. ACM Trans Math Softw 28:152–205. http://crd.lbl.gov/\(\sim\)xiaoye/XBLAS · Zbl 1070.65523
[14] Linnainmaa S (1976) Taylor expansion of the accumulated rounding error. BIT (Nordisk Tidskrift for Informationsbehandling) 16(1): 146–160 · Zbl 0332.65024
[15] MathWorks T. Matlab. http://www.mathworks.com/
[16] Michelsen M (1982) The isothermal flash problem. Part I: stability. Fluid Phase Equilibria 9(1): 1–19 · doi:10.1016/0378-3812(82)85001-2
[17] Miller W, Wrathall C (1980) Software for Roundoff analysis of matrix algorithms. Academic Press, New York · Zbl 0474.65017
[18] Muller JM, Brisebarre N, de Dinechin F, Jeannerod CP, Lefèvre V, Melquiond G, Revol N, Stehlé D, Torres S (2010) Handbook of floating-point arithmetic. Birkhäuser, Boston. ACM G.1.0; G.1.2; G.4; B.2.0; B.2.4; F.2.1. ISBN:978-0-8176-4704-9 · Zbl 1197.65001
[19] Ogita T, Rump S, Oishi S (2005) Accurate sum and dot product. SIAM J Sci Comput 26(6): 1955–1988 · Zbl 1084.65041 · doi:10.1137/030601818
[20] Ring M (2001) MAPM, a portable arbitrary precision math library in C. C/C++ Users J. http://www.tc.umn.edu/\(\sim\)ringx004/mapm-main.html
[21] Rump S (2001) Rigorous and portable standard functions. BIT 41(3): 540–562 · Zbl 0994.65017 · doi:10.1023/A:1021971313412
[22] Rump S, Böhm H (1983) Least significant bit evaluation for arithmetic expressions. Computing 30: 189–199 · Zbl 0503.65031 · doi:10.1007/BF02253892
[23] Society IC (2008) IEEE standard for floating-point arithmetic. Tech rep, Microprocessor Standards Committee of the IEEE Computer Society
[24] Speelpenning B (1980) Compiling fast partial derivatives of functions given by algorithms. PhD thesis, University of Illinois at Urbana, Champaign
[25] Wilkinson J (1971) Modern error analysis. SIAM Rev 13: 548–568 · Zbl 0243.65018 · doi:10.1137/1013095
[26] Ziv A (1991) Fast evaluation of elementary mathematical functions with correctly rounded last bit. ACM Trans Math Softw 17: 410–423 · Zbl 0900.65038 · doi:10.1145/114697.116813
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.