自動残差修正機能付き GBiCGSTAB$(s,L)$法 (科学技術計算アルゴリズムの数理的基盤と展開)

Size: px

Start display at page:

Download "自動残差修正機能付き GBiCGSTAB$(s,L)$法 (科学技術計算アルゴリズムの数理的基盤と展開)"

あきみこのえ
4 years ago
Views:

1 GBiCGSTAB $(s,l)$ GBiCGSTAB(s,L) with Auto-Correction of Residuals (Takeshi TSUKADA) NS Solutions Corporation (Kouki FUKAHORI) Graduate School of Information Science and Technology The University of Tokyo NEC (Masaaki TANIO) NEC Corporation (Masaaki SUGIHARA )*1 Graduate School of Information Science and Technology The University of Tokyo 1 $Ax=b$ $A$ $N\cross N$ $b$ $N$ 2007 Sonneveld van Gijzen [6, 7] $IDR(s)$ $N+N/s$ $BiCG$ BiCGSTAB(L) $(L>1)$ $IDR(s)$ 1 BiCGSTAB(L) $L>1$ 2009 IDR(s) GBiCGSTAB $(s, L)$ [8] IDR(s)stab(L) [5] GBiCGSTAB $(s, L)$ $IDR(s)stab(L)$ GBiCGSTAB $(s, L)$ $IDR(s)$ $s$ ( ) $*1$ msugihara@mist.i.u-tokyo.ac jp

