An optimal order process for solving finite element equations
Authors:
Randolph E. Bank and Todd Dupont
Journal:
Math. Comp. 36 (1981), 3551
MSC:
Primary 65N30; Secondary 65F10
MathSciNet review:
595040
Fulltext PDF Free Access
Abstract 
References 
Similar Articles 
Additional Information
Abstract: A klevel iterative procedure for solving the algebraic equations which arise from the finite element approximation of elliptic boundary value problems is presented and analyzed. The work estimate for this procedure is proportional to the number of unknowns, an optimal order result. General geometry is permitted for the underlying domain, but the shape plays a role in the rate of convergence through elliptic regularity. Finally, a short discussion of the use of this method for parabolic problems is presented.
 [1]
N. S. Bakhvalov, "On the convergence of a relaxation method with natural constraints on the elliptic operator," Ž. Vyčisl. Mat.i Mat. Fiz., v. 6, 1966, pp. 861885.
 [2]
R. E. Bank & Todd Dupont, "Analysis of a twolevel scheme for solving finite element equations," Numer. Math. (Submitted.)
 [3]
James
H. Bramble, Discrete methods for parabolic equations with
timedependent coefficients, Numerical methods for partial
differential equations (Proc. Adv. Sem., Math. Res. Center, Univ.
Wisconsin, Madison, Wis., 1978) Publ. Math. Res. Center Univ. Wisconsin,
vol. 42, Academic Press, New YorkLondon, 1979, pp. 41–52.
MR 558215
(80m:65063)
 [4]
