Nested Dissection of a Regular Finite Element Mesh

TLDR

A regular finite element mesh of \(n^2\) squares yields an \(N\times N\) SPD system whose standard LDL\(^T\) factorization requires \(O(n^4)\) operations and \(O(n^3)\) storage. The study proposes a novel node numbering that, by skipping zero entries, reduces the LDL\(^T\) factorization cost to \(O(n^3)\) operations. The authors employ this mesh numbering to allow the standard LDL\(^T\) algorithm to run without operating on zeros, achieving the reduced complexity. The resulting factorization requires only \(O(n^2\log n)\) storage, and the authors prove that no ordering can achieve fewer than \(O(n^3)\) operations with the standard algorithm.

Abstract

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