BRUHAT DECOMPOSITION AND NUMERICAL STABILITY

For a real nonsingular n-by-n matrix A, there exists a decomposition A = V Pi U, where Pi is a permutation matrix and V,U are upper triangul ar matrices. When Pi (T) V Pi is lower triangular and U is normalized, such a decomposition is called the left Bruhat decomposition of A. An algorithm for computing the left Bruhat decomposition is given. For c lasses of matrices introduced by Wilkinson and recently (from a practi cal application) by Foster that have an exponential growth factor when Gaussian elimination with partial pivoting (GEPP) is applied, left Br uhat decomposition has at most linear growth. A partial pivoting strat egy for Bruhat decomposition is also developed, and an explicit equiva lence between GEPP and Bruhat decomposition with partial pivoting (BDP P) is derived. This equivalence implies that the growth factor for GEP P on A equals the growth factor for BDPP on rho A(T), where rho is the permutation matrix that reverses the rows of A(T). BDPP is shown to g ive a growth factor of at most 2 when applied to any matrix for which GEPP gives the maximal growth factor of 2 (n-1).