Efficient parallel solutions of linear algebraic circuits

Abstract

We define a new restricted type of algebraic circuit (AC) problems, called linear algebraic circuits (LACs), and consider the problem of obtaining efficient solutions for their parallel evaluation. The term "efficiency" indicates that for some fixed number of processors, the algorithm can compete with the sequential evaluation of ACs. While parallel evaluation of general ACs is P-complete, there are restricted types of ACs such as prefix-sums circuits (ACs in the form of chains) and arithmetic expressions (ACs in the form of trees) for which efficient parallel evaluation algorithms exist. In this work, we consider a restricted type, other than chains or trees, of ACs where at least one input of each multiplication must be a constant. We show that LACs can be evaluated in n/18p1/3 log2 p steps, where n is the size of the circuit and p < n is the number of processors. Thus, for suitable values of p, this algorithm can compete with the sequential evaluation of LACs and achieve speedups of about p1/3. It follows that LACs can be represented by a product of matrices. Thus, computing this product in parallel yields a possible evaluation algorithm for LACs. Parallel computation of a product of matrices is also the main "engine" used in existing parallel evaluation algorithms for ACs. We show, via a lower bound, that such a naive solution based on matrix multiplication alone, is inherently inefficient regardless of the order in which the product of the matrices is computed and hence a more complex solution must be devised. Finally, useful applications for parallelizing sequential code are given. © 2003 Elsevier Inc. All rights reserved.