Parallel O(log N) algorithms for computation of manipulator forward dynamics

Abstract

These parallel algorithms described 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/sup -1/=C-D/sup t/A/sup -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/sup -1/. It is shown that the resulting algorithm is strictly parallel. 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.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">&gt;</ETX>