## 2 Sparse Direct Algorithms
### The Analyse Phase  
The aim of the analyse phase of our sparse symmetric direct solvers is to determine the pattern of the sparse Cholesky factor \(L\) such that  
\[PAP^{T}=LL^{T}\]  
where the permutation matrix \(P\) holds the elimination (pivot) order. The performance of most algorithms used in the analyse phase can be enhanced by identifying sets of columns with the same (or similar) sparsity patterns. The set of variables that correspond to such a set of columns in \(A\) is called a supervariable_. In problems arising from finite-element applications, supervariables occur frequently as a result of each node of the finite-element mesh having multiple degrees of freedom associated with it.  
After (optionally) determining supervariables, the analyse phase proceeds by building an _elimination tree_. This is a graph that describes the structure of the Cholesky factor in terms of data dependence between pivotal columns. This permits permutations of the elimination order that do not affect the number of entries in \(L\) to be identified and allows fast algorithms to be used in determining the exact structure of \(L\). An extensive theoretical survey and treatment of elimination trees and associated structures in sparse matrix factorizations is given in [21].  
A _supernode_ is a set of contiguous columns of \(L\) with the same sparsity structure below a dense (or nearly dense) triangular submatrix. This trapezoidal matrix has zero rows corresponding to variables that are eliminated later in the pivot sequence at supernodes that are not ancestors in the elimination tree. This matrix can be compressed by holding only the nonzero rows, each with an index held in an integer. The resulting dense trapezoidal matrix is referred to as the _nodal matrix_. The condensed version of the elimination tree consisting of supernodes is referred to as the _assembly tree_. Supernodes are important as they can be exploited in the factorization phase to facilitate the use of efficient dense linear algebra kernels and, in particular, Level-3 Basic Linear Algebra Subroutines (BLAS kernels) [22]. These can offer such a large performance increase that it is often advantageous to amalgamate supernodes that have similar (but not exactly the same) nonzero patterns, despite this increasing the fill in \(L\) and the operation count [23]. Within the HSL solvers, node amalgamation is controlled by a user-defined parameter (which has a default setting chosen on the basis of extensive experimentation).  
Determining supervariables, constructing an assembly tree, amalgamating supernodes and finding row lists (that is, lists of the variables that belong to each supernode) are common tasks that are performed by most modern sparse direct solvers. For efficiency in terms of both development and software maintenance, all the new HSL solvers, with the exception of HSLMA77, use the same code to perform these tasks [24]. This common code is not suitable for use in HSLMA77, since it requires that the matrix \(A\) is held in main memory: HSLMA77 is designed for very large systems and allows \(A\) to be held in files on disk (see Section 4.2). Thus, separate analyse routines were developed for HSLMA77 that read the entries of \(A\) as they are required into main memory.