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 1,063 records · Page 59

Dipolar Cairo lattice: Geometrical frustration and short-range correlations

We have studied low-energy configurations in two-dimensional arrays consisting of Ising-type dipolar coupled nanomagnets lithographically defined onto a two-dimensional Cairo lattice, thus dubbed the dipolar Cairo lattice. Employing synchrotron-based photoemission electron microscopy (PEEM), we perform real-space imaging of moment configurations achieved after thermal annealing. These states are then characterized in terms of vertex populations, spin- and emergent magnetic charge correlations, and a topology-enforced emergent ice rule. The results reveal a strong dominance of short-range correlations and the absence of long-range order, reflecting the high degree of geometrical spin frustration present in this example of an artificial frustrated spin system.

36 MATERIALS SCIENCE↗

Low-depth Clifford circuits approximately solve MaxCut

We introduce a quantum-inspired approximation algorithm for MaxCut based on low-depth Clifford circuits. We start by showing that the solution unitaries found by the adaptive quantum approximation optimization algorithm (ADAPT-QAOA) for the MaxCut problem on weighted fully connected graphs are (almost) Clifford circuits. Motivated by this observation, we devise an approximation algorithm for MaxCut, ADAPT-Clifford, that searches through the Clifford manifold by combining a minimal set of generating elements of the Clifford group. Our algorithm finds an approximate solution of MaxCut on an N -vertex graph by building a depth O ( N ) Clifford circuit. The algorithm has runtime complexity O ( N 2 ) and O ( N 3 ) for sparse and dense graphs, respectively, and space complexity O ( N 2 ) , with improved solution quality achieved at the expense of more demanding runtimes. We implement ADAPT-Clifford and characterize its performance on graphs with positive and signed weights. The case of signed weights is illustrated with the paradigmatic Sherrington-Kirkpatrick model, for which our algorithm finds solutions with ground-state mean energy density corresponding to ∼ 94 % of the Parisi value in the thermodynamic limit. The case of positive weights is investigated by comparing the cut found by ADAPT-Clifford with the cut found with the Goemans-Williamson (GW) algorithm. For both sparse and dense instances we provide copious evidence that, up to hundreds of nodes, ADAPT-Clifford finds cuts of lower energy than GW. Published by the American Physical Society 2024

Muñoz-Arias, Manuel H. (ORCID:000000025711029X)↗

Search for displaced leptons in $\sqrt{𝑠}$ =13 TeV and 13.6 TeV 𝑝⁢𝑝 collisions with the ATLAS detector

A search for leptons displaced from the primary vertex is performed with the ATLAS detector at the Large Hadron Collider. The search includes the full proton-proton collision dataset collected during Run 2 at $\sqrt{𝑠}$ = 13 TeV and a partial dataset collected during Run 3 in 2022–2023 at $\sqrt{𝑠}$ = 13.6 TeV, corresponding to integrated luminosities of 140 fb −1 and 56.3 fb −1 , respectively. Final states with displaced electrons or muons are considered, and novel triggers introduced in Run 3 are employed that use large impact parameter tracking to reconstruct displaced tracks with low momentum. In addition, photon reconstruction and multivariate techniques are employed to broaden the sensitivity to channels with large background rates or highly displaced electrons, respectively. The results are consistent with the Standard Model background expectations and are used to set model-independent limits on the production of displaced electrons and muons. The analysis is also interpreted in the context of a gauge-mediated supersymmetry breaking model with pair-produced long-lived sleptons and a dark sector model with pair-produced chargino-like states. The results include 95% confidence level exclusions of selectrons with lifetimes from 4 ps to 60 ns and a mass of 150 GeV, and exclusions of selectrons, smuons, and staus with a lifetime of 0.3 ns for masses up to 740, 830, and 440 GeV, respectively. Dark charginos with masses up to 380 GeV are excluded for a mass difference with the neutral state of 40 GeV, and mass differences down to 17 GeV are excluded for dark charginos with a 100 GeV mass.

supersymmetric models↗

Poly[[(acetonitrile)lithium(I)]-μ 3 -tetrafluoridoborato]

