The product of two polynomials in a single variable of degree no more than N with coefficients from a ring, that is a set with addition, subtraction and multiplication operations, can be computed by our 1991 algorithm in O(N * log(N) * loglog(N)) ring operations. Recent improvements of the loglog(N) factor, based on Martin Fuehrer's 2007 speedup of integer multiplication on a Turing machine, have not yet been applicable to our setting, and the best-known algebraic complexity of polynomial multiplication over a ring remains that of 1991. Our algorithm originates from the 1971 Schoenhage-Strassen algorithm for integer multiplication, which is based on the fast Fourier transform but which synthesizes the necessary roots of unity, and we can eliminate all divisions by their orders. Our method of elimination of divisions has been applied to computing integral solutions of systems of sparse linear equations by Mark Giesbrecht in 1997. In my talk I will sketch the main ideas and some applications. My lecture is dedicated to the memory of my co-author David G. Cantor (1935 - 2012).
报告人简介：
Erich L. Kaltofen 现为美国北卡州立大学数学系教授。Kaltofen 教授的研究兴趣广泛，包括符号计算，符号-数值混合计算，代数复杂度，并行计算，编码与解码理论等。在符号计算方面，给出了多变元多项式的不可约分解的多项式时间算法。与支丽红等人的研究开启了符号-数值混合计算这一新的研究领域。2005年，关于稀疏多项式的快速分解算法的工作获得了该年度国际符号与代数计算年会(ISSAC) 的杰出论文奖。鉴于其在符号与代数计算，代数算法及其复杂度理论方面的杰出工作，2009年当选为美国计算机协会(ACM) 会士。
