Towards the next eigenpair in Jacobi-Davidson

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

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

In the non-Hermetian case this strategy will not work as $(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 $Q$ 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 $Q$. Previously we used $\|Au - \theta u\|_2 < \varepsilon$ for a Ritz pair $(\theta, u)$. But if $u$ is a Schur vector it lacks directions of the eigenvector spanned by the columns of $Q$, so the residual will always be large. To remedy this, we inspect the size of the residual with the directions of $Q$ removed:

$\|(I - QQ^*)(Au - \theta u)\|_2 = \|r - Q(Q^*r)\|_2 < \varepsilon$

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

$R \leftarrow \begin{bmatrix}R & z \\ 0 & \theta\end{bmatrix}.$

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