Conjugate Gradients Version 1

Let’s use a different norm compared to the previous derivation. This will only apply to matrices $A$ that are symmetric positive definite.

We will consider the $A$-norm:

$$\begin{array}{c}\Vert x-x^{(k)}{\Vert }_A\\ \Vert z{\Vert }_A=\sqrt{z^{T}Az}\end{array}$$

If $A$ is symmetric positive definite, then this is a norm.

If we look for a solution that minimizes that norm in the Krylov subspace we obtain a simple equation:

$$\Vert x-x^{(k)}{\Vert }_A^2=(x-Q_{k}y{)}^{T}A(x-Q_{k}y)$$

The solution minimizes

$$y^T{Q}_k^{T}A{Q}_{k}y-2b^T{Q}_{k}y+b^{T}x$$

We can prove that the solution is

$$(Q_k^{T}A{Q}_k)y_k=Q_k^{T}b$$

We recognize $Q_k^{T}A{Q}_k$ from Lanczos. This is the same matrix. We project $A$ using $Q_k$ and solve the resulting $k\times k$ system.

Proof. The function to minimize is

$$\begin{array}{rl}\Vert x-x^{(k)}{\Vert }_A^2& =(x-Q_{k}y{)}^{T}A(x-Q_{k}y)\\ & =(A^{1/2}x-A^{1/2}{Q}_{k}y{)}^T(A^{1/2}x-A^{1/2}{Q}_{k}y)\\ & =\Vert A^{1/2}x-A^{1/2}{Q}_{k}y{\Vert }_2^2\end{array}$$

Using our previous reasoning for least-squares, we find that

$$A^{1/2}x-A^{1/2}{Q}_k{y}_k\perp A^{1/2}{Q}_k$$

$Q_k^T{A}^{1/2}(A^{1/2}x-A^{1/2}{Q}_k{y}_k)=0$

$Q_k^{T}Ax-Q^{T}A{Q}_k{y}_k=0$

$(Q_k^{T}A{Q}_k)y_k=Q_k^{T}b$ $\square$

The final equation is:

$$(Q_k^{T}A{Q}_k)y_k=Q_k^{T}b$$

Because we are using the $\Vert {\Vert }_A$ norm, we are able to get rid of $x$ and have $b$ instead.

This leads to:

Conjugate gradients: version 1 §

1. Compute $Q_k$ using Lanczos.
2. $(Q_k^{T}A{Q}_k)y_k=Q_k^{T}b=\Vert b{\Vert }_2{e}_1.$
3. $x^{(k)}=Q_k{y}_k.$

• Space cost: $O(kn).$ This is required because of the last step $Q_k{y}_k$ which requires saving $Q_k$.
• Time cost: $O(k\mathrm{nnz}+kn).$

This process can be made much more efficient. In particular, the space cost can be reduced to $O(n)$. The time cost can be reduced as well but will remain $O(k\mathrm{nnz}+kn).$

But it takes some insight to make it happen.