Never-failing, fast algebraic subdivision and root isolation for polynomials and analytic functions.

Holomorphic functions (such as trigonometric functions) naturally appear in many numerical computations. A fundamental problem here is to approximate the roots of these functions in a given subset of the complex plane. We apply the subdivision paradigm to this problem.

This involves studying the complexity of some existing algorithms as well as devising new predicates to determine termination. To study the complexity behavior, we will need perturbation bounds for such functions, and extend the techniques (especially, continuous amortization) that have been successful in the setting of polynomials. Using some existing techniques for polynomials, we may be able to speed up the convergence of the subdivision approach using a quadratically convergent iteration like Newton's. Our first, polynomial result brings the size of subdivision trees in almost all known algebraic methods down to O(n*logn), where n is the polynomial degree. Especially, this is independent of the root-separation.

Approximating roots of zero dimensional systems of polynomials is a fundamental problem in many areas (such as computing cylindrical algebraic decomposition of a set of polynomials). Standard subdivision-based approaches provide only linear convergence. However, for the case of univariate polynomials Abbott (ACM CommComputeralgebra, 2014) suggested an algorithm that combines the linearly converging subdivision approach with the super-linearly converging secant method to give an algorithm that works well in practice. The running time of Abbott's algorithm has been carefully analyzed. We aim to develop and analyze similar hybrid algorithms, with theoretical guarantees, for approximating common roots of two bivariate polynomials as a first step towards the more general setting in higher dimensions. Our algorithm will rely on interval methods for determining roots in a region of the plane.

Publikationen

• Batra, P.; Mignotte, M.; Stefanescu, D. c: Improvements of Lagrange's bound for polynomial roots. Journal of Symbolic Computation, 82: S. 19-25, 2017. , DOI: 10.1016/j.jsc.2016.10.001
• Batra, P.; Sharma, V.: Near Optimal Subdivision Algorithms for Real Root Isolation. Journal of Symbolic Computation, 83: S. 4-35, 2017. , DOI: 10.1016/j.jsc.2016.11.004
• V. Sharma and P. Batra: Near Optimal Subdivision Algorithms for Real Root Isolation. In Proceedings of the 2015 International Symposium on Symbolic and Algebraic Computation. ACM: S. 331–338, 2015. , DOI: doi:10.1145/2755996.2756656