A parallel algorithm for lagrange interpolation on k-ary n-cubes

Hamid Sarbazi-Azad; Lewis M. Mackenzie; Mohamed Ould-Khaoua

doi:10.1007/3-540-49164-3_9

A parallel algorithm for lagrange interpolation on k-ary n-cubes

Hamid Sarbazi-Azad, Lewis M. Mackenzie, Mohamed Ould-Khaoua

Electrical and Computer Engineering

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

4 Citations (Scopus)

Abstract

Most current multicomputers employ k- ary n-cube networks for lowlatency and high-bandwidth inter-processor communication. This paper introduces a parallel algorithm for computing an N=kⁿ point Lagrange interpolation on these networks. The algorithm consists of three phases: initialisation, main and final. While there is no computation in the initialisation phase, the main phase is composed of kⁿ/2 steps, each consisting of four multiplications and four subtractions, and an additional step including one division and one multiplication. The final phase is carried out in n×⌈k/2⌉ steps, each using one addition.

Original language	English
Title of host publication	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Publisher	Springer Verlag
Pages	85-95
Number of pages	11
Volume	1557
ISBN (Print)	3540656413, 9783540656418
DOIs	https://doi.org/10.1007/3-540-49164-3_9
Publication status	Published - 1999
Event	4th International ACPC Conference on Parallel Computation, ACPC 1999 - Salzburg, Austria Duration: Feb 16 1999 → Feb 18 1999

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	1557
ISSN (Print)	03029743
ISSN (Electronic)	16113349

Other

Other	4th International ACPC Conference on Parallel Computation, ACPC 1999
Country/Territory	Austria
City	Salzburg
Period	2/16/99 → 2/18/99

ASJC Scopus subject areas

Computer Science(all)
Theoretical Computer Science

Access to Document

10.1007/3-540-49164-3_9

Cite this

Sarbazi-Azad, H., Mackenzie, L. M., & Ould-Khaoua, M. (1999). A parallel algorithm for lagrange interpolation on k-ary n-cubes. In Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) (Vol. 1557, pp. 85-95). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1557). Springer Verlag. https://doi.org/10.1007/3-540-49164-3_9

A parallel algorithm for lagrange interpolation on k-ary n-cubes. / Sarbazi-Azad, Hamid; Mackenzie, Lewis M.; Ould-Khaoua, Mohamed.
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Vol. 1557 Springer Verlag, 1999. p. 85-95 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1557).

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

Sarbazi-Azad, H, Mackenzie, LM & Ould-Khaoua, M 1999, A parallel algorithm for lagrange interpolation on k-ary n-cubes. in Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). vol. 1557, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 1557, Springer Verlag, pp. 85-95, 4th International ACPC Conference on Parallel Computation, ACPC 1999, Salzburg, Austria, 2/16/99. https://doi.org/10.1007/3-540-49164-3_9

Sarbazi-Azad H, Mackenzie LM, Ould-Khaoua M. A parallel algorithm for lagrange interpolation on k-ary n-cubes. In Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Vol. 1557. Springer Verlag. 1999. p. 85-95. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/3-540-49164-3_9

Sarbazi-Azad, Hamid ; Mackenzie, Lewis M. ; Ould-Khaoua, Mohamed. / A parallel algorithm for lagrange interpolation on k-ary n-cubes. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Vol. 1557 Springer Verlag, 1999. pp. 85-95 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{1851419c6fe54151b35402355fce4095,

title = "A parallel algorithm for lagrange interpolation on k-ary n-cubes",

abstract = "Most current multicomputers employ k- ary n-cube networks for lowlatency and high-bandwidth inter-processor communication. This paper introduces a parallel algorithm for computing an N=kn point Lagrange interpolation on these networks. The algorithm consists of three phases: initialisation, main and final. While there is no computation in the initialisation phase, the main phase is composed of kn/2 steps, each consisting of four multiplications and four subtractions, and an additional step including one division and one multiplication. The final phase is carried out in n×⌈k/2⌉ steps, each using one addition.",

author = "Hamid Sarbazi-Azad and Mackenzie, {Lewis M.} and Mohamed Ould-Khaoua",

year = "1999",

doi = "10.1007/3-540-49164-3_9",

language = "English",

isbn = "3540656413",

volume = "1557",

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

publisher = "Springer Verlag",

pages = "85--95",

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

note = "4th International ACPC Conference on Parallel Computation, ACPC 1999 ; Conference date: 16-02-1999 Through 18-02-1999",

}

TY - GEN

T1 - A parallel algorithm for lagrange interpolation on k-ary n-cubes

AU - Sarbazi-Azad, Hamid

AU - Mackenzie, Lewis M.

AU - Ould-Khaoua, Mohamed

PY - 1999

Y1 - 1999

N2 - Most current multicomputers employ k- ary n-cube networks for lowlatency and high-bandwidth inter-processor communication. This paper introduces a parallel algorithm for computing an N=kn point Lagrange interpolation on these networks. The algorithm consists of three phases: initialisation, main and final. While there is no computation in the initialisation phase, the main phase is composed of kn/2 steps, each consisting of four multiplications and four subtractions, and an additional step including one division and one multiplication. The final phase is carried out in n×⌈k/2⌉ steps, each using one addition.

AB - Most current multicomputers employ k- ary n-cube networks for lowlatency and high-bandwidth inter-processor communication. This paper introduces a parallel algorithm for computing an N=kn point Lagrange interpolation on these networks. The algorithm consists of three phases: initialisation, main and final. While there is no computation in the initialisation phase, the main phase is composed of kn/2 steps, each consisting of four multiplications and four subtractions, and an additional step including one division and one multiplication. The final phase is carried out in n×⌈k/2⌉ steps, each using one addition.

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

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

U2 - 10.1007/3-540-49164-3_9

DO - 10.1007/3-540-49164-3_9

M3 - Conference contribution

AN - SCOPUS:84957639110

SN - 3540656413

SN - 9783540656418

VL - 1557

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

SP - 85

EP - 95

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

PB - Springer Verlag

T2 - 4th International ACPC Conference on Parallel Computation, ACPC 1999

Y2 - 16 February 1999 through 18 February 1999

ER -

A parallel algorithm for lagrange interpolation on k-ary n-cubes

Abstract

Publication series

Other

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this