What is the complexity of related elliptic, parabolic, and hyperbolic problems?
Author:
Arthur G. Werschulz
Journal:
Math. Comp. 47 (1986), 461472
MSC:
Primary 65P05; Secondary 68Q15
MathSciNet review:
856697
Fulltext 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 wellbehaved elliptic operator, then the steadystate heat equation , the heat equation , and the wave equation all have roughly the same worstcase 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.TorontoLondon, 1965. MR 0178246
(31 #2504)
 [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
(53 #14939)
 [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 (36 #5768)
 [4]
Graeme
Fairweather, Finite element Galerkin methods for differential
equations, Marcel Dekker, Inc., New YorkBasel, 1978. Lecture Notes in
Pure and Applied Mathematics, Vol. 34. MR 0495013
(58 #13781)
 [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
(33 #1719)
 [7]
D. E. Knuth, "Big omicron and big omega and big theta," SIGACT News, April, 1976, pp. 1824.
 [8]
J.
T. Oden and J.
N. Reddy, An introduction to the mathematical theory of finite
elements, WileyInterscience [John Wiley & Sons], New
YorkLondonSydney, 1976. Pure and Applied Mathematics. MR 0461950
(57 #1932)
 [9]
Joe
Fred Traub and H.
Woźniakowsi, A general theory of optimal algorithms,
Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], New
YorkLondon, 1980. ACM Monograph Series. MR 584446
(84m:68041)
 [10]
Arthur
G. Werschulz, Finite element methods are not always optimal,
Adv. in Appl. Math. 8 (1987), no. 3, 354–375.
MR 898711
(89c:65127), http://dx.doi.org/10.1016/01968858(87)900285
 [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
(50 #3613)
 [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. 868875. MR 0411201 (53:14939)
 [3]
 Ju. M. Berezanskii, Expansions in Eigenfunctions of SelfAdjoint 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. 85160. MR 0193499 (33:1719)
 [7]
 D. E. Knuth, "Big omicron and big omega and big theta," SIGACT News, April, 1976, pp. 1824.
 [8]
 J. T. Oden & J. N. Reddy, An Introduction to the Mathematical Theory of Finite Elements, WileyInterscience, 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 8211, University of Maryland, Baltimore County, June, 1982. To appear in Adv. in Appl. Math. MR 898711 (89c:65127)
 [11]
 M. F. Wheeler, "A priori error estimates for Galerkin approximations to parabolic partial differential equations," SIAM J. Numer. Anal., v. 10, 1973, pp. 723759. 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
DOI:
http://dx.doi.org/10.1090/S00255718198608566976
PII:
S 00255718(1986)08566976
Keywords:
Optimal solution of partial differential equations,
elliptic problems,
parabolic problems,
hyperbolic problems,
computational complexity,
informationbased complexity,
optimal algorithms
Article copyright:
© Copyright 1986
American Mathematical Society
