Complete stagnation of GMRES (Q1873705): Difference between revisions

In their introduction, the authors state, ``We study an oddity: the class of problems for which the generalized minimal residual (GMRES) algorithm, when started with the initial guess \(x^{(0)}=0\) and using exact arithmetic, computes \(m\) iterates \(x^{(1)}=\cdots=x^{(m)}=0\) without making any progress at all. We call this \textit{partial} or \textit{m-step stagnation.} If \(m=n-1\), we call this \textit{complete stagnation} of GMRES. In this case, GMRES will compute the exact solution at iteration \(n\).'' Assume that the matrix equation to be solved is \(Ax=b\), and that the matrix \(A\) is diagonalizable and has spectral decomposition \(A=V\Lambda V^{-1}\), with \(\Lambda\) the diagonal matrix whose entries are eigenvalues of \(A\) and \(V\) the matrix whose columns are right eigenvectors of \(A\). Write \(y=V^{-1}b\) and denote the diagonal matrix whose entries are the components of \(y\) by \(Y\). Further, denote the Vandermonde matrix constructed from the first \(m\) eigenvalues of \(A\) by \(Z_m\). Finally, denote \(e_1=[1,0,\ldots,0]^T\). The \textit{stagnation} equation \[ Z^H_{m+1}\bar{Y}(V^HV)y=e_1 \] is shown to completely characterize \(m\)-stagnation. The proof is based on a well-known factorization of the Krylov matrix. In the case of complete stagnation and distinct eigenvalues of \(A\), the stagnation equation becomes a statement of equality of the two matrices \(G(\lambda)=Z_n^{-H}e_1\) and \(F_V(y)=\bar{Y}(V^HV)y\). This segregation of the influences of eigenvalues and eigenvectors allows a geometrical interpretation of the stagnation equation. The authors continue their discussion with several special cases: (1) normal matrices where complete stagnation is impossible if \(G(y)\) has complex or negative real entries; (2) Hermitian and real symmetric matrices where complete stagnation is impossible; and, (3) unitary matrices where stagnation is possible if and only if the phase angles of eigenvalues are distributed uniformly on the unit sphere. Some of the discussion presents new proofs of known results and some results themselves are new. Some of the discussion focusses on particular numerical examples derived from theoretical results.