Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “geometric search”

Search indexed NASA NTRS and DOE OSTI research on propulsion, heat transfer, battery materials and energy systems. Follow report and document links to the original sources.

Quote a phrase for an exact phrase match. Source license links do not imply unrestricted reuse.

At least 19 records
All sourcesNASA NTRSDOE OSTI
DOE OSTI2020

ArborX: A Performance Portable Geometric Search Library

Searching for geometric objects that are close in space is a fundamental component of many applications. The performance of search algorithms comes to the forefront as the size of a problem increases both in terms of total object count as well as in the total number of search queries performed. Scientific applications requiring modern leadership-class supercomputers also pose an additional requirement of performance portability, i.e., being able to efficiently utilize a variety of hardware architectures. In this article, we introduce a new open-source C++ search library, ArborX, which we have designed for modern supercomputing architectures. Herein, we examine scalable search algorithms with a focus on performance, including a highly efficient parallel bounding volume hierarchy implementation, and propose a flexible interface making it easy to integrate with existing applications. We demonstrate the performance portability of ArborX on multi-core CPUs and GPUs and compare it to the state-of-the-art libraries such as Boost.Geometry.Index and nanoflann.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2020

Prediction of chlorine and fluorine crystal structures at high pressure using symmetry driven structure search with geometric constraints

The high-pressure properties of fluorine and chlorine are not yet well understood because both are highly reactive and volatile elements, which have made conducting diamond anvil cell and x-ray diffraction experiments a challenge. Here, we use ab initio methods to search for stable crystal structures of both elements at megabar pressures. We demonstrate how symmetry and geometric constraints can be combined to efficiently generate crystal structures that are composed of diatomic molecules. Furthermore, our algorithm extends the symmetry driven structure search method by adding constraints for the bond length and the number of atoms in a molecule while still maintaining generality. As a method of validation, we have tested our approach for dense hydrogen and reproduced the known molecular structures of Cmca-12 and Cmca-4. We apply our algorithm to study chlorine and fluorine in the pressure range of 10 GPa–4000 GPa while considering crystal structures with up to 40 atoms per unit cell. We predict chlorine to follow the same series of phase transformations as elemental iodine from Cmca to Immm to Fm3¯m, but at substantially higher pressures. We predict fluorine to transition from a C2/c to Cmca structure at 70 GPa, to a novel orthorhombic and metallic structure with P42/mmc symmetry at 2500 GPa, and finally to its cubic analog form with Pm3¯n symmetry at 3000 GPa.

37 INORGANIC, ORGANIC, PHYSICAL, AND ANALYTICAL CH↗
DOE OSTI2024

Advances in ArborX to support exascale applications

ArborX is a performance portable geometric search library developed as part of the Exascale Computing Project (ECP). In this paper, we explore a collaboration between ArborX and a cosmological simulation code HACC. Large cosmological simulations on exascale platforms encounter a bottleneck due to the in-situ analysis requirements of halo finding, a problem of identifying dense clusters of dark matter (halos). This problem is solved by using a density-based DBSCAN clustering algorithm. With each MPI rank handling hundreds of millions of particles, it is imperative for the DBSCAN implementation to be efficient. In addition, the requirement to support exascale supercomputers from different vendors necessitates performance portability of the algorithm. We describe how this challenge problem guided ArborX development, and enhanced the performance and the scope of the library. We explore the improvements in the basic algorithms for the underlying search index to improve the performance, and describe several implementations of DBSCAN in ArborX. Further, we report the history of the changes in ArborX and their effect on the time to solve a representative benchmark problem, as well as demonstrate the real world impact on production end-to-end cosmology simulations.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2025

The ArborX Library: Version 2.0

This article provides an overview of the 2.0 release of the ArborX library, a performance portable geometric search library based on Kokkos. We describe the major changes in ArborX 2.0 including a new interface for the library to support a wider range of user problems, new search data structures (brute force and distributed), support for user functions to be executed on the results (callbacks), and an expanded set of the supported algorithms (ray tracing and clustering).

GPU↗
DOE OSTI2023

