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

DOI:
https://doi.org/10.1090/S0025-5718-1986-0856697-6

MathSciNet review:
856697

Full-text PDF Free Access

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 , the heat equation , and the wave equation all have roughly the same worst-case complexity for *f* in the unit ball of a certain Sobolev space of smoothness *r*.

**[1]**Shmuel Agmon,*Lectures on elliptic boundary value problems*, Prepared for publication by B. Frank Jones, Jr. with the assistance of George W. Batten, Jr. Van Nostrand Mathematical Studies, No. 2, D. Van Nostrand Co., Inc., Princeton, N.J.-Toronto-London, 1965. MR**0178246****[2]**I. Babuška and R. B. Kellogg,*Nonuniform error estimates for the finite element method*, SIAM J. Numer. Anal.**12**(1975), no. 6, 868–875. MR**0411201**, https://doi.org/10.1137/0712064**[3]**Ju. M. Berezans′kiĭ,*Expansions in eigenfunctions of selfadjoint operators*, Translated from the Russian by R. Bolstein, J. M. Danskin, J. Rovnyak and L. Shulman. Translations of Mathematical Monographs, Vol. 17, American Mathematical Society, Providence, R.I., 1968. MR**0222718****[4]**Graeme Fairweather,*Finite element Galerkin methods for differential equations*, Marcel Dekker, Inc., New York-Basel, 1978. Lecture Notes in Pure and Applied Mathematics, Vol. 34. MR**0495013****[5]**B. Z. Kacewicz & G. Wasilkowski, "How powerful is continuous nonlinear information for linear problems?. (In preparation.)**[6]**S. G. Kreĭn and Ju. I. Petunin,*Scales of Banach spaces*, Uspehi Mat. Nauk**21**(1966), no. 2 (128), 89–168 (Russian). MR**0193499****[7]**D. E. Knuth, "Big omicron and big omega and big theta,"*SIGACT News*, April, 1976, pp. 18-24.**[8]**J. T. Oden and J. N. Reddy,*An introduction to the mathematical theory of finite elements*, Wiley-Interscience [John Wiley & Sons], New York-London-Sydney, 1976. Pure and Applied Mathematics. MR**0461950****[9]**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. MR**584446****[10]**Arthur G. Werschulz,*Finite element methods are not always optimal*, Adv. in Appl. Math.**8**(1987), no. 3, 354–375. MR**898711**, https://doi.org/10.1016/0196-8858(87)90028-5**[11]**Mary Fanett Wheeler,*A priori 𝐿₂ error estimates for Galerkin approximations to parabolic partial differential equations*, SIAM J. Numer. Anal.**10**(1973), 723–759. MR**0351124**, https://doi.org/10.1137/0710062

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

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

Additional Information

DOI:
https://doi.org/10.1090/S0025-5718-1986-0856697-6

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