# Why the MIRACLE of Lanczos/CG-like?

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 of zeros). Rather a big miracle when $$A$$ is sparse and $$n = 10^6$$.

In case of non-linear inverse/eigenproblem, 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 understanding why the new direction is "already" orthogonal to the set of all (previous+1) directions. Math is ok, but there is a deep principle behind this thing. It looks like a hidden tridiagonalization process that happens at the same time. Is there an easy way to handle the trick?

• The "miracle" is symmetry -- the Lanczos process (which realizes the A-orthogonalization of the search directions) transforms A into upper Hessenbergform (almost upper triangular with one subdiagonal non-zero). If A is symmetrical, so is the transformed matrix -- which therefore must be tridiagonal and hence all entries except the ones corresponding to the previous direction are zero. – Christian Clason Nov 18 '18 at 13:39
• Yes, you right. Symmetry give the trick... But antisymmetry give also the trick (Skew matrix = A - A'). I simplify my asking, I want the trick for an non-symmetric matrix, hence A = Sym + Skew, maybe there is a way via Sym/Skew decomposition. – sharl Nov 18 '18 at 15:48
• From Hessenberg scheme, Housholder rotation can be generalized in order to tridiagonalized an non-symmetric matrix, using (I - 2uv') instead (I - 2uu') (same as SVD paradigm) and nullified down column and up row at the same time. Tridiag Decomposition is possible via Generalized Housholder (A = UTV', where T is tridiag matrix, U'U=V'V=I). So, I think stupidly the "zeroes trick acceleration" is possible for non-symmetric A matrix – sharl Nov 18 '18 at 16:01
• It's not clear for me, but maybe on the computational point of view, CG = Hessen + Tridiag-QR solving at the same time ? – sharl Nov 18 '18 at 16:28
• You can use other schemes to tridiagonalize, but then you don’t have a similarity transform anymore and lose nice theoretical properties—this is how bicg(stab) works. I recommend looking at the book of Saad on Krylov methods. – Christian Clason Nov 19 '18 at 7:11