The bit-complexity of arithmetic algorithms

DOI10.1016/0196-6774(81)90016-XMaRDI QIDQ3928236zbMATH OpenOpenAlexFDO

Authors Victor Y. Pan

Publication date 1981

Published in Journal of Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0196-6774(81)90016-x

zbMATH Keywords

arithmetic complexitydiscrete Fourier transformpolynomial multiplicationspace-complexitytime-complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Cited in

(5)

• Polynomial division and its computational complexity
• The bit-cost of some algorithms for the solution of linear systems
• 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
• The bit-operation complexity of approximate evaluation of matrix and polynomial products using modular arithmetic

This page was built for publication: The bit-complexity of arithmetic algorithms

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