P6: a root find per grid point, by time iteration on os_time_iter's savings problem

Abierto
#78 0 comentarios 0 reacciones 0 asignados Ver en GitHub

Los mantenedores suelen responder en 1 día

Nadie ha tomado este issue todavía.

Evaluación

Dificultad
5/5
Tiempo estimado
Más de una semana
Aptitud para principiantes
35/100
Tipo de issue
Nueva funcionalidad
Claridad
Bien especificado
Estado de actividad
Activo
Stack tecnológico
numpy, python

Línea de trabajo

The issue specifies the os_time_iter model, three stack implementations, proposed sweeps, and checks, but does not name benchmark files or test entry points. Start by locating the existing P6 plan from issue #5 and the lecture's os_time_iter implementation, then compare how P1, P2, and P5 structure their benchmark cells. Done means implementing the proposed sweeps and checks, with recorded iteration counts and policy errors against the known optimum.

Escrito por el modelo de indexación a partir del texto del issue.

Descripción

#5's Phase 2 lists P6, root finding and optimisation per state: Newton or bisection over a grid, many small independent solves. This proposes P6's design, from lecture-python's os_time_iter (Optimal Savings III: time iteration). The model, the root-finder and the precisions below were agreed with Matt on 2026-11-20. The sweeps are proposed here for his approval. (Revised on 2026-11-20 after development runs on qe-mini1, before approval: the grid sweep stops at 50,000, not 100,000, and Numba's float32 sums the shocks with a compensated sum. Both are explained below.)

Why

  • It is the per-state root find, every iteration. The lecture's Coleman–Reffett operator solves the Euler equation for consumption at every grid point with SciPy's brentq, and time iteration applies it until the policy settles. A NumPy author loops brentq in Python, Numba runs a root-finder per point in compiled code, and JAX vectorises the root-finder over all points at once. A vectorised loop runs until its slowest point has converged, which is the effect #5 asks P6 to measure.
  • Its answer is known exactly. With the lecture's log utility and Cobb–Douglas production, the optimal policy is σ*(x) = (1 − αβ) x, whatever the shocks. So every cell can report its error against the truth, not only against NumPy.

The problem

Model os_time_iter's: u(c) = log c, f(k) = k^α with α = 0.4, β = 0.96, and shocks z = exp(μ + ν ε) with μ = 0 and ν = 0.1; wealth x on an evenly spaced grid from 1e-4 to 4
The shocks Drawn once by NumPy from the lecture's seed (1234), outside the timed cell, and shared by every stack
The operator At each grid point x, the consumption c in (1e-10, x − 1e-10) that solves u′(c) = β · mean over shocks of u′(σ̂(f(x − c) z)) f′(x − c) z, where σ̂ interpolates the current policy linearly, as np.interp does
Time iteration From σ(x) = x, the lecture's start, until the policy changes by less than 1e-5, the lecture's tolerance, or 1,000 iterations
The root-finder Brent's method in every stack, as SciPy's brentq implements it, at its tolerances: xtol 2e-12 and rtol 4 eps in float64; 1e-6 and 4 eps of float32 in float32
What is timed The whole time iteration, from σ(x) = x to the final policy
Sweeps (proposed) grid: 120 points (the lecture's), 1,000, 5,000, 20,000 and 50,000, with the lecture's 250 shocks. shocks: 250, 1,000, 5,000, 20,000 and 100,000, with the lecture's 120 points
Precision float64 and float32
Recorded The time-iteration count, and the policy's largest error against σ*, relative to σ*'s largest value, as a measure of its own

Why Brent everywhere. A prototype on qe-mini1, with another session's timings running alongside, compared root-finders on this model. All took 13 iterations, and their policies agreed to within 7e-13:

Method 120 points 1,000 points
SciPy's brentq in a Python loop (the lecture's) 0.11 s 1.9 s
Bisection, vectorised in NumPy 0.26 s 5.6 s
Bisection, vectorised in JAX on the CPU 0.34 s 3.5 s
Newton with autodiff and a bisection fallback, in JAX 0.21 s 4.0 s

