The Multifrontal Method for Sparse Matrix Solution: Theory and Practice

From MaRDI portal





The main purpose of the paper is to give a uniform presentation of the multifrontal method of \textit{I. S. Duff} and \textit{J. K. Reid} [ACM Trans. Math. Software. 9, 302-325 (1983; Zbl 0515.65022)], one of the significant advances in direct methods for large sparse linear systems solution. The method reorganizes the overall factorization of a sparse matrix into a sequence of partial factorizations of dense smaller matrices. The method has proved to be extremely valuable in many large-scale finite element applications, in the solution of the Navier-Stokes equation, in the solution of separable optimization problems and also in the linear programming. Most formulations of the multifrontal method in the literature rely heavily on the context of the finite element method. The author's exposition is purely from the matrix point of view. The notions of the frontal matrix, update matrix and assembly tree, essential for the method, are all formally defined in terms of the sparse matrix structure. The author's aim is to put the terminologies, notation and algorithm formulation into a standard framework for future references and development. After the presentation -- in the paragraph 2 -- of some basic background on sparse Cholesky factorization, the author introduces the elimination tree structure and defines formally the sequence of frontal and update matrices (paragraph 3). In the next section he considers the way these matrices can be formed. For this purpose, a matrix extend-add operator is defined. Although the author defines frontal and update matrices in terms of elimination tree structure, a more general form of an assembly tree can be used; a new general definition of an assembly tree is also given in the section. In the section 5 some issues related to the storage and manipulation of these frontal and update matrices are considered. An algorithm to generate the best postordering of the tree in minimizing the storage for the stack of full triangular matrices is given here. In the two next sections the supernodal version of the method as well as useful implementation techniques are described and discussed. Finally, in the paragraph 8 the author considers the usage of the multifrontal method in various different computational environments: virtual-memory paging systems, limited core-memory systems and vector and parallel supercomputing machines. No experimental results are presented; rather, references are provided to related papers in the literature.




Cited in
(97)


Describes a project that uses

Uses Software






This page was built for publication: The Multifrontal Method for Sparse Matrix Solution: Theory and Practice

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3990664)