Towards faster real algebraic numbers

ABSTRACT

This paper presents a new encoding scheme for real algebraic number manipulations which enhances current Axiom's Real Closure. Algebraic manipulations are performed using different instantiations of sub-resultant like algorithms instead of Euclidean algorithms. This allows us to work in the ring of real algebraic integers instead of the field of real algebraic numbers avoiding many denominators.

REFERENCES

• 1: Saugata Basu , Richard Pollack , Marie-Françoise Roy, On the combinatorial and algebraic complexity of quantifier elimination, Journal of the ACM (JACM), v.43 n.6, p.1002-1045, Nov. 1996 [doi>10.1145/235809.235813]
• 2: J. Bochnak, M. Coste, and M. Roy. Géométrie algébrique réelle. Springer-Verlag, 1988.
• 3: George E. Collins , Rudiger Loos, Real zeroes of polynomials, Computer algebra: symbolic and algebraic computation (2nd ed.), Springer-Verlag New York, Inc., New York, NY, 1983
• 4: M. Coste, Thoms's lemma, the coding of real algebraic numbers and the computation of the topology of semi-algebraic sets, Journal of Symbolic Computation, v.5 n.1-2, p.121-129, February/April 1988 [doi>10.1016/S0747-7171(88)80008-7]
• 5: J. Della Dora, D. Discrescenzo, and D. Duval. About a new method method for computing in algebraic number fields. LNCS, 204, 1985.
• 6: L. Ducos. Optimizations of the subresultant algorithm. Journal of Pure and Applied Algebra, 1998.
• 7: D. Duval , L. González-Vega, Dynamic evaluation and real closure, Mathematics and Computers in Simulation, v.42 n.4-6, p.551-560, Nov. 1996
• 8: A. Hollcott. Finite Konstruktion geordneter algebraischer Erweterungen von geordneten Grundkorpern. PhD thesis, Univ of Hamburg, 1941.
• 9: S. Lang. Algebraic Numbers. Addison-Wesley Pub. Co., 1964.
• 10: S. Lang. Algebra. Addison-Wesley Pub. Co., 1969.
• 11: G. Lecerf. Dynamic evaluation and real closure. implementation in axiom. Rapport de Dea, available at http://www.medicis.polytechnique.fr/~lecerf/travaux/dea/drc.ps.
• 12: Zenon Ligatsikas , Renaud Rioboo , Marie-Françoise Roy, Generic computation of the real closure of an ordered field, Mathematics and Computers in Simulation, v.42 n.4-6, p.541-549, Nov. 1996
• 13: H. Lombardi and M. F. Roy. Elementary constructive theory of ordered fields. Progress in Mathematics, 34:249-262, 1991.
• 14: Henri Lombardi , Marie-Françoise Roy , Mohad Safey El Din, New structure theorem for subresultants, Journal of Symbolic Computation, v.29 n.4-5, p.663-690, April/May 2000 [doi>10.1006/jsco.1999.0322]
• 15: R. Loos. Generalized polynomial remainder sequences. In Computer Algebra, pages 115-137. Springer-Verlag, New-York, 1982.
• 16: M. Moreno Maza and R. Rioboo. Polynomial gcd computations over towers of algebraic extensions. LNCS, 948, 1996.
• 17: R. Rioboo. Computation of the real closure of an ordered field. In ISSAC'92, San Francisco, 1992. ACM Press.
• 18: Adam Wojciech Strzeboński, Computing in the field of complex algebraic numbers, Journal of Symbolic Computation, v.24 n.6, p.647-656, Dec. 1997 [doi>10.1006/jsco.1997.0158]
• 19: H. Zassenhauss. A real root calculus. In Computational Problems in Abstract Algebra, pages 383-392, Oxford, 1970. Pergamon Press.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.3 Numerical Linear Algebra
          Subjects: Linear systems (direct and iterative methods)

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Combinatorial algorithms

  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms
          Subjects: Analysis of algorithms

General Terms:
Algorithms, Documentation

Keywords:
algebraic integers, algebraic numbers, fractions, real closed fields, real closure, sub-resultants