Optimal parallel algorithms for solving tridiagonal linear systems

Eunice E. Santos

doi:10.1007/bfb0002802

Optimal parallel algorithms for solving tridiagonal linear systems

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

Abstract

We consider the problem of solving tridiagonal linear systems on parallel distributed-memory machines. We present tight asymptotic bounds for solving these systems on the LogP model using two very common direct methods: odd-even cyclic reduction and prefix summing. For each method, we begin by presenting lower bounds on execution time for solving tridiagonal linear systems. Specifically, we present lower bounds in which it is assumed that the number of data items per processor is bounded, a general lower bound, and lower bounds for specific data layouts commonly used in designing parallel algorithms to solve tridiagonal linear systems. Moreover, algorithms are provided which have running times within a constant factor of the lower bounds provided. Lastly, the bounds for odd-even cyclic reduction and prefix summing are compared.

Original language	English (US)
Title of host publication	Euro-Par 1997 Parallel Processing - Third International Conference, Proceedings
Publisher	Springer-Verlag Berlin Heidelberg
Pages	700-709
Number of pages	10
ISBN (Print)	9783540634409
DOIs	https://doi.org/10.1007/bfb0002802
State	Published - Dec 1 1997
Externally published	Yes
Event	3rd International Conference on Parallel Processing, Euro-Par 1997 - Passau, Germany Duration: Aug 26 1997 → Aug 29 1997

Publication series

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

Conference

Conference	3rd International Conference on Parallel Processing, Euro-Par 1997
Country	Germany
City	Passau
Period	8/26/97 → 8/29/97

ASJC Scopus subject areas

Theoretical Computer Science
Computer Science(all)

Access to Document

10.1007/bfb0002802

Fingerprint Dive into the research topics of 'Optimal parallel algorithms for solving tridiagonal linear systems'. Together they form a unique fingerprint.

Cite this

Santos, E. E. (1997). Optimal parallel algorithms for solving tridiagonal linear systems. In Euro-Par 1997 Parallel Processing - Third International Conference, Proceedings (pp. 700-709). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1300 LNCS). Springer-Verlag Berlin Heidelberg. https://doi.org/10.1007/bfb0002802

Optimal parallel algorithms for solving tridiagonal linear systems. / Santos, Eunice E.

Euro-Par 1997 Parallel Processing - Third International Conference, Proceedings. Springer-Verlag Berlin Heidelberg, 1997. p. 700-709 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1300 LNCS).

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

Santos, EE 1997, Optimal parallel algorithms for solving tridiagonal linear systems. in Euro-Par 1997 Parallel Processing - Third International Conference, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 1300 LNCS, Springer-Verlag Berlin Heidelberg, pp. 700-709, 3rd International Conference on Parallel Processing, Euro-Par 1997, Passau, Germany, 8/26/97. https://doi.org/10.1007/bfb0002802

Santos EE. Optimal parallel algorithms for solving tridiagonal linear systems. In Euro-Par 1997 Parallel Processing - Third International Conference, Proceedings. Springer-Verlag Berlin Heidelberg. 1997. p. 700-709. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/bfb0002802

@inproceedings{b143c3f367aa45acbfcab940b195e39e,

title = "Optimal parallel algorithms for solving tridiagonal linear systems",

abstract = "We consider the problem of solving tridiagonal linear systems on parallel distributed-memory machines. We present tight asymptotic bounds for solving these systems on the LogP model using two very common direct methods: odd-even cyclic reduction and prefix summing. For each method, we begin by presenting lower bounds on execution time for solving tridiagonal linear systems. Specifically, we present lower bounds in which it is assumed that the number of data items per processor is bounded, a general lower bound, and lower bounds for specific data layouts commonly used in designing parallel algorithms to solve tridiagonal linear systems. Moreover, algorithms are provided which have running times within a constant factor of the lower bounds provided. Lastly, the bounds for odd-even cyclic reduction and prefix summing are compared.",

author = "Santos, {Eunice E.}",

year = "1997",

month = dec,

day = "1",

doi = "10.1007/bfb0002802",

language = "English (US)",

isbn = "9783540634409",

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

publisher = "Springer-Verlag Berlin Heidelberg",

pages = "700--709",

booktitle = "Euro-Par 1997 Parallel Processing - Third International Conference, Proceedings",

note = "3rd International Conference on Parallel Processing, Euro-Par 1997 ; Conference date: 26-08-1997 Through 29-08-1997",

}

TY - GEN

T1 - Optimal parallel algorithms for solving tridiagonal linear systems

AU - Santos, Eunice E.

PY - 1997/12/1

Y1 - 1997/12/1

N2 - We consider the problem of solving tridiagonal linear systems on parallel distributed-memory machines. We present tight asymptotic bounds for solving these systems on the LogP model using two very common direct methods: odd-even cyclic reduction and prefix summing. For each method, we begin by presenting lower bounds on execution time for solving tridiagonal linear systems. Specifically, we present lower bounds in which it is assumed that the number of data items per processor is bounded, a general lower bound, and lower bounds for specific data layouts commonly used in designing parallel algorithms to solve tridiagonal linear systems. Moreover, algorithms are provided which have running times within a constant factor of the lower bounds provided. Lastly, the bounds for odd-even cyclic reduction and prefix summing are compared.

AB - We consider the problem of solving tridiagonal linear systems on parallel distributed-memory machines. We present tight asymptotic bounds for solving these systems on the LogP model using two very common direct methods: odd-even cyclic reduction and prefix summing. For each method, we begin by presenting lower bounds on execution time for solving tridiagonal linear systems. Specifically, we present lower bounds in which it is assumed that the number of data items per processor is bounded, a general lower bound, and lower bounds for specific data layouts commonly used in designing parallel algorithms to solve tridiagonal linear systems. Moreover, algorithms are provided which have running times within a constant factor of the lower bounds provided. Lastly, the bounds for odd-even cyclic reduction and prefix summing are compared.

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

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

U2 - 10.1007/bfb0002802

DO - 10.1007/bfb0002802

M3 - Conference contribution

AN - SCOPUS:84870926569

SN - 9783540634409

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

SP - 700

EP - 709

BT - Euro-Par 1997 Parallel Processing - Third International Conference, Proceedings

PB - Springer-Verlag Berlin Heidelberg

T2 - 3rd International Conference on Parallel Processing, Euro-Par 1997

Y2 - 26 August 1997 through 29 August 1997

ER -