使用平行運算加速最小平方蒙地卡羅法

Abstract

本研究以平行運算加速最小平方蒙地卡羅法在財金領域的應用。我們根據路徑將最小平方蒙地卡羅法分割成多個子問題，每一個子問題由一個從屬行程獨立運算，直到結果計算完成後再傳回主行程，由主行程平均所有結果來得到最後的評價。此方法將最小平方蒙地卡羅法轉換成尷尬平行的問題。本研究使用平行虛擬機（Parallel Virtual Machine）及ALGLIB實作，並對美式賣權進行評價。由實驗結果可得知，使用平行運算於最小平方蒙地卡羅法時，評價結果並不會失真，同時速度也能有效率的提升，我們使用8台機器共64個行程得到了55倍的加速。本研究所提出的方法可延伸至使用最小平方蒙地卡羅法評價更複雜的衍生性金融商品。

This thesis accelerates the popular least-squares Monte Carlo method (LSM) in finance with parallel computing. Several processes are created to solve LSM. Each process solves a smaller version of LSM independently before averaging the values calculated by all the processes. This methodology turns LSM into an embarrassingly parallel problem. The program is implemented using Parallel Virtual Machine (PVM) and ALGLIB. This thesis focuses on the pricing of American put options. Our proposed method gives accurate option prices with excellent speedups and achieves a speedup of 55 using 64 processes with 8 machines. The same methodology is expected to yield excellent speedups for LSM when applied to more complex financial derivatives.