×

Perspectives on information-based complexity. (English) Zbl 0766.68065

The authors survey the issues of information based complexity (IBC) contrast IBC and numerical analysis and give a rebuttal to criticisms of B. N. Parlett [The symmetric eigenvalue problem, Prentice-Hall, Englewood Cliffs, NJ (1980; Zbl 0431.65017), Some basic information on information-based complexity theory, Bull. Am. Math. Soc. (N.S.) 26, 3-27 (1992)] on IBC.

MSC:

68Q25 Analysis of algorithms and problem complexity

Citations:

Zbl 0431.65017
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] I. Babuška, Information-based numerical practice, J. Complexity 3 (1987), no. 3, 331 – 346. · Zbl 0644.65017 · doi:10.1016/0885-064X(87)90019-7
[2] N. S. Bahvalov, Approximate computation of multiple integrals, Vestnik Moskov. Univ. Ser. Mat. Meh. Astr. Fiz. Him. 1959 (1959), no. 4, 3 – 18 (Russian).
[3] -, On optimal bounds for the convergence of quadrature formulas and Monte-Carlo type integration methods for classes of functions, Numerical Methods for the Solution of Differential and Integral Equations and Quadrature Formulas, Nauka, Moscow, 1964, pp. 5-63. (Russian)
[4] -, On the optimality of linear methods for operator approximation in convex classes of functions, U.S.S.R Comput. Math., and Math. Phys. 11 (1971), 244-249. (Russian)
[5] Lenore Blum, Mike Shub, and Steve Smale, On a theory of computation and complexity over the real numbers: NP-completeness, recursive functions and universal machines, Bull. Amer. Math. Soc. (N.S.) 21 (1989), no. 1, 1 – 46. · Zbl 0681.03020
[6] A. Bojańczyk, Complexity of solving linear systems in different models of computation, SIAM J. Numer. Anal. 21 (1984), no. 3, 591 – 603. · Zbl 0563.65014 · doi:10.1137/0721041
[7] Arthur W. Chou, On the optimality of Krylov information, J. Complexity 3 (1987), no. 1, 26 – 40. · Zbl 0626.65027 · doi:10.1016/0885-064X(87)90003-3
[8] F. Gao and G. W. Wasilkowski, On detecting regularity of functions, work in progress, 1990. · Zbl 0852.65013
[9] Michael R. Garey and David S. Johnson, Computers and intractability, W. H. Freeman and Co., San Francisco, Calif., 1979. A guide to the theory of NP-completeness; A Series of Books in the Mathematical Sciences. · Zbl 0411.68039
[10] Michael Golomb and Hans F. Weinberger, Optimal approximation and error bounds, On numerical approximation. Proceedings of a Symposium, Madison, April 21 – 23, 1958, Edited by R. E. Langer. Publication No. 1 of the Mathematics Research Center, U.S. Army, the University of Wisconsin, The University of Wisconsin Press, Madison, Wis., 1959, pp. 117 – 190. · Zbl 0092.05802
[11] Bolesław Z. Kacewicz, On sequential and parallel solution of initial value problems, J. Complexity 6 (1990), no. 2, 136 – 148. · Zbl 0697.65062 · doi:10.1016/0885-064X(90)90002-U
[12] B. Z. Kacewicz and L. Plaskota, On the minimal cost of approximating linear problems based on information with deterministic noise, Numer. Funct. Anal. Optim. 11 (1990), no. 5-6, 511 – 528. · Zbl 0696.65052 · doi:10.1080/01630569008816386
[13] B. Kacewicz and G. W. Wasilkowski, How powerful is continuous nonlinear information for linear problems?, J. Complexity 2 (1986), no. 4, 306 – 316. · Zbl 0618.65043 · doi:10.1016/0885-064X(86)90008-7
[14] J. Kiefer, Sequential minimax search for a maximum, Proc. Amer. Math. Soc. 4 (1953), 502 – 506. · Zbl 0050.35702
[15] Jacek Kuczyński, On the optimal solution of large eigenpair problems, J. Complexity 2 (1986), no. 2, 131 – 162. · Zbl 0599.65021 · doi:10.1016/0885-064X(86)90016-6
[16] J. Kuczyński and H. Woźniakowski, Estimating the largest eigenvalue by the power and Lanczos algorithms with a random start, Report, Dept. of Computer Science, Columbia University, 1989 (to appear in SIMAX). · Zbl 0759.65016
[17] P. Mathé, \?-numbers in information-based complexity, J. Complexity 6 (1990), no. 1, 41 – 66. · Zbl 0723.68047 · doi:10.1016/0885-064X(90)90011-2
[18] C. McMullen, Families of rational maps and iterative root-finding algorithms, Ph.D. thesis, Harvard University, Cambridge., MA, 1985. · Zbl 0634.30028
[19] A. S. Nemirovsky, On optimality of Krylov’s information when solving linear operator equations, J. Complexity 7 (1991), no. 2, 121 – 130. · Zbl 0757.47010 · doi:10.1016/0885-064X(91)90001-E
[20] A. S. Nemirovsky and D. B. Yudin, Problem complexity and method efficiency in optimization, A Wiley-Interscience Publication, John Wiley & Sons, Inc., New York, 1983. Translated from the Russian and with a preface by E. R. Dawson; Wiley-Interscience Series in Discrete Mathematics.
[21] S. M. Nikolskij, On the problem of approximation estimate by quadrature formulas, Uspekhi. Mat. Nauk 5 (1950), 165-177. (Russian)
[22] Erich Novak, Deterministic and stochastic error bounds in numerical analysis, Lecture Notes in Mathematics, vol. 1349, Springer-Verlag, Berlin, 1988. · Zbl 0656.65047
[23] E. W. Packel and J. F. Traub, Information-based complexity, Nature 328 (1987), 29-33.
[24] Edward W. Packel and Henryk Woźniakowski, Recent developments in information-based complexity, Bull. Amer. Math. Soc. (N.S.) 17 (1987), no. 1, 9 – 36. · Zbl 0639.65030
[25] Beresford N. Parlett, The symmetric eigenvalue problem, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1980. Prentice-Hall Series in Computational Mathematics. · Zbl 0431.65017
[26] Beresford N. Parlett, Some basic information on information-based complexity theory, Bull. Amer. Math. Soc. (N.S.) 26 (1992), no. 1, 3 – 27. , https://doi.org/10.1090/S0273-0979-1992-00239-2 J. F. Traub and H. Woźniakowski, Perspectives on information-based complexity, Bull. Amer. Math. Soc. (N.S.) 26 (1992), no. 1, 29 – 52. · Zbl 0765.65042
[27] Michael O. Rabin, Solving linear equations by means of scalar products, Complexity of computer computations (Proc. Sympos., IBM Thomas J. Watson Res. Center, Yorktown Heights, N.Y., 1972) Plenum, New York, 1972, pp. 11 – 20, 187 – 212.
[28] K. F. Roth, On irregularities of distribution, Mathematika 1 (1954), 73 – 79. · Zbl 0057.28604 · doi:10.1112/S0025579300000541
[29] K. F. Roth, On irregularities of distribution. IV, Acta Arith. 37 (1980), 67 – 75. · Zbl 0425.10057
[30] Arthur Sard, Best approximate integration formulas; best approximation formulas, Amer. J. Math. 71 (1949), 80 – 91. · Zbl 0039.34104 · doi:10.2307/2372095
[31] M. Shub, Review of ”Information, uncertainty, complexity” by J. F. Traub, G. W. Wasilkowski, and H. Woźniakowski (Addison-Wesley, Reading, MA, 1983), SIAM Re. 29 (1987), 495-496.
[32] Michael Shub and Steve Smale, On the existence of generally convergent algorithms, J. Complexity 2 (1986), no. 1, 2 – 11. · Zbl 0595.65048 · doi:10.1016/0885-064X(86)90020-8
[33] I. J. Schoenberg, Spline interpolation and best quadrature formulae, Bull. Amer. Math. Soc. 70 (1964), 143 – 148. · Zbl 0136.36202
[34] Eduard L. Stiefel, Kernel polynomials in linear algebra and their numerical applications, Nat. Bur. Standards Appl. Math. Ser. 49 (1958), 1 – 22.
[35] J. F. Traub, G. W. Wasilkowski, and H. Woźniakowski, Information, uncertainty, complexity, Addison-Wesley, Reading, MA, 1983. · Zbl 0522.68041
[36] J. F. Traub, G. W. Wasilkowski, and H. Woźniakowski, Information-based complexity, Computer Science and Scientific Computing, Academic Press, Inc., Boston, MA, 1988. With contributions by A. G. Werschulz and T. Boult. · Zbl 0654.94004
[37] Joe Fred Traub and H. Woźniakowsi, A general theory of optimal algorithms, Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], New York-London, 1980. ACM Monograph Series.
[38] J. F. Traub and H. Woźniakowski, On the optimal solution of large linear systems, J. Assoc. Comput. Mach. 31 (1984), no. 3, 545 – 559. · Zbl 0628.65026 · doi:10.1145/828.830
[39] J. F. Traub and H. Woźniakowski, Information-based complexity: new questions for mathematicians, Math. Intelligencer 13 (1991), no. 2, 34 – 43. · Zbl 0715.68031 · doi:10.1007/BF03024085
[40] G. W. Wasilkowski and F. Gao, On the power of adaptive information for functions with singularities, Math. Comp. 58 (1992), no. 197, 285 – 304. · Zbl 0751.65008
[41] Arthur G. Werschulz, The computational complexity of differential and integral equations, Oxford Mathematical Monographs, The Clarendon Press, Oxford University Press, New York, 1991. An information-based approach; Oxford Science Publications. · Zbl 0754.65129
[42] H. Woźniakowski, A survey of information-based complexity, J. Complexity 1 (1985), no. 1, 11 – 44. · Zbl 0599.68045 · doi:10.1016/0885-064X(85)90020-2
[43] H. Woźniakowski, Average complexity for linear operators over bounded domains, J. Complexity 3 (1987), no. 1, 57 – 80. · Zbl 0625.65046 · doi:10.1016/0885-064X(87)90005-7
[44] H. Woźniakowski, Average case complexity of multivariate integration, Bull. Amer. Math. Soc. (N.S.) 24 (1991), no. 1, 185 – 194. · Zbl 0729.65010
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.