I'm not sure about whether this is a bottlenecking step in applications, but even so, is it interesting to ask which parts of this are gpu-friendly? That is, is there a (sparse) matrix representation which is used in gpu's? And does it make sense to carry through the dag/tree construction as a sort of "prep" step (on cpu or gpu)?
The initial plain/dense algorithm looks pretty straightforward, but not sure about the tree construction.
One of the easiest ways to make this kind of problem GPU friendly is to use random matrix projections to cast the problem as a much smaller dense problem.
The issue with doing this is that the technique is only practical for certain problems where there are a relatively small (hundreds to thousands) number of dominant eigenvalues.
2 comments
[ 3.1 ms ] story [ 18.0 ms ] threadThe initial plain/dense algorithm looks pretty straightforward, but not sure about the tree construction.
The issue with doing this is that the technique is only practical for certain problems where there are a relatively small (hundreds to thousands) number of dominant eigenvalues.