A note on the (regularizing) preconditioning of \(g\)-Toeplitz sequences via \(g\)-circulants. (English) Zbl 1244.65045
The authors consider the preconditioning of \(g\)-Toeplitz sequences in the generalized case \(g \geq 2\). They show that, while the optimal preconditioning cannot be achieved, the result has a potential positive implication since there exist choices of \(g\)-circulant sequences which are regularizing preconditioning sequences for the corresponding \(g\)-Toeplitz structures. Numerical experiments confirming the theoretical results are also provided.
Reviewer: Constantin Popa (Constanţa)
Keywords:
\(g\)-circulants; spectral distributions; clustering; preconditioning; multigrid methods; \(g\)-Toeplitz sequences; numerical experimentsReferences:
| [1] | Davis, P., Circulant Matrices (1979), J. Wiley and Sons: J. Wiley and Sons New York · Zbl 0418.15017 |
| [2] | Trench, W., Properties of multilevel block \(\alpha \)-circulants, Linear Algebra Appl., 431, 1833-1847 (2009) · Zbl 1178.15017 |
| [3] | Hackbush, W., Multi-Grid Methods and Applications (1979), Springer-Verlag: Springer-Verlag New York |
| [4] | Donatelli, M.; Serra-Capizzano, S.; Sesana, D., Multigrid methods for Toeplitz linear systems with different size reduction, BIT, 1-23 (2011) |
| [5] | Daubechies, I., (Ten Lectures on Wavelets. Ten Lectures on Wavelets, CBMS-NSF Regional Conference Series in Applied Mathematics, vol. 61 (1992), SIAM: SIAM Philadelphia) · Zbl 0776.42018 |
| [6] | Dyn, N.; Levin, D., Subdivision schemes in geometric modelling, Acta Numer., 11, 73-144 (2002) · Zbl 1105.65310 |
| [7] | Strang, G., Wavelets and dilation equations: a brief introduction, SIAM Rev., 31, 4, 614-627 (1989) · Zbl 0683.42030 |
| [8] | Trottenberg, U.; Oosterlee, C. W.; Schüller, A., Multigrid (2001), Academic Press: Academic Press London · Zbl 0976.65106 |
| [9] | Aricò, A.; Donatelli, M.; Serra-Capizzano, S., \(V\)-cycle optimal convergence for certain (multilevel) structured linear systems, SIAM J. Matrix Anal. Appl., 26, 1, 186-214 (2004) · Zbl 1105.65322 |
| [10] | Serra-Capizzano, S., A note on antireflective boundary conditions and fast deblurring models, SIAM J. Sci. Comput., 25, 4, 1307-1325 (2003) · Zbl 1062.65152 |
| [11] | Serra-Capizzano, S., Convergence analysis of two-grid methods for elliptic Toeplitz and PDEs matrix-sequences, Numer. Math., 92, 433-465 (2002) · Zbl 1013.65026 |
| [12] | Ngondiep, E.; Serra-Capizzano, S.; Sesana, D., Spectral features and asymptotic properties and \(g\)-circulants and \(g\)-Toeplitz sequences, SIAM J. Matrix Anal. Appl., 31, 4, 1663-1687 (2010) · Zbl 1206.15010 |
| [13] | Chan, R. H.; Ng, M. K., Conjugate gradient methods for Toeplitz systems, SIAM Rev., 38, 427-482 (1996) · Zbl 0863.65013 |
| [14] | Chan, T. F., An optimal circulant preconditioner for Toeplitz systems, SIAM J. Sci. Stat. Comput., 9, 766-771 (1988) · Zbl 0646.65042 |
| [15] | Serra-Capizzano, S., A Korovkin-type theory for finite Toeplitz operators via matrix algebras, Numer. Math., 82, 1, 117-142 (1999) · Zbl 0930.65024 |
| [16] | Serra-Capizzano, S., A Korovkin based approximation of multilevel Toeplitz matrices (with rectangular unstructured blocks) via multilevel trigonometric matrix spaces, SIAM J. Numer. Anal., 36, 6, 1831-1857 (1999) · Zbl 0958.41016 |
| [17] | Böttcher, A.; Silbermann, B., Introduction to Large Truncated Toeplitz Matrices (1999), Springer-Verlag: Springer-Verlag New York · Zbl 0916.15012 |
| [18] | Böttcher, A.; Grudsky, S.; Maksimenko, E., The Szegö and Avram-Parter theorems for general test functions, C. R. Math. Acad. Sci. Paris, 346, 749-752 (2008) · Zbl 1145.15007 |
| [19] | Böttcher, A.; Gutiérrez-Gutiérrez, J.; Crespo, P., Mass concentration in quasicommutators of Toeplitz matrices, J. Comput. Appl. Math., 205, 129-148 (2007) · Zbl 1128.47063 |
| [20] | Golinskii, L.; Serra-Capizzano, S., The asymptotic properties of the spectrum of non symmetrically perturbed Jacobi matrix sequences, J. Approx. Theory, 144, 1, 84-102 (2007) · Zbl 1111.15013 |
| [21] | Kuijlaars, A. B.J.; Serra-Capizzano, S., Asymptotic zero distribution of orthogonal polynomials with discontinuously varying recurrence coefficients, J. Approx. Theory, 113, 1, 142-155 (2001) · Zbl 0990.42008 |
| [22] | Silbermann, B.; Zabroda, O., Asymptotic behavior of generalized convolutions: an algebraic approach, J. Integral Equations Appl., 18, 2, 169-196 (2006) · Zbl 1149.47020 |
| [23] | Tyrtyshnikov, E.; Zamarashkin, N., Spectra of multilevel Toeplitz matrices: advanced theory via simple matrix relationships, Linear Algebra Appl., 270, 15-27 (1998) · Zbl 0890.15006 |
| [24] | Tilli, P., A note on the spectral distribution of Toeplitz matrices, Linear Multilinear Algebra, 45, 147-159 (1998) · Zbl 0951.65033 |
| [25] | Tilli, P., Some results on complex Toeplitz eigenvalues, J. Math. Anal. Appl., 239, 2, 390-401 (1999) · Zbl 0935.15002 |
| [26] | Tyrtyshnikov, E., A unifying approach to some old and new theorems on distribution and clustering, Linear Algebra Appl., 232, 1-43 (1996) · Zbl 0841.15006 |
| [27] | Serra-Capizzano, S., Distribution results on the algebra generated by Toeplitz sequences: a finite dimensional approach, Linear Algebra Appl., 328, 121-130 (2001) · Zbl 1003.15008 |
| [28] | Serra-Capizzano, S., Generalized locally Toeplitz sequences: spectral analysis and applications to discretized partial differential equations, Linear Algebra Appl., 366, 371-402 (2003) · Zbl 1028.65109 |
| [29] | Axelsson, O.; Lindskög, G., The rate of convergence of the preconditioned conjugate gradient method, Numer. Math., 52, 499-523 (1986) · Zbl 0564.65017 |
| [30] | Tyrtyshnikov, E., Circulant preconditioners with unbounded inverses, Linear Algebra Appl., 216, 1-23 (1995) · Zbl 0821.65013 |
| [31] | Golub, G.; Van Loan, C., Matrix Computations (1983), The Johns Hopkins University Press: The Johns Hopkins University Press Baltimore · Zbl 0559.65011 |
| [32] | Moore, E. H., General Analysis. Part I (1935), Amer. Phil. Society: Amer. Phil. Society Philadelphia · JFM 61.0433.06 |
| [33] | Penrose, R., A generalized inverse for matrices, Proc. Camb. Phil. Soc., 51, 406-413 (1955) · Zbl 0065.24603 |
| [34] | Bhatia, R., Matrix Analysis (1997), Springer-Verlag: Springer-Verlag New York |
| [35] | E. Ngondiep, S. Serra-Capizzano, D. Sesana, Spectral features and asymptotic properties for \(\alpha\alpha\) http://arxiv.org/abs/0906.2104; E. Ngondiep, S. Serra-Capizzano, D. Sesana, Spectral features and asymptotic properties for \(\alpha\alpha\) http://arxiv.org/abs/0906.2104 · Zbl 1206.15010 |
| [36] | Tilli, P., Locally Toeplitz matrices: spectral theory and applications, Linear Algebra Appl., 278, 91-120 (1998) · Zbl 0934.15009 |
| [37] | Serra-Capizzano, S., The GLT class as a generalized Fourier analysis and applications, Linear Algebra Appl., 419, 180-233 (2006) · Zbl 1109.65032 |
| [38] | Serra-Capizzano, S.; Tyrtyshnikov, E., Any circulant-like preconditioner for multilevel matrices is not superlinear, SIAM J. Matrix Anal. Appl., 21, 2, 431-439 (1999) · Zbl 0952.65037 |
| [39] | Estatico, C., A classification scheme for regularizing preconditioners, with application to Toeplitz systems, Linear Algebra Appl., 397, 107-131 (2005) · Zbl 1071.65062 |
| [40] | Serra-Capizzano, S., The spectral approximation of multiplication operators via asymptotic (structured) linear algebra, Linear Algebra Appl., 424, 154-176 (2007) · Zbl 1134.65027 |
| [41] | Strang, G., A proposal for Toeplitz matrix calculations, Stud. Appl. Math., 74, 171-176 (1986) · Zbl 0621.65025 |
| [42] | Tyrtyshnikov, E., Optimal and superoptimal circulant preconditioners, SIAM J. Matrix Anal. Appl., 13, 459-473 (1992) · Zbl 0774.65024 |
| [43] | Estatico, C., Preconditioners for ill-conditioned Toeplitz matrices with differentiable generating functions, Numer. Linear Algebra Appl., 16, 237-257 (2009) · Zbl 1224.65073 |
| [44] | Bertero, M.; Boccacci, P., Introduction to Inverse Problems in Imaging (1998), Institute of Physics Publ.: Institute of Physics Publ. Bristol · Zbl 0914.65060 |
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.
