Asynchronous methods for simultaneous determination of polynomial roots


S. Tričković, M. Trajković, M Petković




In this paper we present the implementation of simultaneous method for the determination of polynomial roots on a distributed memory multicomputer. The total cost of such a parallelization per iteration is the. sum of a computation time and a communication time needed for a total exchange of the data at each iteration step. In order to decrease the communication time, an asynchronous implementation is considered. The computation of the root approximations is still shared among processors but the updating is performed using only nearest neighbor communications. The price to be paid to decrease this time consists in reducing the order of convergence of asynchronous methods. A general theorem which consider the lower bound of the order of convergence is given. Also, the computational efficiency of the synchronous and asynchronous versions are studied in the case of hypercube topology.