An optimal order process for solving finite element equations

Bank, Randolph E.; Dupont, Todd

doi:10.1090/S0025-5718-1981-0595040-2

An optimal order process for solving finite element equations
HTML articles powered by AMS MathViewer

by Randolph E. Bank and Todd Dupont PDF

Math. Comp. 36 (1981), 35-51 Request permission

Abstract:

A k-level 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.

References

Ž. Vyčisl. Mat.i Mat. Fiz.

Numer. Math.

James H. Bramble, Discrete methods for parabolic equations with time-dependent 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 York-London, 1979, pp. 41–52. MR 558215
J. H. Bramble and S. R. Hilbert, Bounds for a class of linear functionals with applications to Hermite interpolation, Numer. Math. 16 (1970/71), 362–369. MR 290524, DOI 10.1007/BF02165007
James H. Bramble and Miloš Zlámal, Triangular elements in the finite element method, Math. Comp. 24 (1970), 809–820. MR 282540, DOI 10.1090/S0025-5718-1970-0282540-0
Achi Brandt, Multi-level adaptive solutions to boundary-value problems, Math. Comp. 31 (1977), no. 138, 333–390. MR 431719, DOI 10.1090/S0025-5718-1977-0431719-X
Jim Douglas Jr., Todd Dupont, and Richard E. Ewing, Incomplete iteration for time-stepping a Galerkin method for a quasilinear parabolic problem, SIAM J. Numer. Anal. 16 (1979), no. 3, 503–522. MR 530483, DOI 10.1137/0716039
Jim Douglas Jr. and Todd Dupont, Galerkin methods for parabolic equations, SIAM J. Numer. Anal. 7 (1970), 575–626. MR 277126, DOI 10.1137/0707048
Jim Douglas Jr., Effective time-stepping 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, London-New York, 1979, pp. 289–304. MR 559305
Todd Dupont and Ridgway Scott, Polynomial approximation of functions in Sobolev spaces, Math. Comp. 34 (1980), no. 150, 441–463. MR 559195, DOI 10.1090/S0025-5718-1980-0559195-7
R. P. Fedorenko, A relaxation method of solution of elliptic difference equations, Ž. Vyčisl. Mat i Mat. Fiz. 1 (1961), 922–927 (Russian). MR 137314
R. P. Fedorenko, On the speed of convergence of an iteration process, Ž. Vyčisl. Mat i Mat. Fiz. 4 (1964), 559–564 (Russian). MR 182163
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

On the Convergence of a Multi-Grid Iteration Applied to Finite Element Equations

On the Computation of Approximate Eigenvalues and Eigenfunctions of Elliptic Operators by Means of a Multi-Grid Method

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. 10 (1976), no. R-1, 43–60 (French, with Loose English summary). MR 0455282
R. A. Nicolaides, On multiple grid and related techniques for solving discrete elliptic systems, J. Comput. Phys. 19 (1975), no. 4, 418–431. MR 413541, DOI 10.1016/0021-9991(75)90072-8
R. A. Nicolaides, On the $l^{2}$ convergence of an algorithm for solving finite element equations, Math. Comp. 31 (1977), no. 140, 892–906. MR 488722, DOI 10.1090/S0025-5718-1977-0488722-3
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
Ridgway Scott, Interpolated boundary conditions in the finite element method, SIAM J. Numer. Anal. 12 (1975), 404–427. MR 386304, DOI 10.1137/0712032
Gilbert Strang and George J. Fix, An analysis of the finite element method, Prentice-Hall Series in Automatic Computation, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1973. MR 0443377
Vidar Thomée, Negative norm estimates and superconvergence in Galerkin methods for parabolic problems, Math. Comp. 34 (1980), no. 149, 93–113. MR 551292, DOI 10.1090/S0025-5718-1980-0551292-5