A complete algorithm to find exact minimal polynomial by approximations

DOI10.1080/00207160.2012.716199zbMATH Open1257.41017arXiv1001.0649OpenAlexW1888522205MaRDI QIDQ4902848FDOQ4902848

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)

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.

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

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

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)

Cites Work

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

Cited In (5)

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

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)