Structured Matrices And Polynomials Book

	Preface
	Glossary
	List of Tables
	List of Figures
1	Computations with Structured Matrices. Introduction	1
1.1	Application areas, our subjects and objectives	1
1.2	Four features of structured matrices	3
1.3	Displacements (some history, definitions and examples)	4
1.4	Compress, Operate, Decompress	7
1.5	Basic operations with compressed structured matrices	10
1.6	Two classes of superfast algorithms. The case of Toeplitz-like matrices	12
1.7	Unified algorithms and algorithmic transformations	13
1.8	Numerical and algebraic versions of structured matrix algorithms. Flops and ops	15
1.9	Limitations of the unification	18
2	Toeplitz/Hankel Matrix Structure and Polynomial Computations	23
2.1	Definitions and preliminaries	23
2.2	Fast Fourier transform (polynomial version)	25
2.3	Fast Fourier transform (matrix version)	26
2.4	Polynomial multiplication (with extensions)	27
2.5	Polynomial division and triangular Toeplitz matrix inversion	30
2.6	The algebra of [f]-circulant matrices. Diagonalizations by DFT's	33
2.7	Algebra of polynomials modulo a polynomial and the Frobenius matrix algebra	36
2.8	Polynomial gcd and the (Extended) Euclidean Algorithm	40
2.9	Applications and extensions of the EEA: modular division, rational functions reconstruction, Pade approximation, and linear recurrence span	46
2.10	Matric algorithms for rational interpolation and the EEA	50
2.11	Matrix approach to Pade approximation	52
3	Matrix Structures of Vandermonde and Cauchy Types and Polynomial and Rational Computations	73
3.1	Multipoint polynomial evaluation	73
3.2	Modular reduction and other extensions	76
3.3	Lagrange polynomial interpolation	78
3.4	Polynomial interpolation (matrix method), transposed Vandermonde matrices, and composition of polynomials	80
3.5	Chinese remainder algorithm, polynomial and rational Hermite interpolation, and decomposition into partial fractions	82
3.6	Cauchy matrix computations. Polynomial and rational interpolation and multipoint evaluation	88
3.7	Loss (erasure)-resilient encoding/decoding and structured matrices	93
3.8	Nevanlinna-Pick interpolation problems	96
3.9	Matrix Nehari Problem	100
3.10	Sparse multivariate polynomial interpolation	101
3.11	Diagonalization of Matrix Algebras. Polynomial Vandermonde Matrices and Discrete Sine and Cosine transforms	103
4	Structured Matrices and Displacement Operators	117
4.1	Some definitions and basic results	118
4.2	Displacements of basic structured matrices	120
4.3	Inversion of the displacement operators	122
4.4	Compressed bilinear expressions for structured matrices	125
4.5	Partly regular displacement operators	134
4.6	Compression of a generator	137
4.7	Structured matrix multiplication	141
4.8	Algorithm design based on multiplicative transformation of operator matrix pairs	144
4.9	Algorithm design based on similarity transformations of operator matrices	147
5	Unified Divide-and-Conquer Algorithm	155
5.1	Introduction. Our subject and results	155
5.2	Complete recursive triangular factorization (CRTF) of general matrices	156
5.3	Compressed computation of the CRTF of structured matrices	159
5.4	Simplified compression of Schur complements	161
5.5	Regularization via symmetrization	162
5.6	Regularization via multiplicative transformation with randomization	164
5.7	Randomization for structured matrices	167
5.8	Applications to computer algebra, algebraic decoding, and numerical rational computations	168
6	Newton-Structured Numerical Iteration	177
6.1	Some definitions and preliminaries	178
6.2	Newton's iteration for root-finding and matrix inversion	179
6.3	Newton-Structured Iteration	181
6.4	Compression of the displacements by the truncation of their smallest singular values	182
6.5	Compression of displacement generators of approximate inverses by substitution	184
6.6	Bounds on the norms of the inverse operator	186
6.7	Initialization, analysis, and modifications of Newton's iteration for a general matrix	189
6.8	How much should we compress the displacements of the computed approximations?	193
6.9	Homotopic Newton's iteration	195
6.10	Newton's iteration for a singular input matrix	201
6.11	Numerical experiments with Toeplitz matrices	202
7	Newton Algebraic Iteration and Newton-Structured Algebraic Iteration	219
7.1	Some introductory remarks	219
7.2	Newton's algebraic iteration: generic algorithm	220
7.3	Specific examples of Newton's algebraic iteration	223
7.4	Newton's algebraic iteration for the inversion of general matrices	226
7.5	Newton and Newton-Structured Algebraic Iterations for characteristic polynomials and the Krylov spaces	227
7.6	Extensions of Krylov space computation	229
7.7	Inversion of general integer matrices and solution of general integer linear systems	230
7.8	Sequences of primes, random primes, and non-singularity of a matrix	232
7.9	Inversion of structured integer matrices	233
	Conclusion	241
	Bibliography	243
	Index	271