One of the best known fast computational algorithms is the fast Fourier transform method. Its efficiency is based mainly on the special structure of the discrete Fourier transform matrix. Recently, many other algorithms of this type were discovered, and the theory of structured matrices emerged.
This volume contains 22 survey and research papers devoted to a variety of theoretical and practical aspects of the design of fast algorithms for structured matrices and related issues. Included are several papers containing various affirmative and negative results in this direction. The theory of rational interpolation is one of the excellent sources providing intuition and methods to design fast algorithms. The volume contains several computational and theoretical papers on the topic. There are several papers on new applications of structured matrices, e.g., to the design of fast decoding algorithms, computing state-space realizations, relations to Lie algebras, unconstrained optimization, solving matrix equations, etc.
The book is suitable for mathematicians, engineers, and numerical analysts who design, study, and use fast computational algorithms based on the theory of structured matrices.
Author(s): Ams-Ims-Siam Joint Summer Research Conference on Fast Algorithms in ma, Vadim Olshevsky, Vadim Olshevsky
Series: Contemporary mathematics 323
Publisher: American Mathematical Society; Society for Industrial and Applied Mathematics
Year: 2003
Language: English
Pages: 446
City: Providence, R.I. :, Philadelphia, PA
Tags: Математика;Вычислительная математика;
CONTEMPORARY MATHEMATICS......Page 1
CONTENTS......Page 7
Foreword......Page 8
Pivoting for Structured Matrices and Rational Tangential Interpolation......Page 10
Inversion of Toeplitz-plus-Hankel matrices with arbitrary rank profile......Page 84
A Lanczos-type Algorithm for the QR Factorization of Cauchy-like Matrices......Page 100
Fast and Stable Algorithms for Reducing Diagonal plus Semiseparable Matrices to Tridiagonal and Bidiagonal Form......Page 114
A Comrade-Matrix-Based Derivation of the Eight Versions of Fast Cosine and Sine Transforms......Page 128
Solving certain matrix equations by means of Toeplitz computations: algorithms and applications......Page 160
A Fast Singular Value Algorithm for Hankel Matrices......Page 178
A modified companion matrix method based on Newton polynomials......Page 188
A Fast Direct Method For Solving The Two-dimensional Helmholtz Equation, With Robbins Boundary Conditions......Page 196
Structured Matrices in Unconstrained Minimization Methods......Page 214
Computation of minimal state space realizations in Jacobson normal form......Page 230
High Order Accurate Particular Solutions of the Biharmonic Equation on General Regions......Page 242
A Fast Projected Conjugate Gradient Algorithm for Training Support Vector Machines......Page 254
A Displacement Approach to Decoding Algebraic Codes......Page 274
Some Convergence Estimates For Algebraic Multilevel Preconditioners......Page 302
Spectral equivalence and matrix algebra preconditioners for multilevel Toeplitz systems: a negative result......Page 322
Spectral Distribution of Hermitian Toeplitz Matrices Formally Generated by Rational Functions......Page 332
From Toeplitz Matrix Sequences to Zero distribution of Orthogonal Polynomials......Page 338
On Lie Algebras, Submanifolds and Structured Matrices......Page 350
Riccati Equations and Bitangential Interpolation Problems with Singular Pick Matrices......Page 370
Functions with Pick matrices having bounded number of negative eigenvalues......Page 402
One-dimensional perturbations of selfadjoint operators with finite or discrete spectrum......Page 428
Titles in This Series......Page 444
