Arithmetic with real algebraic numbers is in NC

ABSTRACT

We describe NC algorithms for doing exact arithmetic with real algebraic numbers in the sign-coded representation introduced by Coste and Roy [CoR 1988]. We present polynomial sized circuits of depth &Ogr;(log3 N) for the monadic operations -&agr;, 1/&agr;, as well as &agr; + r, &agr; · r, and sgn(&agr; - r), where r is rational and &agr; is real algebraic. We also present polynomial sized circuits of depth &Ogr;(log7 N) for the dyadic operations &agr;+&bgr;, &agr;·&bgr;, and sgn(&agr; - &bgr;), where &agr; and &bgr; are both real algebraic. Our algorithms employ a strengthened form of the NC polynomial-consistency algorithm of Ben-Or, Kozen, and Reif [BKR 1986].

REFERENCES

• Akr 1980: A. Akritas, Elements of computer algebra with applications, John Wiley & Sons, Inc., New York, NY, 1989
• Bar 1968: Bareiss, E. H.: "Sylvester's Identity and Multistep Integer-preserving Gaussian Elimination'', Math. Comp. 22 (1968), 565-578.
• BKR 1986: Michael Ben-Or , Dexter Kozen , John Reif, The complexity of elementary algebra and geometry, Journal of Computer and System Sciences, v.32 n.2, p.251-264, April 1986 [doi>10.1016/0022-0000(86)90029-2]
• Ber 1984: Stuart J. Berkowitz, On computing the determinant in small parallel time using a small number of processors, Information Processing Letters, v.18 n.3, p.147-150, March 1984 [doi>10.1016/0020-0190(84)90018-8]
• BCR 1987: Bochnak, J., M. Coste, M-F. Roy: "G~om~trie algebrique r~elle", A series of Modern Surveys in Mathematics, Vo}. 12 (1987), Springer Verlag, Berlin.
• Chi 1985: Alexander L. Chistov, Fast parallel calculation of the rank of matrices over a field of arbitrary characteristic, Fundamentals of Computation Theory, p.63-69, September 09-13, 1985
• CoR 1988: 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]
• Csa 1976: Csanky, L.: "Fast parallel matrix inversion algorithms", SIAM J. Comput. Vol. 5, No. 4, December 1976.
• CLR 1989: Cucker, Felipe, Herv~ Lanneau, M- F. Roy: "NC Computations with Real Algebraic Numbers", SIAM J. Comp. (submitted).
• Gat 1984: Joachim von zur Gathen, Parallel algorithms for algebraic problems, SIAM Journal on Computing, v.13 n.4, p.802-824, Nov. 1984 [doi>10.1137/0213050]
• Loo 1982a: Loos, R.: "Computing in Algebraic Extensions", in "Computer Algebra, Symbolic and Algebraic Computation", edited by B. Buchberger, G. E. Collins, and R. Loos in cooperation with R. Albrecht, Springer Verlag, Wein, 1982.
• Mig 1982: Mignotte, M.: "Some Useful Bounds", in "Computer Algebra, Symbolic and Algebraic Computation", edited by B. Buchberger, G. E. Collins, and R. Loos in cooperation with R. Albrecht, Springer Verlag, Wein, 1982.
• Mul 1987: K. Mulmuley, A fast parallel algorithm to compute the rank of a matrix over an arbitrary field, Combinatorica, v.7 n.1, p.101-104, Jan. 1987 [doi>10.1007/BF02579205]
• Rei 1983: Reif, J.: "Logarithmic depth circuits for algebraic functions", in "Proc. 24th Ann. Symposium on Foundations of Comp. Sci.", Tucson (1983), 138-145.
• RS 1988: Marie-Françoise Roy , Aviva Szpirglas, Complexity of computation on real algebraic numbers, Journal of Symbolic Computation, v.10 n.1, p.39-51, July 1990 [doi>10.1016/S0747-7171(08)80035-1]
• Stu 1904: Sturm, C.' "Uber die AufiSsung der Numerischen Gleichungen (1835)", in the series "Ostwald's Klassiker der Exacten Wissenschaften", Nr. 143, Wilhelm Engelmann, Leipzig (1904).
• Tar 1951: Tarski, A.: "A Decision Method for Elementary Algebra and Geometry", University of California Press, Berkeley (1951).

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

  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION

General Terms:
Algorithms