Iterative Methods For Toeplitz Systems

by Ng, Michael K.

• ISBN13: 9780198504207
• ISBN10: 0198504209
• Format: Hardcover
• Copyright: 2004-12-16
• Publisher: Oxford University Press

Summary

Toeplitz and Toeplitz-related systems arise in a variety of applications in mathematics and engineering, especially in signal and image processing. This book deals primarily with iterative methods for solving Toeplitz and Toeplitz-related linear systems, discussing both the algorithms and their convergence theories. A basic knowledge of real analysis, elementary numerical analysis and linear algebra is assumed. The first part of the book (chapters one and two) gives a brief review of some terms and results in linear algebra and the conjugate gradient method, which are important topics for handling the mathematics later on in the book. The second part of the book (chapters three to seven) presents the theory of using iterative methods for solving Toeplitz and Toeplitz-related systems. The third part of the book (chapters eight to twelve) presents recent results from applying the use of iterative methods in different fields of applications, such as partial differential equations, signal and image processing, integral equations and queuing networks. These chapters provide research and application-oriented readers with a thorough understanding of using iterative methods, enabling them not only to apply these methods to the problems discussed but also to derive and analyze new methods for other types of problems and applications.

Author Biography

Michael K. Ng is an Associate Professor in the Department of Mathematics and also Adjunct Research Fellow in the E-Business Technology Institute at The University of Hong Kong.

Table of Contents

