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

11 QR Factorization

This chapter describes the QR factorization algorithms (orthogonalization of a set of vectors) used in this library. In the linear solvers, the algorithm is selected by passing one of the following constants to set_qr_algo(). The notation follows the conventions given at the beginning of the Linear Solvers chapter.

Constant Method Available solvers
parcel::qr::QR_CGS (0) Classical Gram-Schmidt method pgmres, pcagmres (except CAGMRES_Q_IMPLICIT)
parcel::qr::QR_MGS (1) Modified Gram-Schmidt method pgmres, pcagmres (except CAGMRES_Q_IMPLICIT)
parcel::qr::QR_CHOLESKYQR (2) Cholesky QR method pcagmres
parcel::qr::QR_CAGMRES_CHOLESKYQR (202) Cholesky QR method by the moment method (only for symmetric matrices without preconditioning) pcagmres (only with CAGMRES_Q_IMPLICIT)

Passing a value that the solver does not support to set_qr_algo() throws std::invalid_argument. The combination with how pcagmres forms QQ (set_explicit_q()) is checked at the entry of solver() (Linear Solvers chapter).

CGS2, which repeats the classical Gram-Schmidt method twice, is used within the Arnoldi process of the Krylov-Schur method (ks_arnoldi) (in ks_arnoldi, set_qr_algo(parcel::qr::QR_CGS) means CGS2, which is the default; QR_CGS of pgmres and pcagmres applies the classical Gram-Schmidt method only once, so CGS2 cannot be selected for these two solvers). The algorithms below orthogonalize V=[v1,…,vp]V = [v_1, \ldots, v_p], consisting of pp vectors, to obtain QQ with columns qiq_i and an upper triangular matrix RR (entries Rk,iR_{k,i}).


11.1 Classical Gram-Schmidt Method [1]

QR factorization by Gram-Schmidt orthogonalization. Since the inner products for the ii-th column can be computed together, it requires few collective communications and offers high parallelism, but the loss of orthogonality grows in proportion to the square of the condition number of the matrix. QR_CGS does not reorthogonalize (a single pass only).

  1. fori=1,…,p\mathrm{for}\ i = 1,\ldots,p
  2.   fork=1,…,i−1\mathrm{for}\ k = 1,\ldots,i - 1
  3.     Rk,i=⟨qk,vi⟩R_{k,i} = \langle q_{k},v_{i} \rangle
  4.   end\mathrm{end}
  5.   fork=1,…,i−1\mathrm{for}\ k = 1,\ldots,i - 1
  6.     vi=vi−Rk,iqkv_{i} = v_{i} - R_{k,i}q_{k}
  7.   end\mathrm{end}
  8.   Ri,i=∥vi∥R_{i,i} = \|v_{i}\|
  9.   qi=vi/Ri,iq_{i} = v_{i}\ /\ R_{i,i}
  10. end\mathrm{end}


11.2 Modified Gram-Schmidt Method [1]

A QR factorization that modifies the classical Gram-Schmidt algorithm to reduce errors. Since the already orthogonalized components are subtracted one at a time before the next inner product is computed, it gives better orthogonality than the classical Gram-Schmidt method, but requires a collective communication for each inner product.

  1. fori=1,…,p\mathrm{for}\ i = 1,\ldots,p
  2.   fork=1,…,i−1\mathrm{for}\ k = 1,\ldots,i - 1
  3.     Rk,i=⟨qk,vi⟩R_{k,i} = \langle q_{k},v_{i} \rangle
  4.     vi=vi−Rk,iqkv_{i} = v_{i} - R_{k,i}q_{k}
  5.   end\mathrm{end}
  6.   Ri,i=∥vi∥R_{i,i} = \|v_{i}\|
  7.   qi=vi/Ri,iq_{i} = v_{i}\ /\ R_{i,i}
  8. end\mathrm{end}


11.3 Classical Gram-Schmidt Method with Reorthogonalization (CGS2) [6]

This method repeats the orthogonalization of the classical Gram-Schmidt method once more. Since the second pass removes the components in the directions q1,…,qi−1q_1, \ldots, q_{i-1} left by rounding errors in the first pass, the loss of orthogonality is kept at the level of machine precision as long as the numerical rank of VV has not dropped (“twice is enough”). The amount of computation for inner products and updates is twice that of the classical Gram-Schmidt method, but since the inner products of each pass can be computed together, only two collective communications per column are needed, fewer than the i−1i - 1 of the modified Gram-Schmidt method.

