Source code for healpix_resample.knn

"""
knn.py

GPU-friendly sparse HEALPix regridding from unstructured lon/lat samples
to a subset of HEALPix pixels at a target resolution (nside = 2**level).

Core ideas:
- Use HEALPix local neighbourhoods (healpix_geo.kth_neighbourhood) to avoid N×npix distance matrices.
- Build sparse operators M (samples -> grid) and MT (grid -> samples) with Gaussian weights.
- Solve a damped least-squares problem with Conjugate Gradient (CG) on normal equations.

This module is designed for large N and batched values (B,N) on CUDA.
"""

import math
from dataclasses import dataclass
from typing import Generic, Tuple, Optional, Union

import healpix_geo
import numpy as np
import torch

from healpix_resample.base import ResampleResults, T_Array


def _lonlat_to_xyz(lon_rad: torch.Tensor, lat_rad: torch.Tensor) -> torch.Tensor:
    clat = torch.cos(lat_rad)
    return torch.stack([clat * torch.cos(lon_rad),
                        clat * torch.sin(lon_rad),
                        torch.sin(lat_rad)], dim=-1)  # (...,3)

@torch.no_grad()
def _safe_normalize(values: torch.Tensor, sums: torch.Tensor) -> torch.Tensor:
    """``values / sums`` with 0 (instead of NaN) wherever ``sums`` is 0.

    A zero sum means every weight behind it underflowed to 0 (float32 weights
    of samples far from every kept cell, #77), so the links it normalizes
    carry no information: a weight of 0 is the only value consistent with
    the rest of the operator.
    """
    nonzero = sums != 0
    return torch.where(nonzero, values / torch.where(nonzero, sums, torch.ones_like(sums)), torch.zeros_like(values))


def _sigma_level_m(level: int, radius: float = 6371000.0) -> float:
    # sigma = sqrt(4*pi / (12*4**level)) * R
    return math.sqrt(4.0 * math.pi / (12.0 * (4.0 ** level))) * radius
    
# Cells at the same distance as the Npt-th nearest one, up to this tolerance
# (metres), are all linked to the sample (see `_nearest_with_ties`).
TIE_TOLERANCE_M = 1e-6
# at most this many tied cells beyond the Npt-th one
MAX_TIED_EXTRA = 3


def _arc_distance(xyz_a: torch.Tensor, xyz_b: torch.Tensor, radius: float) -> torch.Tensor:
    """Great-circle distance from the chord. For short distances it resolves
    about 1e-9 m, where ``radius * acos(dot)`` resolves only ~0.1 mm (the dot
    product is then within 1e-11 of 1)."""
    chord = torch.linalg.vector_norm(xyz_a - xyz_b, dim=-1)
    return radius * 2.0 * torch.asin(torch.clamp(chord / 2.0, max=1.0))


def _nearest_with_ties(dist: torch.Tensor, cand: torch.Tensor, k: int):
    """The ``k`` nearest candidates of each row (as ``torch.topk``), plus the
    candidates at the same distance as the ``k``-th one, within
    ``TIE_TOLERANCE_M`` (at most ``MAX_TIED_EXTRA`` of them).

    On some HEALPix rings the cell spacing is commensurate with the spacing of
    a regular lon/lat input (e.g. 1/2700 degree cells and 1 arc-second
    inputs at 45.65 N, level 18): whole columns of samples then have their
    ``k``-th and ``(k+1)``-th nearest cells at exactly the same distance.
    Keeping only one of them would leave the choice to the order of
    ``torch.topk`` for equal values or to the last bits of the distances,
    which differ between platforms. All tied cells are linked instead, so the
    operator is symmetric and the same everywhere.

    Returns ``(d_k, i_k, d_x, i_x)``: distances and candidate entries of the
    ``k`` nearest, then of the tied extra ones (``inf`` / ``-1`` where none),
    sorted by distance.
    """
    kk = min(k + MAX_TIED_EXTRA, dist.shape[1])
    d_s, p_s = torch.topk(dist, k=kk, dim=1, largest=False, sorted=True)
    i_s = torch.gather(cand, 1, p_s)
    d_k, i_k = d_s[:, :k], i_s[:, :k]
    d_x, i_x = d_s[:, k:], i_s[:, k:]
    tied = torch.isfinite(d_x) & (d_x <= d_k[:, -1:] + TIE_TOLERANCE_M)
    d_x = torch.where(tied, d_x, torch.full_like(d_x, float("inf")))
    i_x = torch.where(tied, i_x, torch.full_like(i_x, -1))
    return d_k, i_k, d_x, i_x


def _flatten_ties(tied_rows, tied_idx, tied_dist):
    """The tied extra links collected by the searches (lists of row indices and
    ``(n, E)`` blocks from `_nearest_with_ties`) as flat ``(rows, idx, dist)``
    tensors, sorted by sample (by distance within a sample); ``None`` without
    ties. Blocks of different widths (different rings) are fine."""
    if not tied_rows:
        return None
    rows = torch.cat([r[:, None].expand_as(i)[i >= 0] for r, i in zip(tied_rows, tied_idx)])
    idx = torch.cat([i[i >= 0] for i in tied_idx])
    dist = torch.cat([d[i >= 0] for i, d in zip(tied_idx, tied_dist)])
    order = torch.argsort(rows, stable=True)
    return rows[order], idx[order], dist[order]


def _append_tied(idx_out, dist_out, ties):
    """Add the tied links (from `_flatten_ties`) as extra columns of ``idx_out``
    / ``dist_out`` (``-1`` / ``inf`` in the rows without ties). Without ties
    the arrays are returned unchanged, ``(N, Npt)``."""
    if ties is None:
        return idx_out, dist_out
    rows, idx, dist = ties
    # position of each tied link among the links of its sample
    rank = torch.arange(rows.numel(), device=rows.device) - torch.searchsorted(rows, rows)
    n_extra = int(rank.max()) + 1
    N, Npt = idx_out.shape
    idx_new = torch.full((N, Npt + n_extra), -1, device=idx_out.device, dtype=idx_out.dtype)
    dist_new = torch.full((N, Npt + n_extra), float("inf"), device=dist_out.device, dtype=dist_out.dtype)
    idx_new[:, :Npt] = idx_out
    dist_new[:, :Npt] = dist_out
    idx_new[rows, Npt + rank] = idx
    dist_new[rows, Npt + rank] = dist
    return idx_new, dist_new


@dataclass
class NeighbourLinks:
    """The links found by the neighbour search of a `KNeighborsResampler`
    (``healpix_weighted_nearest``), without their distances.

    They depend only on the geometry (the sample coordinates, the level, the
    search parameters), not on the values: they can be kept and given back to
    a resampler built on the same geometry (``neighbours=``), which then skips
    the search. The distances are computed again from the coordinates, with
    the same operations as the search (`link_distances`), so the resampler is
    the same, bit for bit.

    Attributes
    ----------
    cell_ids : (K,) long
        The cells kept by the search, before the resampler prunes the cells
        no sample links to.
    hi : (N, Npt) long
        Index in ``cell_ids`` of the ``Npt`` nearest kept cells of each
        sample (``-1``: none).
    tie_rows, tie_hi : (T,) long
        The links to the cells tied with a sample's ``Npt``-th nearest one.
    """

    cell_ids: torch.Tensor
    hi: torch.Tensor
    tie_rows: torch.Tensor
    tie_hi: torch.Tensor


@torch.no_grad()
def link_distances(
    lon_deg: torch.Tensor,
    lat_deg: torch.Tensor,
    links: NeighbourLinks,
    *,
    level: int,
    nest: bool,
    ellipsoid: str,
    radius: float,
) -> Tuple[torch.Tensor, torch.Tensor]:
    """Distances (metres) of the links of ``links``, as the neighbour search
    computes them: `_arc_distance` between the unit vectors of the cell
    centres and of the samples (float64). Returns ``(d, tie_d)``: ``(N, Npt)``
    (``inf`` where ``hi`` is ``-1``) and ``(T,)``."""
    dev = links.hi.device
    cells = links.cell_ids.detach().cpu().numpy().astype(np.uint64)
    hp = healpix_geo.nested if nest else healpix_geo.ring
    lon_c, lat_c = hp.healpix_to_lonlat(cells, level, ellipsoid=ellipsoid)
    xyz_c = _lonlat_to_xyz(
        torch.deg2rad(torch.as_tensor(np.asarray(lon_c), dtype=torch.float64, device=dev)),
        torch.deg2rad(torch.as_tensor(np.asarray(lat_c), dtype=torch.float64, device=dev)),
    )
    xyz1 = _lonlat_to_xyz(
        torch.deg2rad(lon_deg.to(dev, dtype=torch.float64)),
        torch.deg2rad(lat_deg.to(dev, dtype=torch.float64)),
    )
    if xyz_c.shape[0] == 0:
        d = torch.full(links.hi.shape, float("inf"), dtype=torch.float64, device=dev)
        return d, torch.empty((0,), dtype=torch.float64, device=dev)
    # in batches of samples: the (n, Npt, 3) gathers of a whole 10 m chunk
    # would take GBs (each distance is computed alone: same values)
    d = torch.empty(links.hi.shape, dtype=torch.float64, device=dev)
    step = 1 << 18
    for s in range(0, links.hi.shape[0], step):
        hi = links.hi[s : s + step]
        dd = _arc_distance(xyz_c[hi.clamp(min=0)], xyz1[s : s + step, None, :], radius)
        d[s : s + step] = torch.where(hi >= 0, dd, torch.full_like(dd, float("inf")))
    tie_d = _arc_distance(xyz_c[links.tie_hi], xyz1[links.tie_rows], radius)
    return d, tie_d


