1973/04/01 by Alan D. George · 5 citations
Computer Science · Mathematics · #Interconnection Networks and Systems #Cellular Automata and Applications #Computational Geometry and Mesh Generation #Mathematics #Factorization #Numbering #Combinatorics #Node (physics) #Discrete mathematics #Algorithm
paper · doi:10.1137/0710032
openalex publication_date 1973/04/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/04
Let M be a mesh consisting of n2 squares called elements, formed by subdividing the unit square (0,1) × (0,1) into n2 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 × N symmetric positive definite system Ax = b, where N = (n + 1)2 , each xi is associated with a node of M, and Aij ≠ 0 if and only if xi and xj are associated with nodes of the same element. If we solve the equations via the standard symmetric factorization of A, then O(n4 ) arithmetic operations are required if the usual row by row (banded) numbering scheme is used, and the storage required is O(n3 ). 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(n3 ) arithmetic operations. Furthermore, the storage required is only O(n2 log 2 n). Finally, we prove that all orderings of the mesh must yield an operation count of at least O(n3 ), provided we use the standard factorization algorithm.