Kai Hormann: Novel Range Functions via Taylor Expansions and Recursive Lagrange Interpolation with Application to Real Root Isolation
10 February 2023 - 10 February 2023
Room B1.17
Range functions are an important tool for interval computations, and they can be employed for the problem of root isolation. In this talk, I will first introduce two new classes of range functions for real functions. They are based on the remainder form by Cornelius and Lohner (1984) and provide different improvements for the remainder part of this form. On the one hand, I will show how centered Taylor expansions can be used to derive a generalization of the classical Taylor form with higher than quadratic convergence. On the other hand, I will discuss a recursive interpolation procedure, in particular based on quadratic Lagrange interpolation, leading to recursive Lagrange forms with cubic and quartic convergence. These forms can be used for isolating the real roots of square-free polynomials with the algorithm EVAL, a relatively recent algorithm that has been shown to be effective and practical. Finally, a comparison of the performance of these new range functions against the standard Taylor form will be given. Specifically, EVAL can exploit features of the recursive Lagrange forms which are not found in range functions based on Taylor expansion.
Experimentally, this yields at least a twofold speedup in EVAL.

The speaker

Kai Hormann is a full professor in the Faculty of Informatics at USI Lugano. He received a Ph.D. in computer science from the University of Erlangen-Nuremberg in 2002 and spent two years as a postdoctoral research fellow at Caltech in Pasadena and the CNR in Pisa, before joining Clausthal University of Technology as an assistant professor in 2004. During the winter term 2007/2008 he visited Freie Universität Berlin as a BMS substitute professor and came to Lugano as an associate professor in 2009. In 2018, he was a visiting professor at NTU Singapore. His research interests are focussed on the mathematical foundations of geometry processing algorithms as well as their applications in computer graphics and related fields. In particular, he is working on generalized barycentric coordinates, subdivision of curves and surfaces, barycentric rational interpolation, and dynamic geometry processing. Professor Hormann has published over 80 highly cited papers in the professional literature and is an associate editor of Computer Aided Geometric Design, Computers & Graphics, and the Dolomites Research Notes on Approximation. He served as chair of the SIAM Activity Group on Geometric Design in 2017/2018 and is entrusted with the chairmanship of the steering board of the international conference Geometric Modeling and Processing (GMP) since 2017.