Recursive-Based PCG Methods for Toeplitz Systems with Nonnegative Generating Functions

@article{Ng2002RecursiveBasedPM,
  title={Recursive-Based PCG Methods for Toeplitz Systems with Nonnegative Generating Functions},
  author={Michael K. P. Ng and Hai-wei Sun and Xiao-Qing Jin},
  journal={SIAM J. Sci. Comput.},
  year={2002},
  volume={24},
  pages={1507-1529},
  url={https://api.semanticscholar.org/CorpusID:8665530}
}
If f is a nonnegative, bounded, and piecewise continuous even function with a finite number of zeros of even order, the spectra of the preconditioned matrices are uniformly bounded except for a fixed number of outliers, and the conjugate gradient method, when applied to solving the precONDitioned system, converges very quickly.
View via Publisher
hub.hku.hk
16 Citations
Highly Influential Citations
1
Background Citations
2
Methods Citations
5
Results Citations
1

Figures and Tables from this paper

16 Citations

Recursive self preconditioning method based on Schur complement for Toeplitz matrices

In this paper, we propose to solve the Toeplitz linear systems Tnx = b by a recursive-based method. The method is based on repeatedly dividing the original problem into two subproblems that involve…

An approximate inverse preconditioner for Toeplitz systems with multiple right-hand sides

On Inexact Preconditioners for Nonsymmetric Matrices

The spectral properties of the preconditioned matrices and the finite-step termination properties of Theoretical Krylov subspace iteration methods with an optimal or Galerkin property are described with respect to these preconditionsers.

Block Diagonal and Schur Complement Preconditioners for Block-Toeplitz Systems with Small Size Blocks

It is shown that for some block-Toeplitz matrices, the spectra of the preconditioned matrices are uniformly bounded except for a fixed number of outliers where this fixed number depends only on the size of the block.

An Inexact Shift-and-Invert Arnoldi Algorithm for Large Non-Hermitian Generalised Toeplitz Eigenproblems

This work presents a practical stopping criterion for their numerical solution, and proposes an inexact shift-and-invert Arnoldi algorithm for the generalised Toeplitz eigen- problem.

A new parameter-free method for Toeplitz systems of weakly nonlinear equations

Approximate inverse-free preconditioners for Toeplitz matrices

Improved Schur complement preconditioners for block-Toeplitz systems with small size blocks

Shift-Invert Arnoldi Approximation to the Toeplitz Matrix Exponential

The shift-invert Arnoldi method is employed to generate an orthonormal basis from the Krylov subspace corresponding to a real Toeplitz matrix and an initial vector and results are given to demonstrate the efficiency of the method.

Shift‐invert Lanczos method for the symmetric positive semidefinite Toeplitz matrix exponential

The Lanczos method with shift‐invert technique is exploited to approximate the symmetric positive semidefinite Toeplitz matrix exponential. The complexity is lowered by the Gohberg–Semencul formula…

41 References

The best circulant preconditioners for Hermitian Toeplitz systems II: The multiple-zero case

The main aim of this paper is to give a complete convergence proof of the conjugate gradient method for this class of generating functions where the generating functions have multiple zeros.

Convergence of the Multigrid Method of Ill-conditioned Block Toeplitz Systems

For a class of block Toeplitz matrices, it is shown that the convergence factor of the two-grid method (TGM) is uniformly bounded below 1 independent of mn and the full MGM has convergence factor depending only on the number of levels.

Preconditioners for Ill-Conditioned Toeplitz Systems Constructed from Positive Kernels

New w-circulant preconditioners are constructed without explicit knowledge of the generating function f by approximating f by its convolution f * KN with a suitable positive reproducing kernel KN by the restriction to positive kernels.

Multigrid Method for Ill-Conditioned Symmetric Toeplitz Systems

It is shown that the convergence factor of the two-grid method is uniformly bounded below one independent of n, and the full multigrid method has convergence factor depending only on the number of levels.

Preconditioning Strategies for Hermitian Toeplitz Systems with Nondefinite Generating Functions

New preconditioning techniques for the solution by the preconditionsed conjugate gradient (PCG) method of Hermitian Toeplitz systems with real and nondefinite generating functions are presented and the convergence speed is shown to be independent of the dimension of the involved matrices.

A Levinson-Galerkin Algorithm for Regularized Trigonometric Approximation

A multilevel algorithm that recursively adapts to the least squares solution of suitable degree for trigonometric least squares approximation is derived and demonstrated by applying it in echocardiography to the recovery of the boundary of the left ventricle of the heart.

Circulant preconditioners for Toeplitz matrices with piecewise continuous generating functions

If instead the generating function is only piecewise continuous, then for all [epsilon] sufficiently small, there are O(log n) eigenvalues of C[sup [minus]1][ sub n]T[sub n] that lie outside the interval (1 - [ep silon], 1 + [epSilon]).

Fast Iterative Solvers for Toeplitz-Plus-Band Systems

The authors prove that if $A_n $ is generated by a nonnegative piecewise continuous function and $B_n$ is positive semidefinite, then there exists a band matrix, C_n, with bandwidth independent of n, such that the spectra of A_n + B_n are uniformly bounded by a constantindependent of n.

Numerische Mathematik Convergence analysis of two-grid methods for elliptic Toeplitz and PDEs Matrix-sequences

By extending the latter approach, this work performs a complete analysis of convergence of the TGM under the sole assumption that f is nonnegative and with a zero at $x^0=0$ of finite order.

Spectral and Computational Analysis of Block Toeplitz Matrices Having Nonnegative Definite Matrix-Valued Generating Functions

A Szegö-style theorem is proved concerning the spectra of the preconditioned matrices of the Hermitian block Toeplitz matrices with m × m blocks generated by a hermitian matrix-valued generating function f ∈ L1([−π, π], Cm×m).