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 (CCC_n). The algorithm consists of three phases: initialization, main and final. While there is no computation in the initialization phase, the main phase is composed of n2~n-1 steps, each consisting of four multiplication's, four subtractions 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 two additions and one communication, followed by the second sub-phase which comprises n steps each consisting of one addition and two communication operations.