The nine node Extrapolated Diffusion method for weighted torus graphs

The convergence analysis of the Extrapolated Diffusion (EDF) method was developed in Karagiorgos and Missirlis (2008) and Markomanolis and Missirlis (2010) for 2D weighted torus and mesh graphs, respectively using the set N1(i) of the nearest neighbors of a source node i in the graph. In the present work we propose a Diffusion scheme which employs the set N1(i)∪N2(i), where N2(i) denotes the set of the nearest neighbors of a source node i with path length two in an attempt to improve the performance of the new method. We develop the convergence analysis of the new EDF method by considering two subsets of N2(i) for 2D weighted torus graphs. In particular, we study five different communication routes for computing the load of each node i in the torus graph and for each route we find closed form formulae for the optimum values of the edge weights, the extrapolation parameters and the convergence factor of the new EDF scheme. A comparison of the convergence factors of all these EDF schemes reveals a 60% improvement in the performance using the cross communication route compared to the conventional EDF method, a fact which is shown theoretically and experimentally.