Parallel and output sensitive algorithms for combinatorial and linear algebra problems
Joseph Cheriyan, John H. Reif · 1993
The notion of output uensitive parallel algorithms for linear algebra problems is formalised in this paper, and such algorithms are presented for finding the rank R of an n x n matrix in randomised parallel time O(log n + logs@ using d(nz + iU(R)) processors, and for finding a maximum linearly independent subset of an n-set of n-dimensional vectors in randomised parallel time O((log n) logz R) using d(n2 + RIW(R)) processors (R is the sise of the subset).Also, output sensitive R.AfC algorithms for some combinatorial problems are developed.The best WC algorithm known for finding a maximum linearly independent subset of an n-set of n-dimensional vectors is giv+ the randomised parallel time ie O(logs TZ) using d(~(n)) processors.Note thatthis problem k-likely harder than the problem of finding a baais for the space spanned by the input vectors.An output sensitive 7WC-algorithm for computing greatest common divisors of polynomials is developed.This result is due to the second author.A miuimum vertex cover in a bipartite graph and a minimum X-Y vertex separator in a digraph can be found in rartdornised parallel time 0(log2 n) using d(lf(n)) processors (n is the number of vertices).This result is due to the first author.Not e that this is the best complexity bound known for 'RhfC algorithms, and matches the best R.Afc complexity bounds for the associated deciuion problems.1