Sat Jul 3 12:03:21 CEST 2010

Linear versus Tree updates

Many DSP algorithms use updates (memoization) to reduce complexity.
Often this is in the form of linear updates.  How many of the
traditional update algorithms can be updated in a more tree-like way,
allowing better parallel decomposition?

I.e, Kalman and FFT are essentially linear update algorithms:
successive steps depend on previous ones, while the inner product is
not (accumulation can be subdivided in arbitrary ways).