A parallel algorithm for Lagrange interpolation on the cube-connected cycles

This paper introduces a parallel algorithm for computing an N = n2(n) point Lagrange interpolation on an n-dimensional cube-connected cycles (CCCn). T he algorithm consists of three phases: initialisation, main and final. Whil e there is no computation in the initialisation phase, the main phase is co mposed of n2(n-1) steps, each consisting of four multiplications, four subt ractions and one communication operation, and an additional step including one division and one multiplication. The final phase is carried out in two sub-phases. There are [n/2] steps in the first sub-phase, each including tw o additions and one communication, followed by the second sub-phase which c omprises n steps each consisting of one addition and two communication oper ations. (C) 2000 Elsevier Science B.V. All rights reserved.