A Parallel Algorithm for Parametric Cubic B-Spline Curves Interpolation

We present a parallel algorithm for solving the problem of interpolation by parametric B-spline curves in MIMD distributed memory message passing environments. The algorithm is based on a domain decomposition approach to the problem, in which the set of interpolation points is subdivided into several subsets and a local B-spline interpolating curve is formed in each subset. In order to obtain the global interplant as the union of local curve, suitable boundary conditions are imposed. Such domain decomposition approach leads to a linear system whose coefficient matrix is a particular almost block diagonal matrix and whose solution can therefore be obtained via efficient parallel algorithms in the considered environment. In particular the solver we used is based on a block Row-Projection iterative algorithm. Some numerical experiments carried out on the Intel Touchstone Delta System show that the proposed algorithm reaches an accurate solution in few iterations and is efficient and scalable in this computational environment.