BZPEERReading, trust and collaboration for research
Menu

Discover

GraphFollow connections around a paper, topic or saved view.

Workspaces

HomePick up where your research flow left off.InboxHandle requests, replies and notifications from one place.CollectionsCurate reading lists, evidence sets and shareable dossiers.ResearchSee your private provenance graph, trail and imports.CollaborationMove from discovery into focused discussion rooms.PublishDraft, preview and publish full-text research articles.

Network

ExpertsFind specialists worth following or asking for help.CommunitiesJoin research circles organized around shared work.PartnersSee external organizations active around the same topics.

Opportunities

ListingsBrowse roles, calls and collaborations with clearer fit signals.

Account

Log inReturn to your reading and collaboration workspace.Create accountStart saving work, following people and joining teams.
Log inCreate account

Researcher profile

Michael Sagraloff

Michael Sagraloff contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
Symbolic ComputationNumerical Analysismath.NAComputational Geometrymath.AGMathematical Softwaremath.GTComputational ComplexityData Structures and Algorithmsmath.AC

Trust snapshot

Quick read

Trust 21 - Emerging
16works
0followers
10topics
4close collaborators

Actions

Decide how to stay connected

Follow researcher0

Research graph

See the researcher in context

Open full explorer

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

16 published item(s)

preprint2016arXiv

A Near-Optimal Subdivision Algorithm for Complex Root Isolation based on the Pellet Test and Newton Iteration

We describe a subdivision algorithm for isolating the complex roots of a polynomial $F\in\mathbb{C}[x]$. Given an oracle that provides approximations of each of the coefficients of $F$ to any absolute error bound and given an arbitrary square $\mathcal{B}$ in the complex plane containing only simple roots of $F$, our algorithm returns disjoint isolating disks for the roots of $F$ in $\mathcal{B}$. Our complexity analysis bounds the absolute error to which the coefficients of $F$ have to be provided, the total number of iterations, and the overall bit complexity. It further shows that the complexity of our algorithm is controlled by the geometry of the roots in a near neighborhood of the input square $\mathcal{B}$, namely, the number of roots, their absolute values and pairwise distances. The number of subdivision steps is near-optimal. For the \emph{benchmark problem}, namely, to isolate all the roots of a polynomial of degree $n$ with integer coefficients of bit size less than $τ$, our algorithm needs $\tilde O(n^3+n^2τ)$ bit operations, which is comparable to the record bound of Pan (2002). It is the first time that such a bound has been achieved using subdivision methods, and independent of divide-and-conquer techniques such as Schönhage's splitting circle technique. Our algorithm uses the quadtree construction of Weyl (1924) with two key ingredients: using Pellet's Theorem (1881) combined with Graeffe iteration, we derive a "soft-test" to count the number of roots in a disk. Using Schröder's modified Newton operator combined with bisection, in a form inspired by the quadratic interval method from Abbot (2006), we achieve quadratic convergence towards root clusters. Relative to the divide-conquer algorithms, our algorithm is quite simple with the potential of being practical. This paper is self-contained: we provide pseudo-code for all subroutines used by our algorithm.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Computing Real Roots of Real Polynomials ... and now For Real!

Very recent work introduces an asymptotically fast subdivision algorithm, denoted ANewDsc, for isolating the real roots of a univariate real polynomial. The method combines Descartes' Rule of Signs to test intervals for the existence of roots, Newton iteration to speed up convergence against clusters of roots, and approximate computation to decrease the required precision. It achieves record bounds on the worst-case complexity for the considered problem, matching the complexity of Pan's method for computing all complex roots and improving upon the complexity of other subdivision methods by several magnitudes. In the article at hand, we report on an implementation of ANewDsc on top of the RS root isolator. RS is a highly efficient realization of the classical Descartes method and currently serves as the default real root solver in Maple. We describe crucial design changes within ANewDsc and RS that led to a high-performance implementation without harming the theoretical complexity of the underlying algorithm. With an excerpt of our extensive collection of benchmarks, available online at http://anewdsc.mpi-inf.mpg.de/, we illustrate that the theoretical gain in performance of ANewDsc over other subdivision methods also transfers into practice. These experiments also show that our new implementation outperforms both RS and mature competitors by magnitudes for notoriously hard instances with clustered roots. For all other instances, we avoid almost any overhead by integrating additional optimizations and heuristics.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Fast Approximate Polynomial Multipoint Evaluation and Applications

