Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “graph coloring”

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 55 records · Page 3
All sourcesNASA NTRSDOE OSTI
NASA NTRS2017

QSPIN: A High Level Java API for Quantum Computing Experimentation

QSPIN is a high level Java language API for experimentation in QC models used in the calculation of Ising spin glass ground states and related quadratic unconstrained binary optimization (QUBO) problems. The Java API is intended to facilitate research in advanced QC algorithms such as hybrid quantum-classical solvers, automatic selection of constraint and optimization parameters, and techniques for the correction and mitigation of model and solution errors. QSPIN includes high level solver objects tailored to the D-Wave quantum annealing architecture that implement hybrid quantum-classical algorithms [Booth et al.] for solving large problems on small quantum devices, elimination of variables via roof duality, and classical computing optimization methods such as GPU accelerated simulated annealing and tabu search for comparison. A test suite of documented NP-complete applications ranging from graph coloring, covering, and partitioning to integer programming and scheduling are provided to demonstrate current capabilities.

Quantu↗
NASA NTRS2018

XY vs X Mixer in Quantum Alternating Operator Ansatz for Optimization Problems with Constraints

Quantum Approximate Optimization Algorithm, further generalized as Quantum Alternating Operator Ansatz (QAOA), is a family of algorithms for combinatorial optimization problems. It is a leading candidate to run on emerging universal quantum computers to gain insight into quantum heuristics. In constrained optimization, penalties are often introduced so that the ground state of the cost Hamiltonian encodes the solution (a standard practice in quantum annealing). An alternative is to choose a mixing Hamiltonian such that the constraint corresponds to a constant of motion and the quantum evolution stays in the feasible subspace. Better performance of the algorithm is speculated due to a much smaller search space. We consider problems with a constant Hamming weight as the constraint. We also compare different methods of generating the generalized W-state, which serves as a natural initial state for the Hamming-weight constraint. Using graph-coloring as an example, we compare the performance of using XY model as a mixer that preserves the Hamming weight with the performance of adding a penalty term in the cost Hamiltonian.

quantum computing↗
DOE OSTI2017

Frog: Asynchronous Graph Processing on GPU with Hybrid Coloring Model

GPUs have been increasingly used to accelerate graph processing for complicated computational problems regarding graph theory. Many parallel graph algorithms adopt the asynchronous computing model to accelerate the iterative convergence. Unfortunately, the consistent asynchronous computing requires locking or atomic operations, leading to significant penalties/overheads when implemented on GPUs. As such, coloring algorithm is adopted to separate the vertices with potential updating conflicts, guaranteeing the consistency/correctness of the parallel processing. Common coloring algorithms, however, may suffer from low parallelism because of a large number of colors generally required for processing a large-scale graph with billions of vertices. We propose a light-weight asynchronous processing framework called Frog with a preprocessing/hybrid coloring model. The fundamental idea is based on Pareto principle (or 80-20 rule) about coloring algorithms as we observed through masses of realworld graph coloring cases. We find that a majority of vertices (about 80%) are colored with only a few colors, such that they can be read and updated in a very high degree of parallelism without violating the sequential consistency. Accordingly, our solution separates the processing of the vertices based on the distribution of colors. In this work, we mainly answer three questions: (1) how to partition the vertices in a sparse graph with maximized parallelism, (2) how to process large-scale graphs that cannot fit into GPU memory, and (3) how to reduce the overhead of data transfers on PCIe while processing each partition. Here, we conduct experiments on real-world data (Amazon, DBLP, YouTube, RoadNet-CA, WikiTalk and Twitter) to evaluate our approach and make comparisons with well-known non-preprocessed (such as Totem, Medusa, MapGraph and Gunrock) and preprocessed (Cusha) approaches, by testing four classical algorithms (BFS, PageRank, SSSP and CC). On all the tested applications and datasets, Frog is able to significantly outperform existing GPU-based graph processing systems except Gunrock and MapGraph. MapGraph gets better performance than Frog when running BFS on RoadNet-CA. The comparison between Gunrock and Frog is inconclusive. Frog can outperform Gunrock more than 1.04X when running PageRank and SSSP, while the advantage of Frog is not obvious when running BFS and CC on some datasets especially for RoadNet-CA.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2022

