.png){kind=icon}
.png){kind=icon}
Return
A parallel algorithm for Lagrange interpolation on the star graph
.png){kind=icon}
PRE
AI
DOI：10.1006/jpdc.2001.1812.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
This paper introduces a new parallel algorithm for computing an N( = n!)-point Lagrange interpolation on an n-star (n > 2). The proposed algorithm exploits several communication techniques on stars in a novel way, which can be adapted for computing similar functions. It is optimal and consists of three phases: initialization, main, and final. While there is no computation in the initialization phase, the main phase is composed of n!/2 steps, each consisting of four multiplications, four subtractions, and one communication operation and an additional step including one division and one multiplication. The final phase is carried out in (n-1) subphases each with O(log n) steps where each step takes three communications and one addition. Results from a cost-performance comparative analysis reveal that for practical network sizes the new algorithm on the star exhibits superior performance over those proposed for common interconnection networks. (C) 2002 Elsevier Science (USA).
Keywords:
interconnection networks
star graph
hypercubes
tori
parallel algorithms
Lagrange interpolation
speedup
cost-performance analysis
Journal
IF:
4
Papers:
3.8K
Citations:
4.8K
Organization
No organization information available