Parallel Output-Sensitive Algorithms for Combinatorial and Linear Algebra Problems
✍ Scribed by John H. Reif
- Publisher
- Elsevier Science
- Year
- 2001
- Tongue
- English
- Weight
- 160 KB
- Volume
- 62
- Category
- Article
- ISSN
- 0022-0000
No coin nor oath required. For personal study only.
✦ Synopsis
This paper gives output-sensitive parallel algorithms whose performance depends on the output size and are significantly more efficient tan previous algorithms for problems with sufficiently small output size. Inputs are n_n matrices over a fixed ground field. Let P(n) and M(n) be the PRAM processor bounds for O(log n) time multiplication of two degree n polynomials, and n_n matrices, respectively. Let T(n) be the time bounds, using M(n) processors, for testing if an n_n matrix is nonsingular, and if so, computing its inverse. We compute the rank R of a matrix in randomized parallel time O(log n+T(R) log R) using nP(n)+M(R) processors (P(n)+RP(R) processors for constant displacement rank matrices, e.g., Toeplitz matrices). We find a maximum linearly independent subset (MLIS) of an n-set of n-dimensional vectors in time O(T(n) log n) using M(n) randomized processors and we also give output-sensitive algorithms for this problem. Applications include output-sensitive algorithms for finding: (i) a size R maximum matching in an 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 subsets of sizes n 1 n 2 , using time O(T(n 1 ) log n) and nP(n)ÂT(n 1 )+ n 1 M(n 1 ) processors.