Polynomial interpolation and polynomial root finding on OTIS-mesh

OTIS-mesh is an efficient model of optoelctronic parallel computers. In this paper, we develop several parallel algorithms for two important problems of numerical analysis, i.e., polynomial interpolation and polynomial root finding on this network. The algorithms are based on two schemes of data mapping namely, row–column mapping and group mapping in which the input data elements are arranged to store into row/column and group wise respectively by suitably exploiting the links of the network. We use Lagrange method for polynomial interpolation and Durand–Kerner method [T.L. Freeman, Calculating polynomial zeros on local memory parallel computer, Parallel Comput. 12 (1989) 351–358.] for polynomial root finding. The optimality/near optimality of the algorithms is shown to achieve with the assumption that the data elements are initially stored following the above mentioned mapping. The scalability of the algorithms is also studied.