Extension of the parallel nested dissection algorithm to path algebra problems

This paper extends the author's parallel nested dissection algorithm of [PR] originally devised for solving sparse linear systems. We present a class of new applications of the nested dissection method, this time to path algebra computations, (in both cases of single source and all pair paths), where the path algebra problem is defined by a symmetric matrix A whose associated graph G with n vertices is planar. We substantially improve the known algorithms for path algebra problems of that general class: (Table presented.) (In case of parallel algorithms we assume that G is given with its O(√n)-separator family.) Further applications lead, in particular, to computing a maxflow and a mincut in an undirected planar network using O(log4n) parallel steps, n1.5/log n processors or alternatively O(log3n) steps, n2/log n processors, versus the known bounds, O(log2n) and n4, of [JV].

Duke Scholars

Author John H. Reif Computer Science