Premium
Stability of block LU factorization
Author(s) -
Demmel James W.,
Higham Nicholas J.,
Schreiber Robert S.
Publication year - 1995
Publication title -
numerical linear algebra with applications
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.02
H-Index - 53
eISSN - 1099-1506
pISSN - 1070-5325
DOI - 10.1002/nla.1680020208
Subject(s) - mathematics , lu decomposition , factorization , diagonally dominant matrix , block (permutation group theory) , combinatorics , incomplete lu factorization , row , block matrix , scalar (mathematics) , matrix (chemical analysis) , matrix decomposition , algorithm , pure mathematics , computer science , invertible matrix , geometry , eigenvalues and eigenvectors , physics , materials science , quantum mechanics , database , composite material
Abstract Many of the currently popular ‘block algorithms’ are scalar algorithms in which the operations have been grouped and reordered into matrix operations. One genuine block algorithm in practical use is block LU factorization, and this has recently been shown by Demmel and Higham to be unstable in general. It is shown here that block LU factorization is stable if A is block diagonally dominant by columns. Moreover, for a general matrix the level of instability in block LU factorization can be bounded in terms of the condition number K (A) and the growth factor for Gaussian elimination without pivoting. A consequence is that block LU factorization is stable for a matrix A that is symmetric positive definite or point diagonally dominant by rows or columns as long as A is well‐conditioned.