Nested Dissection of a Regular Finite Element Mesh

Let M be a mesh consisting of n² squares called elements, formed by subdividing the unit square (0,1) × (0,1) into n² small squares of side 1 / h, and having a node at each of the (n + 1)² grid points. With M we associate the N × N symmetric positive definite system $Ax = b$, where N = (n + 1)², each xᵢ is associated with a node of M, and Aᵢⱼ ≠ 0 if and only if xᵢ and xⱼ are associated with nodes of the same element. If we solve the equations via the standard symmetric factorization of A, then O(n⁴ ) arithmetic operations are required if the usual row by row (banded) numbering scheme is used, and the storage required is O(n³ ). In this paper we present an unusual numbering of the mesh (unknowns) and show that if we avoid operating on zeros, the LDLT factorization of A can be computed using the same standard algorithm in O(n³ ) arithmetic operations. Furthermore, the storage required is only O(n² log ₂ n). Finally, we prove that all orderings of the mesh must yield an operation count of at least O(n³ ), provided we use the standard factorization algorithm.