! Copyright © 2025-2026 Dynare Team ! ! This file is part of Dynare. ! ! Dynare is free software: you can redistribute it and/or modify it under the terms of the ! GNU General Public License as published by the Free Software Foundation, either version 3 of ! the License, or (at your option) any later version. ! ! Dynare is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without ! even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the ! GNU General Public License for more details. ! ! You should have received a copy of the GNU General Public License along with Dynare. If not, ! see . ! ! Original author: Normann Rion ! ! Linear interpolation with bracket search for policy functions module interpolation use iso_fortran_env, only: real64, int32 use calibration_types, only: gray_code_cache use gray_code, only: compute_linear_indices implicit none (type, external) contains subroutine bracket_linear_weight(x, n, xq, nq, xqi, xqpi) !----------------------------------------------------------------------- ! Subroutine: bracket_linear_weight ! ! Purpose: ! For a given monotonic increasing grid `x` and a vector of query ! points `xq`, computes for each query: ! - the index `xqi` such that xq ∈ [x(xqi), x(xqi+1)] ! - the linear interpolation weight `xqpi` for xqi ! ! This allows for fast and robust piecewise linear interpolation. ! ! Arguments: ! x (in) [real64, dimension(n)] ! Monotonically increasing 1D grid. ! ! n (in) [int32] ! Number of elements in x (length of x). ! ! xq (in) [real64, dimension(nq)] ! Query points to locate in the grid. ! ! nq (in) [int32] ! Number of query points (length of xq). ! ! xqi (out) [int32, dimension(nq)] ! For each xq(i), the index `ilow` such that: ! x(ilow) ≤ xq(i) < x(ilow+1) ! ! xqpi (out) [real64, dimension(nq)] ! For each xq(i), the relative weight in the bracketed interval: ! xqpi(i) = (x(ilow+1) - xq(i)) / (x(ilow+1) - x(ilow)) ! ! Notes: ! - Extrapolation is clamped to the first or last interval. ! - Grid `x` must be strictly increasing for meaningful output. ! !----------------------------------------------------------------------- integer(int32), intent(in) :: n, nq real(real64), intent(in) :: x(n), xq(nq) integer(int32), intent(out) :: xqi(nq) real(real64), intent(out) :: xqpi(nq) integer(int32) :: iq, ilow, ihigh, imid do iq = 1, nq if (xq(iq) < x(1)) then ilow = 1 xqi(iq) = ilow xqpi(iq) = 1.0_real64 else if (xq(iq) >= x(n)) then ! Clamp to last interval [x(n-1), x(n)] with weight 0 on lower point ! This ensures ilow+1 = n is valid for interpolation ilow = n - 1 xqi(iq) = ilow xqpi(iq) = 0.0_real64 else ilow = 1 ihigh = n do while (ihigh - ilow > 1) imid = (ihigh + ilow) / 2 if (xq(iq) >= x(imid)) then ilow = imid else ihigh = imid end if end do xqi(iq) = ilow xqpi(iq) = (x(ilow+1) - xq(iq)) / (x(ilow+1) - x(ilow)) end if end do end subroutine bracket_linear_weight subroutine interpolate(out, xq) type(gray_code_cache), target, intent(inout) :: out real(real64), contiguous, target, intent(in) :: xq(:,:) ! N_x × (N_e ⋅ N_a_sp) ! Useful local variables integer(int32) :: n, M, N_a_om, N_a_sp, a, kf, t real(real64), pointer, contiguous :: mat(:,:) => null(), v(:,:) => null() N_a_om = size(out%is_hard_one, 1) n = size(out%is_hard_one, 2) M = size(out%acc, 1) / N_a_om ! M = N_x ⋅ N_e N_a_sp = size(xq, 2) / (M / size(xq,1)) mat(1:M, 1:N_a_om) => out%acc v(1:M, 1:N_a_sp) => xq ! Initialization at the low corner out%linear_idx = out%corner_idx out%sk = .false. out%z = count(out%is_hard_zero, dim=2) out%beta = out%beta_0 do concurrent (a=1:N_a_om) if (out%z(a) == 0_int32) then mat(:,a) = out%beta(a)*v(:,out%linear_idx(a)) else mat(:,a) = 0.0_real64 end if end do ! Gray code traversal over state dimensions for the other corners do t = 1, out%Kcorn - 1 kf = out%flip_idx(t) if (.not. out%sk(kf)) then ! Lower -> upper on dimension kf out%linear_idx = out%linear_idx + out%stride_states(kf) out%sk(kf) = .true. do concurrent (a=1:N_a_om) if (out%is_hard_one(a,kf)) then ! For nodes with a hard-one kf dim, the number of hard-one dims flipped ! to upper increases out%z(a) = out%z(a)+1_int32 else if (out%is_hard_zero(a,kf)) then ! For nodes with a hard-zero kf dim, the number of hard-zero dims flipped ! to lower decreases out%z(a) = out%z(a)-1_int32 else ! For nodes with a soft kf dim, we update the beta ! coefficient out%beta(a) = out%beta(a)*out%r_up(a,kf) end if end do else ! Upper -> lower on dimension kf out%linear_idx = out%linear_idx - out%stride_states(kf) out%sk(kf) = .false. do concurrent (a=1:N_a_om) if (out%is_hard_one(a,kf)) then ! For nodes with a hard-one kf dim, the number of hard-one dims flipped ! to upper decreases out%z(a) = out%z(a)-1_int32 else if (out%is_hard_zero(a,kf)) then ! For nodes with a hard-zero kf dim, the number of hard-zero dims flipped ! to lower increases out%z(a) = out%z(a)+1_int32 else ! For nodes with a soft kf dim, we update the beta ! coefficient out%beta(a) = out%beta(a)*out%r_down(a,kf) end if end do end if do a = 1,N_a_om if (out%z(a) == 0_int32) mat(:,a) = mat(:,a) + out%beta(a)*v(:,out%linear_idx(a)) end do end do end subroutine interpolate end module interpolation