Parallel Quasi-Monte Carlo Approach to Pricing American Options on Multiple Assets

A Parallel Quasi-Monte Carlo Approach to Pricing American Options on Multiple Assets

Proceedings of the 18th Annual International Symposium on High Performance Computing Systems and Applications, Winnipeg, Manitoba, May 16-19, pages 27--35, 2004.
(Co-authors: Kevin Lai, Adam W. Kolkiewicz, Ken S. Tan)

In this research, we develop parallel algorithms for pricing American options on multiple assets. Our parallel methods are based on the low discrepancy (LD) mesh method which combines the quasi-Monte Carlo technique with the stochastic mesh method. We present two approaches to parallelize the backward recursion step, which is the most computational intensive part of the LD mesh method. We perform parallel run time analysis of the proposed methods and prove that both parallel approaches are scalable. The algorithms are implemented using MPI. The parallel efficiency of the methods are demonstrated by pricing several American options.

Comparison of various mesh estimators for American call options

S0 = asset price
sigma = volatility
b = number of mesh points per time step
BG = stochastic mesh method by Broadie and Glasserman
AH = average mesh method by Avramidis and Hyden
Parallel LD = our parallel low discrepancy mesh method
Lattice = binomial lattice method (as benchmark)

Various mesh estimators for American call option on one asset with 50 exercise dates
			Mesh estimators
S0	sigma	b	BG	AH	Parallel LD
90	20%	256	9.96 (1.10)	7.73 (0.78)	4.66 (0.02)
		1024	6.22 (0.27)	5.33 (0.29)	4.51 (0.00)
		4096	5.23 (0.16)	4.94 (0.15)	4.47 (0.00)
		Lattice	4.47	4.47	4.47
	40%	256	33.07 (3.75)	25.77 (2.67)	15.15 (0.10)
		1024	20.75 (0.83)	17.74 (0.95)	14.55 (0.01)
		4096	17.43 (0.55)	16.31 (0.56)	14.41 (0.00)
		Lattice	14.40	14.40	14.40
100	20%	256	16.30 (1.40)	13.13 (0.99)	8.26 (0.01)
		1024	10.40 (0.32)	9.39 (0.32)	8.16 (0.00)
		4096	9..09 (0.20)	8.74 (0.18)	8.14 (0.00)
		Lattice	8.14	8.14	8.14
	40%	256	42.38 (4.35)	33.57 (3.05)	19.92 (0.10)
		1024	26.74 (0.94)	23.55 (1.05)	19.36 (0.01)
		4096	22.78 (0.55)	21.53 (0.64)	19.24 (0.00)
		Lattice	19.23	19.23	19.23
90	20%	256	24.14 (1.71)	20.11 (1.18)	13.47 (0.01)
		1024	16.10 (0.32)	14.96 (0.26)	13.43 (0.00)
		4096	14.35 (0.22)	14.00 (0.19)	13.42 (0.00)
		Lattice	13.42	13.42	13.42
	40%	256	52.44 (4.93)	42.18 (3.52)	25.34 (0.09)
		1024	33.32 (1.05)	29.89 (1.14)	24.84 (0.01)
		4096	28.68 (0.77)	27.27 (0.71)	24.75 (0.00)
		Lattice	24.74	24.74	24.74

(Each number is obtained by the mean of 10 independent runs and the number in brackets is the sample standard error.)

The BG mesh estimators are high-biased and the bias is in fact quite high for low mesh points or high volatility cases. The AH mesh estimators show a reduced bias of the BG results, but are still subject to the same high variation as the BG mesh estimators. The convergence of our parallel LD mesh estimators is very fast; accurate answers can generally be obtained by using small number of mesh points. Moreoever, the parallel LD mesh method is very stable as indicated by the small standard errors.

Parallel efficiency

Example 1: Pricing American max-option on 5 assets, 4 exercise times.

The parallel run times (in seconds) of the block approach.
b	Number of processors
b	1	2	3	4	5	6	7	8
4096	961.52	484.948	325.195	224.263	198.578	166.481	141.99	125.649
8192	3834.285	1917.969	1286.414	962.679	776.43	647.71	557.999	490.994
16384	15311.54	7656.253	5129.152	3858.866	3090.062	2574.452	2212.128	1942.534

The checkerboard approach.
b	Number of processors
b	1	4
4096	1315.259	324.632
8192	5115.727	1285.494
16384	20453.7	5118.776

For this example, the option estimates (based on 10 independent replications) are: 25.35 (0.004), 25.34 (0.004), 25.29 (0.003) for b=4096, 8192, 16384, respectively.

Example 2: Pricing American max-option on 5 assets, 10 exercise times.

The parallel run times (in seconds) of the block approach.
b	Number of processors
b	1	2	3	4	5	6	7	8
4096	5095.13	2545.81	1706.74	1286.18	1059.81	870.29	745.50	656.66
8192	20377.22	10181.06	6826.20	5153.52	4233.41	3487.77	2975.32	2626.94
16384	81533.66	40674	27270.57	20611.08	16881.57	13891.15	11831.57	10454.64

The checkerboard approach.
b	Number of processors
b	1	4
4096	5121.534	1290.33
8192	20501.65	5159.38
16384	81862.02	20623.53

For this example, the option estimates (based on 10 independent replications) are: 27.59 (0.169), 27.11 (0.047), 26.72 (0.022) for b=4096, 8192, 16384, respectively.

Example 3: Pricing American geometric average option on 5 assets, 11 exercise times.

The parallel run times (in seconds) of the block approach.
b	Number of processors
b	1	2	3	4	5	6	7	8
4096	5825.38	2920.18	1949.71	1467.83	1212.89	994.59	869.83	772.20
8192	23290.34	11630.76	7748.60	5836.18	4804.93	3913.95	3377.87	2951.25
16384	92947.7	46485.45	30957.5	23296.62	19071.21	15705.02	13366.35	11946.57

The checkerboard approach.
b	Number of processors
b	1	4
4096	5870.807	1500.41
8192	23402.88	5948.86
16384	93263.29	23693.95

For this example, the option estimates (based on 10 independent replications) are: 4.48 (0.024), 4.40 (0.007), 4.34 (0.000) for b=4096, 8192, 16384, respectively.