Numerical stability of nested dissection orderings

Author:
Indu Mati Anand

Journal:
Math. Comp. **35** (1980), 1235-1249

MSC:
Primary 65F05; Secondary 65N20

DOI:
https://doi.org/10.1090/S0025-5718-1980-0583501-0

MathSciNet review:
583501

Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: Rigorous bounds on rounding errors for sparse positive definite matrices are obtained. When used for nested dissection orderings of finite element matrices, the analysis furnishes bounds which are stronger than those for band orderings.

**[1]**Indu Mati Anand,*Numerical stability of nested dissection orderings*, Math. Comp.**35**(1980), no. 152, 1235–1249. MR**583501**, https://doi.org/10.1090/S0025-5718-1980-0583501-0**[2]**Garrett Birkhoff and Alan George,*Elimination by nested dissection*, Complexity of sequential and parallel numerical algorithms (Proc. Sympos., Carnegie-Mellon Univ., Pittsburgh, Pa., 1973) Academic Press, New York, 1973, pp. 221–269. MR**0366010****[3]**I. S. Duff, A. M. Erisman, and J. K. Reid,*On George’s nested dissection method*, SIAM J. Numer. Anal.**13**(1976), no. 5, 686–695. MR**0426396**, https://doi.org/10.1137/0713056**[4]**George E. Forsythe and Cleve B. Moler,*Computer solution of linear algebraic systems*, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1967. MR**0219223****[5]**A. GEORGE,*An Efficient Band Oriented Scheme for Solving**Grid Problems*, Proc. Fall Joint Computer Conference, 1972.**[6]**Alan George,*Nested dissection of a regular finite element mesh*, SIAM J. Numer. Anal.**10**(1973), 345–363. Collection of articles dedicated to the memory of George E. Forsythe. MR**0388756**, https://doi.org/10.1137/0710032**[7]**Alan George,*Numerical experiments using dissection methods to solve 𝑛 by 𝑛 grid problems*, SIAM J. Numer. Anal.**14**(1977), no. 2, 161–179. MR**0440882**, https://doi.org/10.1137/0714011**[8]**J. Alan George,*Solution of linear systems of equations: direct methods for finite element problems*, Sparse matrix techniques (Adv. Course, Technical Univ. Denmark, Copenhagen, 1976) Springer, Berlin, 1977, pp. 52–101. Lecture Notes in Math., Vol. 572. MR**0440883****[9]**Alan George and Joseph W. H. Liu,*An automatic nested dissection algorithm for irregular finite element problems*, SIAM J. Numer. Anal.**15**(1978), no. 5, 1053–1069. MR**507564**, https://doi.org/10.1137/0715069**[10]**Alan George, William G. Poole Jr., and Robert G. Voigt,*Incomplete nested dissection for solving 𝑛 by 𝑛 grid problems*, SIAM J. Numer. Anal.**15**(1978), no. 4, 662–673. MR**0474729**, https://doi.org/10.1137/0715044**[11]**Alan J. Hoffman, Michael S. Martin, and Donald J. Rose,*Complexity bounds for regular finite difference and finite element grids*, SIAM J. Numer. Anal.**10**(1973), 364–369. Collection of articles dedicated to the memory of George E. Forsythe. MR**0347065**, https://doi.org/10.1137/0710033**[12]**Richard J. Lipton, Donald J. Rose, and Robert Endre Tarjan,*Generalized nested dissection*, SIAM J. Numer. Anal.**16**(1979), no. 2, 346–358. MR**526496**, https://doi.org/10.1137/0716027**[13]**J. K. Reid,*A note on the stability of Gaussian elimination*, J. Inst. Math. Appl.**8**(1971), 374–375. MR**0298861****[14]**O. WIDLUND, "On the use of sparsity of finite element systems of equations by Gaussian elimination-type methods,"*Actas del Seminario Sobre Metodos Numericos Modernas*, Vol. 2, Universidad Central de Venezuela, 1974.**[15]**J. H. Wilkinson,*The algebraic eigenvalue problem*, Clarendon Press, Oxford, 1965. MR**0184422****[16]**J. H. Wilkinson,*A priori error analysis of algebraic processes*, Proc. Internat. Congr. Math. (Moscow, 1966) Izdat. “Mir”, Moscow, 1968, pp. 629–640. MR**0233532**

Retrieve articles in *Mathematics of Computation*
with MSC:
65F05,
65N20

Retrieve articles in all journals with MSC: 65F05, 65N20

Additional Information

DOI:
https://doi.org/10.1090/S0025-5718-1980-0583501-0

Article copyright:
© Copyright 1980
American Mathematical Society