Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



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

Authors: Alan George and Khakim D. Ikramov
Journal: Math. Comp. 73 (2004), 653-657
MSC (2000): Primary 65F10
Published electronically: October 17, 2003
MathSciNet review: 2031399
Full-text PDF

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 [Enhancements On Off] (What's this?)

  • 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

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
Published electronically: October 17, 2003
Additional Notes: This work was supported by Natural Sciences and Engineering Research Council of Canada grant OGP0008111
Article copyright: © Copyright 2003 American Mathematical Society

American Mathematical Society