FdAmericanOption problem and Tracing

[Joseph Wang]

I've tried some numerical experiments, and I don't think that the
problem is easily fixable,
and that the focus should be to put in some checks to make sure that the
time steps are
such that the problem doesn't develop.

I think that the problem is an interaction between large time steps,
small space steps,
and boundary conditions.  If you have large time steps and small space
steps, the error
from the value of the point next to the boundary becomes large.  This
results in an
artificially large second derivative which then destroys the
simulation.  What I did to
convince myself this was the problem was to artifically set the problem
up so that it
is a pure diffusion problem and then run the simulation with different
differencing
methods.  In all cases, you see problems start to in the penultimate
point and then
spread to the middle.

Also something that I've seen that I think is interesting syntax is

#define TRACE(x)  if (turn_on_trace(x)) trace_ostream

This lets you write things like

TRACE(2) << "Trace statement";

[Sinha, Amitesh-2]

I am a new user on this forum. I would like to understand this problem in
order to understand & contribute.
Could somebody please mail a summary of this problem please?

-----Original Message-----
From: [hidden email]
[mailto:[hidden email]]On Behalf Of Joseph
Wang
Sent: Thursday, January 06, 2005 10:50 AM
To: [hidden email]
Cc: Graham Miller; Luigi Ballabio
Subject: [Quantlib-users] FdAmericanOption problem and Tracing


I've tried some numerical experiments, and I don't think that the
problem is easily fixable,
and that the focus should be to put in some checks to make sure that the
time steps are
such that the problem doesn't develop.

I think that the problem is an interaction between large time steps,
small space steps,
and boundary conditions.  If you have large time steps and small space
steps, the error
from the value of the point next to the boundary becomes large.  This
results in an
artificially large second derivative which then destroys the
simulation.  What I did to
convince myself this was the problem was to artifically set the problem
up so that it
is a pure diffusion problem and then run the simulation with different
differencing
methods.  In all cases, you see problems start to in the penultimate
point and then
spread to the middle.

Also something that I've seen that I think is interesting syntax is

#define TRACE(x)  if (turn_on_trace(x)) trace_ostream

This lets you write things like

TRACE(2) << "Trace statement";



-------------------------------------------------------
The SF.Net email is sponsored by: Beat the post-holiday blues
Get a FREE limited edition SourceForge.net t-shirt from ThinkGeek.
It's fun and FREE -- well, almost....http://www.thinkgeek.com/sfshirt
_______________________________________________
Quantlib-users mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/quantlib-users

==============================================================================
This message is for the sole use of the intended recipient. If you received
this message in error please delete it and notify us. If this message was
misdirected, CSFB does not waive any confidentiality or privilege. CSFB
retains and monitors electronic communications sent through its network.
Instructions transmitted over this system are not binding on CSFB until they
are confirmed by us. Message transmission is not guaranteed to be secure.
==============================================================================

[Joseph Wang]

There are three different but related issues.....

1) Basically if you run FdAmericanOption with a fixed number of time
steps and increase the number of space steps, the PDE calculation starts
getting unstable.  Graham Miller posted some test code that nicely
illustrates the problem.  E-mail me if you can't find it in the list
archives at www.quantlib.org

2) There also seems to be some error if you have an even number of grid
steps.

3) Also there has been some discussion on adding a trace statement.

As far as 1) and 2) my current opinion is that the problem is a deep
issue and that the best way of dealing with it is to put in checks that
stop the simulation if the number of space steps are too large or if
there is an even number.  The big problem with 1) and 2) is that the
simulation behaves counter-inituitively.  More grids usually gives a
better result.

Some of the projects I can think of are:

1) write unit tests that compare the output of FdAmericanOption with
some known good results

2) see how bad the problem is.  I suspect that anything that calculates
option prices via PDE will run into this problem.

3) see if this sort of issue is in the literature.

