首页| English| 中国科学院

Effective Subdivision Algorithm for Isolating Roots of Isolating Simple Rools of Real Systems, with Complexity Analysis

副标题:

时间:2018-07-02  来源:数学机械化重点实验室

题目:           Effective Subdivision Algorithm for Isolating Roots of Isolating Simple Rools of Real Systems, with Complexity Analysis

报告人:      Chee K. Yap (Courant Institute of Mathematical Science at New York University)

时间地点:   2018.07.05  9:30pm  N219

摘要:           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)
相关附件
相关文档