3
$\begingroup$

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?

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ 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. $\endgroup$
    – Christian Clason
    Nov 18, 2018 at 13:39
  • $\begingroup$ 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. $\endgroup$
    – sharl
    Nov 18, 2018 at 15:48
  • $\begingroup$ 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 $\endgroup$
    – sharl
    Nov 18, 2018 at 16:01
  • $\begingroup$ It's not clear for me, but maybe on the computational point of view, CG = Hessen + Tridiag-QR solving at the same time ? $\endgroup$
    – sharl
    Nov 18, 2018 at 16:28
  • 1
    $\begingroup$ 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. $\endgroup$
    – Christian Clason
    Nov 19, 2018 at 7:11

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.