A single-tree algorithm to compute the Euclidean minimum spanning tree on GPUs

Computing the Euclidean minimum spanning tree (Emst) is a computationally demanding step of many algorithms. While work-efficient serial and multithreaded algorithms for computing Emst are known, designing an efficient GPU algorithm is challenging due to a complex branching structure, data dependencies, and load imbalances. In this paper, we propose a single-tree $Bor\mathring{u}vka$-based algorithm for computing Emst on GPUs. We use an efficient nearest neighbor algorithm and reduce the number of the required distance calculations by avoiding traversing subtrees with leaf nodes in the same component. The developed algorithms are implemented in a performance portable way using ArborX, an open-source geometric search library based on the Kokkos framework. We evaluate the proposed algorithm on various 2D and 3D datasets, show and compare it with the current state-of-the-art open-source CPU implementations. We demonstrate 4-24 × speedup over the fastest multi-threaded implementation. We prove the portability of our implementation by providing results on a variety of hardware: AMD EPYC 7763, Nvidia A100 and AMD MI250X. We show scalability of the implementation, computing Emst for 37 million 3D cosmological dataset in under a 0.5 second on a single A100 Nvidia GPU.

Prokopenko, Andrey↗
DOE OSTI2021

ArborX

ArborX library tackles a problem of efficiently finding geometric objects that are close in space. Variations of this problem, such as finding the nearest neighbors of a point, or finding all objects within a certain distance, are inherent components of applications in many fields. The data may be large so that solving the problem efficiently may require significant computational resources, such as multiple processors or accelerators such as general purpose GPUs. ArborX' main advantage in its ability to solve large problems efficiently utilizing a combination of distributed and on-node parallelism. ArborX can be run efficiently on a wide variety of hardware, including GPUs from different vendors, which distinguishes it from other available libraries which typically choose only few of these. The other advantage is that it supports both types of user problems: spatial problems (useful for intersections and finding objects within certain distance), and nearest neighbor problems. ArborX also supports flexible interface in its interaction with a user. Particularly, it allows a user to call user's own function on a positive match, a functionality not rarely available in other libraries. ArborX implements construction and traversal algorithms using efficient tree structures, such as bounding volume hierarchy (BVH). At its core, it uses linear BVH for its low construction cost and sufficient quality. ArborX is written using C++, and is parallelized using the message passing interface (MPI) for the distributed communication, and the Kokkos library for on-node parallelism. This approach allows ArborX to be run on a wide variety of hardware, from common laptops and desktops to supercomputers while using the same codebase. ArborX also implements several advanced algorithms using geometric search, such as density-based clustering algorithm DBSCAN.

ECP↗
DOE OSTI2024

Sandia Toolkit Manual (V.5.21.1)

This report provides documentation for the Sandia Toolkit (STK) modules. STK modules are intended to provide infrastructure that assists the development of computational engineering software such as finite-element analysis applications. STK includes modules for unstructured-mesh data structures, reading/writing mesh files, geometric proximity search, transfers, MPMD coupling support, and various other utilities. This document contains a chapter for each module, and each chapter contains overview descriptions and usage examples. Usage examples are primarily code listings which are generated from working test programs that are included in the STK code-base. A goal of this approach is to ensure that the usage examples will not fall out of date.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2023

Sandia Toolkit Manual Version 5.15.6

This report provides documentation for the Sandia Toolkit (STK) modules. STK modules are intended to provide infrastructure that assists the development of computational engineering software such as finite-element analysis applications. STK includes modules for unstructured-mesh data structures, reading/writing mesh files, geometric proximity search, and various utilities. This document contains a chapter for each module, and each chapter contains overview descriptions and usage examples. Usage examples are primarily code listings which are generated from working test programs that are included in the STK code-base. A goal of this approach is to ensure that the usage examples will not fall out of date.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2025

Benders Decomposition Using Graph Modeling and Multi-Parametric Programming

