[For the entire collection see Zbl 0596.00021.]
The paper surveys the theory of parallel computations for algebraic problems. The natural model of computation is the arithmetic circuit, using inputs \(x_ 1,...,x_ n\) and constants from the ground field for free, and the (exact) arithmetic operations \(+,-,*,/\) at unit cost.
Some basic problems of linear algebra, such as computing the determinant, can be solved ”fast in parallel”, namely in depth (= parallel time) \(O(\log^ 2n)\) and size (= number of processors) \(n^{O(1)}\). The calculation of large powers, with an n-bit exponent, requires depth \(\Omega(n)\) over infinite or sufficiently large finite fields. However, over large finite fields of small characteristic this problem can be solved by arithmetic circuits over the prime field of depth \(O(\log^ 2n):\) an exponential gap between the natural model and another - also reasonable - model.
Many problems of polynomial arithmetic, e.g., division with remainder, can be solved in optimal depth \(O(\log n)\). There is a general method that compiles arbitrary polynomial-size (sequential) computations for rational functions of polynomial degree into arithmetic circuits of depth \(0(\log^ 2n).\)
For tasks from linear algebra with a ”combinatorial” aspect, such as the rank of matrices or (possibly singular) systems of linear equations, one has to augment the model by allowing zero-tests. Then most elementary problems of linear algebra fall into two classes of ”equivalent” problems. The trivial lower bound ”depth \(\geq \log_ 2(\)degree of computed function)” for arithmetic circuits only survives as ”depth \(\geq \log\log(\)degree)” in the augmented model.