𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A fast algorithm for the inversion of general Toeplitz matrices

✍ Scribed by P.G. Martinsson; V. Rokhlin; M. Tygert

Publisher
Elsevier Science
Year
2005
Tongue
English
Weight
590 KB
Volume
50
Category
Article
ISSN
0898-1221

No coin nor oath required. For personal study only.

✦ Synopsis

we propose a "fast" algorithm for the construction of a data-sparse inver'~ of a general Toeplitz matrix. The computational cost for inverting an N × N Toeplitz matrix equals the cost of four length-N FFTs plus an O(N)-term. This cost should be compared to the O(Nlog2N) cost of previously published methods. Moreover, while those earlier methods are based on algebraic considerations, the procedure of this paper is analysis-based; as a result, its stability does not depend on the symmetry and positive-definiteness of the matrix being inverted. The performance of the scheme is illustrated with numerical examples.

📜 SIMILAR VOLUMES

Fast algorithm for matrix–vector multipl
Fast algorithm for matrix–vector multiply of asymmetric multilevel block-Toeplitz matrices in 3-D scattering
✍ Benjamin E. Barrowes; Fernando L. Teixeira; Jin A. Kong 📂 Article 📅 2001 🏛 John Wiley and Sons 🌐 English ⚖ 185 KB

## Abstract A new __O__(__N__ log __N__) FFT‐based method to expedite matrix–vector multiplies involving multilevel block‐Toeplitz (MBT) matrices is presented. The method is also a minimal memory method with __O__(__N__) memory requirements because only nonredundant entries of the MBT matrix are st

Sparse approximate inverse preconditione
Sparse approximate inverse preconditioned CG-FFT algorithm with block toeplitz matrix for fast analysis of microstrip circuits
✍ R. S. Chen; K. F. Tsang; Edward K. N. Yung 📂 Article 📅 2002 🏛 John Wiley and Sons 🌐 English ⚖ 154 KB

## Abstract In this paper, the multifrontal method is employed to precondition the conjugate gradient (CG) algorithm with the block Toeplitz matrix based fast Fourier transform (FFT) technique for dense matrix equations from the mixed potential integral equation (MPIE) to enhance the computational