J.
H. Bramble and S.
R. Hilbert, Bounds for a class of linear functionals with
applications to Hermite interpolation, Numer. Math.
16 (1970/1971), 362–369. MR 0290524
(44 #7704)
 [5]
James
H. Bramble and Miloš
Zlámal, Triangular elements in the finite
element method, Math. Comp. 24 (1970), 809–820. MR 0282540
(43 #8250), http://dx.doi.org/10.1090/S00255718197002825400
 [6]
Achi
Brandt, Multilevel adaptive solutions to
boundaryvalue problems, Math. Comp.
31 (1977), no. 138, 333–390. MR 0431719
(55 #4714), http://dx.doi.org/10.1090/S0025571819770431719X
 [7]
Jim
Douglas Jr., Todd
Dupont, and Richard
E. Ewing, Incomplete iteration for timestepping a Galerkin method
for a quasilinear parabolic problem, SIAM J. Numer. Anal.
16 (1979), no. 3, 503–522. MR 530483
(80f:65117), http://dx.doi.org/10.1137/0716039
 [8]
Jim
Douglas Jr. and Todd
Dupont, Galerkin methods for parabolic equations, SIAM J.
Numer. Anal. 7 (1970), 575–626. MR 0277126
(43 #2863)
 [9]
Jim
Douglas Jr., Effective timestepping methods for the numerical
solution of nonlinear parabolic problems, Mathematics of finite
elements and applications, III (Proc. Third MAFELAP Conf., Brunel Univ.,
Uxbridge, 1978) Academic Press, LondonNew York, 1979,
pp. 289–304. MR 559305
(81j:65116)
 [10]
Todd
Dupont and Ridgway
Scott, Polynomial approximation of functions
in Sobolev spaces, Math. Comp.
34 (1980), no. 150, 441–463. MR 559195
(81h:65014), http://dx.doi.org/10.1090/S00255718198005591957
 [11]
R.
P. Fedorenko, A relaxation method of solution of elliptic
difference equations, Ž. Vyčisl. Mat. i Mat. Fiz.
1 (1961), 922–927 (Russian). MR 0137314
(25 #766)
 [12]
R.
P. Fedorenko, On the speed of convergence of an iteration
process, Ž. Vyčisl. Mat. i Mat. Fiz. 4
(1964), 559–564 (Russian). MR 0182163
(31 #6386)
 [13]
Pierre
Grisvard, Behavior of the solutions of an elliptic boundary value
problem in a polygonal or polyhedral domain, Numerical solution of
partial differential equations, III (Proc. Third Sympos. (SYNSPADE), Univ.
Maryland, College Park, Md., 1975) Academic Press, New York, 1976,
pp. 207–274. MR 0466912
(57 #6786)
 [14]
W. Hackbusch, On the Convergence of a MultiGrid Iteration Applied to Finite Element Equations, Report 778, Universität zu Köln, July 1977.
 [15]
W. Hackbusch, On the Computation of Approximate Eigenvalues and Eigenfunctions of Elliptic Operators by Means of a MultiGrid Method, Report 7710, Universität zu Köln, August 1977.
 [16]
Pierre
Jamet, Estimations d’erreur pour des éléments
finis droits presque dégénérés, Rev.
Française Automat. Informat. Recherche Opérationnelle
Sér. \jname RAIRO Analyse Numérique 10
(1976), no. R1, 43–60 (French, with Loose English summary). MR 0455282
(56 #13521)
 [17]
R.
A. Nicolaides, On multiple grid and related techniques for solving
discrete elliptic systems, J. Computational Phys. 19
(1975), no. 4, 418–431. MR 0413541
(54 #1655)
 [18]
R.
A. Nicolaides, On the 𝑙² convergence of
an algorithm for solving finite element equations, Math. Comp. 31 (1977), no. 140, 892–906. MR 0488722
(58 #8239), http://dx.doi.org/10.1090/S00255718197704887223
 [19]
Donald
J. Rose and Gregory
F. Whitten, A recursive analysis of dissection strategies,
Sparse matrix computations (Proc. Sympos., Argonne Nat. Lab., Lemont, Ill.,
1975) Academic Press, New York, 1976, pp. 59–83. MR 0521077
(58 #25119)
 [20]
Ridgway
Scott, Interpolated boundary conditions in the finite element
method, SIAM J. Numer. Anal. 12 (1975),
404–427. MR 0386304
(52 #7162)
 [21]
Gilbert
Strang and George
J. Fix, An analysis of the finite element method,
PrenticeHall, Inc., Englewood Cliffs, N. J., 1973. PrenticeHall Series in
Automatic Computation. MR 0443377
(56 #1747)
 [22]
Vidar
Thomée, Negative norm estimates and
superconvergence in Galerkin methods for parabolic problems, Math. Comp. 34 (1980), no. 149, 93–113. MR 551292
(81a:65092), http://dx.doi.org/10.1090/S00255718198005512925
 [1]
 N. S. Bakhvalov, "On the convergence of a relaxation method with natural constraints on the elliptic operator," Ž. Vyčisl. Mat.i Mat. Fiz., v. 6, 1966, pp. 861885.
 [2]
 R. E. Bank & Todd Dupont, "Analysis of a twolevel scheme for solving finite element equations," Numer. Math. (Submitted.)
 [3]
 J. H. Bramble, "Discrete methods for parabolic equations with timedependent coefficients," Numerical Methods for PDEs, Academic Press, New York, 1979, pp. 4152. MR 558215 (80m:65063)
 [4]
 J. H. Bramble & S. R. Hilbert, "Bounds for a class of linear functionals with applications to Hermite interpolation," Numer. Math., v. 16, 1971, pp. 362369. MR 0290524 (44:7704)
 [5]
 J. H. Bramble & M. Zlamal, "Triangular elements in the finite element method," Math. Comp., v. 24, 1970, pp. 809821. MR 0282540 (43:8250)
 [6]
 A. Brandt, "Multilevel adaptive solutions to boundary value problems," Math. Comp., v. 31, 1977, pp. 333390. MR 0431719 (55:4714)
 [7]
 Jim Douglas, Jr., Todd Dupont & R. E. Ewing, "Incomplete iteration for timestepping a Galerkin method for a quasilinear parabolic problem," SIAM J. Numer. Anal., v. 16, 1979, pp. 503522. MR 530483 (80f:65117)
 [8]
 Jim Douglas, Jr. & Todd Dupont, "Galerkin methods for parabolic equations," SIAM J. Numer. Anal., v. 7, 1970, pp. 575626. MR 0277126 (43:2863)
 [9]
 Jim Douglas, Jr., "Effective timestepping methods for the numerical solution of nonlinear parabolic problems," The Mathematics of Finite Elements and Applications III, MAFELAP 1978 (J. R. Whiteman, Ed.), Academic Press, New York, 1979, pp. 289304. MR 559305 (81j:65116)
 [10]
 Todd Dupont & Ridgway Scott, "Polynomial approximation of functions in Sobolev spaces," Math Comp., v. 34, 1980, pp. 441463. MR 559195 (81h:65014)
 [11]
 R. P. Fedorenko, "A relaxation method for solving elliptic difference equations," Ž. Vyčisl. Mat. i Mat. Fiz., v. 1, 1961, pp. 922927. MR 0137314 (25:766)
 [12]
 R. P. Fedorenko, "The speed of convergence of one iterative process," Ž. Vyčisl. Mat. i Mat. Fiz., v. 4, 1964, pp. 559564. MR 0182163 (31:6386)
 [13]
 P. Grisvard, "Behavior of the solutions of an elliptic boundary value problem in a polygon or polyhedral domain," Numerical Solution of Partial Differential EquationsIII (B. Hubbard, Ed.), Academic Press, New York, 1975, pp. 207274. MR 0466912 (57:6786)
 [14]
 W. Hackbusch, On the Convergence of a MultiGrid Iteration Applied to Finite Element Equations, Report 778, Universität zu Köln, July 1977.
 [15]
 W. Hackbusch, On the Computation of Approximate Eigenvalues and Eigenfunctions of Elliptic Operators by Means of a MultiGrid Method, Report 7710, Universität zu Köln, August 1977.
 [16]
 P. Jamet, "Estimations d'erreur pour des éléments finis droits presque dégénérés," Rev. Française Automat. Informat. Recherche Operationelle, Ser. Rouge, v. 10, 1976, pp. 4361. MR 0455282 (56:13521)
 [17]
 R. A. Nicolaides, "On multiple grid and related techniques for solving discrete elliptic systems," J. Comput. Phys., v. 19, 1975, pp. 418431. MR 0413541 (54:1655)
 [18]
 R. A. Nicolaides, "On the convergence of an algorithm for solving finite element equations," Math. Comp., v. 31, 1977, pp. 892906. MR 0488722 (58:8239)
 [19]
 D. J. Rose & G. F. Whitten, "A recursive analysis of dissection strategies," Sparse Matrix Computations (J. R. Bunch and D. J. Rose, Eds.), Academic Press, New York, 1976, pp. 5983. MR 0521077 (58:25119)
 [20]
 Ridgway Scott, "Interpolated boundary conditions on the finite element method," SIAM J. Numer. Anal., v. 12, 1975, pp. 404427. MR 0386304 (52:7162)
 [21]
 G. Strang & G. Fix, An Analysis of the Finite Element Method, PrenticeHall, Englewood Cliffs, N. J., 1973. MR 0443377 (56:1747)
 [22]
 V. Thomée, "Negative norm estimates and super convergence in Galerkin methods for parabolic problems," Math. Comp., v. 34, 1980, pp. 93113. MR 551292 (81a:65092)
Similar Articles
Retrieve articles in Mathematics of Computation
with MSC:
65N30,
65F10
Retrieve articles in all journals
with MSC:
65N30,
65F10
Additional Information
DOI:
http://dx.doi.org/10.1090/S00255718198105950402
PII:
S 00255718(1981)05950402
Article copyright:
© Copyright 1981
American Mathematical Society
