Store only what is there
Pricing an option on a grid replaces a differential equation by a chain of linear systems. Each grid node is linked to its two neighbours only, so the matrix of the system is tridiagonal: three diagonals of numbers and zeros everywhere else. A dense n×n array stores n² numbers, almost all of them zero; a sparse format stores only the 3n-2 that matter. scipy.sparse.diags([lower, diag, upper], [-1, 0, 1], format='csc') builds such a matrix from its diagonals (the sub-diagonal has n-1 entries and so does the super-diagonal, which is why the lower diagonal is cut to start at the second row and the upper one to end before the last column). The CSC format is the one the sparse solvers want.
The implicit scheme steps the option value back in time by solving A V^new=V^old+boundary at every step. The matrix A does not change from one step to the next, so you factorise it once with scipy.sparse.linalg.splu(A) and each step is only lu.solve(rhs), a very cheap operation for a tridiagonal matrix. The boundary condition at S=0 (a put is worth Ke^(-rτ) there) enters the first equation, which is why the first right-hand side is corrected by lower[0] * K * exp(-r * m * dt). With a 1-year rate of 4.47% and σ=25% the closed-form at-the-money put is worth 7.6987; the scheme gives 7.6958 on a 200×200 grid and 7.6965 on a 400×400 grid, about 0.003 away. A 2000-node grid stores 5,995 numbers in sparse form instead of almost 4 million.
- Store the diagonals, not the zeros:
sparse.diagskeeps 3n - 2 numbers instead of n squared. - Factorise once, solve many times:
splupays the cost up front, then every time step is one cheapsolve. - Boundaries live in the right-hand side: the known value at the edge of the grid is moved to the other side of the equation.
Lab · what's graded
- The three diagonals20 pts
- The sparse matrix15 pts
- Pricing with one factorisation30 pts
- Sparse against dense10 pts
- The pricing error5 pts
- The study on a real rate20 pts