You're probably aware the thrust library which you're already including also provides GPU algorithms for prefix-sum, reduce, sort etc<br>eg. <a href="http://thrust.googlecode.com/svn/tags/1.2.0/doc/html/modules.html">http://thrust.googlecode.com/svn/tags/1.2.0/doc/html/modules.html</a><br>
<br><div class="gmail_quote">On Mon, Aug 16, 2010 at 10:06 PM, Matthew Knepley <span dir="ltr"><<a href="mailto:knepley@gmail.com">knepley@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
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/%7Eblelloch/papers/Ble93.pdf" target="_blank">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/" target="_blank">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>
</blockquote></div><br><br clear="all"><br>-- <br>Chris Cooper<br>Dr. D Studios<br>