The Experts below are selected from a list of 17121 Experts worldwide ranked by ideXlab platform

Victor Y. Pan - One of the best experts on this subject based on the ideXlab platform.

  • faster numerical univariate Polynomial Root finding by means of subdivision iterations
    Computer Algebra in Scientific Computing, 2020
    Co-Authors: Qi Luan, Victor Y. Pan, Wongeun Kim, Vitaly Zaderman
    Abstract:

    Root-finding for a univariate Polynomial is four millennia old and still highly important for Computer Algebra and various other fields. Subdivision Root-finders for a complex univariate Polynomial are known to be highly efficient and practically promising. The recent one by Becker et al. [2] competes for user’s choice and is nearly optimal for dense Polynomials represented in monomial basis, but [18] proposes and analyzes further significant acceleration, which becomes dramatic for Polynomials admitting their fast evaluation (e.g., sparse ones). Here and in the companion paper [19], we present some of these results and algorithms.

  • new practical advances in Polynomial Root clustering
    MACIS, 2019
    Co-Authors: Rémi Imbach, Victor Y. Pan
    Abstract:

    We report an ongoing work on clustering algorithms for complex Roots of a univariate Polynomial p of degree d with real or complex coefficients. As in their previous best subdivision algorithms our Root-finders are robust even for multiple Roots of a Polynomial given by a black box for the approximation of its coefficients, and their complexity decreases at least proportionally to the number of Roots in a region of interest (ROI) on the complex plane, such as a disc or a square, but we greatly strengthen the main ingredient of the previous algorithms. We build the foundation for a new counting test that essentially amounts to the evaluation of a Polynomial p and its derivative \(p'\), which is a major benefit, e.g., for sparse Polynomials p. Moreover with evaluation at about \(\log (d)\) points (versus the previous record of order d) we output correct number of Roots in a disc whose contour has no Roots of p nearby. Our second and less significant contribution concerns subdivision algorithms for Polynomials with real coefficients. Our tests demonstrate the power of the proposed algorithms.

  • new practical advances in Polynomial Root clustering
    arXiv: Symbolic Computation, 2019
    Co-Authors: Rémi Imbach, Victor Y. Pan
    Abstract:

    We report an ongoing work on clustering algorithms for complex Roots of a univariate Polynomial $p$ of degree $d$ with real or complex coefficients. As in their previous best subdivision algorithms our Root-finders are robust even for multiple Roots of a Polynomial given by a black box for the approximation of its coefficients, and their complexity decreases at least proportionally to the number of Roots in a region of interest (ROI) on the complex plane, such as a disc or a square, but we greatly strengthen the main ingredient of the previous algorithms. Namely our new counting test essentially amounts to the evaluation of a Polynomial $p$ and its derivative $p'$, which is a major benefit, e.g., for sparse Polynomials $p$. Moreover with evaluation at about $\log(d)$ points (versus the previous record of order $d$) we output correct number of Roots in a disc whose contour has no Roots of $p$ nearby. Moreover we greatly soften the latter requirement versus the known subdivision algorithms. Our second and less significant contribution concerns subdivision algorithms for Polynomials with real coefficients. Our tests demonstrate the power of the proposed algorithms.

  • old and new nearly optimal Polynomial Root finders
    Computer Algebra in Scientific Computing, 2019
    Co-Authors: Victor Y. Pan
    Abstract:

    Univariate Polynomial Root-finding has been studied for four millennia and still remains the subject of intensive research. Hundreds if not thousands of efficient algorithms for this task have been proposed and analyzed. Two nearly optimal solution algorithms have been devised in 1995 and 2016, based on recursive factorization of a Polynomial and subdivision iterations, respectively, but both of them are superseded in practice by Ehrlich’s functional iterations. By combining factorization techniques with Ehrlich’s and subdivision iterations we devise a variety of new Root-finders. They match or supersede the known algorithms in terms of their estimated complexity for Root-finding on the complex plane, in a disc, and in a line segment and promise to be practically competitive.

  • CASC - Old and New Nearly Optimal Polynomial Root-Finders.
    Computer Algebra in Scientific Computing, 2019
    Co-Authors: Victor Y. Pan
    Abstract:

    Univariate Polynomial Root-finding has been studied for four millennia and still remains the subject of intensive research. Hundreds if not thousands of efficient algorithms for this task have been proposed and analyzed. Two nearly optimal solution algorithms have been devised in 1995 and 2016, based on recursive factorization of a Polynomial and subdivision iterations, respectively, but both of them are superseded in practice by Ehrlich’s functional iterations. By combining factorization techniques with Ehrlich’s and subdivision iterations we devise a variety of new Root-finders. They match or supersede the known algorithms in terms of their estimated complexity for Root-finding on the complex plane, in a disc, and in a line segment and promise to be practically competitive.

Luca Gemignani - One of the best experts on this subject based on the ideXlab platform.

  • accurate Polynomial Root finding methods for symmetric tridiagonal matrix eigenproblems
    Computers & Mathematics With Applications, 2016
    Co-Authors: Luca Gemignani
    Abstract:

    In this paper we consider the application of Polynomial Root-finding methods to the solution of the tridiagonal matrix eigenproblem. All considered solvers are based on evaluating the Newton correction. We show that the use of scaled three-term recurrence relations complemented with error free transformations yields some compensated schemes which significantly improve the accuracy of computed results at a modest increase in computational cost. Numerical experiments illustrate that under some restriction on the conditioning the novel iterations can approximate and/or refine the eigenvalues of a tridiagonal matrix with high relative accuracy.

  • ISSAC - Structured matrix methods for Polynomial Root-finding
    Proceedings of the 2007 international symposium on Symbolic and algebraic computation - ISSAC '07, 2007
    Co-Authors: Luca Gemignani
    Abstract:

    In this paper we discuss the use of structured matrix methods for the numerical approximation of the zeros of a univariate Polynomial. In particular, it is shown that Root-finding algorithms based on floating-point eigenvalue computation can benefit from the structure of the matrix problem to reduce their complexity and memory requirements by an order of magnitude.

  • structured matrix methods for Polynomial Root finding
    International Symposium on Symbolic and Algebraic Computation, 2007
    Co-Authors: Luca Gemignani
    Abstract:

    In this paper we discuss the use of structured matrix methods for the numerical approximation of the zeros of a univariate Polynomial. In particular, it is shown that Root-finding algorithms based on floating-point eigenvalue computation can benefit from the structure of the matrix problem to reduce their complexity and memory requirements by an order of magnitude.

  • Quasiseparable structures of companion pencils under the QZ-algorithm
    Calcolo, 2005
    Co-Authors: Luca Gemignani
    Abstract:

    Matrix methods based on the QR eigenvalue algorithm applied to a companion matrix are customary for Polynomial Root-finding. These methods take advantage of recent results showing that the quasiseparable structure of the input matrix is maintained under the iterative process. The property enables the QR-iteration for a companion matrix to be performed in linear time using a linear memory space. In this note we show the invariance of the quasiseparable structure in the case where the algorithm we deal with is now the QZ-algorithm acting on companion pencils instead of companion matrices.

  • Inverse power and Durand-Kerner iterations for univariate Polynomial Root-finding
    Computers & Mathematics With Applications, 2004
    Co-Authors: Dario Andrea Bini, Luca Gemignani
    Abstract:

    Abstract Univariate Polynomial Root-finding is the oldest classical problem of mathematics and computational mathematics, and is still an important research topic, due to its impact on computational algebra and geometry. The Weierstrass (Durand-Kerner) approach and its variations as well as matrix methods based on the QR algorithm are among the most popular practical choices for simultaneous approximation of all Roots of a Polynomial. We propose an alternative application of the inverse power iteration to generalized companion matrices for Polynomial Root-finding, demonstrate its effectiveness, and relate its study to unifying the derivation of the Weierstrass (Durand-Kerner) algorithm (having quadratic convergence) and its extensions having convergence rates 4, 6, 8, …. Our experiments show substantial improvement versus the latter algorithm, even though the inverse power iteration is most effective for the more limited tasks of approximating a single Root or a few selected Roots.

Ai-long Zheng - One of the best experts on this subject based on the ideXlab platform.

Bahman Kalantari - One of the best experts on this subject based on the ideXlab platform.

  • Algorithms for quaternion Polynomial Root-finding
    Journal of Complexity, 2013
    Co-Authors: Bahman Kalantari
    Abstract:

    Abstract In 1941 Niven pioneered Root-finding for a quaternion Polynomial P ( x ) , proving the fundamental theorem of algebra (FTA) and proposing an algorithm, practical if the norm and trace of a solution are known. We present novel results on theory, algorithms and applications of quaternion Root-finding. Firstly, we give a new proof of the FTA resulting in explicit formulas for both exact and approximate quaternion Roots of P ( x ) in terms of exact and approximate complex Roots of the real Polynomial F ( x ) = P ( x ) P ¯ ( x ) , where P ¯ ( x ) is the conjugate Polynomial. In particular, if | F ( c ) | ≤ ϵ , then for a computable quaternion conjugate q of c , | P ( q ) | ≤ ϵ . Consequences of these include relevance of Root-finding methods for complex Polynomials, computation of bounds on zeros, and algebraic solution of special quaternion equations. Secondly, working directly in the quaternion space, we develop Newton and Halley methods and analyze their local behavior. Surprisingly, even for a quadratic quaternion Polynomial Newton’s method may not converge locally. Finally, we derive an analogue of the Bernoulli method in the quaternion space for computing the dominant Root in certain cases. This requires the development of an independent theory for the solution of quaternion homogeneous linear recurrence relations. These results also lay a foundation for quaternion polynomiography.

  • Polynomial Root finding methods whose basins of attraction approximate voronoi diagram
    Discrete and Computational Geometry, 2011
    Co-Authors: Bahman Kalantari
    Abstract:

    Given a complex Polynomial p(z) with at least three distinct Roots, we first prove that no rational iteration function exists where the basin of attraction of a Root coincides with its Voronoi cell. In spite of this negative result, we prove that the Voronoi diagram of the Roots can be well approximated through a high order sequence of iteration functions, the Basic Family, B m (z), m≥2. Let θ be a simple Root of p(z), V(θ) its Voronoi cell, and A m (θ) its basin of attraction with respect to B m (z). We prove that given any closed subset C of V(θ), including any homothetic copy of V(θ), there exists m 0 such that for all m≥m 0, C is also a subset of A m (θ). This implies that when all Roots of p(z) are simple, the basins of attraction of B m (z) uniformly approximate the Voronoi diagram of the Roots to within any prescribed tolerance. Equivalently, the Julia set of B m (z), and hence the chaotic behavior of its iterations, will uniformly lie to within prescribed strip neighborhood of the boundary of the Voronoi diagram. In a sense, this is the strongest property a rational iteration function can exhibit for Polynomials. Next, we use the results to define and prove an infinite layering within each Voronoi cell of a given set of points, whether known implicitly as Roots of a Polynomial equation, or explicitly via their coordinates. We discuss potential application of our layering in computational geometry.

  • Voronoi Diagrams and Polynomial Root-Finding
    2009 Sixth International Symposium on Voronoi Diagrams, 2009
    Co-Authors: Bahman Kalantari
    Abstract:

    Voronoi diagram of points in the Euclidean plane and its computation is foundational to computational geometry. Polynomial Root-finding is the origin of fundamental discoveries in all of mathematics and sciences. There is an intrinsic connection between Polynomial Root-finding in the complex plane and the approximation of Voronoi cells of its Roots via a fundamental family of iteration functions, the basic family. For instance, the immediate basin of attraction of a Root of a complex Polynomial under Newton's method is a rough approximation to its Voronoi cell. We formally introduce these connections through the Basic Family of iteration functions, its properties with respect to Voronoi diagrams, and a corresponding visualization called polynomiography. Polynomiography is a medium for art, math, education and science. By making use of the Basic Family we introduce a layering of the points within each Voronoi cell of a Polynomial Root and study its properties and potential applications. In particular, we prove some novel results about the basic family in connection with Voronoi diagrams.

  • ISVD - Voronoi Diagrams and Polynomial Root-Finding
    2009 Sixth International Symposium on Voronoi Diagrams, 2009
    Co-Authors: Bahman Kalantari
    Abstract:

    Voronoi diagram of points in the Euclidean plane and its computation is foundational to computational geometry. Polynomial Root-finding is the origin of fundamental discoveries in all of mathematics and sciences. There is an intrinsic connection between Polynomial Root-finding in the complex plane and the approximation of Voronoi cells of its Roots via a fundamental family of iteration functions, the Basic Family. For instance, the immediate basin of attraction of a Root of a complex Polynomial under Newton's method is a rough approximation to its Voronoi cell. We formally introduce these connections through the Basic Family of iteration functions, its properties with respect to Voronoi diagrams, and a corresponding visualization called polynomiography. Polynomiography is a medium for art, math, education and science. By making use of the Basic Family we introduce a layering of the points within each Voronoi cell of a Polynomial Root and study its properties and potential applications. In particular, we prove some novel results about the Basic Family in connection with Voronoi diagrams.

  • Polynomial Root-finding and Polynomiography
    2008
    Co-Authors: Bahman Kalantari
    Abstract:

    This book offers fascinating and modern perspectives into the theory and practice of the historical subject of Polynomial Root-finding, rejuvenating the field via polynomiography, a creative and novel computer visualization that renders spectacular images of a Polynomial equation. Polynomiography will not only pave the way for new applications of Polynomials in science and mathematics, but also in art and education. The book presents a thorough development of the basic family, arguably the most fundamental family of iteration functions, deriving many surprising and novel theoretical and practical applications such as: algorithms for approximation of Roots of Polynomials and analytic functions, polynomiography, bounds on zeros of Polynomials, formulas for the approximation of Pi, and characterizations or visualizations associated with a homogeneous linear recurrence relation. These discoveries and a set of beautiful images that provide new visions, even of the well-known Polynomials and recurrences, are the makeup of a very desirable book. This book is a must for mathematicians, scientists, advanced undergraduates and graduates, but is also for anyone with an appreciation for the connections between a fantastically creative art form and its ancient mathematical foundations. Contents: Approximation of Square-Roots and Their Visualizations; The Fundamental Theorem of Algebra and a Special Case of Taylor s Theorem; Introduction to the Basic Family and Polynomiography; Equivalent Formulations of the Basic Family; Basic Family as Dynamical System; Fixed Points of the Basic Family; Algebraic Derivation of the Basic Family and Characterizations; The Truncated Basic Family and the Case of Halley Family; Characterizations of Solutions of Homogeneous Linear Recurrence Relations; Generalization of Taylor s Theorem and Newton s Method; The Multipoint Basic Family and Its Order of Convergence; A Computational Study of the Multipoint Basic Family; A General Determinantal Lower Bound; Formulas for Approximation of Pi Based on Root-Finding Algorithms; Bounds on Roots of Polynomials and Analytic Functions; A Geometric Optimization and Its Algebraic Offsprings; Polynomiography: Algorithms for Visualization of Polynomial Equations; Visualization of Homogeneous Linear Recurrence Relations; Applications of Polynomiography in Art, Education, Science and Mathematics; Approximation of Square-Roots Revisited; Further Applications and Extensions of the Basic Family and Polynomiography.

Liang Zhao - One of the best experts on this subject based on the ideXlab platform.

  • real Polynomial Root finding by means of matrix and Polynomial iterations
    Theoretical Computer Science, 2017
    Co-Authors: Victor Y. Pan, Liang Zhao
    Abstract:

    Frequently one seeks approximation to all r real Roots of a Polynomial of degree n with real coefficients, which also has nonreal Roots. We split a Polynomial into two factors, one of which has degree r and has r real Roots. We approximate them at a low cost, and then decrease the arithmetic time of the known algorithms for this popular problem by roughly a factor of n/k, if k iterations prepare splitting. k is a small integer unless some nonreal Roots lie close to the real axis, but even if there nonreal Roots near the real axis, we substantially accelerate the known algorithms. We also propose a dual algorithm, operating with the associated structured matrices. At the price of minor increase of the arithmetic time, it facilitates numerical implementation. Our analysis and tests demonstrate the efficiency of our approach.

  • Polynomial Root Isolation by Means of Root Radii Approximation
    arXiv: Numerical Analysis, 2015
    Co-Authors: Victor Y. Pan, Liang Zhao
    Abstract:

    Univariate Polynomial Root-finding is a classical subject, still important for modern computing. Frequently one seeks just the real Roots of a real coefficient Polynomial. 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. The Boolean cost bounds for the refinement of the simple and isolated real Roots have been decreased to nearly optimal, but the success has been more limited at the stage of the isolation of real Roots. We obtain substantial progress by applying the algorithm of of 1982 by Schoenhage for the approximation of the Root radii, that is, the distances of the Roots to the origin. Namely we isolate the simple and well-conditioned real Roots of a Polynomial at the Boolean cost dominated by the nearly optimal bounds for the refinement of such Roots. We also extend our algorithm to the isolation of complex, possibly multiple, Roots and Root clusters staying within the same (nearly optimal) asymptotic Boolean cost bound. Our numerical tests with benchmark Polynomials performed with the IEEE standard double precision show that our nearly optimal real Root-finder is practically promising. Our techniques are simple, and their power and application range may increase in combination with the known efficient methods.

  • Real Polynomial Root-finding by Means of Matrix and Polynomial Iterations
    arXiv: Symbolic Computation, 2015
    Co-Authors: Victor Y. Pan, Liang Zhao
    Abstract:

    Univariate Polynomial Root-finding is a classical subject, still important for modern computing. 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 a long time, and the subject has been intensively studied. Nevertheless, we produce some novel ideas and techniques and obtain dramatic acceleration of the known algorithms. In order to achieve our progress we exploit the correlation between the computations with matrices and Polynomials, randomized matrix computations, and complex plane geometry, extend the techniques of the matrix sign iterations, and use the structure of the companion matrix of the input Polynomial. The results of our extensive tests with benchmark Polynomials and random matrices are quite encouraging. In particular in our tests the number of iterations required for convergence of our algorithms grew very slowly (if at all) as we increased the degree of the univariate input Polynomials and the dimension of the input matrices from 64 to 1024.