## 3 Block Iteration with Parallelization
### Block Iteration  
#### 3.1.1 The Iterative Feasibility of Constructing \(\Phi_{c,c}\)  
To find the time reduction methods, we initially dissect the construction process of \(\Phi_{c,c}\). In terms of Equation (3), matrix \(\Phi_{c,c}\) could be unfolded as follows:  
\[\Phi_{c,c}=\left[ \begin{array}{cccc}\phi(\|\mathbf{x}_{c_{1}}-\mathbf{x}_{c _{1}}\|)&\phi(\|\mathbf{x}_{c_{1}}-\mathbf{x}_{c_{2}}\|)&\phi(\|\mathbf{x}_{c _{1}}-\mathbf{x}_{c_{3}}\|)&\cdots&\phi(\|\mathbf{x}_{c_{1}}-\mathbf{x}_{c_{N _{c}}}\|)\\ \phi(\|\mathbf{x}_{c_{2}}-\mathbf{x}_{c_{1}}\|)&\phi(\|\mathbf{x}_{c_{2}}- \mathbf{x}_{c_{2}}\|)&\phi(\|\mathbf{x}_{c_{2}}-\mathbf{x}_{c_{3}}\|)&\cdots& \phi(\|\mathbf{x}_{c_{2}}-\mathbf{x}_{c_{N_{c}}}\|)\\ \phi(\|\mathbf{x}_{c_{3}}-\mathbf{x}_{c_{1}}\|)&\phi(\|\mathbf{x}_{c_{3}}- \mathbf{x}_{c_{2}}\|)&\phi(\|\mathbf{x}_{c_{3}}-\mathbf{x}_{c_{3}}\|)&\cdots& \phi(\|\mathbf{x}_{c_{3}}-\mathbf{x}_{c_{N_{c}}}\|)\\ \vdots&\vdots&\vdots&\ddots&\vdots\\ \phi(\|\mathbf{x}_{c_{N_{c}}}-\mathbf{x}_{c_{1}}\|)&\phi(\|\mathbf{x}_{c_{N_{ c}}}-\mathbf{x}_{c_{2}}\|)&\phi(\|\mathbf{x}_{c_{N_{c}}}-\mathbf{x}_{c_{3}}\|)&\cdots& \phi(\|\mathbf{x}_{c_{N_{c}}}-\mathbf{x}_{c_{N_{c}}}\|)\\ \end{array} \right]. \tag{13}\]  
According to the characteristics of Euclidean norm, \(\phi(\|\mathbf{x}_{ci}-\mathbf{x}_{c_{j}}\|)=\phi(\|\mathbf{x}_{c_{j}}- \mathbf{x}_{c_{i}}\|)\). Thus, we could get:  
\[\Phi_{c,c}=\left[ \begin{array}{cccc}\phi(0)&\phi_{1,2}&\phi_{1,3}&\cdots& \phi_{1,N_{c}}\\ \phi_{1,2}&\phi(0)&\phi_{2,3}&\cdots&\phi_{2,N_{c}}\\ \phi_{1,3}&\phi_{2,3}&\phi(0)&\cdots&\phi_{3,N_{c}}\\ \vdots&\vdots&\vdots&\ddots&\vdots\\ \phi_{1,N_{c}}&\phi_{2,N_{c}}&\phi_{3,N_{c}}&\cdots&\phi(0)\\ \end{array} \right]. \tag{14}\]  
Equation (14) presents that \(\Phi_{c,c}\) is a real symmetric matrix and its diagonal elements are all equal. From the beginning to the end of greedy selection, each loop step puts one point into the set of control points without any decrease. Therefore, we could establish links between \((i-1)_{th}\) and \(i_{th}\) loop:  
\[\Phi_{i}=\left[ \begin{array}{cc}\Phi_{i-1}&\mathbf{r}\\ \mathbf{r}^{T}&\phi(0)\\ \end{array} \right], \tag{15}\]  
where \(\mathbf{r}=[\phi_{1,i}\ \phi_{2,i}\ \phi_{3,i}\cdots\phi_{i-1,i}]^{T}\). Apparently, it establishes a relationship between \(\Phi_{i-1}\) and \(\Phi_{i}\). In other words, the construction procedure of \(\Phi_{c,c}\) in greedy selection possesses the fundamental precondition of iteration. For each loop, in the process of constructing \(\Phi_{i}\), the values needed to be calculated are vector \(\mathbf{r}\) and \(\phi(0)\), instead of constructing an \(i\times i\) matrix as it is presented in Algorithm 1. In this process, the original computational complexity could be calculated by the following equation:  
\[1^{2}+2^{2}+3^{2}+4^{2}+\cdots+N_{c}^{2}=\frac{N_{c}(N_{c}+1)(2\times N_{c}+ 1)}{6}=O(N_{c}^{3}). \tag{16}\]  
The after-optimized computational complexity could be calculated by the following equation:  
\[1+(2\times 2-1)+(3\times 2-1)+(4\times 2-1)+\cdots+(N_{c}\times 2-1)=N_{c}^{2}=O(N _{c}^{2}). \tag{17}\]  
Therefore, for constructing \(\Phi_{c,c}\), the computing complexity could be reduced from \(O(n^{3})\) to \(O(n^{2})\) by block iteration.