Discretizing PDEs leads to linear systems with large, sparse coefficient matrices. When linear, constant-coefficient PDEs with Dirichlet boundary conditions are discretized on uniform meshes, one can obtain Toeplitz, multilevel Toeplitz and/or block Toeplitz systems [1, 2]. Toeplitz matrices have constant diagonals, and multilevel and block Toeplitz matrices have related structures, that can be exploited to speed up GMRES, and aid convergence analysis. Such systems are widely solved by Krylov subspace methods.

Let

\begin{equation} \label {LE} Ax=b, \end{equation}

where the matrix \(A\) is Toeplitz, \(b\) is a known right-hand side, and \(x\) is the unknown solution. GMRES starts with an initial guess, \(x_0\), and select \(x_k, k = 1,2,\cdots \), such that \(x_k-x_0\in \mathcal {K}_k(A,r_0) := \)span \(\{r_0,\) \(Ar_0,\cdots ,A^{(k-1)} r_0\}\), where \(r_0 = A(x-x_0)\).

Let \(Y\) be the reverse identity matrix, then \(YA\) is symmetric Hankel. One can solve (1) through

\begin{equation} \label {flip} YAx=Yb, \end{equation}

by applying MINRES [3], which is mathematically equivalent to GMRES for a symmetric system. Through our experiments, we find that MINRES on (2) requires about twice as many iterations as GMRES on (1) to converge, especially when preconditioned.

For a symmetric system such as (2), the convergence behavior of MINRES can usually be characterized by the eigenvalues and the RHS. However, when \(A\) is nonsymmetric, GMRES convergence behavior is much more complicated to describe; in extreme cases the spectrum bears no relation to the convergence rate. In [4], the authors prove that any nonoincreasing convergence curve is possible for GMRES by constructing a linear system of prescribed nonzero eigenvalues with a given convergence curve.

In this work, we explore the convergence behavior of GMRES when applied to real tridiagonal Toeplitz systems, where the matrix

\begin{equation} A=\begin{bmatrix} \alpha & \gamma & 0 & \cdots & 0\\ \beta & \alpha & \gamma & \cdots & 0\\ \vdots & \ddots & \ddots & \ddots & \vdots \\ 0 & 0 & \beta & \alpha & \gamma \\ 0 & 0 & 0 & \beta & \alpha \end {bmatrix}, \end{equation}

\(\alpha , \beta , \) and \(\gamma \in \mathbb {R}.\)

We show that different GMRES convergence behavior is possible for different Toeplitz systems that share the same spectra, regardless of their right hand sides. We also explore the connection between the GMRES convergence behavior and the singular values of the tridiagonal Toeplitz matrices.

In spite of the difficulties, there has been plenty of work in the literature inspecting the convergence behavior of GMRES. For instance, in [5], the authors point out that, for a general nonsingluar matrix \(A\), the convergence behavior of GMRES is related to the distribution of eigenvalues of \(A\), and provide an upper bound. However, each eigenvalue is either treated as a member of some cluster, or an outlier to any cluster. For the cases where eigenvalues are not spreading out far away from each other, for example, those of a tridiagonal Toeplitz matrix, or when the clusters are far away from each other, one fails to find a meaningful upper bound since it become too loose. In [6], Meurant shows through APS parametrization of \(A\) that GMRES could have different convergence behaviors for two different matrices with the same spectrum. Nevertheless, a reconstructed matrix \(A\) in this case does not preserve the Toeplitz structure in general. As for tridiagonal matrix systems, Liesen and Strakoš analyze the convergence behavior of GMRES when \(|\alpha |\approx |\beta |\gg |\gamma |\) [7]. For a more general case where \(\beta |\neq |\gamma |\), Li and Zhang provide upper bounds and asymptotic speeds of the 2-norm of the \(k^{th}\) residual via Chebyshev polynomial of the first kind[8] and the second kind[9]. In our work, we formulate equations based on APS parametrization of \(A\) with the constraint that each diagonal is constant to explore what convergence regimes are possible for a tridiagonal Toeplitz system.

References

• [1]  C. Garoni and S. Serra-Capizzano, Generalized Locally Toeplitz Sequences: Theory and Applications, vol. I Springer Cham, 2017.

• [2]  C. Garoni and S. Serra-Capizzano, Generalized Locally Toeplitz Sequences: Theory and Applications, vol. II Springer Cham, 2018.

• [3]  J. Pestana and A. Wathen, A preconditioned MINRES method for nonsymmetric Toeplitz matrices, SIAM J. Matrix Anal. Appl., vol 36(2015), no. 1, 273-288.

• [4]  A. Greenbaum, V. Pták, Z. Strakoš Any non increasing convergence curve is possible for GMRES, SIAM J. Matrix Anal. Appl., vol 17(1996), no. 3, 465-469.

• [5]  S. L. Campbell, I. C. F. Ipsen, C. T. Kelley and C. D. Meyer, GMRES and the minimal polynomial, BIT Numerical Mathematics, vol 36(1996), no. 4, 664-675.

• [6]  G. Meurant, GMRES and the Arioli, Pták, and Strakoš parametrization, BIT Numerical Mathematics, vol 52(2012), 687-702.

• [7]  J. Liesen and Z. Strakoš, Convergence of GMRES for tridiagonal Toeplitz matrices, SIAM J. Matrix Anal. Appl., vol 26(2004), no. 1, 233-251.

• [8]  R. C. Li and W. Zhang, The rate of convergence of GMRES on a tridiagonal Toeplitz linear system, Numerische Mathematik, vol 112(2009), 267-293.

• [9]  R. C. Li and W. Zhang, The rate of convergence of GMRES on a tridiagonal Toeplitz linear system. II, Linear Algebra and its Applications, vol 12(2009), 2425-2436.