A Parallel Algorithm for the Solution of the Deconvolution Problem on Heterogeneous Networks∗†

In this work we present a parallel algorithm for the so-lution of a least squares problem with structured matri-ces. This problem arises in many applications mainly re-lated to digital signal processing. The parallel algorithm is designed to speed up the sequential one on heteroge-neous networks of computers. The parallel algorithm fol-lows the HeHo strategy (Heterogeneous distribution of pro-cesses over processors with homogeneous distribution of computations over the processes) and is implemented us-ing HeteroMPI, a recently developed extension of MPI for programming high performance computations on heteroge-neous networks of computers. The obtained results validate HeteroMPI as a very useful tool for portable implementa-tion of parallel algorithms for heterogeneous environments. 1