PARCEL SYCL v1.2 / User Guide User Guide API Reference Search Download 日本語

8 Linear Solvers

This chapter describes the iterative algorithms used in the library routines. Throughout, we consider solving the linear system Ax=bAx = b whose coefficient matrix AA is a real nglobal×nglobaln_{global} \times n_{global} matrix. Each section gives the algorithm and its notation. The details of the convergence check, the handling of breakdowns and non-finite values, and the returned values are given in the solver() section of each solver in the API Reference (“Common Handling in the Linear Solvers”). ⟨⋅,⋅⟩\langle \cdot,\cdot \rangle denotes the inner product and ∥⋅∥\|\cdot\| the 2-norm. All four linear solvers (pcg, pbicgstab, pgmres, pcagmres) check convergence by comparing the relative residual ∥r∥/∥b∥\|r\| / \|b\| with the value toltol set by set_tolerance() (convergence when ∥r∥/∥b∥<tol\|r\| / \|b\| < tol). The matrices each method can handle and its characteristics are listed below.

Method Class Target matrix Characteristics
Preconditioned conjugate gradient method parcel::krylov::pcg Symmetric positive definite (the preconditioner matrix also symmetric positive definite) Few operations and collective communications per iteration
Preconditioned biconjugate gradient stabilized method parcel::krylov::pbicgstab Symmetric or nonsymmetric Right preconditioning. Performs SpMV and preconditioning twice each per iteration. The residual does not necessarily decrease monotonically
Preconditioned generalized minimal residual method parcel::krylov::pgmres Symmetric or nonsymmetric Right preconditioning. Minimizes the residual norm within the restart length mm
Preconditioned communication-avoiding generalized minimal residual method parcel::krylov::pcagmres Symmetric or nonsymmetric (the moment method only for symmetric matrices without preconditioning) Right preconditioning. Generates ss basis vectors at once and orthogonalizes them, performing iterations equivalent to GMRES(stst) with fewer collective communications. Whether the orthonormal basis QQ is formed explicitly can be selected with set_explicit_q() (if not, orthogonalization uses the Cholesky factorization of the Gram matrix)

In the algorithms and formulas of this manual, iteration numbers are written as parenthesized superscripts (x(i)x^{(i)}, α(i)\alpha^{(i)}), and components of a vector and indices within a set of vectors as subscripts (xix_{i}, vjv_{j}). A superscript without parentheses is a power ((AK−1)s(AK^{-1})^{s}), ATA^{T} is the transpose and A−1A^{-1} the inverse. Matrices are written in upper case, vectors and scalars in lower-case italics, and English keywords and function names (solve\mathrm{solve}, chol\mathrm{chol}, etc.) in upright type. nglobaln_{global} is the order of the matrix (the number of global rows) and nlocaln_{local} the number of rows owned by each rank. Symbols are defined per section and may have a different meaning in another section.

The convergence status constants and their meaning for each solver are summarized in “Convergence Status” in the API Reference.


8.1 Preconditioned Conjugate Gradient Method [1]

The conjugate gradient method (CG method) is a Krylov subspace method for symmetric matrices. Both the coefficient matrix AA and the preconditioner matrix KK are assumed to be symmetric positive definite.

x(0)x^{(0)} is the initial guess passed as the argument x of solver(), KK is the preconditioner matrix specified by set_precon_algo() and related functions (see the “Preconditioners” chapter; K=IK = I without preconditioning), toltol is the convergence tolerance set by set_tolerance() (default 1.0e-8), and NN is the maximum number of iterations set by set_max_iteration() (default 10000). zz is the preconditioned residual, p(i)p^{(i)} is the search direction, q(i)q^{(i)} is Ap(i)Ap^{(i)}, and ρ(i)\rho^{(i)}, α(i)\alpha^{(i)}, β(i)\beta^{(i)}, and γ\gamma are scalars.

  1. Computer(0)=b−Ax(0)forsomeinitialguessx(0)\mathrm{Compute}\ r^{(0)} = b - Ax^{(0)}\ \mathrm{for}\ \mathrm{some}\ \mathrm{initial}\ \mathrm{guess}\ x^{(0)}
  2. p(−1)=0p^{(-1)} = 0
  3. β(−1)=0\beta^{(-1)} = 0
  4. solvezfromKz=r(0)\mathrm{solve}\ z\ \mathrm{from}\ Kz = r^{(0)}
  5. ρ(0)=⟨z,r(0)⟩\rho^{(0)} = \langle z,r^{(0)} \rangle
  6. fori=0,1,…,N−1\mathrm{for}\ i = 0,1,\ldots,N - 1
  7.   p(i)=z+β(i−1)p(i−1)p^{(i)} = z + \beta^{(i - 1)}p^{(i - 1)}
  8.   q(i)=Ap(i)q^{(i)} = Ap^{(i)}
  9.   γ=⟨p(i),q(i)⟩\gamma = \langle p^{(i)},q^{(i)} \rangle
  10.   α(i)=ρ(i)/γ\alpha^{(i)} = \rho^{(i)}\ /\ \gamma
  11.   x(i+1)=x(i)+α(i)p(i)x^{(i + 1)} = x^{(i)} + \alpha^{(i)}p^{(i)}
  12.   r(i+1)=r(i)−α(i)q(i)r^{(i + 1)} = r^{(i)} - \alpha^{(i)}q^{(i)}
  13.   if∥r(i+1)∥/∥b∥<tolthen\mathrm{if}\ \|r^{(i + 1)}\|\ /\ \|b\| < tol\ \mathrm{then}
  14.     quit\mathrm{quit}
  15.   endif\mathrm{endif}
  16.   solvezfromKz=r(i+1)\mathrm{solve}\ z\ \mathrm{from}\ Kz = r^{(i + 1)}
  17.   ρ(i+1)=⟨z,r(i+1)⟩\rho^{(i + 1)} = \langle z,r^{(i + 1)} \rangle
  18.   β(i)=ρ(i+1)/ρ(i)\beta^{(i)} = \rho^{(i + 1)}\ /\ \rho^{(i)}
  19. end\mathrm{end}

