The 10 most recently published documents
The cycle space of a directed graph is generated by a cycle basis, where, in general, cycles are allowed to have both forward and backward arcs. In a forward cycle, all arcs have to follow the given direction. We study the existence, structure, and computational complexity of minimum-weight forward cycle bases in directed graphs. We give a complete structural characterization of digraphs that admit weakly fundamental (and hence integral) forward cycle bases, showing that this holds if and only if every block is either strongly connected or a single arc. We further provide an easily verifiable characterization of when a strongly connected digraph admits a forward fundamental cycle basis, proving that such a basis exists if and only if the set of directed cycles has cardinality equal to the cycle rank; in this case, the basis is unique and computable in polynomial time, and nonexistence can likewise be certified efficiently.
Lastly, we show that while minimum-weight forward fundamental cycle bases can be found in polynomial time whenever they exist, the minimum-weight forward weakly fundamental cycle basis problem is NP-hard via a polynomial-time reduction from the minimum-weight weakly fundamental cycle basis problem on digraphs with metric weights.
Using FPGA-based Network-Attached Accelerators for Energy-Efficient AI Training in HPC Datacenters
(2026)
FPGA-based Network-Attached Accelerators offer a disaggregated alternative to closely-coupled FPGAs or GPUs, but their adoption is very limited due to missing hardware/software frameworks. However, the usability and energy-efficiency of FPGAs for HPC use-cases has been demonstrated previously. Yet, the support by HPC infrastructure for those devices is lacking behind other accelerators. This paper addresses this shortcoming and demonstrates a full-stack approach that seamlessly integrates Network-Attached Accelerators in HPC datacenters and allows flexible and scalable usage of FPGAs. The presented work includes the according framework, integration steps and a show-case application from the geoscience domain.
We evaluate our approach by comparing the training of a Physics-Informed Neural Network on the NAA against two GPU implementations. The NAA reduces total energy consumption by about 50% and 17% compared to the Keras and CUDA implementation, respectively. These results demonstrate that FPGA-based NAAs can be successfully integrated into HPC environments and are a viable path toward more energy-efficient AI training.
We present an eikonal-based approach that is capable of finding a continuous globally optimal trajectory for an aircraft in a stationary wind field. This minimizes emissions and fuel consumption. If the destination is close to a cut locus of the associated Hamilton-Jacobi-Bellman equation, small numerical discretization errors can lead to selecting a merely locally optimal trajectory and missing the globally optimal one. Based on finite element error estimates, we construct a trust region around the cut loci in order to guarantee uniqueness of trajectories for destinations sufficiently far from cut loci.
A Flexible Open-Source Framework for FPGA-based Network-Attached Accelerators using SpinalHDL
(2026)
Domain-specific accelerators are increasingly vital in heterogeneous computing systems, driven by the demand for higher computational capacity and especially energy efficiency. Network-attached FPGAs promise a scalable and flexible alternative to closely coupled FPGAs for integrating accelerators into computing environments. While the advantages of specialized hardware implementations are apparent, traditional hardware development and integration remain time-consuming and complex.
We present an open-source framework which combines a hardware shell with supporting software libraries, which enables fast development and deployment of FPGA-based network-attached accelerators. In contrast to traditional approaches using VHDL or Verilog, we leverage generative programming with SpinalHDL, providing a flexible hardware description with multi-level abstractions. This work eases the integration of accelerators into existing network infrastructures and simplifies adaptation to different FPGAs, eliminating complex and lengthy top-level hardware descriptions.
The mutual information (MI) between two random variables is an important
correlation measure in data analysis. The Shannon entropy of a joint probability distri-
bution is the variable part under fixed marginals. We aim to minimize and maximize it
to obtain the largest and smallest MI possible in this case, leading to a scaled MI ratio
for better comparability. We present algorithmic approaches and optimal solutions for
a set of problem instances based on data from molecular evolution. We show that this
allows us to construct a sensible, systematic correction to raw MI values.
We solve the problem of determining the pose of known shapes in R^3 from their unoccluded silhouettes. The pose is determined up to global optimality using a simple yet under-explored property of the area-of-silhouette: its continuity w.r.t trajectories in the rotation space. The proposed method utilises pre-computed silhouette-signatures, modelled as a response surface of the area-of-silhouettes. Querying this silhouette-signature response surface for pose estimation leads to a strong branching of the rotation search space, making resolution-guided candidate search feasible. Additionally, we utilise the aspect ratio of 2D ellipses fitted to projected silhouettes as an auxiliary global shape signature to accelerate the pose search. This combined strategy forms the first method to efficiently estimate globally optimal pose from just the silhouettes, without being guided by correspondences, for any shape, irrespective of its convexity and genus. We validate our method on synthetic and real examples, demonstrating significantly improved accuracy against comparable approaches.
We present a structure-aware parallel presolve framework specialized to arrowhead linear programs (AHLPs) and designed for high-performance computing (HPC) environments, integrated into the parallel interior point solver PIPS-IPM++. Large-scale LPs arising from automated model generation frequently contain redundancies and numerical pathologies that necessitate effective presolve, yet existing presolve techniques are primarily serial or structure-agnostic and can become time-consuming in parallel solution workflows.
Within PIPS-IPM++, AHLPs are stored in distributed memory, and our presolve builds on this to apply a highly parallel, distributed presolve across compute nodes while keeping communication overhead low and preserving the underlying arrowhead structure. We demonstrate the scalability and effectiveness of our approach on a diverse set of AHLPs and compare it against state-of-the-art presolve implementations, including PaPILO and the presolve implemented within Gurobi. Even on a single machine, our presolve significantly outperforms PaPILO by a factor of 18 and Gurobi’s presolve by a factor of 6 in terms of shifted geometric mean runtime, while reducing the problems by a similar amount to PaPILO. Using a distributed compute environment, we outperform Gurobi's presolve by a factor of 13.