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^*

^*此作品的通信作者

資訊工程學系

研究成果: 雜誌貢獻 › 期刊論文 › 同行評審

1 引文斯高帕斯（Scopus）

摘要

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.

原文	英語
頁（從 - 到）	409-431
頁數	23
期刊	Journal of Scientific Computing
卷	12
發行號	4
DOIs	https://doi.org/10.1023/A:1025629029872
出版狀態	已發佈 - 1997

ASJC Scopus subject areas

軟體
理論電腦科學
數值分析
一般工程
計算機理論與數學
計算數學
應用數學

存取文件

10.1023/A:1025629029872

其它文件與鏈接

引用此

@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 - https://www.scopus.com/pages/publications/0031376635

UR - https://www.scopus.com/pages/publications/0031376635#tab=citedBy

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

摘要

ASJC Scopus subject areas

存取文件

其它文件與鏈接

指紋

引用此