Parallel output-sensitive algorithms for combinatorial and linear algebra problems

This paper gives output-sensitive parallel algorithms whose performance dep ends on the output size and are significantly more efficient tall previous algorithms for problems with sufficiently small output size. Inputs are n x n matrices over a fixed ground field. Let P(n) and M(n) be the PRAM proces sor bounds for O(log n) time multiplication of two degree n polynomials, an d n x n matrices, respectively. Let T(n) be the time bounds, using M(n) pro cessors, for testing if an n x n matrix is nonsingular, and if so, computin g its inverse. We compute the rank R of a matrix in randomized parallel tim e O(log n + T (R) log R) using nP(n) + M(R) processors (P(n) + RP(R) proces sors for constant displacement rank matrices, e.g., Toeplitz matrices). We find a maximum linearly independent subset (MLIS) of an n-set of n-dimensio nal vectors in time O(T(n)log n) using M(n) randomized processors and we al so give output-sensitive algorithms for this problem. Applications include output-sensitive algorithms for finding: (i) a size R maximum matching in a n n-vertex graph using time O(T(R) log n) and nP(n)/T(R) + RM(R) processors , and (ii) a maximum matching in an n-vertex bipartite graph, with vertex s ubsets of sizes n(1) less than or equal to n(2), using time O(T(n(1)) log n ) and nP(n)/T(n(1)) + n(1) M(n(1)) processors. (C) 2001 Academic Press.