D-iteration: Evaluation of the Asynchronous Distributed Computation

The aim of this paper is to present a first evaluation of the potential of an asynchronous distributed computation associated to the recently proposed approach, D-iteration: the D-iteration is a fluid diffusion based iterative method, which has the advantage of being natively distributive. It exploits a simple intuitive decomposition of the matrix-vector product as elementary operations of fluid diffusion associated to a new algebraic representation. We show through experiments on real datasets how much this approach can improve the computation efficiency when the parallelism is applied: with the proposed solution, when the computation is distributed over K virtual machines (PIDs), the memory size to be handled by each virtual machine decreases linearly with K and the computation speed increases almost linearly with K with a slope becoming closer to one when the number N of linear equations to be solved increases. representation/interpretation/decomposition of the matrixvector product as elementary operations of fluid diffusion (cf. [8, 1]). This is an alternative solution to existing iterative methods (cf. [6, 16, 2]): its potential in the context of PageRank equation has been shown in [9] and the application of the approach in a general context is described in [8] (D-iteration). The complexity of the computation of the eigenvector of a matrix is a very well known problem and it increases rapidly with the dimension of the vector space. Efficient, accurate methods to compute eigenvectors of arbitrary matrices are in general a difficult problem (cf.