Restarted and block eigensolvers — Examples

Every projected $H_2=V_2^{\ast }A{V}_2$ in this example is Hermitian because $A^{\ast }=A$, so the supplied two-dimensional solver returns valid complete projected data in finite exact work. By [F1], $q(A)v=(-19e_1-9e_2+e_3)\mathrm{/}(10\sqrt{3})$. The squared component weights are proportional to $361,81,1$, so the Rayleigh quotient of the restarted vector is $(1\cdot 361+2\cdot 81+3\cdot 1)\mathrm{/}(361+81+1)=526\mathrm{/}443<2$, whereas the initial quotient is $(1+2+3)\mathrm{/}3=2$. The wanted component-to-$e_1$ component ratio falls from 1 to 1/19.

Repeating the same exact restart multiplies the $e_3$ component by $q(3)=1\mathrm{/}10$ and the $e_1$ component by $q(1)=-19\mathrm{/}10$ at every cycle. Hence after $t$ cycles their magnitude ratio is $(1\mathrm{/}19{)}^t$, which tends to zero. This shift choice suppresses the wanted eigendirection and gives no general convergence claim.

For each finite $t$, the restart vector is proportional to $q(A{)}^{t}v$, with all coordinates nonzero because none of $q(1),q(2),q(3)$ vanishes. If a Ritz residual were zero, its lifted vector would satisfy $Au=\theta u$; the diagonal equations $({\lambda }_i-\theta )u_i=0$ and distinct ${\lambda }_i$ force $u$ to be proportional to some $e_i$. No $e_i$ lies in $K_2(A,q(A{)}^{t}v)$: representing one would require $c+d{\lambda }_j=0$ for the other two distinct eigenvalues, hence $c=d=0$. Also $q(A{)}^{t}v,Aq(A{)}^{t}v,A^{2}q(A{)}^{t}v$ are independent because their coordinate determinant is the product of the three nonzero coordinates and the Vandermonde determinant for $1,2,3$. Thus no pair is accepted at tolerance zero and the space is not invariant before each scheduled restart.

In a separate boundary run with shift $\mu =3$, the filter has $q(3)=0$ and $q(A)v=(-2e_1-e_2)\mathrm{/}\sqrt{3}$, so the wanted $e_3$ component is removed exactly in one filtering step. The filtered vector is still nonzero, so this is not filtered breakdown; it is a shift-selection failure.

The vectors are orthonormal and have disjoint coordinate supports. Their initial Rayleigh quotients are ${\theta }_1=(99+5)\mathrm{/}100=26\mathrm{/}25$ and ${\theta }_2=((101\mathrm{/}100)99+9)\mathrm{/}100=10899\mathrm{/}10000$. Each $x_i$ has two nonzero coordinates associated with distinct diagonal entries of $A$, so $r_i=(A-{\theta }_{i}I)x_i\mathrm{\ne }0$; also $x_i^{\ast }{r}_i=x_i^{\ast }A{x}_i-{\theta }_i{x}_i^{\ast }{x}_i=0$, and $r_i$ lies in the same two-coordinate plane as $x_i$. Thus $x_i,r_i$ are independent in that plane, and the disjoint planes make $[X,R]$ rank four.

Since $T=I$, $W=R$ and the first trial space is all of ${\mathbb{C}}^4$. Its Rayleigh-Ritz values are exactly $1,101\mathrm{/}100,5,9$, and the selected block is $\mathrm{span}(e_1,e_2)$. The update is successful because the trial rank is four; the returned residuals are zero, so the algorithm returns converged. In particular, $1\le 26\mathrm{/}25$ and $101\mathrm{/}100\le 10899\mathrm{/}10000$, as required by [F2].

For $U=\mathrm{span}(e_1,e_2)$, every unit vector in $S=\mathrm{span}(x_1,x_2)$ has squared norm $1\mathrm{/}100$ in $U^{\perp }$, so ${\sin }^2\vartheta =1\mathrm{/}100$. The strict gap $101\mathrm{/}100<5$ holds, and [F3] gives ${\theta }_2(S)\le 101\mathrm{/}100+(9-101\mathrm{/}100)\mathrm{/}100=10899\mathrm{/}10000$, attained by the computed ${\theta }_2$. The block captures both clustered modes; a one-dimensional trial space cannot contain this two-dimensional invariant subspace.

Here $M=\mathrm{diag}(-14\mathrm{/}5,1\mathrm{/}5,26\mathrm{/}5)$ and $M^{-1}=\mathrm{diag}(-5\mathrm{/}14,5,5\mathrm{/}26)$. Thus the interior mode 4 maps to $\theta =5$, whose modulus exceeds the other transformed eigenvalue moduli $5\mathrm{/}14$ and $5\mathrm{/}26$; $19\mathrm{/}5+1\mathrm{/}5=4$. In the separate harmonic invocation, $W=MU=e_2\mathrm{/}5$, so $G=W^{\ast }W=1\mathrm{/}25$ and $C=W^{\ast }U=1\mathrm{/}5$. The QZ input is this regular one-by-one pencil, already upper triangular with a nonzero diagonal pair, so the QZ procedure's computed condition holds and its status is qz-computed; $(\alpha ,\beta )=(1\mathrm{/}25,1\mathrm{/}5)$. The scalar equation $G-\eta C=0$ gives $\eta =1\mathrm{/}5$ and the same value $\sigma +\eta =4$.

For an inexact solve take $y=(49\mathrm{/}10)e_2$ and $\theta =49\mathrm{/}10$. Then $s_0=My-u=-e_2\mathrm{/}50$ and $r_T=0$, while the mapped value is $\lambda =19\mathrm{/}5+10\mathrm{/}49=981\mathrm{/}245$. Its original residual is $(A-\lambda I)u=-e_2\mathrm{/}245$, which equals ${\theta }^{-1}(s_0-M{r}_T)=-e_2\mathrm{/}245$ by [F4].