A Parallel Solver for Circulant Toeplitz Tridiagonal Systems on Hypercubes

Jung Gen Wu; Wen Ming Yan; Kuo Liang Chung

doi:10.1023/A:1025629029872

A Parallel Solver for Circulant Toeplitz Tridiagonal Systems on Hypercubes

Jung Gen Wu, Wen Ming Yan, Kuo Liang Chung^*

^*Corresponding author for this work

Department of Computer Science and Information Engineering

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

1 Citation (Scopus)

Abstract

Solving circulant Toeplitz tridiagonal systems arises in many engineering applications. This paper presents a fast parallel algorithm for solving this type of systems. The number of floating-point operations required in our algorithm is less than the previous parallel algorithm [cf. Kim and Lee (1990)] for solving the similar system. Specifically, an overlapping technique is proposed to reduce the communication steps required. In addition, an error analysis is given. The implementation of our algorithm on the nCUBE2/E with 16 processors has been carried out. The experimental results show that the speedup is almost linearly proportional to the number of processors.

Original language	English
Pages (from-to)	409-431
Number of pages	23
Journal	Journal of Scientific Computing
Volume	12
Issue number	4
DOIs	https://doi.org/10.1023/A:1025629029872
Publication status	Published - 1997

Keywords

Diagonally dominant matrices
Error analysis
Parallel matrix computations
Toeplitz tridiagonal matrices

ASJC Scopus subject areas

Software
Theoretical Computer Science
Numerical Analysis
General Engineering
Computational Theory and Mathematics
Computational Mathematics
Applied Mathematics

Access to Document

10.1023/A:1025629029872

Cite this

@article{e00e270e4eab4d74a250b4a0fba487a6,

title = "A Parallel Solver for Circulant Toeplitz Tridiagonal Systems on Hypercubes",

abstract = "Solving circulant Toeplitz tridiagonal systems arises in many engineering applications. This paper presents a fast parallel algorithm for solving this type of systems. The number of floating-point operations required in our algorithm is less than the previous parallel algorithm [cf. Kim and Lee (1990)] for solving the similar system. Specifically, an overlapping technique is proposed to reduce the communication steps required. In addition, an error analysis is given. The implementation of our algorithm on the nCUBE2/E with 16 processors has been carried out. The experimental results show that the speedup is almost linearly proportional to the number of processors.",

keywords = "Diagonally dominant matrices, Error analysis, Parallel matrix computations, Toeplitz tridiagonal matrices",

author = "Wu, {Jung Gen} and Yan, {Wen Ming} and Chung, {Kuo Liang}",

note = "Funding Information: 3 To whom correspondence should be addressed at Department of Information Management, National Taiwan University of Science and Technology, No. 43, Section 4, Keelung Road, Taipei, Taiwan 10672, R. O. C. E-mail: klchung(a cs.ntust.edu.tw. This research was sup-ported in part by the National Science Council of R. O. C. under contracts NSC85-2121-MO11-002 and NSC85-2213-E011-009. Funding Information: ' Department of Information and Computer Education, National Taiwan Normal University, Taipei,Taiwan 10610,R.O.C.E-mail:jgwuwice.ntnu.edu.tw.Thisresearchwassupported in part by the National Science Council of R. O. C. under contract NSC85-2213-E003-001.",

year = "1997",

doi = "10.1023/A:1025629029872",

language = "English",

volume = "12",

pages = "409--431",

journal = "Journal of Scientific Computing",

issn = "0885-7474",

publisher = "Springer New York",

number = "4",

}

TY - JOUR

T1 - A Parallel Solver for Circulant Toeplitz Tridiagonal Systems on Hypercubes

AU - Wu, Jung Gen

AU - Yan, Wen Ming

AU - Chung, Kuo Liang

N1 - Funding Information: 3 To whom correspondence should be addressed at Department of Information Management, National Taiwan University of Science and Technology, No. 43, Section 4, Keelung Road, Taipei, Taiwan 10672, R. O. C. E-mail: klchung(a cs.ntust.edu.tw. This research was sup-ported in part by the National Science Council of R. O. C. under contracts NSC85-2121-MO11-002 and NSC85-2213-E011-009. Funding Information: ' Department of Information and Computer Education, National Taiwan Normal University, Taipei,Taiwan 10610,R.O.C.E-mail:jgwuwice.ntnu.edu.tw.Thisresearchwassupported in part by the National Science Council of R. O. C. under contract NSC85-2213-E003-001.

PY - 1997

Y1 - 1997

N2 - Solving circulant Toeplitz tridiagonal systems arises in many engineering applications. This paper presents a fast parallel algorithm for solving this type of systems. The number of floating-point operations required in our algorithm is less than the previous parallel algorithm [cf. Kim and Lee (1990)] for solving the similar system. Specifically, an overlapping technique is proposed to reduce the communication steps required. In addition, an error analysis is given. The implementation of our algorithm on the nCUBE2/E with 16 processors has been carried out. The experimental results show that the speedup is almost linearly proportional to the number of processors.

AB - Solving circulant Toeplitz tridiagonal systems arises in many engineering applications. This paper presents a fast parallel algorithm for solving this type of systems. The number of floating-point operations required in our algorithm is less than the previous parallel algorithm [cf. Kim and Lee (1990)] for solving the similar system. Specifically, an overlapping technique is proposed to reduce the communication steps required. In addition, an error analysis is given. The implementation of our algorithm on the nCUBE2/E with 16 processors has been carried out. The experimental results show that the speedup is almost linearly proportional to the number of processors.

KW - Diagonally dominant matrices

KW - Error analysis

KW - Parallel matrix computations

KW - Toeplitz tridiagonal matrices

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

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

U2 - 10.1023/A:1025629029872

DO - 10.1023/A:1025629029872

M3 - Article

AN - SCOPUS:0031376635

SN - 0885-7474

VL - 12

SP - 409

EP - 431

JO - Journal of Scientific Computing

JF - Journal of Scientific Computing

IS - 4

ER -

A Parallel Solver for Circulant Toeplitz Tridiagonal Systems on Hypercubes

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this