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

DOI10.1016/J.LAA.2015.08.021zbMATH Open1391.65071arXiv1404.5332OpenAlexW1814407173MaRDI QIDQ5962489FDOQ5962489

Stefano Serra Capizzano, Dimitrios Noutsos, P. Vassalos

Publication date: 12 February 2016

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

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.

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

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

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)

Cites Work

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

Cited In (8)

• 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
• Title not available (Why is that?)
• The Spectra of Preconditioned Toeplitz Matrix Sequences Can Have Gaps
• Preconditioning technique based on sine transformation for nonlocal Helmholtz equations with fractional Laplacian
• Spectral Analysis of Nonsymmetric Quasi-Toeplitz matrices with Applications to Preconditioned Multistep Formulas
• Two-parameter modified matrix splitting iteration method for Helmholtz equation
• 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)