A parallel algorithm solving a tridiagonal Toeplitz linear system

Hyoung Joong Kim; Jang Gyu Lee

doi:10.1016/0167-8191(90)90131-R

A parallel algorithm solving a tridiagonal Toeplitz linear system

Hyoung Joong Kim, Jang Gyu Lee

Research output: Contribution to journal › Article › peer-review

5 Citations (Scopus)

Abstract

A new tridiagonal Toeplitz linear system (TTLS) solver is proposed. The solver first decomposes an n-dimensional strictly diagonally dominant TTLS equation into a number of m-dimensional subsystems employing a modified Gaussian elimination method. An analytic solution of a continued fraction is obtained to derive the solver. The solver based on the modified Gaussian elimination method fully exploits parallelism. Computation and communication complexities of the proposed algorithm are all shown to be O(n/m).

Original language	English
Pages (from-to)	289-294
Number of pages	6
Journal	Parallel Computing
Volume	13
Issue number	3
DOIs	https://doi.org/10.1016/0167-8191(90)90131-R
Publication status	Published - 1990 Mar
Externally published	Yes

Keywords

Parallel algorithm
parallel computing
real-time processing
tridiagonal Toeplitz linear system solver

ASJC Scopus subject areas

Software
Theoretical Computer Science
Hardware and Architecture
Computer Networks and Communications
Computer Graphics and Computer-Aided Design
Artificial Intelligence

Access to Document

10.1016/0167-8191(90)90131-R

Cite this

@article{2246dbbb2bf04bc786db80153f49120f,

title = "A parallel algorithm solving a tridiagonal Toeplitz linear system",

abstract = "A new tridiagonal Toeplitz linear system (TTLS) solver is proposed. The solver first decomposes an n-dimensional strictly diagonally dominant TTLS equation into a number of m-dimensional subsystems employing a modified Gaussian elimination method. An analytic solution of a continued fraction is obtained to derive the solver. The solver based on the modified Gaussian elimination method fully exploits parallelism. Computation and communication complexities of the proposed algorithm are all shown to be O(n/m).",

keywords = "Parallel algorithm, parallel computing, real-time processing, tridiagonal Toeplitz linear system solver",

author = "Kim, {Hyoung Joong} and Lee, {Jang Gyu}",

year = "1990",

month = mar,

doi = "10.1016/0167-8191(90)90131-R",

language = "English",

volume = "13",

pages = "289--294",

journal = "Parallel Computing",

issn = "0167-8191",

publisher = "Elsevier",

number = "3",

}

TY - JOUR

T1 - A parallel algorithm solving a tridiagonal Toeplitz linear system

AU - Kim, Hyoung Joong

AU - Lee, Jang Gyu

PY - 1990/3

Y1 - 1990/3

N2 - A new tridiagonal Toeplitz linear system (TTLS) solver is proposed. The solver first decomposes an n-dimensional strictly diagonally dominant TTLS equation into a number of m-dimensional subsystems employing a modified Gaussian elimination method. An analytic solution of a continued fraction is obtained to derive the solver. The solver based on the modified Gaussian elimination method fully exploits parallelism. Computation and communication complexities of the proposed algorithm are all shown to be O(n/m).

AB - A new tridiagonal Toeplitz linear system (TTLS) solver is proposed. The solver first decomposes an n-dimensional strictly diagonally dominant TTLS equation into a number of m-dimensional subsystems employing a modified Gaussian elimination method. An analytic solution of a continued fraction is obtained to derive the solver. The solver based on the modified Gaussian elimination method fully exploits parallelism. Computation and communication complexities of the proposed algorithm are all shown to be O(n/m).

KW - Parallel algorithm

KW - parallel computing

KW - real-time processing

KW - tridiagonal Toeplitz linear system solver

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

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

U2 - 10.1016/0167-8191(90)90131-R

DO - 10.1016/0167-8191(90)90131-R

M3 - Article

AN - SCOPUS:0025402834

SN - 0167-8191

VL - 13

SP - 289

EP - 294

JO - Parallel Computing

JF - Parallel Computing

IS - 3

ER -

A parallel algorithm solving a tridiagonal Toeplitz linear system

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this