In the implementation, by default the solution update of xx at line 11 is performed at every iteration and only one search direction p(i)p^{(i)} is kept. If the environment variable PARCEL_PSTEP is set to a value k≥2k \ge 2, kk search directions are accumulated and added to xx together every kk iterations (the reads and writes of xx drop to 1/k1/k, which is slightly faster, at the cost of the memory of k−1k - 1 vectors; see “Choosing Between Memory and Speed”). The solution is mathematically the same; only the order of rounding changes. Convergence is checked with rr at line 12, so the number of iterations does not depend on PARCEL_PSTEP.

The details of the convergence check, the handling of breakdowns and non-finite values, the returned values and the implementation details are given in “Convergence by Solver” in the API Reference.


8.2 Preconditioned Biconjugate Gradient Stabilized Method [1]

The biconjugate gradient stabilized method (Bi-CGSTAB) is a Krylov subspace method for nonsymmetric matrices. The preconditioner is applied as a right preconditioner; that is, the iteration is performed on AK−1AK^{-1} and the solution is updated with the directions p̂\hat{p} and ê\hat{e} multiplied by K−1K^{-1}, so the residual r(i)r^{(i)} corresponds to the unpreconditioned residual b−Ax(i)b - Ax^{(i)}.

x(0)x^{(0)} is the initial guess passed as the argument x of solver(), KK is the preconditioner matrix specified by set_precon_algo() and related functions, toltol is the value of set_tolerance() (default 1.0e-8), and NN is the value of set_max_iteration() (default 10000). r(0)r^{(0)} is the initial residual, and r*=r(0)r^{\ast} = r^{(0)} is the dual (shadow) residual, which is kept fixed during the iteration. p(i)p^{(i)} is the search direction, ee is the intermediate residual, and c1c_{1}, c2c_{2}, c3c_{3}, α\alpha, and β\beta are scalars.

  1. Computer(0)=b−Ax(0)forsomeinitialguessx(0)\mathrm{Compute}\ r^{(0)} = b - Ax^{(0)}\ \mathrm{for}\ \mathrm{some}\ \mathrm{initial}\ \mathrm{guess}\ x^{(0)}
  2. r*=r(0),p(0)=r(0)r^{\ast} = r^{(0)},\ \ p^{(0)} = r^{(0)}
  3. c1=⟨r*,r(0)⟩c_{1} = \langle r^{\ast},r^{(0)} \rangle
  4. fori=0,1,…,N−1\mathrm{for}\ i = 0,1,\ldots,N - 1
  5.   solvep̂fromKp̂=p(i)\mathrm{solve}\ \hat{p}\ \mathrm{from}\ K\hat{p} = p^{(i)}
  6.   q=Ap̂q = A\hat{p}
  7.   c2=⟨r*,q⟩c_{2} = \langle r^{\ast},q \rangle
  8.   ifc2=0orc2isnotfinitethen\mathrm{if}\ c_{2} = 0\ \mathrm{or}\ c_{2}\ \mathrm{is}\ \mathrm{not}\ \mathrm{finite}\ \mathrm{then}
  9.     quit(breakdown)\mathrm{quit}\ (\mathrm{breakdown})
  10.   endif\mathrm{endif}
  11.   α=c1/c2\alpha = c_{1}\ /\ c_{2}
  12.   e=r(i)−αqe = r^{(i)} - \alpha q
  13.   solveêfromKê=e\mathrm{solve}\ \hat{e}\ \mathrm{from}\ K\hat{e} = e
  14.   v=Aêv = A\hat{e}
  15.   if⟨v,v⟩=0then\mathrm{if}\ \langle v,v \rangle = 0\ \mathrm{then}
  16.     x(i+1)=x(i)+αp̂x^{(i + 1)} = x^{(i)} + \alpha\hat{p}
  17.     quit(convergedif∥e∥/∥b∥<tol,otherwisebreakdown)\mathrm{quit}\ (\mathrm{converged}\ \mathrm{if}\ \|e\|\ /\ \|b\| < tol,\ \mathrm{otherwise}\ \mathrm{breakdown})
  18.   endif\mathrm{endif}
  19.   c3=⟨e,v⟩/⟨v,v⟩c_{3} = \langle e,v \rangle\ /\ \langle v,v \rangle
  20.   x(i+1)=x(i)+αp̂+c3êx^{(i + 1)} = x^{(i)} + \alpha\hat{p} + c_{3}\hat{e}
  21.   r(i+1)=e−c3vr^{(i + 1)} = e - c_{3}v
  22.   c1=⟨r*,r(i+1)⟩c_{1} = \langle r^{\ast},r^{(i + 1)} \rangle
  23.   if∥r(i+1)∥/∥b∥<tolthen\mathrm{if}\ \|r^{(i + 1)}\|\ /\ \|b\| < tol\ \mathrm{then}
  24.     quit\mathrm{quit}
  25.   endif\mathrm{endif}
  26.   ifc3=0orc1=0then\mathrm{if}\ c_{3} = 0\ \mathrm{or}\ c_{1} = 0\ \mathrm{then}
  27.     quit(breakdown)\mathrm{quit}\ (\mathrm{breakdown})
  28.   endif\mathrm{endif}
  29.   β=c1/(c2c3)\beta = c_{1}\ /\ (c_{2}c_{3})
  30.   p(i+1)=r(i+1)+β(p(i)−c3q)p^{(i + 1)} = r^{(i + 1)} + \beta(p^{(i)} - c_{3}q)
  31. end\mathrm{end}

