Simulating rigid bodies in contact is important for a wide range of applications, ranging from mechanical simulation to graphical animation to haptics. Although well studied, this problem can still be difficult to solve numerically. The only guaranteed solution method is a pivoting technique known as Lemke's algorithm which has an expected complexity of O(n^3) in the number of contacts.
I have developed some techniques to reduce the complexity of Lemke's algorithm from O(n^3) to O(n m + m^3) (where m is the number of contacting bodies). In particular, this implies an O(n) complexity for a fixed number of bodies, which is particularly useful for applications involving extended contact, where the number of contacts can be quite large even if the number of bodies is small. Papers describing this work are avaiable here: