The Experts below are selected from a list of 64161 Experts worldwide ranked by ideXlab platform
Chee Yap - One of the best experts on this subject based on the ideXlab platform.
-
novel range functions via taylor expansions and recursive lagrange interpolation with application to Real Root isolation
International Symposium on Symbolic and Algebraic Computation, 2021Co-Authors: Kai Hormann, Lucas Kania, Chee YapAbstract:Range functions are an important tool for interval computations, and they can be employed for the problem of Root isolation. In this paper, we first introduce two new classes of range functions for Real functions. They are based on the remainder form by Cornelius and Lohner [7] and provide different improvements for the remainder part of this form. On the one hand, we use centered Taylor expansions to derive a generalization of the classical Taylor form with higher than quadratic convergence. On the other hand, we propose a recursive interpolation procedure, in particular based on quadratic Lagrange interpolation, leading to recursive Lagrange forms with cubic and quartic convergence. We then use these forms for isolating the Real Roots of square-free polynomials with the algorithm Eval, a relatively recent algorithm that has been shown to be effective and practical. Finally, we compare the performance of our new range functions against the standard Taylor form. Range functions are often compared in isolation; in contrast, our holistic comparison is based on their performance in an application. Specifically, Eval can exploit features of our recursive Lagrange forms which are not found in range functions based on Taylor expansion. Experimentally, this yields at least a twofold speedup in Eval.
-
near optimal tree size bounds on a simple Real Root isolation algorithm
International Symposium on Symbolic and Algebraic Computation, 2012Co-Authors: Vikram Sharma, Chee YapAbstract:The problem of isolating all Real Roots of a square-free integer polynomial f(X) inside any given interval I0 is a fundamental problem. EVAL is a simple and practical exact numerical algorithm for this problem: it recursively bisects I0, and any sub-interval I ⊆ I0, until a certain numerical predicate C0(I) V C1(I) holds on each I. We prove that the size of the recursion tree is O(d(L + r + log d)) where f has degree d, its coefficients have absolute values In the range L ≥ d, our bound is the sharpest known, and provably optimal. Our results are closely paralleled by recent bounds on EVAL by Sagraloff-Yap (ISSAC 2011) and Burr-Krahmer (2012). In the range L ≤ d, our bound is incomparable with those of Sagraloff-Yap or Burr-Krahmer. Similar to the Burr-Krahmer proof, we exploit the technique of "continuous amortization" from Burr-Krahmer-Yap (2009), namely to bound the tree size by an integral ∫IO G(x)dx over a suitable "charging function" G(x). We give an application of this feature to the problem of ray-shooting (i.e., finding smallest Root in a given interval).
-
near optimal tree size bounds on a simple Real Root isolation algorithm
International Symposium on Symbolic and Algebraic Computation, 2012Co-Authors: Vikram Sharma, Chee YapAbstract:The problem of isolating all Real Roots of a square-free integer polynomial f(X) inside any given interval I0 is a fundamental problem. EVAL is a simple and practical exact numerical algorithm for this problem: it recursively bisects I0, and any sub-interval I ⊆ I0, until a certain numerical predicate C0(I) V C1(I) holds on each I. We prove that the size of the recursion tree isO(d(L + r + log d))where f has degree d, its coefficients have absolute values
-
a simple but exact and efficient algorithm for complex Root isolation
International Symposium on Symbolic and Algebraic Computation, 2011Co-Authors: Chee Yap, Michael SagraloffAbstract:We present a new exact subdivision algorithm CEVAL for isolating the complex Roots of a square-free polynomial in any given box. It is a generalization of a previous Real Root isolation algorithm called EVAL. Under suitable conditions, our approach is applicable for general analytic functions. CEVAL is based on the simple Bolzano Principle and is easy to implement exactly. Preliminary experiments have shown its competitiveness. We further show that, for the "benchmark problem" of isolating all Roots of a square-free polynomial with integer coefficients, the asymptotic complexity of both algorithms EVAL and CEVAL matches (up a logarithmic term) that of more sophisticated Real Root isolation methods which are based on Descartes' Rule of Signs, Continued Fraction or Sturm sequence. In particular, we show that the tree size of EVAL matches that of other algorithms. Our analysis is based on a novel technique called Δ-clusters from which we expect to see further applications.
-
an efficient and exact subdivision algorithm for isolating complex Roots of a polynomial and its complexity analysis
2009Co-Authors: Michael Sagraloff, Max Planck, Chee YapAbstract:We introduce an exact subdivision algorithm CEVAL for isolating complex Roots of a square-free polynomial. The subdivision predicates are based on evaluating the original polynomial or its derivatives, and hence is easy to implement. It can be seen as a generalization of a previous Real Root isolation algorithm called EVAL. Under suitable conditions, the algorithm is applicable for general analytic functions. We provide a complexity analysis of our algorithm on the benchmark problem of isolating all complex Roots of a square-free polynomial with Gaussian integer coefficients. The analysis is based on a novel technique called �-clusters. This analysis shows, somewhat surprisingly, that the simple EVAL algorithm matches (up to logarithmic factors) the bit complexity bounds of current practical exact algorithms such as those based on Descartes, Continued Fraction or Sturm methods. Furthermore, the more general CEVAL also achieves the same complexity.
Vikram Sharma - One of the best experts on this subject based on the ideXlab platform.
-
near optimal subdivision algorithms for Real Root isolation
International Symposium on Symbolic and Algebraic Computation, 2015Co-Authors: Vikram Sharma, Prashant BatraAbstract:Isolating Real Roots of a square-free polynomial in a given interval is a fundamental problem. Subdivision based algorithms are a standard approach to solve this problem. E.g., Sturm's method,or various algorithms based on the Descartes's rule of signs. For isolating all the Real Roots of a degree n polynomial with Root separation σ, the subdivision tree size of most of these algorithms is bounded by O(log 1/σ) (assume σ
-
near optimal subdivision algorithms for Real Root isolation
arXiv: Numerical Analysis, 2015Co-Authors: Vikram Sharma, Prashant BatraAbstract:We describe a subroutine that improves the running time of any subdivision algorithm for Real Root isolation. The subroutine first detects clusters of Roots using a result of Ostrowski, and then uses Newton iteration to converge to them. Near a cluster, we switch to subdivision, and proceed recursively. The subroutine has the advantage that it is independent of the predicates used to terminate the subdivision. This gives us an alternative and simpler approach to recent developments of Sagraloff (2012) and Sagraloff-Mehlhorn (2013), assuming exact arithmetic. The subdivision tree size of our algorithm using predicates based on Descartes's rule of signs is bounded by $O(n\log n)$, which is better by $O(n\log L)$ compared to known results. Our analysis differs in two key aspects. First, we use the general technique of continuous amortization from Burr-Krahmer-Yap (2009), and second, we use the geometry of clusters of Roots instead of the Davenport-Mahler bound. The analysis naturally extends to other predicates.
-
near optimal tree size bounds on a simple Real Root isolation algorithm
International Symposium on Symbolic and Algebraic Computation, 2012Co-Authors: Vikram Sharma, Chee YapAbstract:The problem of isolating all Real Roots of a square-free integer polynomial f(X) inside any given interval I0 is a fundamental problem. EVAL is a simple and practical exact numerical algorithm for this problem: it recursively bisects I0, and any sub-interval I ⊆ I0, until a certain numerical predicate C0(I) V C1(I) holds on each I. We prove that the size of the recursion tree is O(d(L + r + log d)) where f has degree d, its coefficients have absolute values In the range L ≥ d, our bound is the sharpest known, and provably optimal. Our results are closely paralleled by recent bounds on EVAL by Sagraloff-Yap (ISSAC 2011) and Burr-Krahmer (2012). In the range L ≤ d, our bound is incomparable with those of Sagraloff-Yap or Burr-Krahmer. Similar to the Burr-Krahmer proof, we exploit the technique of "continuous amortization" from Burr-Krahmer-Yap (2009), namely to bound the tree size by an integral ∫IO G(x)dx over a suitable "charging function" G(x). We give an application of this feature to the problem of ray-shooting (i.e., finding smallest Root in a given interval).
-
near optimal tree size bounds on a simple Real Root isolation algorithm
International Symposium on Symbolic and Algebraic Computation, 2012Co-Authors: Vikram Sharma, Chee YapAbstract:The problem of isolating all Real Roots of a square-free integer polynomial f(X) inside any given interval I0 is a fundamental problem. EVAL is a simple and practical exact numerical algorithm for this problem: it recursively bisects I0, and any sub-interval I ⊆ I0, until a certain numerical predicate C0(I) V C1(I) holds on each I. We prove that the size of the recursion tree isO(d(L + r + log d))where f has degree d, its coefficients have absolute values
-
complexity of Real Root isolation using continued fractions
Theoretical Computer Science, 2008Co-Authors: Vikram SharmaAbstract:In this paper, we provide polynomial bounds on the worst case bit-complexity of two formulations of the continued fraction algorithm. In particular, for a square-free integer polynomial of degree n with coefficients of bit-length L, we show that the bit-complexity of Akritas' formulation is O@?(n^8L^3), and the bit-complexity of a formulation by Akritas and Strzebonski is O@?(n^7L^2); here O@? indicates that we are omitting logarithmic factors. The analyses use a bound by Hong to compute the floor of the smallest positive Root of a polynomial, which is a crucial step in the continued fraction algorithm. We also propose a modification of the latter formulation that achieves a bit-complexity of O@?(n^5L^2).
Elias Tsigaridas - One of the best experts on this subject based on the ideXlab platform.
-
nearly optimal refinement of Real Roots of a univariate polynomial
Journal of Symbolic Computation, 2016Co-Authors: Victor Y. Pan, Elias TsigaridasAbstract:We assume that a Real square-free polynomial A has a degree d, a maximum coefficient bitsize ? and a Real Root lying in an isolating interval and having no nonReal Roots nearby (we quantify this assumption). Then we combine the Double Exponential Sieve algorithm (also called the Bisection of the Exponents), the bisection, and Newton iteration to decrease the width of this inclusion interval by a factor of t = 2 - L . The algorithm has Boolean complexity O ? B ( d 2 ? + d L ) . This substantially decreases the known bound O ? B ( d 3 + d 2 L ) and is optimal up to a polylogarithmic factor. Furthermore we readily extend our algorithm to support the same upper bound on the complexity of the refinement of r Real Roots, for any r ? d , by incorporating the known efficient algorithms for multipoint polynomial evaluation. The main ingredient for the latter is an efficient algorithm for (approximate) polynomial division; we present a variation based on structured matrix computation with quasi-optimal Boolean complexity.
-
Simple and Efficient Real Root-finding for a Univariate Polynomial
2015Co-Authors: Victor Y. Pan, Elias Tsigaridas, Zhao LiangAbstract:Univariate polynomial Root-finding is a classical subject, still important for modern comput-ing. Frequently one seeks just the Real Roots of a polynomial with Real coefficients. They can be approximated at a low computational cost if the polynomial has no nonReal Roots, but for high degree polynomials, nonReal Roots are typically much more numerous than the Real ones. The challenge is known for long time, and the subject has been intensively studied. Nevertheless, we obtain dramatic acceleration of the known algorithms by applying new combinations of the known algorithms and properly exploiting the geometry of the complex plane. We confirm the efficiency of the proposed Real Root-finders by both their Boolean complexity estimates and the results of their numerical tests with benchmark polynomials. In particular in our tests the num-ber of iterations required for convergence of our algorithms grew very slowly as we increased the degree of the polynomials from 64 to 1024. Our techniques is very simple, and we point out their further modifications that promise to produce efficient complex polynomial Root-finders.
-
on the boolean complexity of Real Root refinement
International Symposium on Symbolic and Algebraic Computation, 2013Co-Authors: Victor Y. Pan, Elias TsigaridasAbstract:We assume that a Real square-free polynomial A has a degree d, a maximum coefficient bitsize τ and a Real Root lying in an isolating interval and having no nonReal Roots nearby (we quantify this assumption). Then, we combine the Double Exponential Sieve algorithm (also called the Bisection of the Exponents), the bisection, and Newton iteration to decrease the width of this inclusion interval by a factor of t=2-L. The algorithm has Boolean complexity OB(d2 τ + d L ). Our algorithms support the same complexity bound for the refinement of r Roots, for any r ≤ d.
-
univariate Real Root isolation in an extension field
International Symposium on Symbolic and Algebraic Computation, 2011Co-Authors: Adam Strzebonski, Elias TsigaridasAbstract:We present algorithmic, complexity and implementation results for the problem of isolating the Real Roots of a univariate polynomial in Bα ∈ L[y], where L=Qα is a simple algebraic extension of the rational numbers. We revisit two approaches for the problem. In the first approach, using resultant computations, we perform a reduction to a polynomial with integer coefficients and we deduce a bound of OB(N10) for isolating the Real Roots of Bα, where N is an upper bound on all the quantities (degree and bitsize) of the input polynomials. In the second approach we isolate the Real Roots working directly on the polynomial of the input. We compute improved separation bounds for the Roots and we prove that they are optimal, under mild assumptions. For isolating the Real Roots we consider a modified Sturm algorithm, and a modified version of Descartes' algorithm introduced by Sagraloff. For the former we prove a complexity bound of OB(N8) and for the latter a bound of OB(N7). We implemented the algorithms in C as part of the core library of Mathematica and we illustrate their efficiency over various data sets. Finally, we present complexity results for the general case of the first approach, where the coefficients belong to multiple extensions.
-
univariate Real Root isolation in an extension field
arXiv: Symbolic Computation, 2011Co-Authors: Adam Strzebonski, Elias TsigaridasAbstract:We present algorithmic, complexity and implementation results for the problem of isolating the Real Roots of a univariate polynomial in $B_{\alpha} \in L[y]$, where $L=\QQ(\alpha)$ is a simple algebraic extension of the rational numbers. We consider two approaches for tackling the problem. In the first approach using resultant computations we perform a reduction to a polynomial with integer coefficients. We compute separation bounds for the Roots, and using them we deduce that we can isolate the Real Roots of $B_{\alpha}$ in $\sOB(N^{10})$, where $N$ is an upper bound on all the quantities (degree and bitsize) of the input polynomials. In the second approach we isolate the Real Roots working directly on the polynomial of the input. We compute improved separation bounds for Real Roots and we prove that they are optimal, under mild assumptions. For isolating the Roots we consider a modified Sturm's algorithm, and a modified version of \func{descartes}' algorithm introduced by Sagraloff. For the former we prove a complexity bound of $\sOB(N^8)$ and for the latter a bound of $\sOB(N^{7})$. We implemented the algorithms in \func{C} as part of the core library of \mathematica and we illustrate their efficiency over various data sets. Finally, we present complexity results for the general case of the first approach, where the coefficients belong to multiple extensions.
Mohab Safey El Din - One of the best experts on this subject based on the ideXlab platform.
-
Real Root finding for low rank linear matrices
Applicable Algebra in Engineering Communication and Computing, 2020Co-Authors: Didier Henrion, Simone Naldi, Mohab Safey El DinAbstract:We consider \(m \times s\) matrices (with \(m\ge s\)) in a Real affine subspace of dimension n. The problem of finding elements of low rank in such spaces finds many applications in information and systems theory, where low rank is synonymous of structure and parsimony. We design computer algebra algorithms, based on advanced methods for polynomial system solving, to solve this problem efficiently and exactly: the input are the rational coefficients of the matrices spanning the affine subspace as well as the expected maximum rank, and the output is a rational parametrization encoding a finite set of points that intersects each connected component of the low rank Real algebraic set. The complexity of our algorithm is studied thoroughly. It is polynomial in \(\left( {\begin{array}{c}n+m(s-r)\\ n\end{array}}\right) \). It improves on the state-of-the-art in computer algebra and effective Real algebraic geometry. Moreover, computer experiments show the practical efficiency of our approach.
-
Real Root finding for equivariant semi algebraic systems
International Symposium on Symbolic and Algebraic Computation, 2018Co-Authors: Cordian Riener, Mohab Safey El DinAbstract:Let R be a Real closed field. We consider basic semi-algebraic sets defined by n -variate equations/inequalities of s symmetric polynomials and an equivariant family of polynomials, all of them of degree bounded by 2d
-
Real Root finding for determinants of linear matrices
Journal of Symbolic Computation, 2016Co-Authors: Didier Henrion, Simone Naldi, Mohab Safey El DinAbstract:Let A 0 , A 1 , ? , A n be given square matrices of size m with rational coefficients. The paper focuses on the exact computation of one point in each connected component of the Real determinantal variety { x ? R n : det ? ( A 0 + x 1 A 1 + ? + x n A n ) = 0 } . Such a problem finds applications in many areas such as control theory, computational geometry, optimization, etc. Under some genericity assumptions on the coefficients of the matrices, we provide an algorithm solving this problem whose runtime is essentially polynomial in the binomial coefficient ( n + m n ) . We also report on experiments with a computer implementation of this algorithm. Its practical performance illustrates the complexity estimates. In particular, we emphasize that for subfamilies of this problem where m is fixed, the complexity is polynomial in n.
-
Real Root finding for rank defects in linear hankel matrices
International Symposium on Symbolic and Algebraic Computation, 2015Co-Authors: Didier Henrion, Simone Naldi, Mohab Safey El DinAbstract:Let H0, …, H n be m x m matrices with entries in Q and Hankel structure, i.e. constant skew diagonals. We consider the linear Hankel matrix H(x) = H0+x1H_1+…+xnHn and the problem of computing sample points in each connected component of the Real algebraic set defined by the rank constraint rank}(H(x))≤ r, for a given integer r ≤ m-1. Computing sample points in Real algebraic sets defined by rank defects in linear matrices is a general problem that finds applications in many areas such as control theory, computational geometry, optimization, etc. Moreover, Hankel matrices appear in many areas of engineering sciences. Also, since Hankel matrices are symmetric, any algorithmic development for this problem can be seen as a first step towards a dedicated exact algorithm for solving semi-definite programming problems, i.e. linear matrix inequalities. Under some genericity assumptions on the input (such as smoothness of an incidence variety), we design a probabilistic algorithm for tackling this problem. It is an adaptation of the so-called critical point method that takes advantage of the special structure of the problem. Its complexity reflects this: it is essentially quadratic in specific degree bounds on an incidence variety. We report on practical experiments and analyze how the algorithm takes advantage of this special structure. A first implementation outperforms existing implementations for computing sample points in general Real algebraic sets: it tackles examples that are out of reach of the state-of-the-art.
-
Real Root finding for low rank linear matrices
arXiv: Symbolic Computation, 2015Co-Authors: Didier Henrion, Simone Naldi, Mohab Safey El DinAbstract:We consider $m \times s$ matrices (with $m\geq s$) in a Real affine subspace of dimension $n$. The problem of finding elements of low rank in such spaces finds many applications in information and systems theory, where low rank is synonymous of structure and parsimony. We design computer algebra algorithms, based on advanced methods for polynomial system solving, to solve this problem efficiently and exactly: the input are the rational coefficients of the matrices spanning the affine subspace as well as the expected maximum rank, and the output is a rational parametrization encoding a finite set of points that intersects each connected component of the low rank Real algebraic set. The complexity of our algorithm is studied thoroughly. It is polynomial in $\binom{n+m(s-r)}{n}$. It improves on the state-of-the-art in computer algebra and effective Real algebraic geometry. Moreover, computer experiments show the practical efficiency of our approach.
Michael Sagraloff - One of the best experts on this subject based on the ideXlab platform.
-
a simple but exact and efficient algorithm for complex Root isolation
International Symposium on Symbolic and Algebraic Computation, 2011Co-Authors: Chee Yap, Michael SagraloffAbstract:We present a new exact subdivision algorithm CEVAL for isolating the complex Roots of a square-free polynomial in any given box. It is a generalization of a previous Real Root isolation algorithm called EVAL. Under suitable conditions, our approach is applicable for general analytic functions. CEVAL is based on the simple Bolzano Principle and is easy to implement exactly. Preliminary experiments have shown its competitiveness. We further show that, for the "benchmark problem" of isolating all Roots of a square-free polynomial with integer coefficients, the asymptotic complexity of both algorithms EVAL and CEVAL matches (up a logarithmic term) that of more sophisticated Real Root isolation methods which are based on Descartes' Rule of Signs, Continued Fraction or Sturm sequence. In particular, we show that the tree size of EVAL matches that of other algorithms. Our analysis is based on a novel technique called Δ-clusters from which we expect to see further applications.
-
efficient Real Root approximation
International Symposium on Symbolic and Algebraic Computation, 2011Co-Authors: Michael Kerber, Michael SagraloffAbstract: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 at most 2-L, 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 requiring finite approximations of the polynomial coefficient 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 degree, coefficient size and discriminant. Our bound improves previous work on integer polynomials by a factor of deg f and essentially matches best known theoretical bounds on Root approximation which are obtained by very sophisticated algorithms.
-
on the complexity of Real Root isolation
arXiv: Data Structures and Algorithms, 2010Co-Authors: Michael SagraloffAbstract: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 $\tau$, our bound on the bit complexity writes as $\tilde{O}(n^3\tau^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.
-
an efficient and exact subdivision algorithm for isolating complex Roots of a polynomial and its complexity analysis
2009Co-Authors: Michael Sagraloff, Max Planck, Chee YapAbstract:We introduce an exact subdivision algorithm CEVAL for isolating complex Roots of a square-free polynomial. The subdivision predicates are based on evaluating the original polynomial or its derivatives, and hence is easy to implement. It can be seen as a generalization of a previous Real Root isolation algorithm called EVAL. Under suitable conditions, the algorithm is applicable for general analytic functions. We provide a complexity analysis of our algorithm on the benchmark problem of isolating all complex Roots of a square-free polynomial with Gaussian integer coefficients. The analysis is based on a novel technique called �-clusters. This analysis shows, somewhat surprisingly, that the simple EVAL algorithm matches (up to logarithmic factors) the bit complexity bounds of current practical exact algorithms such as those based on Descartes, Continued Fraction or Sturm methods. Furthermore, the more general CEVAL also achieves the same complexity.
