27th March 2023

# HSL_MA77: Sparse symmetric system: multifrontal out of core

HSL_MA77 solves one or more sets of sparse symmetric equations $$\mathbf{AX} = \mathbf{B}$$ using an out-of-core multifrontal method. The symmetric matrix $$\mathbf{A}$$ may be either positive definite or indefinite. It may be input by the user in either of the following ways:

(i) by square symmetric elements, such as in a finite-element calculation, or

(ii) by rows.

In both cases, the coefficient matrix is of order $$n$$ and is of the form

$\mathbf{A} = \sum_ {k=1} ^ m \mathbf{A} ^{(k)}.$ In (i), the summation is over elements and $$\mathbf{A} ^{(k)}$$ is nonzero only in those rows and columns that correspond to variables in the $$k$$th element. In (ii), the summation is over rows and $$\mathbf{A} ^{(k)}$$ is nonzero only in row $$k$$. In both cases, for each $$k$$, the user must supply a list specifying which columns of $$\mathbf{A}$$ are associated with $$\mathbf{A} ^{(k)}$$, and an array containing $$\mathbf{A} ^{(k)}$$ in packed form.

The multifrontal method is a variant of sparse Gaussian elimination. In the positive-definite case, it involves the Cholesky factorization

$\mathbf{A} = (\mathbf{PL})(\mathbf{PL}) ^T$

where $$\mathbf{P}$$ is a permutation matrix and $$\mathbf{L}$$ is lower triangular. In the indefinite case, it involves the factorization

$\mathbf{A} = (\mathbf{PL})\mathbf{D}(\mathbf{PL}) ^T$

where $$\mathbf{P}$$ is a permutation matrix, $$\mathbf{L}$$ is unit lower triangular, and $$\mathbf{D}$$ is block diagonal with blocks of size $$1 \times 1$$ and $$2 \times 2$$. The factorization is performed by the subroutine MA77_factor and is controlled by an elimination tree that is constructed by the subroutine MA77_analyse, which needs the lists of variables in elements or rows and an elimination sequence. Once a matrix has been factorized, any number of calls to the subroutine MA77_solve may be made for different right-hand sides $$\mathbf{B}$$. An option exists for computing the residuals. For large problems, the matrix data and the computed factors are held in direct-access files.

The efficiency of HSL_MA77 is dependent on the elimination order that the user supplies. The HSL routine HSL_MC68 may be used to obtain a suitable ordering.