Sparse direct factorizations through unassembled hyper-matrices

We set out to efficiently compute the solution of a sequence of linear systems A_ix_i = b_i, where the matrix A_i is tightly related to matrix A_{i –1}. In the setting of an hp -adaptive Finite Element Method, the sequence of matrices A_i results from successive local refinements of the problem domain. At any step i > 1, a factorization already exists and it is the updated linear system relative to the refined mesh for which a factorization must be computed in the least amount of time. This observation holds the promise of a tremendous reduction in the cost of an individual refinement step. We argue that traditional matrix storage schemes, whether dense or sparse, are a bottleneck, limiting the potential efficiency of the solvers. We propose a new hierarchical data structure, the Unassembled Hyper-Matrix (UHM), which allows the matrix to be stored as a tree of unassembled element matrices, hierarchically ordered to mirror the refinement history of the physical domain. The factorization of such an UHM proceeds in terms of element matrices, only assembling nodes when they need to be eliminated. Efficiency comes in terms of both performance and space requirements. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)