Parallelization of ILU decomposition for elliptic boundary value problem of the PDE on AP3000

Kentaro Moriya; Takashi Nodera

doi:10.1007/BFb0094936

Parallelization of ILU decomposition for elliptic boundary value problem of the PDE on AP3000

Kentaro Moriya, Takashi Nodera

Department of Mathematics

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

1 Citation (Scopus)

Abstract

ILU (or Incomplete LU) decomposition is one of the most popular preconditioners for large and sparse linear systems of equations. However, it is difficult to implement the ILU preconditioner on distributed memory parallel computers, because the process consists of forward and backward substitution. The block divided method is one of the algorithms that can paralletize the ILU preconditioner for the linear system obtained by applying the finite difference method to discretize the elliptic boundary value problem of the PDE (or partial differential equation). However, on a distributed memory parallel computer, since the communication overhead is significantly large, the ILU preconditioner does not perform well. We propose an algorithm that decreases the communication overhead on the block divided method and determines the appropriate band-size. Based on our approach, the BiCGStab(g) method with the ILU preconditioner is implemented on the distributed memory parallel computer, Fujitsu AP3000. We also analyze the performance of parallelism in the operation of the ILU preconditioner through numerical results.

Original language	English
Title of host publication	High Performance Computing - 2nd International Symposium, ISHPC 1999, Proceedings
Editors	Kazuki Joe, Akira Fukuda, Constantine Polychronopoulos, Shinji Tomita
Publisher	Springer Verlag
Pages	344-353
Number of pages	10
ISBN (Print)	3540659692, 9783540659693
DOIs	https://doi.org/10.1007/BFb0094936
Publication status	Published - 1999
Event	2nd International Symposium on High Performance Computing, ISHPC 1999 - Kyoto, Japan Duration: 1999 May 26 → 1999 May 28

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	1615
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Other

Other	2nd International Symposium on High Performance Computing, ISHPC 1999
Country/Territory	Japan
City	Kyoto
Period	99/5/26 → 99/5/28

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/BFb0094936

Cite this

Moriya, K., & Nodera, T. (1999). Parallelization of ILU decomposition for elliptic boundary value problem of the PDE on AP3000. In K. Joe, A. Fukuda, C. Polychronopoulos, & S. Tomita (Eds.), High Performance Computing - 2nd International Symposium, ISHPC 1999, Proceedings (pp. 344-353). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1615). Springer Verlag. https://doi.org/10.1007/BFb0094936

Parallelization of ILU decomposition for elliptic boundary value problem of the PDE on AP3000. / Moriya, Kentaro; Nodera, Takashi.
High Performance Computing - 2nd International Symposium, ISHPC 1999, Proceedings. ed. / Kazuki Joe; Akira Fukuda; Constantine Polychronopoulos; Shinji Tomita. Springer Verlag, 1999. p. 344-353 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1615).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Moriya, K & Nodera, T 1999, Parallelization of ILU decomposition for elliptic boundary value problem of the PDE on AP3000. in K Joe, A Fukuda, C Polychronopoulos & S Tomita (eds), High Performance Computing - 2nd International Symposium, ISHPC 1999, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 1615, Springer Verlag, pp. 344-353, 2nd International Symposium on High Performance Computing, ISHPC 1999, Kyoto, Japan, 99/5/26. https://doi.org/10.1007/BFb0094936

Moriya K, Nodera T. Parallelization of ILU decomposition for elliptic boundary value problem of the PDE on AP3000. In Joe K, Fukuda A, Polychronopoulos C, Tomita S, editors, High Performance Computing - 2nd International Symposium, ISHPC 1999, Proceedings. Springer Verlag. 1999. p. 344-353. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/BFb0094936

