Multigrid methods for Toeplitz linear systems with different size reduction

DOI10.1007/S10543-011-0356-YzbMATH Open1251.65047arXiv1010.5730OpenAlexW2056645965MaRDI QIDQ438734FDOQ438734

Authors: Marco Donatelli, Debora Sesana, Stefano Serra Capizzano 

Publication date: 31 July 2012

Published in: BIT (Search for Journal in Brave)

Abstract: Starting from the spectral analysis of g-circulant matrices, we consider a new multigrid method for circulant and Toeplitz matrices with given generating function. We assume that the size n of the coefficient matrix is divisible by g geq 2 such that at the lower level the system is reduced to one of size n/g by employing g-circulant based projectors. We perform a rigorous two-grid convergence analysis in the circulant case and we extend experimentally the results to the Toeplitz setting, by employing structure preserving projectors. The optimality of the proposed two-grid method and of the multigrid method is proved, when the number theta in N of recursive calls is such that 1 < theta < g. The previous analysis is used also to overcome some pathological cases, in which the generating function has zeros located at "mirror points" and the standard two-grid method with g = 2 is not optimal. The numerical experiments show the correctness and applicability of the proposed ideas both for circulant and Toeplitz matrices.

Full work available at URL: https://arxiv.org/abs/1010.5730

Recommendations

• Convergence of the multigrid method for ill-conditioned block Toeplitz systems
• Multigrid methods for Toeplitz matrices
• A note on the convergence of the two-grid method for Toeplitz systems
• Generalized grid transfer operators for multigrid methods applied on Toeplitz matrices
• Convergence analysis of two-grid methods for elliptic Toeplitz and PDEs matrix-sequences

zbMATH Keywords

convergencenumerical experimentscirculant\(g\)-circulant and Toeplitz matricestwo-grid and multigrid methods

Mathematics Subject Classification ID

Multigrid methods; domain decomposition for boundary value problems involving PDEs (65N55) Iterative numerical methods for linear systems (65F10) Toeplitz, Cauchy, and related matrices (15B05)

Cites Work

• Conjugate Gradient Methods for Toeplitz Systems
• Multi-iterative methods
• Convergence analysis of two-grid methods for elliptic Toeplitz and PDEs matrix-sequences
• Multigrid methods for block Toeplitz matrices with small size blocks
• Spectral Features and Asymptotic Properties for g-Circulants and g-Toeplitz Sequences
• An algebraic generalization of local Fourier analysis for grid transfer operators in multigrid based on Toeplitz matrices
• V-cycle Optimal Convergence for Certain (Multilevel) Structured Linear Systems
• A \(V\)-cycle multigrid for multilevel matrix algebras: proof of optimality
• Matrix algebra preconditioners for multilevel Toeplitz matrices are not superlinear
• Multigrid Method for Ill-Conditioned Symmetric Toeplitz Systems
• Any Circulant-Like Preconditioner for Multilevel Matrices Is Not Superlinear
• Compact Fourier Analysis for Designing Multigrid Methods
• Matrix algebra preconditioners for multilevel Toeplitz systems do not insure optimal convergence rate
• A superfast solver for real symmetric Toeplitz systems using real trigonometric transformations
• Properties of unilevel block circulants
• Multigrid methods for Toeplitz matrices
• A note on the convergence of the two-grid method for Toeplitz systems
• Multigrid preconditioning and Toeplitz matrices
• Convergence of the multigrid method for ill-conditioned block Toeplitz systems
• Algebraic analysis of aggregation-based multigrid.
• Estimates of inverses of multivariable Toeplitz matrices
• Fast design of multichannel FIR least-squares filters with optimum lag
• Multigrid Methods for Multilevel Circulant Matrices
• Multigrid Methods for Symmetric Positive Definite Block Toeplitz Matrices with Nonnegative Generating Functions
• Comparison of bounds for V-cycle multigrid

Cited In (15)

• Symbol approach in a signal-restoration problem involving block Toeplitz matrices
• Sparse matrix approximations for multigrid methods
• A note on the eigenvalues of \(g\)-circulants (and of \(g\)-Toeplitz, \(g\)-Hankel matrices)
• Asymptotic spectra of large (grid) graphs with a uniform local structure. II: Numerical applications
• Multigrid methods for Toeplitz matrices
• Function-based block multigrid strategy for a two-dimensional linear elasticity-type problem
• Mixed two-grid finite difference methods for solving one-dimensional and two-dimensional Fitzhugh-Nagumo equations
• Title not available (Why is that?)
• Multigrid methods for block‐Toeplitz linear systems: convergence analysis and applications
• Toeplitz momentary symbols: definition, results, and limitations in the spectral analysis of structured matrices
• A fast and efficient two-grid method for solving \(d\)-dimensional Poisson equations
• Multigrid methods for block Toeplitz matrices with small size blocks
• Analysis of smoothed aggregation multigrid methods based on Toeplitz matrices
• Robust and optimal multi-iterative techniques for Iga Galerkin linear systems
• Multigrid methods: grid transfer operators and subdivision schemes

This page was built for publication: Multigrid methods for Toeplitz linear systems with different size reduction

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q438734)