GMRES vs. ideal GMRES

Abstract

\begin{abstract} \noindent The GMRES algorithm minimizes $\norm{p(A)b}$ over polynomials $p$ of degree $n$ normalized at $z=0$. The ideal GMRES problem is obtained if one considers minimization of $\norm{p(A)}$ instead. The ideal problem forms an upper bound for the worst-case true problem, where the GMRES norm $\norm{p_b(A)b}$ is maximized over $b$. In work not yet published, Faber, Joubert, Knill and Manteuffel have shown that this upper bound need not be attained, constructing a $4 \times 4$ example in which the ratio of the true to ideal GMRES norms is $0.9999$. Here, we present a simpler $4 \times 4$ example in which the ratio approaches zero when a certain parameter tends to zero. The same example also leads to the same conclusion for Arnoldi vs. ideal Arnoldi norms. \end{abstract}