The structure of the title compound, [Li(BF4)(CH3CN)]n, consists of a layered arrangement parallel to (100) in which the Li+ cations are coordinated by three F atoms from three tetrafluoridoborate (BF4 ) anions and an N atom from an acetonitrile molecule. The BF4 anion is coordinated to three different Li+ cations though three F atoms. The structure can be described as being built from vertex-shared BF4 and LiF3(NCCH3) tetrahedra. These tetrahedra reside around a crystallographic inversion center and form 8-membered rings.

36 MATERIALS SCIENCE↗

Derivation of closed-form ellipsoidal X-ray mirror shapes from Fermat's principle

Ellipsoidal and plane-elliptical surfaces are widely used as reflective, point-to-point focusing elements in many optical systems, including X-ray optics. Here the classical optical path function approach of Fermat is applied to derive a closed-form expression for these surfaces that are uniquely described by the object and image distances and the angle of incidence at a point on a mirror surface. A compact description facilitates design, modeling, fabrication, and testing to arbitrary accuracy. Congruent surfaces in two useful coordinate systems — a system centered on the ellipsoid's axes of symmetry and a mirror-centered or `vertex' system with the surface tangent to the xy plane at the mirror's center — are presented. Expressions for the local slope and radii of curvature are derived from the result, and the first several terms of the Maclauren series expansion are provided about the mirror center.

73 NUCLEAR PHYSICS AND RADIATION PHYSICS↗

X-ray crystal structure of a designed rigidified imaging scaffold in the ligand-free conformation

