A complete algorithm to find exact minimal polynomial by approximations

DOI10.1080/00207160.2012.716199MaRDI QIDQ4902848zbMATH OpenOpenAlexFDO

Authors Xiaolin Qin, Yong Feng, Jingwei Chen, Jingzhong Zhang

Publication date 18 January 2013

Published in International Journal of Computer Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1001.0649

zbMATH Keywords

minimal polynomialsymbolic-numerical computationerror controllable algorithminteger relation construction

Mathematics Subject Classification ID

Symbolic computation and algebraic computation (68W30) Uniqueness of best approximation (41A52) Numerical approximation and computational geometry (primarily algorithms) (65D99)

Abstract: We present a complete algorithm for finding an exact minimal polynomial from its approximate value by using an improved parameterized integer relation construction method. Our result is superior to the existence of error controlling on obtaining an exact rational number from its approximation. The algorithm is applicable for finding exact minimal polynomial of an algebraic number by its approximate root. This also enables us to provide an efficient method of converting the rational approximation representation to the minimal polynomial representation, and devise a simple algorithm to factor multivariate polynomials with rational coefficients. Compared with the subsistent methods, our method combines advantage of high efficiency in numerical computation, and exact, stable results in symbolic computation. we also discuss some applications to some transcendental numbers by approximations. Moreover, the Digits of our algorithm is far less than the LLL-lattice basis reduction technique in theory. In this paper, we completely implement how to obtain exact results by numerical approximate computations.

Recommendations

• Finding exact minimal polynomial by approximations
• Reconstructing a minimal polynomial from approximate algebraic numbers
• From an approximate to an exact absolute polynomial factorization
• A constructive algorithm for finding the exact roots of polynomials with computable real coefficients.
• Integer Relations Among Algebraic Numbers

Cites work

• scientific article; zbMATH DE number 1467743 (Why is no real title available?)
• A fourth order Runge–Kutta RK(4,4) method with error control
• Analysis of PSLQ, an integer relation finding algorithm
• Applications of integer relation algorithms
• Approximate gcds of polynomials and sparse SOS relaxations
• Approximate solution for a variable-coefficient semilinear heat equation with nonlocal boundary conditions
• Challenges of symbolic computation: My favorite open problems. With an additional open problem by Robert M. Corless and David J. Jeffrey
• Emerging Tools for Experimental Mathematics
• Error Estimates for the Approximation of a Class of Optimal Control Systems Governed by Linear PDEs
• From an approximate to an exact absolute polynomial factorization
• Obtaining exact value by approximate computations
• Ten Problems in Experimental Mathematics

Cited in

(5)

• A Method to Compute Minimal Polynomials
• Exact bivariate polynomial factorization over \(\mathbb Q\) by approximation of roots
• Finding exact minimal polynomial by approximations
• Reconstructing a minimal polynomial from approximate algebraic numbers
• Computing the determinant of a matrix with polynomial entries by approximation

This page was built for publication: A complete algorithm to find exact minimal polynomial by approximations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4902848)