Bisection needs about 41 evaluations a point to reach 2e-12, where Brent's method needs about 10. Newton took about 37 steps an iteration at its slowest point, most likely because the interpolated policy is piecewise linear, so its derivative jumps and some points keep falling back to bisection. One algorithm in every stack, the lecture's, keeps the comparison about the stacks, as in P1, P2 and P5.

Why each precision has its own tolerance. In a JAX prototype, using bisection, float32 at float64's 2e-12 never stopped. At 1e-6 it took the same 13 iterations, with an error against σ* of 1.64e-6 against float64's 1.52e-6. Those errors come from time iteration's stopping tolerance of 1e-5. They were the same at 120 and 5,000 points and at 250 to 20,000 shocks, since σ* doesn't depend on the shocks and linear interpolation reproduces it exactly.

NumPy and Numba in float32. np.interp returns float64 even for float32 inputs, in NumPy and in Numba, and SciPy's brentq iterates in Python floats. So their float32 cells compute mostly in float64. As for P7 (#73), these cells are what a user gets in float32, and the README will say so. It will also say that P3's NumPy and Numba float32 interpolation, through the same np.interp, is float64 too. JAX's float32 is float32 throughout.

Sizes. Development runs on the M6 (not measurements: another session's timings ran alongside) took every stack to 100,000 in both sweeps, and all agreed. But at 100,000 grid points NumPy's loop took 194 s a run in float64 and 440 s in float32, where its scalar arithmetic mixes float32 and Python floats. A cell is a cold run and at least one warm run, so NumPy's float32 cell came to about 880 s, against the 900 s cell limit, and a slower CPU would time out. So grid stops at 50,000, as P3 does. The shocks sweep keeps 100,000: NumPy took 20 s a run there. A vectorised evaluation holds grid points × shocks values at once: up to 100 MB in float64, at 50,000 points with 250 shocks.

Stacks

The root-finder Over the grid points
NumPy SciPy's brentq A Python loop, as in the lecture
Numba Brent's method written in njit to SciPy's brentq, since Numba has none of its own. It interpolates by hand, so float32 stays float32, and sums over the shocks with Kahan's compensated sum: summed one by one in float32, the error against σ* grew with the shocks, from 2.6e-6 at 250 to 4.2e-4 at 100,000, and took one iteration more at 5,000 and 20,000. NumPy's and JAX's means sum pairwise, and stayed at about 1.5e-6 A prange loop, so numba-parallel splits the points across cores
JAX Brent's method written to SciPy's brentq, as jax.numpy code Vectorised over the points inside lax.while_loop, which runs until the slowest point has converged; time iteration in an outer lax.while_loop

Checks

  • The policy at 64 fixed positions, against NumPy's in float64 at the same size, within a relative 1e-8 in float64 and 1e-3 in float32.
  • The iteration count, against NumPy's in the same precision.
  • The error against σ,* recorded in every cell, so a reader can see each precision's accuracy against the truth.
Lenguaje dominante
Python
Estrellas
0
Forks
1
Merge medio
3 h 29 min
PR fusionados (30 d)
64

Preparar el entorno

Este proyecto no incluye contenedor de desarrollo, Dockerfile ni guía de contribución, así que la configuración corre por tu cuenta: empieza por su README y consulta nuestra guía para la primera contribución para los pasos generales.

Primeros pasos

  1. Lee el issue completo y luego la guía de contribución del proyecto.
  2. Comenta en el issue que vas a ocuparte — evita que dos personas hagan lo mismo.
  3. Haz un fork del repositorio y trabaja en una rama.
  4. Abre un pull request que haga referencia al número del issue.

Más de QuantEcon/benchmarks

Todos los issues de QuantEcon/benchmarks

Issues similares

Más issues de Python

Recibe los nuevos issues en tu correo

Un resumen breve de issues de GitHub para principiantes.