Computational complexity in numerical analysis

doi:10.14708/ma.v3i5.1180

Vol 3, No 5 (1975) , 5-27

Computational complexity in numerical analysis

M. Jankowski, H. Woźniakowski

Digital Object Identifier (DOI): 10.14708/ma.v3i5.1180

Abstract

The authors state their objectives as follows. They wish to present to the Polish audience the main aspects of a modern approach to numerical methods based on the concept of computational complexity. Instead of looking for computational methods which compare favorably with other commonly used techniques, and "gradually'' improving numerical methods for solving a given set of problems, one could formulate an optimality criterion based on the cost of performing numerical computations and regard the choice of a computational technique as a problem of optimization theory. This approach is illustrated by specific examples, such as the choice of a fast Fourier transformation, and a solution of an algebraic system of linear equations. (see MR0519667)

Keywords: 65K05 (68A20)

References

[1] R. Bank, G. Birkhoff and D. J. Rose, An 0(N2) Method for Solving Constant Coefficient Boundary Value Problems in Two Dimensions, Report, Harvard University, 1973.

[2] A. Borodin, Homer's Rule is Uniquely Optimal, Theory of Machines and Computations, red. Kahavi i Paz, 1971, str. 45-58.

[3] R. P. Вrent, The computational complexity of iterative methods for systems of nonlinear equations, Proc. Complexity Symposium, Yorktown Heights, March 1972.

[4] R. P. Вrent, S. Winograd and Р. Wоlfе, Optimal iterative process for root-finding, Num. Math. 20 (1973), str. 327-341.

[5] J. W. Сооleу and J. W. Tukeу, An algorithm for the machine calculation of complex Fourier series, Math. Comput. 19 (1965), str. 297-301.

[6] J. Jankowska, O wielowymiarowej metodzie siecznych, referat na naradzie w Solinie, 1973.

[7] J. Jankowska, Multivariate secant method, w przygotowaniu Uniwersytet Warszawski, 1974.

[8] В. Kасewiсz, Iteracyjna metoda całkowa rozwiązywania równań skalarnych, referat na naradzie w Solinie, 1973.

[9] В. Kасewiсz, Iteracyjna metoda całkowa dla układów równań nieliniowych, praca magisterska, Uniwersytet Warszawski, 1974. [10] R. M. Karp, Wykłady w Carnegie-Mellon (nieopublikowane).

[11] A. Kiełbasiński, Podstawowe pojęcia analizy błędów w metodach numerycznych algebry liniowej, Matematyka Stosowana 4 (1975), str. 5-27.

[12] Клюев и КОКОВКИН-Щербак, О минимализации числа арифметических операций при решении линейных алгебраических систем уравнений, Ж. В. М. М. Ф. 5, № 1, (1965), str. 21-33.

[13] Н. Т. Kung, A bound on the multiplication efficiency of iteration, JCSS 7 (4) (1973), str. 334-342.

[14] Н. Т. Kung, Fast evaluation and interpolation, Report of Computer Science Department of Carnegie-Mellon University, January 1973.

[15] Н. Т. Kung, The computational complexity of algebraic numbers, ukaże się w SIAM Journal on Numerical Analysis.

[16] H. T. Kung and J. F. Traub, Computational complexity of one-point and multipoint iteration, Report, Carnegie-Mellon University, 1973. Ukaże się w Complexity of Real Computation pod red. R. Karpa, American Mathematical Society.

[17] H. T. Kung, Optimal order of one-point and multipoint iteration, Journal ACM, Vol. 21, No. 4, October 1974.

[18] H. T. Kung, Optimal order and efficiency for iterations with two evaluations. Report, Carnegie-Mellon University, 1973.

[19] C. A.Micchelli and W. L. Miranker, High order search methods for finding roots. Ukaże się w Journal of the ACM.

[20] J. M. Ortega and W. C. Rheinbоldt, Iterative solution of nonlinear equations in several variables, Academic Press, 1970.

[21] С. H. Reinsch, wykład w Technische Hochschule, München (nieopublikowane).

[22] J. R. Riсe, On the computational complexity of approximation operations, Report, Purdue University, 1973.

[23] J. Rissanen, On optimum root-finding algorithms, Journ. Math. Anal. Appl. 36 (1971), str. 220-225.

[24] M. Shawand J. F.Traub, Оn the number of multiplications for the evaluation of a polynomial and some of its derivatives, Journal ACM, 1974.

[25] V. Strassen, Gaussian elimination is not optimal, Num. Math. 13 (1969), str. 354-356.

[26] V. Strassen, Die Berechmungskomplexitat von elementar symmetrischen Funktionen und von Interpolationskoeffizienten, Num. Math. 20 (1973), str. 238-251. [27] J. F. Traub, Iterative Methods for the Solution of Equations, Prentice Hall, 1964.

[28] J. F. Traub, Computational complexity of iterative processes, SIAM J. Comput. 1 (1972), str. 167-179.

[29] J. F. Traub, An introduction to some current research in numerical computational complexity, Report, Carnegie-Mellon University, 1973.

[30] J. F. Traub, Theory of optimal algorithms, Report, Carnegie-Mellon University, 1973.

[31] J. F. Traub, On functional iteration and the calculation of roots, Proceedings 16th National ACM Conference, 1961.

[32] H. Woźniakowski, O nieliniowych procesach iteracyjnych w metodach numerycznych, praca doktorska, Uniwersytet Warszawski, 1972.

[33] H. Woźniakowski, Iteracyjne metody maksymalne rozwiązywania równań nieliniowych, sprawozdania IMM UW i ZON UW, zeszyty 38 i 44 (1973 i 1974).

[34] H. Woźniakowski, Maximal stationary iterative methods for the solution of operator equations, SIAM J. Numer. Anal. Vol. 11, No. 5, October 1974.

[35] H. Woźniakowski, Generalized information and maximal order of iteration for operation equations, SIAM J. Numer. Anal. Vol. 12, No. 1, March 1975.

[36] H. Woźniakowski, Analiza numeryczna interpolacyjnych metod iteracyjnych rozwiązywania układów równań nieliniowych (w przygotowaniu).

[37] H. Woźniakowski, Analiza numeryczna algorytmów obliczania wartości wielomianów i ich pochodnych, Matematyka Stosowana 3 (1974), str. 79-92. (por. także angielską wersję SIAM J. Numer. Anal. Vol. 11, No. 4, September 1974).

[38] Complexity of Sequential and Parallel Numerical Algorithms (pod red. J. F. Trauba), Academic Press, 1973.

Pages: 5-27

Full Text: PDF