It is well known that, using fast algorithms for polynomial multiplication and division, evaluation of a polynomial $F \in \mathbb{C}[x]$ of degree $n$ at $n$ complex-valued points can be done with $\tilde{O}(n)$ exact field operations in $\mathbb{C},$ where $\tilde{O}(\cdot)$ means that we omit polylogarithmic factors. We complement this result by an analysis of approximate multipoint evaluation of $F$ to a precision of $L$ bits after the binary point and prove a bit complexity of $\tilde{O}(n(L + τ+ nΓ)),$ where $2^τ$ and $2^Γ,$ with $τ, Γ\in \mathbb{N}_{\ge 1},$ are bounds on the magnitude of the coefficients of $F$ and the evaluation points, respectively. In particular, in the important case where the precision demand dominates the other input parameters, the complexity is soft-linear in $n$ and $L$. Our result on approximate multipoint evaluation has some interesting consequences on the bit complexity of further approximation algorithms which all use polynomial evaluation as a key subroutine. Of these applications, we discuss in detail an algorithm for polynomial interpolation and for computing a Taylor shift of a polynomial. Furthermore, our result can be used to derive improved complexity bounds for algorithms to refine isolating intervals for the real roots of a polynomial. For all of the latter algorithms, we derive near-optimal running times.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

On the Complexity of Solving Zero-Dimensional Polynomial Systems via Projection

Given a zero-dimensional polynomial system consisting of n integer polynomials in n variables, we propose a certified and complete method to compute all complex solutions of the system as well as a corresponding separating linear form l with coefficients of small bit size. For computing l, we need to project the solutions into one dimension along O(n) distinct directions but no further algebraic manipulations. The solutions are then directly reconstructed from the considered projections. The first step is deterministic, whereas the second step uses randomization, thus being Las-Vegas. The theoretical analysis of our approach shows that the overall cost for the two problems considered above is dominated by the cost of carrying out the projections. We also give bounds on the bit complexity of our algorithms that are exclusively stated in terms of the number of variables, the total degree and the bitsize of the input polynomials.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Computing Real Roots of Real Polynomials

Computing the roots of a univariate polynomial is a fundamental and long-studied problem of computational algebra with applications in mathematics, engineering, computer science, and the natural sciences. For isolating as well as for approximating all complex roots, the best algorithm known is based on an almost optimal method for approximate polynomial factorization, introduced by Pan in 2002. Pan's factorization algorithm goes back to the splitting circle method from Schoenhage in 1982. The main drawbacks of Pan's method are that it is quite involved and that all roots have to be computed at the same time. For the important special case, where only the real roots have to be computed, much simpler methods are used in practice; however, they considerably lag behind Pan's method with respect to complexity. In this paper, we resolve this discrepancy by introducing a hybrid of the Descartes method and Newton iteration, denoted ANEWDSC, which is simpler than Pan's method, but achieves a run-time comparable to it. Our algorithm computes isolating intervals for the real roots of any real square-free polynomial, given by an oracle that provides arbitrary good approximations of the polynomial's coefficients. ANEWDSC can also be used to only isolate the roots in a given interval and to refine the isolating intervals to an arbitrary small size; it achieves near optimal complexity for the latter task.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

A Near-Optimal Algorithm for Computing Real Roots of Sparse Polynomials

