P6: a root find per grid point, by time iteration on os_time_iter's savings problem
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
- Lĩnh vực
- machine-learning, performance
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 loopsbrentqin 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
- Đọc hết issue, rồi đọc hướng dẫn đóng góp của dự án.
- 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.
- Fork repository và làm thay đổi trên một nhánh.
- Mở pull request có tham chiếu số hiệu của issue.
Issue khác của QuantEcon/benchmarks
-
Độ khó 4/5 3-5 ngày Mức phù hợp với người mới 25/100
QuantEcon/benchmarks#72 · 1 bình luận ·
Maintainer thường phản hồi trong vòng 1 ngày
-
P5: Markov chains, starting with the stationary distribution of a savings policy (aiyagari_jax)Đang mở
Độ khó 5/5 Hơn một tuần Mức phù hợp với người mới 45/100
QuantEcon/benchmarks#47 ·
Maintainer thường phản hồi trong vòng 1 ngày
-
Độ khó 5/5 Hơn một tuần Mức phù hợp với người mới 25/100
QuantEcon/benchmarks#27 · 2 bình luận ·
Maintainer thường phản hồi trong vòng 1 ngày
-
Float32 fidelity: which float64 lectures need float64, and can the heaviest step drop to float32?Đang mở
Độ khó 5/5 Hơn một tuần Mức phù hợp với người mới 25/100
QuantEcon/benchmarks#11 · 2 bình luận ·
Maintainer thường phản hồi trong vòng 1 ngày
-
Độ khó 5/5 Hơn một tuần Mức phù hợp với người mới 32/100
QuantEcon/benchmarks#5 · 2 bình luận ·
Maintainer thường phản hồi trong vòng 1 ngày
Tất cả issue của QuantEcon/benchmarks
Issue tương tự
-
needs-triage
Độ khó 1/5 Dưới một giờ Mức phù hợp với người mới 88/100
flashinfer-ai/flashinfer#9803 ·
Maintainer thường phản hồi trong vòng 1 ngày
-
bug frontend good first issue help wanted
Độ khó 2/5 1-3 giờ Mức phù hợp với người mới 72/100
oscarbol09/thesisforge#61 ·
-
api bug performance
Độ khó 2/5 1-3 giờ Mức phù hợp với người mới 82/100
oscarbol09/audiobard#159 ·
-
area:web p2 product:business triage:active type:bug
Độ khó 1/5 Dưới một giờ Mức phù hợp với người mới 89/100
cuadrao-ai/argus#2328 ·
Maintainer thường phản hồi trong vòng 1 ngày
-
bug frontend good first issue help wanted
Độ khó 2/5 1-3 giờ Mức phù hợp với người mới 88/100
nikhilb2/simple_invoicing#907 ·