The details of the convergence check, the handling of breakdowns and non-finite values, the returned values and the implementation details are given in “Convergence by Solver” in the API Reference.


8.3 Preconditioned Generalized Minimal Residual Method [1]

The generalized minimal residual method (GMRES(m)) is a Krylov subspace method for nonsymmetric matrices. It updates the approximate solution by minimizing the residual norm over the subspace built by mm steps of the Arnoldi process, and then restarts the iteration using the result as the initial guess (restarting). The PARCEL pgmres uses right preconditioning: the Arnoldi process is performed on AK−1AK^{-1}, and K−1K^{-1} is applied only when the approximate solution is updated. The residual being minimized is therefore the unpreconditioned residual b−Axb - Ax itself. The classical Gram-Schmidt method and the modified Gram-Schmidt method are available as the orthogonalization methods of the Arnoldi process.

x(0)x^{(0)} is the initial guess passed as the argument x of solver(), x(j)x^{(j)} is the approximate solution at the start of the jj-th restart, KK is the preconditioner matrix specified by set_precon_algo() and related functions, mm is the restart length set by set_restart() (default 30), and toltol is the value of set_tolerance() (default 1.0e-8). The maximum number of restarts JJ is determined from the value NN of set_max_iteration() (default 10000) as J=⌈N/m⌉J = \lceil N/m \rceil (if NN is not a multiple of mm, the last restart stops after the remaining N−(J−1)mN - (J-1)m columns). viv_{i} are the orthonormal basis vectors, hk,ih_{k,i} are the entries of the Hessenberg matrix, cos⁡ϕi\cos\phi_{i} and sin⁡ϕi\sin\phi_{i} are the Givens rotation coefficients, ζ=(ζ1,…,ζm+1)T\zeta = (\zeta_{1},\ldots,\zeta_{m+1})^{T} is the rotated right-hand-side vector, HmH_{m} is the m×mm \times m upper triangular matrix consisting of the rotated hk,ih_{k,i} (1≤k≤i≤m1 \leq k \leq i \leq m), and ζ1:m\zeta_{1:m} denotes the first mm components of ζ\zeta. Lines 12-15 show the case where the modified Gram-Schmidt method (parcel::qr::QR_MGS, the default) is selected with set_qr_algo(). The implementation computes v1v_{1} and ζ\zeta with both signs reversed; the two reversals cancel, and the result is the same.

  1. Chooseinitialguessx(0)\mathrm{Choose}\ \mathrm{initial}\ \mathrm{guess}\ x^{(0)}
  2. forj=0,1,…,J−1\mathrm{for}\ j = 0,1,\ldots,J - 1
  3.   r=b−Ax(j)r = b - Ax^{(j)}
  4.   if∥r∥/∥b∥<tolthen\mathrm{if}\ \|r\|\ /\ \|b\| < tol\ \mathrm{then}
  5.     quit\mathrm{quit}
  6.   endif\mathrm{endif}
  7.   v1=r/∥r∥v_{1} = r\ /\ \|r\|
  8.   ζ=(∥r∥,0,…,0)T\zeta = (\|r\|,0,\ldots,0)^{T}
  9.   fori=1,2,…,m\mathrm{for}\ i = 1,2,\ldots,m
  10.     solvev̂ifromKv̂i=vi\mathrm{solve}\ \hat{v}_{i}\ \mathrm{from}\ K\hat{v}_{i} = v_{i}
  11.     w=Av̂iw = A\hat{v}_{i}
  12.     fork=1,2,…,i\mathrm{for}\ k = 1,2,\ldots,i
  13.       hk,i=⟨w,vk⟩h_{k,i} = \langle w,v_{k} \rangle
  14.       w=w−hk,ivkw = w - h_{k,i}v_{k}
  15.     end\mathrm{end}
  16.     hi+1,i=∥w∥h_{i + 1,i} = \|w\|
  17.     vi+1=w/hi+1,iv_{i + 1} = w\ /\ h_{i + 1,i}
  18.     fork=1,2,…,i−1\mathrm{for}\ k = 1,2,\ldots,i - 1
  19.       (hk,ihk+1,i)=(cos⁡ϕk−sin⁡ϕksin⁡ϕkcos⁡ϕk)(hk,ihk+1,i)\begin{pmatrix} h_{k,i} \\ h_{k + 1,i} \end{pmatrix} = \begin{pmatrix} \cos\phi_{k} & -\sin\phi_{k} \\ \sin\phi_{k} & \cos\phi_{k} \end{pmatrix}\begin{pmatrix} h_{k,i} \\ h_{k + 1,i} \end{pmatrix}
  20.     end\mathrm{end}
  21.     cos⁡ϕi=1/1+(hi+1,i/hi,i)2\cos\phi_{i} = 1\ /\ \sqrt{1 + (h_{i + 1,i}\ /\ h_{i,i})^{2}}
  22.     sin⁡ϕi=−cos⁡ϕihi+1,i/hi,i\sin\phi_{i} = -\cos\phi_{i}h_{i + 1,i}\ /\ h_{i,i}
  23.     (ζiζi+1)=(cos⁡ϕi−sin⁡ϕisin⁡ϕicos⁡ϕi)(ζiζi+1)\begin{pmatrix} \zeta_{i} \\ \zeta_{i + 1} \end{pmatrix} = \begin{pmatrix} \cos\phi_{i} & -\sin\phi_{i} \\ \sin\phi_{i} & \cos\phi_{i} \end{pmatrix}\begin{pmatrix} \zeta_{i} \\ \zeta_{i + 1} \end{pmatrix}
  24.     hi,i=cos⁡ϕihi,i−sin⁡ϕihi+1,ih_{i,i} = \cos\phi_{i}h_{i,i} - \sin\phi_{i}h_{i + 1,i}
  25.     hi+1,i=0h_{i + 1,i} = 0
  26.   end\mathrm{end}
  27.   y=Hm−1ζ1:my = H_{m}^{-1}\zeta_{1:m}
  28.   solvex̂fromKx̂=∑k=1mykvk\mathrm{solve}\ \hat{x}\ \mathrm{from}\ K\hat{x} = \sum_{k = 1}^{m} y_{k}v_{k}
  29.   x(j+1)=x(j)+x̂x^{(j+1)} = x^{(j)} + \hat{x}
  30. end\mathrm{end}

