12th July 2004

MA62: Sparse symmetric finite-element system: out-of-core frontal method

To solve one or more sets of sparse symmetric linear unassembled finite-element equations, $$\mathbf{AX} = \mathbf{B}$$, by the frontal method, optionally holding the matrix factor out-of-core in direct-access files. The package is primarily designed for positive-definite matrices since numerical pivoting is not performed. Use is made of high-level BLAS kernels. The coefficient matrix $$\mathbf{A}$$ must of the form

$\mathbf{A} = \sum_ {k=1} ^ m \mathbf{A} ^{(k)}$ with $$\mathbf{A} ^{(k)}$$ nonzero only in those rows and columns that correspond to variables in the $$k$$-th element.

The frontal method is a variant of Gaussian elimination and involves the factorization

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

where $$\mathbf{P}$$ is a permutation matrix, $$\mathbf{D}$$ is a diagonal matrix, and $$\mathbf{L}$$ is a unit lower triangular matrix. The solution process is completed by performing the forward elimination

$(\mathbf{PL})\mathbf{DY}\normalfont = \mathbf{B},$

followed by the back substitution

$(\mathbf{PL}) ^ T \mathbf{X} = \mathbf{Y}.$

MA62 stores the reals of the factors and their indices separately. A principal feature of MA62 is that, by holding the factors out-of-core, large problems can be solved using a predetermined and relatively small amount of in-core memory. At an intermediate stage of the solution, $$l$$ say, the ‘front’ contains those variables associated with one or more of $$\mathbf{A} ^{(k)}$$, $$k = 1, 2,..., l$$, which are also present in one or more of $$\mathbf{A} ^{(k)}$$, $$k = l+1,..., m$$. For efficiency, the user should order the $$\mathbf{A} ^{(k)}$$ so that the number of variables in the front (the ‘front size’) is small. For example, a very rectangular grid should be ordered pagewise parallel to the short side of the rectangle. The elements may be preordered using the HSL routine MC63.