PARALLEL O(LOG-N) ALGORITHMS FOR COMPUTATION OF MANIPULATOR FORWARD DYNAMICS

In this paper, parallel O(log N) algorithms for computation of manipulator forward dynamics are developed, These parallel algorithms are based on a new O(N) solution to the problem, The underlying feature of this O(N) method is a different strategy for decomposition of interbody force which results in a new factorization of mass matrix (M). Specifically, a factorization of inverse of the mass matrix in the form of Schur Complement is derived as M(-1) = C - B-t A(-1) B wherein A,B, and C are block tridiagonal matrices. The new O(N) algorithm is then derived as a recursive implementation of this factorization of M(-1). It is shown that the resulting algorithm is strictly parallel, that is, it is less efficient than other methods for serial computation of the problem, However, it is the first known algorithm that can be parallelized to derive a both time- and processor-optimal parallel algorithm for the problem, i.e., a parallel O(log N) algorithm with O(N) processors, Strategies for multilevel exploitation of parallelism in the computation are also discussed, resulting in more efficient parallel O(log N) algorithms, The parallel algorithms developed in this paper, in addition to their theoretical significance, are also important from a practical implementation standpoint due to their simple architectural requirements.