The details of the convergence check, the handling of breakdowns and non-finite values, the returned values and the implementation details are given in “Convergence by Solver” in the API Reference.


8.4 Preconditioned Communication-Avoiding Generalized Minimal Residual Method [2,3]

The communication-avoiding generalized minimal residual method (CA-GMRES(s,t)) is a Krylov subspace method for nonsymmetric matrices. It generates, at once, the basis vectors corresponding to ss iterations of GMRES(m) and orthogonalizes them block by block. This is repeated tt times, the approximate solution is updated with the resulting stst basis vectors, and the iteration is restarted with the result as the initial guess. m=stm = st corresponds to the restart length of GMRES(m). Mathematically, CA-GMRES(s,t) and GMRES(m) have equivalent convergence, and by applying a communication-avoiding QR factorization, CA-GMRES reduces the number of collective communications compared with GMRES(m). However, because ss basis vectors are generated at once, if ss is too large, rounding errors destroy the orthogonality of the basis vectors and the convergence becomes worse than that of GMRES. PARCEL supports only the monomial basis (vi+1=AK−1viv_{i+1} = AK^{-1}v_{i}); the Newton basis is not implemented. As in pgmres, right preconditioning is used.

x(0)x^{(0)} is the initial guess passed as the argument x of solver(), x(j)x^{(j)} is the approximate solution at the start of the jj-th restart, KK is the preconditioner matrix specified by set_precon_algo() and related functions, ss and tt are the values set by set_restart(s, t) (default s=8s = 8, t=4t = 4), and toltol is the value of set_tolerance() (default 1.0e-8). The maximum number of restarts JJ is determined from the value NN of set_max_iteration() (default 10000) as J=⌈N/(st)⌉J = \lceil N/(st) \rceil (if NN is not a multiple of stst, the last restart solves the least-squares problem with the remaining columns only). The QR factorization method at lines 19 and 26 is selected with set_qr_algo() (parcel::qr::QR_CGS, QR_MGS (default), QR_CHOLESKYQR; see the “QR Factorization” chapter). The algorithm below forms the orthonormal basis QQ explicitly. The case without forming QQ is described below.

