Linear operators and linear systems¶
A sum reduction that is linear in one of its Vj inputs is a matrix-vector
product with an implicit M×N matrix. kernox can expose it as a linear operator,
and solve linear systems with it, as PyKeOps' solve does.
Kernel ridge regression with solve¶
Find a such that (alpha·I + K) a = rhs, where K is a Gaussian kernel
matrix:
import torch
import kernox as kp
device = "cuda"
x, y, b = kp.Vi("x", 3), kp.Vj("y", 3), kp.Vj("b", 1)
K = kp.compile((kp.exp(-x.sqdist(y)) * b).sum_over("j"), dtype="float64")
X = torch.randn(2_000, 3, device=device, dtype=torch.float64)
rhs = torch.randn(2_000, 1, device=device, dtype=torch.float64)
a = K.solve("b", rhs, alpha=0.1, x=X, y=X) # (2000, 1)
The first argument names the unknown, a Vj variable of the reduction. The
other inputs are passed by keyword, as for a normal call.
solve uses the conjugate gradient method of PyKeOps, with the same
defaults:
| Option | Default | Meaning |
|---|---|---|
alpha |
1e-10 |
regularization alpha·I |
eps |
1e-6 |
stop when the residual norm is below max(eps·|rhs|, eps) |
maxiter |
10·M |
iteration limit; a RuntimeWarning is emitted if it is reached |
x0 |
zeros | starting point |
The operator must be square (same number of rows and same dimension on both
sides) and is assumed symmetric positive definite, as in PyKeOps: this is not
checked. If an input is named like one of these options, pass the inputs as a
dictionary: K.solve("b", rhs, alpha=0.1, inputs={"x": X, "y": X}).
solve is differentiable with respect to rhs and to the other tensor inputs.
Linear operators¶
run.linear_operator(var, **inputs) binds all inputs except var and returns
an operator with the interface of scipy.sparse.linalg.LinearOperator:
op = K.linear_operator("b", x=X, y=X)
v = torch.randn(2_000, 1, device=device, dtype=torch.float64)
u = op @ v # same as K(x=X, y=X, b=v)
u = op.matvec(v)
w = op.rmatvec(v) # transpose product, also op.T @ v
print(op.shape) # (2000, 2000)
Operands can be (N, Dv) tensors (the result is then (M, Do)), flat
vectors of length N·Dv, or (N·Dv, k) matrices of k columns. shape is
(M·Do, N·Dv). kernox checks symbolically that the reduction really is linear
in var, and raises ValidationError otherwise.
The operator plugs into SciPy's iterative solvers and eigensolvers. For this
interoperability, matvec and rmatvec also accept NumPy arrays: they are
copied to the device of the inputs, and the result is returned as a NumPy
array. This is the only place where kernox accepts NumPy arrays.
import scipy.sparse.linalg as sla
eigenvalues = sla.eigsh(sla.aslinearoperator(op), k=5, return_eigenvectors=False)
Batches¶
With batch dimensions on the bound inputs, op.batch gives the
batch shape and solve solves one system per batch element (like PyKeOps, a
single conjugate gradient runs on the block-diagonal system). rhs can carry
its own batch dimensions, broadcast with those of the inputs.
The conjugate gradient alone¶
kp.conjugate_gradient(linop, b, x0=None, eps=1e-6, maxiter=None) runs the
solver on any function linop and returns (x, info), where info reports
convergence, the number of iterations and the final residual.
x_cg, info = kp.conjugate_gradient(lambda v: 0.1 * v + op @ v, rhs)
print(info["converged"], info["niter"])