Let $p\in\mathbb{Z}[x]$ be an arbitrary polynomial of degree $n$ with $k$ non-zero integer coefficients of absolute value less than $2^τ$. In this paper, we answer the open question whether the real roots of $p$ can be computed with a number of arithmetic operations over the rational numbers that is polynomial in the input size of the sparse representation of $p$. More precisely, we give a deterministic, complete, and certified algorithm that determines isolating intervals for all real roots of $p$ with $O(k^3\cdot\log(nτ)\cdot \log n)$ many exact arithmetic operations over the rational numbers. When using approximate but certified arithmetic, the bit complexity of our algorithm is bounded by $\tilde{O}(k^4\cdot nτ)$, where $\tilde{O}(\cdot)$ means that we ignore logarithmic. Hence, for sufficiently sparse polynomials (i.e. $k=O(\log^c (nτ))$ for a positive constant $c$), the bit complexity is $\tilde{O}(nτ)$. We also prove that the latter bound is optimal up to logarithmic factors.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

From Approximate Factorization to Root Isolation with Application to Cylindrical Algebraic Decomposition

We present an algorithm for isolating the roots of an arbitrary complex polynomial $p$ that also works for polynomials with multiple roots provided that the number $k$ of distinct roots is given as part of the input. It outputs $k$ pairwise disjoint disks each containing one of the distinct roots of $p$, and its multiplicity. The algorithm uses approximate factorization as a subroutine. In addition, we apply the new root isolation algorithm to a recent algorithm for computing the topology of a real planar algebraic curve specified as the zero set of a bivariate integer polynomial and for isolating the real solutions of a bivariate polynomial system. For input polynomials of degree $n$ and bitsize $τ$, we improve the currently best running time from $\tO(n^{9}τ+n^{8}τ^{2})$ (deterministic) to $\tO(n^{6}+n^{5}τ)$ (randomized) for topology computation and from $\tO(n^{8}+n^{7}τ)$ (deterministic) to $\tO(n^{6}+n^{5}τ)$ (randomized) for solving bivariate systems.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

On the Complexity of Computing with Planar Algebraic Curves

In this paper, we give improved bounds for the computational complexity of computing with planar algebraic curves. More specifically, for arbitrary coprime polynomials $f$, $g \in \mathbb{Z}[x,y]$ and an arbitrary polynomial $h \in \mathbb{Z}[x,y]$, each of total degree less than $n$ and with integer coefficients of absolute value less than $2^τ$, we show that each of the following problems can be solved in a deterministic way with a number of bit operations bounded by $\tilde{O}(n^6+n^5τ)$, where we ignore polylogarithmic factors in $n$ and $τ$: (1) The computation of isolating regions in $\mathbb{C}^2$ for all complex solutions of the system $f = g = 0$, (2) the computation of a separating form for the solutions of $f = g = 0$, (3) the computation of the sign of $h$ at all real valued solutions of $f = g = 0$, and (4) the computation of the topology of the planar algebraic curve $\mathcal{C}$ defined as the real valued vanishing set of the polynomial $f$. Our bound improves upon the best currently known bounds for the first three problems by a factor of $n^2$ or more and closes the gap to the state-of-the-art randomized complexity for the last problem.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Root Refinement for Real Polynomials

We consider the problem of approximating all real roots of a square-free polynomial $f$. Given isolating intervals, our algorithm refines each of them to a width of $2^{-L}$ or less, that is, each of the roots is approximated to $L$ bits after the binary point. Our method provides a certified answer for arbitrary real polynomials, only considering finite approximations of the polynomial coefficients and choosing a suitable working precision adaptively. In this way, we get a correct algorithm that is simple to implement and practically efficient. Our algorithm uses the quadratic interval refinement method; we adapt that method to be able to cope with inaccuracies when evaluating $f$, without sacrificing its quadratic convergence behavior. We prove a bound on the bit complexity of our algorithm in terms of the degree of the polynomial, the size and the separation of the roots, that is, parameters exclusively related to the geometric location of the roots. Our bound is near optimal and significantly improves previous work on integer polynomials. Furthermore, it essentially matches the best known theoretical bounds on root approximation which are obtained by very sophisticated algorithms. We also investigate the practical behavior of the algorithm and demonstrate how closely the practical performance matches our asymptotic bounds.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Exact Symbolic-Numeric Computation of Planar Algebraic Curves

