TY - GEN
T1 - Effective subdivision algorithm for isolating zeros of real systems of equations, with complexity analysis
AU - Xu, Juan
AU - Yap, Chee
N1 - Publisher Copyright:
© 2019 Association for Computing Machinery.
PY - 2019/7/8
Y1 - 2019/7/8
N2 - We describe a new algorithm Miranda for isolating the simple zeros of a function f : Rn → Rn within a box B0 ⊆ Rn. The function f and its partial derivatives must have interval forms, but need not be polynomial. Our subdivision-based algorithm is “effective” in the sense that our algorithmic description also specifies the numerical precision that is sufficient to certify an implementation with any standard BigFloat number type. The main predicate is the Moore-Kioustelidis (MK) test, based on Miranda's Theorem (1940). Although the MK test is well-known, this paper appears to be the first synthesis of this test into a complete root isolation algorithm. We provide a complexity analysis of our algorithm based on intrinsic geometric parameters of the system. Our algorithm and complexity analysis are developed using 3 levels of description (Abstract, Interval, Effective). This methodology provides a systematic pathway for achieving effective subdivision algorithms in general.
AB - We describe a new algorithm Miranda for isolating the simple zeros of a function f : Rn → Rn within a box B0 ⊆ Rn. The function f and its partial derivatives must have interval forms, but need not be polynomial. Our subdivision-based algorithm is “effective” in the sense that our algorithmic description also specifies the numerical precision that is sufficient to certify an implementation with any standard BigFloat number type. The main predicate is the Moore-Kioustelidis (MK) test, based on Miranda's Theorem (1940). Although the MK test is well-known, this paper appears to be the first synthesis of this test into a complete root isolation algorithm. We provide a complexity analysis of our algorithm based on intrinsic geometric parameters of the system. Our algorithm and complexity analysis are developed using 3 levels of description (Abstract, Interval, Effective). This methodology provides a systematic pathway for achieving effective subdivision algorithms in general.
KW - Certified Computation
KW - Complexity Analysis
KW - Effective Certified Algorithm
KW - Miranda Theorem
KW - Moore-Kioustelidis Test
KW - Root Isolation
KW - Subdivision Algorithms
KW - System of Real Equations
UR - http://www.scopus.com/inward/record.url?scp=85069752003&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85069752003&partnerID=8YFLogxK
U2 - 10.1145/3326229.3326270
DO - 10.1145/3326229.3326270
M3 - Conference contribution
AN - SCOPUS:85069752003
T3 - Proceedings of the International Symposium on Symbolic and Algebraic Computation, ISSAC
SP - 355
EP - 362
BT - ISSAC 2019 - Proceedings of the 2019 ACM International Symposium on Symbolic and Algebraic Computation
PB - Association for Computing Machinery
T2 - 44th ACM International Symposium on Symbolic and Algebraic Computation, ISSAC 2019
Y2 - 15 July 2019 through 18 July 2019
ER -