Featherstone

gistfile1.txt

Given J*JT * x = b, solve for x in linear time and space.

J is m by n
x is m by 1
b is m by 1
m < n

J is a rectangular matrix that represents a tree with equal and opposite entries.

For example:

J = [1 -1  0  0]
    [0  1 -1  0]
    [0  1  0 -1]

This is a 4 node tree:

1 -- 2 -- 3
      \-- 4

Note that J is sparse and can be stored in O(m) memory.

The columns of J represent the nodes (bodies).
The rows of J represent the edges (joints).

J is the transpose of the Incidence matrix (http://en.wikipedia.org/wiki/Incidence_matrix)

"This is the essential linear algebra problem that Featherstone's algorithm solves in linear time and space" - erin from twitter