Numerical stability of nested dissection orderings
Author:
Indu Mati Anand
Journal:
Math. Comp. 35 (1980), 12351249
MSC:
Primary 65F05; Secondary 65N20
MathSciNet review:
583501
Fulltext PDF Free Access
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
(82c:65014), http://dx.doi.org/10.1090/S00255718198005835010
 [2]
Garrett
Birkhoff and Alan
George, Elimination by nested dissection, Complexity of
sequential and parallel numerical algorithms (Proc. Sympos.,
CarnegieMellon Univ., Pittsburgh, Pa., 1973) Academic Press, New York,
1973, pp. 221–269. MR 0366010
(51 #2262)
 [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
(54 #14339)
 [4]
George
E. Forsythe and Cleve
B. Moler, Computer solution of linear algebraic systems,
PrenticeHall, Inc., Englewood Cliffs, N.J., 1967. MR 0219223
(36 #2306)
 [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
(52 #9590)
 [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
(55 #13750)
 [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
(55 #13751)
 [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
(80a:65085), http://dx.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
(57 #14363)
 [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 (49 #11785)
 [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
(80d:65041), http://dx.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
(45 #7910)
 [14]
O. WIDLUND, "On the use of sparsity of finite element systems of equations by Gaussian eliminationtype 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
(32 #1894)
 [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
(38 #1853)
 [1]
 I. M. ANAND, Numerical Stability of Nested Dissection Orderings, Ph.D. Thesis, New York University, New York, 1979. MR 583501 (82c:65014)
 [2]
 G. BIRKHOFF & A. GEORGE, "Elimination by nested dissection," in Complexity of Sequential and Parallel Algorithms (J. Traub, Ed.), Academic Press, New York, 1973, pp. 221269. MR 0366010 (51:2262)
 [3]
 I. S. DUFF, A. M. ERISMAN & J. K. REID, "On George's nested dissection algorithm," SIAM J. Numer. Anal., v. 13, 1976, pp. 686695. MR 0426396 (54:14339)
 [4]
 G. E. FORSYTHE & C. B. MOLER, Computer Solution of Linear Algebraic Systems, PrenticeHall, Englewood Cliffs, N. J., 1967. MR 0219223 (36:2306)
 [5]
 A. GEORGE, An Efficient Band Oriented Scheme for Solving Grid Problems, Proc. Fall Joint Computer Conference, 1972.
 [6]
 A. GEORGE, "Nested dissection of a regular finite element mesh," SIAM J. Numer. Anal., v. 10, 1973, pp. 345363. MR 0388756 (52:9590)
 [7]
 A. GEORGE, "Numerical experiments using dissection methods to solve grid problems," SIAM J. Numer. Anal., v. 14, 1977, pp. 161179. MR 0440882 (55:13750)
 [8]
 A. GEORGE, "Solution of linear systems of equations: Direct methods for finite element problems," Sparse Matrix Techniques (V. A. Barker, Ed.), Lecture Notes in Math., vol. 572, SpringerVerlag, Berlin and New York, 1977, pp. 52101. MR 0440883 (55:13751)
 [9]
 A. GEORGE & J. W. H. LIU, "An automatic nested dissection algorithm flor irregular finite element problems," SIAM J. Numer. Anal., v. 15, 1978, pp. 10531069. MR 507564 (80a:65085)
 [10]
 A. GEORGE, W. G. POOLE, JR. & R. G. VOIGT, "Incomplete nested dissection for solving grid problems," SIAM J. Numer. Anal., v. 15, 1978, pp. 662673. MR 0474729 (57:14363)
 [11]
 A. HOFFMAN, M. S. MARTIN & D. J. ROSE, "Complexity bounds for regular finite difference and finiteelement grids," SIAM J. Numer. Anal., v. 10, 1973, pp. 364369. MR 0347065 (49:11785)
 [12]
 R. J. LIPTON, D. J. ROSE & R. E. TARJAN, "Generalized nested dissection," SIAM J. Numer. Anal., v. 16, 1979, pp. 346358. MR 526496 (80d:65041)
 [13]
 J. K. REID, "A note on the stability of Gaussian elimination," J. Inst. Math. Appl., v. 8, 1971, pp. 374375. MR 0298861 (45:7910)
 [14]
 O. WIDLUND, "On the use of sparsity of finite element systems of equations by Gaussian eliminationtype 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 (32:1894)
 [16]
 J. H. WILKINSON, "A priori error analysis of algebraic processes," Proc. Internat. Congr. Math. (Moscow, 1966), Izdat. "Mir", Moscow, 1968, pp. 629640. MR 0233532 (38:1853)
Similar Articles
Retrieve articles in Mathematics of Computation
with MSC:
65F05,
65N20
Retrieve articles in all journals
with MSC:
65F05,
65N20
Additional Information
DOI:
http://dx.doi.org/10.1090/S00255718198005835010
PII:
S 00255718(1980)05835010
Article copyright:
© Copyright 1980
American Mathematical Society
