PV-OSIMr: A Lowest Order Complexity Algorithm for Computing the Delassus Matrix

We present PV-OSIMr, an efficient algorithm for computing the Delassus matrix (also known as the inverse operational space inertia matrix) for a kinematic tree, with the lowest order computational complexity known in literature. PV-OSIMr is derived by optimizing the recently proposed PV-OSIM algorithm using the compositionality of the force and motion propagators. It has a computational complexity of $O(n+m^2)$ compared to $O(n+m^2d)$ of the PV-OSIM algorithm and $O(n+md+m^2)$ of the extended force propagator algorithm (EFPA), where $n$ is the number of joints, $m$ is the number of constraints and $d$ is the depth of the kinematic tree. Since the Delassus matrix is an $m×m$ sized matrix and its computation must consider all the n joints, PV-OSIMr's asymptotic computational complexity is optimal. We further benchmark our algorithm and find it to be often more efficient than the PV-OSIM and EFPA in practice.