Session S34 - Symbolic and Numerical Computation with Polynomials

Wednesday, July 21, 19:45 ~ 20:15 UTC-3

Novel Range Functions via Recursive Lagrange Interpolation, and its effectiveness in Real Root Isolation

Chee Yap

Courant, NYU, United States   -   This email address is being protected from spambots. You need JavaScript enabled to view it.

ABSTRACT: Range functions are an important tool for interval computations, and they can be employed for the problem of root isolation. In this paper, we first introduce new classes of range functions for real functions, using the remainder form framework of Cornelius and Lohner (1984). In particular, we propose a family of {\bf recursive Lagrange forms}. We then use some forms with cubic and quartic convergence for isolating the real roots of square-free polynomials with the algorithm {\bf Eval}, a relatively recent algorithm that has been shown to be effective and practical. Finally, we compare the performance of our new range functions against the standard Taylor forms. Range functions are often compared in isolation; in contrast, our holistic comparison is based on their performance in the {\bf Eval} algorithm. Here, some unique features of our recursive Lagrange forms which are not found in Taylor forms can be exploited. Theoretically, we expect a 3-fold speedup. Experimentally, we see a 2- to 4-fold speedup in {\bf Eval}.

Joint work with Kai Hormann (USI , Lugano, Switzerland) and Lucas Kania (USI, Lugano, Switzerland).

View abstract PDF