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: (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 (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 , consisting of vectors, to obtain with columns and an upper triangular matrix (entries ).
11.1 Classical Gram-Schmidt Method [1]
QR factorization by Gram-Schmidt orthogonalization. Since the inner products for the -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).
- Algorithm
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.
- Algorithm
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 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 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 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.
- Algorithm (column )
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.
- Algorithm
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 () when pcagmres does not form (CAGMRES_Q_IMPLICIT; Linear Solvers chapter). For the monomial basis without preconditioning, (), if is symmetric then (the moments), and the Gram matrix is a Hankel matrix (). are obtained from the dot products of the four vectors with the even-numbered basis vectors , so the dot products need not be computed. is not formed; only is returned.
- Algorithm
( is an even number of 2 or more).
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 is not symmetric, or for a preconditioned basis, is not a Hankel matrix and is wrong. pcagmres checks at the entry that there is no preconditioning and that is even, but does not check the symmetry of .