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.