Faster relaxed multiplication

DOI10.1145/2608628.2608657zbMath1325.68305OpenAlexW2106529515MaRDI QIDQ3452421

Joris van der Hoeven

Publication date: 11 November 2015

Published in: Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/2608628.2608657

zbMATH Keywords

complexityFFTpower seriescomputer algebramultiplicationonline algorithmfundamental algorithms

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30) Numerical methods for discrete and fast Fourier transforms (65T50) Formal power series rings (13F25) Online algorithms; streaming algorithms (68W27)

Related Items

On the complexity and parallel implementation of Hensel's lemma and Weierstrass preparation, Integer multiplication in time \(O(n\log n)\), Fast integer multiplication using generalized Fermat primes, Relaxed Hensel lifting of triangular sets, A simple and fast online power series multiplication and its analysis, Computing with D-algebraic power series, Fast amortized multi-point evaluation, From implicit to recursive equations, Fast Gröbner basis computation and polynomial reduction for generic bivariate ideals, Unnamed Item, On existence and uniqueness of formal power series solutions of algebraic ordinary differential equations

Uses Software

• Jordan

Cites Work

• Unnamed Item
• Unnamed Item
• An effective implementation of symbolic-numeric cylindrical algebraic decomposition for quantifier elimination
• Cylindrical algebraic decomposition using validated numerics
• The Jordan Curve Theorem, Formally and Informally
• On Computable Numbers, with an Application to the Entscheidungsproblem
• Definability and decision problems in arithmetic