[docs] @torch.no_grad() def healpix_weighted_nearest( longitude1: torch.Tensor, latitude1: torch.Tensor, level: int, Npt: int, *, return_ties: bool = False, **kwargs, ): """ Returns: cell_ids: (K,) HEALPix pixels (at level) kept by the weight threshold (and intersected with out_cell_ids, if given) idx_k : (N, Npt + E) indices into cell_ids (0..K-1), -1 if not enough neighbours dist_k : (N, Npt + E) distances (m) to the centres of those pixels, inf if not enough neighbours With ``return_ties=True``: ``(cell_ids, idx_k, dist_k, ties)``, where ``idx_k`` / ``dist_k`` are ``(N, Npt)`` and ``ties = (rows, idx, dist)`` holds the tied links as flat 1-D tensors (empty without ties). This is what ``KNeighborsResampler`` uses: the ties are a few per million samples, so they do not widen the ``(N, Npt)`` arrays. Notes: - The E extra columns of idx_k / dist_k hold the cells at the same distance as the Npt-th one (ties, see ``_nearest_with_ties``), -1 / inf for the samples without a tie; E = 0 when no sample has a tie. - Distances: chord-based great-circle distance in the Npt-nearest search (``_arc_distance``), ``R * acos(dot)`` in the threshold stage. - healpix_geo is used for lonlat_to_healpix, kth_neighbourhood, healpix_to_lonlat. - The accuracy is good enough for "pixel centre matching". - ``batch_size``: the weight accumulation and the Npt-nearest search allocate about ``(2*ring+1)**2 * 100`` bytes per sample (the neighbourhood ids, centre coordinates, distances and weights of every sample at once). With ``batch_size`` set, the samples are processed in slices of that size, so this temporary memory is bounded by the batch and not by N; the per-cell weight sums and the per-sample results are the same (see ``_healpix_weighted_nearest_batched``). - ``coarse_level_delta`` (nested ids only, ``Npt > 1``): number the cells from their parents that many levels coarser (``c * 4**k + j`` ids, centres computed once per cell) and get the neighbourhoods from the face coordinates instead of a global sort and ``kth_neighbourhood`` per sample, in batches of ``batch_size`` samples (default 32768). Same result as without it, in less time and memory. See ``_coarse_weighted_nearest``. The other keyword arguments are those of ``_healpix_weighted_nearest``. """ cell_ids, idx_k, dist_k, ties = _healpix_weighted_nearest(longitude1, latitude1, level, Npt, **kwargs) if not return_ties: idx_k, dist_k = _append_tied(idx_k, dist_k, ties) return cell_ids, idx_k, dist_k if ties is None: dev = cell_ids.device ties = ( torch.empty((0,), device=dev, dtype=torch.long), torch.empty((0,), device=dev, dtype=torch.long), torch.empty((0,), device=dev, dtype=torch.float64), ) return cell_ids, idx_k, dist_k, ties
def _healpix_weighted_nearest( longitude1: torch.Tensor, # (N,) degrees latitude1: torch.Tensor, # (N,) degrees level: int, Npt: int, *, nest: bool = True, threshold: float = 0.1, radius: float = 6371000.0, ellipsoid: str = "WGS84", sigma: float | None = None, # allowed subset of output pixels (HEALPix ids at the same "level") out_cell_ids: Optional[Union[np.ndarray, torch.Tensor]] = None, # neighbourhood used to estimate the weights (builds cell_ids) ring_weight: Optional[int] = None, # neighbourhood used to find Npt neighbours among the kept pixels (can grow automatically) ring_search_init: Optional[int] = None, ring_search_max: int = 20, num_threads: int = 0, device_for_dist: Optional[torch.device] = None, # process the samples in batches of this size (None: all at once) batch_size: Optional[int] = None, # candidate cells from the cells this many levels coarser (None: the # fine-level neighbourhoods); see `_coarse_weighted_nearest` coarse_level_delta: Optional[int] = None, ) -> Tuple[torch.Tensor, torch.Tensor, torch.Tensor]: """See :func:`healpix_weighted_nearest`. Returns ``(cell_ids, idx_k, dist_k, ties)`` with ``(N, Npt)`` arrays and the tied links from `_flatten_ties` (``None`` without ties).""" assert longitude1.ndim == latitude1.ndim == 1 N = int(longitude1.numel()) assert Npt >= 1 # The geometry runs in float64: healpix_geo returns float64 cell centres, # and float32 coordinates would mix dtypes in the distance buffers (#73). longitude1 = longitude1.to(torch.float64) latitude1 = latitude1.to(torch.float64) # --- default rings # smallest ring giving >= Npt candidates in a (2r+1)^2 square, plus a margin r_min = int(math.ceil((math.sqrt(Npt) - 1.0) / 2.0)) if ring_weight is None: ring_weight = max(2, r_min + 2) # wider: better estimate of the global weights if ring_search_init is None: ring_search_init = max(1, r_min + 1) # the search below must run at least once ring_search_max = max(ring_search_max, ring_search_init) # --- distances: computed on the GPU when available dev = device_for_dist if device_for_dist is not None else longitude1.device if coarse_level_delta is not None and Npt > 1: if not nest: raise ValueError("coarse_level_delta needs the nested indexing scheme (nest=True)") if not 1 <= int(coarse_level_delta) <= level: raise ValueError(f"coarse_level_delta must be in [1, level], got {coarse_level_delta}") if batch_size is not None and int(batch_size) < 1: raise ValueError(f"batch_size must be >= 1, got {batch_size}") return _coarse_weighted_nearest( longitude1, latitude1, level=level, Npt=Npt, k=int(coarse_level_delta), threshold=threshold, radius=radius, ellipsoid=ellipsoid, sigma=sigma, out_cell_ids=out_cell_ids, ring_weight=ring_weight, ring_search_init=ring_search_init, ring_search_max=ring_search_max, num_threads=num_threads, dev=dev, batch_size=int(batch_size) if batch_size is not None else 1 << 15, ) if batch_size is not None and Npt > 1: if int(batch_size) < 1: raise ValueError(f"batch_size must be >= 1, got {batch_size}") return _healpix_weighted_nearest_batched( longitude1, latitude1, level=level, Npt=Npt, nest=nest, threshold=threshold, radius=radius, ellipsoid=ellipsoid, sigma=sigma, out_cell_ids=out_cell_ids, ring_weight=ring_weight, ring_search_init=ring_search_init, ring_search_max=ring_search_max, num_threads=num_threads, dev=dev, batch_size=int(batch_size), ) # --- CPU numpy for healpix_geo lon_np = longitude1.detach().cpu().numpy().astype(np.float64) lat_np = latitude1.detach().cpu().numpy().astype(np.float64) if nest: ipix1 = healpix_geo.nested.lonlat_to_healpix(lon_np, lat_np, level, num_threads=num_threads,ellipsoid=ellipsoid) ipix_u, inv = np.unique(ipix1.astype(np.uint64), return_inverse=True) if Npt==1: return torch.from_numpy(ipix_u.astype(np.int64)).to(dev), torch.from_numpy(inv.astype(np.int64)).to(dev), 0, None neigh_u_w = healpix_geo.nested.kth_neighbourhood(ipix_u, level, ring_weight, num_threads=num_threads) else: ipix1 = healpix_geo.ring.lonlat_to_healpix(lon_np, lat_np, level, num_threads=num_threads,ellipsoid=ellipsoid) ipix_u, inv = np.unique(ipix1.astype(np.uint64), return_inverse=True) if Npt==1: return torch.from_numpy(ipix_u.astype(np.int64)).to(dev), torch.from_numpy(inv.astype(np.int64)).to(dev), 0, None neigh_u_w = healpix_geo.ring.kth_neighbourhood(ipix_u, level, ring_weight, num_threads=num_threads) # healpix_geo.kth_neighbourhood may return -1 for "invalid" neighbours. # We replace invalid entries by a valid neighbour (the last valid in the row; fallback to the center pixel). # This keeps arrays dense (no masking) and avoids uint64 overflow issues. # Duplicates are later handled naturally by weight accumulation + normalization. neigh_u_w = neigh_u_w.astype(np.int64, copy=False) valid = neigh_u_w >= 0 # position of the last valid entry in each row last_valid_pos = valid[:, ::-1].argmax(axis=1) last_valid_pos = (neigh_u_w.shape[1] - 1) - last_valid_pos last_valid = neigh_u_w[np.arange(neigh_u_w.shape[0]), last_valid_pos] # fallback when the whole row is invalid -> centre pixel all_invalid = ~valid.any(axis=1) last_valid[all_invalid] = ipix_u[all_invalid].astype(np.int64, copy=False) # replace the -1 entries (explicit broadcast) mask = neigh_u_w < 0 neigh_u_w[mask] = np.broadcast_to(last_valid[:, None], neigh_u_w.shape)[mask] del valid, mask, last_valid, last_valid_pos, all_invalid # neigh_w : (N, Kw) # Every (N, Kw) temporary of this stage (~100 B per sample and per # neighbourhood pixel each) is dropped as soon as the next one is built: # they used to stay alive until the function returned, under the search # below. neigh_w = neigh_u_w[inv] Kw = neigh_w.shape[1] del neigh_u_w # --- lon/lat centres of the neighbourhood pixels (Kw*N can be large) => computed on unique pixels neigh_w_flat = neigh_w.reshape(-1).astype(np.uint64) del neigh_w neigh_w_uniq, back = np.unique(neigh_w_flat, return_inverse=True) del neigh_w_flat if nest: lon_c_deg, lat_c_deg = healpix_geo.nested.healpix_to_lonlat(neigh_w_uniq, level,ellipsoid=ellipsoid) else: lon_c_deg, lat_c_deg = healpix_geo.ring.healpix_to_lonlat(neigh_w_uniq, level,ellipsoid=ellipsoid) lon1 = torch.deg2rad(longitude1.to(dev)) lat1 = torch.deg2rad(latitude1.to(dev)) xyz1 = _lonlat_to_xyz(lon1, lat1) # (N,3) lon_c = torch.deg2rad(torch.from_numpy(np.asarray(lon_c_deg)).to(dev)) lat_c = torch.deg2rad(torch.from_numpy(np.asarray(lat_c_deg)).to(dev)) xyz_c = _lonlat_to_xyz(lon_c, lat_c) # (Kuniq,3) # Remap neighbours to unique indices (Kuniq) back_t = torch.from_numpy(np.asarray(back, dtype=np.int64)).to(dev) # (N*Kw,) del back back_t = back_t.view(N, Kw) # (N,Kw) xyz_c_n = xyz_c[back_t] # (N,Kw,3) dot = (xyz_c_n * xyz1[:, None, :]).sum(dim=-1) # (N,Kw) del xyz_c_n dot = torch.clamp(dot, -1.0, 1.0) ang = torch.acos(dot) del dot dist = radius * ang # (N,Kw) del ang # --- weights and per-pixel sum # Same default as KNeighborsResampler.__init__: when sigma is not supplied, # fall back to the HEALPix pixel scale sqrt(4*pi/(12*4**level))*R. if sigma is None: sigma = _sigma_level_m(level, radius=radius) # w = exp(-2*d^2/sigma^2) w = torch.exp((-2.0) * (dist * dist) / (sigma * sigma)) # (N,Kw) del dist # scatter_add over unique pixels # w is accumulated on each pixel (Kuniq) sums = torch.zeros((xyz_c.shape[0],), device=dev, dtype=w.dtype) # Thresholding stage: # We compute Gaussian weights from each sample to its neighbourhood pixel centers, # then accumulate a global weight sum per HEALPix cell. Only cells whose total # influence exceeds 'threshold' are kept in cell_ids_keep (size K). sums.scatter_add_(0, back_t.reshape(-1), w.reshape(-1)) del w, back_t keep = sums >= threshold if not torch.any(keep): # no pixel passes the threshold -> return empty + -1/inf cell_ids = torch.empty((0,), device=dev, dtype=torch.long) idx_k = torch.full((N, Npt), -1, device=dev, dtype=torch.long) dist_k = torch.full((N, Npt), float("inf"), device=dev, dtype=lon1.dtype) return cell_ids, idx_k, dist_k, None # kept cell_ids (HEALPix ids) cell_ids_np = neigh_w_uniq # np.uint64, size Kuniq keep_idx = torch.nonzero(keep, as_tuple=False).squeeze(1) # indices in [0..Kuniq-1] cell_ids_keep = torch.from_numpy(cell_ids_np.astype(np.int64)).to(dev)[keep_idx] # (K,) # xyz of the kept pixels (K,3) xyz_keep = xyz_c[keep_idx] # --- optional: explicitly restrict the output pixels # out_cell_ids can be a list/array/torch tensor of HEALPix ids (at the same level). if out_cell_ids is not None: out_t = out_cell_ids if isinstance(out_cell_ids, torch.Tensor) else torch.as_tensor(out_cell_ids) out_t = out_t.to(device=dev, dtype=torch.long).reshape(-1) if out_t.numel() == 0: # empty subset requested -> nothing to regrid cell_ids = torch.empty((0,), device=dev, dtype=torch.long) idx_k = torch.full((N, Npt), -1, device=dev, dtype=torch.long) dist_k = torch.full((N, Npt), float("inf"), device=dev, dtype=lon1.dtype) return cell_ids, idx_k, dist_k, None out_sorted = torch.unique(out_t) out_sorted, _ = torch.sort(out_sorted) # robust membership test via searchsorted (avoids depending on torch.isin) pos_out = torch.searchsorted(out_sorted, cell_ids_keep) pos_out = torch.clamp(pos_out, 0, out_sorted.numel() - 1) in_mask = (out_sorted[pos_out] == cell_ids_keep) if not torch.any(in_mask): cell_ids = torch.empty((0,), device=dev, dtype=torch.long) idx_k = torch.full((N, Npt), -1, device=dev, dtype=torch.long) dist_k = torch.full((N, Npt), float("inf"), device=dev, dtype=lon1.dtype) return cell_ids, idx_k, dist_k, None keep_idx = keep_idx[in_mask] cell_ids_keep = cell_ids_keep[in_mask] xyz_keep = xyz_c[keep_idx] # --- for each point: find the Npt nearest kept pixels # Strategy: HEALPix neighbourhood around the pixel containing the point, with a growing ring. # Neighbourhood pixels are mapped to indices in cell_ids_keep via sort + searchsorted. cell_sorted, order = torch.sort(cell_ids_keep) # (K,), (K,) K = int(cell_ids_keep.numel()) idx_out = torch.full((N, Npt), -1, device=dev, dtype=torch.long) dist_out = torch.full((N, Npt), float("inf"), device=dev, dtype=lon1.dtype) r = ring_search_init done = torch.zeros((N,), device=dev, dtype=torch.bool) tied_rows, tied_idx, tied_dist = [], [], [] # The samples searched at a ring: all of them at the first ring, then only # the ones not served yet (``todo``: their indices). A sample is served at # the first ring where it finds Npt kept pixels, and its result depends on # its own candidates only, so the served samples need not be searched # again at the wider rings. (With ``out_cell_ids``, the few samples next # to the requested cells whose nearest pixels are not requested used to # send every sample through every ring, with (N, (2r+1)**2) temporaries # at each ring, kept alive until the next ring had its own.) todo = None ipix_u64 = ipix1.astype(np.uint64, copy=False) # kth_neighbourhood runs on the CPU, but only for the rings that are needed. # It is computed on unique pixels to limit the number of calls. while r <= ring_search_max and not bool(torch.all(done).item()): if r == ring_search_init: ipu, inv_r, xyz1_r = ipix_u, inv, xyz1 else: todo = torch.nonzero(~done, as_tuple=False).squeeze(1) # (T,) ipu, inv_r = np.unique(ipix_u64[todo.cpu().numpy()], return_inverse=True) xyz1_r = xyz1[todo] # (T,3) if nest: neigh_u = healpix_geo.nested.kth_neighbourhood(ipu, level, r, num_threads=num_threads) else: neigh_u = healpix_geo.ring.kth_neighbourhood(ipu, level, r, num_threads=num_threads) neigh = neigh_u[inv_r] # (T, Ks) Ks = neigh.shape[1] neigh_t = torch.from_numpy(neigh.astype(np.int64)).to(dev) del neigh_u, neigh # map neigh_t -> index in cell_ids_keep pos = torch.searchsorted(cell_sorted, neigh_t) pos = torch.clamp(pos, 0, K - 1) hit = (cell_sorted[pos] == neigh_t) cand_idx_keep = torch.where(hit, order[pos], torch.full_like(pos, -1)) # indices in cell_ids_keep del neigh_t, pos, hit # distances for the valid candidates safe = torch.clamp(cand_idx_keep, 0, K - 1) xyz2 = xyz_keep[safe] # (T,Ks,3) del safe dist2 = _arc_distance(xyz2, xyz1_r[:, None, :], radius) del xyz2 dist2 = torch.where(cand_idx_keep >= 0, dist2, torch.full_like(dist2, float("inf"))) # the k nearest among these candidates, plus the cells tied with the k-th k = min(Npt, Ks) d_k, i_k, d_x, i_x = _nearest_with_ties(dist2, cand_idx_keep, k) del dist2, cand_idx_keep # points are accepted once they have at least Npt valid neighbours (i.e. d_k[:, Npt-1] < inf) valid_enough = (d_k[:, -1] < float("inf")) served = valid_enough if todo is None else todo[valid_enough] if torch.any(valid_enough): idx_out[served] = i_k[valid_enough] dist_out[served] = d_k[valid_enough] done[served] = True # tied extra links of the served samples (rows of the searched # subset, mapped back to sample indices) rows = torch.nonzero(valid_enough & (i_x >= 0).any(dim=1)).squeeze(1) if rows.numel(): tied_rows.append(rows if todo is None else todo[rows]) tied_idx.append(i_x[rows]) tied_dist.append(d_x[rows]) r += 1 # Points that never found Npt kept pixels within ring_search_max rings keep # the ones they found at the last (widest) ring, padded with -1/inf. Dropping # them all instead left every sample without a link when the samples are # much sparser than the cells, and the operator then came out empty (#74). # (d_k, i_k, k and valid_enough are those of the last ring, over the # samples searched at that ring: all of them, or ``todo``.) partial = ~done if torch.any(partial): found = torch.isfinite(d_k) rows = partial if todo is None else ~valid_enough idx_out[partial, :k] = torch.where(found, i_k, torch.full_like(i_k, -1))[rows] dist_out[partial, :k] = d_k[rows] return cell_ids_keep, idx_out, dist_out, _flatten_ties(tied_rows, tied_idx, tied_dist) def _ring_window(r: int) -> tuple[np.ndarray, np.ndarray]: """Offsets ``(di, dj)`` of the ``(2r+1)**2`` cells within ``r`` rings.""" d = np.arange(-r, r + 1) di, dj = np.meshgrid(d, d, indexing="ij") return di.ravel(), dj.ravel() def _spread_bits(v: torch.Tensor) -> torch.Tensor: """The bits of ``v`` (< 2**32) at the even positions of an int64.""" v = v & 0xFFFFFFFF v = (v | (v << 16)) & 0x0000FFFF0000FFFF v = (v | (v << 8)) & 0x00FF00FF00FF00FF v = (v | (v << 4)) & 0x0F0F0F0F0F0F0F0F v = (v | (v << 2)) & 0x3333333333333333 return (v | (v << 1)) & 0x5555555555555555 def _on_device(dev: torch.device) -> bool: """Whether the coarse search builds the neighbourhoods inside the faces on ``dev`` (CUDA) rather than with ``healpix_geo`` on the CPU.""" return dev.type == "cuda" def _base_cell_coordinates_to_nested( face: torch.Tensor, i: torch.Tensor, j: torch.Tensor, level: int ) -> torch.Tensor: """``healpix_geo.nested.base_cell_coordinates_to_healpix`` in torch (on any device): the nested id is the face number followed by the bits of ``j`` and ``i`` interleaved.""" return (face << (2 * level)) | (_spread_bits(j) << 1) | _spread_bits(i) def _coarse_weighted_nearest( longitude1: torch.Tensor, latitude1: torch.Tensor, *, level: int, Npt: int, k: int, threshold: float, radius: float, ellipsoid: str, sigma: float | None, out_cell_ids, ring_weight: int, ring_search_init: int, ring_search_max: int, num_threads: int, dev: torch.device, batch_size: int, ): """:func:`healpix_weighted_nearest` with the cell table and the neighbourhoods built from the nested structure (``coarse_level_delta``; nested ids only, ``Npt > 1``, arguments after the defaults have been resolved). Same result as the fine search, in less time and memory. The fine search calls ``kth_neighbourhood`` for every sample pixel, gathers the ``(N, (2*ring_weight+1)**2)`` neighbour ids and their centres, and numbers the cells with a global ``np.unique`` of all those ids (a sort of ``N * 49`` ids for ``Npt = 9``). Here: - the cell table is the union of the cells ``k`` levels coarser around the samples' coarse cells (``kth_neighbourhood`` at the coarse level, on unique coarse cells only). Its fine cells are the descendants ``c * 4**k + j``, so the table index of a fine cell is ``rank(c) * 4**k + (id % 4**k)``: no global sort. The centres are computed once per table cell; - inside a base face, the cells within ``r`` rings of a cell are those at ``(i + di, j + dj)``, ``|di|, |dj| <= r``, in the face coordinates (``healpix_to_base_cell_coordinates``): their ids come from ``base_cell_coordinates_to_healpix``. The pixels within ``max(ring_weight, ring_search_max)`` cells of a face edge keep ``kth_neighbourhood`` (whose rings may cross into other faces); - everything per sample (ids, distances, weights) is computed in batches of ``batch_size`` samples. The neighbourhoods, distances, weights, threshold, rings and ties are those of the fine search, so the result is the same. Returns ``(cell_ids, idx_k, dist_k, ties)`` as `_healpix_weighted_nearest`. """ N = int(longitude1.numel()) nside = 1 << level nsub = 4**k R = max(ring_weight, ring_search_max) lon_np = longitude1.detach().cpu().numpy().astype(np.float64) lat_np = latitude1.detach().cpu().numpy().astype(np.float64) ipix = healpix_geo.nested.lonlat_to_healpix( lon_np, lat_np, level, num_threads=num_threads, ellipsoid=ellipsoid ).astype(np.uint64) face, fi, fj = healpix_geo.nested.healpix_to_base_cell_coordinates(ipix, level, num_threads=num_threads) fi, fj = fi.astype(np.int64), fj.astype(np.int64) edge = (np.minimum(fi, fj) < R) | (np.maximum(fi, fj) >= nside - R) # on a GPU, the neighbourhoods inside the faces are computed there (the # same ids as healpix_geo's) on_dev = _on_device(dev) if on_dev: face_t = torch.from_numpy(face.astype(np.int64)).to(dev) fi_t, fj_t = torch.from_numpy(fi).to(dev), torch.from_numpy(fj).to(dev) # --- cell table: the coarse cells within rc coarse rings of the samples' # coarse cells cover every neighbourhood (rc * 2**k >= R + 2**k: the # sample may lie anywhere in its coarse cell; one more ring for the # irregular neighbourhoods at the face corners) coarse = (ipix >> np.uint64(2 * k)).astype(np.int64) uc = np.unique(coarse) rc = -(-R // 2**k) + 1 nb = healpix_geo.nested.kth_neighbourhood(uc.astype(np.uint64), level - k, rc, num_threads=num_threads) V = np.unique(nb[nb >= 0].astype(np.int64)) # sorted coarse cells del nb, uc fine = (V[:, None] * nsub + np.arange(nsub)[None, :]).reshape(-1) # ascending flon, flat = healpix_geo.nested.healpix_to_lonlat(fine.astype(np.uint64), level, ellipsoid=ellipsoid) xyz_f = _lonlat_to_xyz( torch.deg2rad(torch.from_numpy(np.asarray(flon)).to(dev)), torch.deg2rad(torch.from_numpy(np.asarray(flat)).to(dev)), ) del flon, flat V_t = torch.from_numpy(V).to(dev) xyz1 = _lonlat_to_xyz(torch.deg2rad(longitude1.to(dev)), torch.deg2rad(latitude1.to(dev))) def table_index(ids) -> torch.Tensor: """Table index of fine cell ids (-1 stays -1).""" if isinstance(ids, torch.Tensor): ids_t = ids else: ids_t = torch.from_numpy(ids.astype(np.int64)).to(dev) valid = ids_t >= 0 c = torch.where(valid, ids_t >> (2 * k), torch.zeros_like(ids_t)) pos = torch.searchsorted(V_t, c) pos_c = torch.clamp(pos, 0, V_t.numel() - 1) if not bool(torch.all(~valid | (V_t[pos_c] == c))): raise RuntimeError("coarse_level_delta: a neighbourhood cell is outside the cell table") return torch.where(valid, pos_c * nsub + (ids_t & (nsub - 1)), torch.full_like(ids_t, -1)) def window(rows: np.ndarray, r: int) -> np.ndarray: """Ids of the cells within r rings of the pixels of the samples ``rows``, as the fine search gets them (-1: no cell).""" out = np.empty((rows.size, (2 * r + 1) ** 2), dtype=np.int64) e = edge[rows] if (~e).any(): ri = rows[~e] di, dj = _ring_window(r) ii = (fi[ri, None] + di[None, :]).astype(np.uint32) jj = (fj[ri, None] + dj[None, :]).astype(np.uint32) ff = np.broadcast_to(face[ri, None], ii.shape).astype(np.uint8) out[~e] = healpix_geo.nested.base_cell_coordinates_to_healpix( ff.ravel(), ii.ravel(), jj.ravel(), level, num_threads=num_threads ).reshape(ii.shape).astype(np.int64) if e.any(): out[e] = healpix_geo.nested.kth_neighbourhood( ipix[rows[e]], level, r, num_threads=num_threads ).astype(np.int64) return out def window_dev(rows: np.ndarray, r: int, fill: bool) -> torch.Tensor: """``window`` (then ``_fill_invalid_neighbours`` if ``fill``) on the device: the pixels inside their face there, the others (whose rings may cross into other faces) with ``kth_neighbourhood``.""" out = torch.empty((rows.size, (2 * r + 1) ** 2), dtype=torch.long, device=dev) e = edge[rows] if (~e).any(): inner = torch.from_numpy(~e).to(dev) ri = torch.from_numpy(rows[~e]).to(dev) di, dj = (torch.from_numpy(a.astype(np.int64)).to(dev) for a in _ring_window(r)) out[inner] = _base_cell_coordinates_to_nested( face_t[ri, None], fi_t[ri, None] + di[None, :], fj_t[ri, None] + dj[None, :], level ) if e.any(): nb = healpix_geo.nested.kth_neighbourhood( ipix[rows[e]], level, r, num_threads=num_threads ).astype(np.int64) if fill: nb = _fill_invalid_neighbours(nb, ipix[rows[e]]) out[torch.from_numpy(e).to(dev)] = torch.from_numpy(nb).to(dev) return out if sigma is None: sigma = _sigma_level_m(level, radius=radius) # --- threshold stage (as the fine search: the -1 entries of a # neighbourhood are replaced by its last valid cell, and counted) sums = torch.zeros(fine.size, device=dev, dtype=torch.float64) for s in range(0, N, batch_size): rows = np.arange(s, min(N, s + batch_size)) if on_dev: nbw = window_dev(rows, ring_weight, fill=True) else: nbw = _fill_invalid_neighbours(window(rows, ring_weight), ipix[rows]) idx = table_index(nbw) dot = torch.clamp((xyz_f[idx] * xyz1[s:s + rows.size, None, :]).sum(dim=-1), -1.0, 1.0) dist = radius * torch.acos(dot) w = torch.exp((-2.0) * (dist * dist) / (sigma * sigma)) sums.scatter_add_(0, idx.reshape(-1), w.reshape(-1)) del nbw, idx, dot, dist, w keep = sums >= threshold del sums if out_cell_ids is not None: out_t = out_cell_ids if isinstance(out_cell_ids, torch.Tensor) else torch.as_tensor(out_cell_ids) out_np = np.unique(out_t.detach().cpu().numpy().astype(np.int64).reshape(-1)) keep &= torch.from_numpy(np.isin(fine, out_np)).to(dev) if not torch.any(keep): return ( torch.empty((0,), device=dev, dtype=torch.long), torch.full((N, Npt), -1, device=dev, dtype=torch.long), torch.full((N, Npt), float("inf"), device=dev, dtype=torch.float64), None, ) cell_ids_keep = torch.from_numpy(fine).to(dev)[keep] # ascending rank = torch.where(keep, torch.cumsum(keep.to(torch.long), 0) - 1, torch.full_like(keep, -1, dtype=torch.long)) # --- search stage: growing rings, the unserved samples only (as the fine # search) idx_out = torch.full((N, Npt), -1, device=dev, dtype=torch.long) dist_out = torch.full((N, Npt), float("inf"), device=dev, dtype=torch.float64) tied_rows, tied_idx, tied_dist = [], [], [] todo = np.arange(N) r = ring_search_init while r <= ring_search_max and todo.size: served_all = [] for s in range(0, todo.size, batch_size): rows = todo[s:s + batch_size] rows_t = torch.from_numpy(rows).to(dev) ti = table_index(window_dev(rows, r, fill=False) if on_dev else window(rows, r)) cand = torch.where(ti >= 0, rank[torch.clamp(ti, min=0)], torch.full_like(ti, -1)) dist = _arc_distance(xyz_f[torch.clamp(ti, min=0)], xyz1[rows_t, None, :], radius) dist = torch.where(cand >= 0, dist, torch.full_like(dist, float("inf"))) kk = min(Npt, cand.shape[1]) d_k, i_k, d_x, i_x = _nearest_with_ties(dist, cand, kk) ok = torch.isfinite(d_k[:, -1]) & (kk == Npt) take = ok | (r == ring_search_max) if torch.any(take): found = torch.isfinite(d_k[take]) idx_out[rows_t[take], :kk] = torch.where(found, i_k[take], torch.full_like(i_k[take], -1)) dist_out[rows_t[take], :kk] = d_k[take] t = torch.nonzero(ok & (i_x >= 0).any(dim=1)).squeeze(1) if t.numel(): tied_rows.append(rows_t[t]) tied_idx.append(i_x[t]) tied_dist.append(d_x[t]) served_all.append(take.cpu().numpy()) del ti, cand, dist, d_k, i_k, d_x, i_x todo = todo[~np.concatenate(served_all)] r += 1 return cell_ids_keep, idx_out, dist_out, _flatten_ties(tied_rows, tied_idx, tied_dist) def _fill_invalid_neighbours(neigh: np.ndarray, centre: np.ndarray) -> np.ndarray: """Replace the -1 entries of a ``kth_neighbourhood`` result (rows = pixels ``centre``) by the last valid neighbour of the row, or by the centre pixel when the whole row is invalid: the same rule as the unbatched search, so the arrays stay dense and duplicates are handled by the weight sums.""" neigh = neigh.astype(np.int64, copy=False) valid = neigh >= 0 last_valid_pos = valid[:, ::-1].argmax(axis=1) last_valid_pos = (neigh.shape[1] - 1) - last_valid_pos last_valid = neigh[np.arange(neigh.shape[0]), last_valid_pos] all_invalid = ~valid.any(axis=1) last_valid[all_invalid] = centre[all_invalid].astype(np.int64, copy=False) mask = neigh < 0 neigh[mask] = np.broadcast_to(last_valid[:, None], neigh.shape)[mask] return neigh @torch.no_grad() def _healpix_weighted_nearest_batched( longitude1: torch.Tensor, latitude1: torch.Tensor, *, level: int, Npt: int, nest: bool, threshold: float, radius: float, ellipsoid: str, sigma: float | None, out_cell_ids, ring_weight: int, ring_search_init: int, ring_search_max: int, num_threads: int, dev: torch.device, batch_size: int, ) -> Tuple[torch.Tensor, torch.Tensor, torch.Tensor]: """Batched version of :func:`healpix_weighted_nearest` (same arguments, after the defaults have been resolved; ``Npt > 1``). The unbatched function holds, for every sample at once, the ``(2*ring_weight+1)**2`` neighbourhood pixels with their centre coordinates, distances and weights, and then the ``(2*r+1)**2`` candidates of the nearest search: about 1.5-2 kB per sample, so a healpix-convert chunk of 32 million samples needs more than 100 GiB. Here the samples are processed in slices of ``batch_size``: 1. the set of neighbourhood pixels (the candidates for ``cell_ids``) is built from the unique sample pixels, in slices; 2. the per-pixel weight sums used by ``threshold`` are accumulated slice by slice into one global array (``scatter_add_`` in sample order, so each pixel receives the same contributions in the same order as in the unbatched function); 3. the ``Npt``-nearest search runs slice by slice, with the ring growing until every sample of the slice is served (as before, a sample is served at the first ring where it finds ``Npt`` kept pixels, so the result of a sample does not depend on the other samples of its slice). Steps 2 and 3 therefore give the same ``cell_ids``, ``idx_k`` and ``dist_k`` as the unbatched function; the only possible difference is the floating point summation order inside ``scatter_add_``, which does not change the ``threshold`` decision except for a pixel whose weight sum is within rounding of ``threshold``. The memory of the temporaries is then about ``2 kB * batch_size`` plus the global arrays (``O(N * Npt)`` for the results and ``O(K)`` for the candidate pixels). """ N = int(longitude1.numel()) hp = healpix_geo.nested if nest else healpix_geo.ring # --- CPU numpy for healpix_geo lon_np = longitude1.detach().cpu().numpy().astype(np.float64) lat_np = latitude1.detach().cpu().numpy().astype(np.float64) ipix1 = hp.lonlat_to_healpix(lon_np, lat_np, level, num_threads=num_threads, ellipsoid=ellipsoid) ipix1 = ipix1.astype(np.uint64, copy=False) ipix_u = np.unique(ipix1) # --- 1. candidate pixels: the union of the ring_weight neighbourhoods of the # unique sample pixels, built in slices of the (sorted, hence spatially # grouped) unique pixels so that no (U, Kw) array is ever allocated. parts = [] for s in range(0, ipix_u.size, batch_size): u = ipix_u[s : s + batch_size] neigh = hp.kth_neighbourhood(u, level, ring_weight, num_threads=num_threads) neigh = neigh.astype(np.int64, copy=False) parts.append(np.unique(neigh[neigh >= 0]).astype(np.uint64)) parts.append(u) # fallback of all-invalid rows neigh_w_uniq = np.unique(np.concatenate(parts)) # sorted uint64, size Kuniq del parts Kuniq = int(neigh_w_uniq.size) lon_c_deg, lat_c_deg = hp.healpix_to_lonlat(neigh_w_uniq, level, ellipsoid=ellipsoid) lon_c = torch.deg2rad(torch.from_numpy(np.asarray(lon_c_deg)).to(dev)) lat_c = torch.deg2rad(torch.from_numpy(np.asarray(lat_c_deg)).to(dev)) xyz_c = _lonlat_to_xyz(lon_c, lat_c) # (Kuniq,3) if sigma is None: sigma = _sigma_level_m(level, radius=radius) lon1_all = torch.deg2rad(longitude1.to(dev)) lat1_all = torch.deg2rad(latitude1.to(dev)) # --- 2. per-pixel weight sums, accumulated over the slices sums = torch.zeros((Kuniq,), device=dev, dtype=torch.float64) for s in range(0, N, batch_size): e = min(N, s + batch_size) ipu_b, inv_b = np.unique(ipix1[s:e], return_inverse=True) neigh_u_w = _fill_invalid_neighbours( hp.kth_neighbourhood(ipu_b, level, ring_weight, num_threads=num_threads), ipu_b ) neigh_w = neigh_u_w[inv_b] # (b, Kw) Kw = neigh_w.shape[1] back = np.searchsorted(neigh_w_uniq, neigh_w.reshape(-1).astype(np.uint64)) back_t = torch.from_numpy(back.astype(np.int64)).to(dev).view(e - s, Kw) del neigh_u_w, neigh_w, back xyz1 = _lonlat_to_xyz(lon1_all[s:e], lat1_all[s:e]) # (b,3) dot = (xyz_c[back_t] * xyz1[:, None, :]).sum(dim=-1) # (b,Kw) dot = torch.clamp(dot, -1.0, 1.0) dist = radius * torch.acos(dot) w = torch.exp((-2.0) * (dist * dist) / (sigma * sigma)) del dot, dist sums.scatter_add_(0, back_t.reshape(-1), w.reshape(-1)) del back_t, w, xyz1 keep = sums >= threshold if not torch.any(keep): cell_ids = torch.empty((0,), device=dev, dtype=torch.long) idx_k = torch.full((N, Npt), -1, device=dev, dtype=torch.long) dist_k = torch.full((N, Npt), float("inf"), device=dev, dtype=lon1_all.dtype) return cell_ids, idx_k, dist_k, None keep_idx = torch.nonzero(keep, as_tuple=False).squeeze(1) cell_ids_keep = torch.from_numpy(neigh_w_uniq.astype(np.int64)).to(dev)[keep_idx] xyz_keep = xyz_c[keep_idx] del sums, keep # --- optional: explicitly restrict the output pixels (same as unbatched) if out_cell_ids is not None: out_t = out_cell_ids if isinstance(out_cell_ids, torch.Tensor) else torch.as_tensor(out_cell_ids) out_t = out_t.to(device=dev, dtype=torch.long).reshape(-1) if out_t.numel() == 0: cell_ids = torch.empty((0,), device=dev, dtype=torch.long) idx_k = torch.full((N, Npt), -1, device=dev, dtype=torch.long) dist_k = torch.full((N, Npt), float("inf"), device=dev, dtype=lon1_all.dtype) return cell_ids, idx_k, dist_k, None out_sorted = torch.unique(out_t) out_sorted, _ = torch.sort(out_sorted) pos_out = torch.searchsorted(out_sorted, cell_ids_keep) pos_out = torch.clamp(pos_out, 0, out_sorted.numel() - 1) in_mask = (out_sorted[pos_out] == cell_ids_keep) if not torch.any(in_mask): cell_ids = torch.empty((0,), device=dev, dtype=torch.long) idx_k = torch.full((N, Npt), -1, device=dev, dtype=torch.long) dist_k = torch.full((N, Npt), float("inf"), device=dev, dtype=lon1_all.dtype) return cell_ids, idx_k, dist_k, None keep_idx = keep_idx[in_mask] cell_ids_keep = cell_ids_keep[in_mask] xyz_keep = xyz_c[keep_idx] del xyz_c # --- 3. for each sample: the Npt nearest kept pixels, slice by slice cell_sorted, order = torch.sort(cell_ids_keep) K = int(cell_ids_keep.numel()) idx_out = torch.full((N, Npt), -1, device=dev, dtype=torch.long) dist_out = torch.full((N, Npt), float("inf"), device=dev, dtype=lon1_all.dtype) tied_rows, tied_idx, tied_dist = [], [], [] for s in range(0, N, batch_size): e = min(N, s + batch_size) b = e - s ipu_b, inv_b = np.unique(ipix1[s:e], return_inverse=True) xyz1 = _lonlat_to_xyz(lon1_all[s:e], lat1_all[s:e]) # (b,3) idx_b = idx_out[s:e] dist_b = dist_out[s:e] done = torch.zeros((b,), device=dev, dtype=torch.bool) r = ring_search_init while r <= ring_search_max and not bool(torch.all(done).item()): neigh_u = hp.kth_neighbourhood(ipu_b, level, r, num_threads=num_threads) neigh_t = torch.from_numpy(neigh_u[inv_b].astype(np.int64)).to(dev) # (b, Ks) Ks = neigh_t.shape[1] pos = torch.searchsorted(cell_sorted, neigh_t) pos = torch.clamp(pos, 0, K - 1) hit = (cell_sorted[pos] == neigh_t) cand_idx_keep = torch.where(hit, order[pos], torch.full_like(pos, -1)) del neigh_t, pos, hit safe = torch.clamp(cand_idx_keep, 0, K - 1) dist2 = _arc_distance(xyz_keep[safe], xyz1[:, None, :], radius) del safe dist2 = torch.where(cand_idx_keep >= 0, dist2, torch.full_like(dist2, float("inf"))) k = min(Npt, Ks) d_k, i_k, d_x, i_x = _nearest_with_ties(dist2, cand_idx_keep, k) del dist2, cand_idx_keep valid_enough = (d_k[:, -1] < float("inf")) update = (~done) & valid_enough if torch.any(update): idx_b[update] = i_k[update] dist_b[update] = d_k[update] done[update] = True rows = torch.nonzero(update & (i_x >= 0).any(dim=1)).squeeze(1) if rows.numel(): tied_rows.append(rows + s) tied_idx.append(i_x[rows]) tied_dist.append(d_x[rows]) r += 1 partial = ~done if torch.any(partial): found = torch.isfinite(d_k) idx_b[partial, :k] = torch.where(found, i_k, torch.full_like(i_k, -1))[partial] dist_b[partial, :k] = d_k[partial] return cell_ids_keep, idx_out, dist_out, _flatten_ties(tied_rows, tied_idx, tied_dist)
[docs] class KNeighborsResampler(Generic[T_Array]): """GPU-friendly sparse HEALPix regridding via local Gaussian weights + CG deconvolution. This class builds two sparse operators from unstructured lon/lat samples to a subset of HEALPix pixels at a target resolution (nside = 2**level). Notation (matching your notebook): - N: number of samples (lon/lat) - K: number of kept HEALPix cells (cell_ids) - M: operator of shape (N, K) (named ``M`` here) - MT: operator of shape (K, N) (named ``MT`` here) The solver estimates ``hval`` (B,K) such that ``M @ hval.T`` matches ``val`` (B,N), by solving a damped normal equation around a reference field ``x_ref = val @ M``. """
[docs] def __init__( self, lon_deg: T_Array, lat_deg: T_Array, Npt: int, level: int, *, nest: bool = True, radius: float = 6371000.0, ellipsoid: str = "WGS84", dtype: torch.dtype = torch.float64, device: torch.device | str | None = None, ring_weight: Optional[int] = None, ring_search_init: Optional[int] = None, ring_search_max: int = 2, num_threads: int = 0, threshold: float = 0.1, sigma_m: float | None = None, verbose: bool = True, out_cell_ids: T_Array | None = None, group_by: bool = False, batch_size: int | None = None, coarse_level_delta: int | None = None, neighbours: Optional["NeighbourLinks"] = None, ) -> None: """Pre-compute sparse operators. Args: lon_deg, lat_deg: unstructured sample coordinates in degrees, shape (N,); float32 or float64, the geometry is computed in float64 Npt: number of nearest HEALPix cells used per sample. A sample that does not find Npt kept cells within ``ring_search_max`` rings (samples much sparser than the cells) keeps the ones it found. ring_search_init, ring_search_max: first and last HEALPix ring of the per-sample neighbour search; a ``ring_search_max`` below ``ring_search_init`` is raised to it level: HEALPix level, nside = 2**level sigma_m: Gaussian length scale (meters). If None, uses the HEALPix pixel scale sigma = sqrt(4*pi/(12*4**level))*R. threshold: keep only HEALPix cells whose global weight sum >= threshold nest: HEALPix indexing scheme dtype/device: torch dtype/device for all matrices and computations out_cell_ids: optional subset of ``level`` cells to restrict the output to (e.g. one chunk or one parent cell). If none of these cells has enough support among the samples, the operator is built with ``K = 0`` instead of raising: ``resample()`` then returns ``cell_ids`` of size 0 and ``cell_data`` of shape ``(B, 0)``, except ``NearestResampler``, whose fallback fills the requested cells with their nearest sample (see its ``max_distance_m``). batch_size: process the samples in slices of this size when building the operators (see ``healpix_weighted_nearest``): the temporary memory of the neighbour search is then about 2 kB per sample of a slice instead of 2 kB per sample. ``None`` (default) processes all samples at once. The result is the same. coarse_level_delta: number the cells of the neighbour search from their parents this many levels coarser (nested only; see ``healpix_weighted_nearest``): the same cells, neighbours and ties as the fine-level search, in less time and memory. ``None`` (default): the fine-level search. neighbours: the links (`NeighbourLinks`) of an earlier resampler on the same samples, level and search parameters (its ``neighbours`` attribute): the neighbour search is skipped and the distances computed again, so the resampler is the same, bit for bit. With ``Npt=1`` it is ignored. Raises: RuntimeError: without ``out_cell_ids``, when no cell passes ``threshold`` (lower ``threshold`` or widen the neighbourhood rings), or when cells pass it but no sample reaches any of them within ``ring_search_max`` rings. """ self.level = int(level) self.nside = 2 ** int(level) self.group_by = bool(group_by) if not self.group_by: self.Npt = int(Npt) self.nest = bool(nest) self.radius = float(radius) self.ellipsoid = str(ellipsoid) self.dtype = dtype if device is None: device = "cuda" if torch.cuda.is_available() else "cpu" else: # device may already be a torch.device (e.g. passed through from # another resampler's .device attribute) rather than a string -- # only str has .startswith(). Same guard already used in # clough_tocher.py's equivalent constructor. if isinstance(device, str) and device.startswith("cuda") and not torch.cuda.is_available(): raise RuntimeError("CUDA requested but not available.") self.device = torch.device(device) self.threshold = float(threshold) self.out_cell_ids = out_cell_ids self.batch_size = None if batch_size is None else int(batch_size) # --- sigma in meters (controls the Gaussian weights used for thresholding) sigma = float(_sigma_level_m(level, radius=radius) if sigma_m is None else sigma_m) self.sigma_m = sigma self.verbose = verbose # --- move lon/lat to torch on target device (but healpix_geo needs CPU numpy internally) lon_t = lon_deg if isinstance(lon_deg, torch.Tensor) else torch.as_tensor(lon_deg) lat_t = lat_deg if isinstance(lat_deg, torch.Tensor) else torch.as_tensor(lat_deg) # Links to the cells tied with a sample's Npt-th nearest one (see # `_nearest_with_ties`): flat sample / cell index / distance, a few per # million samples, kept apart so that `hi` / `d_m` stay (N, Npt). self.tie_rows = torch.empty((0,), dtype=torch.long, device=self.device) self.tie_hi = torch.empty((0,), dtype=torch.long, device=self.device) self.tie_d = torch.empty((0,), dtype=self.dtype, device=self.device) if self.group_by: if self.nest: cell_ids = healpix_geo.nested.lonlat_to_healpix(lon_t,lat_t, self.level, ellipsoid=self.ellipsoid) else: cell_ids = healpix_geo.ring.lonlat_to_healpix(lon_t,lat_t, self.level, ellipsoid=self.ellipsoid) cell_ids,hi = torch.unique(torch.tensor(cell_ids,dtype=torch.long,device=self.device), return_inverse=True) self.cell_ids = cell_ids self.hi = hi else: # float64 geometry, whatever the dtype of the input coordinates (#73) lon_t = lon_t.to(self.device, dtype=torch.float64) lat_t = lat_t.to(self.device, dtype=torch.float64) if self.out_cell_ids is not None: self.xyz_samples = _lonlat_to_xyz(torch.deg2rad(lon_t),torch.deg2rad(lat_t)) # (N,3) # --- get kept healpix cells + per-sample nearest indices + distances if neighbours is not None and Npt > 1: # the links of an earlier search on the same geometry: only # their distances are computed (as the search does) if neighbours.hi.shape != (lon_t.numel(), self.Npt): raise ValueError( f"neighbours: links of {tuple(neighbours.hi.shape)} for " f"{lon_t.numel()} samples and Npt={self.Npt}" ) cell_ids = neighbours.cell_ids.to(self.device) hi = neighbours.hi.to(self.device) d, tie_d = link_distances( lon_t, lat_t, neighbours, level=self.level, nest=self.nest, ellipsoid=self.ellipsoid, radius=self.radius, ) ties = (neighbours.tie_rows.to(self.device), neighbours.tie_hi.to(self.device), tie_d) else: cell_ids, hi, d, ties = healpix_weighted_nearest( lon_t, lat_t, level=self.level, Npt=self.Npt, nest=self.nest, threshold=self.threshold, radius=self.radius, ellipsoid=self.ellipsoid, sigma=self.sigma_m, out_cell_ids=self.out_cell_ids, ring_weight=ring_weight, ring_search_init=ring_search_init, ring_search_max=ring_search_max, num_threads=num_threads, device_for_dist=self.device, batch_size=self.batch_size, coarse_level_delta=coarse_level_delta, return_ties=True, ) if Npt > 1: self.neighbours = NeighbourLinks(cell_ids, hi, ties[0], ties[1]) # With `out_cell_ids`, an empty result is a legitimate outcome: none of # the requested cells has enough support among the samples (e.g. a # chunk at the edge of the input whose nearby samples all lie just # outside it). The operator is then built with K = 0 and every # resampler handles the requested cells as it does any unsupported # cell. Without `out_cell_ids` every sample supports its own cell, so # an empty result means the threshold or the rings are wrong. if cell_ids.numel() == 0 and self.out_cell_ids is None: raise RuntimeError( "No HEALPix cell passed the threshold. " "Lower 'threshold' or increase neighbourhood rings." ) # Store geometry outputs self.cell_ids = cell_ids.to(torch.long).to(self.device) # (K,) self.hi = hi.to(torch.long).to(self.device) # (N,Npt) indices into cell_ids if Npt>1: self.d_m = d.to(self.dtype).to(self.device) # (N,Npt) meters self.tie_rows = ties[0].to(torch.long).to(self.device) self.tie_hi = ties[1].to(torch.long).to(self.device) self.tie_d = ties[2].to(self.dtype).to(self.device) # --- prune retained cells with zero actual sample links ----- # `healpix_weighted_nearest` decides which cells to *retain* # (self.cell_ids) via a wide-radius (`ring_weight`) accumulated # weight-sum threshold test, but separately searches each # sample's own nearest `Npt` cells *among the retained set* # using a different, narrower `ring_search_init`/ # `ring_search_max` radius. These two criteria are not # guaranteed consistent: a cell can pass the wide-radius # threshold test via many samples' small individual # contributions while never actually being one of any single # sample's own `Npt`-nearest retained cells. Such a cell ends # up with zero (i, k) links in `self.hi` -- an entirely empty # column once `comp_matrix()` builds the sparse `M`/`MT` -- so # every resampler built on this class silently returns exactly # `0.0` for it, for *any* input value (not just NaN). This was # tracked down from the "all-NaN input produces some non-NaN # cells" report in `planning/03_bilinear_nan_investigation.md` # -- confirmed by direct investigation to be this, not a # CSR/COO sparse-matmul NaN-propagation bug (both formats # agree exactly, since neither has any stored entry for these # columns to begin with). # # Only prune in the default (`out_cell_ids=None`) # auto-discovery mode: if the caller explicitly requested a # specific cell subset via `out_cell_ids`, don't silently drop # any of it here. `PSFResampler` already has its own # fallback-fill mechanism for weakly-supported `out_cell_ids` # columns (see `psf.py:comp_matrix`'s `bad_k` handling); other # resamplers' `out_cell_ids` gap is a separate, pre-existing # limitation out of scope for this fix. if self.out_cell_ids is None: K_before = int(self.cell_ids.numel()) reachable = torch.zeros(K_before, dtype=torch.bool, device=self.device) valid_hi = self.hi[self.hi >= 0] if valid_hi.numel() > 0: reachable[valid_hi] = True reachable[self.tie_hi] = True n_orphaned = int((~reachable).sum()) if n_orphaned > 0: if self.verbose: print( f"[KNeighborsResampler] dropping {n_orphaned:,} retained " f"cell(s) that passed the wide-neighbourhood 'threshold' " f"test but were never selected by any sample's own " f"Npt-nearest search (would otherwise silently read back " f"as 0.0 for any input)." ) new_index = torch.full((K_before,), -1, dtype=torch.long, device=self.device) new_index[reachable] = torch.arange( int(reachable.sum()), device=self.device ) self.cell_ids = self.cell_ids[reachable] self.hi = torch.where( self.hi >= 0, new_index[self.hi.clamp(min=0)], self.hi ) self.tie_hi = new_index[self.tie_hi] # Cells passed the threshold, but no sample reached any of # them: an empty operator would be returned silently (#74). if self.cell_ids.numel() == 0: raise RuntimeError( f"{K_before:,} HEALPix cell(s) passed the threshold, but no " f"sample found any of them within ring_search_max rings. " f"Increase 'ring_search_max' or use a coarser 'level'." ) self.K = int(self.cell_ids.numel()) self.N = int(lon_t.numel()) if self.out_cell_ids is not None: # --- geometry buffers for optional fallbacks (e.g. when out_cell_ids forces empty columns) # unit vectors for output HEALPix cell centers (K,3) cell_np = self.cell_ids.detach().cpu().numpy().astype(np.uint64) if self.nest: lon_c_deg, lat_c_deg = healpix_geo.nested.healpix_to_lonlat(cell_np, self.level, ellipsoid=self.ellipsoid) else: lon_c_deg, lat_c_deg = healpix_geo.ring.healpix_to_lonlat(cell_np, self.level, ellipsoid=self.ellipsoid) lon_c = torch.deg2rad(torch.as_tensor(lon_c_deg, device=self.device, dtype=self.xyz_samples.dtype)) lat_c = torch.deg2rad(torch.as_tensor(lat_c_deg, device=self.device, dtype=self.xyz_samples.dtype)) self.xyz_cells = _lonlat_to_xyz(lon_c, lat_c) # (K,3) if not self.group_by: self.comp_matrix()
# ------------------------------------------------------------------ # Sparse operators M (N,K), MT (K,N), M_cons (N,K) # # `comp_matrix()` only builds `M`, the operator `resample()` uses, and # builds it in CSC layout: `val @ M` runs over the cells, so torch # transposes a CSR `M` to CSC on every call (a full sort of the N*Npt # links, ~200 B per sample of temporaries, several seconds); stored in # CSC it is a plain spMM. The links come out of the neighbour search # one row per sample, so the per-cell normalisation is a bincount and # the CSC order is one stable argsort of the cell indices -- no # (2, N*Npt) COO index tensor and no `coalesce()`. When every sample has # Npt links (the dense case) the sorted arrays are reused as views and # normalised in place, so the construction holds ~4 arrays of N*Npt. # # `MT` (used by `invert()` and the CG solvers) and `M_cons` (used by # `resample(conservative=True)`) are built on first access and cached, # so a caller that only interpolates never pays for them. All three are # identical, entry by entry, to the former eager COO -> coalesce -> CSR # construction (same links, same values; `M` differs only in layout). # # The links to cells tied with a sample's Npt-th nearest one (`tie_rows`, # `tie_hi`, `tie_d`: a few per million samples) are kept out of the # (N, Npt) arrays, so ties do not change this path: they are added to the # per-cell sums and inserted into the CSC arrays at the end # (`_insert_tied_links`), and appended to the COO links of `MT` / `M_cons`. # # Subclasses customise the weights through `_distance_weights()` (or # `_all_link_weights()`), `_norm_col()` and `_norm_row()` rather than # overriding `comp_matrix()`. # ------------------------------------------------------------------ def _distance_weights(self, d: torch.Tensor, rows: Optional[torch.Tensor] = None) -> torch.Tensor: """Raw (unnormalised) weight of links at distances ``d`` (metres). ``d`` is either ``self.d_m`` (``(N, Npt)``, ``rows`` None) or the distances of the tied links (``rows``: their samples). Gaussian ``exp(-2 d^2 / sigma^2)`` here; ``BilinearResampler`` and ``BicubicResampler`` override it. """ return torch.exp((-2.0) * (d * d) / (self.sigma_m * self.sigma_m)) def _link_weights(self) -> torch.Tensor: """Raw (unnormalised) weight of every (sample, cell) link of ``hi``, ``(N, Npt)``. Entries where ``self.hi < 0`` (sample found fewer than Npt cells) are ignored by the callers. """ return self._distance_weights(self.d_m) def _tie_weights(self) -> torch.Tensor: """Raw weight of every tied link (``tie_rows`` / ``tie_hi``), ``(T,)``.""" return self._distance_weights(self.tie_d, self.tie_rows) def _all_link_weights(self): """``(_link_weights(), _tie_weights())``; a subclass whose weights depend on all the links of a cell (``BicubicResampler``) overrides this.""" return self._link_weights(), self._tie_weights() def _norm_col(self, cols: torch.Tensor, w: torch.Tensor, tie_cols: Optional[torch.Tensor] = None, tie_w: Optional[torch.Tensor] = None) -> torch.Tensor: """Per-cell weight sum ``(K,)`` that `M`'s columns are divided by (over the links ``cols`` / ``w`` and, if given, the tied links).""" norm = torch.bincount(cols, weights=w, minlength=self.K) if tie_cols is not None and tie_cols.numel(): # added after the other links of the cell, as one pass over all # the links would (same rounding as the eager construction) norm.index_add_(0, tie_cols, tie_w.to(norm.dtype)) return norm.to(self.dtype) def _norm_row(self, rows: torch.Tensor, w: torch.Tensor) -> torch.Tensor: """Per-sample weight sum ``(N,)`` that `MT`'s / `M_cons`'s rows are divided by.""" return torch.bincount(rows, weights=w, minlength=self.N).to(self.dtype) def _sorted_links(self, w: Optional[torch.Tensor] = None): """Valid links of ``hi`` in row-major order (by sample, cells sorted within a sample); ``w``: their raw weights (default `_link_weights()`). Returns ``(cols, w, counts, duplicated)``: cell index and raw weight of every valid link (flat, ``N*Npt`` long when every sample has Npt links -- then views of the sorted ``(N, Npt)`` arrays), the number of valid links per sample ``(N,)`` or ``None`` when all equal Npt, and whether some sample links the same cell twice (then the order is not coalesced and the caller falls back to COO). The tied links are not included (see `_insert_tied_links`). """ hi_s, perm = torch.sort(self.hi, dim=1) w_s = torch.gather(self._link_weights() if w is None else w, 1, perm) del perm valid = hi_s >= 0 duplicated = bool(((hi_s[:, 1:] == hi_s[:, :-1]) & valid[:, 1:]).any()) if bool(valid.all()): return hi_s.reshape(-1), w_s.reshape(-1), None, duplicated counts = valid.sum(dim=1) cols = hi_s[valid] del hi_s w = w_s[valid] return cols, w, counts, duplicated def _flat_links(self): """Valid links in neighbour-search order (``hi.reshape(-1)``), as the eager construction enumerated them, then the tied links: ``(rows, cols, w)``.""" w, w_tie = self._all_link_weights() flat_hi = self.hi.reshape(-1) valid = flat_hi >= 0 rows = torch.arange(self.N, device=self.device, dtype=torch.long)[:, None].expand(self.hi.shape).reshape(-1)[valid] cols, w = flat_hi[valid], w.reshape(-1)[valid] if self.tie_rows.numel(): rows = torch.cat([rows, self.tie_rows]) cols = torch.cat([cols, self.tie_hi]) w = torch.cat([w, w_tie]) return rows, cols, w def _csr_from_coo(self, rows: torch.Tensor, cols: torch.Tensor, vals: torch.Tensor, shape) -> torch.Tensor: return torch.sparse_coo_tensor( torch.stack([rows, cols], dim=0), vals.to(self.dtype), size=shape, device=self.device, dtype=self.dtype, ).coalesce().to_sparse_csr() def _insert_tied_links(self, ccol, rows, vals, tie_vals): """Insert the tied links (``tie_rows`` / ``tie_hi``, values ``tie_vals``) into the CSC arrays ``(ccol, rows, vals)`` built from ``hi``, keeping the rows of every column sorted. Only the few columns with a tied link are searched; the large arrays are copied once.""" T = int(self.tie_rows.numel()) if T == 0: return ccol, rows, vals N = self.N key = self.tie_hi * N + self.tie_rows # (column, row) order order = torch.argsort(key) t_cols, t_rows, t_vals, key = self.tie_hi[order], self.tie_rows[order], tie_vals[order], key[order] # the entries of the columns that hold a tied link, as (column, row) keys cols_u = torch.unique(t_cols) lens = ccol[cols_u + 1] - ccol[cols_u] seg_start = torch.repeat_interleave(ccol[cols_u], lens) seg_offset = torch.arange(int(lens.sum()), device=rows.device) - torch.repeat_interleave( torch.cumsum(lens, 0) - lens, lens) seg_keys = torch.repeat_interleave(cols_u, lens) * N + rows[seg_start + seg_offset] # position of each tied link in the old arrays: start of its column plus # the entries of that column with a smaller row before = torch.searchsorted(seg_keys, key) - torch.searchsorted(seg_keys, t_cols * N) pos = ccol[t_cols] + before new_idx = pos + torch.arange(T, device=rows.device) # ties are in (column, row) order L = rows.numel() keep = torch.ones(L + T, dtype=torch.bool, device=rows.device) keep[new_idx] = False new_rows = torch.empty(L + T, dtype=rows.dtype, device=rows.device) new_vals = torch.empty(L + T, dtype=vals.dtype, device=vals.device) new_rows[keep] = rows new_vals[keep] = vals new_rows[new_idx] = t_rows new_vals[new_idx] = t_vals.to(vals.dtype) new_ccol = ccol.clone() new_ccol[1:] += torch.cumsum(torch.bincount(t_cols, minlength=self.K), 0) return new_ccol, new_rows, new_vals def comp_matrix(self): """Build ``self.M`` (N,K), sparse CSC: links weighted by `_link_weights()` (and the tied links by `_tie_weights()`), normalised per cell (column). ``MT`` and ``M_cons`` are built lazily.""" self._MT = None self._M_cons = None w_links, w_tie = self._all_link_weights() cols, w, counts, duplicated = self._sorted_links(w_links) del w_links if duplicated: # A sample linking the same cell twice: `coalesce()` adds the two # weights; keep that behaviour on this (unseen in practice) path. del cols, w, counts rows, cols, w = self._flat_links() norm_col = self._norm_col(cols, w) self.M = self._csr_from_coo(rows, cols, _safe_normalize(w, norm_col[cols]), (self.N, self.K)).to_sparse_csc() return norm_col = self._norm_col(cols, w, self.tie_hi, w_tie) # per-cell normalisation (0 where every weight of the cell underflowed) w = _safe_normalize(w.to(self.dtype), norm_col[cols]) tie_vals = _safe_normalize(w_tie.to(self.dtype), norm_col[self.tie_hi]) del norm_col ccol = torch.zeros(self.K + 1, dtype=torch.long, device=self.device) torch.cumsum(torch.bincount(cols, minlength=self.K), 0, out=ccol[1:]) perm = torch.argsort(cols, stable=True) # row-major -> column-major del cols vals = w[perm] del w if counts is None: # every sample has Npt links: flat link l belongs to sample l // Npt perm.floor_divide_(self.hi.shape[1]) rows = perm else: rows = torch.repeat_interleave( torch.arange(self.N, device=self.device, dtype=torch.long), counts )[perm] del perm ccol, rows, vals = self._insert_tied_links(ccol, rows, vals, tie_vals) self.M = torch.sparse_csc_tensor( ccol, rows, vals, size=(self.N, self.K), device=self.device, dtype=self.dtype, check_invariants=False, # sorted and in range by construction ) def _build_MT(self) -> None: # (K,N), normalised per sample (row of M): weights and sums are # computed in the search order like the former eager construction. # A sample whose weights all underflowed (float32, far from every # kept cell: #77) has norm_row 0; its links get 0, not 0/0 = NaN. rows, cols, w = self._flat_links() norm_row = self._norm_row(rows, w) self._MT = self._csr_from_coo(cols, rows, _safe_normalize(w, norm_row[rows]), (self.K, self.N)) def _build_M_cons(self) -> None: # (N,K) CSR, same links as M, normalised per sample (issue #44). rows, cols, w = self._flat_links() norm_row = self._norm_row(rows, w) self._M_cons = self._csr_from_coo(rows, cols, _safe_normalize(w, norm_row[rows]), (self.N, self.K)) @property def MT(self) -> torch.Tensor: """Sparse CSR ``(K, N)`` operator, cells -> samples (``invert()``); built on first access.""" if getattr(self, "_MT", None) is None: self._build_MT() return self._MT @MT.setter def MT(self, value: torch.Tensor) -> None: self._MT = value @property def M_cons(self) -> torch.Tensor: """Sparse CSR ``(N, K)`` conservative operator (``resample(conservative=True)``, same links as ``M``, each sample's weights summing to 1); built on first access.""" if getattr(self, "_M_cons", None) is None: self._build_M_cons() return self._M_cons @M_cons.setter def M_cons(self, value: torch.Tensor) -> None: self._M_cons = value @torch.no_grad() def invert(self, hval: T_Array) -> T_Array: """Project HEALPix field back to the sample locations. Args: hval: (B,K) or (K,) on same device Returns: val_hat: (B,N) or (N,) """ y = hval if isinstance(hval, torch.Tensor) else torch.as_tensor(hval) y = y.to(self.device, dtype=self.dtype) if hval.ndim == 1: res = (y[None, :] @ self.MT)[0] else: res = y @ self.MT if not isinstance(hval, torch.Tensor): res=res.cpu().numpy() return res @torch.no_grad() def resample( self, val: T_Array, *, lam: float = 0.0, max_iter: int = 100, tol: float = 1e-8, x0: Optional[torch.Tensor] = None, return_info: bool = False, ) -> ResampleResults[T_Array]: """Estimate the HEALPix field from unstructured samples. Args: val: (B,N) or (N,) values at lon/lat sample points lam: Tikhonov regularization strength (damping) used in CG max_iter, tol: CG parameters x0: optional initial guess for the *delta* around x_ref, shape (B,K) return_info: whether to return CG diagnostics Returns: hval: (B,K) or (K,) (optional) info: CG information dict """ y = val if isinstance(val, torch.Tensor) else torch.as_tensor(val) y = y.to(self.device, dtype=self.dtype) clean_shape=False if y.ndim == 1: clean_shape=True y = y[None, :] # reference field (B,K) hval = y @ self.M cell_ids = self.cell_ids if not isinstance(val, torch.Tensor): hval= hval.cpu().numpy() cell_ids = cell_ids.cpu().numpy() if clean_shape: hval = hval[0] return ResampleResults(cell_data=hval, cell_ids=cell_ids) def get_cell_ids(self): return self.cell_ids.cpu().numpy()
@torch.no_grad() def _conservative_resample(op: "KNeighborsResampler", val: T_Array, area: torch.Tensor) -> ResampleResults: """Shared conservative-mode forward pass for KNN-based interpolating resamplers (`BilinearResampler`, `BicubicResampler`) that build an `M_cons` operator in their own `comp_matrix()` -- see either class's `resample(conservative=True)` docstring for the full derivation and guarantee. `op.M_cons` is `(N, K)`, with each row (source sample) summing to exactly 1 (a partition of unity) for well-conditioned samples -- see each caller's own comp_matrix()/docstring for when that can be only approximate (e.g. BicubicResampler's signed-kernel floor). Because `M_cons`'s per-sample normalization is fixed at construction time (unlike `M`'s per-cell normalization, which implicitly assumes every linked sample is present), zeroing a NaN sample's value *and* excluding its area here is enough on its own to keep the exact identity sum_k hval[k] == sum_i (valid i) val[i] * area[i] with no separate renormalization step needed -- a cleaner NaN story than the interpolation path's (see `KNeighborsResampler.resample()`'s docstring for that caveat). """ y = val if isinstance(val, torch.Tensor) else torch.as_tensor(val) y = y.to(op.device, dtype=op.dtype) squeezed = y.ndim == 1 if squeezed: y = y.unsqueeze(0) # (1, N) nan_mask = torch.isnan(y) valid = ~nan_mask y_filled = torch.where(valid, y, torch.zeros_like(y)) row_has_data = valid.any(dim=-1) # (B,) weighted = y_filled * area # (B, N), area (N,) broadcasts over rows hval = weighted @ op.M_cons # (B, K) hval[~row_has_data] = float("nan") cell_ids = op.cell_ids if squeezed: hval = hval.squeeze(0) if not isinstance(val, torch.Tensor): hval = hval.cpu().numpy() cell_ids = cell_ids.cpu().numpy() return ResampleResults(cell_data=hval, cell_ids=cell_ids)