### Abstract

We describe a new algorithm Miranda for isolating the simple zeros of a function f : R_{n} → Rn within a box B0 ⊆ R_{n}. 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.

Original language | English (US) |
---|---|

Title of host publication | ISSAC 2019 - Proceedings of the 2019 ACM International Symposium on Symbolic and Algebraic Computation |

Publisher | Association for Computing Machinery |

Pages | 355-362 |

Number of pages | 8 |

ISBN (Electronic) | 9781450360845 |

DOIs | |

State | Published - Jul 8 2019 |

Event | 44th ACM International Symposium on Symbolic and Algebraic Computation, ISSAC 2019 - Beijing, China Duration: Jul 15 2019 → Jul 18 2019 |

### Publication series

Name | Proceedings of the International Symposium on Symbolic and Algebraic Computation, ISSAC |
---|

### Conference

Conference | 44th ACM International Symposium on Symbolic and Algebraic Computation, ISSAC 2019 |
---|---|

Country | China |

City | Beijing |

Period | 7/15/19 → 7/18/19 |

### Keywords

- Certified Computation
- Complexity Analysis
- Effective Certified Algorithm
- Miranda Theorem
- Moore-Kioustelidis Test
- Root Isolation
- Subdivision Algorithms
- System of Real Equations

### ASJC Scopus subject areas

- Mathematics(all)

## Fingerprint Dive into the research topics of 'Effective subdivision algorithm for isolating zeros of real systems of equations, with complexity analysis'. Together they form a unique fingerprint.

## Cite this

*ISSAC 2019 - Proceedings of the 2019 ACM International Symposium on Symbolic and Algebraic Computation*(pp. 355-362). (Proceedings of the International Symposium on Symbolic and Algebraic Computation, ISSAC). Association for Computing Machinery. https://doi.org/10.1145/3326229.3326270