Class ProjectedTridiagonalSOR

java.lang.Object
net.finmath.finitedifference.solvers.ProjectedTridiagonalSOR
public final class ProjectedTridiagonalSOR extends Object
Utility class providing a projected successive over-relaxation (PSOR) algorithm for tridiagonal linear complementarity problems.

The class is intended for problems of the form 

    A x >= b
    x >= obstacle
    (A x - b)_i (x_i - obstacle_i) = 0

where A is a tridiagonal matrix, b is the right-hand side, and obstacle is the lower obstacle or payoff constraint.

The method combines a Gauss-Seidel iteration with over-relaxation and a pointwise projection onto the admissible set defined by the obstacle. It is particularly useful for finite difference discretizations of variational inequalities, for example in the pricing of American-style options.

Two overloads of the solver are provided: one accepting a TridiagonalMatrix container and one accepting the three diagonals directly. Additional utility methods compute the infinity norm of the complementarity residual for a candidate solution.

The caller must provide arrays of consistent length, a positive system dimension, and a tridiagonal system with non-zero diagonal entries.

Author:
Alessandro Gnoatto

  • Method Summary

    Modifier and Type
    Method
    Description
    static double
    complementarityResidualInfNorm(double[] lower, double[] diag, double[] upper, double[] rhs, double[] obstacle, double[] x)
    Computes the infinity norm of the complementarity residual for a candidate solution.
    static double
    complementarityResidualInfNorm(TridiagonalMatrix matrix, double[] rhs, double[] obstacle, double[] x)
    Computes the infinity norm of the complementarity residual for a candidate solution.
    static double[]
    solve(double[] lower, double[] diag, double[] upper, double[] rhs, double[] obstacle, double[] initialGuess, double omega, int maxIterations, double tolerance)
    Solves a tridiagonal linear complementarity problem using projected SOR.
    static double[]
    solve(TridiagonalMatrix matrix, double[] rhs, double[] obstacle, double[] initialGuess, double omega, int maxIterations, double tolerance)
    Solves a tridiagonal linear complementarity problem using projected SOR.

    Methods inherited from class Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

  • Method Details

    • solve

      public static double[] solve(TridiagonalMatrix matrix, double[] rhs, double[] obstacle, double[] initialGuess, double omega, int maxIterations, double tolerance)
      Solves a tridiagonal linear complementarity problem using projected SOR.

      This is a convenience overload accepting the system matrix in TridiagonalMatrix form.

      Parameters:
      matrix - The tridiagonal system matrix.
      rhs - The right-hand side vector b.
      obstacle - The obstacle vector defining the lower bound constraint x >= obstacle.
      initialGuess - The initial iterate used to start the PSOR iteration.
      omega - The relaxation parameter. Values in the interval (0, 2) are typically used in practice.
      maxIterations - The maximum number of PSOR iterations.
      tolerance - The stopping tolerance for the maximum absolute change between two consecutive iterates. If tolerance <= 0, the iteration runs for the full number of iterations.
      Returns:
      An approximate solution of the tridiagonal linear complementarity problem.

    • solve

      public static double[] solve(double[] lower, double[] diag, double[] upper, double[] rhs, double[] obstacle, double[] initialGuess, double omega, int maxIterations, double tolerance)
      Solves a tridiagonal linear complementarity problem using projected SOR.

      Starting from the provided initial guess, the method performs Gauss-Seidel-style updates, applies over-relaxation, and then projects each updated component onto the obstacle constraint. Before the iteration starts, the initial guess is projected onto the admissible region x >= obstacle.

      At each iteration, the method monitors the maximum absolute update size. If this quantity falls below the specified tolerance, the iteration is stopped early.

      Parameters:
      lower - The lower diagonal of the tridiagonal system matrix.
      diag - The main diagonal of the tridiagonal system matrix.
      upper - The upper diagonal of the tridiagonal system matrix.
      rhs - The right-hand side vector b.
      obstacle - The obstacle vector defining the lower bound constraint x >= obstacle.
      initialGuess - The initial iterate used to start the PSOR iteration.
      omega - The relaxation parameter. Values in the interval (0, 2) are typically used in practice.
      maxIterations - The maximum number of PSOR iterations.
      tolerance - The stopping tolerance for the maximum absolute change between two consecutive iterates. If tolerance <= 0, the iteration runs for the full number of iterations.
      Returns:
      An approximate solution of the tridiagonal linear complementarity problem.
      Throws:
      ArithmeticException - If a zero diagonal entry is encountered during the iteration.

    • complementarityResidualInfNorm

      public static double complementarityResidualInfNorm(TridiagonalMatrix matrix, double[] rhs, double[] obstacle, double[] x)
      Computes the infinity norm of the complementarity residual for a candidate solution.

      This is a convenience overload accepting the system matrix in TridiagonalMatrix form.

      Parameters:
      matrix - The tridiagonal system matrix.
      rhs - The right-hand side vector b.
      obstacle - The obstacle vector.
      x - The candidate solution vector.
      Returns:
      The infinity norm of the complementarity residual.

    • complementarityResidualInfNorm

      public static double complementarityResidualInfNorm(double[] lower, double[] diag, double[] upper, double[] rhs, double[] obstacle, double[] x)
      Computes the infinity norm of the complementarity residual for a candidate solution.

      For each component, the residual combines:

      • the primal feasibility violation max(0, obstacle[i] - x[i]),
      • the dual feasibility violation max(0, rhs[i] - (A x)[i]),
      • the complementarity defect |(x[i] - obstacle[i]) * ((A x)[i] - rhs[i])|.

      The method returns the maximum of these quantities over all components. A value close to zero indicates that the complementarity conditions are nearly satisfied.

      Parameters:
      lower - The lower diagonal of the tridiagonal system matrix.
      diag - The main diagonal of the tridiagonal system matrix.
      upper - The upper diagonal of the tridiagonal system matrix.
      rhs - The right-hand side vector b.
      obstacle - The obstacle vector.
      x - The candidate solution vector.
      Returns:
      The infinity norm of the complementarity residual.