FAST ITERATIVE SOLVERS FOR TOEPLITZ-PLUS-BAND SYSTEMS

Raymond H. CHAN; Kwok-Po NG

doi:10.1137/0914061

FAST ITERATIVE SOLVERS FOR TOEPLITZ-PLUS-BAND SYSTEMS

Raymond H. CHAN
, Kwok-Po NG

Research output: Journal Publications and Reviews › RGC 21 - Publication in refereed journal › peer-review

Abstract

The authors consider the solutions of Hermitian Toeplitz-plus-band systems (A_n + B_n)x = b, where A_n are n-by-n Toeplitz matrices and B_n are n-by-n band matrices with bandwidth independent of n. These systems appear in solving integrodifferential equations and signal processing. However, unlike the case of Toeplitz systems, no fast direct solvers have been developed for solving them. In this paper, the preconditioned conjugate gradient method with band matrices as preconditioners is used. The authors prove that if A_n is generated by a nonnegative piecewise continuous function and B_n is positive semidefinite, then there exists a band matrix C_n, with bandwidth independent of n, such that the spectra of C_n^-1 (A_n + B_n) are uniformly bounded by a constant independent of n. In particular, we show that the solution of (A_n + B_n)x = b can be obtained in O(n log n) operations.

Original language	English
Pages (from-to)	1013-1019
Journal	SIAM Journal on Scientific Computing
Volume	14
Issue number	5
DOIs	https://doi.org/10.1137/0914061
Publication status	Published - Sept 1993
Externally published	Yes

Research Keywords

Toeplitz matrix
band matrix
generating function
preconditioned conjugate gradient method

Access Output

10.1137/0914061

Other Access Options

Check CityUHK Library

Permanent Link

Right click to copy link

Cite this

@article{2638ca2b47ae4467ad92e9d68768668f,

title = "FAST ITERATIVE SOLVERS FOR TOEPLITZ-PLUS-BAND SYSTEMS",

abstract = "The authors consider the solutions of Hermitian Toeplitz-plus-band systems (An + Bn)x = b, where An are n-by-n Toeplitz matrices and Bn are n-by-n band matrices with bandwidth independent of n. These systems appear in solving integrodifferential equations and signal processing. However, unlike the case of Toeplitz systems, no fast direct solvers have been developed for solving them. In this paper, the preconditioned conjugate gradient method with band matrices as preconditioners is used. The authors prove that if An is generated by a nonnegative piecewise continuous function and Bn is positive semidefinite, then there exists a band matrix Cn, with bandwidth independent of n, such that the spectra of Cn-1 (An + Bn) are uniformly bounded by a constant independent of n. In particular, we show that the solution of (An + Bn)x = b can be obtained in O(n log n) operations. ",

keywords = "Toeplitz matrix, band matrix, generating function, preconditioned conjugate gradient method",

author = "CHAN, \{Raymond H.\} and Kwok-Po NG",

year = "1993",

month = sep,

doi = "10.1137/0914061",

language = "English",

volume = "14",

pages = "1013--1019",

journal = "SIAM Journal on Scientific Computing",

issn = "1064-8275",

publisher = "Society for Industrial and Applied Mathematics",

number = "5",

}

TY - JOUR

T1 - FAST ITERATIVE SOLVERS FOR TOEPLITZ-PLUS-BAND SYSTEMS

AU - CHAN, Raymond H.

AU - NG, Kwok-Po

PY - 1993/9

Y1 - 1993/9

N2 - The authors consider the solutions of Hermitian Toeplitz-plus-band systems (An + Bn)x = b, where An are n-by-n Toeplitz matrices and Bn are n-by-n band matrices with bandwidth independent of n. These systems appear in solving integrodifferential equations and signal processing. However, unlike the case of Toeplitz systems, no fast direct solvers have been developed for solving them. In this paper, the preconditioned conjugate gradient method with band matrices as preconditioners is used. The authors prove that if An is generated by a nonnegative piecewise continuous function and Bn is positive semidefinite, then there exists a band matrix Cn, with bandwidth independent of n, such that the spectra of Cn-1 (An + Bn) are uniformly bounded by a constant independent of n. In particular, we show that the solution of (An + Bn)x = b can be obtained in O(n log n) operations.

AB - The authors consider the solutions of Hermitian Toeplitz-plus-band systems (An + Bn)x = b, where An are n-by-n Toeplitz matrices and Bn are n-by-n band matrices with bandwidth independent of n. These systems appear in solving integrodifferential equations and signal processing. However, unlike the case of Toeplitz systems, no fast direct solvers have been developed for solving them. In this paper, the preconditioned conjugate gradient method with band matrices as preconditioners is used. The authors prove that if An is generated by a nonnegative piecewise continuous function and Bn is positive semidefinite, then there exists a band matrix Cn, with bandwidth independent of n, such that the spectra of Cn-1 (An + Bn) are uniformly bounded by a constant independent of n. In particular, we show that the solution of (An + Bn)x = b can be obtained in O(n log n) operations.

KW - Toeplitz matrix

KW - band matrix

KW - generating function

KW - preconditioned conjugate gradient method

U2 - 10.1137/0914061

DO - 10.1137/0914061

M3 - RGC 21 - Publication in refereed journal

SN - 1064-8275

VL - 14

SP - 1013

EP - 1019

JO - SIAM Journal on Scientific Computing

JF - SIAM Journal on Scientific Computing

IS - 5

ER -

FAST ITERATIVE SOLVERS FOR TOEPLITZ-PLUS-BAND SYSTEMS

Abstract

Research Keywords

Access Output

Other Access Options

Permanent Link

Fingerprint

Cite this