An efficient algorithm for the parallel solution of high-dimensional differential equations

Stefan Klus; Tuhin Sahai; Cong Liu; Michael Dellnitz

doi:10.1016/j.cam.2010.12.026

An efficient algorithm for the parallel solution of high-dimensional differential equations

Stefan Klus, Tuhin Sahai^*, Cong Liu, Michael Dellnitz

^*Corresponding author for this work

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

6 Citations (Scopus)

Abstract

The study of high-dimensional differential equations is challenging and difficult due to the analytical and computational intractability. Here, we improve the speed of waveform relaxation (WR), a method to simulate high-dimensional differential-algebraic equations. This new method termed adaptive waveform relaxation (AWR) is tested on a communication network example. Further, we propose different heuristics for computing graph partitions tailored to adaptive waveform relaxation. We find that AWR coupled with appropriate graph partitioning methods provides a speedup by a factor between 3 and 16.

Original language	English
Pages (from-to)	3053-3062
Number of pages	10
Journal	Journal of Computational and Applied Mathematics
Volume	235
Issue number	9
DOIs	https://doi.org/10.1016/j.cam.2010.12.026
Publication status	Published - 1 Mar 2011

Keywords

Adaptive windowing
Graph partitioning
Parallel algorithms
Petri nets
Waveform relaxation

ASJC Scopus subject areas

Computational Mathematics
Applied Mathematics

Access to Document

10.1016/j.cam.2010.12.026

Cite this

@article{a798f0a2b7304a01b3b922034b4da2b6,

title = "An efficient algorithm for the parallel solution of high-dimensional differential equations",

abstract = "The study of high-dimensional differential equations is challenging and difficult due to the analytical and computational intractability. Here, we improve the speed of waveform relaxation (WR), a method to simulate high-dimensional differential-algebraic equations. This new method termed adaptive waveform relaxation (AWR) is tested on a communication network example. Further, we propose different heuristics for computing graph partitions tailored to adaptive waveform relaxation. We find that AWR coupled with appropriate graph partitioning methods provides a speedup by a factor between 3 and 16.",

keywords = "Adaptive windowing, Graph partitioning, Parallel algorithms, Petri nets, Waveform relaxation",

author = "Stefan Klus and Tuhin Sahai and Cong Liu and Michael Dellnitz",

year = "2011",

month = mar,

day = "1",

doi = "10.1016/j.cam.2010.12.026",

language = "English",

volume = "235",

pages = "3053--3062",

journal = "Journal of Computational and Applied Mathematics",

issn = "0377-0427",

publisher = "Elsevier B.V.",

number = "9",

}

TY - JOUR

T1 - An efficient algorithm for the parallel solution of high-dimensional differential equations

AU - Klus, Stefan

AU - Sahai, Tuhin

AU - Liu, Cong

AU - Dellnitz, Michael

PY - 2011/3/1

Y1 - 2011/3/1

N2 - The study of high-dimensional differential equations is challenging and difficult due to the analytical and computational intractability. Here, we improve the speed of waveform relaxation (WR), a method to simulate high-dimensional differential-algebraic equations. This new method termed adaptive waveform relaxation (AWR) is tested on a communication network example. Further, we propose different heuristics for computing graph partitions tailored to adaptive waveform relaxation. We find that AWR coupled with appropriate graph partitioning methods provides a speedup by a factor between 3 and 16.

AB - The study of high-dimensional differential equations is challenging and difficult due to the analytical and computational intractability. Here, we improve the speed of waveform relaxation (WR), a method to simulate high-dimensional differential-algebraic equations. This new method termed adaptive waveform relaxation (AWR) is tested on a communication network example. Further, we propose different heuristics for computing graph partitions tailored to adaptive waveform relaxation. We find that AWR coupled with appropriate graph partitioning methods provides a speedup by a factor between 3 and 16.

KW - Adaptive windowing

KW - Graph partitioning

KW - Parallel algorithms

KW - Petri nets

KW - Waveform relaxation

UR - https://www.scopus.com/pages/publications/79951514580

U2 - 10.1016/j.cam.2010.12.026

DO - 10.1016/j.cam.2010.12.026

M3 - Article

AN - SCOPUS:79951514580

SN - 0377-0427

VL - 235

SP - 3053

EP - 3062

JO - Journal of Computational and Applied Mathematics

JF - Journal of Computational and Applied Mathematics

IS - 9

ER -

An efficient algorithm for the parallel solution of high-dimensional differential equations

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this