Source code for quantdata.sanos.tridiag
"""
Grid Sanos tridiagonal solver for SANOS-type transition operators, c.f. http://arxiv.org/abs/2211.13227
"""
from __future__ import annotations
from quantdata.utils.backbone import Backbone, BackboneNumpy
from cdxcore.err import verify_inp
[docs]
def solve_sanos_tridiagonal(*, w_minus: Backbone.Array,
w_plus: Backbone.Array,
rhs: Backbone.Array,
backbone : Backbone = BackboneNumpy(),
) -> Backbone.Array:
"""Solve SANOS tridiagonal system with boundary structure from w_minus/w_plus.
The system size is ``N = (N-2) + 2`` where:
- ``w_minus`` and ``w_plus`` have shape ``(..., N-2)``
- ``rhs`` has shape ``(..., N)``
This avoids materializing full tridiagonal bands and is more memory efficient
for the SANOS parameterization.
"""
assert w_minus.shape == w_plus.shape, f"w_minus and w_plus must have the same shape, got {w_minus.shape} and {w_plus.shape}"
n_inner = w_minus.shape[-1]
n = n_inner + 2
lead = w_minus.shape[:-1]
assert rhs.shape == lead + (n,), f"rhs must have shape {lead + (n,)}, got {tuple(rhs.shape)}"
# classic form
# https://en.wikipedia.org/wiki/Tridiagonal_matrix_algorithm
#
# b_0 c_0 x_0 rhs_0
# a_1 b_1 c_1 x_1 rhs_1
# a_2 b_2 c_2 x_2 = rhs_2
# ... ... ...
# a_{N-1} b_{N-1} x_{N-1} rhs_{N-1}
#
# Row 0:
# b_0 = 1
# c_0 = -w_minus[0]
#
# 1 * x0 - w_minus[0] * x1 = rhs0
cp_terms = [-w_minus[..., 0]] # = c_0/b_0
y_terms = [rhs[..., 0]] # = rhs_0/b_0
# Rows 1..N-2
# a_i = - w_plus[i-1] (if i > 1 else 0)
# b_i = 1 + w_minus[i] + w_plus[i]
# c_i = - w_minus[i+1] (if i < N-2 else 0)
#
# =>
#
# cp_i = c_i / (b_i - a_i * cp_{i-1})
# y_i = (rhs_i - a_i * y_{i-1}) / (b_i - a_i * cp_{i-1})
for i in range(1, n - 1):
a_i = -w_plus[..., i - 2] if i > 1 else 0.
b_i = 1.0 + w_minus[..., i - 1] + w_plus[..., i - 1]
c_i = -w_minus[..., i] if i < (n - 2) else 0.
denom = b_i - a_i * cp_terms[i - 1]
cp_terms.append(c_i / denom)
y_terms.append((rhs[..., i] - a_i * y_terms[i - 1]) / denom)
# Last row:
# a_{N-1} = -w_plus[N-3]
# b_{N-1} = 1
#
# -w_plus[N-3] * x[N-2] + 1 * x[N-1] = rhs[N-1]
a_last = -w_plus[..., -1]
b_last = 1.
denom = b_last - a_last * cp_terms[-1]
y_terms.append((rhs[..., -1] - a_last * y_terms[-1]) / denom)
# forward pass
x_terms = [None] * n
x_terms[-1] = y_terms[-1]
for i in range(n - 2, -1, -1):
x_terms[i] = y_terms[i] - cp_terms[i] * x_terms[i + 1]
return backbone.stack(x_terms, axis=-1, dtype=rhs.dtype)