We present a novel certified and complete algorithm to compute arrangements of real planar algebraic curves. It provides a geometric-topological analysis of the decomposition of the plane induced by a finite number of algebraic curves in terms of a cylindrical algebraic decomposition. From a high-level perspective, the overall method splits into two main subroutines, namely an algorithm denoted Bisolve to isolate the real solutions of a zero-dimensional bivariate system, and an algorithm denoted GeoTop to analyze a single algebraic curve. Compared to existing approaches based on elimination techniques, we considerably improve the corresponding lifting steps in both subroutines. As a result, generic position of the input system is never assumed, and thus our algorithm never demands for any change of coordinates. In addition, we significantly limit the types of involved exact operations, that is, we only use resultant and gcd computations as purely symbolic operations. The latter results are achieved by combining techniques from different fields such as (modular) symbolic computation, numerical analysis and algebraic geometry. We have implemented our algorithms as prototypical contributions to the C++-project CGAL. They exploit graphics hardware to expedite the symbolic computations. We have also compared our implementation with the current reference implementations, that is, LGP and Maple's Isolate for polynomial system solving, and CGAL's bivariate algebraic kernel for analyses and arrangement computations of algebraic curves. For various series of challenging instances, our exhaustive experiments show that the new implementations outperform the existing ones.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

A Worst-case Bound for Topology Computation of Algebraic Curves

Computing the topology of an algebraic plane curve $\mathcal{C}$ means to compute a combinatorial graph that is isotopic to $\mathcal{C}$ and thus represents its topology in $\mathbb{R}^2$. We prove that, for a polynomial of degree $n$ with coefficients bounded by $2^ρ$, the topology of the induced curve can be computed with $\tilde{O}(n^8(n+ρ^2))$ bit operations deterministically, and with $\tilde{O}(n^8ρ^2)$ bit operations with a randomized algorithm in expectation. Our analysis improves previous best known complexity bounds by a factor of $n^2$. The improvement is based on new techniques to compute and refine isolating intervals for the real roots of polynomials, and by the consequent amortized analysis of the critical fibers of the algebraic curve.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Arrangement Computation for Planar Algebraic Curves

We present a new certified and complete algorithm to compute arrangements of real planar algebraic curves. Our algorithm provides a geometric-topological analysis of the decomposition of the plane induced by a finite number of algebraic curves in terms of a cylindrical algebraic decomposition of the plane. Compared to previous approaches, we improve in two main aspects: Firstly, we significantly reduce the amount of exact operations, that is, our algorithms only uses resultant and gcd as purely symbolic operations. Secondly, we introduce a new hybrid method in the lifting step of our algorithm which combines the usage of a certified numerical complex root solver and information derived from the resultant computation. Additionally, we never consider any coordinate transformation and the output is also given with respect to the initial coordinate system. We implemented our algorithm as a prototypical package of the C++-library CGAL. Our implementation exploits graphics hardware to expedite the resultant and gcd computation. We also compared our implementation with the current reference implementation, that is, CGAL's curve analysis and arrangement for algebraic curves. For various series of challenging instances, our experiments show that the new implementation outperforms the existing one.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

On the Complexity of Real Root Isolation

