A complete algorithm to find exact minimal polynomial by approximations

Abstract

Based on an improved parameterized integer relation construction method, a complete algorithm is proposed for finding an exact minimal polynomial from its approximate root. It relies on a study of the error controlling for its approximation. We provide a sufficient condition on the precision of the approximation, depending only on the degree and the height of its minimal polynomial. Our result is superior to the existent error controlling on obtaining an exact rational or algebraic number from its approximation. Moreover, some applications are presented and compared with the subsistent methods.

Keywords:

• error controllable algorithm
• symbolic–numerical computation
• integer relation construction
• minimal polynomial

2010 AMS Subject Classifications :

• 41A52
• 65D99
• 68W30

Acknowledgements

This work was partially supported by the National Basic Research Program of China (2011CB302402), the National Natural Science Foundation of China (91118001, 11171053), and the West Light Foundation of the Chinese Academy of Sciences. The authors are grateful to the anonymous referees for their helpful comments and suggestions.

Notes

ϵ is defined by the same way for the rest of this article.