Parallel output-sensitive algorithms for combinatorial and linear algebra problems

DOI10.1006/JCSS.2000.1740MaRDI QIDQ5943098zbMATH OpenOpenAlexFDO

Authors J. Reif

Publication date 15 July 2002

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1006/jcss.2000.1740

zbMATH Keywords

bipartite matchingmatrix rankoutput-sensitive algorithmsparallel computationrandomized parallel algorithms

Mathematics Subject Classification ID

Vector spaces, linear dependence, rank, lineability (15A03) Parallel numerical computation (65Y05)

Review text

The author presents an output-sensitive randomized parallel algorithm for computing the rank of a matrix. An output-sensitive randomized parallel algorithm for finding a maximum linearly independent subset is also presented. Some combinatorial applications of this algorithm on maximum matchings in graphs are discussed.

Recommendations

• Fast matrix rank algorithms and applications
• Fast matrix rank algorithms and applications
• Randomization and the parallel solution of linear algebra problems
• Randomized Parallel Algorithms for Matroid Union and Intersection, with Applications to Arborescences and Edge-Disjoint Spanning Trees
• scientific article; zbMATH DE number 1304350

Cites work

• A fast parallel algorithm to compute the rank of a matrix over an arbitrary field
• Asymptotically fast solution of Toeplitz and related systems of linear equations
• Constructing a perfect matching is in random NC
• Displacement ranks of matrices and linear equations
• Divide-and-Conquer Solutions of Least-Squares Problems for Matrices with Displacement Structure
• Fast Algorithms for Bipartite Network Flow
• Fast parallel matrix and GCD computations
• Fast Probabilistic Algorithms for Verification of Polynomial Identities
• Fast solution of toeplitz systems of equations and computation of Padé approximants
• scientific article; zbMATH DE number 3651744 (Why is no real title available?)
• scientific article; zbMATH DE number 3698383 (Why is no real title available?)
• scientific article; zbMATH DE number 107951 (Why is no real title available?)
• scientific article; zbMATH DE number 1256710 (Why is no real title available?)
• scientific article; zbMATH DE number 4120318 (Why is no real title available?)
• Improved processor bounds for combinatorial problems in RNC
• Inverses of Toeplitz Operators, Innovations, and Orthogonal Polynomials
• Matching is as easy as matrix inversion
• Matrix multiplication via arithmetic progressions
• Maximum matchings in general graphs through randomization
• On fast multiplication of polynomials over arbitrary algebras
• Parallel Prefix Computation
• Probabilistic parallel prefix computation
• Superfast Solution of Real Positive Definite Toeplitz Systems

This page was built for publication: Parallel output-sensitive algorithms for combinatorial and linear algebra problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5943098)