Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “vertex”

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 217 records · Page 12
All sourcesNASA NTRSDOE OSTI
DOE OSTI2024

Clustering and Cliques in Preferential Attachment Random Graphs with Edge Insertion

In this paper, we investigate the global clustering coefficient (a.k.a transitivity) and clique number of graphs generated by a preferential attachment random graph model with an additional feature of allowing edge connections between existing vertices. Specifically, at each time step t, either a new vertex is added with probability f(t), or an edge is added between two existing vertices with probability 1 – f(t). We establish concentration inequalities for the global clustering and clique number of the resulting graphs under the assumption that f(t) is a regularly varying function at infinity with index of regular variation –$\gamma$, where $\gamma$ $\in$ [0, 1). Finally, we also demonstrate an inverse relation between these two statistics: the clique number is essentially the reciprocal of the global clustering coefficient.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2021

Lower bounds on circuit depth of the quantum approximate optimization algorithm

The quantum approximate optimization algorithm (QAOA) is a method of approximately solving combinatorial optimization problems. While QAOA is developed to solve a broad class of combinatorial optimization problems, it is not clear which classes of problems are best suited for it. One factor in demonstrating quantum advantage is the relationship between a problem instance and the circuit depth required to implement the QAOA method. As errors in noisy intermediate-scale quantum (NISQ) devices increase exponentially with circuit depth, identifying lower bounds on circuit depth can provide insights into when quantum advantage could be feasible. In this work, we identify how the structure of problem instances can be used to identify lower bounds for circuit depth for each iteration of QAOA and examine the relationship between problem structure and the circuit depth for a variety of combinatorial optimization problems including MaxCut and MaxIndSet. Specifically, we show how to derive a graph, G, that describes a general combinatorial optimization problem and show that the depth of circuit is at least the chromatic index of G. By looking at the scaling of circuit depth, we argue that MaxCut, MaxIndSet, and some instances of vertex covering and Boolean satisfiability problems are suitable for QAOA approaches while knapsack and traveling salesperson problems are not.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2021

Impact of graph structures for QAOA on MaxCut

The quantum approximate optimization algorithm (QAOA) is a promising method of solving combinatorial optimization problems using quantum computing. QAOA on the MaxCut problem has been studied extensively on graphs with specific structure; however, little is known about the general performance of the algorithm on arbitrary graphs. Here, we investigate how different graph characteristics correlate with QAOA performance at depths at most three on the MaxCut problem for all connected non-isomorphic graphs with at most eight vertices. Some good predictors of QAOA success relate to graph symmetries, odd cycles, and density. For example, on eight vertex graphs, the average probability for selecting an optimal solution for graphs that contain no odd cycles after three iterations of QAOA is 60.6% compared to 48.2% for those that do. The data generated from these studies are shared in a publicly accessible database to serve as a benchmark for QAOA calculations and experiments. Knowing the relationship between structure and performance can be used to identify classes of combinatorial problems that are likely to exhibit a quantum advantage.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2025

Graph decomposition techniques for solving combinatorial optimization problems with variational quantum algorithms

The quantum approximate optimization algorithm (QAOA) has the potential to approximately solve complex combinatorial optimization problems in polynomial time. However, current noisy quantum devices cannot solve large problems due to hardware constraints. In this work, we develop an algorithm that decomposes the QAOA input problem graph into a smaller problem and solves MaxCut using QAOA on the reduced graph. The algorithm requires a subroutine that can be classical or quantum—in this work, we implement the algorithm twice on each graph. One implementation uses the classical solver Gurobi in the subroutine and the other uses QAOA. We solve these reduced problems with QAOA. On average, the reduced problems require only approximately 1/10 of the number of vertices than the original MaxCut instances. Furthermore, the average approximation ratio of the original MaxCut problems is 0.75, while the approximation ratios of the decomposed graphs are on average of 0.96 for both Gurobi and QAOA. With this decomposition, we are able to measure optimal solutions for ten 100-vertex graphs by running single-layer QAOA circuits on the Quantinuum trapped-ion quantum computer H1-1, sampling each circuit only 500 times. This approach is best suited for sparse, particularly k-regular graphs, as k-regular graphs on n vertices can be decomposed into a graph with at most $\frac{nk}{k+1}$ vertices in polynomial time. Further reductions can be obtained with a potential trade-off in computational time. In conclusion, while this paper applies the decomposition method to the MaxCut problem, it can be applied to more general classes of combinatorial optimization problems.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2023

