Bermudan LLM
Locked
 
|
Dear All,
I implemented a parallel version of Longstaff-Swartz algorithm. The code can be found here http://code.google.com/p/qlp/. Currently the algorithm was applied to equity options only. However almost everything is templatized and should be applicable to LMM with minimal changes . Compared to QuatLib's Longstaff-Swartz engine the parallel implementation runs about 50 time faster with 4 threads. Since single factor Monte-Carlo isn't very interesting, my actual goal is to implement Bermudan LLM and integrate it into QuantLib. There is one issues though. We need an efficient SVD algorithms. The SVD in the current version of QuantLib is OK for small matrices but I suspect it might be terribly slow for larger matrices. A good replacement would be ATLAS. It uses BSD-style license and can be more than 10 times faster than un-optimized implementation. But what the developers say about introducing additional dependencies? ATLAS is available on almost all Linux distributions, but Windows version can be problematic. Regards, Kakhkhor Abdijalilov. ------------------------------------------------------------------------------ Get a FREE DOWNLOAD! and learn more about uberSVN rich system, user administration capabilities and model configuration. Take the hassle out of deploying and managing Subversion and the tools developers use with it. http://p.sf.net/sfu/wandisco-d2d-2 _______________________________________________ QuantLib-dev mailing list [hidden email] https://lists.sourceforge.net/lists/listinfo/quantlib-dev |
|
|
On Sat, Aug 20, 2011 at 6:40 AM, Kakhkhor Abdijalilov
<[hidden email]> wrote: > my actual goal > is to implement Bermudan LLM and integrate it into QuantLib. do you plan a new implementation? why don't you reuse Mark Joshi's one > There is > one issues though. > We need an efficient SVD algorithms. The SVD in the current version of > QuantLib is OK for small matrices but I suspect it might be terribly > slow for larger matrices. I don't think Mark's code do use SVD and anyway I would be surprised if matrix decomposition is a bottleneck: a proper implementation would decompose the matrices once and then it's done. Hardly significant compared to the simulations that will use the decomposed matrices ciao -- Nando ------------------------------------------------------------------------------ uberSVN's rich system and user administration capabilities and model configuration take the hassle out of deploying and managing Subversion and the tools developers use with it. Learn more about uberSVN and get a free download at: http://p.sf.net/sfu/wandisco-dev2dev _______________________________________________ QuantLib-dev mailing list [hidden email] https://lists.sourceforge.net/lists/listinfo/quantlib-dev |
|
|
Longstaff-Schwartz method for Bermudan LLM requires OLS for every
early exercise opportunity, not just once. I checked "Numerical recipes", Demel's and Golub's books and all recommend not to use normal equations to solve OLS. Equity version of Longstaff-Schwartz in QuantLib uses SVD too. The cost of SVD scales as SAMPLES*FACTORS^3, but the cost of path generation scales as SAMPLES*FACTORS^2. SVD doesn't scale well as more CPU cores are used, but path generation should scale almost perfectly. Regards, Kakhkhor Abdijalilov. ------------------------------------------------------------------------------ EMC VNX: the world's simplest storage, starting under $10K The only unified storage solution that offers unified management Up to 160% more powerful than alternatives and 25% more efficient. Guaranteed. http://p.sf.net/sfu/emc-vnx-dev2dev _______________________________________________ QuantLib-dev mailing list [hidden email] https://lists.sourceforge.net/lists/listinfo/quantlib-dev |
|
|
Hi Kakhkhor
I apologize, I completely misinterpreted your question, my fault. As you wrote ATLAS would be problematic because in Windows it is available only if using cygwin, as far as I know. Besides it is plain C, isn't it? What about using uBLAS, the C++ boost implementation? As you understand moving to uBLAS would be a major change anyway and to do it in a backward compatible way (i.e. not dropping support for QuantLib::Matrix, QuantLib::Array, etc.) would be even more challenging, so Luigi opinion on this will rule. Unfortunately as he gets older he's more and more conservative ;-) I for one would support a transition to uBLAS and removing all the QuantLib code that could be replaced by boost (e.g. math and stat functions), maybe on a QuantLib 2.x branch which would be not backward compatible with the 1.x branch ciao -- Nando On Wed, Aug 24, 2011 at 12:37 AM, Kakhkhor Abdijalilov <[hidden email]> wrote: > Longstaff-Schwartz method for Bermudan LLM requires OLS for every > early exercise opportunity, not just once. > I checked "Numerical recipes", Demel's and Golub's books and all > recommend not to use normal equations to solve OLS. Equity version of > Longstaff-Schwartz in QuantLib uses SVD too. > > The cost of SVD scales as SAMPLES*FACTORS^3, but the cost of path > generation scales as SAMPLES*FACTORS^2. SVD doesn't scale well as more > CPU cores are used, but path generation should scale almost perfectly. > > Regards, > Kakhkhor Abdijalilov. > > ------------------------------------------------------------------------------ > EMC VNX: the world's simplest storage, starting under $10K > The only unified storage solution that offers unified management > Up to 160% more powerful than alternatives and 25% more efficient. > Guaranteed. http://p.sf.net/sfu/emc-vnx-dev2dev > _______________________________________________ > QuantLib-dev mailing list > [hidden email] > https://lists.sourceforge.net/lists/listinfo/quantlib-dev > ------------------------------------------------------------------------------ EMC VNX: the world's simplest storage, starting under $10K The only unified storage solution that offers unified management Up to 160% more powerful than alternatives and 25% more efficient. Guaranteed. http://p.sf.net/sfu/emc-vnx-dev2dev _______________________________________________ QuantLib-dev mailing list [hidden email] https://lists.sourceforge.net/lists/listinfo/quantlib-dev |
|
|
On 24 August 2011 at 16:17, Ferdinando Ametrano wrote: | Hi Kakhkhor | | I apologize, I completely misinterpreted your question, my fault. | | As you wrote ATLAS would be problematic because in Windows it is | available only if using cygwin, as far as I know. Besides it is plain | C, isn't it? Atlas is one of several accelerated implementation of the BLAS. It can certainly be compiled with different Windows toolchains; there is eg a binary you can download for R which was built with MinGW (ie very much not Cygwin) as R on Windows requires the MinGW toolchain. Commercial software (Matlab comes to mind) often bundles its own accelerated BLAS; Atlas happens to have the most liberal license (but Goto is now 'Open' too as the original author moved on). | What about using uBLAS, the C++ boost implementation? AFAICT it is a pain to use, and the numerics wrapper for actual linear algrebra was once again being rewritten when I last checked. It also falls back to using a BLAS implementations. FWIW I never managed to even cook up a simple linear regression 'from first principles' (eg using a SVD) with uBlas. An alternative could be provided by Eigen (http://eigen.tuxfamily.org) which is very clever, very fast, very templated C++ --- and does not use BLAS! But it would add another build dependency which is a clear downside. Another somewhat lighter alternative is Armadillo (http://arma.sf.net). Also templated, can use BLAS and a little simpler than Eigen. I quite like it -- and have written an package 'RcppArmadillo' that makes it a snap to use this from R, leveraging our Rcpp package also used to tie [parts of] QuantLib to R via RQuantLib. [ From all that, I have a number of competing 'FastLm' implementations of linear model fits (ie. ordinary least squares) using Armadillo, Eigen and GSL. Armadillo does fine, Eigen does better and GSL is slowest. My blog had a few posts on that. ] | As you understand moving to uBLAS would be a major change anyway and | to do it in a backward compatible way (i.e. not dropping support for | QuantLib::Matrix, QuantLib::Array, etc.) would be even more | challenging, so Luigi opinion on this will rule. | Unfortunately as he gets older he's more and more conservative ;-) | | I for one would support a transition to uBLAS and removing all the | QuantLib code that could be replaced by boost (e.g. math and stat | functions), maybe on a QuantLib 2.x branch which would be not backward | compatible with the 1.x branch That is probably a good design decision in the medium term but you may want to really check viability of some of the required operations first. Hth, Dirk | ciao -- Nando | | On Wed, Aug 24, 2011 at 12:37 AM, Kakhkhor Abdijalilov | <[hidden email]> wrote: | > Longstaff-Schwartz method for Bermudan LLM requires OLS for every | > early exercise opportunity, not just once. | > I checked "Numerical recipes", Demel's and Golub's books and all | > recommend not to use normal equations to solve OLS. Equity version of | > Longstaff-Schwartz in QuantLib uses SVD too. | > | > The cost of SVD scales as SAMPLES*FACTORS^3, but the cost of path | > generation scales as SAMPLES*FACTORS^2. SVD doesn't scale well as more | > CPU cores are used, but path generation should scale almost perfectly. | > | > Regards, | > Kakhkhor Abdijalilov. | > | > ------------------------------------------------------------------------------ | > EMC VNX: the world's simplest storage, starting under $10K | > The only unified storage solution that offers unified management | > Up to 160% more powerful than alternatives and 25% more efficient. | > Guaranteed. http://p.sf.net/sfu/emc-vnx-dev2dev | > _______________________________________________ | > QuantLib-dev mailing list | > [hidden email] | > https://lists.sourceforge.net/lists/listinfo/quantlib-dev | > | | ------------------------------------------------------------------------------ | EMC VNX: the world's simplest storage, starting under $10K | The only unified storage solution that offers unified management | Up to 160% more powerful than alternatives and 25% more efficient. | Guaranteed. http://p.sf.net/sfu/emc-vnx-dev2dev | _______________________________________________ | QuantLib-dev mailing list | [hidden email] | https://lists.sourceforge.net/lists/listinfo/quantlib-dev -- Two new Rcpp master classes for R and C++ integration scheduled for New York (Sep 24) and San Francisco (Oct 8), more details are at http://dirk.eddelbuettel.com/blog/2011/08/04#rcpp_classes_2011-09_and_2011-10 http://www.revolutionanalytics.com/products/training/public/rcpp-master-class.php ------------------------------------------------------------------------------ EMC VNX: the world's simplest storage, starting under $10K The only unified storage solution that offers unified management Up to 160% more powerful than alternatives and 25% more efficient. Guaranteed. http://p.sf.net/sfu/emc-vnx-dev2dev _______________________________________________ QuantLib-dev mailing list [hidden email] https://lists.sourceforge.net/lists/listinfo/quantlib-dev |
|
|
2011/8/24 Dirk Eddelbuettel <[hidden email]>
Goto is probably one of the best implementations of BALS. Unfortunately, it is no longer being actively developed by Kazushige Goto. I give the address where you can find fresh updates.
I also thought about Eigen... but like you wrote, it means another dependency. Best regards,
daniel
------------------------------------------------------------------------------ EMC VNX: the world's simplest storage, starting under $10K The only unified storage solution that offers unified management Up to 160% more powerful than alternatives and 25% more efficient. Guaranteed. http://p.sf.net/sfu/emc-vnx-dev2dev _______________________________________________ QuantLib-dev mailing list [hidden email] https://lists.sourceforge.net/lists/listinfo/quantlib-dev |
|
|
On 24 August 2011 at 17:29, Daniel Cegiełka wrote: | | 2011/8/24 Dirk Eddelbuettel <[hidden email]> | | | On 24 August 2011 at 16:17, Ferdinando Ametrano wrote: | | Hi Kakhkhor | | | | I apologize, I completely misinterpreted your question, my fault. | | | | As you wrote ATLAS would be problematic because in Windows it is | | available only if using cygwin, as far as I know. Besides it is plain | | C, isn't it? | | Atlas is one of several accelerated implementation of the BLAS. It can | certainly be compiled with different Windows toolchains; there is eg a | binary | you can download for R which was built with MinGW (ie very much not Cygwin) | as R on Windows requires the MinGW toolchain. | | Commercial software (Matlab comes to mind) often bundles its own | accelerated | BLAS; Atlas happens to have the most liberal license (but Goto is now | 'Open' | too as the original author moved on). | | | Goto is probably one of the best implementations of BALS. Unfortunately, it is | no longer being actively developed by Kazushige Goto. I give the address where | you can find fresh updates. | | http://prs.ism.ac.jp/~nakama/SurviveGotoBLAS2/ That are 'just' maintenance updates by Ei-Ji Nakama. The new and more ambitious project I was referring to is on github: https://github.com/xianyi/OpenBLAS but I have not tried it. Dirk | | | | What about using uBLAS, the C++ boost implementation? | | AFAICT it is a pain to use, and the numerics wrapper for actual linear | algrebra was once again being rewritten when I last checked. It also falls | back to using a BLAS implementations. FWIW I never managed to even cook | up a | simple linear regression 'from first principles' (eg using a SVD) with | uBlas. | | An alternative could be provided by Eigen (http://eigen.tuxfamily.org) | which | is very clever, very fast, very templated C++ --- and does not use BLAS! | But | it would add another build dependency which is a clear downside. | | | I also thought about Eigen... but like you wrote, it means | another dependency. | | Best regards, | daniel | | | | | | Another somewhat lighter alternative is Armadillo (http://arma.sf.net). | Also | templated, can use BLAS and a little simpler than Eigen. I quite like it -- | and have written an package 'RcppArmadillo' that makes it a snap to use | this | from R, leveraging our Rcpp package also used to tie [parts of] QuantLib to | R | via RQuantLib. | | [ From all that, I have a number of competing 'FastLm' implementations of | linear model fits (ie. ordinary least squares) using Armadillo, Eigen and | GSL. Armadillo does fine, Eigen does better and GSL is slowest. My blog | had | a few posts on that. ] | | | As you understand moving to uBLAS would be a major change anyway and | | to do it in a backward compatible way (i.e. not dropping support for | | QuantLib::Matrix, QuantLib::Array, etc.) would be even more | | challenging, so Luigi opinion on this will rule. | | Unfortunately as he gets older he's more and more conservative ;-) | | | | I for one would support a transition to uBLAS and removing all the | | QuantLib code that could be replaced by boost (e.g. math and stat | | functions), maybe on a QuantLib 2.x branch which would be not backward | | compatible with the 1.x branch | | That is probably a good design decision in the medium term but you may want | to really check viability of some of the required operations first. | | Hth, Dirk | | | ciao -- Nando | | | | On Wed, Aug 24, 2011 at 12:37 AM, Kakhkhor Abdijalilov | | <[hidden email]> wrote: | | > Longstaff-Schwartz method for Bermudan LLM requires OLS for every | | > early exercise opportunity, not just once. | | > I checked "Numerical recipes", Demel's and Golub's books and all | | > recommend not to use normal equations to solve OLS. Equity version of | | > Longstaff-Schwartz in QuantLib uses SVD too. | | > | | > The cost of SVD scales as SAMPLES*FACTORS^3, but the cost of path | | > generation scales as SAMPLES*FACTORS^2. SVD doesn't scale well as more | | > CPU cores are used, but path generation should scale almost perfectly. | | > | | > Regards, | | > Kakhkhor Abdijalilov. | | > | | > | ------------------------------------------------------------------------------ | | > EMC VNX: the world's simplest storage, starting under $10K | | > The only unified storage solution that offers unified management | | > Up to 160% more powerful than alternatives and 25% more efficient. | | > Guaranteed. http://p.sf.net/sfu/emc-vnx-dev2dev | | > _______________________________________________ | | > QuantLib-dev mailing list | | > [hidden email] | | > https://lists.sourceforge.net/lists/listinfo/quantlib-dev | | > | | | | | ------------------------------------------------------------------------------ | | EMC VNX: the world's simplest storage, starting under $10K | | The only unified storage solution that offers unified management | | Up to 160% more powerful than alternatives and 25% more efficient. | | Guaranteed. http://p.sf.net/sfu/emc-vnx-dev2dev | | _______________________________________________ | | QuantLib-dev mailing list | | [hidden email] | | https://lists.sourceforge.net/lists/listinfo/quantlib-dev | | -- | Two new Rcpp master classes for R and C++ integration scheduled for | New York (Sep 24) and San Francisco (Oct 8), more details are at | http://dirk.eddelbuettel.com/blog/2011/08/04# | rcpp_classes_2011-09_and_2011-10 | http://www.revolutionanalytics.com/products/training/public/ | rcpp-master-class.php | | ------------------------------------------------------------------------------ | EMC VNX: the world's simplest storage, starting under $10K | The only unified storage solution that offers unified management | Up to 160% more powerful than alternatives and 25% more efficient. | Guaranteed. http://p.sf.net/sfu/emc-vnx-dev2dev | _______________________________________________ | QuantLib-dev mailing list | [hidden email] | https://lists.sourceforge.net/lists/listinfo/quantlib-dev | | -- Two new Rcpp master classes for R and C++ integration scheduled for New York (Sep 24) and San Francisco (Oct 8), more details are at http://dirk.eddelbuettel.com/blog/2011/08/04#rcpp_classes_2011-09_and_2011-10 http://www.revolutionanalytics.com/products/training/public/rcpp-master-class.php ------------------------------------------------------------------------------ EMC VNX: the world's simplest storage, starting under $10K The only unified storage solution that offers unified management Up to 160% more powerful than alternatives and 25% more efficient. Guaranteed. http://p.sf.net/sfu/emc-vnx-dev2dev _______________________________________________ QuantLib-dev mailing list [hidden email] https://lists.sourceforge.net/lists/listinfo/quantlib-dev |
|
|
Longstaff-Schwartz method doesn't need and shouldn't use full SVD.
LAPACK has thin version of SVD, but Eigen doesn't. One possible option is to link to standard CBLAS/LAPACK interface. MKL 10.3 introduced C-API to LAPACK. The same interface can be built for ATLAS, ACML or any other implementation that provides CBLAS/LAPACK interface. A high level abstraction layer would separate users from low level implementation. This way users would be able to link to their favorite CBLAS/LAPACK implementation. Regards, Kakhkhor Abdijalilov. ------------------------------------------------------------------------------ EMC VNX: the world's simplest storage, starting under $10K The only unified storage solution that offers unified management Up to 160% more powerful than alternatives and 25% more efficient. Guaranteed. http://p.sf.net/sfu/emc-vnx-dev2dev _______________________________________________ QuantLib-dev mailing list [hidden email] https://lists.sourceforge.net/lists/listinfo/quantlib-dev |
|
|
2011/8/25 Kakhkhor Abdijalilov <[hidden email]> Longstaff-Schwartz method doesn't need and shouldn't use full SVD. It has a lot of sense. User will be able to use well optimized CBLAS/LAPACK (like MKL, Goto or GPU based), and by the way QuantLib binary will be much smaller.
regards, daniel
------------------------------------------------------------------------------ EMC VNX: the world's simplest storage, starting under $10K The only unified storage solution that offers unified management Up to 160% more powerful than alternatives and 25% more efficient. Guaranteed. http://p.sf.net/sfu/emc-vnx-dev2dev _______________________________________________ QuantLib-dev mailing list [hidden email] https://lists.sourceforge.net/lists/listinfo/quantlib-dev |
|
|
In reply to this post by Kakhkhor Abdijalilov
Dear Aman,
I appreciate your offer to help.If you wish to contribute please, join the Google group I created for the project. Recently I took a closer look at QuantLib's matrix subroutines and noticed the following: (*) Internal implementation can be replaced with calls to BLAS subroutines without affecting the interface. (*) SVD class is much slower (up 50 times with large matrices) than SVD from LAPACK when the later is linked to optimized BLAS such as ATLAS. (*) For the best performance SSE/SSE2 vector instructions can be used to speedup path generations. These are available on all x86 architectures. Fallback to scalar form is the matter of simple macro switch. Users wouldn't have to deal with SSE/SSE2 directly if they use supplied payoffs. (*) Overall speedup can be somewhere between 50 to 100 times when 12 or more CPU cores are used. Regards, Kakhkhor Abdijalilov. ------------------------------------------------------------------------------ BlackBerry® DevCon Americas, Oct. 18-20, San Francisco, CA Learn about the latest advances in developing for the BlackBerry® mobile platform with sessions, labs & more. See new tools and technologies. Register for BlackBerry® DevCon today! http://p.sf.net/sfu/rim-devcon-copy1 _______________________________________________ QuantLib-dev mailing list [hidden email] https://lists.sourceforge.net/lists/listinfo/quantlib-dev |
«
Return to quantlib-dev
|
1 view|%1 views
| Free forum by Nabble | Edit this page |