The Arnoldi process of the Krylov-Schur method (ks_arnoldi) uses this method by default. At each Arnoldi step, the new basis vector is orthogonalized against the existing basis. The Krylov-Schur method assumes that the orthogonality of the basis is preserved across restarts; if orthogonality is lost, spurious eigenvalues (ghost eigenvalues) appear for repeated eigenvalues. CGS2 prevents this.

  1. R1:i−1,i=0R_{1:i - 1,i} = 0
  2. forpass=1,2\mathrm{for}\ pass = 1,2
  3.   ξ=Q1:i−1Tvi\xi = Q_{1:i - 1}^{T}v_{i}
  4.   vi=vi−Q1:i−1ξv_{i} = v_{i} - Q_{1:i - 1}\xi
  5.   R1:i−1,i=R1:i−1,i+ξR_{1:i - 1,i} = R_{1:i - 1,i} + \xi
  6. end\mathrm{end}
  7. Ri,i=∥vi∥R_{i,i} = \|v_{i}\|
  8. qi=vi/Ri,iq_{i} = v_{i}\ /\ R_{i,i}


11.4 Cholesky QR Method [7]

Cholesky QR is a QR factorization consisting of a matrix product and a Cholesky factorization. It has high arithmetic intensity and can be computed with a single collective communication, but the loss of orthogonality grows in proportion to the square of the condition number of the matrix. PARCEL performs it only once; the repeated variant (CholeskyQR2) is not implemented. The Gram matrix is computed on the device, and the Cholesky factorization is performed on the host.

  1. G=VTVG = V^{T}V
  2. ComputeRfromG=RTR(Choleskydecomposition)\mathrm{Compute}\ R\ \mathrm{from}\ G = R^{T}R\ (\mathrm{Cholesky}\ \mathrm{decomposition})
  3. Q=VR−1Q = VR^{-1}



11.5 Cholesky QR Method by the Moment Method (QR_CAGMRES_CHOLESKYQR)

This is a Cholesky QR method specific to CA-GMRES, used only for the first block (k=0k = 0) when pcagmres does not form QQ (CAGMRES_Q_IMPLICIT; Linear Solvers chapter). For the monomial basis without preconditioning, vi=Aiv0v_{i} = A^{i}v_{0} (i=0,…,si = 0,\ldots,s), if AA is symmetric then ⟨vi,vj⟩=v0TAi+jv0=μi+j\langle v_{i},v_{j} \rangle = v_{0}^{T}A^{i+j}v_{0} = \mu_{i+j} (the moments), and the Gram matrix G=VTVG = V^{T}V is a Hankel matrix (Gij=μi+jG_{ij} = \mu_{i+j}). μ0,…,μ2s\mu_{0},\ldots,\mu_{2s} are obtained from the 4×(s/2+1)4 \times (s/2+1) dot products of the four vectors [v0,v1,vs−1,vs][v_{0},v_{1},v_{s-1},v_{s}] with the even-numbered basis vectors [v0,v2,…,vs][v_{0},v_{2},\ldots,v_{s}], so the (s+1)2(s+1)^{2} dot products need not be computed. QQ is not formed; only RR is returned.

V=[v0,…,vs]V = [v_{0},\ldots,v_{s}] (ss is an even number of 2 or more).

  1. C=[v0,v1,vs−1,vs]T[v0,v2,…,vs]C = [v_{0},v_{1},v_{s-1},v_{s}]^{T}[v_{0},v_{2},\ldots,v_{s}]
  2. Setμ0,…,μ2sfromC\mathrm{Set}\ \mu_{0},\ldots,\mu_{2s}\ \mathrm{from}\ C
  3. Gij=μi+j(0≤i,j≤s)G_{ij} = \mu_{i+j}\ \ (0 \leq i,j \leq s)
  4. ComputeRfromG=RTR(Choleskydecomposition)\mathrm{Compute}\ R\ \mathrm{from}\ G = R^{T}R\ (\mathrm{Cholesky}\ \mathrm{decomposition})

The matrix product in line 1 is computed on the device, and with MPI the local values are reduced (one collective communication). The Cholesky factorization is performed on the host. If AA is not symmetric, or for a preconditioned basis, GG is not a Hankel matrix and RR is wrong. pcagmres checks at the entry that there is no preconditioning and that ss is even, but does not check the symmetry of AA.