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,099 records · Page 61

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.↗

Transport, hysteresis and avalanches in artificial spin ice systems

We examine the hopping dynamics of an artificial spin ice system constructed from colloids on a kagome optical trap array where each trap has two possible states. By applying an external drive from an electric field which is analogous to a biasing applied magnetic field for real spin systems, we can create polarized states that obey the spin-ice rules of two spins in and one spin out at each vertex. We demonstrate that when we sweep the external drive and measure the fraction of the system that has been polarized, we can generate a hysteresis loop analogous to the hysteretic magnetization versus external magnetic field curves for real spin systems. The disorder in our system can be readily controlled by changing the barrier that must be overcome before a colloid can hop from one side of a trap to the other. For systems with no disorder, the effective spins all flip simultaneously as the biasing field is changed, while for strong disorder the hysteresis curves show a series of discontinuous jumps or avalanches similar to Barkhausen noise.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

Topological defects from doping and quenched disorder in artificial ice systems

We examine the ice-rule obeying and ice-rule breaking vertices in an artificial spin ice system created using magnetic vortices in type-II superconductors with nanostructured pinning arrays. We show that this system can be doped by changing the external field to move the number of vortices away from commensurability and create sites that contain two or zero vortices. For a square ice, the doping leads to the formation of a grain boundary of vertices that do not obey the ice rules. In commensurate systems where the ice rules are obeyed, we can introduce random disorder at the individual pinning sites to create regions where vortices may not be able to flip from one side of the trap to another. For weak disorder, all of the vertices still obey the ice rules, while at intermediate levels of disorder we find grain boundaries of vertices which do not obey the ice rules. For strong disorder it is possible to create isolated paired vertices that do not obey the ice rules. In summary, we have shown that an artificial square ice can be created using vortices in a type-II superconductor interacting with a periodic array of pinning sites where each site has a double well potential. By defining the direction of the effective spin according to the side of the double well occupied by the vortex, we find that this system obeys the ice rules for square ice. We add disorder to the system in the form of randomness of the height of the potential barrier at the center of the well, and obtain vertex configurations using a rotating drive protocol which is similar to the shaking ac magnetic field used in nanomagnetic systems. For weak disorder the entire system still obeys the square ice rules. For intermediate disorder, ice-rule breaking vertices appear and form grain boundaries, while for strong disorder there are both gain boundaries and isolated paired defects. In a system with uniform potential barrier heights, we introduce disorder by moving away from commensurability and creating Home pinning sites that contain two or zero vortices. In this case we find grain boundaries that emanate from the defect site and span the sample.

36 MATERIALS SCIENCE↗

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↗

A hybrid electron and photon IMRT planning technique that lowers normal tissue integral patient dose using standard hardware

Purpose: To present a mixed electron and photon IMRT planning technique using electron beams with an energy range of 6-22 MeV and standard hardware that minimizes integral dose to patients for targets as deep as 7.5 cm. Methods: Ten brain cases, two lung, a thyroid, an abdominal, and a parotid case were planned using two planning techniques: a photon-only IMRT (IMRT) versus a mixed modality treatment (E + IMRT) that includes an enface electron beam and a photon IMRT portion that ensures a uniform target coverage. The electron beam is delivered using a regular cutout placed in an electron cone. The electron energy was chosen to provide a good trade-off between minimizing integral dose and generating a uniform, deliverable plan. The authors choose electron energies that cover the deepest part of PTV with the 65%-70% isodose line. The normal tissue integral dose, the dose for ring structures around the PTV, and the volumes of the 75%, 50%, and 25% isosurfaces were used to compare the dose distributions generated by the two planning techniques. Results: The normal tissue integral dose was lowered by about 20% by the E + IMRT plans compared to the photon-only IMRT ones for most studied cases. With the exception of lungs, the dose reduction associated to the E + IMRT plans was more pronounced further away from the target. The average dose ratio delivered to the 0-2 cm and the 2-4 cm ring structures for brain patients for the two planning techniques were 89.6% and 70.8%, respectively. The enhanced dose sparing away from the target for the brain patients can also be observed in the ratio of the 75%, 50%, and 25% isodose line volumes for the two techniques, which decreases from 85.5% to 72.6% and further to 65.1%, respectively. For lungs, the lateral electron beams used in the E + IMRT plans were perpendicular to the mostly anterior/posterior photon beams, generating much more conformal plans. Conclusions: The authors proved that even using the existing electron delivery hardware, a mixed electron/photon planning technique (E + IMRT) can decrease the normal tissue integral dose compared to a photon-only IMRT plan. Different planning approaches can be enabled by the use of an electron beam directed toward organs at risk distal to the target, which are still spared due the rapid dose fall-off of the electron beam. Examples of such cases are the lateral electron beams in the thoracic region that do not irradiate the heart and contralateral lung, electron beams pointed toward kidneys in the abdominal region, or beams treating brain lesions pointed toward the brainstem or optical apparatus. For brain, electron vertex beams can also be used without irradiating the whole body. Since radiation retreatments become more and more common, minimizing the normal tissue integral dose and the dose delivered to tissues surrounding the target, as enabled by E + IMRT type techniques, should receive more attention.

62 RADIOLOGY AND NUCLEAR MEDICINE↗