## 3 Block Iteration with Parallelization
### Block Iteration
#### 3.1.2 The Iterative Feasibility of Inversion  
The inversion of \(\Phi_{c,c}\) occupies almost half of the time cost. Optimizing the inverse process is one of the essential parts of the work in this paper. In Section 3.1.1, we separate \(\Phi_{i}\) into a \(2\times 2\) block matrix. According to the research done by [PERSON] et al. [25], we could obtain several effective methods to inverse a \(2\times 2\) block matrix. Considering that \(\Phi_{i}\) is a real symmetric matrix, we inverse it as the following:  
\[\Phi_{i}^{-1}=Q_{i}=\left[\begin{array}{cc}M_{i-1}&\eta\\ \eta^{T}&p\end{array}\right], \tag{18}\]where \(Q_{i}\) is an \(i\times i\) matrix, \(M_{i-1}\) is an \((i-1)\times(i-1)\) matrix, \(\eta\) is an \((i-1)\) dimensional vector and \(p\) is a real number. In addition, we formulate the equation:  
\[\Phi_{i}Q_{i}=\left[\begin{array}{cc}\Phi_{i-1}&\mathbf{r}\\ \mathbf{r}^{T}&\phi(0)\end{array}\right]\left[\begin{array}{cc}M_{i-1}& \eta\\ \eta^{T}&p\end{array}\right]=E_{i}, \tag{19}\]  
where \(E_{i}\) is an \(i\times i\) identity matrix. Thus, we could obtain the equation set:  
\[\left\{\begin{array}{l}\Phi_{i-1}M_{i-1}+\mathbf{r}\eta^{T}=E_{i-1},\\ \Phi_{i-1}\eta+\mathbf{r}p=\mathbf{0},\\ \mathbf{r}^{T}M_{i-1}+\phi(0)\eta^{T}=\mathbf{0}^{T},\\ \mathbf{r}^{T}\eta+\phi(0)p=1,\end{array}\right. \tag{20}\]  
where \(E_{i-1}\) is an \((i-1)\times(i-1)\) identity matrix, and \(\mathbf{0}\) is \(i\) dimensional zero vector. The solution is:  
\[\left\{\begin{array}{l}p=\dfrac{1}{\phi(0)-\mathbf{r}^{T}\[PERSON]_{i-1}^{-1} \mathbf{r}},\\ \eta=-\dfrac{\[PERSON]_{i-1}^{-1}\mathbf{r}}{\phi(0)-\mathbf{r}^{T}\[PERSON]_{i-1}^{-1} \mathbf{r}},\\ M_{i-1}=\dfrac{\[PERSON]_{i-1}^{-1}\mathbf{r}(\[PERSON]_{i-1}^{-1}\mathbf{r})^{T}}{\phi( 0)-\mathbf{r}^{T},\[PERSON]_{i-1}^{-1}\mathbf{r}}+\[PERSON]_{i-1}^{-1}-\[PERSON]_{i-1}^{-1} \eta^{T}.\end{array}\right. \tag{21}\]  
In addition, we assume the equation set:  
\[\left\{\begin{array}{l}\beta=-\Phi_{i-1}^{-1}\mathbf{r},\\ b=\dfrac{1}{\phi(0)-\mathbf{r}^{T}\[PERSON]_{i-1}^{-1}\mathbf{r}},\end{array}\right. \tag{22}\]  
where \(\beta\) is an \((i-1)\) dimensional vector and \(b\) is a real number. Combining Equations (21) and (22), we obtain the solution:  
\[\Phi_{i}^{-1}=\left[\begin{array}{cc}\Phi_{i-1}^{-1}+b\beta\beta^{T}&b\beta \\ b\beta^{T}&b\end{array}\right]. \tag{23}\]  
Equation (23) establishes links between \(Ph_{i}^{-1}\) and \(\Phi_{i-1}^{-1}\). Therefore, the process of inversion has the ability of iteration. For each loop, in this process, the values needed to be calculated are \(\beta\), \(b\) and \(\Phi_{i-1}^{-1}+b\beta\beta^{T}\) rather than the inversion process of the whole \(i\times i\) matrix as it presented in Algorithm 1. In general, inversion adopts the method of Gauss elimination or LU factorization to inverse matrix. The computing complexity of Gauss elimination or LU factorization is approximately \(O(n^{3})\)[26]. For the block iteration method, the computing complexity decreases to \(O(n^{2})\)[19].  
In addition, the initial matrix of some RBFs such as TPS is \(\Phi_{0}=[\phi(0)]=[0]\), and their inverse matrices never exist. Therefore, for these kinds of RBF, at the beginning of the loop, we should inverse the initial \(2\times 2\) matrix by the classical methods such as LU factorization.