A Note on the LDL T Decomposition of Matrices from Saddle-Point Problems
Miroslav Tůma · SIAM Journal on Matrix Analysis and Applications · 2002
Sparse linear systems Kx=b are considered, where K is a specially structured symmetric indefinite matrix. These systems arise frequently, e.g., from mixed finite element discretizations of PDE problems. The LDL T factorization of K with diagonal D and unit lower triangular L is known to exist for natural ordering of K, but the resulting triangular factors can be rather dense. On the other hand, for a given permutation matrix P, the LDL T factorization of P TKP may not exist. In this paper a new way to obtain a fill-in minimizing permutation based on initial fill-in minimizing ordering is introduced. For an important subclass of matrices arising from mixed and hybrid finite element discretizations, the existence of the LDL T factorization of the permuted matrix is proved. Experimental results on practical problems indicate that the amount of computational savings can be substantial when compared with the approach based on Schur complement.