Sparse Direct Factorizations through Unassembled Hyper-Matrices

Overview

We advocate a novel strategy for sparse direct factorizations that is geared towards the matrices that arise from hp adaptive Finite Element Methods. In that context, a sequence of linear systems derived by successive local refinement of the problem domain needs to be solved. Thus, there is an opportunity for a factorization strategy that proceeds by updating (and possibly downdating) the factorization. Our scheme consists of storing the matrix as unassembled element matrices, hierarchically ordered to mirror the refinement history of the domain. The factorization of such an `unassembled hyper-matrix' proceeds in terms of element matrices, only assembling nodes when they need to be eliminated. The main benefits are efficiency from the fact that only updates to the factorization are made, high scalar efficiency since the factorization process uses dense matrices throughout, and a workflow that integrates naturally with the application.

We advocate a novel strategy for sparse direct factorizations that is geared towards the matrices that arise from hp adaptive Finite Element Methods. In that context, a sequence of linear systems derived by successive local refinement of the problem domain needs to be solved. Thus, there is an opportunity for a factorization strategy that proceeds by updating (and possibly downdating) the factorization. Our scheme consists of storing the matrix as unassembled element matrices, hierarchically ordered to mirror the refinement history of the domain. The factorization of such an `unassembled hyper-matrix' proceeds in terms of element matrices, only assembling nodes when they need to be eliminated. The main benefits are efficiency from the fact that only updates to the factorization are made, high scalar efficiency since the factorization process uses dense matrices throughout, and a workflow that integrates naturally with the application.

People

• Victor Eijkhout, Texas Advanced Computing Center
• Paolo Bientinesi, Computer Science Department, RWTH Aachen, Germany
• Robert van de Geijn, Department of Computer Science, and Institute for Computational Engineering and Sciences
• Jason Kurtz, Aerospace Engineering and Engineering Mechanics, The University of Texas at Austin
• Kyungjoo Kim (graduate student), Department of Aerospace Engineering

Downloads

Our software will be released into the public domain.

Publications

Sparse Direct Factorizations through Unassembled Hyper-Matrices
TACC Technical Report TR-07-02

@ARTICLE{Bientinesi:2010uhm,
author = {Paolo Bientinesi and Victor Eijkhout and Kyungjoo Kim and Jason Kurtz and Robert van de Geijn},
title = {Sparse Direct Factorizations through Unassembled Hyper-Matrices},
journal = {Computer Methods in Applied Mechanics and Engineering},
year = {2010},
volume = {199},
pages = {430--438},
doi = {http://dx.doi.org/10.1016/j.cma.2009.07.012}
}