Essential spectral equivalence via multiple step preconditioning and applications to ill conditioned Toeplitz matrices

DOI10.1016/J.LAA.2015.08.021MaRDI QIDQ5962489zbMATH OpenOpenAlexFDO

Authors Dimitrios Noutsos, Stefano Serra Capizzano, P. Vassalos

Publication date 12 February 2016

Published in Linear Algebra and its Applications (Search for Journal in Brave)

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

zbMATH Keywords

preconditioningspectral analysisToeplitzPCG method\(\tau\) matrices

Mathematics Subject Classification ID

Numerical computation of eigenvalues and eigenvectors of matrices (65F15) Preconditioners for iterative methods (65F08) Iterative numerical methods for linear systems (65F10) Numerical computation of matrix norms, conditioning, scaling (65F35)

Abstract: In this note, we study the fast solution of Toeplitz linear systems with coefficient matrix $T_n(f)$, where the generating function $f$ is nonnegative and has a unique zero at zero of any real positive order $heta$. As preconditioner we choose a matrix ${au}_n(f)$ belonging to the so-called $au$ algebra, which is diagonalized by the sine transform associated to the discrete Laplacian. In previous works, the spectral equivalence of the matrix sequences ${{au}_n(f)}_n$ and ${T_n(f)}_n$ was proven under the assumption that the order of the zero is equal to $2$: in other words the preconditioned matrix sequence ${{au}_n^{-1}(f)T_n(f)}_n$ has eigenvalues, which are uniformly away from zero and from infinity. Here we prove a generalization of the above result when $heta<2$. Furthermore, by making use of multiple step preconditioning, we show that the matrix sequences ${{au}_n(f)}_n$ and ${T_n(f)}_n$ are essentially spectrally equivalent for every $heta>2$, i.e., for every $heta>2$, there exist $m_{h}eta$ and a positive interval $$ such that all the eigenvalues of ${{au}_n^{-1}(f)T_n(f)}_n$ belong to this interval, except at most $m_{h}eta$ outliers larger than $$. Such a nice property, already known only when $heta$ is an even positive integer greater than 2, is coupled with the fact that the preconditioned sequence has an eigenvalue cluster at one, so that the convergence rate of the associated preconditioned conjugate gradient method is optimal. As a conclusion we discuss possible generalizations and we present selected numerical experiments.

Recommendations

• New band Toeplitz preconditioners for ill-conditioned symmetric positive definite Toeplitz systems
• scientific article; zbMATH DE number 1974620
• scientific article; zbMATH DE number 1092922
• Iterative methods for ill-conditioned Toeplitz matrices
• Analysis of Preconditioning Techniques for Ill-Conditioned Toeplitz Matrices

Cites work

• scientific article; zbMATH DE number 1350351 (Why is no real title available?)
• scientific article; zbMATH DE number 1974620 (Why is no real title available?)
• scientific article; zbMATH DE number 2118874 (Why is no real title available?)
• A unifying approach to abstract matrix algebra preconditioning
• An Introduction to Iterative Toeplitz Solvers
• Analysis of Preconditioning Techniques for Ill-Conditioned Toeplitz Matrices
• Any Circulant-Like Preconditioner for Multilevel Matrices Is Not Superlinear
• Asymptotic Spectra of Hermitian Block Toeplitz Matrices and Preconditioning Results
• C. G. preconditioning for Toeplitz matrices
• How to prove that a preconditioner cannot be superlinear
• Isogeometric analysis. Toward integration of CAD and FEA
• Iterative methods for ill-conditioned Toeplitz matrices
• Matrix algebra preconditioners for multilevel Toeplitz systems do not insure optimal convergence rate
• Multi-iterative methods
• New PCG based algorithms for the solution of Hermitian Toeplitz systems
• On the rate of convergence of the preconditioned conjugate gradient method
• Preconditioning block Toeplitz matrices
• Robust and optimal multi-iterative techniques for Iga Galerkin linear systems
• Robust and optimal multi-iterative techniques for Iga collocation linear systems
• Spectral and computational analysis of block Toeplitz matrices having nonnegative definite matrix-valued generating functions
• Spectral and computational properties of band symmetric Toeplitz matrices
• Superlinear PCG methods for symmetric Toeplitz systems
• Superlinear convergence for PCG using band plus algebra preconditioners for Toeplitz systems
• Symbol approach in a signal-restoration problem involving block Toeplitz matrices

Cited in

(8)

• Two-parameter modified matrix splitting iteration method for Helmholtz equation
• Spectral Analysis of Nonsymmetric Quasi-Toeplitz matrices with Applications to Preconditioned Multistep Formulas
• scientific article; zbMATH DE number 1974620 (Why is no real title available?)
• Band Toeplitz preconditioners for non-symmetric real Toeplitz systems by preconditioned GMRES method
• A \(\tau\)-preconditioner for space fractional diffusion equation with non-separable variable coefficients
• Preconditioning technique based on sine transformation for nonlocal Helmholtz equations with fractional Laplacian
• The Spectra of Preconditioned Toeplitz Matrix Sequences Can Have Gaps
• Spectral analysis for preconditioning of multi-dimensional Riesz fractional diffusion equations

This page was built for publication: Essential spectral equivalence via multiple step preconditioning and applications to ill conditioned Toeplitz matrices

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