# A Parallel Two-Stage Iteration Method for Solving Continuous Sylvester Equations
## 3 Parallel Implementation of the Two-Stage Iteration Method
### Parallel Implementation of Inner Iteration Scheme  
(1) Compute process:  
1 Processor \(p_{i}(i=1,2,\cdots,p)\) computes  
\[R_{i}^{(0)}=F_{i}-(A_{i}X^{(0)}+X_{i}^{(i)}B)\text{ and }[R_{i}^{(0)},R_{i}^{(0)}],\]  
obtain \([R_{i}^{(0)},R_{i}^{(0)}]\) after all-reduce, then compute  
\[Q_{i}^{(1)}=R_{i}^{(0)}/\|R^{(0)}\|.\]  
2 Compute  
\[G_{i}^{(1)}=A_{i}Q^{(1)}+Q_{i}^{(1)}B\text{ and }[G_{i}^{(1)},Q_{i}^{(1)}],\]  
obtain \(a_{1}=[G_{i}^{(1)},Q_{i}^{(1)}]\) after all-reduce. Compute  
\[H_{i}^{(1)}=G_{i}^{(1)}-a_{1}Q_{i}^{(1)}\text{ and }[H_{i}^{(1)},H_{i}^{(1)}],\]  
get \([H^{(1)},H^{(1)}]\) after all-reduce and \(b_{1}=\sqrt{[H^{(1)},H^{(1)}}\), then compute \(\widetilde{r}_{1}\),\(\widetilde{\xi}_{1}\),\(\widetilde{W}_{i}^{(1)}\) and \(X_{i}^{(1)}=X_{i}^{(0)}+\widetilde{\xi}_{1}\widetilde{W}_{i}^{(1)}\) in each processor.  
3 Processor \(p_{i}(i=1,2,\cdots,p)\) computes  
\[Q_{i}^{(2)}=H_{i}^{(1)}/b_{1}\text{ and }G_{i}^{(2)}=A_{i}Q^{(2)}+Q_{i}^{(2)}B,\]  
and computes the inner product \([G_{i}^{(2)},Q_{i}^{(2)}]\), get \(a_{2}=[G^{(2)},Q^{(2)}]\) after all-reduce. Compute  
\[H_{i}^{(2)}=G_{i}^{(2)}-a_{2}Q_{i}^{(2)}-b_{1}Q_{i}^{(1)}\text{ and }[H_{i}^{(2)},H_{i}^{(2)}],\]  
get \([H^{(2)},H^{(2)}]\) after all-reduce, compute \(b_{2}=\sqrt{[H^{(2)},H^{(2)}]}\).  
4 Processor \(p_{i}(i=1,2,\cdots,p)\) computes  
\[c_{1}=\frac{a_{1}}{(a_{1}^{2}+b_{2}^{2})^{\frac{1}{2}}},\ s_{1}= \frac{b_{1}}{(a_{1}^{2}+b_{2}^{2})^{\frac{1}{2}}},\ \delta_{2}=b_{1}c_{1}+a_{2}s_{1},\ \varepsilon_{3}=b_{2}s_{1},\] \[r_{1}=(a_{1}^{2}+b_{1}^{2})^{\frac{1}{2}},\ \xi_{1}=\|r_{0}\|/r_{1},\ \widetilde{r}_{2}=b_{1}s_{1}-a_{2}c_{1},\ r_{2}=( \widetilde{r}_{2}^{2}+b_{2}^{2})^{\frac{1}{2}},\ \widetilde{\delta}_{3}=-b_{2}c_{1},\]  
if \(\widetilde{r}_{2}<10^{-15}\) stop, otherwise compute \(\widetilde{\xi}_{2}=-\delta_{2}\xi_{1}/\widetilde{r}_{2}\).  
5 Processor \(p_{i}(i=1,2,\cdots,p)\) computes  
\[\xi_{2}=-\frac{\delta_{2}\xi_{1}}{r_{2}},\ W_{i}^{(1)}=c_{1} \widetilde{W}_{i}^{(1)}+s_{1}Q_{i}^{(2)},\ \widetilde{W}_{i}^{(2)}=s_{1}\widetilde{W}_{i}^{(1)}-c_{1}Q_{i}^{(2)},\] \[Y_{i}^{(1)}=X_{i}^{(0)}+\xi_{1}W_{i}^{(1)},X_{i}^{(2)}=Y_{i}^{(1) }+\widetilde{\xi}_{2}\widetilde{W}_{i}^{(2)}.\](2) Cycle process:  
Step 1. Processor \(p_{i}(i=1,2,\cdots,p)\) computes  
\[\|R^{(k-1)}\|=|b_{k-1}(s_{k-2}\xi_{k-2}-c_{k-2}\widetilde{\xi}_{k-1})|,\]  
if \(\|R^{(k-1)}\|<\varepsilon\) stop, otherwise, turn to Step 2.  
Step 2. Processor \(p_{i}(i=1,2,\cdots,p)\) computes  
\[Q_{i}^{(k)}=H_{i}^{(k-1)}/b_{k-1}\text{ and }G_{i}^{(k)}=A_{i}Q^{(k)}+Q_{i}^{(k)}B,\]  
then compute \([G_{i}^{(k)},Q_{i}^{(k)}]\), obtain \(a_{k}=[G^{(k)},Q^{(k)}]\), after all-reduce. Compute  
\[H_{i}^{(k)}=G_{i}^{(k)}-a_{k}Q_{i}^{(k)}-b_{k-1}Q_{i}^{(k-1)}\text{ and }[H_{i}^{(k)},H_{i}^{(k)}],\]  
Obtain \([H^{(k)},H^{(k)}]\) after all-reduce, compute \(b_{k}=\sqrt{[H^{(k)},H^{(k)}]}\).  
Step 3. Processor \(p_{i}(i=1,2,\cdots,p)\) computes  
\[c_{k-1}=\frac{\widetilde{\tau}_{k-1}}{(\widetilde{r}_{k-1}^{2}+ b_{k-1}^{2})^{\frac{1}{2}}},\;s_{k-1}=\frac{b_{k-1}}{(\widetilde{r}_{k-1}^{2}+ b_{k-1}^{2})^{\frac{1}{2}}},\;\varepsilon_{k+1}=b_{k}s_{k-1},\] \[\delta_{k}=\widetilde{\delta}_{k}c_{k-1}+a_{k}s_{k-1},\;\widetilde {\tau}_{k}=\widetilde{\delta}_{k}s_{k-1}-a_{k}c_{k-1},\;r_{k}=(\widetilde{r}_ {k}^{2}+b_{k}^{2})^{\frac{1}{2}},\;\widetilde{\delta}_{k+1}=-b_{k}c_{k-1},\]  
if \(\widetilde{r}_{k}<10^{-15}\) stop; otherwise, compute \(\widetilde{\xi}_{k}=(\varepsilon_{k}\xi_{k-2}+\delta_{k}\xi_{k-1})/\widetilde {\tau}_{k}\).  
Step 4. Processor \(p_{i}(i=1,2,\cdots,p)\) computes  
\[\begin{split}&\xi_{k}=-(\varepsilon_{k}\xi_{k-2}+\delta_{k}\xi_{k- 1})/r_{k},\;W_{i}^{k-1}=c_{k-1}\widetilde{W}_{i}^{(k-1)}+s_{k-1}Q_{i}^{(k)},\\ &\widetilde{W}_{i}^{(k)}=s_{k-1}\widetilde{W}_{i}^{k-1}-c_{k-1}Q _{i}(k),\;Y_{i}^{(k-1)}=Y_{i}^{(k-2)}+\xi_{k-1}W_{i}^{(k-1)},\\ & X_{i}^{(k)}=Y_{i}^{(k-1)}+\widetilde{\xi}_{k}\widetilde{W}_{i} ^{(k)}.\end{split}\]  
Step 5 Let \(k:=k+1\), turn to Step 1.