Multigrid Method for Ill-Conditioned Symmetric Toeplitz Systems
The goal of this paper is to efficiently solve Toeplitz systems with generating functions that are nonnegative, even and have zeroes in their range. The authors develop an idea previously examined by \textit{G. Fiorentino} and \textit{S. Serra} [ibid. 17, No. 5, 1068-1081 (1996; Zbl 0858.65039)] that consists in applying the multigrid method to those ill-conditioned systems. Both, the two-grid (TGM) and the multiple-grid (MGM) approaches are discussed. After proving convergence for TGM when using the damped-Jacobi method as smoothing operator, convergence for MGM is established as well. As to the computational cost, it is shown that it is \(O(n \log n)\) per iteration and about four times the cost involved in the circulant preconditioned conjugate gradient methods (CGM) or the band-Toeplitz preconditioned CGM. The examples examined show that convergence is achieved much faster than in the former CGM, yielding a lower computational cost. On the other hand, the overall computational cost appears to be higher when using MGM than when applying the band-Toeplitz CGM. However, it is pointed out that the convergence rate of CGM can be very much improved with other smoothing methods, such as red-black Jacobi, block-Jacobi and Gauss-Seidel. Moreover, there are functions for which MGM can be applied while band-Toeplitz CGM cannot. The results exposed in the paper show the interest of further developing the study of the MGM in order to numerically solve ill-conditioned Toeplitz systems.
- A note on the convergence of the two-grid method for Toeplitz systems
- Convergence analysis of two-grid methods for elliptic Toeplitz and PDEs matrix-sequences
- Superlinear PCG methods for symmetric Toeplitz systems
- A survey of preconditioners for ill-conditioned Toeplitz systems
- Superlinear convergence for PCG using band plus algebra preconditioners for Toeplitz systems
- Convergence of the multigrid method for ill-conditioned block Toeplitz systems
- A method of speeding TGM for solving Toeplitz systems
- Multigrid preconditioning and Toeplitz matrices
- Band-times-circulant preconditioners for non-symmetric Toeplitz systems
- Optimal, quasi-optimal and superlinear band-Toeplitz preconditioners for asymptotically ill-conditioned positive definite Toeplitz systems
- A Multigrid Tutorial, Second Edition
- A Proposal for Toeplitz Matrix Calculations
- An Optimal Circulant Preconditioner for Toeplitz Systems
- Convergence Estimates for Multigrid Algorithms without Regularity Assumptions
- Fast Band-Toeplitz Preconditioners for Hermitian Toeplitz Systems
- scientific article; zbMATH DE number 3988038 (Why is no real title available?)
- Multigrid Methods for Symmetric Positive Definite Block Toeplitz Matrices with Nonnegative Generating Functions
- Multigrid methods for Toeplitz matrices
- Toeplitz Equations by Conjugate Gradients with Circulant Preconditioner
- Toeplitz Preconditioners for Toeplitz Systems with Nonnegative Generating Functions
- Multigrid methods for indefinite Toeplitz matrices
- Multigrid methods for Toeplitz matrices
- Matrix algebra preconditioners for multilevel Toeplitz matrices are not superlinear
- A note on the convergence of the two-grid method for Toeplitz systems
- Function-based block multigrid strategy for a two-dimensional linear elasticity-type problem
- Spectral analysis and multigrid preconditioners for two-dimensional space-fractional diffusion equations
- Uniform convergence of V-cycle multigrid algorithms for two-dimensional fractional Feynman-Kac equation
- A hybrid preconditioner of banded matrix approximation and alternating direction implicit iteration for symmetric Sinc--Galerkin linear systems
- Two-grid methods for Hermitian positive definite linear systems connected with an order relation
- Gaussian radial basis function and quadrature sinc method for two-dimensional space-fractional diffusion equations
- Extensions and analysis of worst-case parameter in weighted Jacobi's method for solving second order implicit PDEs
- Uniform convergence of V-cycle multigrid finite element method for one-dimensional time-dependent fractional problem
- Generalized grid transfer operators for multigrid methods applied on Toeplitz matrices
- A nonlinear multigrid method for total variation minimization from image restoration
- Multigrid solution techniques for anisotropic structured linear systems
- Multigrid methods for block Toeplitz matrices with small size blocks
- On a nonlinear multigrid algorithm with primal relaxation for the image total variation minimisation
- Multigrid methods for anisotropic BTTB systems
- A fast second-order scheme for nonlinear Riesz space-fractional diffusion equations
- A method of speeding TGM for solving Toeplitz systems
- A new semi-smooth Newton multigrid method for control-constrained semi-linear elliptic PDE problems
- Multigrid methods for (multilevel) structured matrices associated with a symbol and related applications
- A semismooth Newton multigrid method for constrained elliptic optimal control problems
- MGM optimal convergence for certain (multilevel) structured linear systems
- An algebraic generalization of local Fourier analysis for grid transfer operators in multigrid based on Toeplitz matrices
- Optimal, quasi-optimal and superlinear band-Toeplitz preconditioners for asymptotically ill-conditioned positive definite Toeplitz systems
- A splitting preconditioner for Toeplitz-like linear systems arising from fractional diffusion equations
- Preconditioned iterative methods for fractional diffusion equation
- Multigrid method for fractional diffusion equations
- scientific article; zbMATH DE number 1086533 (Why is no real title available?)
- Multigrid methods for Toeplitz linear systems with different size reduction
- Spectral Analysis and Multigrid Methods for Finite Volume Approximations of Space-Fractional Diffusion Equations
- Second-order LOD multigrid method for multidimensional Riesz fractional diffusion equation
- How to prove that a preconditioner cannot be superlinear
- Multigrid Methods for Symmetric Positive Definite Block Toeplitz Matrices with Nonnegative Generating Functions
- Multigrid methods for block‐Toeplitz linear systems: convergence analysis and applications
- Spectral analysis for preconditioning of multi-dimensional Riesz fractional diffusion equations
- A multigrid method for nonlocal problems: non-diagonally dominant or Toeplitz-plus-tridiagonal systems
- Convergence analysis of a multigrid method for a nonlocal model
- Multigrid with FFT smoother for a simplified 2D frictional contact problem
- A Symbol-Based Analysis for Multigrid Methods for Block-Circulant and Block-Toeplitz Systems
- Convergence of the multigrid method for ill-conditioned block Toeplitz systems
- The solution of ill-conditioned symmetric Toeplitz systems via two-grid and wavelet methods
- A note on algebraic multigrid methods for the discrete weighted Laplacian
- A Mixed-Type Circulant Preconditioner for a Nonlocal Elastic Model
- Symbol based convergence analysis in multigrid methods for saddle point problems
- An aggregation-based two-grid method for multilevel block Toeplitz linear systems
- Band plus algebra preconditioners for two-level Toeplitz systems
- Fast algebraic multigrid for block-structured dense systems arising from nonlocal diffusion problems
- Spectral analysis of -preconditioners for two-level Toeplitz systems with applications in nonlocal diffusion models
- A smoothing analysis for multigrid methods applied to tempered fractional problems
- Analysis on aggregation and block smoothers in multigrid methods for block Toeplitz linear systems
- Spectral analysis and structure preserving preconditioners for fractional diffusion equations
- A V-cycle multigrid for multilevel matrix algebras: proof of optimality
- An accelerated algebraic multigrid algorithm for total-variation denoising
This page was built for publication: Multigrid Method for Ill-Conditioned Symmetric Toeplitz Systems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4389255)
