Schwarz Modulus Based Matrix Splittings with Minimal Polynomial Extrapolation Acceleration for linear complementarity problems arising from American option pricing
For practitioners pricing American options, this method offers a faster solver for linear complementarity problems, though the improvement is demonstrated only on a model problem.
The paper introduces a Schwarz modulus-based matrix splitting method accelerated by minimal polynomial extrapolation for solving linear complementarity problems in American option pricing, achieving up to an order of magnitude reduction in iteration counts compared to classical methods.
Pricing American options is more complicated than pricing European options, because they can be exercised at any time, and one thus needs to solve a linear complementarity problem instead of simply doing time stepping for computing European options. We introduce a new Schwarz modulus-based splitting method for solving such linear complementarity problems, and further accelerate them using Modified Polynomial Extrapolation, a non-linear vector sequence acceleration technique, which is very much related to Krylov methods in the linear case. Numerical experiments on a model problem show that our new solver can have close to an order of magnitude lower iteration counts than the classically used modulus-based matrix splitting technique.