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

Let A be an n × 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(nlog 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.