B_=[e2,…,es+1]\underline{B} = [e_{2},\ldots,e_{s+1}] is the change-of-basis matrix of the monomial basis ((s+1)×s(s+1) \times s; ele_{l} is the ll-th unit vector), BB is its first ss rows, and bkb_{k} is its entry in row s+1s+1, column ss. An underlined symbol denotes the version with one more vector (column or row) than the symbol without the underline. V_k=[vsk+1,…,vs(k+1)+1]\underline{V}_{k} = [v_{sk+1},\ldots,v_{s(k+1)+1}] are the s+1s+1 basis vectors generated in the kk-th block, and VkV_{k} are those ss vectors excluding the first. Q=[q1,q2,…]Q = [q_{1}, q_{2}, \ldots] is the orthonormalized basis, and Q1:mQ_{1:m} denotes its first mm columns. P_0\underline{P}_{0} and R_0\underline{R}_{0} are the QR factors of V_0\underline{V}_{0}, and PkP_{k} and SkS_{k} are the QR factors of VkV_{k}. C_k\underline{C}_{k} is the coefficient matrix of the block classical Gram-Schmidt method ((sk+1)×(s+1)(sk+1) \times (s+1)), CkC_{k} is its ss columns excluding the first (corresponding to VkV_{k}), and EkE_{k} is the first ss columns of C_k\underline{C}_{k} with the last row removed. R_k\underline{R}_{k} is the (s+1)×(s+1)(s+1) \times (s+1) upper triangular matrix obtained by the QR factorization, RkR_{k} is its leading s×ss \times s block, zkz_{k} and ρk\rho_{k} are the upper ss components and the diagonal entry of its (s+1)(s+1)-th column, and δk\delta_{k} is the entry of RkR_{k} in row ss, column ss. H_(k)\underline{H}_{(k)} is the (s(k+1)+1)×s(k+1)(s(k+1)+1) \times s(k+1) Hessenberg matrix for Q1:s(k+1)+1Q_{1:s(k+1)+1}, and H(k)H_{(k)} is that matrix with the last row removed. UkU_{k} and HkH_{k} are the parts of the ss columns added to H_(k)\underline{H}_{(k)} in the kk-th block that lie in the rows of the previous blocks and of the kk-th block, respectively, and γk\gamma_{k} is the entry in its last row. ζ\zeta is the rotated right-hand-side vector, ζ1:st\zeta_{1:st} denotes its first stst components, hk,ih_{k,i} is the (k,i)(k,i) entry of H_(t−1)\underline{H}_{(t-1)}, and cos⁡ϕi\cos\phi_{i} and sin⁡ϕi\sin\phi_{i} are the Givens rotation coefficients. After the rotations, H(t−1)H_{(t-1)} is upper triangular.

  1. B_=[e2,e3,…,es+1]\underline{B} = [e_{2},e_{3},\ldots,e_{s + 1}]
  2. Chooseinitialguessx(0)\mathrm{Choose}\ \mathrm{initial}\ \mathrm{guess}\ x^{(0)}
  3. forj=0,1,…,J−1\mathrm{for}\ j = 0,1,\ldots,J - 1
  4.   r=b−Ax(j)r = b - Ax^{(j)}
  5.   if∥r∥/∥b∥<tolthen\mathrm{if}\ \|r\|\ /\ \|b\| < tol\ \mathrm{then}
  6.     quit\mathrm{quit}
  7.   endif\mathrm{endif}
  8.   v1=r/∥r∥v_{1} = r\ /\ \|r\|
  9.   ζ=(∥r∥,0,…,0)T\zeta = (\|r\|,0,\ldots,0)^{T}
  10.   fork=0,1,…,t−1\mathrm{for}\ k = 0,1,\ldots,t - 1
  11.     ifk>0then\mathrm{if}\ k > 0\ \mathrm{then}
  12.       vsk+1=qsk+1v_{sk + 1} = q_{sk + 1}
  13.     endif\mathrm{endif}
  14.     fori=1,2,…,s\mathrm{for}\ i = 1,2,\ldots,s
  15.       solvev̂sk+ifromKv̂sk+i=vsk+i\mathrm{solve}\ \hat{v}_{sk + i}\ \mathrm{from}\ K\hat{v}_{sk + i} = v_{sk + i}
  16.       vsk+i+1=Av̂sk+iv_{sk + i + 1} = A\hat{v}_{sk + i}
  17.     end\mathrm{end}
  18.     ifk=0then\mathrm{if}\ k = 0\ \mathrm{then}
  19.       QRdecompositionV_0=P_0R_0\mathrm{QR}\ \mathrm{decomposition}\ \underline{V}_{0} = \underline{P}_{0}\underline{R}_{0}
  20.       Q1:s+1=P_0Q_{1:s+1} = \underline{P}_{0}
  21.       H_(0)=R_0B_R0−1\underline{H}_{(0)} = \underline{R}_{0}\underline{B}R_{0}^{-1}
  22.       γ0=δ0−1ρ0b0\gamma_{0} = \delta_{0}^{-1}\rho_{0}b_{0}
  23.     else\mathrm{else}
  24.       C_k=Q1:sk+1TV_k\underline{C}_{k} = Q_{1:sk+1}^{T}\underline{V}_{k}
  25.       Vk=Vk−Q1:sk+1CkV_{k} = V_{k} - Q_{1:sk+1}C_{k}
  26.       QRdecompositionVk=PkSk\mathrm{QR}\ \mathrm{decomposition}\ V_{k} = P_{k}S_{k}
  27.       Q1:s(k+1)+1=[Q1:sk+1,Pk]Q_{1:s(k+1)+1} = [Q_{1:sk+1},P_{k}]
  28.       R_k=(Rkzk01,sρk)\underline{R}_{k} = \begin{pmatrix} R_{k} & z_{k} \\ 0_{1,s} & \rho_{k} \end{pmatrix}
  29.       Uk=−H(k−1)EkRk−1+C_kB_Rk−1U_{k} = -H_{(k-1)}E_{k}R_{k}^{-1} + \underline{C}_{k}\underline{B}R_{k}^{-1}
  30.       Hk=RkBRk−1+δk−1bkzkesT−γk−1e1eskTEkRk−1H_{k} = R_{k}BR_{k}^{-1} + \delta_{k}^{-1}b_{k}z_{k}e_{s}^{T} - \gamma_{k - 1}e_{1}e_{sk}^{T}E_{k}R_{k}^{-1}
  31.       γk=δk−1ρkbk\gamma_{k} = \delta_{k}^{-1}\rho_{k}b_{k}
  32.       H_(k)=(H(k−1)Ukγk−1e1eskT01,skHkγkesT)\underline{H}_{(k)} = \begin{pmatrix} H_{(k-1)} & U_{k} \\ \begin{matrix} \gamma_{k - 1}e_{1}e_{sk}^{T} \\ 0_{1,sk} \end{matrix} & \begin{matrix} H_{k} \\ \gamma_{k}e_{s}^{T} \end{matrix} \end{pmatrix}
  33.     endif\mathrm{endif}
  34.   end\mathrm{end}
  35.   fori=1,2,…,st\mathrm{for}\ i = 1,2,\ldots,st
  36.     fork=1,2,…,i−1\mathrm{for}\ k = 1,2,\ldots,i - 1
  37.       (hk,ihk+1,i)=(cos⁡ϕk−sin⁡ϕksin⁡ϕkcos⁡ϕk)(hk,ihk+1,i)\begin{pmatrix} h_{k,i} \\ h_{k + 1,i} \end{pmatrix} = \begin{pmatrix} \cos\phi_{k} & -\sin\phi_{k} \\ \sin\phi_{k} & \cos\phi_{k} \end{pmatrix}\begin{pmatrix} h_{k,i} \\ h_{k + 1,i} \end{pmatrix}
  38.     end\mathrm{end}
  39.     cos⁡ϕi=1/1+(hi+1,i/hi,i)2\cos\phi_{i} = 1\ /\ \sqrt{1 + (h_{i + 1,i}\ /\ h_{i,i})^{2}}
  40.     sin⁡ϕi=−cos⁡ϕihi+1,i/hi,i\sin\phi_{i} = -\cos\phi_{i}h_{i + 1,i}\ /\ h_{i,i}
  41.     (ζiζi+1)=(cos⁡ϕi−sin⁡ϕisin⁡ϕicos⁡ϕi)(ζiζi+1)\begin{pmatrix} \zeta_{i} \\ \zeta_{i + 1} \end{pmatrix} = \begin{pmatrix} \cos\phi_{i} & -\sin\phi_{i} \\ \sin\phi_{i} & \cos\phi_{i} \end{pmatrix}\begin{pmatrix} \zeta_{i} \\ \zeta_{i + 1} \end{pmatrix}
  42.     hi,i=cos⁡ϕihi,i−sin⁡ϕihi+1,ih_{i,i} = \cos\phi_{i}h_{i,i} - \sin\phi_{i}h_{i + 1,i}
  43.     hi+1,i=0h_{i + 1,i} = 0
  44.   end\mathrm{end}
  45.   y=H(t−1)−1ζ1:sty = H_{(t-1)}^{-1}\zeta_{1:st}
  46.   solvex̂fromKx̂=∑k=1stykqk\mathrm{solve}\ \hat{x}\ \mathrm{from}\ K\hat{x} = \sum_{k = 1}^{st} y_{k}q_{k}
  47.   x(j+1)=x(j)+x̂x^{(j+1)} = x^{(j)} + \hat{x}
  48. end\mathrm{end}

