Towards the next eigenpair in Jacobi-Davidson

After removing a converged Ritz vector from the search space, we must ensure that new expansions do not bring it back. In practice this means updating the correction equation so that these directions are deflated.

June 3, 2017 - 5 minute read -
gsoc julia

In the Hermetian case it is very easy to find the next approximate eigenpair once another is converged. We simply require our correction tt to be orthogonal not only to uu, but as well to all previously converged Ritz vectors. If XX contains the converged Ritz vectors, define the orthonormal matrix Q=[X,u]Q = [X, u], so that (IQQ)(I - QQ^*) is a projection. Our new correction equation will then be

(IQQ)A(IQQ)t=r and tu. (I - QQ^*)A(I - QQ^*)t = -r \text{ and } t \perp u.

In the non-Hermetian case this strategy will not work as (IQQ)(I - QQ^*) will fail to be a projection if the Ritz vectors are not orthogonal. So what can we do?

The non-Hermetian case

To fix this problem, we simply change our goal somewhat. Rather than computing and storing eigenvectors, we compute Schur vectors, so that we can guarantee orthonormality of QQ and therefore use the new correction equation.

However, if we choose to work with Schur vectors rather than eigenvectors, we must also come up with a new convergence criterion. Suppose the converged Schur vectors are stored in QQ. Previously we used Auθu2<ε\|Au - \theta u\|_2 < \varepsilon for a Ritz pair (θ,u)(\theta, u). But if uu is a Schur vector it lacks directions of the eigenvector spanned by the columns of QQ, so the residual will always be large. To remedy this, we inspect the size of the residual with the directions of QQ removed:

(IQQ)(Auθu)2=rQ(Qr)2<ε \|(I - QQ^*)(Au - \theta u)\|_2 = \|r - Q(Q^*r)\|_2 < \varepsilon

When a few Schur vectors are converged we get a decomposition AQ=QRAQ = QR with RR upper triangular and QQ unitary. The next converged Schur vector uu is appended to QQ as Q[Qu]Q \leftarrow \begin{bmatrix}Q & u\end{bmatrix}. Updating RR is easy as well, as it must be of the form

R[Rz0θ]. R \leftarrow \begin{bmatrix}R & z \\ 0 & \theta\end{bmatrix}.

Equating AQ=QRAQ = QR implies Qz=rQz = r, so therefore z:=Qrz := Q^*r. Note that this quantity is already computed when we validate the convergence criterion.