Oracle computations in parallel numerical linear algebra

DOI10.1016/0304-3975(94)90102-3MaRDI QIDQ1325837zbMATH OpenOpenAlexFDO

Authors Mauro Leoncini, Bruno Codenotti, Giovanni Resta

Publication date 30 October 1994

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

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

zbMATH Keywords

oracle computationsparallel algorithmsparallel-time complexityreducibilityreduction algorithms

Mathematics Subject Classification ID

Parallel numerical computation (65Y05) Complexity and performance of numerical algorithms (65Y20)

Review text

Using a new notion of reducibility, the authors investigate the behaviour of several known reductions among important problems in linear algebra. The main concern is the relative parallel-time complexity of certain problems within the class NC. It is shown that, within the computational model considered, many known reduction algorithms do not extend whereas the extension of other ones requires additional care.

Recommendations

• Parallel algebraic reductions among numerical problems
• Randomization and the parallel solution of linear algebra problems
• scientific article; zbMATH DE number 434716
• Complexity of parallel matrix computations
• On speed versus accuracy: Some case studies

Cites work

• A taxonomy of problems with fast parallel algorithms
• An improved parallel processor bound in fast matrix inversion
• Computing Powers in Parallel
• Fast parallel matrix and GCD computations
• Fast Parallel Matrix Inversion Algorithms
• How to multiply matrices faster
• scientific article; zbMATH DE number 4213315 (Why is no real title available?)
• scientific article; zbMATH DE number 3949600 (Why is no real title available?)
• scientific article; zbMATH DE number 3513716 (Why is no real title available?)
• scientific article; zbMATH DE number 3624682 (Why is no real title available?)
• scientific article; zbMATH DE number 3628385 (Why is no real title available?)
• scientific article; zbMATH DE number 1142306 (Why is no real title available?)
• scientific article; zbMATH DE number 3999284 (Why is no real title available?)
• On Relating Time and Space to Size and Depth
• Optimization, approximation, and complexity classes
• Parallel algebraic reductions among numerical problems
• Parallel computation for well-endowed rings and space-bounded probabilistic machines
• Parallel evaluation of the determinant and of the inverse of a matrix

Cited in

(1)

• Parallel algebraic reductions among numerical problems

This page was built for publication: Oracle computations in parallel numerical linear algebra

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