Improving Projected Successive OverRelaxation Method for Linear Complementarity Problems
by
Minas D. Koulisianis
Computer Engineering and Informatics Deptartment, University of Patras, GREECE
Coauthors: Theodor S. Papatheodorou (Computer Engineering and Informatics Deptartment, University of Patras, GREECE)

Projected Successive OverRelaxation (PSOR), an important method for solving Linear Complementarity Problems (LCP), can be improved considerably if one takes into account the underlying physical properties of the problem involved. We show this for LCPs arising in the case of the American Options Valuation Problem. For such problems, a time stepping procedure is necessary in which one has to solve a sequence of discrete LCPs, one per each time step. In this case, a moving (unknown) boundary separates two domains over which different solution properties hold. Taking advantage of this separation leads to an implementation of PSOR for problems of smaller dimension. This, in turn, leads to a new iterative scheme which is up to 50% faster as compared to plain PSOR.

References

M. D. Koulisianis, T.S. Papatheodorou, A 'Moving Index' method for the solution of the American options valuation problem, Mathematics and Computers in Simulation, Volume 54, Issue 4-5, 15 December 2000, Elsevier Science

Date received: March 29, 2001