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

Đang mở
#78 0 bình luận 0 reaction 0 người được giao Xem trên GitHub

Maintainer thường phản hồi trong vòng 1 ngày

Chưa có ai nhận issue này.

Đánh giá

Độ khó
5/5
Thời gian dự kiến
Hơn một tuần
Mức phù hợp với người mới
35/100
Loại issue
Tính năng
Độ rõ ràng
Đặc tả rõ ràng
Mức độ hoạt động
Sôi nổi
Công nghệ
numpy, python

Hướng nghiên cứu

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.

Do mô hình lập chỉ mục viết ra từ nội dung của issue.

Mô tả

#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.
Ngôn ngữ chính
Python
Star
0
Fork
1
Merge trung bình
3 giờ 29 phút
Pull request đã merge (30 ngày)
64

Chuẩn bị môi trường

Dự án này không cung cấp dev container, Dockerfile hay hướng dẫn đóng góp, nên bạn cần tự thiết lập môi trường: hãy bắt đầu từ README và xem hướng dẫn đóng góp lần đầu của chúng tôi để biết các bước chung.

Bắt đầu từ đâu

  1. Đọc hết issue, rồi đọc hướng dẫn đóng góp của dự án.
  2. Bình luận trên issue rằng bạn sẽ nhận — tránh hai người làm cùng một việc.
  3. Fork repository và làm thay đổi trên một nhánh.
  4. Mở pull request có tham chiếu số hiệu của issue.

Issue khác của QuantEcon/benchmarks

Tất cả issue của QuantEcon/benchmarks

Issue tương tự

Thêm issue về Python

Nhận issue mới trong hộp thư của bạn

Bản tóm tắt ngắn những issue GitHub phù hợp với người mới.