On the Complexity of Sparse $QR$ and $LU$ Factorization of Finite-Element Matrices

Let A be an $n \times n$ sparse nonsingular matrix derived from a two-dimensional finite-element mesh. If the matrix is symmetric and positive definite, and a nested dissection ordering is used, then the Cholesky factorization of A can be computed using $O(n^{{3 / 2}} )$ arithmetic operations, and the number of nonzeros in the Cholesky factor is $O(n\log n)$. In this article we show that the same complexity bounds can be attained when A is nonsymmetric and indefinite, and either Gaussian elimination with partial pivoting or orthogonal factorization is applied. Numerical experiments for a sequence of irregular mesh problems are provided.