Can someone post Recursive Doubling as suggested by Y.zhang in Fast Tridiagonal Solver on the GPU .

[GoogleCodeExporter]

we need to apply this to real-time shallow water simulation and we would like 
it to compare it with multithreaded implementation in C++ .

Original issue reported on code.google.com by suyesh.t...@gmail.com on 15 Aug 2010 at 5:18

[GoogleCodeExporter]

There is a branch of CUDPP for this development.  You can access it here:
http://code.google.com/p/cudpp/source/browse/#svn/branches/tridiagonal

Original comment by harr...@gmail.com on 3 Nov 2010 at 11:50

• Changed state: Done
• Added labels: Type-Other
• Removed labels: Type-Defect

[GoogleCodeExporter]

Yes.We have CR and PCR but i'm looking for RD ( recursive doubling ) 
implementation. I don't think it is present in 
http://code.google.com/p/cudpp/source/browse/#svn/branches/tridiagonal [ it 
contains only CR,PCR and Hybrid CRPCR ]

Thanks in advance

Original comment by suyesh.t...@gmail.com on 7 Jan 2011 at 4:59

[GoogleCodeExporter]

I know this is old... but I'd like to warn anyone else looking to implement 
recursive doubling:

Recursive doubling is inherently numerically unstable. The algorithm works with 
arbitrary precision values. Examine the algorithm and you should notice that 
elements within C_i get progressively large, ultimately resulting in numerical 
instability. (In my implementation, numerical instability occurs when n > 128.)

It'd be nice to know if there is a solution to this problem. I couldn't find it 
after spending quite some time implementing recursive doubling.

Original comment by djh.s...@gmail.com on 11 Sep 2012 at 5:52

[GoogleCodeExporter]

In our 2010 PPoPP paper ("Fast Tridiagonal Solvers on the GPU"), we noted the 
same; both plain recursive doubling and RD+cyclic reduction overflowed in our 
tests. I agree: this is not suitable for a GPU implementation.

Original comment by jow...@gmail.com on 12 Sep 2012 at 4:08