Next: Algorithm
Up: Band Lanczos Method
Previous: The Need for Deflation
  Contents
  Index
Basic Properties
After the first
iterations, the band Lanczos algorithm has
generated the first
Lanczos vectors (4.28).
These vectors are constructed to be orthonormal:
![\begin{displaymath}
V_j^{\ast} V_j = I_j,\quad \mbox{where}\quad
V_j = \left[ \begin{array}{cccc}
v_1 & v_2 & \cdots & v_j
\end{array} \right].
\end{displaymath}](img1126.png) |
(38) |
Here,
denotes the
identity matrix.
In addition to (4.28), the algorithm has constructed
the vectors
![\begin{displaymath}
\hat{v}_{j+1},\hat{v}_{j+2},\ldots,\hat{v}_{j+p_c},
\end{displaymath}](img1129.png) |
(39) |
which are the candidates for the next
Lanczos vectors,
.
Here,
is the number of starting vectors,
, minus
the number of deflations that have occurred during the first
iterations.
The vectors (4.30) are constructed so that they
satisfy the orthogonality relations
![\begin{displaymath}
V_j^{\ast} \hat{v}_{k} = 0 \quad \mbox{for all} \quad
k=j+1,j+2,\ldots,j+p_c.
\end{displaymath}](img1132.png) |
(40) |
The band Lanczos algorithm has a very simple built-in deflation
procedure based on the vectors (4.30).
In fact, an exact deflation at iteration
is equivalent
to
.
Therefore, in the algorithm, one checks if
is smaller than some suitable deflation tolerance.
If yes, the vector
is deflated and
is
reduced by 1.
Otherwise,
is normalized to become the next
Lanczos vector
.
The recurrences that are used in the algorithm to generate the
vectors (4.28) and (4.30) can be summarized
compactly as follows:
![\begin{displaymath}
A V_j = V_j T_j + \left[ \begin{array}{ccccccc}
0 & \cdots ...
...hat{v}_{j+p_c}
\end{array} \right]
+ \hat{V}_j^{\rm {(dl)}}.
\end{displaymath}](img1137.png) |
(41) |
Here,
is a
matrix whose entries are
chosen so that the orthogonality conditions (4.29)
and (4.31) are satisfied.
The matrix
in (4.32) contains
mostly zero columns, together with the unnormalized
vectors that have been
deflated during the first
iterations.
Recall that
is the number of deflated vectors.
It turns out that orthogonality only has to be explicitly enforced
among
consecutive Lanczos vectors and, once deflation has
occurred, against
fixed earlier vectors.
As a result, the matrix
is ``essentially'' banded with
bandwidth
, where the bandwidth is reduced by 2 every time a
deflation occurs.
In addition, each inexact deflation causes
to have nonzero elements
in a fixed row outside and to the right of the banded part.
More precisely, the row index of each such row caused by deflation
is given by
, where
is the number of
the iteration at which the deflation has occurred and
is the
corresponding value of
at that iteration.
The matrix
can thus be written as
![\begin{displaymath}
T_j = T_j^{\rm {(b)}} + T_j^{\rm {(d)}},
\end{displaymath}](img1143.png) |
(42) |
where
is a banded matrix and
contains the horizontal ``spikes'' outside the band of
due to
deflation.
In particular, if no inexact deflation has occurred, then
is the zero matrix.
Finally, we note that the banded part
of
is
a Hermitian matrix.
For example, consider the case of
starting vectors and
assume that during the first
iterations, deflations
have occurred at steps
,
, and
.
These three deflations correspond to deleting the vectors
,
, and
, as well as the following
-multiples
of these three vectors, from the block Krylov sequence (4.27).
In this case, the matrix
has the following sparsity structure:
![\begin{displaymath}
T_{15} = %%\footnotesize{
\left[ \begin{array}{ccccccccccccc...
... \\
& & & & & & & & & & & &{*}&{*}&{*}
\end{array} \right].
\end{displaymath}](img1155.png) |
(43) |
Here, the
's denote potentially nonzero entries within
the banded part,
, and the
's denote
potentially nonzero entries of
due to the deflations at iterations
,
, and
.
Note that the three deflations have reduced the initial
bandwidth
to
at iteration
.
After
iterations of the band Lanczos algorithm,
approximate eigensolutions for the Hermitian
eigenvalue problem (4.25) are obtained by
computing eigensolutions of
,
Here,
is the projection of
onto the space spanned by the Lanczos basis matrix
, i.e.,
![\begin{displaymath}
T_j^{\rm {(pr)}} = V_j^{\ast} A V_j.
\end{displaymath}](img1164.png) |
(44) |
Each value
and its Ritz vector,
, yield an approximate eigenpair of
.
Of course, the matrix
is not computed via
its definition (4.35).
Instead, we use the formula
![\begin{displaymath}
T_j^{\rm {(pr)}} = T_j + \left(T_j^{\rm {(d)}}\right)^{\ast}.
\end{displaymath}](img1166.png) |
(45) |
By (4.36), we only have to conjugate and
transpose the part of
outside its banded part and add it to
in order to obtain
.
To show that (4.36) indeed holds true, note that
by multiplying (4.32) from the
left by
and by using the orthogonality
relations (4.29) and (4.31), we get
![\begin{displaymath}
T_j^{\rm {(pr)}} = V_j^{\ast} A V_j = T_j + S_j, \quad \mbox{where} \quad
S_j = V_j^{\ast} \hat{V}_j^{\rm {(dl)}}.
\end{displaymath}](img1168.png) |
(46) |
Since the matrices
and
are
both Hermitian, it follows from (4.33) that
in (4.37).
Thus (4.37) reduces to (4.36).
For example, for
in (4.34) the associated
matrix
is of the form
![\begin{displaymath}
T_{15}^{\rm {(pr)}} = %%\footnotesize{
\left[ \begin{array}{...
... &
&\overline{{\tt d}}& & &{*}&{*}&{*}
\end{array} \right].
\end{displaymath}](img1172.png) |
(47) |
Here, the
's below the banded
part were obtained by conjugating and transposing the corresponding
entries above the banded part in (4.34).
We remark that, in (4.38), the entries
and
outside the banded part are usually small.
More precisely, if the deflation criterion (4.42)
below is used, then the absolute values of all
's and
's is bounded by the deflation
tolerance
.
Even though these entries are small, setting them to zero
would introduce unnecessary errors.
Indeed, the projection property (4.35) for
holds true only if all entries
and
outside the banded part are included in
.
Finally, we note that the band Lanczos
algorithm terminates as soon as
is reached.
This means that
deflations have occurred, and thus the
block Krylov sequence is exhausted.
At termination due to
, the relation (4.32)
for the Lanczos vectors reduces to
![\begin{displaymath}
A V_j = V_j T_j + \hat{V}_j^{\rm {(dl)}}.
\end{displaymath}](img1177.png) |
(48) |
Using (4.37), we can rewrite (4.39) as
follows:
![\begin{displaymath}
A V_j - V_j T_j^{\rm {(pr)}} =
\left(I - V_j V_j^{\ast} \right) \hat{V}_j^{\rm {(dl)}}.
\end{displaymath}](img1178.png) |
(49) |
Now let
and
be any of the eigenpairs
of
, and assume that
is normalized
so that
.
Recall that the pair
and
is used as an approximate eigensolution of
.
By multiplying (4.40) from the right by
and taking norms, it follows that the residual of the
approximate eigensolution
and
can be bounded as follows:
![\begin{displaymath}
\left\Vert A x_i^{(j)} - \theta_i^{(j)} x_i^{(j)} \right\Ver...
...ert _2
\leq \left\Vert \hat{V}_j^{\rm {(dl)}} \right\Vert _2.
\end{displaymath}](img1181.png) |
(50) |
In particular, if only exact deflation is performed, then
and (4.41) shows that
each eigenvalue
of
is indeed an eigenvalue of
.
For general deflation,
, however,
is of the order
of the deflation tolerance.
More precisely, if the deflation check (4.42) below
is used, then
where
denotes the deflation tolerance.
Next: Algorithm
Up: Band Lanczos Method
Previous: The Need for Deflation
  Contents
  Index
Susan Blackford
2000-11-20