Structured Matrices and Polynomials

by Pan, Victor

• ISBN13: 9780817642402
• ISBN10: 0817642404
• Format: Hardcover
• Copyright: 2001-12-01
• Publisher: Birkhauser

Summary

Structured matrices serve as a natural bridge between the areas of algebraic computations with polynomials and numerical matrix computations, allowing cross-fertilization of both fields. This book covers most fundamental numerical and algebraic computations with Toeplitz, Hankel, Vandermonde, Cauchy, and other popular structured matrices. Throughout the computations, the matrices are represented by their compressed images, called displacements, enabling both a unified treatment of various matrix structures and dramatic saving of computer time and memory. The resulting superfast algorithms allow further dramatic parallel acceleration using FFT and fast sine and cosine transforms. Included are specific applications to other fields, in particular, superfast solutions to: various fundamental problems of computer algebra; the tangential Nevanlinna--Pick and matrix Nehari problems The primary intended readership for this work includes researchers, algorithm designers, and advanced graduate students in the fields of computations with structured matrices, computer algebra, and numerical rational interpolation. The book goes beyond research frontiers and, apart from very recent research articles, includes yet unpublished results. To serve a wider audience, the presentation unfolds systematically and is written in a user-friendly engaging style. Only some preliminary knowledge of the fundamentals of linear algebra is required. This makes the material accessible to graduate students and new researchers who wish to study the rapidly exploding area of computations with structured matrices and polynomials. Examples, tables, figures, exercises, extensive bibliography, and index lend this text to classroom use or self-study.

Table of Contents

