Parallel and output sensitive algorithms for combinatorial and linear algebra problems
The notion of output sensitive parallel algorithms for linear algebra problems is formalized in this paper, and such algorithms are presented for finding the rank of an n x n matrix in randomized parallel time 0(log n + logR) using 0(n2 + M(R)) processors, and for finding a maximum linearly independent subset of an n-set of n-dimensional vectors in randomized parallel time 0((log n) log3 R) using (n2 + RM(R)) processors (R is the size of the subset). Also, output sensitive TLSfC algorithms for some combinatorial problems are developed. The best TLSfC algorithm known for finding a maximum linearly independent subset of an n-set of n-dimensional vectors is given; the randomized parallel time is 0(logn) using 0(M(n)) processors. Note that this problem is likely harder than the problem of rinding a basis for the space spanned by the input vectors. An output sensitive TUfC algorithm for computing greatest common divisors of polynomials is developed. This result is due to the second author. A minimum vertex cover in a bipartite graph and a minimum X-Y vertex separator in a digraph can be found in randomized parallel time 0(log3 n) using 0(M(n)) processors (n is the number of vertices). This result is due to the first author. Note that this is the best complexity bound known for TLhfC algorithms, and matches the best TLSfC complexity bounds for the associated decision problems.
