(2018.07.05 9:30pm N219)Chee K. Yap :Effective Subdivision Algorithm for Isolating Roots of Isolating Simple Rools of Real Systems, with Complexity Analysis
Time：2018-07-02 Source：KLMM
Title： Effective Subdivision Algorithm for Isolating Roots of Isolating Simple Rools of Real Systems, with Complexity Analysis
Speaker： Chee K. Yap (Courant Institute of Mathematical Science at New York University)
Time&Venue： 2018.07.05 9:30pm N219
Abstract:： We describe a new algorithm for isolating simple roots of a zero-dimensional real system within a box in $\RR^n$. The system is not necessarily polynomial. Our subdivision-based algorithm is effective in that it has provide explicit precision requirements to justify a rigorous BigFloat implemention. This is aided by the use of 3 levels of abstraction of our algorithmic primitives. The main predicate is the Moore-Kostelides (MK) test, which is based on the Miranda Theorem (1940). Although the MK test is well-known as a root finding technique, to our knowledge, it has not been synthesized into a complete global algorithm. Our algorithm uses two other predicates: an exclusion and a Jacobian test. We provide a complexity analysis of our algorithm based on intrinsic geometric parameters. (Joint Work with Juan Xu)
Home
Chinese
Contact
About