Research Catalog

Title

Structured matrices and polynomials : unified superfast algorithms / Victor Y. Pan.

Author

Pan, Victor.

Publication

Boston : Birkhäuser/Springer, [2001], ©2001.

Items in the Library & Off-site

Holdings

Details

Description

xxiv, 278 pages : illustrations; 25 cm

Subjects

• Polynomials > Data processing
• Matrices > Data processing

Bibliography (note)

• Includes bibliographical references (p. [243]-270) and index.

Contents

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

ISBN

• 0817642404 (alk. paper)
• 3764342404 (alk. paper)

LCCN

2001035928

OCLC

• ocm47045174
• SCSB-4168735

Owning Institutions

Columbia University Libraries