Conjugate Gradient Methods for Toeplitz Systems

DOI10.1137/S0036144594276474zbMath0863.65013OpenAlexW2005041367MaRDI QIDQ4714415

Raymond Honfu Chan, Michael Kwok-Po Ng

Publication date: 8 June 1997

Published in: SIAM Review (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/s0036144594276474

zbMATH Keywords

complexityintegral equationsfast Fourier transformfilteringtime series analysisToeplitz matricescirculant matricespreconditioned conjugate gradient methodsfast sine transformqueuing problemssignal and image restoration

Mathematics Subject Classification ID

Computing methodologies for image processing (68U10) Numerical methods for integral equations (65R20) Finite element, Rayleigh-Ritz and Galerkin methods for boundary value problems involving PDEs (65N30) Iterative numerical methods for linear systems (65F10) Numerical computation of matrix norms, conditioning, scaling (65F35) Probabilistic methods, stochastic differential equations (65C99)

Related Items (only showing first 100 items - show all)

Solving composite sum of powers via Padé approximation and orthogonal polynomials with application to optimal PWM problem ⋮ Spectral behavior of preconditioned non-Hermitian multilevel block Toeplitz matrices with matrix-valued symbol ⋮ Application of two-dimensional hat functions for solving space-time integral equations ⋮ Every matrix is a product of Toeplitz matrices ⋮ Computations with infinite Toeplitz matrices and polynomials ⋮ Structured matrices and Newton's iteration: unified approach ⋮ Matrix algebra preconditioners for multilevel Toeplitz matrices are not superlinear ⋮ Four short stories about Toeplitz matrix calculations ⋮ Block band Toeplitz preconditioners derived from generating function approximations: analysis and applications ⋮ The GLT class as a generalized Fourier analysis and applications ⋮ Fast superoptimal preconditioning of multiindex Toeplitz matrices ⋮ Preconditioners for elliptic problems via non-uniform meshes ⋮ Band preconditioners for block-Toeplitz -- Toeplitz-block systems ⋮ Preconditioned iterative methods for fractional diffusion equation ⋮ A new solver for the elastic normal contact problem using conjugate gradients, deflation, and an FFT-based preconditioner ⋮ Fast finite difference methods for space-fractional diffusion equations with fractional derivative boundary conditions ⋮ A fast method for a generalized nonlocal elastic model ⋮ FFT-based exponentially weighted recursive least squares computations ⋮ A \(V\)-cycle multigrid for multilevel matrix algebras: proof of optimality ⋮ The solution of ill-conditioned symmetric Toeplitz systems via two-grid and wavelet methods ⋮ Matrix algebra preconditioners for multilevel Toeplitz systems do not insure optimal convergence rate ⋮ Discrete fundamental solution preconditioning for hyperbolic systems of PDE ⋮ Equivalent conditions for convergence of splittings of non-Hermitian indefinite matrices ⋮ Inverse Toeplitz preconditioners for ill-posed problems ⋮ DFT representations of Toeplitz-plus-Hankel Bézoutians with application to fast matrix-vector multiplication ⋮ Korovkin theorems and linear positive Gram matrix algebra approximations of Toeplitz matrices ⋮ Kronecker product and SVD approximations in image restoration ⋮ Solution of Toeplitz normal equations by sine transform based preconditioning ⋮ \(h\)-space structure in matrix displacement formulas ⋮ Block Toeplitz matrices and preconditioning ⋮ A practical algorithm to design fast and optimal band-Toeplitz preconditioners for Hermitian Toeplitz systems ⋮ Computing eigenvalues and singular values of Toeplitz matrices ⋮ Scientific applications of iterative Toeplitz solvers ⋮ A fast stationary iterative method for a partial integro-differential equation in pricing options ⋮ The spectral approximation of multiplication operators via asymptotic (structured) linear algebra ⋮ How real is your matrix? ⋮ An approximate inverse preconditioner for Toeplitz systems with multiple right-hand sides ⋮ A circulant preconditioner for fractional diffusion equations ⋮ BTTB preconditioners for BTTB systems ⋮ Multigrid method for fractional diffusion equations ⋮ Erratum to: ``On the HSS iteration methods for positive definite Toeplitz linear systems ⋮ Modified SMS method for computing outer inverses of Toeplitz matrices ⋮ On CSCS-based iteration methods for Toeplitz system of weakly nonlinear equations ⋮ Using the Sherman-Morrison-Woodbury inversion formula for a fast solution of tridiagonal block Toeplitz systems ⋮ Multigrid methods for Toeplitz linear systems with different size reduction ⋮ Band plus algebra preconditioners for two-level Toeplitz systems ⋮ Tri-diagonal preconditioner for pricing options ⋮ A new preconditioner for the interface system arising in a fast Helmholtz solver ⋮ An \(O(N \log ^{2}N)\) alternating-direction finite difference method for two-dimensional fractional diffusion equations ⋮ A fast and faithful collocation method with efficient matrix assembly for a two-dimensional nonlocal diffusion model ⋮ On parameterized inexact Uzawa methods for generalized saddle point problems ⋮ Strang-type preconditioners for solving fractional diffusion equations by boundary value methods ⋮ Second-order LOD multigrid method for multidimensional Riesz fractional diffusion equation ⋮ A composite preconditioner for the electromagnetic scattering from a large cavity ⋮ Fast numerical method for crack problem in the porous elastic material ⋮ Fast transform based preconditioners for 2D finite-difference frequency-domain. Waveguides and periodic structures ⋮ Stability of the notion of approximating class of sequences and applications ⋮ Accelerated circulant and skew circulant splitting methods for Hermitian positive definite Toeplitz systems ⋮ A divide-and-conquer fast finite difference method for space-time fractional partial differential equation ⋮ A class of iteration methods based on the HSS for Toeplitz systems of weakly nonlinear equations ⋮ An efficient nonconvex regularization for wavelet frame and total variation based image restoration ⋮ Circulant preconditioned iterations for fractional diffusion equations based on Hermitian and skew-Hermitian splittings ⋮ Kriging and spatial design accelerated by orders of magnitude: combining low-rank covariance approximations with FFT-techniques ⋮ Fast preconditioned iterative methods for finite volume discretization of steady-state space-fractional diffusion equations ⋮ Multigrid methods: grid transfer operators and subdivision schemes ⋮ A space-time fractional phase-field model with tunable sharpness and decay behavior and its efficient numerical simulation ⋮ A preconditioned fast finite difference method for space-time fractional partial differential equations ⋮ Time-invariant Radon transform by generalized Fourier slice theorem ⋮ A fast, preconditioned conjugate gradient Toeplitz solver ⋮ Factorization strategies for third-order tensors ⋮ Antireflective boundary conditions for deblurring problems ⋮ Modified HSS iteration methods for a class of complex symmetric linear systems ⋮ A direct method to solve block banded block Toeplitz systems with non-banded Toeplitz blocks ⋮ Inverse product Toeplitz preconditioners for non-Hermitian Toeplitz systems ⋮ Image restoration by cosine transform-based iterative regularization ⋮ On HSS and AHSS iteration methods for nonsymmetric positive definite Toeplitz systems ⋮ Product-type block preconditioners for electromagnetic cavity problems ⋮ Block preconditioners with circulant blocks for general linear systems ⋮ A modified T. Chan's preconditioner for Toeplitz systems ⋮ A fast numerical solution method for two dimensional Fredholm integral equations of the second kind based on piecewise polynomial interpolation ⋮ Approximate inverse-free preconditioners for Toeplitz matrices ⋮ A fast numerical algorithm for a basic dual integral equation of the flapping wing in a flow of non-viscous incompressible fluid ⋮ Preconditioned iterative methods for space-time fractional advection-diffusion equations ⋮ A preconditioned fast finite volume scheme for a fractional differential equation discretized on a locally refined composite mesh ⋮ Fast numerical solution for fractional diffusion equations by exponential quadrature rule ⋮ Improved Schur complement preconditioners for block-Toeplitz systems with small size blocks ⋮ On preconditioned and relaxed AVMM methods for quadratic programming problems with equality constraints ⋮ On the HSS iteration methods for positive definite Toeplitz linear systems ⋮ Structured condition numbers of structured Tikhonov regularization problem and their estimations ⋮ A multivariate preconditioned conjugate gradient approach for maximum likelihood estimation in vector long memory processes ⋮ A framework for polynomial preconditioners based on fast transforms. I: Theory ⋮ A total least squares method for Toeplitz systems of equations ⋮ Application of FFT-based algorithms for large-scale universal kriging problems ⋮ Fast and high-order accuracy numerical methods for time-dependent nonlocal problems in \(\mathbb{R}^2\) ⋮ Efficient iterative solution of the three-dimensional Helmholtz equation ⋮ The generalized superoptimal preconditioner ⋮ Representations of Toeplitz-plus-Hankel martrices using trigonometric transformations with application to fast matrix-vector multiplication ⋮ A note on preconditioning for \(M\)-matrix ⋮ BCCB preconditioners for solving linear systems from delay differential equations ⋮ Incomplete circulant and skew-circulant splitting iteration method for time-dependent space fractional diffusion equations

This page was built for publication: Conjugate Gradient Methods for Toeplitz Systems