×

Automatic computation of partial derivatives and rounding error estimates with applications to large-scale systems of nonlinear equations. (English) Zbl 0677.65015

The problem of computing the Jacobian of functions is studied in some detail. The main idea is to evaluate formulas and its (first partial) derivatives by sequences of very simple steps of the form \(v_ i=\phi_ i(u_{i1},u_{i2},...,u_{im})\) where the chain rule is used repeatedly for the derivatives and where the \(\phi_ i\) are predefined basic computations.
The order of the computation is described by a graph. The authors distinguish between bottom-up and top-down traversing this graph, where the classical method is represented by the bottom-up traversing.
The authors develop absolute and probabilistic error estimates. They perform various tests with respect to running time and rounding errors using involved models from chemistry. They report that their algorithm for computing the accurate Jacobian is six times faster than that by numerical differentiation.
Reviewer: G.Opfer

MSC:

65D25 Numerical differentiation
65H10 Numerical computation of solutions to systems of equations
65Yxx Computer aspects of numerical algorithms
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Aho, A. V.; Hopcroft, J. E.; Ullman, J. D., The Design and Analysis of Computer Algorithms (1974), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0286.68029
[2] Alefeld, G.; Herzberger, J., Introduction to Interval Computations (1983), Academic Press: Academic Press New York
[3] Bauer, F. L., Computational graphs and rounding error, SIAM J. Numer. Anal., 11, 87-96 (1974) · Zbl 0337.65028
[4] Baur, W.; Strassen, V., The complexity of partial derivatives, Theoretical Computer Science, 22, 317-330 (1983) · Zbl 0498.68028
[5] Iri, M., Simultaneous computation of functions, partial derivatives and estimates of rounding errors—complexity and practicality, Japan J. Appl. Math., 1, 223-252 (1984) · Zbl 0634.65009
[6] Iri, M.; Kubota, K., Methods of fast automatic differentiation and Applications, Research Memorandum RMI 87-02 (1987), Department of Mathematical Engineering and Instrumentation Physics, University of Tokyo
[7] Iri, M.; Ono, H.; Toda, H., Fast differentiation of composite functions and numerical integration formulas of the Runge—Kutta type for ordinary differential equations (in Japanese), Trans. Info. Process. Soc. Japan, 27, 389-396 (1986)
[8] Iwata, N.; Iri, M., A method of computing partial derivatives of functions of several variables and its implementation (in Japanese), Paper presented at the Research Meeting of the Working Group of Numerical Analysis of Information Processing Society of Japan (December 9, 1983), held on
[9] JUSE (the Union of Japanese Scientists and Engineers), Dynamic Process Simulation (V2) User’s Manual (in Japanese).; JUSE (the Union of Japanese Scientists and Engineers), Dynamic Process Simulation (V2) User’s Manual (in Japanese).
[10] Kim, K. V.; Nesterov, Ju. E.; Skokov, V. A.; Čerkasskiĭ, B. V., Éffektivnyĭ algoritm vyčislenija proizvodnyh i èkstremal’nye zadači (in Russian), Èkonomika i Matematičeskie Metody, 20, 309-318 (1984)
[11] Kim, K. V.; Nesterov, Ju. E.; Čerkasskiĭ, B. V., Ocenka trudoemkosti vyčislenija gradienta (in Russian), Doklady Akademii Nauk SSSR. Matematika, 275, 1306-1309 (1984)
[12] Kim, K. V.; Nesterov, Yu. E.; Cherkassky, B. V., An algorithm for fast differentiations and its applications, (Abstracts of the 12th IFIP Conference on System Modelling and Optimization (September 2-6, 1985), Budapest: Budapest Hungary), 181-182
[13] Rall, L. B., Automatic Differentiation — Techniques and Applications, 120 (1981), Springer: Springer Berlin, Lecture Notes Comput. Sci. · Zbl 0473.68025
[14] Sawyer, J. W., First partial differentiation by computer with an application to categorical data analysis, The American Statistician, 38, 300-308 (1984) · Zbl 0548.65005
[15] Wengert, R. E., A simple automatic derivative evaluation program, Comm. ACM, 7, 463-464 (1964) · Zbl 0131.34602
[16] Wilkinson, J. H., Rounding Errors in Algebraic Processes (1963), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ · Zbl 0113.10606
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.