Lines 14-17 generate the monomial basis of the kk-th block (B_\underline{B} is fixed) and consist only of preconditioning and sparse matrix-vector products (no collective communication). Lines 35-44 apply the Givens rotations to each column of the Hessenberg matrix of the tt blocks, and lines 45-47 update the solution.

The details of the convergence check, the handling of breakdowns and non-finite values, the returned values and the implementation details are given in “Convergence by Solver” in the API Reference.

8.4.1 How Q Is Formed (set_explicit_q)

pcagmres lets you choose with set_explicit_q(mode) whether the orthogonalized basis QQ is formed explicitly (the value can be obtained with get_explicit_q()). mode is one of the following constants in the namespace parcel::krylov.

Constant Value Behavior
CAGMRES_Q_AUTO (default) 0 Forms QQ as in the algorithm above, except that QQ is not formed when QR_CHOLESKYQR is used with t=1t = 1
CAGMRES_Q_EXPLICIT 1 Always forms QQ (also with QR_CHOLESKYQR and t=1t = 1)
CAGMRES_Q_IMPLICIT 2 Does not form QQ for any tt (below). The QR factorization is QR_CHOLESKYQR (used if set_qr_algo() is not called) or QR_CAGMRES_CHOLESKYQR (the moment method)

The combinations of CAGMRES_Q_IMPLICIT with QR_CGS or QR_MGS, and of QR_CAGMRES_CHOLESKYQR with CAGMRES_Q_AUTO or CAGMRES_Q_EXPLICIT, throw std::invalid_argument at the entry of solver() (the setters may be called in any order, so the combination is checked at the entry). Out-of-range values make set_explicit_q() throw std::invalid_argument. get_qr_algo() returns the QR factorization actually used. The selected mode is shown at the end of the timing line (the pcagmres time line), such as Q = auto: formed or Q = implicit: not formed, CholeskyQR.

8.4.2 When Q Is Not Formed (CAGMRES_Q_IMPLICIT) [2,3,7]

When set_explicit_q(parcel::krylov::CAGMRES_Q_IMPLICIT) is specified, the following three points differ from the algorithm above.

  1. The orthonormal basis QQ is not formed explicitly. The basis V=[v0,…,vst]V = [v_{0},\ldots,v_{st}] is kept as it is, and only the upper triangular matrix RR (V=QRV = QR) is obtained from the Cholesky factorization of the Gram matrix VTVV^{T}V. The Hessenberg matrix is assembled from RR with the same formulas as in the algorithm above, and the solution update uses V(R−1y)V(R^{-1}y) instead of QyQy. The default (CAGMRES_Q_AUTO) with QR_CHOLESKYQR omits QQ only when t=1t = 1, whereas CAGMRES_Q_IMPLICIT omits it also for t>1t > 1.
  2. The basis is stored separately in even- and odd-numbered vectors, and their storage precisions can be selected with the template arguments Teven_basis and Todd_basis of solver() (both default to Tbasis; not used except with CAGMRES_Q_IMPLICIT).
  3. With set_qr_algo(parcel::qr::QR_CAGMRES_CHOLESKYQR), the Gram matrix of the first block is built from the moments (QR Factorization chapter). This is correct only when AA is symmetric and there is no preconditioning.

