The Faber-Manteuffel Theorem Revisited

Jörg Liesen

Center for Simulation of Advanced Rockets, 3243 Digital Computer Laboratory, 1304 W. Springfield Ave., Urbana, IL 61801, USA


The Faber-Manteuffel Theorem [V. Faber and T. Manteuffel, SIAM J. Numer. Anal., 21 (1984), pp. 352-362] is a fundamental result in the theory of Krylov subspace methods. In a nutshell it says that no (single) short-term recurrence Krylov subspace method for general non-symmetric linear systems exists that minimizes the error in an inner product norm independent of the initial guess.

Despite the importance of this result, its previously existing proofs are based on complicated algebraic or topological constructions, which provide little insight about the necessity of its main assumptions for the existence of a short-term recurrence. To smooth the path mapped out by the original discoverers we will give an elementary proof of this theorem. Our approach will hopefully improve the general understanding of short-term recurrence methods, and potentially pave the way for further work in this area.

The talk is based on joint work with Prof. Paul Saylor, MPS Directorate, National Science Foundation, USA.