SqFreeEVAL
SqFreeEVAL: An (almost) optimal real-root isolation algorithm. Let f be a univariate polynomial with real coefficients, f∈ℝ[X]. Subdivision algorithms based on algebraic techniques (e.g., Sturm or Descartes methods) are widely used for isolating the real roots of f in a given interval. In this paper, we consider a simple subdivision algorithm whose primitives are purely numerical (e.g., function evaluation). The complexity of this algorithm is adaptive because the algorithm makes decisions based on local data. The complexity analysis of adaptive algorithms (and this algorithm in particular) is a new challenge for computer science. In this paper, we compute the size of the subdivision tree for the SqFreeEVAL algorithm.The SqFreeEVAL algorithm is an evaluation-based numerical algorithm which is well-known in several communities. The algorithm itself is simple, but prior attempts to compute its complexity have proven to be quite technical and have yielded sub-optimal results. Our main result is a simple O(d(L+lnd)) bound on the size of the subdivision tree for the SqFreeEVAL algorithm on the benchmark problem of isolating all real roots of an integer polynomial f of degree d and whose coefficients can be written with at most L bits.Our proof uses two amortization-based techniques: first, we use the algebraic amortization technique of the standard Mahler-Davenport root bounds to interpret the integral in terms of d and L. Second, we use a continuous amortization technique based on an integral to bound the size of the subdivision tree. This paper is the first to use the novel analysis technique of continuous amortization to derive state of the art complexity bounds.
This software is also peer reviewed by journal TOMS.
This software is also peer reviewed by journal TOMS.
Keywords for this software
References in zbMATH (referenced in 10 articles , 1 standard article )
Showing results 1 to 10 of 10.
Sorted by year (- Burr, Michael; Gao, Shuhong; Tsigaridas, Elias: The complexity of subdivision for diameter-distance tests (2020)
- Becker, Ruben; Sagraloff, Michael; Sharma, Vikram; Yap, Chee: A near-optimal subdivision algorithm for complex root isolation based on the Pellet test and Newton iteration (2018)
- Burr, Michael A.: Continuous amortization and extensions: with applications to bisection-based root isolation (2016)
- Sagraloff, Michael; Mehlhorn, Kurt: Computing real roots of real polynomials (2016)
- Mehlhorn, Kurt; Sagraloff, Michael; Wang, Pengming: From approximate factorization to root isolation with application to cylindrical algebraic decomposition (2015)
- Wang, Cong; Chiang, Yi-Jen; Yap, Chee: On soft predicates in subdivision motion planning (2015)
- Yap, Chee K.: Soft subdivision search in motion planning. II: Axiomatics (2015)
- Sagraloff, Michael: On the complexity of the Descartes method when using approximate arithmetic (2014)
- Burr, Michael A.; Krahmer, Felix: SqFreeEVAL: An (almost) optimal real-root isolation algorithm (2012)
- Burr, Michael; Krahmer, Felix: Sqfreeeval: an (almost) optimal real-root isolation algorithm (2011) ioport