• C++ Programming for Financial Engineering
    Highly recommended by thousands of MFE students. Covers essential C++ topics with applications to financial engineering. Learn more Join!
    Python for Finance with Intro to Data Science
    Gain practical understanding of Python to read, understand, and write professional Python code for your first day on the job. Learn more Join!
    An Intuition-Based Options Primer for FE
    Ideal for entry level positions interviews and graduate studies, specializing in options trading arbitrage and options valuation models. Learn more Join!

Asian put option using explicit scheme

Joined
2/3/13
Messages
245
Points
138
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:
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.
 
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.
 
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.
 
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
 
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?
 
Back
Top