Finding exact minimal polynomial by approximations

ABSTRACT

We present a new algorithm for reconstructing an exact algebraic number from its approximate value by using an improved parameterized integer relation construction method. Our result is consistent with 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. The experimental results show that the method is more efficient than identify in Maple for obtaining an exact algebraic number from its approximation. 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.

REFERENCES

• 1: Hans Boehm , Robert Cartwright, Exact real arithmetic formulating real numbers as functions, Research topics in functional programming, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
• 2: Hans-J. Boehm , Robert Cartwright , Mark Riggle , Michael J. O'Donnell, Exact real arithmetic: a case study in higher order programming, Proceedings of the 1986 ACM conference on LISP and functional programming, p.162-173, August 1986, Cambridge, Massachusetts, United States [doi>10.1145/319838.319860]
• 3: Jonathan M. Borwein , Petr Lisoněk, Applications of integer relation algorithms, Discrete Mathematics, v.217 n.1-3, p.65-82, April 2000 [doi>10.1016/S0012-365X(99)00256-3]
• 4: BORWEIN, P., HARE, K. G. and MEICHSNER, A. Reverse Symbolic Computations, The identity Fuction. http://www.math.uwaterloo.ca/Ükghare/Preprints/PDF/P9 MSWS.pdf
• 5: W. S. Brown, On Euclid's Algorithm and the Computation of Polynomial Greatest Common Divisors, Journal of the ACM (JACM), v.18 n.4, p.478-504, Oct. 1971 [doi>10.1145/321662.321664]
• 6: CHÉZE, G., GALLIGO, A. From an approximate to an exact absolute polynomial factorization. Journal of Symbolic Computation, 41: 682--696, 2006.
• 7: COLLINS, G. E. Polynomial remainder sequences and determinants. Amer. Math. Monthly, 73(1966): 708--712.
• 8: Robert M. Corless , André Galligo , Ilias S. Kotsireas , Stephen M. Watt, A geometric-numeric algorithm for absolute factorization of multivariate polynomials, Proceedings of the 2002 international symposium on Symbolic and algebraic computation, p.37-45, July 07-10, 2002, Lille, France [doi>10.1145/780506.780512]
• 9: Robert M. Corless , Mark Giesbrecht , Ilias S. Kotsireas , Stephen M. Watt, Numerical Implicitization of Parametric Hypersurfaces with Linear Algebra, Revised Papers from the International Conference on Artificial Intelligence and Symbolic Computation, p.174-183, July 17-19, 2000
• 10: Robert M. Corless , Mark W. Giesbrecht , Mark van Hoeij , Ilias S. Kotsireas , Stephen M. Watt, Towards factoring bivariate approximate polynomials, Proceedings of the 2001 international symposium on Symbolic and algebraic computation, p.85-92, July 2001, London, Ontario, Canada [doi>10.1145/384101.384114]
• 11: EDALAT, A. and POTTS, P. J. A new representation for exact real numbers. In Mathematical foundations of programming semantics (Pittsburgh, PA, 1997), page 14 pp. (electronic). Elsevier, Amsterdam, 1997.
• 12: Helaman R. P. Ferguson , David H. Bailey , Steve Arno, Analysis of PSLQ, an integer relation finding algorithm, Mathematics of Computation, v.68 n.225, p.351-369, Jan. 1999 [doi>10.1090/S0025-5718-99-00995-3]
• 13: Yuzhen Huang , Wenda Wu , Hans J. Stetter , Lihong Zhi, Pseudofactors of multivariate polynomials, Proceedings of the 2000 international symposium on Symbolic and algebraic computation, p.161-168, July 2000, St. Andrews, Scotland [doi>10.1145/345542.345616]
• 14: Bettina Just, Integer Relations Among Algebraic Numbers, Proceedings on Mathematical Foundations of Computer Science 1989, p.314-320, August 28-September 01, 1989
• 15: KANNAN, R., LENSTRA, A. K., and LOVÁSZ, L. Polynomial Factorization and Nonrandomness of Bits of Algebraic and Some Transcendental Numbers. Math. Comput. 50, 182(1988): 235--250.
• 16: LANG, S. Algebra, 3rd edition, Springer-Verlag, New York, 2002.
• 17: LOOS, B. Computing in Algebraic Extensions, Computer Algebra, (Ed. by B. Buchberger, et al), Springer-Verlag, (1982), pp. 173--187.
• 18: MIGNOTTE, M., An inequality about factors of polynomials, Math. Comp., 28, 128(1974): 1153--1157.
• 19: SASAKI, T., SUZUKI, M., et al. Approximate factorization of multivariate polynomials and absolute irreducibility testing. Japan J. Indust. Appl. Math. 8 (1991), 357--375.
• 20: SCHÖNHAGE, A. Quasi-gcd computations. J.Complexity. 1(1985): 118--137.
• 21: Marc-Paul van der Hulst , Arjen K. Lenstra, Factorization of Polynominals by Transcendental Evaluation, Research Contributions from the European Conference on Computer Algebra-Volume 2, p.138-145, April 01-03, 1985
• 22: YANG, L., ZHANG, J. Z., and HOU, X. R. A criterion of dependency between algebraic equation and its application. Proc. IWMN'92, Internat. Academic Publishers, pp. 110--134, 1992.
• 23: ZHANG, J. Z., FENG, Y. Obtaining Exact Value by Approximate Computations. Science in China Series A: Mathematics. 50, 9(2007): 1361--1368.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computations on polynomials

Additional Classification:
  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms
          Subjects: Algebraic algorithms

General Terms:
Algorithms, Experimentation

Keywords:
algebraic number, integer relation algorithm, minimal polynomial, numerical approximate computation, symbolic-numerical computation