An introduction to iterative Toeplitz solvers by Raymond Hon-Fu Chan, Xiao-Qing Jin

By Raymond Hon-Fu Chan, Xiao-Qing Jin

Toeplitz structures come up in numerous purposes in arithmetic, medical computing, and engineering, together with numerical partial and traditional differential equations, numerical strategies of convolution-type fundamental equations, desk bound autoregressive time sequence in facts, minimum attention difficulties up to the mark thought, approach identity difficulties in sign processing, and picture recovery difficulties in picture processing. This functional booklet introduces present advancements in utilizing iterative equipment for fixing Toeplitz platforms in response to the preconditioned conjugate gradient procedure. The authors concentrate on the $64000 points of iterative Toeplitz solvers and provides unique realization to the development of effective circulant preconditioners. purposes of iterative Toeplitz solvers to sensible difficulties are addressed, allowing readers to take advantage of the ebook s equipment and algorithms to unravel their very own difficulties. An appendix containing the MATLAB® courses used to generate the numerical effects is incorporated. scholars and researchers in computational arithmetic and medical computing will reap the benefits of this booklet.

Show description

Read Online or Download An introduction to iterative Toeplitz solvers PDF

Similar algorithms and data structures books

Problems on algorithms

Too usually the matter units in average set of rules texts are composed of small, idiosyncratic devices of busy-work and inappropriate questions - forcing teachers into the time-consuming activity of discovering or composing extra difficulties. Designed to fill that hole, this complement presents an in depth and sundry number of precious, sensible difficulties at the layout, research, and verification of algorithms.

Practical Handbook of Genetic Algorithms: Applications

The math hired by way of genetic algorithms (GAs)are one of the most fun discoveries of the previous couple of a long time. From the development of a uncomplicated GA via to complicated implementation, the sensible instruction manual of Genetic Algorithms stands as an important resource of compiled wisdom from revered specialists worldwide.

Multimedia Database Management Systems

A complete, systematic method of multimedia database administration structures. It offers equipment for dealing with the expanding calls for of multimedia databases and their inherent layout and structure matters, and covers tips on how to create a good multimedia database via integrating a few of the details indexing and retrieval tools on hand.

Additional info for An introduction to iterative Toeplitz solvers

Example text

Chan’s preconditioner. 8. Let f be a function in the Wiener class. Then lim ρ [s(Tn ) − cF (Tn )] = 0, n→∞ where ρ[·] denotes the spectral radius. Proof. 6), it is clear that Bn ≡ s(Tn ) − cF (Tn ) is circulant with entries  k   (tk − tk−n ), 0 ≤ k ≤ m, bk = n   n − k (tk−n − tk ), m < k ≤ n − 1. n Here for simplicity, we assume n = 2m. 6), the jth eigenvalue λj (Bn ) of Bn 2πijk n−1 is given by k=0 bk e n , and we therefore have m λj (Bn ) ≤ 2 k=1 k (|tk | + |tk−n |). n 24 Chapter 2. Circulant preconditioners This implies m ρ[Bn ] ≤ 2 k=1 k |tk | + 2 n n−1 |tk |.

Chan and Yeung later used Jackson’s theorems [35, pp. 5. 6 (R. Chan and Yeung [31]). Suppose f is a Lipschitz function of order ν for 0 < ν ≤ 1, or f has a continuous νth derivative for ν ≥ 1. Then there exists a constant c > 0 which depends only on f and ν such that for large n, k |||e(2k) ||| c log2 p ≤ . 2. 2 21 Optimal (circulant) preconditioner T. Chan in [33] proposed a specific circulant preconditioner called the optimal circulant preconditioner for solving Toeplitz systems. His idea was then extended in [22, 82] for general matrices.

Moreover, all preconditioned systems converge at the same rate for large n. 7. 1. 13)). 1 the spectra of the matrices Tn , (s(Tn ))−1 Tn , (cF (Tn ))−1 Tn , and (tF (Tn ))−1 Tn for n = 32. We can see that the spectra of the preconditioned matrices are in a small interval around 1, except for few outliers, and that all the eigenvalues are well separated away from 0. 1. Preconditioners used and number of iterations. n 32 64 128 256 512 1024 I 15 17 19 20 21 22 s(Tn ) 7 7 7 7 7 8 cF (Tn ) 6 7 7 7 7 8 tF (Tn ) 8 7 7 7 7 7 34 Chapter 2.

Download PDF sample

Rated 5.00 of 5 – based on 29 votes