A simple and fast online power series multiplication and its analysis. (January 2016)

• Record Type: Journal Article
• Authors: Lebreton, Romain; Schost, Éric
• Is Part Of: Journal of symbolic computation. Volume 72(2016)
• Page Start: 231
• Page End: 251
• Publication Date: 2016-01
• Subjects: Online algorithm -- Relaxed algorithm -- Multiplication of power series -- Arithmetic complexity; Mathematics -- Data processing -- Periodicals; Numerical analysis -- Data processing -- Periodicals; Automatic programming (Computer science) -- Periodicals; Mathématiques -- Informatique -- Périodiques; Analyse numérique -- Informatique -- Périodiques; Programmation automatique -- Périodiques; Automatic programming (Computer science); Mathematics -- Data processing; Numerical analysis -- Data processing; Periodicals; Electronic journals; 510.285
• DOI: 10.1016/j.jsc.2015.03.001
• Languages: English
• ISSNs: 0747-7171

Abstract

Abstract: This paper focuses on online (or relaxed ) algorithms for the multiplication of power series over a field and their complexity analysis. We propose a new online algorithm for the multiplication using middle and short products of polynomials as building blocks, and we give the first precise analysis of the arithmetic complexity of various online multiplications. Our algorithm is faster than Fischer and Stockmeyer's by a constant factor; this is confirmed by experimental results.