A logarithmic Boolean time algorithm for parallel polynomial division

DOI10.1016/0020-0190(87)90139-6zbMath0653.68017OpenAlexW2086472440MaRDI QIDQ1107986

Dario Andrea Bini, Pan, Victor Y.

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

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

Related Items

Matrix structures in parallel matrix computations, Transformations of matrix structures work again

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• How to multiply matrices faster
• Polynomial division and its computational complexity
• The bit complexity of matrix multiplication and of related computations in linear algebra. The segmented \(\lambda\) algorithms
• The bit-operation complexity of matrix multiplication and of all pair shortest path problem
• Parallel Solution of Certain Toeplitz Linear Systems
• Logarithmic Depth Circuits for Algebraic Functions
• Fast parallel matrix and GCD computations
• Computational complexity of computing polynomials over the fields of real and complex numbers