I am no longer as pessimistic as I once was. To start, this is a good report on prefix-sum in parallel:<div><br></div><div>  <a href="http://www.cs.cmu.edu/~blelloch/papers/Ble93.pdf">http://www.cs.cmu.edu/~blelloch/papers/Ble93.pdf</a></div>
<div><br></div><div>It can solve first-order recurrences optimally. Higher order recurrences can be reduced to first-order,</div><div>however it is not work optimal (too big by a factor of the order, m), which seems alright to me. Thus</div>
<div>we should be able to solve bandwidth m matrices efficiently. Here is a nice implementation of prefix-sum</div><div><br></div><div>  <a href="http://code.google.com/p/cudpp/">http://code.google.com/p/cudpp/</a></div><div>
<br></div><div>This all leads me to believe that for a bounded number of nonzeros per row, we can get an efficient</div><div>algorithm for triangular solve.</div><div><br></div><div>  Matt</div><div><br>-- <br>What most experimenters take for granted before they begin their experiments is infinitely more interesting than any results to which their experiments lead.<br>
-- Norbert Wiener<br>
</div>