I INTRODUCTION
1 Notations and definitions	3	(9)
1.1 Vectors	3	(1)
1.2 Matrices	4	(3)
1.3 Matrix norms	7	(1)
1.4 Eigenvalues	8	(2)
1.5 Singular value decomposition	10	(1)
1.6 Exercises	10	(2)
2 Iterative methods	12	(13)
2.1 Stationary iterative methods	12	(1)
2.2 Conjugate gradient iterations	13	(4)
2.3 Preconditioning	17	(1)
2.4 Conjugate gradient least squares	18	(2)
2.5 Exercises	20	(5)
II THEORY
3 Toeplitz systems	25	(23)
3.1 Toeplitz matrices	25	(2)
3.1.1 An example of Toeplitz system	25	(2)
3.2 Direct methods	27	(10)
3.2.1 The Levinson Durbin algorithm	27	(2)
3.2.2 The Gohberg Sernencul formula	29	(1)
3.2.3 The fast Cholesky factorization	29	(1)
3.2.4 Displacement rank	30	(1)
3.2.5 The Schur algorithm	31	(2)
3.2.6 Superfast direct Toeplitz solvers	33	(2)
3.2.7 Look-ahead algorithms	35	(1)
3.2.8 Stability	36	(1)
3.3 Iterative methods	37	(1)
3.4 Toeplitz matrix-vector multiplications	37	(3)
3.4.1 Diagonalization of circulant matrices	37	(1)
3.4.2 Diagonalization of {ω}-circulant matrices	38	(1)
3.4.3 Computation of a Toeplitz matrix	39	(1)
3.5 Generating functions	40	(5)
3.6 Conjugate gradient methods for Toeplitz systenis	45	(1)
3.7 Exercises	46	(1)
3.8 Notes	47	(1)
4 Circulant preconditioners	48	(32)
4.1 Historical remarks	48	(1)
4.2 Complexity	48	(1)
4.3 Strang's preconditioner	49	(7)
4.3.1 Generalized Strang preconditioner	56	(1)
4.4 T. Chan's preconditioner	56	(6)
4.4.1 Huckle's preconditioners	61	(1)
4.5 Other circulant-type preconditioners	62	(3)
4.5.1 Preconditioners by embedding	62	(1)
4.5.2 Preconditioners by minimization of norms	62	(2)
4.5.3 {ω}-circulant preconditioners	64	(1)
4.6 A numerical example	65	(1)
4.7 Circulant preconditioners from kernel functions	65	(6)
4.8 Piecewise continuous generating functions	71	(3)
4.9 Non-Hermitian Toeplitz systems	74	(2)
4.10 Exercises	76	(2)
4.11 Notes	78	(2)
5 Non-circulant type preconditioners	80	(14)
5.1 Optimal transform-based preconditioners	80	(8)
5.1.1 Sine transform-based preconditioner	81	(5)
5.1.2 Cosine transform-based preconditioner	86	(1)
5.1.3 Hartley transform-based preconditioner	87	(1)
5.2 Toeplitz preconditioners	88	(3)
5.3 Exercises	91	(1)
5.4 Notes	92	(2)
6 Ill-conditioned Toeplitz systems	94	(40)
6.1 Introduction	94	(1)
6.2 Toeplitz-type preconditioners	94	(4)
6.3 Circulant-type preconditioners	98	(4)
6.4 The best circulant preconditioners	102	(10)
6.4.1 Construction of the preconditioner	103	(1)
6.4.2 Properties of the kernel function	104	(5)
6.4.3 Spectra of the preconditioned matrices	109	(3)
6.5 Numerical examples	112	(2)
6.6 Multigrid methods	114	(16)
6.6.1 Weakly diagonally dominant Toeplitz matrices	119	(3)
6.6.2 More general Toeplitz matrices	122	(1)
6.6.3 Convergence results for full multigrid method	123	(3)
6.6.4 Computational cost	126	(1)
6.6.5 Richardson iteration as smoother	127	(3)
6.7 Recursive-based PCG methods	130	(1)
6.8 Exercises	131	(1)
6.9 Notes	132	(2)
7 Structured systems	134	(45)
7.1 Toeplitz-like systems	134	(8)
7.1.1 Normal equations of Toeplitz systems	135	(4)
7.1.2 Toeplitz-plus-Hankel systems	139	(3)
7.2 Toeplitz-plus-band systems	142	(1)
7.3 Block systems	143	(13)
7.3.1 Approximation operators for block matrices	143	(7)
7.3.2 Block preconditioners for general matrices	150	(1)
7.3.3 Quadrantally symmetric matrices	151	(3)
7.3.4 Separable matrices	154	(1)
7.3.5 Numerical examples	155	(1)
7.4 Toeplitz least squares problems	156	(16)
7.4.1 1D Toeplitz-block least squares problems	157	(3)
7.4.2 2D Toeplitz-block least squares problems	160	(10)
7.4.3 Numerical examples	170	(2)
7.5 Total least squares methods	172	(2)
7.6 Exercises	174	(1)
7.7 Notes	175	(4)
III APPLICATIONS
8 Applications to ODEs and PDEs	179	(32)
8.1 Introduction	179	(1)
8.2 Circulaut preconditioners for elliptic problems	180	(8)
8.3 Sine transform-based preconditioners	188	(5)
8.3.1 Two-dimensional irregular domains	191	(1)
8.3.2 Higher dimensional rectangular domains	192	(1)
8.4 A numerical example	193	(1)
8.5 Domain decomposition	194	(1)
8.6 Banded preconditioners for sine Galerkin systems	195	(4)
8.7 Numerical solutions of biharmonic equations	199	(2)
8.8 Hyperbolic and parabolic equations	201	(2)
8.9 Ordinary differential equations	203	(7)
8.9.1 Some families of BVMs	204	(1)
8.9.2 Preconditioners	205	(5)
8.10 Exercises	210	(1)
8.11 Notes	210	(1)
9 Applications to queueing networks	211	(27)
9.1 Introduction	211	(1)
9.2 Overflow queueing networks	211	(4)
9.3 Queueing networks with batch arrivals	215	(4)
9.4 Markov-modulated Poisson processes	219	(11)
9.4.1 Failure-prone manufacturing systems	227	(3)
9.5 Stochastic automata networks	230	(6)
9.5.1 Circulant, preconditioners for SAN	232	(4)
9.6 Exercises	236	(1)
9.7 Notes	237	(1)
10 Applications to signal processing	238	(1)
10.1 Introduction	238	(1)
10.2 Known statistics solution	239	(1)
10.3 Least squares filters	240	(4)
10.3.1 Linear phase least squares filters	242	(2)
10.4 Recursive least squares computations	244	(2)
10.5 Exponentially weighted least squares computation	246	(2)
10.6 Exercises	248	(1)
10.7 Notes	249	(1)
11 Applications to image processing	250	(1)
11.1 Introduction	250	(1)
11.2 The one-dimensional deblurring problem	250	(8)
11.2.1 The zero (Dirichlet) boundary conditions	252	(1)
11.2.2 Periodic boundary conditions	252	(1)
11.2.3 Neumann boundary conditions	253	(2)
11.2.4 Tikhonov regularization	255	(1)
11.2.5 A numerical example	256	(2)
11.3 High-resolution image reconstruction	258	(5)
11.3.1 Preconditioners	263	(1)
11.4 Total variation regularization	263	(7)
11.4.1 Cosine transform-based preconditioners	266	(1)
11.4.2 The product preconditioner	267	(2)
11.4.3 Numerical examples	269	(1)
11.5 Blind image restoration	270	(5)
11.5.1 Alternating minimization algorithm	274	(1)
11.5.2 A numerical example	275	(1)
11.6 Iterative regularization methods	275	(7)
11.6.1 Preconditioners	279	(2)
11.6.2 Symmetric indefinite conjugate gradient methods	281	(1)
11.6.3 Spatial-variant image restoration	282	(1)
11.7 Exercises	282	(1)
11.8 Notes	283	(2)
12 Applications to integral equations	285	(1)
12.1 Introduction	285	(1)
12.2 Wiener-Hopf equations	285	(7)
12.2.1 Circulant integral operators	286	(3)
12.2.2 Other circulant integral operators	289	(3)
12.3 Quadrature rules	292	(2)
12.3.1 A numerical example	293	(1)
12.4 Inverse lout problems	294	(1)
12.5 Thermal tomography	295	(4)
12.5.1 Regularization by the identity and Laplacian operators	296	(1)
12.5.2 Preconditioning	297	(2)
12.6 Boundary integral equations	299	(12)
12.6.1 The optimal circulant integral operator	303	(3)
12.6.2 Condition numbers of the preconditioned systems	306	(2)
12.6.3 Galerkin methods	308	(1)
12.6.4 A numerical example	309	(2)
12.7 Fast dense matrix methods	311	(12)
12.7.1 Optimal circulant preconditioners	315	(4)
12.7.2 A numerical example	319	(4)
12.8 Exercises	323	(1)
12.9 Notes	324	(1)
References	325	(23)
Index	348