The Bath algebraic number package

ABSTRACT

This paper describes a package implemented in REDUCE 3.2 for the manipulation of algebraic numbers. The package regards algebraic numbers as elements of abstract extensions of the rational numbers, not as particular real or complex numbers. We describe in this paper the various design choices that were made, and the current state of the package, as well as future possibilities for enhancement.

REFERENCES

• Abbott et al., 1985: J. A. Abbott , R. J. Bradford , J. H. Davenport, A remark on factorisation, ACM SIGSAM Bulletin, v.19 n.2, p.31-33, May 1985 [doi>10.1145/1089402.1089408]
• Abbott et al., 1986: Abbott,J.A., Bradford,R.J., Davenport,J.H., The Bath Algebraic Number Package. Bath Computer Science Technical Report 2, Bath University 1986.
• Bradford et al., 1986: R. J. Bradford , A. C. Hearn , J. A. Padget , E. Schrüfer, Enlarging the REDUCE domain of computation, Proceedings of the fifth ACM symposium on Symbolic and algebraic computation, p.100-106, July 21-23, 1986, Waterloo, Ontario, Canada [doi>10.1145/32439.32460]
• Davenport, 1981: James H. Davenport, Integration of algebraic functions, Proceedings of the International Symposiumon on Symbolic and Algebraic Computation, p.415-425, June 01, 1979
• Davenport, 1985: Davenport,J,H., Computer Algebra for Cylindrical Algebraic Decomposition. TRITA-NA-8511, NADA, KTH, Stockholm, Sept. 1985.
• ffitch & Norman, 1977: ~tch. J.P.. Norman, A.C., Implementing LISP in a High-Level Language. Software - Practice and Experience, 7(1977). pp. 713-725
• Hearn, 1979: Anthony C. Hearn, Non-modular computation of polynomial GCD's using trial division, Proceedings of the International Symposiumon on Symbolic and Algebraic Computation, p.227-239, June 01, 1979
• Hearn, 1982: Anthony C. Hearn, REDUCE - A Case Study in Algebra System Development, Proceedings of the European Computer Algebra Conference on Computer Algebra, p.263-272, April 05-07, 1982
• Knuth, 1981: Donald E. Knuth, The art of computer programming, volume 2 (3rd ed.): seminumerical algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
• Landau, 1985: Landau,S., Factoring Polynomials over Algebraic Number fields. SIAM J.Comp, l(Feb 1985)pp. 184-195.
• Lenstra, 1982: Arjen K. Lenstra, Lattices and Factorization of Polynomials over Algebraic Number Fields, Proceedings of the European Computer Algebra Conference on Computer Algebra, p.32-39, April 05-07, 1982
• Lenstra, 1983: Arjen K. Lenstra, Factoring polynominals over algebraic number fields, Proceedings of the European Computer Algebra Conference on Computer Algebra, p.245-254, March 28-30, 1983
• Loos. 1982: Loos,R., Computing in Algebraic Extensions. Computing Suppl. 4 {Springer-Verlag 1982} pp. 173-187.
• McCallum. 1985: McCallum,S.. An Improved Projection Operation or Cylindrical Algebraic Decomposition. Computer Science Tech. Report 548, Univ. Wisconsin at Madison, Feb.. 1985.
• Moore & Norman, 1981: P. M. A. Moore , A. C. Norman, Implementing a polynomial factorization and GCD package, Proceedings of the fourth ACM symposium on Symbolic and algebraic computation, p.109-116, August 05-07, 1981, Snowbird, Utah, United States [doi>10.1145/800206.806379]
• Najid-Zejli, 1985: Najid-Zejli,H,, Extensions algdbriques: cas g~n~,ral et cas des radicaux. Th~se de troisieme cycle. IMAG, Grenoble, 25.6.85.
• Trager, 1976: Barry M. Trager, Algebraic factoring and rational function integration, Proceedings of the third ACM symposium on Symbolic and algebraic computation, p.219-226, August 10-12, 1976, Yorktown Heights, New York, United States [doi>10.1145/800205.806338]
• Wang, 1976: Waag.P.S,, Factoring Multivariate Polynomials over Algebraic Number F~elds. Math. Comp, 30(1976) pp. 324-336.
• Wang et al., 1982: Paul S. Wang , M. J. T. Guy , J. H. Davenport, P-adic reconstruction of rational numbers, ACM SIGSAM Bulletin, v.16 n.2, p.2-3, May 1982 [doi>10.1145/1089292.1089293]
• Weinberger & Rothschild, 1976: P. J. Weinberger , L. P. Rothschild, Factoring Polynomials Over Algebraic Number Fields, ACM Transactions on Mathematical Software (TOMS), v.2 n.4, p.335-350, Dec. 1976 [doi>10.1145/355705.355709]

INDEX TERMS

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

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

  G. Mathematics of Computing

  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.1 Expressions and Their Representation
          Subjects: Simplification of expressions
      I.1.3 Languages and Systems

          Nouns: REDUCE

General Terms:
Design, Measurement, Performance