Preconditioners for symmetrized Toeplitz and multilevel Toeplitz matrices. (English) Zbl 1420.65024
Summary: When solving linear systems with nonsymmetric Toeplitz or multilevel Toeplitz matrices using Krylov subspace methods, the coefficient matrix may be symmetrized. The preconditioned MINRES method can then be applied to this symmetrized system, which allows rigorous upper bounds on the number of MINRES iterations to be obtained. However, effective preconditioners for symmetrized (multilevel) Toeplitz matrices are lacking. Here, we propose novel ideal preconditioners and investigate the spectra of the preconditioned matrices. We show how these preconditioners can be approximated and demonstrate their effectiveness via numerical experiments.
MSC:
| 65F08 | Preconditioners for iterative methods |
| 65F10 | Iterative numerical methods for linear systems |
| 15B05 | Toeplitz, Cauchy, and related matrices |
| 35R11 | Fractional partial differential equations |
Keywords:
Toeplitz matrix; multilevel Toeplitz matrix; symmetrization; preconditioning; Krylov subspace methodReferences:
| [1] | M. Arioli, V. Pták, and Z. Strakoš, Krylov sequences of maximal length and convergence of GMRES, BIT, 38 (1998), pp. 636-643, https://doi.org/10.1007/BF02510405. · Zbl 0916.65031 |
| [2] | F. Avram, On bilinear forms in Gaussian random variables and Toeplitz matrices, Probab. Theory Related Fields, 79 (1988), pp. 37-45, https://doi.org/10.1007/BF00319101. · Zbl 0648.60043 |
| [3] | T. Breiten, V. Simoncini, and M. Stoll, Low-rank solvers for fractional differential equations, Electron. Trans. Numer. Anal., 45 (2016), pp. 107-132. · Zbl 1338.65071 |
| [4] | R. H. Chan and K.-P. Ng, Toeplitz preconditioners for Hermitian Toeplitz systems, Linear Algebra Appl., 190 (1993), pp. 181-208, https://doi.org/10.1016/0024-3795(93)90226-E. · Zbl 0783.65042 |
| [5] | R. H. Chan, M. K. Ng, and R. J. Plemmons, Generalization of Strang’s preconditioner with applications to Toeplitz least squares problems, Numer. Linear Algebra Appl., 3 (1996), pp. 45-64. · Zbl 0842.65029 |
| [6] | R. H. Chan and M.-C. Yeung, Circulant preconditioners constructed from kernels, SIAM J. Numer. Anal., 29 (1992), pp. 1093-1103, https://doi.org/10.1137/0729066. · Zbl 0761.65016 |
| [7] | R. H.-F. Chan and X.-Q. Jin, An Introduction to Iterative Toeplitz Solvers, Fund. Alg. 5, SIAM, 2007, https://doi.org/10.1137/1.9780898718850. · Zbl 1146.65028 |
| [8] | T. F. Chan, An optimal circulant preconditioner for Toeplitz systems, SIAM J. Sci. Stat. Comput., 9 (1988), pp. 766-771, https://doi.org/10.1137/0909051. · Zbl 0646.65042 |
| [9] | M. Donatelli, C. Garoni, M. Mazza, S. Serra-Capizzano, and D. Sesana, Preconditioned HSS method for large multilevel block Toeplitz linear systems via the notion of matrix-valued symbol, Numer. Linear Algebra Appl., 23 (2016), pp. 83-119, https://doi.org/10.1002/nla.2007. · Zbl 1413.65057 |
| [10] | M. Donatelli, M. Mazza, and S. Serra-Capizzano, Spectral analysis and structure preserving preconditioners for fractional diffusion equations, J. Comput. Phys., 307 (2016), pp. 262-279, https://doi.org/10.1016/j.jcp.2015.11.061. · Zbl 1352.65305 |
| [11] | D. Fasino and P. Tilli, Spectral clustering properties of block multilevel Hankel matrices, Linear Algebra Appl., 306 (2000), pp. 155-163, https://doi.org/10.1016/S0024-3795(99)00251-7. · Zbl 0952.15016 |
| [12] | P. Ferrari, I. Furci, S. Hon, M. Ayman Mursaleen, and S. Serra-Capizzano, The Eigenvalue Distribution of Special 2-by-2 Block Matrix Sequences, with Applications to the Case of Symmetrized Toeplitz Structures, preprint, https://arxiv.org/abs/1810.03326, 2018. · Zbl 1426.15041 |
| [13] | C. Garoni and S. Serra-Capizzano, Generalized Locally Toeplitz Sequences: Theory and Applications. Vol. I, Springer, 2017. · Zbl 1376.15002 |
| [14] | I. Gohberg, P. Lancaster, and L. Rodman, Indefinite Linear Algebra and Applications, Birkhäuser Verlag, Basel, 2005. · Zbl 1084.15005 |
| [15] | A. Greenbaum, V. Pták, and Z. Strakoš, Any nonincreasing convergence curve is possible for GMRES, SIAM J. Matrix Anal. Appl., 17 (1996), pp. 465-469, https://doi.org/10.1137/S0895479894275030. · Zbl 0857.65029 |
| [16] | U. Grenander and G. Szegö, Toeplitz Forms and Their Applications, 2nd ed., AMS Chelsea Publishing, 2001. |
| [17] | M. Hanke and J. G. Nagy, Toeplitz approximate inverse preconditioner for banded Toeplitz matrices, Numer. Algorithms, 7 (1994), pp. 183-199, https://doi.org/10.1007/BF02140682. · Zbl 0810.65029 |
| [18] | M. R. Hestenes and E. Stiefel, Methods of conjugate gradients for solving linear systems, J. Res. Nat. Bur. Standards, 49 (1952), pp. 409-436. · Zbl 0048.09901 |
| [19] | R. D. Hill, R. G. Bates, and S. R. Waters, On centrohermitian matrices, SIAM J. Matrix Anal. Appl., 11 (1990), pp. 128-133, https://doi.org/10.1137/0611009. · Zbl 0709.15021 |
| [20] | R. A. Horn and C. R. Johnson, Matrix Analysis, Cambridge University Press, 1990. · Zbl 0704.15002 |
| [21] | T. Huckle, S. Serra-Capizzano, and C. Tablino-Possio, Preconditioning strategies for non-Hermitian Toeplitz linear systems, Numer. Linear Algebra Appl., 12 (2005), pp. 211-220, https://doi.org/10.1002/nla.396. · Zbl 1164.65394 |
| [22] | Z. Liu, Y. Zhang, and R. Ralha, Computing the square roots of matrices with central symmetry, Appl. Math. Comput., 186 (2007), pp. 715-726, https://doi.org/10.1016/j.amc.2006.08.032. · Zbl 1121.65045 |
| [23] | M. Mazza and J. Pestana, Spectral properties of flipped Toeplitz matrices and related preconditioning, BIT, to appear, https://doi.org/10.1007/s10543-018-0740-y. · Zbl 1417.15045 |
| [24] | M. M. Meerschaert and C. Tadjeran, Finite difference approximations for fractional advection-dispersion flow equations, J. Comput. Appl. Math., 172 (2004), pp. 65-77, https://doi.org/10.1016/j.cam.2004.01.033. · Zbl 1126.76346 |
| [25] | M. M. Meerschaert and C. Tadjeran, Finite difference approximations for two-sided space-fractional partial differential equations, Appl. Numer. Math., 56 (2006), pp. 80-90, https://doi.org/10.1016/j.apnum.2005.02.008. · Zbl 1086.65087 |
| [26] | H. Moghaderi, M. Dehghan, M. Donatelli, and M. Mazza, Spectral analysis and multigrid preconditioners for two-dimensional space-fractional diffusion equations, J. Comput. Phys., 350 (2017), pp. 992-1011, https://doi.org/10.1016/j.jcp.2017.08.064. · Zbl 1380.65240 |
| [27] | M. K. Ng, Iterative Methods for Toeplitz Systems, Oxford University Press, Oxford, UK, 2004. · Zbl 1059.65031 |
| [28] | M. K. Ng and D. Potts, Circulant preconditioners for indefinite Toeplitz systems, BIT, 41 (2001), pp. 1079-1088, https://doi.org/10.1023/A:1021905715654. |
| [29] | C. C. Paige and M. A. Saunders, Solution of sparse indefinite systems of linear equations, SIAM J. Numer. Anal., 12 (1975), pp. 617-629, https://doi.org/10.1137/0712047. · Zbl 0319.65025 |
| [30] | C. C. Paige and M. A. Saunders, LSQR: An algorithm for sparse linear equations and sparse least squares, ACM Trans. Math. Software, 8 (1982), pp. 43-71, https://doi.org/10.1145/355984.355989. · Zbl 0478.65016 |
| [31] | J. Pan, R. Ke, M. K. Ng, and H.-W. Sun, Preconditioning techniques for diagonal-times-Toeplitz matrices in fractional diffusion equations, SIAM J. Sci. Comput., 36 (2014), pp. A2698-A2719, https://doi.org/10.1137/130931795. · Zbl 1314.65112 |
| [32] | H.-K. Pang and H.-W. Sun, Multigrid method for fractional diffusion equations, J. Comput. Phys., 231 (2012), pp. 693-703, https://doi.org/10.1016/j.jcp.2011.10.005. · Zbl 1243.65117 |
| [33] | S. V. Parter, On the distribution of the singular values of Toeplitz matrices, Linear Algebra Appl., 80 (1986), pp. 115-130, https://doi.org/10.1016/0024-3795(86)90280-6. · Zbl 0601.15006 |
| [34] | J. Pestana, Nonstandard Inner Products and Preconditioned Iterative Methods, Ph.D. thesis, University of Oxford, 2011. |
| [35] | J. Pestana and A. J. Wathen, A preconditioned MINRES method for nonsymmetric Toeplitz matrices, SIAM J. Matrix Anal. Appl., 36 (2015), pp. 273-288, https://doi.org/10.1137/140974213. · Zbl 1315.65034 |
| [36] | I. S. Pressman, Matrices with multiple symmetry properties: Applications of centrohermitian and perhermitian matrices, Linear Algebra Appl., 284 (1998), pp. 239-258, https://doi.org/10.1016/S0024-3795(98)10144-1. · Zbl 0957.15019 |
| [37] | Y. Saad and M. H. Schultz, GMRES: A generalized minimal residual algorithm for solving nonsymmetric linear systems, SIAM J. Sci. Stat. Comput., 7 (1986), pp. 856-869, https://doi.org/10.1137/0907058. · Zbl 0599.65018 |
| [38] | S. Serra, Preconditioning strategies for asymptotically ill-conditioned block Toeplitz systems, BIT, 34 (1994), pp. 579-594. · Zbl 0823.65030 |
| [39] | S. Serra, Spectral and computational analysis of block Toeplitz matrices having nonnegative definite matrix-valued generating functions, BIT, 39 (1999), pp. 152-175, https://doi.org/10.1023/A:1022329526925. · Zbl 0917.65031 |
| [40] | S. Serra Capizzano, Matrix algebra preconditioners for multilevel Toeplitz matrices are not superlinear, Linear Algebra Appl., 343/344 (2002), pp. 303-319, https://doi.org/10.1016/S0024-3795(01)00361-5. · Zbl 1001.65041 |
| [41] | S. Serra Capizzano and E. Tyrtyshnikov, Any circulant-like preconditioner for multilevel matrices is not superlinear, SIAM J. Matrix Anal. Appl., 21 (1999), pp. 431-439, https://doi.org/10.1137/S0895479897331941. · Zbl 0952.65037 |
| [42] | S. Serra Capizzano and E. Tyrtyshnikov, How to prove that a preconditioner cannot be superlinear, Math. Comp., 72 (2003), pp. 1305-1316, https://doi.org/10.1090/S0025-5718-03-01506-0. · Zbl 1021.15005 |
| [43] | G. Strang, A proposal for Toeplitz matrix calculations, Stud. Appl. Math., 74 (1986), pp. 171-176, https://doi.org/10.1002/sapm1986742171. · Zbl 0621.65025 |
| [44] | W. F. Trench, Characterization and properties of matrices with generalized symmetry or skew symmetry, Linear Algebra Appl., 377 (2004), pp. 207-218, https://doi.org/10.1016/j.laa.2003.07.013. · Zbl 1046.15028 |
| [45] | E. E. Tyrtyshnikov, Optimal and superoptimal circulant preconditioners, SIAM J. Matrix Anal. Appl., 13 (1992), pp. 459-473, https://doi.org/10.1137/0613030. · Zbl 0774.65024 |
| [46] | H. Wang, K. Wang, and T. Sircar, A direct \(O(N\log_2N)\) finite difference method for fractional diffusion equations, J. Comput. Phys., 229 (2010), pp. 8095-8104, https://doi.org/10.1016/j.jcp.2010.07.011. · Zbl 1198.65176 |
| [47] | H. Widom, On the singular values of Toeplitz matrices, Zeit. Anal. Anwend., 8 (1989), pp. 221-229, https://doi.org/10.4171/ZAA/350. · Zbl 0692.47028 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