4) once we have agreed to a format for putting in trace statements,
there is a lot of work to do adding trace statements to the code.  My
own experience has been that it is practically impossible to debug
highly numerical code without some tracing mechanism.  Also, my
experience has also been that keeping trace code in the production code
is usually a good thing.  (i.e. if you have to add some print debug
statements to track down a problem, it is really nice to have a
mechanism to keep those debug statements in the production code).

5) Also it would be nice to setup cppdoc

[Luigi Ballabio]

On 01/06/05 06:31:46, Joseph Wang wrote:

>
> 1) Basically if you run FdAmericanOption with a fixed number of time  
> steps and increase the number of space steps, the PDE calculation starts  
> getting unstable.
> 2) There also seems to be some error if you have an even number of grid  
> steps.
>
> As far as 1) and 2) my current opinion is that the problem is a deep  
> issue and that the best way of dealing with it is to put in checks that  
> stop the simulation if the number of space steps are too large or if  
> there is an even number.  The big problem with 1) and 2) is that the  
> simulation behaves counter-inituitively.  More grids usually gives a  
> better result.

Hmm. As to evenness, it is easy enough to write

   gridPoints += gridPoints % 2 + 1

so that the number is always odd. But as to space steps, how are we to  
decide whether we have too many?


> Some of the projects I can think of are:
>
> 1) write unit tests that compare the output of FdAmericanOption with some  
> known good results

This would be good, but it would only check that a given combination of  
parameters is safe. It could help us define some range of parameters to be  
rejected, but I doubt that it would make us confident that an algorithm  
works for arbitrary parameters (maturity, volatility, time/asset steps...)

> 2) see how bad the problem is.  I suspect that anything that calculates  
> option prices via PDE will run into this problem.

I'm running a few tests as I write this mail. As to dividends, the code  
currently in CVS runs Graham's test case safely up to 210 grid points and  
then diverges. As to plain american options, let me compile and run it...
I see. FdAmericanOption went all the way to 5000 grid points without losing  
a beat. It looks like it's something in the dividend option...

> 3) see if this sort of issue is in the literature.

Well, it just so happen that we have Daniel Duffy on the list.  Daniel, do  
you have any insight?

But all in all, I guess we should sit down and redesign the framework. The  
existing one is ancient and it should be retrofitted to the current library  
design anyway (engines and such.) It could be the right time to have a good  
look at it.

Later,
        Luigi

[Luigi Ballabio]

On 01/06/05 06:31:46, Joseph Wang wrote:

> Also there has been some discussion on adding a trace statement.
>
> once we have agreed to a format for putting in trace statements, there is  
> a lot of work to do adding trace statements to the code.  My own  
> experience has been that it is practically impossible to debug highly  
> numerical code without some tracing mechanism.  Also, my experience has  
> also been that keeping trace code in the production code is usually a  
> good thing.  (i.e. if you have to add some print debug statements to  
> track down a problem, it is really nice to have a mechanism to keep those  
> debug statements in the production code).

I agree that trace code should stay in. But surely you're not suggesting  
that adding such code should be done all at once? People might simply add  
it when they need it and leave it there afterwards.

As to the format:

> something that I've seen that I think is interesting syntax is
>
> #define TRACE(x)  if (turn_on_trace(x)) trace_ostream
>
> This lets you write things like
>
> TRACE(2) << "Trace statement";

Nice, but fragile: for instance,

if (condition)
    TRACE(2) << "statement";
else
    do_something();

might not do what one expects when tracing is on...

I'd go for something like

TRACE(tag, statement);

which does not suffer from such problems and can be #defined away by speed  
frea---I mean, performance-concerned users :)  Moreover, the macro could be  
written so that it allows

TRACE(tag, "statement1" << variable << "statement2" ...);

which is almost as nice as TRACE(tag) << whatever.

Finally, I intentionally wrote a generic "tag" variable, as I'm not sure  
whether a number or a string should be used. Thoughts?

Later,
        Luigi

[Luigi Ballabio]

On 01/06/05 06:31:46, Joseph Wang wrote:
>
> Also it would be nice to setup cppdoc

I admit that I'm not familiar with cppdoc, but what's wrong with Doxygen?

Later,
        Luigi

[Joseph Wang]

