1. Introduction#

This note describes the computer implementation of the multifrontal solver in C*ode_aster*. It is intended for code developers and is not a « self-supporting » document.

This method was developed as a prototype within the ISA group in 1993 [RO93], and then introduced in*Code_Aster* in 1994, in a form adapted to this code:

  • Factorization of a matrix not necessarily in central memory (« out of core »), based on the JEVEUX software package.

  • Treatment of boundary conditions with Lagrange multipliers.

  • It was also assumed that there was no need to activate a pivot search.

Initially, only a sequential version for a symmetric real matrix was implemented in*Code_Aster*.

Subsequently, non-symmetric and complex versions were introduced.

Full parallelism was developed in the prototype [RO95], it was not retained for the version developed in Code_aster. The reasons for this are as follows:

  • The priority objective at the time was to optimize memory occupancy in order to deal with large linear systems. However, parallelism requires more memory than sequential.

  • The parallelism of the multi-front end requires parallel memory management specific to this method, which should have coexisted with the JEVEUX software package, which is intrinsically sequential.

  • Parallelism was also not a priority at a time when only weakly parallel computers were available.

A theoretical basis for the method can be found in [DU86], [AS87], [], [], [RO93] & [RO95], as well as in the Code_Aster reference documentation: « Linear solver using the Multi-Frontale method », [R6.02.02].

The double-precision version REAL *8 (resp. COMPLEX*16) is performed by calling the FORTRAN mulfr8 routine (resp. mlfc16).

Subsequently, the version for a symmetric matrix of real variable will be described in detail, and paragraphs will be devoted to the non-symmetric and complex versions. For more details on C*ode_aster* data structures, refer to the documentation [D4.06.07] (sd_ nume_ddl) and [D4.06.10] (sd_matr_asse).

1.1. General principles.#

We want to replace the factorization of a sparse matrix by a series of factorization of full matrices. It’s the Cartesian principle: replace a difficult problem with a set of simple problems.

To do this, we first have an algorithm for renumbering system variables. This algorithm (of minimum degree, for example), makes it possible to minimize the order of the full matrices to be factored; it is the first axis of efficiency of the method.

In addition, from this renumbering, the following two products can be extracted:

  • An elimination tree, obtained from the « sparsity » of the initial matrix and the optimum filling resulting from the renumbering. This graph (in the form of a tree) provides the order in which variables are eliminated and induces parallelism. (Indeed a « child » node must be eliminated before a « father » node, but all the « children » of the same « father » can be eliminated independently, i.e. in parallel.) This parallelism is the second axis of efficiency of the method.

*The concept of a supernode. This concept was originally designed to minimize the (not negligible) cost of renumbering. To simplify, we call a supernode, a set of nodes (in the sense of graph theory), having the same neighbors. The tree mentioned above is in fact formed of supernodes whose size increases when one goes up in the tree, this increase is an illustration of the filling due to the Gauss elimination method. This grouping has the following advantage: we eliminate the variables by group, and not one by one, thus allowing the use of efficient block methods (using BLAS at level 2 or 3, matrix*vector or matrix*matrix products). This block work is the third axis of efficiency.

In summary, the 3 main lines of strength of the method are:

  • A renumbering,

  • An elimination tree,

  • A grouping of variables.

Numerical factorization then takes place as follows:

We go through the elimination tree, at each stage (elimination of the supernode), we have a full matrix associated with the supernode and its neighbors, we perform the Gauss elimination limited to the variables of the supernode. We thus obtain on the one hand the columns of the final factorized (variables of the supernode), and a frontal matrix modified and reduced to the neighbors (« Schur complement »), which will be assembled in the frontal matrix of the variables of the « father » supernode.

1.2. Programming the method.#

In general, the programming of the multi-frontal method is divided into 2 phases:

  • a so-called « symbolic » factorization phase, including renumbering,

  • a numerical factorization phase proper.

In Code_Aster, the renumbering and the first phase are carried out by the call to subroutine MLTPRE (called via MLFC16 and MULFR8, in the « hat » routines TLDLG2 and TLDLG3).

The second phase is carried out via the call to these routines MLFC16 and MULFR8, in complex or real cases.