Preface	ix
Glossary	xix
List of Tables	xxiii
List of Figures	xxv
Computations with Structured Matrices. Introduction	1	(22)
Application areas, our subjects and objectives	1	(2)
Four features of structured matrices	3	(1)
Displacements (some history, definitions and examples)	4	(3)
Compress, Operate, Decompress	7	(3)
Basic operations with compressed structured matrices	10	(2)
Two classes of superfast algorithms. The case of Toeplitz-like matrices	12	(1)
Unified algorithms and algorithmic transformations	13	(2)
Numerical and algebraic versions of structured matrix algorithms. Flops and ops	15	(3)
Numerical implementation	15	(2)
Algebraic implementation	17	(1)
Unification and separation of numerical and algebraic versions of algorithms	17	(1)
Computational complexity estimates	17	(1)
Limitations of the unification	18	(1)
Organization of the book	19	(1)
Notes	19	(2)
Exercises	21	(2)
Toeplitz/Hankel Matrix Structure and Polynomial Computations	23	(50)
Definitions and preliminaries	23	(2)
Fast Fourier transform (polynomial version)	25	(1)
Fast Fourier transform (matrix version)	26	(1)
Polynomial multiplication (with extensions)	27	(3)
Polynomial division and triangular Toeplitz matrix inversion	30	(3)
The algebra of f-circulant matrices. Diagonalizations by DFT's	33	(3)
Algebra of polynomials modulo a polynomial and the Frobenius matrix algebra	36	(4)
Polynomial gcd and the (Extended) Euclidean Algorithm	40	(6)
Applications and extensions of the EEA: modular division, rational function reconstruction, Pade approximation, and linear recurrence span	46	(4)
Matrix algorithms for rational interpolation and the EEA	50	(2)
Matrix approach to Pade approximation	52	(3)
Conclusion	55	(1)
Notes	56	(1)
Exercises	57	(4)
Appendix. Pseudocodes	61	(12)
Matrix Structures of Vandermonde and Cauchy Types and Polynomial and Rational Computations	73	(44)
Multipoint polynomial evaluation	73	(3)
Modular reduction and other extensions	76	(2)
Lagrange polynomial interpolation	78	(2)
Polynomial interpolation (matrix method), transposed Vandermonde matrices, and composition of polynomials	80	(2)
Chinese remainder algorithm, polynomial and rational Hermite interpolation, and decomposition into partial fractions	82	(6)
Cauchy matrix computations. Polynomial and rational interpolation and multipoint evaluation	88	(5)
Loss (erasure)-resilient encoding/decoding and structured matrices	93	(3)
Nevanlinna-Pick interpolation problems	96	(4)
Matrix Nehari Problem	100	(1)
Sparse multivariate polynomial interpolation	101	(2)
Diagonalization of Matrix Algebras. Polynomial Vandermonde Matrices and Discrete Sine and Cosine transforms	103	(5)
Conclusion	108	(1)
Notes	109	(4)
Exercises	113	(4)
Structured Matrices and Displacement Operators	117	(38)
Some definitions and basic results	118	(2)
Displacements of basic structured matrices	120	(2)
Inversion of the displacement operators	122	(3)
Compressed bilinear expressions for structured matrices	125	(9)
Partly regular displacement operators	134	(3)
Compression of a generator	137	(4)
SVD-based compression of a generator in numerical computations with finite precision	137	(2)
Elimination based compression of a generator in computations in an abstract field	139	(2)
Structured matrix multiplication	141	(3)
Algorithm design based on multiplicative transformation of operator matrix pairs	144	(3)
Algorithm design based on similarity transformations of operator matrices	147	(1)
Conclusion	148	(1)
Notes	149	(1)
Exercises	150	(5)
Unified Divide-and-Conquer Algorithm	155	(22)
Introduction. Our subject and results	155	(1)
Complete recursive triangular factorization (CRTF) of general matrices	156	(3)
Compressed computation of the CRTF of structured matrices	159	(2)
Simplified compression of Schur complements	161	(1)
Regularization via symmetrization	162	(2)
Regularization via multiplicative transformation with randomization	164	(3)
Randomization for structured matrices	167	(1)
Applications to computer algebra, algebraic decoding, and numerical rational computations	168	(2)
Conclusion	170	(1)
Notes	170	(2)
Exercises	172	(5)
Newton-Structured Numerical Iteration	177	(42)
Some definitions and preliminaries	178	(1)
Newton's iteration for root-finding and matrix inversion	179	(2)
Newton-Structured Iteration	181	(1)
Compression of the displacements by the truncation of their smallest singular values	182	(2)
Compression of displacement generators of approximate inverses by substitution	184	(2)
Bounds on the norms of the inverse operator	186	(3)
Introductory comments	186	(1)
Bounds via powering the operator matrices	187	(1)
The spectral approach	187	(1)
The bilinear expression approach	188	(1)
Estimation using the Frobenius norm	188	(1)
Initialization, analysis, and modifications of Newton's iteration for a general matrix	189	(4)
How much should we compress the displacements of the computed approximations?	193	(2)
Homotopic Newton's iteration	195	(6)
An outline of the algorithms	195	(1)
Symmetrization of the input matrix	196	(1)
Initialization of a homotopic process for the inversion of general and structured matrices	196	(2)
The choice of step sizes for a homotopic process. Reduction to the choice of tolerance values	198	(1)
The choice of tolerance values	199	(1)
Variations and parallel implementation of the Newton-Structured Iteration	199	(2)
Newton's iteration for a singular input matrix	201	(1)
Numerical experiments with Toeplitz matrices	202	(2)
Conclusion	204	(10)
Notes	214	(1)
Exercises	215	(4)
Newton Algebraic Iteration and Newton-Structured Algebraic Iteration	219	(22)
Some introductory remarks	219	(1)
Newton's algebraic iteration: generic algorithm	220	(3)
Specific examples of Newton's algebraic iteration	223	(3)
Newton's algebraic iteration for the inversion of general matrices	226	(1)
Newton and Newton-Structured Algebraic Iterations for characteristic polynomials and the Krylov spaces	227	(2)
Extensions of Krylov space computation	229	(1)
Inversion of general integer matrices and solution of general integer linear systems	230	(2)
Sequences of primes, random primes, and non-singularity of a matrix	232	(1)
Inversion of structured integer matrices	233	(3)
Conclusion	236	(1)
Notes	236	(1)
Exercises	237	(4)
Conclusion	241	(2)
Bibliography	243	(28)
Index	271