GMRES.md

Previously, we introduce several iterative algorims to solve the linear equation Ax = b, where A is n x n symmetric matrix. What if A is non-symmetric matrix? To address the issue, we apply the generalized minimal residual method (GMRES), which will be introduced in the following.

The basic idea of GMRES is to construct the approximate solution , where . Note that is the k-dimension Krylov subspace, is the initial guess, and is the initial residual.

Change Target Function

Recall that our goal is to find the solution that minimizes the residual, shown as follow:

Let , where is k x k unitary matrix and can be computed by using Arnoldi iteration.

Therefore, we can rewrite the function to be minimized as:

,

where (a) equation holds since

,

(b) equation holds according to the Arnoldi equation ,

(c) equation holds since is the first column of (k+1) x (k+1) identity matrix,

and (d) equation holds since is orthonormal.

Algorithm

In summary, the algorithm is shown as follow

At k-th iteration:

1. Compute using Arnoldi iteration;
2. Find that minimizes ;
3. Form the solution ;

Solve Least Square Problem

In the following, let us take a close look at the detailed implemention of how to find that minimizes .

To solve the least square problem

,

we adopt QR decomposition, shwon as follow

,

where is (k+1) x (k+1) orthogonal matrix and is (k+1) x k upper triangular matrix.

The difficulty is that we expect to update the decomposition of cheaply at each step of Arnoldi iteration. That is,

,

where . This implies that we add a new column and a new row at each step.

To proceed, we apply Given rotations.

Let represent the rotation matrix, shown as

.

At next step, we premultiply to the new column and get the rotationed column . Append the rotationed column and to previous , we have a almost triangular matrix

.

In order to get a triangular matrix , premultiply by :

where ,

,

and

.

Therefore, let us look at the QR decomposition again. We find that is the acumulated product of the rotation matrices and is unitary.

Finally, we can rewrite the target function as:

,

where .

The that minimizes the target function is .