A logarithmic Boolean time algorithm for parallel polynomial division

DOI10.1016/0020-0190(87)90139-6MaRDI QIDQ1107986zbMATH OpenOpenAlexFDO

Authors Dario A. Bini, Victor Y. Pan

Publication date 1987

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0020-0190(87)90139-6

zbMATH Keywords

Boolean circuit complexitydivision with remainderinteger polynomialspolynomial divisionparallel computational complexitytriangular Toeplitz matrix inversioninterpolation by binary segmentation

Mathematics Subject Classification ID

Direct numerical methods for linear systems and matrix inversion (65F05) Analysis of algorithms and problem complexity (68Q25) Software, source code, etc. for problems pertaining to field theory (12-04)

Recommendations

• scientific article; zbMATH DE number 3958730
• Polynomial division and its computational complexity
• Improved Parallel Polynomial Division
• Very Fast Parallel Polynomial Arithmetic
• Parallel algorithms for matrix polynomial division

Cites work

• scientific article; zbMATH DE number 3856407 (Why is no real title available?)
• scientific article; zbMATH DE number 3750146 (Why is no real title available?)
• scientific article; zbMATH DE number 3471577 (Why is no real title available?)
• scientific article; zbMATH DE number 3566175 (Why is no real title available?)
• scientific article; zbMATH DE number 3628385 (Why is no real title available?)
• scientific article; zbMATH DE number 3383473 (Why is no real title available?)
• Computational complexity of computing polynomials over the fields of real and complex numbers
• Fast parallel matrix and GCD computations
• How to multiply matrices faster
• Logarithmic Depth Circuits for Algebraic Functions
• Parallel Solution of Certain Toeplitz Linear Systems
• Polynomial division and its computational complexity
• The bit complexity of matrix multiplication and of related computations in linear algebra. The segmented algorithms
• The bit-operation complexity of matrix multiplication and of all pair shortest path problem

Cited in

(6)

• scientific article; zbMATH DE number 3958730 (Why is no real title available?)
• Matrix structures in parallel matrix computations
• Improved Parallel Polynomial Division
• Transformations of matrix structures work again
• Fast parallel algorithms for polynomial division over an arbitrary field of constants
• Polynomial division and its computational complexity

This page was built for publication: A logarithmic Boolean time algorithm for parallel polynomial division

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