Exploring temporal community evolution: algorithmic approaches and parallel optimization for dynamic community detection

Abstract Dynamic (temporal) graphs are a convenient mathematical abstraction for many practical complex systems including social contacts, business transactions, and computer communications. Community discovery is an extensively used graph analysis kernel with rich literature for static graphs. However, community discovery in a dynamic setting is challenging for two specific reasons. Firstly, the notion of temporal community lacks a widely accepted formalization, and only limited work exists on understanding how communities emerge over time. Secondly, the added temporal dimension along with the sheer size of modern graph data necessitates new scalable algorithms. In this paper, we investigate how communities evolve over time based on several graph metrics under a temporal formalization. We compare six different algorithmic approaches for dynamic community detection for their quality and runtime. We identify that a vertex-centric (local) optimization method works as efficiently as the classical modularity-based methods. To its advantage, such local computation allows for the efficient design of parallel algorithms without incurring a significant parallel overhead. Based on this insight, we design a shared-memory parallel algorithm DyComPar , which demonstrates between 4 and 18 fold speed-up on a multi-core machine with 20 threads, for several real-world and synthetic graphs from different domains.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2020

An ab initio molecular dynamics exploration of associates in Ba-Bi liquid with strong ordering trends

Fictive associates are widely used to describe and model liquid phases with strong ordering trends. However, little evidence is known about the assumed associates in most cases. In the present work, an ab initio molecular dynamics (AIMD) study is employed to investigate the characters of the Ba-Bi liquid, in which associates have been assumed in existing thermodynamic modeling. It is found that in the Ba rich melt, the Bi atoms are almost completely surrounded by Ba atoms. The Bi-centered coordination polyhedrons are strongly associated to crystalline structures of Ba 5 Bi 3 and Ba 4 Bi 3 with a longer lifetime than other polyhedrons during the AIMD simulations. In addition, these Bi-centered polyhedrons in Ba rich melt connect with each other through vertex, edge, face, and/or bipyramid sharing to form medium range orders (MRO). In the Bi rich melt, the Ba-centered polyhedrons also form MROs, but they are both structurally and compositionally diverse with a shorter lifetime. These findings from AIMD study provide evidences that there exist a strongly ordering Ba 4 Bi 3 associate and a weakly ordering BaBi 3 associate in the Ba-Bi liquid. Here, the predicted enthalpy of mixing in the liquid agrees well with the results by the CALPHAD modeling in the literature.

36 MATERIALS SCIENCE↗
DOE OSTI2021

Short- and medium-range orders in Al90Tb10 glass and their relation to the structures of competing crystalline phases

Molecular dynamics simulations using an interatomic potential developed by artificial neural network deep machine learning are performed to study the local structural order in Al90Tb10 metallic glass. We show that more than 80% of the Tb-centered clusters in Al90Tb10 glass have short-range order (SRO) with their 17 first coordination shell atoms stacked in a ‘3661’ or ‘15551’ sequence. Medium-range order (MRO) in Bergman-type packing extended out to the second and third coordination shells is also clearly observed. Analysis of the network formed by the ‘3661’ and ‘15551’ clusters show that ~82% of such SRO units share their faces or vertexes, while only ~6% of neighboring SRO pairs are interpenetrating. Such a network topology is consistent with the Bergman-type MRO around the Tb-centers. Moreover, crystal structure searches using genetic algorithm and the neural network interatomic potential reveal several low-energy metastable crystalline structures in the composition range close to Al 90 Tb 10 . Some of these crystalline structures have the ‘3661’ SRO while others have the ‘15551’ SRO. While the crystalline structures with the ‘3661’ SRO also exhibit the MRO very similar to that observed in the glass, the ones with the ‘15551’ SRO have very different atomic packing in the second and third shells around the Tb centers from that of the Bergman-type MRO observed in the glassy phase.

36 MATERIALS SCIENCE↗
DOE OSTI2020

Eliashberg theory of phonon-mediated superconductivity — When it is valid and how it breaks down

