Available in electronic format
Available in print format		 Mathematics of Computation
Journal of the American Mathematical Society
ISSN 1088-6842(e) ISSN 0025-5718(p)
Previous issue | Table of contents | Next issue
Articles in press | Recently posted articles | Most recent issue | All issues
Previous Article | Next Article
     

Gaussian elimination is stable for the inverse of a diagonally dominant matrix

Author(s): Alan George; Khakim D. Ikramov.
Journal: Math. Comp. 73 (2004), 653-657.
MSC (2000): Primary 65F10
Posted: October 17, 2003
Retrieve article in: PDF DVI PostScript

Abstract | References | Similar articles | Additional information

Abstract: Let $B\in M_n({\mathbf{C}})$ be a row diagonally dominant matrix, i.e.,

\begin{displaymath}\sigma_i \vert b_{ii}\vert = \sum_{\substack{j=1 j\ne i }}^n \vert b_{ij}\vert, \quad i = 1,\ldots,n, \end{displaymath}

where $0 \le \sigma_i < 1, i= 1,\ldots,n,$ with $ \sigma = \max_{1\le i \le n} \sigma_i.$We show that no pivoting is necessary when Gaussian elimination is applied to $A = B^{-1}.$ Moreover, the growth factor for $A$ does not exceed $1 + \sigma.$ The same results are true with row diagonal dominance being replaced by column diagonal dominance.

References:

1.
N.J. Higham, Factorizing complex symmetric matrices with positive definite real and imaginary parts, Math. Comp. 67 (1998), 1591-1599. MR 99a:65049

2.
F.R. Gantmacher, The Theory of Matrices, Chelsea, New York, 1959. MR 21:6372c

3.
A.M. Ostrowski, Note on bounds for determinants with dominant principal diagonal, Proc. Amer. Math. Soc. 3 (1952), 26-30. MR 14:611c

4.
R.A. Horn and C.R. Johnson, Matrix Analysis, Cambridge University Press, 1985. MR 87e:15001

5.
M. Neumann and R.J. Plemmons, Backward error analysis for linear systems associated with inverses of $H$-matrices, BIT 24 (1984), 102-112. MR 85f:65027

6.
R.A. Willoughby, The inverse $M$-matrix problem, Linear Algebra Appl. 18 (1977), 75-94. MR 57:12561

7.
R. Andersen and R. Bloomfield, A time series approach to numerical differentiation, Technometrics 16 (1974), 69-75. MR 53:1889

8.
H.S. Leff, Correlation inequalities for coupled oscillators, J. Math. Phys. 12 (1971), 569-578. MR 43:8322

9.
N.J. Higham, Accuracy and Stability of Numerical Algorithms, SIAM, Philadelphia, 1996. MR 97a:65047

Similar Articles:

Retrieve articles in Mathematics of Computation with MSC (2000): 65F10

Retrieve articles in all Journals with MSC (2000): 65F10

Additional Information:

Alan George
Affiliation: School of Computer Science, University of Waterloo, Waterloo, Ontario, Canada

Khakim D. Ikramov
Affiliation: Faculty of Computational Mathematics and Cybernetics, Moscow State University, 119992 Moscow, Russia
Email: ikramov@cs.msu.su

DOI: 10.1090/S0025-5718-03-01591-6
PII: S 0025-5718(03)01591-6
Keywords: Gaussian elimination, growth factor, diagonally dominant matrices, Schur complement
Received by editor(s): February 13, 2002
Received by editor(s) in revised form: August 1, 2002
Posted: October 17, 2003
Additional Notes: This work was supported by Natural Sciences and Engineering Research Council of Canada grant OGP0008111
Copyright of article: Copyright 2003, American Mathematical Society

  AMS Website Logo Small Comments: webmaster@ams.org
© Copyright 2008, American Mathematical Society
Privacy Statement 		Search the AMSPowered by Google