Structure-Adaptive Tree Field Integrators
Abstract
We present a new class of near-linear algorithms for efficiently integrating general tensor fields defined on trees with distance dependent kernels, the Structure-Adaptive Tree Field Integrators (STAD-TFIs). STAD-TFIs exploit the tree's underlying structure through decompositions built around path backbones and single vertex separators, and use two-dimensional fast Fourier transforms to compute interactions jointly. By exploiting this structural information, STAD-TFIs achieve more computationally efficient integration than their regular efficient tree field integrators (TFI) counterparts. We provide a detailed theoretical analysis of our proposed approach and complement it with an exhaustive empirical evaluation, ranging from speed tests on synthetic trees, through accelerated Sinkhorn-based relaxations of the Optimal Transport algorithms on real meshes, to Topological Attention Transformers for vision tasks. To the best of our knowledge, we provide some of the first results showing that efficient to compute and accurate relaxations of the geodesic Sinkhorn-based solutions of the Optimal Transport problem can be derived by applying fast TFI methods.
Related
- A novel class of high-order uniformly accurate exponential integrators with local linear extension for the charged-particle dynamics under strong magnetic field
- Quasi-periodic tree sets and structure trees
- Beyond Imputation: Mask-Adaptive Conformal Prediction via Tree Embeddings on General Missing Data Mechanisms
- Recovering a structure from its tree of tuples
- The mean-field limit of non-exchangeable particle systems with non-conservative dynamics and adaptive weights
BibTeX
@misc{roy2026structureadaptive,
title = {{Structure-Adaptive Tree Field Integrators}},
author = {Millend Roy and Soham Samal and Ivan Zelich and Krzysztof Marcin Choromanski},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.34025},
eprint = {2609.34025},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.34025},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Structure-Adaptive Tree Field Integrators
AU - Millend Roy
AU - Soham Samal
AU - Ivan Zelich
AU - Krzysztof Marcin Choromanski
PY - 2026
DA - 2026/09/27
PB - arXiv
DO - 10.48550/arxiv.2609.34025
UR - https://arxiv.org/abs/2609.34025
AB - We present a new class of near-linear algorithms for efficiently integrating general tensor fields defined on trees with distance dependent kernels, the Structure-Adaptive Tree Field Integrators (STAD-TFIs). STAD-TFIs exploit the tree's underlying structure through decompositions built around path backbones and single vertex separators, and use two-dimensional fast Fourier transforms to compute interactions jointly. By exploiting this structural information, STAD-TFIs achieve more computationally efficient integration than their regular efficient tree field integrators (TFI) counterparts. We provide a detailed theoretical analysis of our proposed approach and complement it with an exhaustive empirical evaluation, ranging from speed tests on synthetic trees, through accelerated Sinkhorn-based relaxations of the Optimal Transport algorithms on real meshes, to Topological Attention Transformers for vision tasks. To the best of our knowledge, we provide some of the first results showing that efficient to compute and accurate relaxations of the geodesic Sinkhorn-based solutions of the Optimal Transport problem can be derived by applying fast TFI methods.
ER -