Finite-budget block LOBPCG for a Hermitian-definite pencil with explicit rank-loss status

Let $A=A^{\ast }\in {\mathbb{C}}^{n\times n}$, let $B=B^{\ast }>0$, and let $T=T^{\ast }>0$ be a fixed preconditioning operator. Here $B>0$ and $T>0$ mean $x^{\ast }Bx>0$ and $x^{\ast }Tx>0$ for every nonzero $x$. The $B$-inner product and norm are those of The B-inner product, B-norm, and dual residual norm. Choose a block width $1\le q\le n$, a residual tolerance $\tau \ge 0$, a finite iteration budget $N_{\max }\ge 0$, and an input matrix $X_0\in {\mathbb{C}}^{n\times q}$. The output is a block of Ritz pairs and one of converged, budget-exhausted, rank-loss, or invalid-initial-block.

1. If $X_0$ does not have full column rank or does not satisfy $X_0^{\ast }B{X}_0=I_q$, return invalid-initial-block. Diagonalize the Hermitian compression $X_0^{\ast }A{X}_0=Z_0{\mathrm{\Theta }}_0{Z}_0^{\ast }$ with $Z_0$ unitary and the $q$ Ritz values in increasing order, then replace $X_0$ by $X_0{Z}_0$. Thus the columns used in the first residual block are the actual B-orthonormal Ritz vectors paired with the diagonal entries of ${\mathrm{\Theta }}_0$. Set the previous search block $D_0$ empty and initialize the iteration counter $k=0$.

2. At iteration $k$, form the original residual block $R_k=A{X}_k-B{X}_k{\mathrm{\Theta }}_k$. If every column has Euclidean norm at most $\tau$, return converged. If $k=N_{\max }$, return budget-exhausted with $({\mathrm{\Theta }}_k,X_k)$.

3. Compute the preconditioned residual block $W_k=T{R}_k$ and set $Y_k=[X_k,W_k,D_k]$, omitting the empty block at $k=0$. Compute an exact rank-revealing $B$-QR with column pivoting as follows. Starting with no columns in $Q_k$, for each remaining column $y_j$ of $Y_k$ compute its residual $c_j=y_j-Q_k(Q_k^{\ast }B{y}_j)$ and choose a column with largest $B$-norm $\mathrm{\parallel }{c}_j{\mathrm{\parallel }}_B$ (break ties by original column order). If the largest residual norm is zero, stop; otherwise append the normalized residual to $Q_k$ and remove that pivot column. Let $s_k$ be the number of columns appended and let ${\mathrm{\Pi }}_k$ record the pivot order followed by the unused columns. If $s_k<q$, return rank-loss with the current Ritz pairs; no projected solve is attempted on that branch. Otherwise set $S_k=Q_k^{\ast }B{Y}_k{\mathrm{\Pi }}_k(:,1:s_k)\mathrm{.}$ The pivot construction gives $Y_k{\mathrm{\Pi }}_k(:,1:s_k)=Q_k{S}_k,Q_k^{\ast }B{Q}_k=I_{s_k},$ and $S_k$ is invertible because its selected columns are independent. Dependent trial columns are discarded and their count is recorded as a rank-compression diagnostic.

4. The projected matrix $Q_k^{\ast }A{Q}_k$ is Hermitian, hence normal, so its orthonormal eigenbasis and real eigenvalues are supplied by Complex spectral theorem: a normal endomorphism of a finite-dimensional complex inner product space has an orthonormal eigenbasis, and conversely. Solve $Q_k^{\ast }A{Q}_k{Z}_k=Z_k{\mathrm{\Theta }}_{k+1}$ and choose its $q$ smallest eigenvalues. Set $C_k={\mathrm{\Pi }}_k(:,1:s_k)S_k^{-1}{Z}_k$; then $Y_k{C}_k=Q_k{Z}_k$. Partition $C_k=\left[\begin{array}{c}{C}_X\\ C_W\\ C_D\end{array}\right]$, omitting the $C_D$ block when $D_k$ is empty. The projected metric is positive definite because for nonzero $z$, $(Q_{k}z{)}^{\ast }B(Q_{k}z)=\mathrm{\parallel }z{\mathrm{\parallel }}_2^2>0$. Set $X_{k+1}=X_k{C}_X+W_k{C}_W+D_k{C}_D,D_{k+1}=W_k{C}_W+D_k{C}_D,$ again omitting the empty-block term. Let ${\mathrm{\Theta }}_{k+1}$ be the selected diagonal Ritz-value matrix and increment $k$.

5. Repeat from step 2. No convergence, rate, or accuracy is asserted when the budget or rank-loss branch is returned. The exact SPD conditions on $B$ and $T$ define the permitted metric and preconditioner; no particular incomplete-factorization procedure is assumed.