Parallel GMRES for solving sparse linear systems
-
$r_0=b-Ax^{(0)}\ is\ the\ initial\ residual,\ \beta:=||r_0||_2,\ v_1:=r_0/\beta$ -
$For\ j=1,2,...,maxiter\ Do:$ -
$\ \ \ \ \ \ \ \ w=Av_j$ % Matrix-vector multiplication -
$\ \ \ \ \ \ \ \ For\ i=1,2,...,j\ Do:$ % Arnoldi Part (MGS) -
$\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ h_{i,j}=dot(v_i,w)$ -
$\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ w=w-h_{i,j}v_i$ -
$\ \ \ \ \ \ \ \ End\ for$ -
$\ \ \ \ \ \ \ \ h_{j+1,j}=||w||_2$ -
$\ \ \ \ \ \ \ \ If\ h_{j+1,j}\ \neq 0\ then:$ -
$\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ v_{j+1}=w/h_{j+1,j}$ -
$\ \ \ \ \ \ \ \ End\ if$ -
$\ \ \ \ \ \ \ \ [H, c, s]=GivensRotate(H, c, s, j)$ % Apply Givens rotations to upper Hessenberg matrix H -
$\ \ \ \ \ \ \ \ Eliminate H(j+1, i)$ -
$\ \ \ \ \ \ \ \ Update\ the\ residual$ -
$\ \ \ \ \ \ \ \ If\ residual < \epsilon\ then:\ break$ -
$End\ for$ -
$Solve\ least-squares\ problem (back\ substitution)$
- matlab/: MATLAB version
- omp/: OpenMP version
- MPI version
- Preconditioner