We introduce a new approach to isolate the real roots of a square-free polynomial $F=\sum_{i=0}^n A_i x^i$ with real coefficients. It is assumed that each coefficient of $F$ can be approximated to any specified error bound. The presented method is exact, complete and deterministic. Due to its similarities to the Descartes method, we also consider it practical and easy to implement. Compared to previous approaches, our new method achieves a significantly better bit complexity. It is further shown that the hardness of isolating the real roots of $F$ is exclusively determined by the geometry of the roots and not by the complexity or the size of the coefficients. For the special case where $F$ has integer coefficients of maximal bitsize $τ$, our bound on the bit complexity writes as $\tilde{O}(n^3τ^2)$ which improves the best bounds known for existing practical algorithms by a factor of $n=deg F$. The crucial idea underlying the new approach is to run an approximate version of the Descartes method, where, in each subdivision step, we only consider approximations of the intermediate results to a certain precision. We give an upper bound on the maximal precision that is needed for isolating the roots of $F$. For integer polynomials, this bound is by a factor $n$ lower than that of the precision needed when using exact arithmetic explaining the improved bound on the bit complexity.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

On the Complexity of Solving a Bivariate Polynomial System

We study the complexity of computing the real solutions of a bivariate polynomial system using the recently proposed algorithm BISOLVE. BISOLVE is a classical elimination method which first projects the solutions of a system onto the $x$- and $y$-axes and, then, selects the actual solutions from the so induced candidate set. However, unlike similar algorithms, BISOLVE requires no genericity assumption on the input nor it needs any change of the coordinate system. Furthermore, extensive benchmarks from \cite{bes-bisolve-2011} confirm that the algorithm outperforms state of the art approaches by a large factor. In this work, we show that, for two polynomials $f,g\in\mathbb{Z}[x,y]$ of total degree at most $n$ with integer coefficients bounded by $2^τ$, BISOLVE computes isolating boxes for all real solutions of the system $f=g=0$ using $\Otilde(n^8τ^{2})$ bit operations, thereby improving the previous record bound by a factor of at least $n^{2}$.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

When Newton meets Descartes: A Simple and Fast Algorithm to Isolate the Real Roots of a Polynomial

We introduce a new algorithm denoted DSC2 to isolate the real roots of a univariate square-free polynomial f with integer coefficients. The algorithm iteratively subdivides an initial interval which is known to contain all real roots of f. The main novelty of our approach is that we combine Descartes' Rule of Signs and Newton iteration. More precisely, instead of using a fixed subdivision strategy such as bisection in each iteration, a Newton step based on the number of sign variations for an actual interval is considered, and, only if the Newton step fails, we fall back to bisection. Following this approach, our analysis shows that, for most iterations, we can achieve quadratic convergence towards the real roots. In terms of complexity, our method induces a recursion tree of almost optimal size O(nlog(n tau)), where n denotes the degree of the polynomial and tau the bitsize of its coefficients. The latter bound constitutes an improvement by a factor of tau upon all existing subdivision methods for the task of isolating the real roots. In addition, we provide a bit complexity analysis showing that DSC2 needs only \tilde{O}(n^3tau) bit operations to isolate all real roots of f. This matches the best bound known for this fundamental problem. However, in comparison to the much more involved algorithms by Pan and Schönhage (for the task of isolating all complex roots) which achieve the same bit complexity, DSC2 focuses on real root isolation, is very easy to access and easy to implement.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

An Elimination Method for Solving Bivariate Polynomial Systems: Eliminating the Usual Drawbacks

We present an exact and complete algorithm to isolate the real solutions of a zero-dimensional bivariate polynomial system. The proposed algorithm constitutes an elimination method which improves upon existing approaches in a number of points. First, the amount of purely symbolic operations is significantly reduced, that is, only resultant computation and square-free factorization is still needed. Second, our algorithm neither assumes generic position of the input system nor demands for any change of the coordinate system. The latter is due to a novel inclusion predicate to certify that a certain region is isolating for a solution. Our implementation exploits graphics hardware to expedite the resultant computation. Furthermore, we integrate a number of filtering techniques to improve the overall performance. Efficiency of the proposed method is proven by a comparison of our implementation with two state-of-the-art implementations, that is, LPG and Maple's isolate. For a series of challenging benchmark instances, experiments show that our implementation outperforms both contestants.

0 citations0 reviewsNo code linkedOpen access