596 Appendix A
So,uuTis anN×Nmatrix, which can be written as
u 1 uT 0 ··· 0
u 2 uT 0 ··· 0
..
.0··· 0
ui− 1 uT 0 ··· 0
0 ··· 00 ··· 0
..
...
.
..
.
0 ··· 00 ··· 0
(A.124)
from which it is readily seen that multiplication ofS′with the matrixOTi from the
left, zeroes the upperi−2 elements of the right columncof the not yet diagonalised
block inS′. Similarly, multiplying the resulting matrix from the right withOizeroes
thei−2 leftmost elements of theith row, and we arrive at the form (A.121) but
now tridiagonalised one step further.
We still have to solve the eigenvalue problem for the tridiagonalised matrix
obtained in this way. This is rather difficult and we give only an outline of the
procedure. The method consists again of constructing a sequence of matrices which
are successive orthogonal transformations of the original matrix. After some time,
the latter takes on a lower triangular form (or upper triangular, depending on the
transformation) with the eigenvalues appearing on the diagonal. This algorithm is
called theQLorQRalgorithm according to whether one arrives at a lower or upper
tridiagonal form. For tridiagonal matrices, this procedure scales asO(N^2 ).
It is clear that the tridiagonalisation procedure preceding theQR(orQL) step
takesO(m^2 )steps for stagemof the process. Therefore, the procedure as a whole
takesO(N^3 )steps. TheO(N^3 )time complexity makes the diagonalisation of large
matrices very time consuming.
If the matrix is not Hermitian, the Householder method does not work. The
algorithm to be used in that case is the Hessenberg method, which we shall not
discusshere[ 1 ].
Sparse matricesFor diagonalisation problems, we can exploit sparseness of the matrices involved,
just as in the case of linear systems of equations, discussed inAppendix A8.1. An
example of a sparse diagonalisation problem is when we discretise a quantum
Hamiltonian on a cubic grid, leading to a sparse matrix, as we have seen in
Appendix A7.2.
A multiplication of such a matrix with a vector takes onlyO(N)steps. For sparse
matrices like this, there exist special algorithms for solving the eigenvalue problem,
requiring fewer steps than the Householder method, which does not exploit the