We analyze the validity of Eliashberg theory of phonon-mediated superconductivity in 2D systems in light of recent extensive Monte-Carlo studies of the Holstein model. Conventional wisdom says that Eliashberg theory is applicable as long as vertex corrections remain small. For small ratio of the phonon energy Ω 0 and the Fermi energy E F , this condition is supposed to hold even when the dimensionless electron–phonon coupling λ is larger than one, i.e., in the strong coupling regime. A comparison between various quantities computed in the Migdal approximation and those computed by Quantum Monte Carlo prove that this belief is wrong, and we identify analytically some of the ways in which this breakdown occurs for various ‘‘normal state’’ properties at λ = λ cr , where λ cr = O(1). Here, the breakdown occurs at temperatures high enough that neither superconducting nor charge–density wave correlations extend over any significant range of distances, so it cannot be associated with the onset of an instability toward any of the relevant ordered ground-states — rather it is associated with the local physics of classical bipolaron formation. Still, we show that certain properties, including the superconducting Tc and the superconducting gap structure below T c , can be accurately inferred from the strong-coupling limit of Eliashberg theory at λ ≤ λ cr .

75 CONDENSED MATTER PHYSICS, SUPERCONDUCTIVITY AND↗
DOE OSTI2023

The MIGDAL experiment: Measuring a rare atomic process to aid the search for dark matter

We present the Migdal In Galactic Dark mAtter expLoration (MIGDAL) experiment aiming at the unambiguous observation and study of the so-called Migdal effect induced by fast-neutron scattering. It is hoped that this elusive atomic process can be exploited to enhance the reach of direct dark matter search experiments to lower masses, but it is still lacking experimental confirmation. Our goal is to detect the predicted atomic electron emission which is thought to accompany nuclear scattering with low, but calculable, probability, by deploying an Optical Time Projection Chamber filled with a low-pressure gas based on CF 4 . Initially, pure CF 4 will be used, and then in mixtures containing other elements employed by leading dark matter search technologies — including noble species, plus Si and Ge. High resolution track images generated by a Gas Electron Multiplier stack, together with timing information from scintillation and ionisation readout, will be used for 3D reconstruction of the characteristic event topology expected for this process — an arrangement of two tracks sharing a common vertex, with one belonging to a Migdal electron and the other to a nuclear recoil. Different energy-loss rate distributions along both tracks will be used as a powerful discrimination tool against background events. In this article we present the design of the experiment, informed by extensive particle and track simulations and detailed estimations of signal and background rates. In pure CF 4 we expect to observe 8.9 (29.3) Migdal events per calendar day of exposure to an intense D–D (D–T) neutron generator beam at the NILE facility located at the Rutherford Appleton Laboratory (UK). With our nominal assumptions, 5σ median discovery significance can be achieved in under one day with either generator.

46 INSTRUMENTATION RELATED TO NUCLEAR SCIENCE AND ↗
DOE OSTI2021

The Stellar decomposition: A compact representation for simplicial complexes and beyond

Here, we introduce the Stellar decomposition, a model for efficient topological data structures over a broad range of simplicial and cell complexes. A Stellar decomposition of a complex is a collection of regions indexing the complex’s vertices and cells such that each region has sufficient information to locally reconstruct the star of its vertices, i.e., the cells incident in the region’s vertices. Stellar decompositions are general in that they can compactly represent and efficiently traverse arbitrary complexes with a manifold or non-manifold domain. They are scalable to complexes in high dimension and of large size, and they enable users to easily construct tailored application-dependent data structures using a fraction of the memory required by a corresponding global topological data structure on the complex. As a concrete realization of this model for spatially embedded complexes, we introduce the Stellar tree, which combines a nested spatial tree with a simple tuning parameter to control the number of vertices in a region. Stellar trees exploit the complex’s spatial locality by reordering vertex and cell indices according to the spatial decomposition and by compressing sequential ranges of indices. Stellar trees are competitive with state-of-the-art topological data structures for manifold simplicial complexes and offer significant improvements for cell complexes and non-manifold simplicial complexes. We conclude with a high-level description of several mesh processing and analysis applications that utilize Stellar trees to process large datasets.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2022

An investigation of the multi-mode Richtmyer-Meshkov instability at a gas/HE interface using Pagosa

