QuantLib › quantlib-users

Re: [Quantlib-dev] Bermudan LLM

Classic

List

Threaded

7 messages Options

Kakhkhor Abdijalilov

Re: [Quantlib-dev] Bermudan LLM

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-users mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/quantlib-users

Ferdinando M. Ametrano-3

Re: [Quantlib-dev] Bermudan LLM

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-users mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/quantlib-users

Dirk Eddelbuettel

Re: [Quantlib-dev] Bermudan LLM

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-users mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/quantlib-users

Daniel Cegiełka

Re: [Quantlib-dev] Bermudan LLM

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/

| 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

Dirk Eddelbuettel

Re: [Quantlib-dev] Bermudan LLM

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-users mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/quantlib-users

Kakhkhor Abdijalilov

Re: [Quantlib-dev] Bermudan LLM

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-users mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/quantlib-users

Daniel Cegiełka

Re: [Quantlib-dev] Bermudan LLM

2011/8/25 Kakhkhor Abdijalilov <[hidden email]>

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.

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

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