Complexity of parallel matrix computations

DOI10.1016/0304-3975(87)90019-3zbMath0641.68058OpenAlexW1995272909MaRDI QIDQ1100892

Pan, Victor Y.

Publication date: 1987

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(87)90019-3

zbMATH Keywords

parallel complexitymatrix computations

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30) Parallel numerical computation (65Y05) Theory of operating systems (68N25) Numerical linear algebra (65Fxx)

Related Items (21)

Specified precision polynomial root isolation is in NC ⋮ Algebraic complexity of computing polynomial zeros ⋮ On polynomial ideals, their complexity, and applications ⋮ Sequential and parallel complexity of approximate evaluation of polynomial zeros ⋮ Parallel computation of polynomial GCD and some related parallel computations over abstract fields ⋮ Algebraic and numerical techniques for the computation of matrix determinants ⋮ Parallel evaluation of the determinant and of the inverse of a matrix ⋮ Matrix structures in parallel matrix computations ⋮ Optimal and nearly optimal algorithms for approximating polynomial zeros ⋮ Membership in polynomial ideals over Q is exponential space complete ⋮ Parallel algorithms for certain matrix computations ⋮ Computing the sign or the value of the determinant of an integer matrix, a complexity survey. ⋮ Parallel solution of linear systems by repeated squaring ⋮ Nearly optimal solution of rational linear systems of equations with symbolic lifting and numerical initialization ⋮ Parallel solution of Toeplitzlike linear systems ⋮ Parametrization of Newton's iteration for computations with structured matrices and applications ⋮ Efficient parallel factorization and solution of structured and unstructured linear systems ⋮ Fast and scalable parallel matrix computations with reconfigurable pipelined optical buses ⋮ Fast and efficient parallel solution of dense linear systems ⋮ Successive matrix squaring algorithm for computing the Drazin inverse ⋮ Parallel algorithms for matrix polynomial division

Cites Work

• How to multiply matrices faster
• Fast algorithms for the characteristic polynomial
• Algebraic complexity of computing polynomial zeros
• Matching is as easy as matrix inversion
• A new look at the Lanczos algorithm for solving symmetric systems of linear equations
• The complexity of partial derivatives
• An improved parallel processor bound in fast matrix inversion
• Improved processor bounds for combinatorial problems in RNC
• On the computational power of pushdown automata
• Fast algorithms for rational Hermite approximation and solution of Toeplitz systems
• Parallel Algorithms for Algebraic Problems
• Fast Probabilistic Algorithms for Verification of Polynomial Identities
• Fast Parallel Matrix Inversion Algorithms
• Fast parallel matrix and GCD computations
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Complexity of parallel matrix computations