## Parallel output-sensitive algorithms for combinatorial and linear algebra problems

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 n1 ≤ n2, using time O(T(n)1) log n) and nP(n)/T(n1 + n1M(n1) processors.

### Duke Scholars

## Published In

## DOI

## ISSN

## Publication Date

## Volume

## Issue

## Start / End Page

## Related Subject Headings

- Computation Theory & Mathematics
- 49 Mathematical sciences
- 46 Information and computing sciences
- 0806 Information Systems
- 0805 Distributed Computing
- 0802 Computation Theory and Mathematics

### Citation

*Journal of Computer and System Sciences*,

*62*(3), 398–412. https://doi.org/10.1006/jcss.2000.1740

*Journal of Computer and System Sciences*62, no. 3 (January 1, 2001): 398–412. https://doi.org/10.1006/jcss.2000.1740.

*Journal of Computer and System Sciences*, vol. 62, no. 3, Jan. 2001, pp. 398–412.

*Scopus*, doi:10.1006/jcss.2000.1740.

## Published In

## DOI

## ISSN

## Publication Date

## Volume

## Issue

## Start / End Page

## Related Subject Headings

- Computation Theory & Mathematics
- 49 Mathematical sciences
- 46 Information and computing sciences
- 0806 Information Systems
- 0805 Distributed Computing
- 0802 Computation Theory and Mathematics