|
Some basic information on information-based complexity theory
Author(s):
Beresford
N.
Parlett
Journal:
Bull. Amer. Math. Soc.
26
(1992),
3-28.
MSC (1991):
Primary 68Q25;
Secondary 65F99, 65Y20
MathSciNet review:
1102755
Retrieve article in:
PDF
References |
Similar articles |
Additional information
References:
- [Ba, 1987]
- I. Babuska, Information-based numerical practice, J. Complexity \textbf{3} (1987), 331--346. MR 919680
- [Bl, Shu, \& Sm, 1989]
- L. Blum, M. Shub, and S. Smale, On a theory of computation and complexity over the real numbers$;$ NP completeness, recursive functions, and Turing machines, Bull. Amer. Math. Soc. (N.S.) \textbf{21} (1989), 1--46. MR 974426
- [Bo \& Mu, 1975]
- A. Borodin and I. Munro, Computational complexity of algebraic and numeric problems, Amer. Elsevier, New York, 1975. MR 468309
- [Cu \& Wi, 1985]
- J. K. Cullum and R. A. Willoughby, Lanczos algorithms for large symmetric eigenvalue computations, Vol. {\rm I:} Theory, Progr. Comput. Sci., Birkhauser, Basel, 1985. MR 808962
- [Da, 1967]
- J. W. Daniel, The conjugate gradient method for linear and nonlinear operator equations, SIAM J. Numer. Anal. \textbf{4} (1967), 10--26. MR 217987
- [Go \& Va, 1984]
- G. H. Golub and C. V. Van Loan, Advanced matrix computations, Johns Hopkins Univ. Press, Maryland, 1984. MR
- [Je, 1977]
- A. Jennings, Matrix computation for engineers and scientists, John Wiley \& Sons, Chichester, 1977. MR 471244
- [Ka, 1966]
- S. Kaniel, Estimates for some computational techniques in linear algebra, Math. Comp. \textbf{20} (1966), 369--378. MR 234618
- [Ku, 1986]
- J. Kuczynski, A generalized minimal residual algorithm for finding an eigenpair of a large matrix, J. Complexity \textbf{2} (1986), 131--162. MR
- [Ku, 1985]
- J. Kuczynski, Implementation of the GMR algorithm for large symmetric eigenproblems, Tech. Report, Comp. Sci. Dept., Columbia University, New York, 1985. MR
- [Ku \& Wo, 1992]
- J. Kuczynski and H. Wo\'zniakowski, Average case complexity of the symmetric Lanczos algorithm, SIAM J. Matrix Anal. Appl., 1992 (to appear). MR
- [La, 1952]
- C. Lanczos, Solution of systems of linear equations by minimized iterations, J. Res. Nat. Bur. Standards \textbf{49} (1952), 33--51. MR 51583
- [Me, 1963]
- G. Meinardus, \"Uber eine Verallgemeinerung einer Ungleichung von L. V. Kantorowitsch, Numer. Math. \textbf{5} (1963), 14--23. MR 160311
- [O'L, Ste \& Va, 1979]
- D. O'Leary, G. W. Stewart and J. S. Vandergraft, Estimating the largest eigenvalue of a positive definite matrix, Math. Comp. \textbf{33} (1979), 1289--1292. MR 537973
- [Pa, 1980]
- B. N. Parlett, The symmetric eigenvalue problem, Prentice-Hall, New Jersey, 1980. MR 570116
- [Pa, 1982]
- B. N. Parlett, Two monitoring schemes for the Lanczos algorithm, Computing Methods in Applied Sciences and Engineering (V. R. Glowinski and J. L. Lions, eds.), North-Holland Press, 1982. MR
- [Pa, 1984]
- B. N. Parlett, The software scene in the extraction of eigenvalues from sparse matrices, SIAM J. Sci. Statist. Comput. \textbf{5} (1984), 590--603. MR 754487
- [Pa \& No, 1985]
- B. N. Parlett and B. Nour-Omid, The use of refined error bounds when updating eigenvalues of tridiagonals, Linear Algebra Appl. \textbf{68} (1985), 179--219. MR 794821
- [Pa, Si \& Str, 1982]
- B. N. Parlett, H. A. Simon, and L. M. Stringer, On estimating the largest eigenvalue with the Lanczos algorithm, Math. Comp. \textbf{38} (1982), 153--165. MR 637293
- [Pac, 1986]
- E. Packel, {\rm Review of} A general theory of optimal algorithms, by J. F. Traub and H. Wo\'zniakowski (Academic Press, New York, 1980), SIAM Rev. \textbf{28} (1986), 435--437. MR 584446
- [Pac \& Wo, 1987]
- E. Packel and H. Wo\'zniakowski, Recent developments on information-based complexity, Bull. Amer. Math. Soc. (N.S.) \textbf{17} (1987), 9--26. MR 888879
- [Ra, 1972]
- M. O. Rabin, \emph{Solving linear equations by means of scalar products}. MR 391584
- [Sa, 1980]
- Y. Saad, On the rates of convergence of the Lanczos and the block-Lanczos methods, SIAM J. Numer. Anal. \textbf{17} (1980), 687--706. MR 588755
- [Sc, 1979]
- D. S. Scott, How to make the Lanczos algorithm converge slowly, Math. Comp. \textbf{33} (1979), 239--247. MR 514821
- [Sch \& Str, 1971]
- A. Schoenhage and V. Strassen, Schnelle Multiplikation Grosser Zahlen, Commuting \textbf{7} (1971), 281--292. MR 292344
- [Sh, 1977]
- I. Shavitt, The method of configuration interaction, Modern Theoretical Chemistry, vol. 3 (H. P. Schaefer, ed.), Plenum Press, 1977. MR
- [Shu, 1987]
- M. Shub, {\rm Review of} Information, uncertainty, complexity, by J. F. Traub, H. Wo\'zniakowski et al. (Addison-Wesley, Reading, MA 1983), SIAM Rev. \textbf{29} (1987), 495--496. MR
- [Sti, 1958]
- E. Stiefel, Kernel polynomials in linear algebra and their numerical applications, NBS Appl. Math. \textbf{43} (1958), 1--22. MR 92214
- [Str, 1969]
- V. Strassen, Gaussian elimination is not optimal, Numer. Math. \textbf{13} (1969), 354--356. MR 248973
- [Tr \& Wo, 1980]
- J. F. Traub and H. Wo\'zniakowski, A general theory of optimal algorithms, Academic Press, New York, 1980. MR 584446
- [Tr \& Wo, 1984]
- J. F. Traub and H. Wo\'zniakowski, On the optimal solution of large linear systems, J. Assoc. Comput. Mach., \textbf{31} (1984), 545--559. MR 819157
- [Tr \& Wo, 1988]
- J. F. Traub and H. Wo\'zniakowski, Information-based complexity, Academic Press, New York, 1988. MR 958691
- [Tr, Wo \& Wa, 1983]
- J. F. Traub, H. Wo\'zniakowski, and G. Wasilkowski, Information, uncertainty, complexity, Addison-Wesley, Reading, 1983. MR
- [Wi, 1970]
- S. Winograd, On the number of multiplication necessary to compute certain functions, Comm. Pure Appl. Math. \textbf{23} (1970), 165--179. MR 260150
- [Wi, 1980]
- S. Winograd, Arithmetic complexity of computations, CBMS-NSF Regional Conf. Ser. In Appl. Math., vol. 33, SIAM, Philadelphia, 1980. MR 565260
- [Wo, 1985]
- H. Wo\'zniakowski, A survey of information-based complexity, J. Complexity \textbf{1} (1985), 11--44. MR 829868
Similar Articles:
Retrieve articles in Bulletin of the American Mathematical Society
with MSC
(1991):
68Q25, 65F99, 65Y20
Retrieve articles in all Journals with MSC
(1991):
68Q25, 65F99, 65Y20
Additional Information:
DOI:
10.1090/S0273-0979-1992-00239-2
PII:
S 0273-0979(1992)00239-2
|
