Algorithm

The algorithm used in STRUMPACK is described in detail in [5], and is based on the work by Jianlin Xia [9]. Here we summarize the main algorithm features. HSS Preconditioning has more information on the low-rank compression strategy and how to tune this to get a good preconditioner for your specific problem. There are three main steps in the algorithm: matrix reordering, factorization and solve.

Matrix reordering:

There are three distinct matrix reordering steps: one for stability, one to limit fill- in and one to reduce HSS-ranks. First, the matrix is reordered and possibly scaled for numerical stability by the MC64 code [3] or by a code from Combinatorial BLAS [1]. This step is called the matching phase. For many matrices, this reordering can safely be disabled. By default, MC64 is used to maximize the product of the diagonal values of the matrix, and to scale the rows and columns of the matrix. Alternatively, MC64 can be used to maximize the smallest diagonal value or to maximize the sum of the diagonals. Next, a nested dissection reordering is applied to limit fill-in. Both (Par)Metis and (PT-)Scotch are supported. We expose one user tunable parameter which controls the size of the smallest separators. Finally, when HSS compression is used, there is an extra reordering step to reduce the HSS-ranks. This reordering uses Metis and does not require user tuning.

Factorization:

Before the actual numerical factorization, there is a symbolic factorization step to construct the elimination tree. After that, the multifrontal factorization procedure traverses this elimination tree from bottom (smallest separators) to top (root separator). With each node of the elimination tree a dense matrix is associated, referred to as a frontal matrix, or simply front. These fronts can possibly be compressed as Hierarchically Semi-Separable (HSS) matrices. This compression will only pay off for fronts that are large enough, which are typically the frontal matrices at the nodes in the elimination tree close to the root. Without any HSS compression, the solver acts as a standard multifrontal direct solver. HSS approximations are constructed using a randomized sampling algorithm.

Solve:

Once the matrix is factorized, the factors can be used to efficiently solve a linear system of equations by doing a forward and a backward solve sweeps. When no HSS compression is used, this is a direct solver. The multifrontal solve procedure is then used within an iterative refinement loop, with typically only 1 or very few iterations. However, when the factors are compressed using HSS, a single multifrontal solve is only approximate and the solve is by default used as a preconditioner for GMRES(30). The required number of GMRES iterations will depend strongly on the quality of the HSS approximation.