The underlying assumption behind currently available sparse direct solvers, namely that an individual solve in isolation should take minimal time, does not represent an optimal solution in the setting of an adaptive finite element method. There, intermediate results, in the form of a factorization, from the solution of a current refinement can be updated when a local refinement occurs. Two innovations underlie the project: an interface that allows applications to pass information about refinement to the direct solver library and a data structure, the Unassembled HyperMatrix, that allows sparse matrices and their factorization to be stored in an unassembled format that facilitates the updating of the matrix and its factorization. In other words, this research is based on the ideas of inheriting the elimination tree from the refinement history of the domain and storing element matrices unassembled on all levels, assembling them only when necessary for the factorization. Since the resulting solver functions fully in terms of element matrices, dense submatrices are naturally exposed as part of the factorization which will allow high-performance kernels like the level-3 BLAS to be fully exploited. The focus of the research includes the design of an API that optimally integrates the solver into applications, the development of the Unassembled HyperMatrix infrastructure, and an investigation of stability and complexity, in particular the design of pivoting strategies for the indefinite case.
Computational simulation has joined the two traditional methods in science, theory and experiment, as an equal partner. For many applications, ranging from the similation of vibration in an automobile to the computation of the radar signature an airplane on radar, finite element methods are the computational method of choice. The best of these methods use adaptive approximations to balance accuracy against the time required for the solution. Invariably, most time is spent in the solution of a system of linear equations. It is the reduction of this solution time, in the specific setting of an adaptive application, that is the focus of this research. The innovation that is the basis of this project consists in storing the linear system in a new format, the Unassembled HyperMatrix, that allows much of a past computation to be reused when an adaptation occurs. Hand in hand with this theoretical innovation goes the development of an interface that allows an application to express adaptation to the solver library. The new approach has the potential for reducing the cost of a solution related to an adaptation substantially.
