Top

BIT Numerical Mathematics

Published in:

04-07-2021

Band-times-circulant preconditioners for non-symmetric Toeplitz systems

Authors: Dimitrios Noutsos, Grigorios Tachyridis

Published in: BIT Numerical Mathematics | Issue 2/2022

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

In this paper we study \(n\times n\) non-symmetric, real Toeplitz systems of the form \(T_n(f)x = b\), where the generating function of the Toeplitz matrix f is known a priori. We study the behavior of a specific circulant preconditioner and we also propose a preconditioner arising from the combination of a band Toeplitz matrix and circulant matrices, for ill-conditioned Toeplitz systems. For the solution of the system we use Krylov subspace methods and more specifically the Conjugate Gradient method for the corresponding preconditioned system of the normal equations and the Preconditioned Generalized Minimal Residual method. We prove theoretical results, which guarantee the efficiency of the proposed preconditioner either when f is continuous or it is piecewise continuous. We emphasize that f may have zeros in \((-\pi ,\pi ]\). Finally, we present various numerical experiments, where the efficiency of the proposed preconditioning technique is shown, since we get the solution of the preconditioned system in a small number of iterations.

previous article A higher order weak approximation of McKean–Vlasov type SDEs

next article An accelerated minimal gradient method with momentum for strictly convex quadratic optimization

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Axelsson, O.: Conjugate gradient type methods for unsymmetric and inconsistent systems of linear equations. Linear Algebra Appl. 29, 1–16 (1980). https://doi.org/10.1016/0024-3795(80)90226-8MathSciNetCrossRefMATH

Bendixson, I.: Sur les racines d’une équation fondamentale. Acta Math. 25, 359–365 (1902). https://doi.org/10.1007/BF02419030MathSciNetCrossRefMATH

Chan, R.H., Ng, M.K.: Conjugate gradient methods for Toeplitz systems. SIAM Rev. 38(3), 427–482 (1996). https://doi.org/10.1137/S0036144594276474MathSciNetCrossRefMATH

Chan, R.H., Yeung, M.C.: Circulant preconditioners for complex Toeplitz matrices. SIAM J. Numer. Anal. 30(4), 1193–1207 (1993). https://doi.org/10.1137/0730062MathSciNetCrossRefMATH

Chan, T.F.: An optimal circulant preconditioner for Toeplitz systems. SIAM J. Sci. Statist. Comput. 9(4), 766–771 (1988). https://doi.org/10.1137/0909051MathSciNetCrossRefMATH

Di Benedetto, F., Fiorentino, G., Serra, S.: CG preconditioning for Toeplitz matrices. Comput. Math. Applic. 25(6), 35–45 (1993). https://doi.org/10.1016/0898-1221(93)90297-9MathSciNetCrossRefMATH

Di Benedetto, F., Serra Capizzano, S.: A unifying approach to abstract matrix algebra preconditioning. Numer. Math. 82(1), 57–90 (1999)MathSciNetCrossRef

Duffy, D.J.: Finite Difference Methods in Financial Engineering: a Partial Differential Equation approach. John Wiley, Hoboken (2013)

Ferrari, P., Furci, I., Hon, S., Mursaleen, M.A., Serra-Capizzano, S.: The eigenvalue distribution of special 2-by-2 block matrix-sequences with applications to the case of symmetrized Toeplitz structures. SIAM J. Matrix Anal. Appl. 40(3), 1066–1086 (2019). https://doi.org/10.1137/18M1207399MathSciNetCrossRefMATH

10.

Garren, K.R.: Bounds for the Eigenvalues of a Matrix. In: Dissertations, Theses, and Masters Projects. Paper 1539624585 (1965). https://doi.org/10.21220/s2-p2tn-7046

11.

Gmati, N., Philippe, B.: Comments on the GMRES convergence for preconditioned systems. In: International Conference on Large-Scale Scientific Computing, pp. 40–51. Springer (2007). https://doi.org/10.1007/978-3-540-78827-0_4

12.

Higham, N.J.: Functions of Matrices: Theory and Computation. SIAM, Philadelphia (2008)CrossRef

13.

Hirsch, M.: Sur les racines d’une équation fondamentale. Acta Math. 25, 367–370 (1902). https://doi.org/10.1007/BF02419031MathSciNetCrossRefMATH

14.

Hon, S., Wathen, A.: Circulant preconditioners for analytic functions of Toeplitz matrices. Numer. Algor. 79(4), 1211–1230 (2018). https://doi.org/10.1007/s11075-018-0481-7MathSciNetCrossRefMATH

15.

Horn, R.A., Johnson, C.R.: Topics in Matrix Analysis. Cambridge University Press, Cambridge (1994)MATH

16.

Kressner, D., Luce, R.: Fast computation of the matrix exponential for a Toeplitz matrix. SIAM J. Matrix Anal. Appl. 39(1), 23–47 (2018). https://doi.org/10.1137/16M1083633MathSciNetCrossRefMATH

17.

Nachtigal, N.M., Reddy, S.C., Trefethen, L.N.: How fast are nonsymmetric matrix iterations? SIAM J. Matrix Anal. Appl. 13(3), 778–795 (1992). https://doi.org/10.1137/0613049MathSciNetCrossRefMATH

18.

Ng, M.: Iterative Methods for Toeplitz Systems. Oxford University Press, New York (2004)MATH

19.

Noschese, S., Pasquini, L., Reichel, L.: Tridiagonal Toeplitz matrices: properties and novel applications. Numer. Linear Algebra Appl. 20(2), 302–326 (2013). https://doi.org/10.1002/nla.1811MathSciNetCrossRefMATH

20.