Here, in this work, we present a hydrocode Pagosa and explore the Richtmyer-Meshkov Instability (RMI) at an air/high explosive (HE) interface for the first time that is important but has not received much attention yet in the high explosive safety field. Thus, the presented Pagosa can be expected to predict the whole deflagration-to-detonation transition (DDT) process in future. In Pagosa, spatial discretization is implemented on cubic staggered grids by computing different variables at the vertex and the cell center, respectively, a special operator-splitting technique is employed to reduce the computational cost, and an artificial viscosity is added to handle the discontinuous shock waves in our simulations. To quantitatively evaluate the capability of Pagosa to solve these kinds of instabilities, the single mode Rayleigh-Taylor instability (RTI) and the multimode RMI at an air/SF 6 interface are first performed, respectively. The Pagosa results are compared with the related numerical solutions in the existing references and the experimental result. Moreover, a theoretical derivation of growth of RTI is also provided based on our numerical method. Subsequently, we explore the multi-mode RMI at an air/HE interface as well as the effects of several factors using Pagosa. Numerical results show that Pagosa is a powerful toolset to generate the right structures and the amplitude of RTI and RMI at an air/SF 6 interface. The solid HE can be penetrated by a strong shock wave and forms RMI deformations. The RMI at an air/HE interface behaves very different than at an air/SF 6 interface, periodic, decreased oscillation is observed due to material character, and is very sensitive to the initial simulation settings, that is, a tiny change in physical quantities will lead to a remarkable RMI structure, which is also observed in a shock bubble interaction. The findings in this work are significant, and will present a new insight for the high explosive field.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2020

A coupled multipoint stress–multipoint flux mixed finite element method for the Biot system of poroelasticity

In this work, we present a mixed finite element method for a five-field formulation of the Biot system of poroelasticity that reduces to a cell-centered pressure–displacement system on simplicial and quadrilateral grids. A mixed stress–displacement–rotation formulation for elasticity with weak stress symmetry is coupled with a mixed velocity–pressure Darcy formulation. The spatial discretization is based on combining the multipoint stress mixed finite element (MSMFE) method for elasticity and the multipoint flux mixed finite element (MFMFE) method for Darcy flow. It uses the lowest order Brezzi–Douglas–Marini mixed finite element spaces for the poroelastic stress and Darcy velocity, piecewise constant displacement and pressure, and continuous piecewise linear or bilinear rotation. A vertex quadrature rule is applied to the velocity, stress, and stress–rotation bilinear forms, which block-diagonalizes the corresponding matrices and allows for local velocity, stress, and rotation elimination. This leads to a cell-centered positive-definite system for pressure and displacement at each time step. We perform error analysis for the semidiscrete and fully discrete formulations, establishing first order convergence for all variables in their natural norms. The numerical tests confirm the theoretical convergence rates and illustrate the locking-free property of the method.

42 ENGINEERING↗
DOE OSTI2021

GETaLM: A generator for electron tagger and luminosity monitor for electron - proton and ion collisions

The study of elastic bremsstrahlung and electron tagging in electron-proton or ion collisions is gaining importance with the planned construction of several experimental facilities focused on deep-inelastic scattering (DIS) measurements. This paper describes a program which generates bremsstrahlung photons in electron-proton and electron-ion interactions as well as scattered electrons in bremsstrahlung processes and in a quasi-real photon approximation to the general DIS process. Here, the effects of electron beam divergence and the spread of the interaction vertex are implemented. The program can be used as an input to simulations of instrumentation for bremsstrahlung photon detection, luminosity measurements, electron tagging, and the determination of the cross sections of corresponding processes.

73 NUCLEAR PHYSICS AND RADIATION PHYSICS↗
DOE OSTI2021

Accurate numerical, integral methods for computing drift-kinetic Trubnikov-Rosenbluth potentials

A novel numerical method is employed to compute the integral form of the axi-symmetric Trubnikov-Rosenbluth potentials. Two methods for quadrature in pitch-angle are described and their convergence properties are studied. Careful attention is given to quadrature over a singular Green's function. Here it is shown that an infinite series representation of the Green's function can be used more efficiently than its closed form involving complete elliptic integrals. Then a collocation method in speed, with its associated quadrature scheme, is laid out and its convergence properties are studied. Using the proposed scheme, accurate low-order moments of the field collision operator are obtained using relatively few velocity space degrees of freedom. The scheme is showcased by solving for the equilibrium, axi-symmetric bootstrap current in tokamaks. A C 0 Gauss-Lobatto-Legendre finite element pitch-angle basis with vertex nodes at the trapped/passing boundary is shown, in the context of the integral methods used, to be much more efficient than the more common Legendre polynomial expansion.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗
DOE OSTI2026

