## 6 Numerical Methods and Algorithms
### Models at the Macro-Scale
#### 6.1.2 Solution of the \"Discrete in Space\"
\(S\left(\mathbf{A}_{h},\mathbf{f}^{h},\mathbf{f}^{h}_{0},\mathbf{b}^{h}\right)\) is in general a tool to compute iteratively an approximation for the solution of the linear system \(\mathbf{A}_{h}\mathbf{f}_{h}=\mathbf{b}_{h}\) from the initial guess \(\mathbf{f}^{h}_{0}\). Algorithm 6 describes the recursive implementation schema of AMG methods based on the ingredients listed above, where \(\mathbf{x}^{h}_{0}\) is the initial guess for solution \(\mathbf{x}^{h}\). . Details about restriction, prolongation, and relaxation operators can be found in Stuben [154]. 4. **The Saddle Point Problem solvers** Let us consider the block \(2\times 2\) linear systems of the form \[\left[ \begin{array}{cc}A&B_{1}^{T}\\ B_{2}&-\mathbb{C}\end{array} \right]\left[ \begin{array}{c}x_{1}\\ x_{2}\end{array} \right]=\left[ \begin{array}{c}y_{1}\\ y_{2}\end{array} \right]\] (143) where \(A\in\Re^{n\times n}\), \(B_{1},B_{2}\in\Re^{m\times n}\) and \(\mathbb{C}\in\Re^{m\times m}\). If one or more of the following requirements are met by the constituent blocks \(A\), \(B_{1}\), \(B_{2}\), and \(\mathbb{C}\), then the linear system (143) defines a (generalized) \"_Saddle Point problem\"_[155]: **C1**\(A\) is symmetric (\(A=A^{T}\));  
Figure 10: Illustrations of different V and W cycles. **C2** the symmetric part of \(A\), \(H=\frac{1}{2}\big{(}A+A^{T}\big{)}\), is positive semidefinite;  
**C3**\(B_{1}=B_{2}=B\);  
**C4**\(C\) is symmetric and positive semidefinite;  
**C5**\(C=O\). In addition to the standard differentiation between direct and iterative techniques, generalized Saddle Point problem-solving algorithms can be broadly classified into two groups: _segregated_ and _coupled_ methods [155]. **Segregated methods**\(x_{1}\) and \(x_{2}\), the two unknown vectors, are computed independently via segregated procedures. This method entails solving two linear systems (referred to as reduced systems), one for each of \(x_{i}\), that are less in size than \(n+m\). Each reduced system in segregated techniques can be addressed using an iterative or direct approach. The Schur complement reduction method, which is based on a block LU factorization of the block \(2\times 2\) matrix in Equation (143) (also known as the global matrix \(\mathcal{A}\)), is one of the primary examples of the segregated approach. Indeed, if \(A\) is nonsingular, the Saddle Point matrix admits the following block triangular factorization:  
\[\mathcal{A}=\left[ \begin{array}{cc}A&B_{1}^{T}\\ B_{2}&-C\end{array} \right]=\left[ \begin{array}{cc}I&0\\ B_{2}A^{-1}&I\end{array} \right]\left[ \begin{array}{cc}A&B_{1}^{T}\\ 0&S\end{array} \right], \tag{144}\]  
where \(S=-\big{(}C+B_{2}A^{-1}B_{1}^{T}\big{)}\) is the Schur complement of \(A\) in \(\mathcal{A}\). It follows that if \(\mathcal{A}\) is nonsingular, \(S\) is also nonsingular. Using Equation (144), the linear system (143) can be transformed into  
\[\left[ \begin{array}{cc}I&0\\ -B_{2}A^{-1}&I\end{array} \right]\left[ \begin{array}{cc}A&B_{1}^{T}\\ B_{2}&-C\end{array} \right]\left[ \begin{array}{cc}x_{1}\\ x_{2}\end{array} \right]=\left[ \begin{array}{cc}I&0\\ -B_{2}A^{-1}&I\end{array} \right]\left[ \begin{array}{c}y_{1}\\ y_{2}\end{array} \right], \tag{145}\]  
or equivalently,  
\[\left[ \begin{array}{cc}A&B_{1}^{T}\\ 0&S\end{array} \right]\left[ \begin{array}{c}x_{1}\\ x_{2}\end{array} \right]=\left[ \begin{array}{c}y_{1}\\ y_{2}-B_{2}A^{-1}y_{1}\end{array} \right]. \tag{146}\]  
Then, the solution of the linear system (143) by the segregated method can be performed using Algorithm 7. Solution of linear systems at the lines 4, 6 and 8 of Algorithm 7 can be solved either directly or iteratively. This approach is attractive if the order \(m\) of the reduced system at line 6 of Algorithm 7 is small and if linear systems with coefficient matrix \(A\) can be solved efficiently. Since the solution of two linear systems with coefficient matrix \(A\) is required, it should be convenient to perform just one LU factorization of \(A\) to be used twice.