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² ₂ 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.