Moriya, Kentaro ; Nodera, Takashi. / Parallelization of ILU decomposition for elliptic boundary value problem of the PDE on AP3000. High Performance Computing - 2nd International Symposium, ISHPC 1999, Proceedings. editor / Kazuki Joe ; Akira Fukuda ; Constantine Polychronopoulos ; Shinji Tomita. Springer Verlag, 1999. pp. 344-353 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{4a7abc91f2bc438095c5d3e0e2172df2,

title = "Parallelization of ILU decomposition for elliptic boundary value problem of the PDE on AP3000",

abstract = "ILU (or Incomplete LU) decomposition is one of the most popular preconditioners for large and sparse linear systems of equations. However, it is difficult to implement the ILU preconditioner on distributed memory parallel computers, because the process consists of forward and backward substitution. The block divided method is one of the algorithms that can paralletize the ILU preconditioner for the linear system obtained by applying the finite difference method to discretize the elliptic boundary value problem of the PDE (or partial differential equation). However, on a distributed memory parallel computer, since the communication overhead is significantly large, the ILU preconditioner does not perform well. We propose an algorithm that decreases the communication overhead on the block divided method and determines the appropriate band-size. Based on our approach, the BiCGStab(g) method with the ILU preconditioner is implemented on the distributed memory parallel computer, Fujitsu AP3000. We also analyze the performance of parallelism in the operation of the ILU preconditioner through numerical results.",

author = "Kentaro Moriya and Takashi Nodera",

note = "Publisher Copyright: {\textcopyright} 1999, Springer-Verlag. All rights reserved.; 2nd International Symposium on High Performance Computing, ISHPC 1999 ; Conference date: 26-05-1999 Through 28-05-1999",

year = "1999",

doi = "10.1007/BFb0094936",

language = "English",

isbn = "3540659692",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "344--353",

editor = "Kazuki Joe and Akira Fukuda and Constantine Polychronopoulos and Shinji Tomita",

booktitle = "High Performance Computing - 2nd International Symposium, ISHPC 1999, Proceedings",

}

TY - GEN

T1 - Parallelization of ILU decomposition for elliptic boundary value problem of the PDE on AP3000

AU - Moriya, Kentaro

AU - Nodera, Takashi

PY - 1999

Y1 - 1999

N2 - ILU (or Incomplete LU) decomposition is one of the most popular preconditioners for large and sparse linear systems of equations. However, it is difficult to implement the ILU preconditioner on distributed memory parallel computers, because the process consists of forward and backward substitution. The block divided method is one of the algorithms that can paralletize the ILU preconditioner for the linear system obtained by applying the finite difference method to discretize the elliptic boundary value problem of the PDE (or partial differential equation). However, on a distributed memory parallel computer, since the communication overhead is significantly large, the ILU preconditioner does not perform well. We propose an algorithm that decreases the communication overhead on the block divided method and determines the appropriate band-size. Based on our approach, the BiCGStab(g) method with the ILU preconditioner is implemented on the distributed memory parallel computer, Fujitsu AP3000. We also analyze the performance of parallelism in the operation of the ILU preconditioner through numerical results.

AB - ILU (or Incomplete LU) decomposition is one of the most popular preconditioners for large and sparse linear systems of equations. However, it is difficult to implement the ILU preconditioner on distributed memory parallel computers, because the process consists of forward and backward substitution. The block divided method is one of the algorithms that can paralletize the ILU preconditioner for the linear system obtained by applying the finite difference method to discretize the elliptic boundary value problem of the PDE (or partial differential equation). However, on a distributed memory parallel computer, since the communication overhead is significantly large, the ILU preconditioner does not perform well. We propose an algorithm that decreases the communication overhead on the block divided method and determines the appropriate band-size. Based on our approach, the BiCGStab(g) method with the ILU preconditioner is implemented on the distributed memory parallel computer, Fujitsu AP3000. We also analyze the performance of parallelism in the operation of the ILU preconditioner through numerical results.

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

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

U2 - 10.1007/BFb0094936

DO - 10.1007/BFb0094936

M3 - Conference contribution

AN - SCOPUS:84958051293

SN - 3540659692

SN - 9783540659693

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 344

EP - 353

BT - High Performance Computing - 2nd International Symposium, ISHPC 1999, Proceedings

A2 - Joe, Kazuki

A2 - Fukuda, Akira

A2 - Polychronopoulos, Constantine

A2 - Tomita, Shinji

PB - Springer Verlag

T2 - 2nd International Symposium on High Performance Computing, ISHPC 1999

Y2 - 26 May 1999 through 28 May 1999

ER -

Parallelization of ILU decomposition for elliptic boundary value problem of the PDE on AP3000

Abstract

Publication series

Other

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this