CONGO²: Scalable Online Anomaly Detection and Localization in Power Electronics Networks

Rapid and accurate detection and localization of electronic disturbances simultaneously are important for preventing its potential damages and determining potential remedies. Existing anomaly detection methods are severely limited by the low accuracy, the expensive computational cost and the need for highly trained personnel. There is an urgent need for a scalable online algorithm for in-field analysis of large-scale power electronics networks. Here in this paper, we propose a fast and accurate algorithm for anomaly detection and localization of power electronics networks: stratified colored-node graph (CONGO2). This algorithm hierarchically models the change of correlated waveforms and then correlated sensors using the colored-node graph. By aggregating the change of each sensor with its neighbors’ inputs, we can spontaneously identify and localize the anomaly that cannot be detected by data collected from a single sensor. As our proposed method only focuses on the changes within a short time frame, it is highly computational efficient and only needs small data storage. Thus, our method is ideal for online and reliable anomaly detection and localization of large-scale power electronic networks. Compared to existing anomaly detection methods, our method is entirely data-driven without training data, highly accurate and reliable for wide-spectrum anomalies detection, and more importantly, capable of both detection and localization. Thus, it is ideal for infield deployment for large-scale power electronic networks. As illustrated by a distributed energy resources (DERs) power grid with 37-node, our method can effectively detect and localize various cyber and physical attacks.

42 ENGINEERING↗
DOE OSTI2017

(4,2)-choosability of planar graphs with forbidden structures

All planar graphs are 4-colorable and 5-choosable, while some planar graphs are not 4-choosable. Determining which properties guarantee that a planar graph can be colored using lists of size four has received significant attention. In terms of constraining the structure of the graph, for any l ? {3, 4, 5, 6, 7}, a planar graph is 4-choosable if it is l-cycle-free. In terms of constraining the list assignment, one refinement of k-choosability is choosability with separation. A graph is (k, s)-choosable if the graph is colorable from lists of size k where adjacent vertices have at most s common colors in their lists. Every planar graph is (4, 1)-choosable, but there exist planar graphs that are not (4, 3)-choosable. It is an open question whether planar graphs are always (4, 2)-choosable. A chorded l-cycle is an l-cycle with one additional edge. We demonstrate for each l ? {5, 6, 7} that a planar graph is (4, 2)-choosable if it does not contain chorded l-cycles.

li, ch↗
DOE OSTI2016

A graph-theoretical representation of multiphoton resonance processes in superconducting quantum circuits

We propose a graph-theoretical formalism to study generic circuit quantum electrodynamics systems consisting of a two level qubit coupled with a single-mode resonator in arbitrary coupling strength regimes beyond rotating-wave approximation. We define colored-weighted graphs, and introduce different products between them to investigate the dynamics of superconducting qubits in transverse, longitudinal, and bidirectional coupling schemes. In conclusion, the intuitive and predictive picture provided by this method, and the simplicity of the mathematical construction, are demonstrated with some numerical studies of the multiphoton resonance processes and quantum interference phenomena for the superconducting qubit systems driven by intense ac fields.

75 CONDENSED MATTER PHYSICS, SUPERCONDUCTIVITY AND↗
DOE OSTI2019

A Synchronization-Avoiding Distance-1 Grundy Coloring Algorithm for Power-Law Graphs

In this paper, we propose a distributed, unordered, label-correcting distance-1 Grundy (vertex) coloring algorithm, namely, Distributed Control (DC) coloring algorithm. Our algorithm eliminates the need for vertex-centric barriers and global synchronization for color refinement, relying only on atomic operations and local termination detection to update vertex color. DC proceeds optimistically, correcting the colors asynchronously as the algorithm progresses and depends on local ordering of tasks to minimize the execution of sub-optimal work. We implement our DC coloring algorithm and the well-known Jones-Plassmann algorithm and compare their performance with 4 different types of standard RMAT graphs and real-world graphs. We show that the elimination of waiting time of global and vertex-centric barriers and investing this time for local ordering leads to improved scaling for graphs with prominent power-law characteristics and densely interconnected local subgraphs.