Simulations of grain growth in tungsten armor materials under ARC plasma edge operation conditions using an integrated plasma-edge/materials model

An integrated model of grain growth deuterium-exposed tungsten polycrystals, consisting of a two-dimensional vertex dynamics model fitted to atomistic data, has been developed to assess the grain growth kinetics of deuterium-exposed polycrystalline tungsten (W). The model tracks the motion of grain boundaries under the effect of driving forces stemming from grain boundary curvature and differential deuterium concentration accumulation. Here, we apply the model to experimentally synthesized tungsten polycrystals under deuterium-saturated conditions relevant to the ARC concept design. The results indicate rapid grain growth kinetics in the near-surface region adjacent to the plasma, where the temperature reaches 1400 K, whereas the microstructure remains stable deeper in the material with the lower temperature of 1000 K. The combined modeling and analysis further reveal that monolithic tungsten produced via conventional fabrication routes is highly susceptible to grain coarsening at temperatures exceeding 1000 K, largely independent of the magnitude of the applied driving force. Moreover, the accumulation of deuterium near grain boundaries has a pronounced inhibitory effect on grain boundary migration. High-angle grain boundaries ( > 50°) contribute more significantly to the overall grain growth process.

36 MATERIALS SCIENCE↗
DOE OSTI2023

Distributed approximate minimal Steiner trees with millions of seed vertices on billion-edge graphs

In this report, we present a parallel 2-approximation Steiner minimal tree algorithm and its MPI-based distributed implementation. In place of expensive distance computations between all pairs of seed vertices, the solution we employ exploits a cheaper Voronoi cell computation. Our design leverages asynchronous processing and message prioritization to accelerate convergence of distance computations, and harnesses vertex and edge centric processing to offer fast time-to-solution. We demonstrate scalability and performance using real-world graphs with up to 128 billion edges and 512 compute nodes, and show the ability to find Steiner trees with up to one million seed vertices. Using 12 data instances, we present comparison with the state-of-the-art exact solver, SCIP-Jack, and two sequential 2-approximate algorithms. We empirically show that, on average, the total distance of the Steiner tree identified by our solution is 1.1290 times greater than the Steiner minimal tree – well within the theoretical approximation bound of 2.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2021

Tunning the linkage of structure units to enable stable spinel-based cathode in the wide potential window

The low practical capacity (<140 mA h g –1 ) of spinel phase LiMn 2–x Ni x O 4 (0 < x < 1) excludes it from high energy density lithium ion batteries (LIBs) for powering electric vehicles. Extending the operating potential window from 3.0 to 4.8 V to 2.0–4.8 V can double the capacity, but result in fast capacity decay due to the drastic cubic-tetragonal phase transition below 3.0 V, induced by serious Jahn-Teller (J-T) distortion of structure units (Mn 3+ )O 6 octahedra. Herein, we propose a novel strategy to suppress J-T distortion by tuning the linkage of structure units MnO 6 octahedra. The original full-vertex-sharing LiO 4 tetrahedra around MnO 6 octahedra in spinel phase are partially replaced by edge-sharing LiO 6 octahedra, which relate Mn-O bonds along the dz 2 direction with those along the d xy plane, thus significantly mitigating J-T distortion and suppressing the phase transition when discharged to 2.0 V. Following this strategy, the prepared spinel-based cathode achieves a high reversible capacity of about 290 mA h g –1 and an energy density up to 957 W h kg –1 with improved cycling stability. Furthermore, this work finds a new opportunity for the traditional spinel cathode towards applications in high energy density LIBs in a low cost and sustainable manner.

25 ENERGY STORAGE↗
DOE OSTI2020

Design and performance of silicon strip sensors with slim edges for HPS experiment

In this paper, we report on design and performance of new strip sensors for the Heavy Photon Search (HPS) experiment. The sensors feature a slim edge implementation using the Scribe–Cleave–Passivate (SCP) method. The slim edge design has allowed the introduction of a new layer closer to the target, which increased the tracking acceptance and vertex precision, improving physics reach of the experiment. We describe the production, testing, and operational experience with the new sensors.

46 INSTRUMENTATION RELATED TO NUCLEAR SCIENCE AND ↗