Asian put option using explicit scheme

[Abhishek Najbile]

Hi Guys,

I am pricing a continuous Asian put option using the explicit scheme. I worked out the PDE and got very accurate results to the monte carlo price I got for it. I want to make my code run faster. I have brought it down to about 2 minutes from 11. I want to make it run in under a minute. If any body can help me I will really appreciate it. Thanks. Heres the code:

function price=solve_asian_put_explicit(r,sigma,K,T,N_time,N_space,S_max,N_v,S0);
%**********************************************************
 
%**********************************************************
delta_t=T/N_time; %step in time variable
delta_s=(S_max)/N_space; %step in space variable
ind=floor(S0/delta_s);
delta_s=S0/ind;
delta_v=(K*T)/N_v;
rho=delta_t/(delta_s^2);
dt_dv=delta_t/delta_v;
dt_ds=delta_t/(2*delta_s);
 
%**********************************************************
s=(1:(N_space-1))*delta_s;
s_sqr=s.^2;
v=(0:(N_v+1))*delta_v;
%**********************************************************
phi=zeros(N_space-1,N_v+2);
phi_new=zeros(N_space-1,N_v+2);
% initial condition
for i=1:N_space-1
for j=1:N_v+2
phi(i,j)=max((K*T)-v(j),0);
end
end
%**********************************************************
a=(-r*s*(dt_ds)+(rho*0.5*sigma^2*s_sqr));
b=(1-rho*sigma^2*(s_sqr)-delta_t*r-1.5*s*dt_dv);
c=(2*s*dt_dv);
d=(-0.5*s*dt_dv);
e=(dt_ds*r*s+rho*0.5*sigma^2*s_sqr);
for k=1:N_time
for i=2:N_space-2
for j=1:N_v
phi_new(i,j)= phi(i-1,j)*a(i)+phi(i,j)*b(i)+phi(i,j+1)*c(i)+phi(i,j+2)*d(i)+phi(i+1,j)*e(i);
end;
end;
phi=phi_new;
end;
 
%**********************************************************
 
% return the result
price=phi(ind,1)/T
 
%****************************************
T=1; %maturity
r=0.03; %interest rate
sigma=0.3; %volatility
K=100; %strike price
S0=100; %initial stock price
S_max=S0*exp((r-sigma^2/2)*T+3*sigma*sqrt(T));
N_space=200;
N_time=20000;
N_v=400;
 
 
% compute approximate solution
tic
 
f_approx=solve_asian_put_explicit(r,sigma,K,T,N_time,N_space,S_max,N_v,S0);
 
time_explicit_scheme=toc
%****************************************

-Cheers.

 

[Daniel Duffy]

First question: this code is a finite difference scheme? (remark about MC is confusing).

Explicit is too slow; use an implicit method. 1 minute is too long.

edit: how do you (intend to) model boundary conditons?

// And do it in C++ is the fastest.

 

[Abhishek Najbile]

Hi Daniel,

Thanks for your reply.Yes the code is a finite difference scheme. I priced a discrete asian call option using MC and used put call parity to get a price for the continuous put option. Then I used my finite difference code to check if I got the right answer and its pretty accurate but the time is a little too long. I would have used implicit but my assignment asks for explicit and have to use Matlab to compute it. Is there are way I can reduce the time even more. Thanks.

-Cheers.

 

[Polter]

0. Before you do anything else, profile your code to find out where the main bottlenecks are; here's how:
http://yagtom.googlecode.com/svn/trunk/html/speedup.html

See also:
http://undocumentedmatlab.com/blog/undocumented-profiler-options-part-3/
http://undocumentedmatlab.com/blog/undocumented-profiler-options-part-4/
http://undocumentedmatlab.com/blog/more-undocumented-timing-features/
http://www.wilmott.com/messageview.cfm?catid=8&threadid=83514

1. If possible, vectorize the loops which are the main bottlenecks (it probably won't make sense to vectorize the rest -- e.g., for-loop around line 25, "phi(i,j)=max((K*T)-v(j),0);", could probably be easily vectorized, but I wouldn't expect it to yield significant gains overall, given that your main workhorse is the later loop).

See also "Writing Fast MATLAB Code" (PDF: http://www.getreuer.info/matopt.pdf) from here -- http://www.getreuer.info/tutorials -- and apply where applicable.

2. Try(*) parallelizing the remaining bottleneck-contributing loops,
http://www.mathworks.com/help/distcomp/parfor.html
http://blogs.mathworks.com/loren/2009/10/02/using-parfor-loops-getting-up-and-running/
http://people.sc.fsu.edu/~jburkardt/presentations/sem_2012_parfor.pdf -- in particular, note the ODE example; here's a short description: http://people.sc.fsu.edu/~jburkardt/m_src/ode_sweep_parfor/ode_sweep_parfor.html

(*) -- I say "try", given that parallelism has its own overheads and difficulties and it's not always worth it (e.g., for short tasks -- it's about bandwidth, not latency); but if a tasks takes over a minute, chances are it might help.

3. If you do decide to get more speed, the way Duffy suggested is the way to go, here's how to get started:
- "Writing MATLAB C/MEX Code" (PDF: http://www.getreuer.info/cmex.pdf) from http://www.getreuer.info/tutorials
- http://www.nr.com/nr3_matlab.html

 

[Daniel Duffy]

In general, there's no point trying to parallelise FDM (pde in 1 and 2 factors are too small). And a parallel solution may even be slower.

1. One idea is to do loop-level parallelism on the inner array S for each S mesh point (will have an array of I==A points).

2. Make sure the loop is column-major (Matlab ~ FORTRAN?)

3. Maybe line 37 can be optimised??

A. where are your boundary conditions and how did you discretise dV/dt + adV/dI term? What is I_max?

 

[Daniel Duffy]

If you a few hours then you could try ADE

http://papers.ssrn.com/sol3/papers.cfm?abstract_id=1552926

Euler is OK for 101 but at some time get to the hard stuff if you want better performance, e.g. Crank Nicolson.