Benders decomposition is a widely used method for solving large and structured optimization problems, but its performance is affected by the repeated solution of subproblems. We propose a flexible and modular algorithmic framework for accelerating Benders decomposition. Specifically, we express the problem structure by using a graph-theoretic modeling abstraction in which nodes represent optimization subproblems and edges represent connectivity between subproblems. A key innovation of our approach is that we embed multiparametric programming (mp) surrogates for node subproblems, which maps the exact analytical map of the subproblem solution space. The use of mp surrogates allows us to replace subproblem solves with fast look-ups and function evaluations for primal and dual variables during the iterative Benders process. We formally show the equivalence between classical Benders cuts and those derived from the mp solution. We implement our framework in the open-source PlasmoBenders.jl software package. To demonstrate the capabilities of the proposed framework, we apply it to a two-stage stochastic programming problem, which aims to make optimal capacity expansion decisions under market uncertainty. We evaluate both single-cut and multicut variants of Benders decomposition and show that the use of mp surrogates achieves substantial speedups in subproblem solve time, while preserving the convergence guarantees of Benders decomposition. We highlight advantages in solution analysis and interpretability that is enabled by mp critical region tracking; specifically, we show that these reveal how decisions evolve geometrically across the Benders search. Our results aim to demonstrate that combining surrogate modeling with graph modeling offers a promising and extensible foundation for structure-exploiting decomposition. In addition, by decomposing the problem into more tractable subproblems, the proposed approach also aims to overcome scalability issues of mp. Finally, the use of mp surrogates provides a unifying and modular optimization framework that enables the representation of heterogeneous node subproblems as modeling objects with a homogeneous structure.

37 INORGANIC, ORGANIC, PHYSICAL, AND ANALYTICAL CH↗
DOE OSTI2021

Axom

Axom is an open-source library of "building block" software components that provide core infrastructure capabilities for HPC applications. Such capabilities include: input file parsing and verification for various file formats, format specification for material shape input to multi-material simulations and tools for placing those shapes on meshes, parallel distributed coordination of diagnostic messages, geometric primitives, spatial queries and spatial search acceleration data structures, in memory key-value data store for managing simulation data and parallel file I/O. Axom components are used widely across LLNL Advanced Simulation and Computing program applications. It is also part of the LLNL institutionally-supported RADIUSS project, which promotes and funds its adoption by projects across LLNL.

Zagaris, George↗
DOE OSTI2024

Predicted High-Pressure Hot Superconductivity in Li 2 CaH 16 and Li 2 CaH 17 Phases that Resemble the Type-II Clathrate Structure

High-temperature high-pressure superconducting hydrides are typically characterized by cage-like hydrogenic lattices filled with electropositive metal atoms. Here, density functional theory based evolutionary crystal structure searches find two phases that possess these geometric features and are related to the Type-II clathrate structure. In these Fd$\overline{3}$m Li 2 CaH 16 and R$\overline{3}$m Li 2 CaH 17 phases the calcium atom occupies the larger cage and the lithium atom the smaller one. The highest superconducting critical temperatures predicted within the isotropic Eliashberg formalism, 330 K at 350 GPa for Fd$\overline{3}$m Li 2 CaH 16 and 370 K at 300 GPa for R$\overline{3}$m Li 2 CaH 17 , suggest these structures are another example of hot superconducting hydrides. As pressure is lowered the cage-like lattices distort with the emergence of quasimolecular hydrogenic motifs; nonetheless Li 2 CaH 17 is predicted to be superconducting down to 160 GPa at 205 K.

37 INORGANIC, ORGANIC, PHYSICAL, AND ANALYTICAL CH↗
DOE OSTI2024

Quantum Spin Dynamics Due to Strong Kitaev Interactions in the Triangular-Lattice Antiferromagnet CsCeSe 2

The extraordinary properties of the Kitaev model have motivated an intense search for new physics in materials that combine geometrical and bond frustration. In this Letter, we employ inelastic neutron scattering, spin wave theory, and exact diagonalization to study the spin dynamics in the perfect triangular-lattice antiferromagnet (TLAF) CsCeSe 2 . This material orders into a stripe phase, which is demonstrated to arise as a consequence of the off-diagonal bond-dependent terms in the spin Hamiltonian. By studying the spin dynamics at intermediate fields, we identify an interaction between the single-magnon state and the two-magnon continuum that causes decay of coherent magnon excitations, level repulsion, and transfer of spectral weight to the continuum that are controlled by the strength of the magnetic field. Our results provide a microscopic mechanism for the stabilization of the stripe phase in TLAF and show how complex many-body physics can be present in the spin dynamics in a magnet with strong Kitaev coupling even in an ordered ground state. Published by the American Physical Society 2024