Firoz, Jesun S.↗
NASA NTRS2001

Studying Earth's Environment From Space: Classroom and Laboratory Activities with Instructor Resources

Standard, text-book based learning for earth, ocean, and atmospheric sciences has been limited by the unavailability of quantitative teaching materials. While a descriptive presentation, in a lecture format, of discrete satellite images is often adequate for high school classrooms, this is seldom the case at the undergraduate level. In order to address these concerns, a series of numerical exercises for the Macintosh was developed for use with satellite-derived Sea Surface Temperature, pigment and sea ice concentration data. Using a modified version of NIH Image, to analyze actual satellite data, students are able to better understand ocean processes, such as circulation, upwelling, primary production, and ocean/atmosphere coupling. Graphical plots, image math, and numerical comparisons are utilized to substantiate temporal and spatial trends in sea surface temperature and ocean color. Particularly for institutions that do not offer a program in remote sensing, the subject matter is presented as modular units, each of which can be readily incorporated into existing curricula. These materials have been produced in both CD-ROM and WWW format, making them useful for classroom or lab setting. Depending upon the level of available computer support, graphics can be displayed directly from the CD-ROM, or as a series of color view graphs for standard overhead projection.

Smith, Elizabeth A.↗
NASA NTRSDate not supplied

Dynamic Channel Assignments for Efficient Use of Aviation Spectrum Allocations

The demand for voice and data communications continues to rise with the emergence of new aerial vehicles into the airspace and the continued growth of aviation operations throughout the National Airspace System (NAS). Recent studies have shown that the anticipated growing demand for spectrum resources will exceed the capacity of existing aviation spectrum allocations. Further, airspace configurations, via assignment of fixed channel allocations within standard service volumes, do not allow for the dynamic and efficient distribution of spectrum resources based on airspace demand; as a result, a new approach to aviation spectrum management is needed to support the forecasted needs of new airspace users. The National Aeronautics and Space Administration (NASA) is investigating applications of artificial intelligence (AI), machine learning (ML), and other advanced concepts to solve a dynamic constraint satisfaction problem which is analogous to the frequency assignment problem faced by aviation. Procedures and strategies for dynamic channel allocation can be borrowed from other large-scale mobile services (i.e., 4G/5G applications) and can provide a novel spectrum management approach that allows for the intelligent utilization of aviation spectrum throughout the airspace while maintaining the strict quality of service prescribed by aeronautical standards.

Communications↗
NASA NTRSDate not supplied

Dynamic Channel Assignments for Efficient Use of Aviation Spectrum Allocations

The demand for voice and data communications continues to rise with the emergence of new aerial vehicles into the airspace and the continued growth of aviation operations throughout the National Airspace System (NAS). Recent studies have shown that the anticipated growing demand for spectrum resources will exceed the capacity of existing aviation spectrum allocations. Further, airspace configurations, via assignment of fixed channel allocations within standard service volumes, do not allow for the dynamic and efficient distribution of spectrum resources based on airspace demand; as a result, a new approach to aviation spectrum management is needed to support the forecasted needs of new airspace users. The National Aeronautics and Space Administration (NASA) is investigating applications of artificial intelligence (AI), machine learning (ML), and other advanced concepts to solve a dynamic constraint satisfaction problem which is analogous to the frequency assignment problem faced by aviation. Procedures and strategies for dynamic channel allocation can be borrowed from other large-scale mobile services (i.e., 4G/5G applications) and can provide a novel spectrum management approach that allows for the intelligent utilization of aviation spectrum throughout the airspace while maintaining the strict quality of service prescribed by aeronautical standards.

communications↗
DOE OSTI2019

Ordering of Trotterization: Impact on Errors in Quantum Simulation of Electronic Structure

