题目：New algorithms for polynomials of high degree

报告人：François VIGNERON, Université de Reims（兰斯大学）

时间：2024年12月18日（星期三）16: 00-17: 00

地点：东区第五教学楼5107教室

摘要：In this talk, I will first expose some of the well known algorithms to evaluate polynomials and find their roots. Next, I will present some new algorithms that we have developed in collaboration with R.Anton & N.Mihalache. Our new method can, on average, evaluate a polynomial of degree d with a computational cost of $O(\sqrt{d})$. The trick is to take fully advantage of the finite precision of computer arithmetic to discard the terms that have no influence on the result. We have implemented a C-library and the benchmarks confirm this result in practice. Regarding splitting, we have recently achieved an exhaustive certified list of the roots of some polynomials at the tera-scale (degree up to $10^{12}$) that are of interest for the study of the Mandelbrot set. As a side product of our investigations, our team has also discovered a new proof of the fundamental theorem of algebra, which is based on ODEs.