75 CONDENSED MATTER PHYSICS, SUPERCONDUCTIVITY AND↗
DOE OSTI2026

Graph Identification of Proteins in Tomograms (GRIP-Tomo) 2.0: Topologically aware classification for proteins

Cryo-electron tomography (cryo-ET) enables structural characterization of biomolecules under near-native conditions. Existing approaches for interpreting the resulting three-dimensional volumes are computationally expensive and have difficulty interpreting density associated with small proteins/complexes. To explore alternate approaches for identifying proteins in cryo-ET data we pursued a Graph Network and topologically invariant approach. Here, we report on a fast algorithm that classifies particles by searching for nuances of evolutionarily conversed motifs and the geometrical characteristics of protein structure. GRIP-Tomo 2.0 is a machine-learning pipeline that extracts interpretable topological features of protein structures within noisy experimental backgrounds. Compared to version 1.0, the new pipeline includes three upgrades that significantly improve performance including synthetic tomogram generation simulating realistic noise, graph-based persistent feature extraction as protein fingerprints, and high-performance computing acceleration. GRIP-Tomo 2.0 achieves over 90% accuracy in classifying between proteins and noise using both real and synthetic datasets which represents a foundational step toward advancing cryo-ET workflows and empowering automated visual proteomics.

Li, Chengxuan↗
DOE OSTI2024

Discovering Classical Spin Liquids by Topological Search of High Symmetry Nets

Spin liquids are a paradigmatic example of a nontrivial state of matter. The search for new spin liquids is a key interdisciplinary challenge. Geometrical frustration-where the geometry of the net that the spins occupy precludes the generation of a simple ordered state-is a particularly fruitful way to generate these intrinsically disordered states. Prior focus has been on a handful of high symmetry nets. There are, however, many three-dimensional nets, each of which has the potential to form unique states. In this paper, we investigate the high symmetry nets-those which are both vertex- and edge-transitive-for the simplest possible interaction sets: nearest-neighbor couplings of antiferromagnetic Heisenberg and Ising spins. While the well-known crs (pyrochlore) net is the only nearest-neighbor Heisenberg antiferromagnet which does not order, we identify two new frustrated nets (lcx and thp) possessing finite temperature Heisenberg spin-liquid states with strongly suppressed magnetic ordering and noncollinear ground states. With Ising spins, we identify three new classical spin liquids that do not order down to T/J = 0.01. We highlight materials that contain these high symmetry nets, and which could, if substituted with appropriate magnetic ions, potentially host these unusual states. Our systematic survey will guide searches for novel magnetic phases.

37 INORGANIC, ORGANIC, PHYSICAL, AND ANALYTICAL CH↗
DOE OSTI2020

Grain boundary structure search by using an evolutionary algorithm with effective mutation methods

Grain boundaries (GBs) accommodate the misorientation between adjacent grains in a polycrystalline material. GBs are geometrically described by the macroscopic and microscopic degrees of freedom. Besides, at the atomistic level, GBs exhibit complicated behaviors under varying thermodynamic conditions. The complexity of atomistic GB structures demands stochastic searching for possible states. The effectiveness of stochastic search methods relies on techniques to recreate and select atomistic structures. In this work, we developed a new mutation operator that can induce direct and collective atomistic structure changes to boost the search efficiency of exploring GB structures with evolutionary algorithms (EA). We implemented the mutation methods along with innovative selection, crossover, boundary condition preprocessing methods to form an EA-based package to explore GB structures in grand canonical ensembles with atomistic simulations. We used this package to study the [001] symmetric tilt grain boundaries (STGBs) in FCC copper (Cu), the [110] STGBs in BCC tungsten (W), and the $[1\bar{2}10]$ STGBs in HCP magnesium (Mg). The results show that our design and implementation based on new mutation procedures, selection, and boundary conditions provide a high-quality search of atomistic GB structures in the grand canonical ensemble for different crystal lattices.

