Fast and efficient solution of path algebra problems

AbstractThis paper extends the author's parallel nested dissection algorithm (Pan and Reif, Technical Report 88-18, Computer Science Department, SUNY Albany, 1988) 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 the single source path problems and of the all pair path problems), where the path algebra problem is defined by a symmetric matrix A whose associated undirected graph G has a known family of separators of small size s(n) (in many cases of interest, s(n) = O(√n).) The assumption that G has known separators is reasonable in a large variety of practical dynamic situations, where G is fixed and the entries of the matrix A associated with the edges of G may vary with the input. We substantially improve the known algorithms for path algebra problems of this general class: Previous estimates Path problemSequential timeParallel timeProccessorsPrecomputed separatorsSingle sourceO(n2)O(n)O(I(n) log n)nn3/(I(n) log n)No YesAll pairsO(n3)O(n)O(I(n) log n)n2n3/(I(n) log n)No Yes New AlgrithmsPath problemSequential timeParallel timeProcessorsPrecomputed separatorsSingle sourceO(n1.5)O((log n) √n)O(I(n) log2 n)n/log nn1.5/(I(n) log n)No YesAll pairsO(n2log n)O((log n) √n)O(I(n) log2 n)n1.5n2/I(n) log n)No YesHere we assume that G is given with its O(√n)-separator family. The latter assumption can be lifted for the sequential time estimates and for O((log n) √n) parallel time estimates for planar graphs, because the evaluation of an O(√)-separator family can be done in O(n) sequential time (Lipton and Tarjan, SIAM J. Appl. Math.36, No. 2, (1979), 177–189) or, on PRAM, in O((log n) √n) parallel time with (√n)/log n processors (Gazit and Miller, manuscript, Computer Sci. Dept., University of Southern California, 1986), with small overhead constants in both cases. I(n) denotes parallel time of computing the sum of n values, I(n)=O(log n) for any EREW PRAM, I(n) = O(1) on a randomized CRCW PRAM. Furthermore using the randomized algorithm of (Gazit and Miller, in “Proceedings, 28th Annu. IEEE Symp. FOCS, 1987,” pp. 238–248), we may precompute separators of a planar graph using O(log2n) time, n + ƒ1+ϵ processors for a positive ϵ where ƒ is the number of faces; this is less than the cost of the subsequent path computation. Moreover, we preserve the above processor bounds but further decrease the parallel time by a factor of log n (via a modification of our new algorithms based on pipelining) in the important case of computing the minimum cost paths in a planar graph. Further applications lead, in particular, to computing a maxflow and a mincut in an undirected planar network using O(I(n) log2 n) parallel steps, n1.5I(n)log n processors, versus the known bounds, O(log2 n) and n4, of (Johnson, J. ACM34, No. 4 (1987), 950–967)