A complete algorithm to find exact minimal polynomial by approximations

References

• Bailey , D. , Borwein , J. , Kapoor , V. and Weisstein , E. 2006 . Ten problems in experimental mathematics . Am. Math. Month. , 113 : 481 – 509 . (doi:10.2307/27641975)
   Web of Science ®Google Scholar
• Borwein , J. and Corless , R. 1999 . Emerging tools for experimental mathematics . Am. Math. Month. , 106 : 889 – 909 . (doi:10.2307/2589743)
   Web of Science ®Google Scholar
• P. Borwein, K.G. Hare, and A. Meichsener, Reverse Symbolic Computations, The Identity Function, Proceedings from the Maple Summer Workshop, Maple Software, Waterloo, 2002.
   Google Scholar
• Borwein , J. M. and Lisonek , P. 2000 . Applications of integer relation algorithms . Disc. Math. , 217 : 65 – 82 . (doi:10.1016/S0012-365X(99)00256-3)
   Web of Science ®Google Scholar
• Chèze , G. and Galligo , A. 2005 . “ Four lectures on polynomial absolute factorization ” . In Solving Polynomial Equations: Foundations, Algorithms, and Applications , Edited by: Dickenstein , A. and Emiris , I. Vol. 14 , 339 – 392 . Springer-Verlag : Algorithms and Computation in Mathematics .
   Google Scholar
• Chèze , G. and Galligo , A. 2006 . From an approximate to an exact absolute polynomial factorization . J. Symbol. Comput. , 41 : 682 – 696 . (doi:10.1016/j.jsc.2005.11.004)
   Web of Science ®Google Scholar
• J.W. Chen, Y. Feng, X.L. Qin, and J.Z. Zhang, Exact Polynomial Factorization by Approximate High Degree Algebraic Numbers, Proceedings of 2009 International Workshop on Symbolic–Numeric Computation SNC’09, ACM Press, New York, 2009, pp. 21–28.
   Google Scholar
• R.M. Corless, M.W. Giesbrecht, M. van Hoeij, I.S. Kotsireas, and S.M. Watt, Towards Factoring Bivariate Approximate Polynomials, Proceedings of 2001 International Symposium on Symbolic and Algebraic Computation ISSAC’01, ACM Press, New York, 2001, pp. 85–92.
   Google Scholar
• R.M. Corless, A. Galligo, I.S. Kotsireas, and S.M. Watt, A Geometric-Numeric Algorithm for Absolute Factorization of Multivariate Polynomials, Proceedings of 2002 International Symposium on Symbolic and Algebraic Computation ISSAC’02, ACM Press, New York, 2002, pp. 37–45.
   Google Scholar
• David , H. B. 2000 . Integer relation detection . Comput. Sci. Eng. , 2 : 24 – 28 . (doi:10.1109/5992.814653)
   Web of Science ®Google Scholar
• C. Fieker and C. Friedrichs, On reconstruction of algebraic numbers, in Algorithmic Number Theory (Leiden, 2000), LNCS Vol. 1838, Springer-Verlag, Berlin, Heidelberg, 2000, pp. 285–296.
   Google Scholar
• Ferguson , H. R.P. , Bailey , D. H. and Arno , S. 1999 . Analysis of PSLQ, an integer relation finding algorithm . Math. Comput. , 68 : 351 – 369 . (doi:10.1090/S0025-5718-99-00995-3)
   Web of Science ®Google Scholar
• Just , B. 1989 . Integer relations among algebraic numbers . Math. Found. Comput. Sci. , : 314 – 320 .
   Google Scholar
• Kaltofen , E. 2000 . Challenges of symbolic computation: My favorite open problems . J. Symbol. Comput. , 29 : 891 – 919 . (doi:10.1006/jsco.2000.0370)
   Web of Science ®Google Scholar
• E. Kaltofen, B. Li, Z.F. Yang, and L.H. Zhi, Exact Certification of Global Optimality of Approximate Factorizations via Rationalizing Sums-of-Squares with Floating Point Scalars, Proceedings of 2008 International Symposium on Symbolic and Algebraic Computation ISSAC’08, ACM Press, New York, pp. 155–163.
   Google Scholar
• R. Kannan, A.K. Lenstra, and L. Lovász, Polynomial Factorization and Nonrandomness of Bits of Algebraic and Some Transcendental Numbers, Proceedings of the Sixteenth Annual ACM Symposium on Theory of Computing STOC’84, ACM Press, New York, 1984, pp. 191–200.
   Google Scholar
• Kannan , R. , Lenstra , A. K. and Lovász , L. 1988 . Polynomial factorization and nonrandomness of bits of algebraic and some transcendental numbers . Math. Comput. , 50 : 235 – 250 . (doi:10.1090/S0025-5718-1988-0917831-4)
   Web of Science ®Google Scholar