36 MATERIALS SCIENCE↗
DOE OSTI2020

The Breakthrough Listen Search for Intelligent Life: A 3.95–8.00 GHz Search for Radio Technosignatures in the Restricted Earth Transit Zone

We report on a search for artificial narrowband signals of 20 stars within the restricted Earth Transit Zone (rETZ) as a part of the ten-year Breakthrough Listen (BL) search for extraterrestrial intelligence (ETI). The rETZ is the region of the sky from which an observer would see Earth transit the Sun with an impact parameter of less than 0.5. This region of the sky is geometrically unique, providing a potential way for an ETI to discover the solar system. The targets were nearby (7–143 pc) and the search covered an electromagnetic frequency range of 3.95–8.00 GHz. We used the Robert C. Byrd Green Bank Telescope to perform these observations with the standard BL data recorder. We searched these data for artificial narrowband (∼Hz) signals with Doppler drift rates of ±20 Hz s{sup −1}. We find no evidence for radio technosignatures from ETI in our observations. The observing campaign would have allowed for detections of emissions that were 10{sup −3} to 0.88 times as powerful as the signaling capability of the Arecibo radar transmitter. We conclude that at least 0.6% of the systems in the rETZ within 150 pc do not possess the type of transmitters searched in this survey. To our knowledge, this is the first targeted search for ETI of the rETZ. All data used in this paper are publicly available via the BL Public Data Archive (http://seti.berkeley.edu/bldr2).

79 ASTRONOMY AND ASTROPHYSICS↗
DOE OSTI2024

Asynchronous GPU-based DEM solver embedded in commercial CFD software with polyhedral mesh support

A novel graphical processing unit-based discrete element method solver is introduced to improve stability, performance, and provide seamless integration into commercial or open-source computational fluid dynamics software. A key innovation is eliminating a need for network communication between solvers, which was previously required for cross-platform coupling. This is accomplished by a direct coupling method that employs dynamic-linked libraries. Furthermore, the solver optimizes memory usage by streamlining the particle-cell search algorithm by eliminating the cells' searching grid. This ensures the solver is compatible with a wide range of mesh types, providing high geometric flexibility. The approach simplifies the simulation process by directly incorporating computational fluid dynamics mesh information into the discrete element method solver. The performance analysis indicates about sixteen times boost in computational speed compared to benchmark central processing unit-based solvers. Finally, the solver's compatibility with polyhedral meshes, a vital advantage for complex geometries, is tested against a referenced study regarding the simulation of an immersed-tube fluidized bed.

32 ENERGY CONSERVATION, CONSUMPTION, AND UTILIZATI↗
DOE OSTI2023

KamNet: An integrated spatiotemporal deep neural network for rare event searches in KamLAND-Zen

Rare event searches allow us to search for new physics at energy scales inaccessible with other means by leveraging specialized large-mass detectors. Machine learning provides a new tool to maximize the information provided by these detectors. The information is sparse, which forces these algorithms to start from the lowest level data and exploit all symmetries in the detector to produce results. In this work we present KamNet, which harnesses breakthroughs in geometric deep learning and spatiotemporal data analysis to maximize the physics reach of KamLAND-Zen, a kiloton scale spherical liquid scintillator detector searching for 0⁢νβ⁢β. Using a simplified background model for KamLAND, we show that KamNet outperforms a conventional convolutional neural network (CNN) on benchmarking Monte Carlo simulations with an increasing level of robustness. Using simulated data, we then demonstrate KamNet's ability to increase KamLAND-Zen's sensitivity to 0ν⁢ββ and 2⁢ν⁢β⁢β decay to excited states. A key component of this work is the addition of an attention mechanism to elucidate the underlying physics KamNet is using for the background rejection.

73 NUCLEAR PHYSICS AND RADIATION PHYSICS↗