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

オープン
#78 コメント 0 件 リアクション 0 件 担当者 0 名 GitHub で見る

メンテナーはふだん 1 日以内に返信

まだ誰も着手していません。

評価

難易度
5/5
見積もり時間
1週間以上
初心者へのやさしさ
35/100
issue の種類
機能追加
明瞭さ
明確に書かれている
活発さ
活発
技術スタック
numpy, python

調査の方向性

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.

索引モデルが issue の本文から書いたものです。

説明

#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.
主要言語
Python
スター
0
フォーク
1
平均マージ
3時間 29分
マージ済み PR(30日)
64

環境構築

このプロジェクトには開発コンテナ、Dockerfile、コントリビューションガイドがありません。まず README を読み、一般的な手順ははじめてのコントリビューションガイドを参照してください。

はじめの一歩

  1. issue を最後まで読み、次にプロジェクトのコントリビューションガイドを読みます。
  2. 着手することを issue にコメントします — 二人が同じ作業をするのを防げます。
  3. リポジトリをフォークし、ブランチを切って変更します。
  4. issue 番号を参照したプルリクエストを送ります。

QuantEcon/benchmarks のほかの issue

QuantEcon/benchmarks の issue をすべて見る

似ている issue

Python の issue をもっと見る

新しい issue をメールで受け取る

初心者向けの GitHub issue を短くまとめたダイジェスト。