• Knuth , D. E. 2008 . The Art of Computer Programming, Volume 2: Seminumerical Algorithms , 3 , Beijing : China Machine Press .
   Google Scholar
• Lang , S. 2002 . Algebra , 3 , New York : Springer-Verlag .
   Google Scholar
• Li , B. , Nie , J. and Zhi , L. H. 2008 . Approximate GCDs of polynomials and sparse SOS relaxations . Theor. Comput. Sci. , 409 : 200 – 210 . (doi:10.1016/j.tcs.2008.09.003)
   Web of Science ®Google Scholar
• Mignotte , M. and Stefanescu , D. 1999 . Polynomials: An Algorithmic Approach , Singapore : Springer-Verlag .
   Google Scholar
• I. Morel, D. Stehlé, and G. Villard, H-LLL: Using Householder Inside LLL, Proceedings of 2009 International Symposium on Symbolic and Computation ISSAC’09, ACM Press, New York, 2009, pp. 271–278.
   Google Scholar
• P.Q. Nguyen and D. Stehlé, Floating-point LLL Revisited, Proceedings of 24th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Aarhus, Denmark, EUROCRYPT 2005, 2005, pp. 215–233.
   Google Scholar
• Pablo , G. and Erwin , H. 2009 . Error estimates for the approximation of a class of optimal control systems governed by linear PDEs . Numer. Funct. Anal. Optim. , 30 : 523 – 547 . (doi:10.1080/01630560902987931)
   Web of Science ®Google Scholar
• X.L. Qin, Y. Feng, J.W. Chen, and J.Z. Zhang, Finding Exact Minimal Polynomial by Approximations, Proceedings of 2009 International Workshop on Symbolic–Numeric Computation SNC’09, ACM Press, New York, 2009, pp. 125–131.
   Google Scholar
• Qin , X. L. , Feng , Y. , Chen , J. W. and Li , J. 2010 . Exact representation of real algebraic number by approximations and its applications . J. Sichuan Univ. (Engineering Science Edition) (in Chinese) , 42 : 126 – 131 .
   Google Scholar
• Rump , S. M. 2005 . “ Computer-assisted proofs and self-validating methods ” . In Handbook of Accuracy and Reliability in Scientific Computation , Edited by: Einarsson , B. 195 – 240 . Philadelphia : Society for Industrial and Applied Mathematics .
   Google Scholar
• Schinzel , A. 2000 . Polynomials with Special Regard to Reducibility , Cambridge : Cambridge University Press .
   Google Scholar
• L.N. Trefethen, Predictions for Scientific Computing Fifty Years from Now, Technical Report, University of Manchester, 1998. Available at http://eprints.maths.ox.ac.uk/1304/.
   Google Scholar
• M.-P. Van Der Hulst and A.K. Lenstra, Factorization of Polynomials by Transcendental Evaluation, Proceedings of European Conference on Computer Algebra EUROCAL’85, LNCS Vol. 204, Springer-Verlag, Berlin, Heidelberg, 1985, pp. 138–145.
   Google Scholar
• Wu , W. T. 2005 . “ Hybrid computation ” . In 100 Interdisciplinary Science Puzzles of the 21st Century (in Chinese) , Edited by: Li , J. X. 656 – 657 . Beijing : Science Press .
   Google Scholar
• Wu , W. T. and Gao , X. S. 2007 . Mathematics mechanization and applications after thirty years . Front. Comput. Sci. China , 1 : 1 – 8 . (doi:10.1007/s11704-007-0001-8)
   Google Scholar
• Yaakub , A. R. and Evans , D. J. 1999 . A fourth order Runge–Kutta RK(4,4) method with error control . Int. J. Comput. Math. , 71 : 383 – 411 . (doi:10.1080/00207169908804817)
   Web of Science ®Google Scholar
• Yang , L. , Zhang , J. Z. and Hou , X. H. 1996 . Nonlinear Algebraic Equation System and Automated Theorem Proving (in Chinese) , Shanghai : Shanghai Scientific and Technological Education Publishing House .
   Google Scholar
• Zhang , J. Z. and Feng , Y. 2007 . Obtaining exact value by approximate computations . Sci. China Math. , 50 : 1361 – 1368 . (doi:10.1007/s11425-007-0092-6)
   Web of Science ®Google Scholar
• Zhou , S. P. and Cui , M. G. 2009 . Approximate solution for a variable-coefficient semilinear heat equation with nonlocal boundary conditions . Int. J. Comput. Math. , 86 : 2248 – 2258 . (doi:10.1080/00207160903229881)
   Web of Science ®Google Scholar