Longstaff & Schwartz

The Longstaff & Schwartz algorithm involves two subroutines:

Generating random paths

• Sobol sequence

• CUDA SDK contains and example derived from code by Mike Giles
• http://www.nag.co.uk/numeric/GPUs/index.asp (found through a link on Mike Giles website) Also relevant for Cholesky and LU decomposition below.

• Mersenne-Twister

Solving linear system of equations

• LU decomposition
• Cholesky decomposition
• QR decomposition
• (D)LSBRR routine of the IMSL Fortran library is what the original article suggests. The algorithm used documented on page 126-127 in the book Matrix Computations by Golub and Van Loan. http://www.roguewave.com/Portals/0/products/imsl-numerical-libraries/fortran-library/docs/6.0/math/default.htm?turl=lsbrr.htm
• GPU implementations for LU, Cholesky and QR decompositions: https://devtalk.nvidia.com/default/topic/405197/cuda-programming-and-performance/lu-qr-and-cholesky-factorizations-using-gpu/
• http://gamma.cs.unc.edu/LU-GPU/
• http://www.noctua-blog.com/index.php/2011/04/21/lu-matrix-decomposition-in-parallel-with-cuda/

Root finding (from Ken)

• Laguerre's method. See for instance Python method at http://w3mentor.com/learn/python/scientific-computation/python-example-of-using-laguerres-method-to-compute-all-the-roots-of-equation/
• Jenkins-Traub algorithm (used in R, what Rolf's R code uses because it uses polyroot). Jenkins and Traub (1972) TOMS Algorithm 419. Comm. ACM, 15, 97–99.
• Statistics.Math.RootFinding from the Haskell library statistics. Implements Ridder's method: Ridders, C.F.J. (1979) A new algorithm for computing a single root of a real continuous function. IEEE Transactions on Circuits and Systems 26:979–980.