Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



What is the complexity of related elliptic, parabolic, and hyperbolic problems?

Author: Arthur G. Werschulz
Journal: Math. Comp. 47 (1986), 461-472
MSC: Primary 65P05; Secondary 68Q15
MathSciNet review: 856697
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: Traub and Woźniakowski have dealt with the complexity of some simple partial differential equations. They chose three model problems and showed that the parabolic problem considered had significantly lower complexity than the elliptic problem, which in turn had significantly lower complexity than the hyperbolic problem considered. They asked whether this is true in general. We show that this is not the case by proving that if L is a reasonably well-behaved elliptic operator, then the steady-state heat equation $ Lu = f$, the heat equation $ {\partial _t}u + Lu = f$, and the wave equation $ {\partial _{tt}}u + Lu = f$ all have roughly the same worst-case complexity for f in the unit ball of a certain Sobolev space of smoothness r.

References [Enhancements On Off] (What's this?)

  • [1] S. Agmon, Lectures on Elliptic Boundary Value Problems, Van Nostrand, Princeton, N.J., 1965. MR 0178246 (31:2504)
  • [2] I. Babuška & R. B. Kellogg, "Nonuniform error estimates for the finite element method," SIAM J. Numer. Anal., v. 12, 1975, pp. 868-875. MR 0411201 (53:14939)
  • [3] Ju. M. Berezanskii, Expansions in Eigenfunctions of Self-Adjoint Operators, Transl. Math. Monographs, vol. 17, Amer. Math. Soc., Providence, R.I., 1968. MR 0222718 (36:5768)
  • [4] G. Fairweather, Finite Element Galerkin Methods for Differential Equations, Lecture Notes in Pure and Appl. Math., vol. 34, Marcel Dekker, New York, 1978. MR 0495013 (58:13781)
  • [5] B. Z. Kacewicz & G. Wasilkowski, "How powerful is continuous nonlinear information for linear problems?. (In preparation.)
  • [6] S. G. Krein and Y. I. Petunin, "Scales of Banach spaces," Russian Math. Surveys, v. 21, 1966, pp. 85-160. MR 0193499 (33:1719)
  • [7] D. E. Knuth, "Big omicron and big omega and big theta," SIGACT News, April, 1976, pp. 18-24.
  • [8] J. T. Oden & J. N. Reddy, An Introduction to the Mathematical Theory of Finite Elements, Wiley-Interscience, New York, 1976. MR 0461950 (57:1932)
  • [9] J. F. Traub & H. Woźniakowski, A General Theory of Optimal Algorithms, Academic Press, New York, 1980. MR 584446 (84m:68041)
  • [10] A. G. Werschulz, Finite Element Methods are Not Always Optimal, Mathematics Research Report 82-11, University of Maryland, Baltimore County, June, 1982. To appear in Adv. in Appl. Math. MR 898711 (89c:65127)
  • [11] M. F. Wheeler, "A priori $ {L^2}$-error estimates for Galerkin approximations to parabolic partial differential equations," SIAM J. Numer. Anal., v. 10, 1973, pp. 723-759. MR 0351124 (50:3613)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC: 65P05, 68Q15

Retrieve articles in all journals with MSC: 65P05, 68Q15

Additional Information

Keywords: Optimal solution of partial differential equations, elliptic problems, parabolic problems, hyperbolic problems, computational complexity, information-based complexity, optimal algorithms
Article copyright: © Copyright 1986 American Mathematical Society

American Mathematical Society