In-direct Scheduler / 2nd Degree Scheduler

[GoogleCodeExporter]

Consider the Lasso Shooting algorithm:  we have a bipartite graph; left is the 
x's (to be optimized) and right is vector Ax, which are computed from x's. 
Update of each x is computed from values of Ax. 

Now, if we update x_j, we write a new value for each Ax_i which are connected 
to x_j.  But, now we need to update each x_k which is connected to each such 
Ax_i which was connected to x_j.

One can already do this scheduling in GraphLab, but it is very inefficient, as 
the dynamic scheduling becomes a n^2 problem. Instead, if after each K steps, 
scheduler would check which Ax_i were updated, and would then reschedule all 
such x_k which are connected to those Ax_i, this would be much more efficient. 
I would call this "In-direct Scheduler" or "2nd Degree Scheduler".

As for Lasso, we probably would not like to dynamic scheduling due to overhead. 
But maybe  there are other algorithms that would benefit from same strategy?

Original issue reported on code.google.com by akyrola...@gmail.com on 2 Nov 2010 at 5:05