An effective algorithm to solve option pricing problems

Document Type : Research Paper


Department of Mathematics‎, ‎Lorestan University‎, ‎Khorramabad‎, ‎Iran‎‎


‎We are aimed to develop a fast and direct algorithm to solve linear‎ complementarity problems (LCP's) arising from option pricing problems‎. We discretize the free boundary problem of American options in temporal direction and obtain a sequence of linear complementarity problems (LCP's) in the finite dimensional Euclidian space $\mathbb{R}^m$‎. ‎We develop a fast and direct algorithm based on the active set strategy to solve the LCP's‎. The active set strategy in general needs $O(2^m m^3)$ operations to solve $m$ dimensional LCP's‎. ‎Using Thomas algorithm‎, ‎we develop an algorithm with order of complexity $O(m)$ which can extremely speed up the computations‎.