Noutsos, D., Serra-Capizzano, S., Vassalos, P.: Spectral equivalence and matrix algebra preconditioners for multilevel Toeplitz systems: a negative result. Contemp. Math. 323, 313–322 (2003)MathSciNetCrossRef

21.

Noutsos, D., Serra-Capizzano, S., Vassalos, P.: Matrix algebra preconditioners for multilevel Toeplitz systems do not insure optimal convergence rate. Theor. Comput. Sci. 315(2–3), 557–579 (2004). https://doi.org/10.1016/j.tcs.2004.01.007MathSciNetCrossRefMATH

22.

Noutsos, D., Tachyridis, G.: Band Toeplitz preconditioners for non-symmetric real Toeplitz systems by preconditioned GMRES method. J. Comput. Appl. 373, 112250 (2020). https://doi.org/10.1016/j.cam.2019.04.030MathSciNetCrossRefMATH

23.

Noutsos, D., Vassalos, P.: Superlinear convergence for PCG using band plus algebra preconditioners for Toeplitz systems. Comput. Math. Appl. 56, 1255–1270 (2008). https://doi.org/10.1016/j.camwa.2008.02.046MathSciNetCrossRefMATH

24.

Noutsos, D., Vassalos, P.: Band plus algebra preconditioners for two-level Toeplitz systems. BIT Numer. Math. 51(3), 695–719 (2011). https://doi.org/10.1007/s10543-011-0314-8MathSciNetCrossRefMATH

25.

Pestana, J., Wathen, A.J.: A preconditioned minres method for nonsymmetric Toeplitz matrices. SIAM J. Matrix Anal. Appl. 36(1), 273–288 (2015). https://doi.org/10.1137/140974213MathSciNetCrossRefMATH

26.

Potts, D., Steidl, G.: Optimal trigonometric preconditioners for nonsymmetric Toeplitz systems. Linear Algebra Appl. 281(1–3), 265–292 (1998). https://doi.org/10.1016/S0024-3795(98)10042-3MathSciNetCrossRefMATH

27.

Potts, D., Steidl, G.: Preconditioners for ill-conditioned Toeplitz matrices. BIT Numer. Math. 39(3), 513–533 (1999). https://doi.org/10.1023/A:1022322820082MathSciNetCrossRefMATH

28.

Saad, Y., Schultz, M.H.: GMRES: A generalized minimal residual algorithm for solving nonsymmetric linear systems. SIAM J. Sci. Statist. Comp. 7(3), 856–869 (1986). https://doi.org/10.1137/0907058MathSciNetCrossRefMATH

29.

Sachs, E., Strauss, A.: Efficient solution of a partial integro-differential equation in finance. Appl. Numer. Math. 58(11), 1687–1703 (2008). https://doi.org/10.1016/j.apnum.2007.11.002MathSciNetCrossRefMATH

30.

Serra-Capizzano, S.: Spectral behavior of matrix sequences and discretized boundary value problems. Linear Algebra Appl. 337(1–3), 37–78 (2001). https://doi.org/10.1016/S0024-3795(01)00335-4MathSciNetCrossRefMATH

31.

Serra-Capizzano, S., Tyrtyshnikov, E.: Any circulant-like preconditioner for multilevel matrices is not superlinear. SIAM J. Matrix Anal. Appl. 21(2), 431–439 (2000). https://doi.org/10.1137/S0895479897331941MathSciNetCrossRefMATH

32.

Sohrab, H.H.: Basic Real Analysis. Birkhäuser, New York (2003)CrossRef

33.

Strang, G.: A proposal for Toeplitz matrix calculations. Stud. Appl. Math. 74(2), 171–176 (1986). https://doi.org/10.1002/sapm1986742171CrossRefMATH

34.

Tyrtyshnikov, E.E.: Circulant preconditioners with unbounded inverses. Linear Algebra Appl. 216, 1–23 (1995). https://doi.org/10.1016/0024-3795(93)00092-EMathSciNetCrossRefMATH

35.

Tyrtyshnikov, E.E.: A unifying approach to some old and new theorems on distribution and clustering. Linear Algebra Appl. 232, 1–43 (1996). https://doi.org/10.1016/0024-3795(94)00025-5MathSciNetCrossRefMATH

36.

Widom, H.: Hankel matrices. Trans. Am. Math. Soc. 121(1), 1–35 (1966)MathSciNetCrossRef

37.

Yeung, M.C., Chan, R.H.: Circulant preconditioners for Toeplitz matrices with piecewise continuous generating functions. Math. Comput. 61(204), 701–718 (1993). https://doi.org/10.2307/2153248MathSciNetCrossRefMATH

Title: Band-times-circulant preconditioners for non-symmetric Toeplitz systems
Authors: Dimitrios Noutsos
Grigorios Tachyridis
Publication date: 04-07-2021
Publisher: Springer Netherlands
Published in: BIT Numerical Mathematics / Issue 2/2022
Print ISSN: 0006-3835
Electronic ISSN: 1572-9125
DOI: https://doi.org/10.1007/s10543-021-00883-y

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Springer Professional "Wirtschaft+Technik"

Other articles of this Issue 2/2022

How to avoid order reduction when Lawson methods integrate nonlinear initial boundary value problems

Efficient shifted fractional trapezoidal rule for subdiffusion problems with nonsmooth solutions on uniform meshes

An accelerated minimal gradient method with momentum for strictly convex quadratic optimization

Pointwise and uniform error estimates associated with Abel-Whittaker interpolation series and its dual

An efficient hybrid method for uncertainty quantification

A higher order weak approximation of McKean–Vlasov type SDEs

Premium Partner