Trotter–Suzuki decompositions are frequently used in the quantum simulation of quantum chemistry. They transform the evolution operator into a form implementable on a quantum device, while incurring an error—the Trotter error. The Trotter error can be made arbitrarily small by increasing the Trotter number. However, this increases the length of the quantum circuits required, which may be impractical. It is therefore desirable to find methods of reducing the Trotter error through alternate means. The Trotter error is dependent on the order in which individual term unitaries are applied. Due to the factorial growth in the number of possible orderings with respect to the number of terms, finding an optimal strategy for ordering Trotter sequences is difficult. In this paper, we propose three ordering strategies, and assess their impact on the Trotter error incurred. Initially, we exhaustively examine the possible orderings for molecular hydrogen in a STO-3G basis. We demonstrate how the optimal ordering scheme depends on the compatibility graph of the Hamiltonian, and show how it varies with increasing bond length. We then use 44 molecular Hamiltonians to evaluate two strategies based on coloring their incompatibility graphs, while considering the properties of the obtained colorings. We find that the Trotter error for most systems involving heavy atoms, using a reference magnitude ordering, is less than 1 kcal/mol. Relative to this, the difference between ordering schemes can be substantial, being approximately on the order of millihartrees. The coloring-based ordering schemes are reasonably promising—particularly for systems involving heavy atoms—however further work is required to increase dependence on the magnitude of terms. Finally, we consider ordering strategies based on the norm of the Trotter error operator, including an iterative method for generating the new error operator terms added upon insertion of a term into an ordered Hamiltonian.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2013

Hierarchical probing for estimating the trace of the matrix inverse on toroidal lattices

The standard approach for computing the trace of the inverse of a very large, sparse matrix $A$ is to view the trace as the mean value of matrix quadratures, and use the Monte Carlo algorithm to estimate it. This approach is heavily used in our motivating application of Lattice QCD. Often, the elements of $A^{-1}$ display certain decay properties away from the non zero structure of $A$, but random vectors cannot exploit this induced structure of $A^{-1}$. Probing is a technique that, given a sparsity pattern of $A$, discovers elements of $A$ through matrix-vector multiplications with specially designed vectors. In the case of $A^{-1}$, the pattern is obtained by distance-$k$ coloring of the graph of $A$. For sufficiently large $k$, the method produces accurate trace estimates but the cost of producing the colorings becomes prohibitively expensive. More importantly, it is difficult to search for an optimal $k$ value, since none of the work for prior choices of $k$ can be reused.

Stathopoulos, Andreas↗
NASA NTRS2010

Math Description Engine Software Development Kit

The Math Description Engine Software Development Kit (MDE SDK) can be used by software developers to make computer-rendered graphs more accessible to blind and visually-impaired users. The MDE SDK generates alternative graph descriptions in two forms: textual descriptions and non-verbal sound renderings, or sonification. It also enables display of an animated trace of a graph sonification on a visual graph component, with color and line-thickness options for users having low vision or color-related impairments. A set of accessible graphical user interface widgets is provided for operation by end users and for control of accessible graph displays. Version 1.0 of the MDE SDK generates text descriptions for 2D graphs commonly seen in math and science curriculum (and practice). The mathematically rich text descriptions can also serve as a virtual math and science assistant for blind and sighted users, making graphs more accessible for everyone. The MDE SDK has a simple application programming interface (API) that makes it easy for programmers and Web-site developers to make graphs accessible with just a few lines of code. The source code is written in Java for cross-platform compatibility and to take advantage of Java s built-in support for building accessible software application interfaces. Compiled-library and NASA Open Source versions are available with API documentation and Programmer s Guide at http:/ / prim e.jsc.n asa. gov.

Shelton, Robert O.↗
DOE OSTI2023

Perfecting one-loop BCJ numerators in SYM and supergravity