x(0)x^{(0)} is the initial guess passed as the argument x of solver(), x(j)x^{(j)} is the approximate solution at the start of the jj-th restart, KK is the preconditioner matrix specified by set_precon_algo() and related functions, ss and tt are the values set by set_restart(s, t) (default s=8s = 8, t=4t = 4), and toltol is the value of set_tolerance() (default 1.0e-8). The maximum number of restarts JJ is determined from the value NN of set_max_iteration() (default 10000) as J=⌈N/(st)⌉J = \lceil N/(st) \rceil. In this section the basis vectors are numbered from 0; Va:b=[va,…,vb]V_{a:b} = [v_{a},\ldots,v_{b}], Ra:b,c:dR_{a:b,c:d} is the submatrix of RR in rows aa to bb and columns cc to dd, Wk=Vsk+1:sk+sW_{k} = V_{sk+1:sk+s} are the ss basis vectors newly generated in the kk-th block, and ele_{l} is the ll-th unit vector (0-based). chol(S)\mathrm{chol}(S) denotes the upper triangular matrix UU of the Cholesky factorization S=UTUS = U^{T}U of a symmetric matrix SS. H_(k)\underline{H}_{(k)} and ζ\zeta are the same as in the pcagmres algorithm above, and the Givens rotations in lines 28-30 are the same computation as lines 35-44 of the algorithm above.

  1. Chooseinitialguessx(0)\mathrm{Choose}\ \mathrm{initial}\ \mathrm{guess}\ x^{(0)}
  2. forj=0,1,…,J−1\mathrm{for}\ j = 0,1,\ldots,J - 1
  3.   r=b−Ax(j)r = b - Ax^{(j)}
  4.   if∥r∥/∥b∥<tolthen\mathrm{if}\ \|r\|\ /\ \|b\| < tol\ \mathrm{then}
  5.     quit\mathrm{quit}
  6.   endif\mathrm{endif}
  7.   v0=r/∥r∥v_{0} = r\ /\ \|r\|
  8.   ζ=(∥r∥,0,…,0)T\zeta = (\|r\|,0,\ldots,0)^{T}
  9.   fork=0,1,…,t−1\mathrm{for}\ k = 0,1,\ldots,t - 1
  10.     ifk=0then\mathrm{if}\ k = 0\ \mathrm{then}
  11.       v‾=v0\bar{v} = v_{0}
  12.     else\mathrm{else}
  13.       v‾=V0:skR0:sk,0:sk−1esk\bar{v} = V_{0:sk}R_{0:sk,0:sk}^{-1}e_{sk}
  14.     endif\mathrm{endif}
  15.     fori=1,2,…,s\mathrm{for}\ i = 1,2,\ldots,s
  16.       solvepfromKp=v‾\mathrm{solve}\ p\ \mathrm{from}\ Kp = \bar{v}
  17.       vsk+i=Apv_{sk + i} = Ap
  18.       v‾=vsk+i\bar{v} = v_{sk + i}
  19.     end\mathrm{end}
  20.     ifk=0then\mathrm{if}\ k = 0\ \mathrm{then}
  21.       R0:s,0:s=chol(V0:sTV0:s)R_{0:s,0:s} = \mathrm{chol}(V_{0:s}^{T}V_{0:s})
  22.     else\mathrm{else}
  23.       R0:sk,Wk=R0:sk,0:sk−T(V0:skTWk)R_{0:sk,W_{k}} = R_{0:sk,0:sk}^{-T}(V_{0:sk}^{T}W_{k})
  24.       RWk,Wk=chol(WkTWk−R0:sk,WkTR0:sk,Wk)R_{W_{k},W_{k}} = \mathrm{chol}(W_{k}^{T}W_{k} - R_{0:sk,W_{k}}^{T}R_{0:sk,W_{k}})
  25.     endif\mathrm{endif}
  26.     Computethek-thblockofH_(k)fromRasinpcagmres\mathrm{Compute}\ \mathrm{the}\ k\text{-}th\ \mathrm{block}\ \mathrm{of}\ \underline{H}_{(k)}\ \mathrm{from}\ R\ \mathrm{as}\ \mathrm{in}\ \mathrm{pcagmres}
  27.   end\mathrm{end}
  28.   foro=1,2,…,st\mathrm{for}\ o = 1,2,\ldots,st
  29.     applytheGivensrotationtocolumnoofH_(t−1)andζ\mathrm{apply}\ \mathrm{the}\ \mathrm{Givens}\ \mathrm{rotation}\ \mathrm{to}\ \mathrm{column}\ o\ \mathrm{of}\ \underline{H}_{(t-1)}\ \mathrm{and}\ \zeta
  30.   end\mathrm{end}
  31.   y=H(t−1)−1ζ1:sty = H_{(t-1)}^{-1}\zeta_{1:st}
  32.   z=R0:st−1,0:st−1−1yz = R_{0:st - 1,0:st - 1}^{-1}y
  33.   solvex̂fromKx̂=V0:st−1z\mathrm{solve}\ \hat{x}\ \mathrm{from}\ K\hat{x} = V_{0:st - 1}z
  34.   x(j+1)=x(j)+x̂x^{(j+1)} = x^{(j)} + \hat{x}
  35. end\mathrm{end}

v‾\bar{v} in line 13 is the sksk-th column qskq_{sk} of QQ; only the starting vector of each block is built from VV and RR (corresponding to line 12, vsk+1=qsk+1v_{sk+1} = q_{sk+1}, of the algorithm above). R0:sk,Wk=Q0:skTWkR_{0:sk,W_{k}} = Q_{0:sk}^{T}W_{k} in line 23 is the coefficient of the block classical Gram-Schmidt method, and line 24 is the Cholesky QR of the projected WkW_{k}; RR is extended one block at a time while staying upper triangular. In line 26, k=0k = 0 uses the same formulas as lines 21-22 of the algorithm above, and k>0k > 0 the same formulas as lines 28-32, with C_k=[esk,R0:sk,Wk]\underline{C}_{k} = [e_{sk}, R_{0:sk,W_{k}}] and Rk=RWk,WkR_{k} = R_{W_{k},W_{k}}. H(t−1)H_{(t-1)} in line 31 is the upper triangular matrix obtained by removing the last row of the rotated H_(t−1)\underline{H}_{(t-1)}.

The details of the convergence check, the handling of breakdowns and non-finite values, the returned values and the implementation details are given in “Convergence by Solver” in the API Reference.

8.5 Precision of Orthogonalization and of the Basis

