A Parallel Solver for Circulant Toeplitz Tridiagonal Systems on Hypercubes

Jung-Gen Wu, Wen Ming Yan, Kuo Liang Chung

Research output: Contribution to journalArticle

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 languageEnglish
Pages (from-to)409-431
Number of pages23
JournalJournal of Scientific Computing
Volume12
Issue number4
DOIs
Publication statusPublished - 1997 Jan 1

Fingerprint

Toeplitz System
Tridiagonal Systems
Hypercube
Parallel algorithms
Parallel Algorithms
Floating point
Engineering Application
Error Analysis
Error analysis
Fast Algorithm
Overlapping
Speedup
Linearly
Directly proportional
Communication
Experimental Results

Keywords

  • Diagonally dominant matrices
  • Error analysis
  • Parallel matrix computations
  • Toeplitz tridiagonal matrices

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science
  • Engineering(all)
  • Computational Theory and Mathematics

Cite this

A Parallel Solver for Circulant Toeplitz Tridiagonal Systems on Hypercubes. / Wu, Jung-Gen; Yan, Wen Ming; Chung, Kuo Liang.

In: Journal of Scientific Computing, Vol. 12, No. 4, 01.01.1997, p. 409-431.

Research output: Contribution to journalArticle

Wu, Jung-Gen ; Yan, Wen Ming ; Chung, Kuo Liang. / A Parallel Solver for Circulant Toeplitz Tridiagonal Systems on Hypercubes. In: Journal of Scientific Computing. 1997 ; Vol. 12, No. 4. pp. 409-431.
@article{48929e13534e4461979c09abdc0fec3d,
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 = "Jung-Gen Wu and Yan, {Wen Ming} and Chung, {Kuo Liang}",
year = "1997",
month = "1",
day = "1",
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

PY - 1997/1/1

Y1 - 1997/1/1

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

VL - 12

SP - 409

EP - 431

JO - Journal of Scientific Computing

JF - Journal of Scientific Computing

SN - 0885-7474

IS - 4

ER -