Multigrid methods for Toeplitz linear systems with different size reduction
From MaRDI portal
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.
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
Cites work
- A V-cycle multigrid for multilevel matrix algebras: proof of optimality
- A note on the convergence of the two-grid method for Toeplitz systems
- A superfast solver for real symmetric Toeplitz systems using real trigonometric transformations
- Algebraic analysis of aggregation-based multigrid.
- An algebraic generalization of local Fourier analysis for grid transfer operators in multigrid based on Toeplitz matrices
- Any Circulant-Like Preconditioner for Multilevel Matrices Is Not Superlinear
- Compact Fourier Analysis for Designing Multigrid Methods
- Comparison of bounds for V-cycle multigrid
- Conjugate Gradient Methods for Toeplitz Systems
- Convergence analysis of two-grid methods for elliptic Toeplitz and PDEs matrix-sequences
- Convergence of the multigrid method for ill-conditioned block Toeplitz systems
- Estimates of inverses of multivariable Toeplitz matrices
- Fast design of multichannel FIR least-squares filters with optimum lag
- Matrix algebra preconditioners for multilevel Toeplitz matrices are not superlinear
- Matrix algebra preconditioners for multilevel Toeplitz systems do not insure optimal convergence rate
- Multi-iterative methods
- Multigrid Method for Ill-Conditioned Symmetric Toeplitz Systems
- Multigrid Methods for Multilevel Circulant Matrices
- Multigrid Methods for Symmetric Positive Definite Block Toeplitz Matrices with Nonnegative Generating Functions
- Multigrid methods for Toeplitz matrices
- Multigrid methods for block Toeplitz matrices with small size blocks
- Multigrid preconditioning and Toeplitz matrices
- Properties of unilevel block circulants
- Spectral Features and Asymptotic Properties for g-Circulants and g-Toeplitz Sequences
- V-cycle Optimal Convergence for Certain (Multilevel) Structured Linear Systems
Cited in
(15)- Sparse matrix approximations for multigrid methods
- Symbol approach in a signal-restoration problem involving block Toeplitz matrices
- A note on the eigenvalues of \(g\)-circulants (and of \(g\)-Toeplitz, \(g\)-Hankel matrices)
- Multigrid methods for Toeplitz matrices
- Asymptotic spectra of large (grid) graphs with a uniform local structure. II: Numerical applications
- 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
- scientific article; zbMATH DE number 1617964 (Why is no real title available?)
- 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)
