# The miracle of the Lanczos/conjugate gradient algorithm

Lanczos/Arnoldi/Rietz/CG-like algorithm share the same core strategy... In each, a little miracle appears, most of the Gram-Schmidt inner products are zeroes ! In others words, new direction need only get orthonormalized with the one previous updated search direction (or two in lanczos case), no need to check other previous directions (because zeros). Rather a big miracle when A is sparse and n = 10^6.

In case of non-linear inverse or eigen problem, this property is not true, but depending of the "nonlinearity rate", the values could be small and easily neglected or threshold since the iterative nature of the algorithm assumed that the residual must decrease in each step. So this property remains useful.

Any suggestions are welcome for understand why the new direction is "already" orthogonal to the set of all previous+1 (or +2) directions. Math is ok, but there is a deep principle behind this thing. It look like a hidden bi or tridiagonalization process that happen at the same time. Is there an easy way to handle the trick ?

The Lanczos iteration builds an orthogonal basis $$\left(q_i\right)$$ for the nested Krylov subspaces, given some matrix $$A$$ and vector $$b$$. For $$i > j + 1$$ you get: $$q_i^T A q_j = 0$$
since $$q_j \in \mathcal{K}_j$$, so $$Aq_j \in \mathcal{K}_{j+1}$$ and $$q_i$$ is orthogonal to $$\mathcal{K}_{j+1}$$ since $$i > j + 1$$. So the matrix $$Q_k^T A Q_k = H_k$$ is lower-Hessenberg, where $$Q_k = \left(q_1, \ldots, q_k \right)$$. When $$A$$ is symmetric, then so is $$H_k$$ which is therefore tridiagonal. Summarizing, what makes it work is:
1. the fact that we're building an orthogonal basis for Krylov subspaces, which are all related by applying $$A$$
2. the fact that $$A$$ is symmetric