I've started up a quantlib wiki at ....

http://www.gnacademy.org/twiki/bin/view/Quantlib

The system is set up for open editing right now.

If someone can point wiki.quantlib.org at 206.196.68.254, I can
configure the server to bring up
the right pages.

[Joseph Wang]

Luigi Ballabio wrote:

>
> Finally, I intentionally wrote a generic "tag" variable, as I'm not
> sure  whether a number or a string should be used. Thoughts?

The way that java does it is to use integer constants.  This makes it
easier to compare and for example
turn on all debug statements above level N or below level M.  If you set
the integers to be constants,
then you don't lose anything regarding readability.

The odd thing is that I would have imagined that there is a standard
tracing module in C++ but
there doesn't seem to be one.

[Luigi Ballabio]

On 01/14/05 03:58:52, Joseph Wang wrote:
>> Finally, I intentionally wrote a generic "tag" variable, as I'm not sure  
>> whether a number or a string should be used. Thoughts?
>
> The way that java does it is to use integer constants.  This makes it  
> easier to compare and for example turn on all debug statements above  
> level N or below level M.  If you set the integers to be constants, then  
> you don't lose anything regarding readability.

Yes, but it implies a total order. For logs it makes sense (error < warning
< info...) but I was wondering whether one would possibly want to enable  
tracing from two different parts of the library without the one necessarily  
triggering the other as well...

Later,
        Luigi

[Jens Thiel-2]

Hi Luigi,

I know some companies using http://log4cpp.sourceforge.net/, modeled after
the similar Java library. Haven't used it personally, though.

Jens.


--
Jens Thiel
http://ManagedXLL.net/
[phone]

> -----Original Message-----
> From: [hidden email]
> [mailto:[hidden email]] On Behalf
> Of Luigi Ballabio
> Sent: Friday, January 14, 2005 4:37 PM
> To: Joseph Wang
> Cc: QuantLib users
> Subject: Re: [Quantlib-users] Tracing
>
>
> On 01/14/05 03:58:52, Joseph Wang wrote:
> >> Finally, I intentionally wrote a generic "tag" variable,
> as I'm not sure  
> >> whether a number or a string should be used. Thoughts?
> >
> > The way that java does it is to use integer constants.  
> This makes it
> > easier to compare and for example turn on all debug
> statements above  
> > level N or below level M.  If you set the integers to be
> constants, then  
> > you don't lose anything regarding readability.
>
> Yes, but it implies a total order. For logs it makes sense
> (error < warning < info...) but I was wondering whether one
> would possibly want to enable  
> tracing from two different parts of the library without the
> one necessarily  
> triggering the other as well...
>
> Later,
> Luigi
>
>
>
>
> -------------------------------------------------------
> The SF.Net email is sponsored by: Beat the post-holiday blues
> Get a FREE limited edition SourceForge.net t-shirt from
> ThinkGeek. It's fun and FREE -- well,
> almost....http://www.thinkgeek.com/sfshirt
> _______________________________________________
> Quantlib-users mailing list [hidden email]
> https://lists.sourceforge.net/lists/listinfo/quantlib-users
>
>

[Ferdinando M. Ametrano-3]

At 03:12 AM 1/14/2005, Joseph Wang wrote:
>If someone can point wiki.quantlib.org at 206.196.68.254, I can configure
>the server to bring up
>the right pages.

wiki.quantlib.org should point to 206.196.68.254 in a few hours.

thank you

ciao -- Nando

[Joseph Wang]

I'll set up the server to direct requests to this address to the wiki.  
This should also take a few hours.

In the mean time, it can be reached at ...

http://www.gnacademy.org/twiki/bin/view/Quantlib/



Ferdinando Ametrano wrote:

> At 03:12 AM 1/14/2005, Joseph Wang wrote:
>
>> If someone can point wiki.quantlib.org at 206.196.68.254, I can
>> configure the server to bring up
>> the right pages.
>
>
> wiki.quantlib.org should point to 206.196.68.254 in a few hours.
>
> thank you
>
> ciao -- Nando