Parallel and output sensitive algorithms for combinatorial and linear algebra problems


Conference Paper

© 1993 ACM. 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.

Full Text

Duke Authors

Cited Authors

  • Cheriyan, J; Reif, JH

Published Date

  • August 1, 1993

Published In

  • Proceedings of the 5th Annual Acm Symposium on Parallel Algorithms and Architectures, Spaa 1993

Start / End Page

  • 50 - 56

International Standard Book Number 10 (ISBN-10)

  • 0897915992

International Standard Book Number 13 (ISBN-13)

  • 9780897915991

Digital Object Identifier (DOI)

  • 10.1145/165231.165238

Citation Source

  • Scopus