132
3 Berggren Basis and Completeness Relations
method provides with a tridiagonal matrix, convenient to diagonalize. Theoretically,
Eq. (3.101) provides with orthogonal |V i vectors with real or complex-symmetric
matrices. However, numerically the orthogonality is quickly lost, so that a partial
or full reorthogonalization of Lanczos vectors has to be done. For that reason, the
Lanczos method has been abandoned for total diagonalization of real symmetric
matrices, as other methods are more efficient therein.
The QL method is an iterative method applied to the tridiagonal matrix, obtained
from either the Householder or Lanczos method. It consists of a sequence of
orthogonal transformations applied to the tridiagonal matrix, which makes its offdiagonal matrix elements vanish very quickly. The whole process has a numerical
cost of about 3d 3 multiplications, so that it is tractable up to dimensions of few
thousands typically. No loss of numerical precision has been noticed using the
QL method with complex tridiagonal matrices. However, its convergence is much
slower than in the real symmetric case when both eigenvalues and eigenvectors
are computed (see Fig. 3.7). In fact, it is faster to calculate the eigenvalues of the
tridiagonal complex symmetric matrix obtained using the QL method and their
eigenvectors by inverse iteration if all eigenvalues differ by more than 10 −5 . One
will denote this method by QL in the following.
It has been noticed as well that the tridiagonalization of the full complex
symmetric matrix provided by the Lanczos + full reorthogonalization method,
Time (s)
Matrix dimension
0 100 200 300 400 500 600 700 800 900 1000
10
0
10
-1
10
-2
10
1
Fig. 3.7 Time (in seconds) to diagonalize a random complex symmetric tridiagonal matrix whose
elements are uniformly distributed in [−0.5 : 0.5] for both real and imaginary part with the full
QL method (dashed line with squares) and the QL method for eigenvalues and the shift-and-invert
method for eigenvectors (solid line with filled circles)
3 Berggren Basis and Completeness Relations
method provides with a tridiagonal matrix, convenient to diagonalize. Theoretically,
Eq. (3.101) provides with orthogonal |V i vectors with real or complex-symmetric
matrices. However, numerically the orthogonality is quickly lost, so that a partial
or full reorthogonalization of Lanczos vectors has to be done. For that reason, the
Lanczos method has been abandoned for total diagonalization of real symmetric
matrices, as other methods are more efficient therein.
The QL method is an iterative method applied to the tridiagonal matrix, obtained
from either the Householder or Lanczos method. It consists of a sequence of
orthogonal transformations applied to the tridiagonal matrix, which makes its offdiagonal matrix elements vanish very quickly. The whole process has a numerical
cost of about 3d 3 multiplications, so that it is tractable up to dimensions of few
thousands typically. No loss of numerical precision has been noticed using the
QL method with complex tridiagonal matrices. However, its convergence is much
slower than in the real symmetric case when both eigenvalues and eigenvectors
are computed (see Fig. 3.7). In fact, it is faster to calculate the eigenvalues of the
tridiagonal complex symmetric matrix obtained using the QL method and their
eigenvectors by inverse iteration if all eigenvalues differ by more than 10 −5 . One
will denote this method by QL in the following.
It has been noticed as well that the tridiagonalization of the full complex
symmetric matrix provided by the Lanczos + full reorthogonalization method,
Time (s)
Matrix dimension
0 100 200 300 400 500 600 700 800 900 1000
10
0
10
-1
10
-2
10
1
Fig. 3.7 Time (in seconds) to diagonalize a random complex symmetric tridiagonal matrix whose
elements are uniformly distributed in [−0.5 : 0.5] for both real and imaginary part with the full
QL method (dashed line with squares) and the QL method for eigenvalues and the shift-and-invert
method for eigenvectors (solid line with filled circles)