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‎.


[1] R.W. Cottle, J.S. Pang and R.E. Stone, The Linear Complementarity Problem, Society for Industrial and Applied Mathematics, 2009.
[2] J. Crank, Free and Moving Boundary Problems, Oxford Science Publications, Clarendon Press, 1984.
[3] D.J. Duffy, Finite Difference Methods in Financial Engineering, Wiley Finance Series, John Wiley & Sons, Ltd., Chichester, 2006.
[4] M.B. Giles and R. Carter, Convergence analysis of Crank-Nicholson and Rannacher time-marching, J. Comput. Finance 9 (2006) 89–112.
[5] R. Glowinski, Numerical Methods for Nonlinear Variational Problems, Scientific Computation, Springer Berlin Heidelberg, 2013.
[6] P. Hartman and G. Stampacchia, On some non-linear elliptic differential-functional equations, Acta Math. 115(1) (1966) 271–310.
[7] A.D. Holmes, A Front-Fixing Finite Element Method for the Valuation of American Options, PhD thesis, University of Nevada, Las Vegas, 2010.
[8] S. Ikonen and J. Toivanen, Pricing American options using LU decomposition, Appl. Math. Sci. (Ruse) 1(49-52) (2007) 2529–2551.
[9] D. Kinderlehrer and G. Stampacchia, An Introduction to Variational Inequalities and Their Applications, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2000.
[10] M. Moradipour and S.A. Yousefi, Using spectral element method to solve variational inequalities with applications in finance, Chaos, Solitons Fractals 81 (2015) 208–217.
[11] J.L. Morales, J. Nocedal and M. Smelyanskiy, An algorithm for the fast solution of symmetric linear complementarity problems, Numer. Math. 111(2) (2008) 251–266.
[12] R. Rannacher, Finite element solution of diffusion problems with irregular data, Numerische Math. 43(2) (1984) 309–327.
[13] R.U. Seydel, Tools for Computational Finance, Universitext Springer-Verlag, Berlin, Fourth Edition, 2009.
[14] J. Toivanen, Numerical valuation of European and American options under Kou’s jump-diffusion model, SIAM J. Sci. Comput. 30(4) (2008) 1949–1970.
Volume 12, Issue 1
May 2021
Pages 261-271
  • Receive Date: 18 August 2020
  • Revise Date: 07 November 2020
  • Accept Date: 10 November 2020