Parallel output-sensitive algorithms for combinatorial and linear algebra problems

DOI10.1006/jcss.2000.1740zbMath0989.65055OpenAlexW1963827523MaRDI QIDQ5943098

John H. 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

parallel computationoutput-sensitive algorithmsbipartite matchingmatrix rankrandomized parallel algorithms

Mathematics Subject Classification ID

Cites Work

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

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