Imaging scaffolds composed of designed protein cages fused to designed ankyrin repeat proteins (DARPins) have enabled the structure determination of small proteins by cryogenic electron microscopy (cryo-EM). One particularly well characterized scaffold type is a symmetric tetrahedral assembly composed of 24 subunits, 12 A and 12 B, which has three cargo-binding DARPins positioned on each vertex. Here, the X-ray crystal structure of a representative tetrahedral scaffold in the apo state is reported at 3.8 Å resolution. The X-ray crystal structure complements recent cryo-EM findings on a closely related scaffold, while also suggesting potential utility for crystallographic investigations. As observed in this crystal structure, one of the three DARPins, which serve as modular adaptors for binding diverse `cargo' proteins, present on each of the vertices is oriented towards a large solvent channel. The crystal lattice is unusually porous, suggesting that it may be possible to soak crystals of the scaffold with small (≤30 kDa) protein cargo ligands and subsequently determine cage–cargo structures via X-ray crystallography. The results suggest the possibility that cryo-EM scaffolds may be repurposed for structure determination by X-ray crystallography, thus extending the utility of electron-microscopy scaffold designs for alternative structural biology applications.

59 BASIC BIOLOGICAL SCIENCES↗

Synchronization-Avoiding Graph Algorithms

Because they were developed for optimal sequential complexity, classical graph algorithms as found in textbooks have strictly-defined orders of operations. Enforcing a prescribed order of operations, or even an approximate order, in a distributed memory setting requires significant amounts of synchronization, which in turn can severely limit scalability. As a result, new algorithms are typically required to achieve scalable performance, even for solving well-known graph problems. Yet, even in these cases, parallel graph algorithms are written according to parallel programming models that evolved for, e.g., scientific computing, and that still have inherent, and scalability-limiting, amounts of synchronization. In this paper we present a new approach to parallel graph algorithms: synchronization-avoiding algorithms. To eliminate synchronization and its associated overhead, synchronization-avoiding algorithms perform work in an unordered and fully asynchronous fashion in such a way that the result is constantly refined toward its final state. “Wasted” work is minimized by locally prioritizing tasks using problem-dependent task utility metrics. We classify algorithms for graph applications into two broad categories: algorithms with monotonic updates (which evince global synchronization) and algorithms with nonmonotonic updates (which evince vertex-centric synchronization). We apply our approach to both classes and develop novel, synchronization-avoiding algorithms for solving exemplar problems: SSSP and connected components for the former, graph coloring for the latter. We demonstrate that eliminating synchronization in conjunction with effective scheduling policies and optimizations in the runtime results in improved scalability for both classes of algorithms.

Firoz, Jesun S.↗

Massive Social Network Analysis: Mining Twitter for Social Good

Social networks produce an enormous quantity of data. Facebook consists of over 400 million active users sharing over 5 billion pieces of information each month. Analyzing this vast quantity of unstructured data presents challenges for software and hardware. We present GraphCT, a Graph Characterization Tooklit for massive graphs representing social network data. On a 128-processor Cray XMT, GraphCT estimates the betweenness centrality of an artificially generated (R-MAT) 537 million vertex, 8.6 billion edge graph in 55 minutes. We use GraphCT to analyze public data from Twitter, a microblogging network. Twitter's message connections appear primarily tree-structured as a news dissemination system. Within the public data, however, are clusters of conversations. Using GraphCT, we can rank actors within these conversations and help analysts focus attention on a much smaller data subset.

99 GENERAL AND MISCELLANEOUS↗

Distributed-memory Parallel Algorithms for Matching and Coloring

Graph matching and coloring constitute two fundamental classes of combinatorial problems having numerous established as well as emerging applications in computational science and engineering, high-performance computing, and informatics. We provide a snapshot of an on-going work on the design and implementation of new highly-scalable distributed-memory parallel algorithms for two prototypical problems from these classes, edge-weighted matching and distance-1 vertex coloring. Graph algorithms in general have low concurrency and poor data locality, making it challenging to achieve scalability on massively parallel machines. We overcome this challenge by employing a variety of techniques, including approximation, speculation and iteration, optimized communication, and randomization, in concert. We present preliminary results on weak and strong scalability studies conducted on an IBM Blue Gene/P machine employing up to tens of thousands of processors. The results show that the algorithms hold strong potential for computing at petascale.

Combinatorial scientific computing↗

Exploring MPI Communication Models for Graph Applications Using Graph Matching as a Case Study

Traditional implementations of parallel graph operations on distributed memory platforms are written using Message Passing Interface (MPI) point to point communication primitives such as Send-Recv (blocking and nonblocking). Apart from this classical model, the MPI community has over the years added other communication models; however, their suitability for handling the irregular traffic workloads typical of graph operations remain comparatively less explored. Our aim in this paper is to study these relatively underutilized communication models of MPI for graph applications. More specifically, we evaluate MPI’s one-sided programming, or Remote Memory Access (RMA), and nearest neighborhood collectives using a process graph topology. There are features in these newer models that are intended to better map to irregular communication patterns, as exemplified in graph algorithms. As a concrete application for our case study, we use distributed memory implementations of a weighted graph matching algorithm to investigate performances of MPI-3 RMA and neighborhood collective operations compared to nonblocking Send- Recv. A matching in a graph is a subset of edges such that no two matched edges are incident on the same vertex. A maximum weight matching is a matching of maximum weight computed as the sum of the weights of matched edges. Algorithms for optimal matching have quadratic complexity and are difficult to parallelize. More importantly, execution of graph matching is dominated by high volume of irregular memory accesses, making it an ideal candidate for studying the effects of various MPI communication models on graph applications at scale. Our neighborhood collectives and RMA implementations yields up to 6× speedup over traditional optimized nonblocking Send-Recv implementations, on thousands of cores of the NERSC Cori supercomputer. We believe the lessons learned from this case study can be adopted to benefit a wider range of graph application codes.

Ghosh, Sayan↗

Picasso: Memory-Efficient Graph Coloring Using Palettes With Applications in Quantum Computing

A coloring of a graph is an assignment of colors to vertices such that no two neighboring vertices have the same color. The need for memory-efficient coloring algorithms is motivated by their application in computing clique partitions of graphs arising in quantum computations where the objective is to map a large set of Pauli strings into a compact set of unitaries. We present Picasso, a randomized memory-efficient iterative parallel graph coloring algorithm with theoretical sublinear space guarantees under practical assumptions. The parameters of our algorithm provide a trade-off between coloring quality and resource consumption. To assist the user, we also propose a machine learning model to predict the coloring algorithm’s parameters considering these trade-offs. We provide a sequential and a parallel implementation of the proposed algorithm. We perform an experimental evaluation on a 64-core AMD CPU equipped with 512 GB of memory and an Nvidia A100 GPU with 40GB of memory. For a small dataset where existing coloring algorithms can be executed within the 512 GB memory budget, we show up to 68× memory savings. On massive datasets we demonstrate that GPU-accelerated Picasso can process inputs with 49.5× more Pauli strings (vertex set in our graph) and 2,478× more edges than state-of-the-art parallel approaches.

artificial intelligence, quantum computing↗

GraphReduce: Large-Scale Graph Analytics on Accelerator-Based HPC Systems

Recent work on real-world graph analytics has sought to leverage the massive amount of parallelism offered by GPU devices, but challenges remain due to the inherent irregularity of graph algorithms and limitations in GPU-resident memory for storing large graphs. We present GraphReduce, a highly efficient and scalable GPU-based framework that operates on graphs that exceed the device’s internal memory capacity. GraphReduce adopts a combination of both edge- and vertex-centric implementations of the Gather-Apply-Scatter programming model and operates on multiple asynchronous GPU streams to fully exploit the high degrees of parallelism in GPUs with efficient graph data movement between the host and the device.

Architecture optimization, reuse, performance, ene↗

Improving Performance of Multi-Area State Estimation Using Spectral Clustering

This paper investigates the problem of dividing a large power system into several areas to be solved by a state estimator which coordinates locally obtained decentralized estimates. By applying automatic partitioning to the utility system, the performance of the distributed state estimator can be improved as compared to the pre-defined utility control areas. The presented approach utilizes the spectral properties of the un-directed graph formed by assigning a vertex to every bus and an edge to every pair of buses connected by a line. The graph Laplacian matrix and associated eigenvectors and eigenvalues are used to cluster the graph vertices in such a way that each area has a large number of internal connections, but a small number of external connections. This approach is demonstrated using the IEEE 118 bus system.

Kelle, David↗

Towards Feature-Preserving 2D and 3D Vector Field Compression

The objective of this work is to develop error-bounded lossy compression methods to preserve topological features in 2D and 3D vector fields. Specifically, we explore the preservation of critical points in piecewise linear vector fields. We define the preservation of critical points as, without any false positive, false negative, or false type change in the decompressed data, (1) keeping each critical point in its original cell and (2) retaining the type of each critical point (e.g., saddle and attracting node). The key to our method is to adapt a vertex-wise error bound for each grid point and to compress input data together with the error bound field using a modified lossy compressor. Our compression algorithm can be also embarrassingly parallelized for large data handling and in situ processing. We benchmark our method by comparing it with existing lossy compressors in terms of false positive/negative/type rates, compression ratio, and various vector field visualizations with several scientific applications.

critical points↗

True Load Balancing for Matricized Tensor Times Khatri-Rao Product

MTTKRP is the bottleneck operation in algorithms used to compute the CP tensor decomposition. For sparse tensors, utilizing the compressed sparse fibers (CSF) storage format and the CSF-oriented MTTKRP algorithms is important for both memory and computational efficiency on distributed-memory architectures. Existing intelligent tensor partitioning models assume the computational cost of MTTKRP to be proportional to the total number of nonzeros in the tensor. However, this is not the case for the CSF-oriented MTTKRP on distributed-memory architectures. We outline two deficiencies of nonzero-based intelligent partitioning models when CSF-oriented MTTKRP operations are performed locally: failure to encode processors' computational loads and increase in total computation due to fiber fragmentation. We focus on existing fine-grain hypergraph model and propose a novel vertex weighting scheme that enables this model encode correct computational loads of processors. We also propose to augment the fine-grain model by fiber nets for reducing the increase in total computational load via minimizing fiber fragmentation. In this way, the proposed model encodes minimizing the load of the bottleneck processor. In conclusion, parallel experiments with real-world sparse tensors on up to 1024 processors prove the validity of the outlined deficiencies and demonstrate the merit of our proposed improvements in terms of parallel runtimes.

97 MATHEMATICS AND COMPUTING↗

Quickest Detection for Changes in Maximal kNN Coherence of Random Matrices

This paper addresses the problem of quickest detection of a change in the maximal coherence between columns of a n p random matrix based on a sequence of matrix observations having a single unknown change point. The random matrix is assumed to have identically distributed rows and the maximal coherence is defined as the largest of the ( 2 p) correlation coefficients associated with any row. Likewise the κ nearest neighbor (kNN) coherence is defined as the κ-th largest of these correlation coefficients. The forms of the preand postchange distributions of the observed matrices are assumed to belong to the family of elliptically contoured densities with sparse dispersion matrices but are otherwise unknown. A nonparametric stopping rule is proposed that is based on the maximal kNN sample coherence between columns of each observed random matrix. This is a summary statistic that is related to a test of existence of a hub vertex in a sample correlation graph having degree at least κ. Performance bounds on the delay and false alarm performance of the proposed stopping rule are obtained in the purely high-dimensional regime where p → ∞ and n is fixed. When the prechange dispersion matrix is diagonal it is shown that, among all functions of the proposed summary statistic, the proposed stopping rule is asymptotically optimal under a minimax quickest change detection model as the stopping threshold approaches infinity. Furthermore, the theory developed also applies to sequential hypothesis testing and fixed sample size tests.

96 KNOWLEDGE MANAGEMENT AND PRESERVATION↗

Simplex‐based model for nanoparticle grain identification in four‐dimensional scanning transmission electron microscopy data

Grain identification in polycrystalline nanoparticles, for example, determining which crystal phases are present at each spatial location, is fundamental to materials characterisation. This is particularly challenging when grains overlap extensively, as commonly occurs in four-dimensional scanning transmission electron microscopy (4D-STEM) datasets. We propose a simplex-based model (SBM) in which each simplex vertex represents the diffraction pattern (DP) of a pure grain, and the simplex edges and interior represent overlapping grains. Our SBM grain identification algorithm operates on the Bragg disk (BD) data matrix distilled from the 4D-STEM data to identify the grain membership at each scan position, together with a BD feature matrix whose columns represent the DPs for each constituent grain, which is important for identifying the crystal structure of each grain. We solve the model using a two-stage algorithm. In Stage 1, we adapt a linear mixing algorithm to estimate an initial BD feature matrix whose columns represent DPs of potentially overlapping grains. Our Stage 2 algorithm incorporates sparsity considerations to transform the initial BD feature matrix so that its columns represent DPs of pure grains. Using simulated datasets with various grain configurations, we demonstrate that SBM recovers both the BD feature matrix and membership maps more accurately than existing methods, even when a grain lacks any pure region and completely overlaps with other grains.

4D-STEM segmentation↗

Experimental and Numerical Analysis of Additively Manufactured Inconel 718 Coupons With Lattice Structure

Abstract In the present paper, two lattice geometries suitable for near surface and double wall cooling were developed and tested. The first type of unit cell consisted of six ligaments of 0.5 mm diameter joined at a common vertex near the middle. The second type of unit cell was derived from the first type by adding four mutually perpendicular ligaments in the middle plane. Two lattice configurations, referred to as L1 and L2, respectively, were obtained by repeating the corresponding unit cell in streamwise and spanwise directions in an inline fashion. Test coupons consisting of these lattice geometries embedded inside rectangular cooling channel with dimensions of 2.54 mm height, 38.07 mm width, and 38.1 mm in length were fabricated using Inconel 718 powder and selective laser sintering (SLS) process. The heat transfer and pressure drop performance was then evaluated using steady-state tests with constant wall temperature boundary condition and for channel Reynolds number ranging from 2800 to 15,000. The lattices depicted a higher heat transfer compared with a smooth channel and both the heat transfer and pressure drop increased with a decrease in the porosity from L1 to L2. Steady-state conjugate numerical results revealed formation of prominent vortical structures in the inter-unit cell spaces, which diverted the flow toward the top end wall and created an asymmetric heat transfer between the two end walls. In conclusion, these lattice structures provided an augmented heat transfer while favorably redistributing the coolant within channel.

Engineering↗