Fast inversion of triangular Toeplitz matrices

Fu Rong Lin; Wai Ki Ching; Michael K. Ng

doi:10.1016/j.tcs.2004.01.005

Fast inversion of triangular Toeplitz matrices

Fu Rong Lin^*, Wai Ki Ching, Michael K. Ng

^*Corresponding author for this work

Department of Mathematics

Research output: Contribution to journal › Journal article › peer-review

26 Citations (Scopus)

Abstract

In this paper, we present an approximate inversion method for triangular Toeplitz matrices based on trigonometric polynomial interpolation. To obtain an approximate inverse of high accuracy for a triangular Toeplitz matrix of size n, our algorithm requires two fast Fourier transforms (FFTs) and one fast cosine transform of 2n-vectors. We then revise the approximate method proposed by Bini (SIAM J. Comput. 13 (1984) 268). The complexity of the revised Bini algorithm is two FFTs of 2n-vectors.

Original language	English
Pages (from-to)	511-523
Number of pages	13
Journal	Theoretical Computer Science
Volume	315
Issue number	2-3
DOIs	https://doi.org/10.1016/j.tcs.2004.01.005
Publication status	Published - 6 May 2004

Scopus Subject Areas

Theoretical Computer Science
General Computer Science

User-Defined Keywords

Fast cosine transform
Fast Fourier transform
Interpolation
Triangular Toeplitz matrix

Access to Document

10.1016/j.tcs.2004.01.005

Cite this

@article{009968d3e4db4df68b7187cf1dbeab1c,

title = "Fast inversion of triangular Toeplitz matrices",

abstract = "In this paper, we present an approximate inversion method for triangular Toeplitz matrices based on trigonometric polynomial interpolation. To obtain an approximate inverse of high accuracy for a triangular Toeplitz matrix of size n, our algorithm requires two fast Fourier transforms (FFTs) and one fast cosine transform of 2n-vectors. We then revise the approximate method proposed by Bini (SIAM J. Comput. 13 (1984) 268). The complexity of the revised Bini algorithm is two FFTs of 2n-vectors.",

keywords = "Fast cosine transform, Fast Fourier transform, Interpolation, Triangular Toeplitz matrix",

author = "Lin, {Fu Rong} and Ching, {Wai Ki} and Ng, {Michael K.}",

note = "Publisher copyright: {\textcopyright} 2004 Published by Elsevier B.V.",

year = "2004",

month = may,

day = "6",

doi = "10.1016/j.tcs.2004.01.005",

language = "English",

volume = "315",

pages = "511--523",

journal = "Theoretical Computer Science",

issn = "0304-3975",

publisher = "Elsevier",

number = "2-3",

}

TY - JOUR

T1 - Fast inversion of triangular Toeplitz matrices

AU - Lin, Fu Rong

AU - Ching, Wai Ki

AU - Ng, Michael K.

PY - 2004/5/6

Y1 - 2004/5/6

N2 - In this paper, we present an approximate inversion method for triangular Toeplitz matrices based on trigonometric polynomial interpolation. To obtain an approximate inverse of high accuracy for a triangular Toeplitz matrix of size n, our algorithm requires two fast Fourier transforms (FFTs) and one fast cosine transform of 2n-vectors. We then revise the approximate method proposed by Bini (SIAM J. Comput. 13 (1984) 268). The complexity of the revised Bini algorithm is two FFTs of 2n-vectors.

AB - In this paper, we present an approximate inversion method for triangular Toeplitz matrices based on trigonometric polynomial interpolation. To obtain an approximate inverse of high accuracy for a triangular Toeplitz matrix of size n, our algorithm requires two fast Fourier transforms (FFTs) and one fast cosine transform of 2n-vectors. We then revise the approximate method proposed by Bini (SIAM J. Comput. 13 (1984) 268). The complexity of the revised Bini algorithm is two FFTs of 2n-vectors.

KW - Fast cosine transform

KW - Fast Fourier transform

KW - Interpolation

KW - Triangular Toeplitz matrix

UR - http://www.scopus.com/inward/record.url?scp=2042541397&partnerID=8YFLogxK

U2 - 10.1016/j.tcs.2004.01.005

DO - 10.1016/j.tcs.2004.01.005

M3 - Journal article

AN - SCOPUS:2042541397

SN - 0304-3975

VL - 315

SP - 511

EP - 523

JO - Theoretical Computer Science

JF - Theoretical Computer Science

IS - 2-3

ER -

Fast inversion of triangular Toeplitz matrices

Abstract

Scopus Subject Areas

User-Defined Keywords

Access to Document

Other files and links

Fingerprint

Cite this