Parallel arithmetic computations: A survey.(English)Zbl 0616.68037

Mathematical foundations of computer science, Proc. 12th Symp., Bratislava/Czech. 1986, Lect. Notes Comput. Sci. 233, 93-112 (1986).
[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.

MSC:

 68W30 Symbolic computation and algebraic computation 68Q25 Analysis of algorithms and problem complexity 68N25 Theory of operating systems 68-02 Research exposition (monographs, survey articles) pertaining to computer science

Zbl 0596.00021