GMRES-type solvers iterate while orthogonalizing the basis of the Krylov subspace. In pgmres and pcagmres, the precision in which the basis is stored and the precision in which orthogonalization is computed can be specified separately (for the syntax see “Calling a Linear Solver” in “Usage”).

In this section, nlocaln_{local} is the local number of rows and mm is the restart length of pgmres (set_restart(m)). ss and tt are the parameters of CA-GMRES(s,t) (pcagmres), specified with set_restart(s, t) (default s=8s = 8, t=4t = 4).

With rounding errors, the orthogonalized basis QQ is not exactly orthogonal. The loss of orthogonality ∥I−QTQ∥\|I - Q^{T}Q\| is determined by the unit roundoff uu of the precision used to compute the orthogonalization and by the condition number κ(V)\kappa(V) of the basis VV before orthogonalization. It is proportional to uκ(V)u\,\kappa(V) for the modified Gram-Schmidt method [8], and to uκ(V)2u\,\kappa(V)^{2} for the classical Gram-Schmidt method [9] and the Cholesky QR method [11]. uu is about 1.1×10−161.1 \times 10^{-16} in double precision, about 6.0×10−86.0 \times 10^{-8} in single precision, and about 4.9×10−44.9 \times 10^{-4} in half precision. The Cholesky QR method fails when uκ(V)2u\,\kappa(V)^{2} approaches 1, because the Gram matrix is then no longer numerically positive definite. In addition, storing the orthogonalized QQ at a lower precision degrades the orthogonality by its rounding (relative uu in each entry of QQ).

The Arnoldi process of pgmres orthogonalizes each new vector against the previously orthogonalized basis, one vector at a time. GMRES with the modified Gram-Schmidt method is backward stable, and orthogonality is lost significantly only after the residual has become sufficiently small [10]. Therefore, even with a low precision for the orthogonalization precision TGS, the iteration proceeds, and the effect appears mainly as a lower limit on the achievable residual (the limit grows with uu).

In pcagmres, orthogonalization has two stages, and ss and tt act on them respectively.

The detection of rank deficiency of the basis (a lucky breakdown) uses a threshold determined from u=max⁡(uTbasis,uTcalcQR)u = \max(u_{Tbasis}, u_{TcalcQR}) (100u100\sqrt{u} for the Cholesky QR method, 1000u1000u otherwise).

The computations on vectors of length nlocaln_{local} (dot products and updates) handled by each argument, and their precisions, are shown below. Note that in pcagmres, the roles of TcalcQR and THessenberg differ depending on whether the orthogonal basis QQ is formed explicitly (set_explicit_q(); Linear Solvers chapter).

Solver Argument Handles Data size
pgmres Tvec (data precision) Storage of the basis vectors nlocal×(m+1)n_{local} \times (m+1)
pgmres TGS Dot products and coefficients of the Gram-Schmidt orthogonalization Dot products of length nlocaln_{local}
pgmres THessenberg Precision in which the solution yy of the least-squares problem (solved on the host) is passed to the device Length mm
pcagmres Tbasis Storage of the basis VV and the orthogonalized basis QQ VV is nlocal×(s+1)n_{local} \times (s+1), QQ is nlocal×(st+1)n_{local} \times (st+1)
pcagmres (when QQ is formed) TcalcQR Computation of the QR factorization within a block (dot products of length nlocaln_{local}) Dot products of length nlocaln_{local}
pcagmres (when QQ is formed) THessenberg Computation of the projection QTVQ^{T}V between blocks (dot products of length nlocaln_{local}) and its subtraction from VV; storage of RR, the projection coefficients and the Hessenberg matrix Dot products of length nlocaln_{local}, (st+1)(s+1)(st+1)(s+1)
pcagmres (CAGMRES_Q_IMPLICIT) TcalcQR Computation of the Gram matrix (all dot products of length nlocaln_{local} within and between blocks) Dot products of length nlocaln_{local}
pcagmres (CAGMRES_Q_IMPLICIT) THessenberg Storage of the Gram matrix, RR and the Hessenberg matrix About (st+1)(s+1)(st+1)(s+1)
pcagmres (CAGMRES_Q_IMPLICIT) Todd_basis, Teven_basis Storage of the odd- and even-numbered vectors of the basis VV nlocal×(st+1)n_{local} \times (st+1) in total

The samples fix TcalcQR and THessenberg to double precision for the following reason. Lowering the precision reduces memory and data movement for the basis (Tbasis), which holds st+1st+1 or more vectors of length nlocaln_{local}. On the other hand, what decides whether orthogonalization succeeds is the computation precision of the orthogonalization within and between blocks (TcalcQR and THessenberg in pcagmres, and TcalcQR in the variant that does not form QQ, CAGMRES_Q_IMPLICIT). These are the precisions in which dot products are accumulated while reading the basis, and raising them does not change the amount of basis data read and written. The stored matrices (RR, the Hessenberg matrix, etc.) are small, about (st+1)(s+1)(st+1)(s+1). Hence the basis alone is lowered to match the data precision, while the orthogonalization computations and the small matrices are kept in double precision. The orthogonality is then preserved to the level determined by the rounding of Tbasis, which stores the basis QQ. The C and Fortran wrapper (capi/wrapper_parcel_sycl.cpp) gives these two with the macro parcel_solver_calc_qr_type (default parcel_double), and the verification sample tests/verify/parcel_krylov_sample_verify.cpp fixes them to parcel_double. TGS and THessenberg of pgmres are both given the data precision (the library default is parcel_double). All 13 representative configurations in “Precision Configurations” use double precision for TcalcQR and THessenberg of pcagmres (including the variant that does not form QQ). Convergence when these are lowered has not been checked.