The convergence of the GMRES linear solver is notoriously hard to predict.A particularly enlightening result by[Greenbaum, Pták, Strakoš, 1996]is that, given any convergence curve, one can build a linear system for which GMRES realizes that convergence curve.What is even more extraordinary is that the eigenvalues of the problem matrix can be chosen arbitrarily.We build upon this idea to derive novel results about weighted GMRES.We prove that for any linear system and any prescribed convergence curve, there exists a weight matrix M for which weighted GMRES (i.e.GMRES in the inner product induced by M ) realizes that convergence curve, and we characterize the form of M .Additionally, we exhibit a necessary and sufficient condition on M for the simultaneous prescription of two convergence curves, one realized by GMRES in the Euclidean inner product, and the other in the inner product induced by M .These results are then applied to infer some properties of preconditioned GMRES when the preconditioner is applied either on the left or on the right.For instance, we show that any two convergence curves are simultaneously possible for left and right preconditioned GMRES.
This paper extends the theory of prescribed convergence curves for the GMRES algorithm to scenarios involving weighted GMRES and preconditioned GMRES. It builds on the foundational results concerning GMRES convergence properties and presents novel theoretical findings that demonstrate how a weight matrix can influence convergence behavior. The authors show that for any linear system and a desired convergence curve, an appropriate weight matrix can be constructed to ensure that GMRES performs accordingly. Furthermore, they establish necessary and sufficient conditions for achieving simultaneous convergence curves for GMRES and weighted GMRES, as well as for left and right preconditioned GMRES. This is illustrated through various theorems and proposed theoretical results that characterize weight matrices and highlight implications for both weighted GMRES and preconditioned GMRES. Moreover, aspects of numerical experiments are discussed that provide empirical validation of the theoretical results, showcasing the relationship between convergence behavior and choice of preconditioners.
This paper employs the following methods:
- GMRES
- weighted GMRES
- left preconditioned GMRES
- right preconditioned GMRES
The following datasets were used in this research:
- Any nonincreasing convergence curve can be realized by GMRES and weighted GMRES.
- Existence of a Hermitian positive definite weight matrix M for a given convergence curve and linear system.
- Necessary and sufficient conditions for realising two convergence curves simultaneously for GMRES and weighted GMRES.
The authors identified the following limitations:
- The condition for simultaneous prescription of convergence curves may not be natural for larger systems.
- Number of GPUs: None specified
- GPU Type: None specified
- Compute Requirements: None specified