Multi-frontal solver algorithm
The multi-frontal solver algorithm was proposed in 1987 as a modification of the frontal solver algorithm by Iain Duff and John Reid [1]. The idea behind the multi-frontal algorithm is to perform the elimination as in the frontal solver algorithm but over many elements simultaneously.
In other words, in our example in this chapter, we have a matrix that was created by combining three elemental matrices \( \begin{bmatrix} {\frac{1}{20}} & {\frac{13}{120}} & {\frac{1}{120}}\\ {\frac{13}{120}} & {\frac{9}{20}} & {\frac{13}{120}} \\ {\frac{1}{120}} & {\frac{13}{120}} & {\frac{1}{20}} \\ \end{bmatrix} \)
Also in this section, to better illustrate the operation of the algorithm, we will leave the numbers as fractional, of course remembering that they are stored in the computer in the floating-point form.
So we generate all three elemental matrices, and locate (mark in red) the matrix rows that we can eliminate
\( \begin{bmatrix} {\color{red}\frac{1}{20}} & {\color{red}\frac{13}{120}} & {\color{red}\frac{1}{120}}\\ {\frac{13}{120}} & {\frac{9}{20}} & {\frac{13}{120}} & {\frac{13}{120}} & {\frac{1}{20}} \\ \end{bmatrix} \\ \begin{bmatrix} u_{1} \\ u_{2} \\ u_{3} \\ \end{bmatrix} = \begin{bmatrix} {\color{red}1} \\ 1 \\ 1 \end{bmatrix} \)
\( \begin{bmatrix} {\frac{1}{20}} & {\frac{13}{120}} & {\frac{1}{120}} & {\frac{9}{20}} & {\frac{13}{120}} & {\frac{13}{120}} & {\frac{1}{20}} \\ \end{bmatrix} \\ \begin{bmatrix} u_{2} \\ u_{3} \\ u_{4} \\ \end{bmatrix} = \begin{bmatrix} 1 \\ 1 \\ \end{bmatrix} \)
\( \begin{bmatrix} {\frac{1}{20}} & {\frac{13}{120}} & {\frac{1}{120}}\\ {\frac{13}{120}} & {\frac{9}{20}} & {\frac{13}{120}} & {\color{red}\frac{13}{120}} & {\color{red}\frac{1}{20}} \\ \end{bmatrix} \\ \begin{bmatrix} u_{3} \\ u_{4} \\ u_{5} \\ \end{bmatrix} = \begin{bmatrix} 1 \\ 1 \\ {\color{red}1} \end{bmatrix} \)
In our case, when we operate on B-spline functions, we cannot unfortunately eliminate any rows from a single element matrix unless we merge three element matrices, or unless the rows are located at the edge of the area. This means that we can eliminate the first row from the frontal matrix related to the first element
\( 1^{st}=1^{st}/A(1,1)=1^{st}/20=1^{st}*20 \)
\( \begin{bmatrix} \frac{1}{20}{\color{red}*20} & \frac{13}{120}{\color{red}*20} & \frac{1}{120}{\color{red}*20} \\ \frac{13}{120} & \frac{9}{20} & \frac{13}{120} \\ \frac{1}{120} & \frac{13}{120} & \frac{1}{20} \\ \end{bmatrix} \\ \begin{bmatrix} u_{1} \\ u_{2} \\ u_{3} \\ \end{bmatrix} = \begin{bmatrix} 1{\color{red}*20} \\ 1 \\ 1 \\ \end{bmatrix} \)
\( \begin{bmatrix} {\color{red}1} & {\color{red}\frac{13}{6}} & {\color{red}\frac{1}{6}} \\\frac{13}{120} & \frac{9}{20} & \frac{13}{120} \\\frac{1}{120} & \frac{13}{120} & \frac{1}{20} \\ \end{bmatrix} \\ \begin{bmatrix} u_{1} \\ u_{2} \\ u_{3} \\ \end{bmatrix} = \begin{bmatrix} {\color{red}20} \\ 1 \\ 1 \\ \end{bmatrix} \)
\( 2^{nd}=2^{nd}-1^{st}*A(2,1)=2^{nd}-1^{st}\frac{13}{120} \)
\( \begin{bmatrix} {\color{red}1}& {\color{red}\frac{13}{6}} & {\color{red}\frac{1}{6}} \\ \frac{13}{120}{\color{red}-1\frac{13}{120}} & \frac{9}{20}{\color{red}-\frac{13}{6}\frac{13}{120}} & \frac{13}{120}{\color{red}-\frac{1}{6}\frac{13}{120}} \\ \frac{1}{120} & \frac{13}{120} & \frac{1}{20} \\ \end{bmatrix} \\ \begin{bmatrix} u_{1} \\ u_{2} \\ u_{3} \\ \end{bmatrix} = \begin{bmatrix} {\color{red}20} \\ 1{\color{red}-20\frac{13}{120}} \\ 1 \end{bmatrix} \)
\( \begin{bmatrix} 1 & \frac{13}{6} & \frac{1}{6} \\ {\color{red}0} & {\color{red}\frac{31}{144}} & {\color{red}\frac{13}{144}} \\ \frac{1}{120} & \frac{13}{120} & \frac{1}{20} \\ \end{bmatrix} \\ \begin{bmatrix} u_{1} \\ u_{2} \\ u_{3} \\ \end{bmatrix} = \begin{bmatrix} 20 \\ {\color{red}-\frac{7}{6}} \\ 1 \end{bmatrix} \)
\( 3^{rd}=3^{rd}-1^{st}*A(3,1)=3^{rd}-1^{st}/120 \)
\( \begin{bmatrix} 1 & \frac{13}{6} & \frac{1}{6} \\ 0 & \frac{31}{144} & \frac{13}{144} \\ \frac{1}{120}{\color{red}-1\frac{1}{120}} & \frac{13}{120}{\color{red}-\frac{31}{144}\frac{1}{120}} & \frac{1}{20}{\color{red}-\frac{13}{144}\frac{1}{120}} \\ \end{bmatrix} \\ \begin{bmatrix} u_{1} \\ u_{2} \\ u_{3} \\ \end{bmatrix} = \begin{bmatrix} 20 \\ -\frac{7}{6} \\ 1{\color{red}-20\frac{1}{120}} \end{bmatrix} \)
\( \begin{bmatrix} 1 & \frac{13}{6} & \frac{1}{6} \\ 0 & \frac{31}{144} & \frac{13}{144} \\ {\color{red}0} & {\color{red}\frac{1841}{17280}} & {\color{red}\frac{864}{17280}} \\ \end{bmatrix} \\ \begin{bmatrix} u_{1} \\ u_{2} \\ u_{3} \\ \end{bmatrix} = \begin{bmatrix} 20 \\ -\frac{7}{6} \\ {\color{red}\frac{5}{6}} \end{bmatrix} \)
In the matrix related to the second element, it is not possible to eliminate any row because all rows are missing some columns that will be added when we combine this matrix with neighboring matrices.
Similarly, in the matrix related to the last element, we can eliminate the last row. In this matrix, we change the order of the lines so that the line to be eliminated is at the beginning
\( 1^{st}=1^{st}/A(1,1)=1^{st}/20=1^{st}*20 \)
\( \begin{bmatrix} \frac{1}{20}{\color{red}*20} & \frac{13}{120}{\color{red}*20} & \frac{1}{120}{\color{red}*20} \\ \frac{13}{120} & \frac{9}{20} & \frac{13}{120} \\ \frac{1}{120} & \frac{13}{120} & \frac{1}{20} \\ \end{bmatrix} \\ \begin{bmatrix} u_{5} \\ u_{4} \\ u_{3} \\ \end{bmatrix} = \begin{bmatrix} 1{\color{red}*20} \\ 1 \\ 1 \\ \end{bmatrix} \)
\( \begin{bmatrix} {\color{red}1} & {\color{red}\frac{13}{6}} & {\color{red}\frac{1}{6}} \\ \frac{13}{120} & \frac{9}{20} & \frac{13}{120} \\ \frac{1}{120} & \frac{13}{120} & \frac{1}{20} \\ \end{bmatrix} \\ \begin{bmatrix} u_{5} \\ u_{4} \\ u_{3} \\ \end{bmatrix} = \begin{bmatrix} {\color{red}20} \\ 1 \\ 1 \\ \end{bmatrix} \)
\( 2^{nd}=2^{nd}-1^{st}*A(2,1)=2^{nd}-1^{st}\frac{13}{120} \)
\( \begin{bmatrix} {\color{red}1} & {\color{red}\frac{13}{6}} & {\color{red}\frac{1}{6}} \\ \frac{13}{120}{\color{red}-1\frac{13}{120}} & \frac{9}{20}{\color{red}-\frac{13}{6}\frac{13}{120}} & \frac{13}{120}{\color{red}-\frac{1}{6}\frac{13}{120}} \\ \frac{1}{120} & \frac{13}{120} & \frac{1}{20} \\ \end{bmatrix} \\ \begin{bmatrix} u_{5} \\ u_{4} \\ u_{3} \\ \end{bmatrix} = \begin{bmatrix} {\color{red}20} \\ 1{\color{red}-20\frac{13}{120}} \\ 1 \end{bmatrix} \)
\( \begin{bmatrix} 1 & \frac{13}{6} & \frac{1}{6} \\ {\color{red}0} & {\color{red}\frac{31}{144}} & {\color{red}\frac{13}{144}} \\ \frac{1}{120} & \frac{13}{120} & \frac{1}{20} \\ \end{bmatrix} \\ \begin{bmatrix} u_{5} \\ u_{4} \\ u_{3} \\ \end{bmatrix} = \begin{bmatrix} 20 \\ {\color{red}-\frac{7}{6}} \\ 1 \end{bmatrix} \)
\( 3^{rd}=3^{rd}-1^{st}*A(3,1)=3^{rd}-1^{st}/120 \)
\( \begin{bmatrix} 1 & \frac{13}{6} & \frac{1}{6} \\ 0 & \frac{31}{144} & \frac{13}{144} \\ \frac{1}{120}{\color{red}-1\frac{1}{120}} & \frac{13}{120}{\color{red}-\frac{31}{144}\frac{1}{120}} & \frac{1}{20}{\color{red}-\frac{13}{144}\frac{1}{120}} \\ \end{bmatrix} \\ \begin{bmatrix} u_{5} \\ u_{4} \\ u_{3} \\ \end{bmatrix} = \begin{bmatrix} 20 \\ -\frac{7}{6} \\ 1{\color{red}-20\frac{1}{120}} \end{bmatrix} \)
\( \begin{bmatrix} 1 & \frac{13}{6} & \frac{1}{6} \\ 0 & \frac{31}{144} & \frac{13}{144} \\ {\color{red}0} & {\color{red}\frac{1841}{17280}} & {\color{red}\frac{864}{17280}} \\ \end{bmatrix} \\ \begin{bmatrix} u_{5} \\ u_{4} \\ u_{3} \\ \end{bmatrix} = \begin{bmatrix} 20 \\ -\frac{7}{6} \\ {\color{red}\frac{5}{6}} \end{bmatrix} \)
So at this point, we have two sub-matrices resulting from the elimination of one row in the first and third matrices
\( \begin{bmatrix} {\color{red}\frac{31}{144}} & {\color{red}\frac{13}{144}} \\ {\color{red}\frac{1841}{17280}} & {\color{red}\frac{864}{17280}} \\ \end{bmatrix} \\ \begin{bmatrix} u_{2} \\ u_{3} \\ \end{bmatrix} = \begin{bmatrix} {\color{red}-\frac{7}{6}} \\ {\color{red}\frac{5}{6}} \end{bmatrix} \)
\( \begin{bmatrix} {\color{blue}\frac{31}{144}} & {\color{blue}\frac{13}{144}} \\ {\color{blue}\frac{1841}{17280}} & {\color{blue}\frac{864}{17280}} \\ \end{bmatrix} \\ \begin{bmatrix}u_{4} \\ u_{3} \\ \end{bmatrix} = \begin{bmatrix} {\color{blue}-\frac{7}{6}} \\ {\color{blue}\frac{5}{6}} \end{bmatrix} \)
Such subarrays, obtained by eliminating certain rows, are called Schur's complement matrices. Additionally, we obviously have a matrix related to the second element (with variables \( u_{2}, u_{3}, u_{4} \)).
\( \begin{bmatrix} {\frac{1}{20}} & {\frac{13}{120}} & {\frac{1}{120}}\\ {\frac{13}{120}} & {\frac{9}{20}} & {\frac{13}{120}} & {\frac{13}{120}} & {\frac{1}{20}} \\ \end{bmatrix} \\ \begin{bmatrix} u_{2} \\ u_{3} \\ u_{4} \\ \end{bmatrix} = \begin{bmatrix} {\color{blue}1} \\ {\color{blue}1} \\ {\color{blue}1} \end{bmatrix} \)
Missing parts from rows related to the variables \( u_2,u_3 \) are in the first sub-matrix called Schur's Complement, while the missing parts of rows related to the variables \( u_3, u_4 \) are in a sub-matrix called the Schur's Complement associated with the third element.
The multi-frontal solver algorithm will now merge the frontal matrices.