2 150 GBiCGSTAB $(s, L)$ $IDR(s)$ [4] $\triangle r_{k}$ $A\Delta x_{k}$ : $\triangle r_{k}=-a\triangle x_{k}$ (1) $IDR(s)$ AC-IDR $(s)$ (Auto-Corrected $IDR(s)$ ) GBiCGSTAB $(s, L)$ GBiCGSTAB $(s,l)$ AC-GBiCGSTAB $(s,l)$ (GBiCGSTAB(s,L) with Auto-Correction of Residuals) (1) DC-GBiCGSTAB $(s, L)$ GBiCGSTAB $(s, L)$ with Direct-Computaion of Residuals) GBiCGSTAB $(s,l)$ AC-GBiCGSTAB $(s,l)$ DC-GBiCGSTAB $(s, L)$ (GBiCGSTAB(s, $L$ ) 2 GBiCGSTAB $(s, L)$ GBiCGSTAB $(s, L)$ Algorithm 1 $r_{k,p}^{(j)}=a^{p}r_{k}^{(j)},$ $U_{k,p}^{(j)}=A^{p}U_{k}^{(j)}$ 2 GBiCG-PART MR-PART 1 GBiCGSTAB(8,8) MatrixMarket wang4 ( ). $0$ { $500$ $600$ 700 Numbor of $MaW\infty$ 1 GBiCGSTAB(8,8) MatrixMarket walig4

3 151 $Algorithm1GBiCGSTAB(s,L)$ $x_{0}\in \mathbb{r}^{n}:\mathscr{d}ven,r_{0,0}:=b-a\tilde{r}_{0}\in \mathbb{r}^{n\cross s}:$ $k:=0$ Set $U_{0,0}^{(1)}:=[r_{0}, Ar_{0}, \cdots, A^{s-1}r_{0}]$ $U_{0,1}^{(1)}$ Compute given. $\Lambda I_{0}:=\tilde{R}_{0}^{T}U_{0,1}^{(1)},$ $m_{0}:=\tilde{r}_{0}^{t}r_{0}$ Solve $M\vec{\alpha}_{0}^{(1)}=m$ for $\vec{\alpha}_{0}^{(1)}$ $r_{0,0}^{(1)}:=r_{0,0}-u_{0,1}^{(1)}\vec{\alpha}_{0}^{(1)}x_{0}^{(1)}:=x_{0}+u_{0,0}^{(1)}\vec{\alpha}_{0}^{(1)}$ while 1 $r_{k,0}^{(0)}\vert\geq e\vert b\vert$ do $/*GBiCG-PART*/$ for $j=$ lto do do $L$ if $(k=0)\cap(j=1)$ then Go to $\{j=2\}$ end if for $i=$ lto do $s$ if $i=1$ then Solve $M_{k}^{(j-1)}\vec{\beta}=m_{k}^{(j-1)}$ $U_{k,p}^{(j)}e_{1}:=r_{k,p}^{(j-1)}-U_{k,p}^{(j-1)}\vec{\beta}$ for $\vec{\beta}$ $(p=0,1, \cdots, j-1)$ else Solve $[m_{k}^{(j-1)},$ $M_{k}^{(j)}[1 : i-2],$ $li_{k}^{(j-1)}[i :s]]\vec{\beta}=\lambda I_{k}^{(j)}e_{i-1}$ $\vec{\beta}\cdot$ for, $U_{k,p}^{(j)}e_{i}:=U_{k,p+1}^{(j)}e_{i-1}-[r_{k,p},$ $U_{k,p+1}^{(j)}[1 :i-2]$, $U_{k,p}^{(j-1)}[i :s]]\vec{\beta}$ $(p=0,1, \cdots, j-1)$ end if Compute $U_{k,j}^{(j)}e_{i}=A\cross U_{k,j-1}^{(j)}e_{i}$ $M_{k}^{(j)}e_{i}:=\tilde{R}_{0}^{T}U_{k,j}^{(j)}e_{i}$ end for $\Lambda I_{k}^{(j)}\vec{\alpha}_{k}^{(j)}=m_{k}^{(j-1)}$ Solve for $x_{k}^{(j)}:=x_{k}^{(j-1)}+u_{k0}^{(j)}\vec{\alpha}_{k}^{(j)}$ $\vec{\alpha}_{k}^{(j)}$ $r_{k,p}^{(j)}:=r_{k,p}^{(j-1)}-u_{k,p+1}^{(j)}\vec{\alpha}_{k}^{(j)}$ $(p=0,1_{\dot{1}}\cdots, j-1)$ Compute end for $/*MR-$PART $*/$ $\vec{\gamma}_{k+1}$ $:=$ argmin $\vec{\gamma}\vert $r_{k,j}^{(j)}=a\cross r_{k,j-1}^{(j)}$ r_{k,0}^{(l)}-[r_{k,1}^{(l)},$ $\cdots$, $r_{k,l}^{(l)}]\vec{\gamma}\vert$ $r_{k+1,0}^{(0)}:=r_{k,0}^{(l)}-[r_{k,1}^{(l)},$ $\cdots,$ $r_{k,l}^{(l)}]\vec{\gamma}_{k+1}$ $x_{k+1}^{(0)}$ $.=x_{k}^{(l)}+[r_{k_{\rangle}0}^{(l)},$ $\cdots,$ $r_{k,l-1}^{(l)}]\vec{\gamma}_{k+1}$. $U_{k+1,0}^{(0)}:=U_{k,0}^{(L)}-[U_{k,1}^{(L)},$ $\cdots,$ $U_{k,L}^{(L)}]\vec{\gamma}_{k+1}$ $1\downarrow I_{k+1}^{(0)}:=-\gamma_{k+1,L}ilI_{k}^{(L)}m_{k+1}^{(0)}=\tilde{R}_{0}^{T}r_{k+1}$ $k=k+1$ end while

4 152 3 AC-GBiCGSTAB $(s, L)$ 3.1 $AC- DR(s)$ $IDR(s)$ AC-IDR $(s)$ $\triangle r_{k}$ $A\triangle x_{k}$ $\frac{\vert\triangle r_{k}+a\triangle x_{k}\vert}{\vert b\vert}$ ( inconsistency ) inconsistency $I_{k}$ $\theta$ Algorithm 2 $\triangle x_{k}$ Compute Compute Ik( ) if then $(I_{k}<\theta)$ $\triangle r_{k}$ Compute normally else Compute $\triangle end if r_{k}$ by $x_{k+1}:=x_{k}+\triangle x_{k}$ $r_{k+1}:=r_{k}+\triangle r_{k}$ using $\triangle r_{k}:=-a\delta x_{k}$ AC-IDR $(s)$ 3 7 % $\sim$ 3.2 AC-GBiCGSTAB $(s, L)$ AC-GBiCGSTAB GBiCGSTAB $(s, L)$ $\triangle r_{k}$ : $(s, L)$ $\triangle x_{k}$ $\triangle x_{k}(=x_{k+1}^{(0)}-x_{k}^{(0)})=\sum_{j=1}^{l}u_{k,0}^{(j)}\vec{\alpha}_{k}^{(j)}+[r_{k,0}^{(l)},$ $r_{k,1}^{(l)},$ $\cdots,$ $r_{k,l-1}^{(l)}]\vec{\gamma}_{k+1}$, $\triangle r_{k}(=r_{k+1,0}^{(0)}-r_{k,0}^{(0)})=-\sum_{j=1}^{l}u_{k,1}^{(j)}r\tilde{v}_{k}^{(j)}-[r_{k,1\dot{/}}^{(l)}r_{k,2}^{(l)},$ $\cdots,$ $r_{k,l}^{(l)}]\vec{\gamma}_{k+1}$, $x_{k+1}^{(0)}=x_{k}^{(0)}+\triangle x_{k,}$. $r_{k+1,0}^{(0)}=r_{k,0}^{(0)}+\triangle r_{k}$.

5 153 GBiCGSTAB $(s, L)$ $IDR(s)$ $\triangle r_{k}$ $\frac{\vert\triangle r_{k}+a\triangle x_{k}\vert}{\vert b\vert}$ inconsistency $A\triangle x_{k}$ $\triangle r_{k}$ $\triangle x_{k}$ $I_{k}:= \frac{\vert r_{k,0}^{(0)}\vert}{\vert b }\cross\max_{1\leq j\leq L}$ $($Range $(\vec{\alpha}_{k}^{(j)}))\cross$ Range $(\vec{\gamma}_{k+1})$ $U$ ( ) inconsistency $\max c(i) $ Range(C) 2 $:= \frac{1\leq i\leq s}{\min_{1\leq j_{-s}^{i}} c(j) }$ inconsistency {e-008 le $1eW06$ [scaled $res duaq$ $ \max $ Range of $alpha\lrcorner)$] [Range of gamma] 2 $I_{k}$ inconsistency GBiCGSTAB $(s, L)$ AC- GBiCGSTAB $(s, L)$ Algorithm 3

6 , 154 Algorithm 3 AC-GBiCGSTAB $(s, L)$ initial setting $\Vert r_{k,0}^{(0)}\vert\geq\epsilon\vert b\vert$ while do $/*GBiCG-PART*/$ for $j=$ lto do do $L$ if $(k=0)\cap(j=1)$ then Go to $\{j=2 \}$ end if Update $U_{k,p}^{(j)}(p=0,1, \cdots,j)$ $\Lambda I_{k}^{(j)}=\tilde{R}_{0}^{T}U_{kj}^{(j)}$ Compute $\vec{\alpha}_{k}^{(j)}$ $\Lambda Solve I_{k}^{(j)}\vec{\alpha}_{k}^{(j)}=m_{k}^{(j-1)}$ for $r_{k,p}^{(j)}:=r_{k,p}^{(j-1)}-u_{k,p+1}^{(j)}\vec{\alpha}_{k}^{(j)}(p=0,1, \cdots, j-1)$ Compute end for $/*MR-$PART $*/$ $r_{k,j}^{(j)}=a\cross r_{k,j-1}^{(j)}$ $\vec{\gamma}_{k+1}$ $:= \arg\min_{\vec{\gamma}}\vert r_{k,0}^{(l)}-[r_{k,1}^{(l)}$, $\cdot\cdot\cdot$ $r_{k,l}^{(l)}]\vec{\gamma}\vert$ $\triangle x_{k}:=\sum_{j=1}^{l}u_{k,0}^{(j)}\vec{\alpha}_{k}^{(j)}+[r_{k,0}^{(l)},$ $r_{k,1}^{(l)},$ $\cdots,$ $r_{k,l-1}^{(l)}]\vec{\gamma}_{k+1}$ $I_{k}= \frac{\vert r_{k,0}^{(0)}\vert}{\vert b }\cross\max j$ if $(I_{k}<\theta)$ then $($Range $(\vec{\alpha}_{k}^{(j)}))\cross$ Range $(\vec{\gamma}_{k+1})$ $\triangle r_{k}:=-\sum_{j=1}^{l}u_{k,1}^{(j)}\vec{\alpha}_{k}^{(j)}-[r_{k,1}^{(l)},$ $r_{k,2}^{(l)},$ $\cdots.r_{k,l}^{(l)}]\vec{\gamma}_{k+1}$ else $\triangle r_{k}$ $:=-A\triangle x_{k}$ (direct-computation) end if $x_{k+1}^{(0)}:=x_{k}^{(0)}+\triangle x_{k}$ $r_{k+1,0}^{(0)}:=r_{k,0}^{(0)}+\triangle r_{k}$ end while 4 (1) GBiCGSTAB $(s, L)$ ( DC-GBiCGSTAB $(s, L)$ (GBiCGSTAB $(s, L)$ with Direct-Computaion of Residuals) ) GBiCGSTAB $(s,l)$ Y AC-GBiCGSTAB $(s,l)$ $\grave$ DC-GBiCGSTAB $(s, L)$ Xeon E5450 processor $(3.OGHz)$ Fortran90 ( Intel 10.1)

7 $\bullet$ $\bullet$ $\bullet$ 155. $s,$ : $x_{0}=0$. $L=1,2,4,8$. : $10^{-8}$ ) : $\theta=0.1$. lon $(N$ The University of Florida sparse matrix collection [1] Matrix- Market [2] 30 ( 2 ). $b$ $x$ 1 1 (a)wang4, (b) $sme3da$ 3 CPU time, $\geq 10^{-8}$ GBiCGSTAB$(s, L)$ $L=8$ AC-GBiCGSTA $(s, L)$ DC-GBiCGSTAB $(s, L)$ AC-GBiCGSTA $(s, L)$ DC-GBiCGSTAB $(s, L)$ GBiCGSTAB $(s, L)$ 2, 3 wang4, $sme3$da GBiCGSTAB(8, 8) AC-GBiCGSTAB(8, 8) DC-GBiCGSTAB(8, 8) AC-GBiCGSTAB DC-GBiCGSTAB AC-GBiCGSTAB DC-GBiCGSTAB 2 30 GBiCGSTAB AC-GBiCGSTAB DC-GBiCGSTAB CPU time CPU time GBiCGSTAB CPU time 1 2 AC-GBiCGSTAB(s,L) DC-GBiCGSTAB $(s, L)$ GBiCGSTAB $(s, L)$ ( ) 10% 5 GBiCGSTAB $(s, L)$ ( ) GBiCGSTAB $(s, L)$ ( AC-GBiCGSTAB(s, $L$ ) ( ) 10% DC-GBiCGSTAB $(s. L)$ )

$156 1 CPU time, ( wang4, $sme3da$ ) MV $($ $=$ time(s) tnorm $\geq$

8 156 1 CPU time, ( wang4, $sme3da$ ) MV $($ $=$ time(s) tnorm $\geq 10^{-8}$ (a) wang4 $=CPU$ time( ), tnorm $=$ ( ) tnorm $)$ (b) $smc3da$

9 157 $0$ Number of Matvecs (a) GBiCGSTAB(8,8) $0$ $35\mathfrak{N}$ lr Number of Ma(vecs (a) GBiCGSTAB(8,8) 4000 $0$ Number of MaVecs (b) AC-GBiCGSTAB $(8,8)$ $0$ KO 1000 lm $2\infty 0$ Number of Matvecs (b) AC-GBiCGSTAB(8,8) Numkr of Malvecs (c) DC-GBiCGSTAB $(8,8)$ 3 GBiCGSTAB(8,8), AC-GBiCGSTAB (8,8), DC-GBiCGSTAB(8,8) wang4 Number of Matvecs (c) DC-GBiCGSTAB(8,8) 4 GBiCGSTAB(8,8), AC-GBiCGSTAB (8,8), DC-GBiCGSTAB(8,8) $sme3da$

10 158 2CPU time $($ PCC(percentage of correct convergences) $=$ $s,$ $L=1,2,4,8$ $)$

11 159 [1] T. Davis: University of Florida sparse matrix collection, [2] MatrixMarket: [3] G. L. G. Sleijpen and D. R. Fokkema: BiCGSTAB(L) for linear equations involving unsymmetric matrices with complex spectrum, Electronic Transactions on Numencal Analysis, Vol. 1 (1993), pp [4] : 2008 (74), pp [5] G. L. G. Sleijpen and M. B. van Gijzen: Exploiting BiCGstab(L) strategies to induce dimension reduction, SIAM Journal on Scientific Computing, Vol. 32 (2010). pp [6] P. Sonneveld and M. B. van Gijzen: $IDR(s)$ : a family of simple and fast algorithms for solving large nonsymmetric systems of linear equations, Reports of the Department of Applied Mathematical Analysis, REPORT (2007), Delft University of Technology. AC-IDR(s) [7] P. Sonneveld and M. B. van Gijzen: IDR $(s)$ : a family of simple and fast algorithms for solving large nonsymmetric linear systems, SIAM Joumal on Scientific Computing, Vol. 31 (2008), pp [8] M. Tanio and M. Sugihara: GBi-CGSTAB $(s, L)$ : IDR $(s)$ with higher-order stabilization polynomials, Joumal of Computational and Applied Mathematics, Vol. 235 (2010), pp

IDRstab(s, L) GBiCGSTAB(s, L) 2. AC-GBiCGSTAB(s, L) Ax = b (1) A R n n x R n b R n 2.1 IDR s L r k+1 r k+1 = b Ax k+1 IDR(s) r k+1 = (I ω k A)(r k dr

1 2 IDR(s) GBiCGSTAB(s, L) IDR(s) IDRstab(s, L) GBiCGSTAB(s, L) Verification of effectiveness of Auto-Correction technique applied to preconditioned iterative methods Keiichi Murakami 1 Seiji Fujino 2