2007/12/13 by Shivkumar Chandrasekaran, Ming Gu, X. Sun +2 · 2 citations
Computer Science · Physics and Astronomy · Engineering · Mathematics · #Matrix Theory and Algorithms #Electromagnetic Scattering and Analysis #Numerical methods in engineering #Toeplitz matrix #Mathematics #Solver #Rank (graph theory) #Fast Fourier transform #Cauchy distribution #Matrix (chemical analysis) #Linear system #System of linear equations #Applied mathematics #Algorithm #Mathematical analysis #Pure mathematics #Mathematical optimization #Combinatorics
paper · doi:10.1137/040617200
openalex publication_date 2007/12/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/03
In this paper we develop a new superfast solver for Toeplitz systems of linear equations. To solve Toeplitz systems many people use displacement equation methods. With displacement structures, Toeplitz matrices can be transformed into Cauchy-like matrices using the FFT or other trigonometric transformations. These Cauchy-like matrices have a special property, that is, their off-diagonal blocks have small numerical ranks. This low-rank property plays a central role in our superfast Toeplitz solver. It enables us to quickly approximate the Cauchy-like matrices by structured matrices called sequentially semiseparable (SSS) matrices. The major work of the constructions of these SSS forms can be done in precomputations (independent of the Toeplitz matrix entries). These SSS representations are compact because of the low-rank property. The SSS Cauchy-like systems can be solved in linear time with linear storage. Excluding precomputations the main operations are the FFT and SSS system solve, which are both very efficient. Our new Toeplitz solver is stable in practice. Numerical examples are presented to illustrate the efficiency and the practical stability.