The Experts below are selected from a list of 7767 Experts worldwide ranked by ideXlab platform
Jae Wan Shim - One of the best experts on this subject based on the ideXlab platform.
-
Univariate Polynomial equation providing on-lattice higher-order models of thermal lattice Boltzmann theory.
Physical review. E Statistical nonlinear and soft matter physics, 2013Co-Authors: Jae Wan ShimAbstract:A Univariate Polynomial equation is presented. It provides on-lattice higher-order models of the thermal lattice Boltzmann equation. The models can be accurate up to any required level and can be applied to regular lattices, which allow efficient and accurate approximate solutions of the Boltzmann equation. We derive models approaching the complete Galilean invariant and providing accuracy of the fourth-order moment and beyond. We simulate one-dimensional thermal shock tube problems to illustrate the accuracy of our models. Moreover, we show the remarkably enhanced stability obtained by our models and our discretized equilibrium distributions.
-
Univariate Polynomial equation providing models of thermal lattice boltzmann theory
arXiv: Mathematical Physics, 2011Co-Authors: Jae Wan ShimAbstract:A Univariate Polynomial equation is presented. It provides models of the thermal lattice Boltzmann equation. The models can be accurate up to any required level and can be applied to regular lattices, which allow efficient and accurate approximate solutions of the Boltzmann equation. We derive models satisfying the complete Galilean invariant and providing accuracy of the 4th-order moment and beyond. We simulate thermal shock tube problems to illustrate the accuracy of our models and to show the remarkably enhanced stability obtained by our models and our discretized equilibrium distributions.
Pablo A Parrilo - One of the best experts on this subject based on the ideXlab platform.
-
explicit sos decompositions of Univariate Polynomial matrices and the kalman yakubovich popov lemma
Conference on Decision and Control, 2007Co-Authors: E M Aylward, S M Itani, Pablo A ParriloAbstract:The purpose of this paper is twofold. The first is to make explicit the relationship between sum of squares (SOS) decompositions of Univariate Polynomial matrices and the Kalman-Yakubovich-Popov (KYP) lemma. The second is to present an efficient algorithm for explicitly finding an SOS decomposition of such matrices, inspired by the Hamiltonian-type methods for the solution of Riccati equations.
-
CDC - Explicit SOS decompositions of Univariate Polynomial matrices and the Kalman-Yakubovich-Popov lemma
2007 46th IEEE Conference on Decision and Control, 2007Co-Authors: E M Aylward, S M Itani, Pablo A ParriloAbstract:The purpose of this paper is twofold. The first is to make explicit the relationship between sum of squares (SOS) decompositions of Univariate Polynomial matrices and the Kalman-Yakubovich-Popov (KYP) lemma. The second is to present an efficient algorithm for explicitly finding an SOS decomposition of such matrices, inspired by the Hamiltonian-type methods for the solution of Riccati equations.
Luca Gemignani - One of the best experts on this subject based on the ideXlab platform.
-
ISSAC - Structured matrix methods for Polynomial root-finding
Proceedings of the 2007 international symposium on Symbolic and algebraic computation - ISSAC '07, 2007Co-Authors: Luca GemignaniAbstract: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, 2007Co-Authors: Luca GemignaniAbstract: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.
-
Inverse power and Durand-Kerner iterations for Univariate Polynomial root-finding
Computers & Mathematics With Applications, 2004Co-Authors: Dario Andrea Bini, Luca GemignaniAbstract: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.
Éric Schost - One of the best experts on this subject based on the ideXlab platform.
-
ISSAC - Implementations of Efficient Univariate Polynomial Matrix Algorithms and Application to Bivariate Resultants
Proceedings of the 2019 on International Symposium on Symbolic and Algebraic Computation, 2019Co-Authors: Seung Gyu Hyun, Vincent Neiger, Éric SchostAbstract:Complexity bounds for many problems on matrices with Univariate Polynomial entries have been improved in the last few years. Still, for most related algorithms, efficient implementations are not available, which leaves open the question of the practical impact of these algorithms, e.g. on applications such as decoding some error-correcting codes and solving Polynomial systems or structured linear systems. In this paper, we discuss implementation aspects for most fundamental operations: multiplication, truncated inversion, approximants, interpolants, kernels, linear system solving, determinant, and basis reduction. We focus on prime fields with a word-size modulus, relying on Shoup's C++ library NTL. Combining these new tools to implement variants of Villard's algorithm for the resultant of generic bivariate Polynomials (ISSAC 2018), we get better performance than the state of the art for large parameters.
-
Implementations of efficient Univariate Polynomial matrix algorithms and application to bivariate resultants
arXiv: Symbolic Computation, 2019Co-Authors: Seung Gyu Hyun, Vincent Neiger, Éric SchostAbstract:Complexity bounds for many problems on matrices with Univariate Polynomial entries have been improved in the last few years. Still, for most related algorithms, efficient implementations are not available, which leaves open the question of the practical impact of these algorithms, e.g. on applications such as decoding some error-correcting codes and solving Polynomial systems or structured linear systems. In this paper, we discuss implementation aspects for most fundamental operations: multiplication, truncated inversion, approximants, interpolants, kernels, linear system solving, determinant, and basis reduction. We focus on prime fields with a word-size modulus, relying on Shoup's C++ library NTL. Combining these new tools to implement variants of Villard's algorithm for the resultant of generic bivariate Polynomials (ISSAC 2018), we get better performance than the state of the art for large parameters.
-
Implementations of efficient Univariate Polynomial matrix algorithms and application to bivariate resultants
2019Co-Authors: Seung Gyu Hyun, Vincent Neiger, Éric SchostAbstract:Complexity bounds for many problems about matrices with Univariate Polynomial entries have been improved in the last few years. Still, for most recent algorithms, efficient implementations are not yet available. This leaves open the question of the practical impact of these algorithms on potential applications, which include decoding some error-correcting codes and solving Polynomial systems or structured linear systems. In this paper, we describe the implementation of some of the most fundamental algorithms for Polynomial matrices: multiplication, truncated inversion, approximants, interpolants, kernels, linear system solving, and determinant. Our work currently focuses on prime fields with a word-size modulus and is based on Shoup's C++ library NTL. We combine these new tools to implement variants of Villard's recent algorithm for the resultant of generic bivariate Polynomials (ISSAC 2018), and exhibit parameter ranges for which they outperform previous state of the art.
-
complexity and performance results for non fft based Univariate Polynomial multiplication
ADVANCES IN MATHEMATICAL AND COMPUTATIONAL METHODS: ADDRESSING MODERN CHALLENGES OF SCIENCE TECHNOLOGY AND SOCIETY, 2011Co-Authors: Muhammad F. I. Chowdhury, Marc Moreno Maza, Wei Pan, Éric SchostAbstract:Today's parallel hardware architectures and computer memory hierarchies enforce revisiting fundamental algorithms which were often designed with algebraic complexity as the main complexity measure and with sequential running time as the main performance counter. This study is devoted to two algorithms of Univariate Polynomial multiplication; that are independent of the coefficient ring: the plain and the Toom‐Cook Univariate multiplications. We analyze their cache complexity and report on their parallel implementations in Cilk++ [1].
-
Complexity and performance results for non FFT-based Univariate Polynomial multiplication
ACM Communications in Computer Algebra, 2011Co-Authors: Muhammad F. I. Chowdhury, Marc Moreno Maza, Wei Pan, Éric SchostAbstract:Today's parallel hardware architectures and computer memory hierarchies enforce revisiting fundamental algorithms which were often designed with algebraic complexity as the main complexity measure and with sequential running time as the main performance counter. This study is devoted to two algorithms for Univariate Polynomial multiplication algorithms that are are independent of the coefficient ring: the plain and the Toom-Cook Univariate multiplications. We analyze their cache complexity and report on their parallel implementations in Cilk++.
Victor Y. Pan - One of the best experts on this subject based on the ideXlab platform.
-
CASC - Faster Numerical Univariate Polynomial Root-Finding by Means of Subdivision Iterations
Computer Algebra in Scientific Computing, 2020Co-Authors: Qi Luan, Victor Y. Pan, Wongeun Kim, Vitaly ZadermanAbstract: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.
-
faster numerical Univariate Polynomial root finding by means of subdivision iterations
Computer Algebra in Scientific Computing, 2020Co-Authors: Qi Luan, Victor Y. Pan, Wongeun Kim, Vitaly ZadermanAbstract: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 Acceleration of Nearly Optimal Univariate Polynomial Root-findERS.
arXiv: Numerical Analysis, 2018Co-Authors: Victor Y. PanAbstract:Univariate Polynomial root-finding has been studied for four millennia and is still the subject of intensive research. Hundreds of efficient algorithms for this task have been proposed. Two of them are nearly optimal. The first one, proposed in 1995, relies on recursive factorization of a Polynomial, is quite involved, and has never been implemented. The second one, proposed in 2016, relies on subdivision iterations, was implemented in 2018, and promises to be practically competitive, although user's current choice for Univariate Polynomial root-finding is the package MPSolve, proposed in 2000, revised in 2014, and based on Ehrlich's functional iterations. By proposing and incorporating some novel techniques we significantly accelerate both subdivision and Ehrlich's iterations. Moreover our acceleration of the known subdivision root-finders is dramatic in the case of sparse input Polynomials. Our techniques can be of some independent interest for the design and analysis of Polynomial root-finders.
-
Accelerated Approximation of the Complex Roots and Factors of a Univariate Polynomial
Theoretical Computer Science, 2017Co-Authors: Victor Y. Pan, Elias TsigaridasAbstract:The known algorithms approximate the roots of a complex Univariate Polynomial in nearly optimal arithmetic and Boolean time. They are, however, quite involved and require a high precision of computing when the degree of the input Polynomial is large, which causes numerical stability problems. We observe that these difficulties do not appear at the initial stages of the algorithms, and in our present paper we extend one of these stages, analyze it, and avoid the cited problems, still achieving the solution within a nearly optimal complexity estimates, provided that some mild initial isolation of the roots of the input Polynomial has been ensured. The resulting algorithms promise to be of some practical value for root-finding and can be extended to the problem of Polynomial factorization, which is of interest on its own right. We conclude with outlining such an extension, which enables us to cover the cases of isolated multiple roots and root clusters.
-
Accelerated Approximation of the Complex Roots and Factors of a Univariate Polynomial
Theoretical Computer Science, 2017Co-Authors: Victor Y. Pan, Elias TsigaridasAbstract:Abstract The algorithms of Pan (1995) [20] and Pan (2002) [22] approximate the roots of a complex Univariate Polynomial in nearly optimal arithmetic and Boolean time but require a precision of computing that exceeds the degree of the Polynomial. This causes numerical stability problems when the degree is large. We observe, however, that such a difficulty disappears at the initial stage of the algorithms, and in our present paper we extend this stage to root-finding within a nearly optimal arithmetic and Boolean complexity bounds provided that some mild initial isolation of the roots of the input Polynomial has been ensured. Furthermore our algorithm is nearly optimal for the approximation of the roots isolated in a fixed disc, square or another region on the complex plane rather than all complex roots of a Polynomial. Moreover the algorithm can be applied to a Polynomial given by a black box for its evaluation (even if its coefficients are not known); it promises to be of practical value for Polynomial root-finding and factorization, the latter task being of interest on its own right. We conclude with summarizing our algorithms and their extension to the approximation of isolated multiple roots and root clusters.
