"Weighted inner products for GMRES and GMRES-DR"

Mark Embree, Ronald B. Morgan, and Huy V. Nguyen

To appear in*SIAM J. Scientific Comp.*

Preprint: arXiv:1607.00255 [math.NA] (revised March 2017)

### What it does

### Why it matters

Mark Embree, Ronald B. Morgan, and Huy V. Nguyen

To appear in

Preprint: arXiv:1607.00255 [math.NA] (revised March 2017)

In 1998 Essai proposed a variant of the GMRES algorithm in which the inner product is changed at
each restart, as determined by the current residual vector.
From some systems this modification gives much faster convergence; for others, little improvement
or even slower convergence. While the promise of this method has attracted attention over the years,
our inability to predict the matrices on which excels has limited its adoption.
This manuscript proposes that this W-GMRES algorithm performs well when the eigenvectors
of the coefficient matrix are *localized*, i.e., small aside from a few entries.
For matrices lacking this property, we propose the W-GMRES-DCT matrix, which incorporates
a fast discrete cosine transform into the inner product: this method seems to perform
well when the eigenvectors are localized *in the Fourier basis*
(as is often the case for discretizations of constant-coefficient differential equations).
The manuscript also shows how to incorporate an inner product in the GMRES-DR algorithm.

W-GMRES seems to have the most impact for difficult problems with small restart parameters.
By better understanding the cases where it succeeds, we can deploy it more strategically.
The W-GMRES-DCT algorithm shows how to extend the benefits of weighted inner products
to a another important class of matrices, and suggests the development of
fast transformations that localize eigenvectors for other specific applications.
Weighting can be combined with deflated restarting to give W-GMRES-DR.

*W-GMRES for the Add20 matrix (Essai's example)*

*W-GMRES-DCT for a 2d convection diffusion matrix*