## 6 Numerical Methods and Algorithms
### Models at the Macro-Scale
#### 6.1.2 Solution of the \"Discrete in Space\"
Numerical issues related to the stability and accuracy of the presented direct solver can be found in [146]. With the aim to present and discuss methods useful in computing the \(LU\) decomposition of sparse matrices, we propose the \"_Frontal_ methods\". Such methods have their origin in the solution of finite-element problems, but they are not restricted to this application. They are of great interest in their own right since the extension of these ideas to multiple fronts, regardless of the origin of the problem, will offer a great opportunity for parallelism [146; 148; 149]. In the context of \"_Frontal methods_\" the matrix \(\mathbf{A}\) can be considered as the sum of submatrices of varying sizes, as happens for the matrices that are the result of the assembly process underlying the discretization using finite elements. That is, each entry is computed as the sum of one or more values:  
\[\mathbf{A}_{ij}=\sum_{l=1,\ldots,L}\mathbf{A}_{ij}^{[l]},\ \forall i,j=1,\ldots,M. \tag{127}\]  
Entry \(\mathbf{A}_{ij}\) in (127) is said to be fully summed (or fully assembled) if all the operations (127) have been performed, and the index of the unknown \(k\) is said to be fully summed if all the \(\mathbf{A}\) entries in its row (i.e., \(\mathbf{A}_{kj},\ \forall j=1,\ldots,M\)) and its column (i.e., \(\mathbf{A}_{ik},\ \forall i=1,\ldots,M\)) are fully summed. The fundamental notion of frontal techniques is to limit decomposition operations to a frontal matrix \(\mathbf{F}\), on which Level 3 BLAS [150] is used to execute dense matrix operations. (The BLAS (Basic Linear Algebra Subprograms) are routines that provide optimized standard building blocks for performing primary vector and matrix operations. BLAS routines can be classified depending on the type of operands: Level 1: operations involving just vector operands; Level 2: operations between vectors and matrices; and Level 3: operations involving just matrix operands.) In the frontal scheme, the factorization proceeds as a sequence of partial factorization on frontal matrices \(\mathbf{F}^{[l]}\), which can be represented, up to some row or column permutations, by a \(2\times 2\) blocks structure:  
\[\mathbf{F}^{[l]}=\left[ \begin{array}{cc}\mathbf{F}^{[l]}_{11}&\mathbf{F}^{[l]}_{12}\\ \mathbf{F}^{[l]}_{21}&\mathbf{F}^{[l]}_{22}\end{array} \right]. \tag{128}\]  
where \(\mathbf{F}^{[l]}_{11}\) is related to the unknown indices that are fully summed. The \(LU\) decomposition by Frontal methods can be described by Algorithm 4. A variation of frontal solvers is the _Multifrontal method_. It could be considered an improvement of the frontal solver, which, based on an appropriate order or coupling of the addends in the summation in (127), can lead to the use of several independent fronts paving the way, naturally, to the development of parallel algorithms. Efficient parallel and sequential decomposition algorithms based on Frontal and Multifrotal methods should be able to perform an analysis of the structure of matrix \(A\) to define all the needed reorganizations of its row and columns (i.e., by the definition of appropriate permutations) to better exploit sparsity, preserve \"good\" numerical properties, and define the order of front assembly. See [146] for details about techniques to be used in such analyses.