ePubs

The open archive for STFC research publications

Full Record Details

DOI 10.5286/raltr.2010031
Persistent URL http://purl.org/net/epubs/work/54246
Record Status Checked
Record Id 54246
Title A modern analyse phase for sparse tree-based direct methods
Contributors
Abstract The analyse phase of a sparse direct solver for symmetrically structured linear systems of equations is used to determine the sparsity pattern of the matrix factor. This allows the subsequent numerical factorization and solve phases to be executed efficiently. The analyse phase typically involves identifying supernodes, amalgamating supernodes to form relaxed supernodes and computing their variable lists, and determining the assembly tree. Two main approaches have been used. The first, based on the initial work of Duff and Reid in the early 1980s, originates from their development of the multifrontal method. This approach emphasises the identification of supervariables of A and, in later versions, handles pre-specified 2 × 2 block pivots; it has been successfully used in both out-of-core and parallel solvers. The second approach, following the work of Gilbert, Ng and Peyton a decade or so later, adopts a graph theoretic view of assembled matrices, exploiting this to determine column counts for the matrix factor without finding the explicit pattern of the factor. This allows supernodes to be amalgamated before a symbolic factorization is performed, leading to significant savings in the analyse time. The aims of this paper are two-fold: to incorporate supervariables into the Gilbert, Ng and Peyton approach and to describe an adaptation for matrices in elemental form (such as arise in finite-element applications), without explicitly assembling the system matrix. Various implementation details designed to enhance performance are described. Modifications to support block pivots are introduced. Numerical experiments using problems from practical applications are used throughout and demonstrate that it is advantageous, in terms of both memory and time, to work directly with the elemental form.
Organisation CSE , CSE-NAG , STFC
Keywords direct solver , analyse phase , sparse symmetric linear systems , element problems , supervariables , supernodes
Funding Information
Related Research Object(s):
Licence Information:
Language English (EN)
Type Details URI(s) Local file(s) Year
Report RAL Technical Reports RAL-TR-2010-031. 2010. RAL-TR-2010-031.pdf 2010