We take a major step towards computing D-dimensional one-loop amplitudes in general gauge theories, compatible with the principles of unitarity and the color-kinematics duality. For n-point amplitudes with either supersymmetry multiplets or generic non-supersymmetric matter in the loop, simple all-multiplicity expressions are obtained for the maximal cuts of kinematic numerators of n-gon diagrams. At n = 6, 7 points with maximal supersymmetry, we extend the cubic-diagram numerators to encode all contact terms, and thus solve the long-standing problem of simultaneously realizing the following properties: color-kinematics duality, manifest locality, optimal power counting of loop momenta, quadratic rather than linearized Feynman propagators, compatibility with double copy as well as all graph symmetries. Color-kinematics dual representations with similar properties are presented in the half-maximally supersymmetric case at n = 4, 5 points. The resulting gauge-theory integrands and their supergravity counterparts obtained from the double copy are checked to reproduce the expected ultraviolet divergences.

72 PHYSICS OF ELEMENTARY PARTICLES AND FIELDS↗
NASA NTRSDate not supplied

Influence of Thermophysical Property Variability on Thermal Predictions of Ti-6Al-4V

The additive manufacturing (AM) industry has experienced rapid growth in recent decades as industrial interest in the process has grown. Because of this, there are many groups interested in simulations of the AM process. However, the influence of thermophysical property variability on the melt pool geometry during processing of various AM alloys is unclear. The goal of my work at NASA Langley Research Center (LaRC) was to characterize this influence on Ti-6Al-4V during AM processing alongside developing a tool to enable equivalent studies on other AM materials. To facilitate this process, a database tool was developed to contain and organize thermophysical data previously reported by primary sources. The specific thermophysical properties of interest for this study were density, specific heat capacity, and conductivity. Thermal diffusivity was calculated using the other three properties. This data was then fit with a Gaussian distribution and then randomly sampled from using Monte Carlo random value sampling. Using the Rosenthal equation, this sample data was used to simulate the temperature field during additive manufacturing and extract the melt pool geometry. Specifically, the melt pool’s length, width, and depth. This process was repeated an arbitrary number of times, with the default being 1000. Once this information was obtained, histograms were made showing the distributions of the sizes of the melt pool’s length, width, and depth. Representative statistical metrics of the distributions were calculated (mean, standard deviation, and coefficient of variance). This work found that at the simulated processing values, the melt pool’s width and depth had a 5.7% variation while the length had a 3.2% variation. Additionally, a tool was constructed to graph a thermal color map representation of the melt pool for specific, arbitrary values of density, specific heat, and conductivity. This tool allowed for more efficient plotting of individual queries of the thermophysical properties. The results that were observed in the research were that values reported in literature vary and this variance can have a significant impact on the simulation. Predictions of the melt pool’s dimensions show that length has a standard deviation of approximately 6 μm, width has a standard deviation of approximately 5 μm, and depth can vary by approximately 3 μm. Considering the mean sizes of length, width, and depth are 185 μm, 88 μm, and 44 μm respectively, such a deviation is significant. This shows that depth, for example, could be more than 10% larger or smaller than expected. This demonstrates that variability in the reported thermophysical properties are not negligible and should be expected to have an influence on the results of the laser powder bed fusion additive manufacturing process. When simulating this process in the future, measures should be taken to account for this discrepancy and the uncertainty involved

Justin Martin↗
DOE OSTI2013

Homological stabilizer codes

In this paper we define homological stabilizer codes on qubits which encompass codes such as Kitaev's toric code and the topological color codes. These codes are defined solely by the graphs they reside on. This feature allows us to use properties of topological graph theory to determine the graphs which are suitable as homological stabilizer codes. We then show that all toric codes are equivalent to homological stabilizer codes on 4-valent graphs. We show that the topological color codes and toric codes correspond to two distinct classes of graphs. We define the notion of label set equivalencies and show that under a small set of constraints the only homological stabilizer codes without local logical operators are equivalent to Kitaev's toric code or to the topological color codes. - Highlights: Black-Right-Pointing-Pointer We show that Kitaev's toric codes are equivalent to homological stabilizer codes on 4-valent graphs. Black-Right-Pointing-Pointer We show that toric codes and color codes correspond to homological stabilizer codes on distinct graphs. Black-Right-Pointing-Pointer We find and classify all 2D homological stabilizer codes. Black-Right-Pointing-Pointer We find optimal codes among the homological stabilizer codes.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