← All problems
#82 Linear Recurrence Medium

Given two matrices a and x, each of shape [B, L] (batch size × sequence length), compute the linear recurrence h of shape [B, L] defined by: h[b, 0] = x[b, 0] and h[b, t] = a[b, t] × h[b, t−1] + x[b, t] for t ≥ 1. All values are float32. This operation is the core computational primitive of State Space Models (SSMs) such as Mamba, S4, and H3.

Linear Recurrence: h[t] = a[t] · h[t-1] + x[t] h[0] h[1] h[2] h[3] ×a[1] ×a[2] ×a[3] x[0] x[1] x[2] x[3] + + + + …

Implementation Requirements

Examples

Example 1 — exponential decay (a = 0.5, single impulse):

\[ a = \begin{bmatrix} 0.5 & 0.5 & 0.5 & 0.5 \end{bmatrix}, \quad x = \begin{bmatrix} 1.0 & 0.0 & 0.0 & 0.0 \end{bmatrix} \] \[ h = \begin{bmatrix} 1.0 & 0.5 & 0.25 & 0.125 \end{bmatrix} \]

Example 2 — prefix sum (a = 1, unit inputs):

\[ a = \begin{bmatrix} 1.0 & 1.0 & 1.0 & 1.0 \end{bmatrix}, \quad x = \begin{bmatrix} 1.0 & 1.0 & 1.0 & 1.0 \end{bmatrix} \] \[ h = \begin{bmatrix} 1.0 & 2.0 & 3.0 & 4.0 \end{bmatrix} \]

Full example with B = 2, L = 4:

\[ a = \begin{bmatrix} 0.5 & 0.5 & 0.5 & 0.5 \\ 1.0 & 1.0 & 1.0 & 1.0 \end{bmatrix}, \quad x = \begin{bmatrix} 1.0 & 0.0 & 0.0 & 0.0 \\ 1.0 & 1.0 & 1.0 & 1.0 \end{bmatrix} \] \[ h = \begin{bmatrix} 1.0 & 0.5 & 0.25 & 0.125 \\ 1.0 & 2.0 & 3.0 & 4.0 \end{bmatrix} \]

Constraints

Guided walkthrough coming soon. Below is the official starter signature in each language; the clickable line-by-line explanation hasn't been authored yet.
Problem text & starters from the official AlphaGPU/leetgpu-challenges. Solve it on leetgpu.com.