Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “Computational Complexity”

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 127 records · Page 7

A QUALITATIVE METHOD TO ESTIMATE HSI DISPLAY COMPLEXITY

There is mounting evidence that complex computer system displays in control rooms contribute to cognitive complexity and, thus, to the probability of human error. Research shows that reaction time increases and response accuracy decreases as the number of elements in the display screen increase. However, in terms of supporting the control room operator, approaches focusing on addressing display complexity solely in terms of information density and its location and patterning, will fall short of delivering a properly designed interface. This paper argues that information complexity and semantic complexity are mandatory components when considering display complexity and that the addition of these concepts assists in understanding and resolving differences between designers and the preferences and performance of operators. This paper concludes that a number of simplified methods, when combined, can be used to estimate the impact that a particular display may have on the operator's ability to perform a function accurately and effectively. We present a mixed qualitative and quantitative approach and a method for complexity estimation.

99 GENERAL AND MISCELLANEOUS↗

High Performance Descriptive Semantic Analysis of Semantic Graph Databases

As semantic graph database technology grows to address components ranging from extant large triple stores to SPARQL endpoints over SQL-structured relational databases, it will become increasingly important to be able to understand their inherent semantic structure, whether codified in explicit ontologies or not. Our group is researching novel methods for what we call descriptive semantic analysis of RDF triplestores, to serve purposes of analysis, interpretation, visualization, and optimization. But data size and computational complexity makes it increasingly necessary to bring high performance computational resources to bear on this task. Our research group built a novel high performance hybrid system comprising computational capability for semantic graph database processing utilizing the large multi-threaded architecture of the Cray XMT platform, conventional servers, and large data stores. In this paper we describe that architecture and our methods, and present the results of our analyses of basic properties, connected components, namespace interaction, and typed paths such for the Billion Triple Challenge 2010 dataset.

99 GENERAL AND MISCELLANEOUS↗

A Decision-Based Iterative Modeling Framework for Probabilistic Performance Assessments - 18441

Radiological probabilistic performance assessments (PPAs) employ highly complex computer models to simulate the release of radionuclides from wastes in an engineered disposal facility, migration of these radionuclides over time, and resulting radiological dose to potentially exposed individuals. An iterative approach to PPA modeling is described to help define the appropriate complexity of the computer model. An initial model is developed that addresses all relevant processes and media, but that employs preliminary statistical parameter distributions to minimize the initial effort expended. Where appropriate, transport and exposure submodels with simplifying assumptions are also used in the initial model. Different assumptions and boundaries may be explored with the initial model to assess their importance in constraining model results. Exploration of the results of the initial model are used to determine the benefits of model refinements, and to guide such refinements to focus on specific areas of the model that most influence the model outputs of interest. This approach promotes efficiency and model parsimony, but does not compromise defensibility when performed in a transparent manner. Key model boundaries for a PPA include the time frame of the modeling (temporal boundaries), where future human receptors may be located (spatial boundaries), and what types of land uses and activities may exist in the future (exposure scenarios). Simplified transport and exposure models can be useful in helping decision makers and stakeholders establish such boundaries by analyzing the consequences of selecting different bounds and understanding which assumptions and boundaries have the greatest influence on the magnitude and distribution of model results. Pathway analysis and parameter sensitivity analysis performed on PPA model results are key components of the iterative modeling approach. The objective of pathway analysis is to identify the critical radionuclides and pathways contributing to radiation dose during the modeling performance period. An environmental 'pathway' is described by the connections from a waste package or cell in the disposal facility to a future human exposure event. These connections are commonly visualized using graphical means. A simple example of a potentially complete pathway for radon-222 is: radium-containing waste → radon emanation → upwards diffusion in cap material → diffusion/advection into a future building → inhalation exposure to a building occupant Parameter sensitivity analysis is conducted on the results of a PPA to identify those specific model input parameters whose distribution of values contributes the most to the distribution of target model output, such as annual radiation dose. Pathway and sensitivity analyses on initial modeling results provide information for guiding subsequent model development, and possibly interim decisions, by informing questions tied to the modeling objectives and performance criteria. For example, questions related to radiological doses from existing disposals may include: 1. Is radiation dose from radiological exposures either obviously negligible or obviously unacceptable based on initial modeling results? 2. If dose is not obviously negligible or unacceptable relative to applicable performance criteria, what model refinements would reduce uncertainty in the results to better inform decisions? (authors)

12 MANAGEMENT OF RADIOACTIVE AND NON-RADIOACTIVE W↗

Static Subspace Approximation for Random Phase Approximation Correlation Energies: Implementation and Performance

Developing theoretical understanding of complex reactions and processes at interfaces requires using methods that go beyond semilocal density functional theory to accurately describe the interactions between solvent, reactants and substrates. Methods based on many-body perturbation theory, such as the random phase approximation (RPA), have previously been limited due to their computational complexity. However, this is now a surmountable barrier due to the advances in computational power available, in particular through modern GPU-based supercomputers. In this work, we describe the implementation of RPA calculations within BerkeleyGW and show its favorable computational performance on large complex systems relevant for catalysis and electrochemistry applications. Our implementation builds off of the static subspace approximation which, by employing a compressed representation of the frequency dependent polarizability, enables the evaluation of the RPA correlation energy with significant acceleration and systematically controllable accuracy. We find that the computational cost of calculating the RPA correlation energy scales only linearly with system size for systems containing up to 50 thousand bands, and is expected to scale quadratically thereafter. We also show excellent strong scaling results across several supercomputers, demonstrating the performance and portability of this implementation.

algorithmic development↗

Characterizing quantum supremacy in near-term devices

A critical question for quantum computing in the near future is whether quantum devices without error correction can perform a well-defined computational task beyond the capabilities of supercomputers. Such a demonstration of what is referred to as quantum supremacy requires a reliable evaluation of the resources required to solve tasks with classical approaches. Here, we propose the task of sampling from the output distribution of random quantum circuits as a demonstration of quantum supremacy. We extend previous results in computational complexity to argue that this sampling task must take exponential time in a classical computer. We introduce cross-entropy benchmarking to obtain the experimental fidelity of complex multiqubit dynamics. This can be estimated and extrapolated to give a success metric for a quantum supremacy demonstration. We study the computational cost of relevant classical algorithms and conclude that quantum supremacy can be achieved with circuits in a two-dimensional lattice of 7 × 7 qubits and around 40 clock cycles. This requires an error rate of around 0.5% for two-qubit gates (0.05% for one-qubit gates), and it would demonstrate the basic building blocks for a fault-tolerant quantum computer.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

Reduced-order modeling on a near-term quantum computer

Quantum computing is an advancing area of research in which computer hardware and algorithms are developed to take advantage of quantum mechanical phenomena. In recent studies, quantum algorithms have shown promise in solving linear systems of equations as well as systems of linear ordinary differential equations (ODEs) and partial differential equations (PDEs). Reducedorder modeling (ROM) algorithms for studying fluid dynamics have shown success in identifying linear operators that can describe flowfields, where dynamic mode decomposition (DMD) is a particularly useful method in which a linear operator is identified from data. In this work, DMD is reformulated as an optimization problem to propagate the state of the linearized dynamical system on a quantum computer. This reformulation was chosen as a means of facilitating implementation on a near-term quantum computer. Quadratic unconstrained binary optimization (QUBO), a technique for optimizing quadratic polynomials in binary variables, allows for quantum annealing algorithms to be applied. A quantum circuit model (quantum approximation optimization algorithm, QAOA) is utilized to obtain predictions of the state trajectories. Results are shown for the quantum-ROM predictions for flow over a 2D cylinder at Re = 220 and flow over a NACA0009 airfoil at Re = 500 and α = 15°. The quantum-ROM predictions are found to depend on the number of bits utilized for a fixed point representation and the truncation level of the DMD model. Comparisons with DMD predictions from a classical computer algorithm are made, as well as an analysis of the computational complexity and prospects for future, more fault-tolerant quantum computers.

97 MATHEMATICS AND COMPUTING↗

A Computationally Based Approach to Homogenizing Advanced Alloys

We have developed a computationally based approach to optimizing the homogenization heat treatment of complex alloys. The Scheil module within the Thermo-Calc software is used to predict the as-cast segregation present within alloys, and DICTRA (Diffusion Controlled TRAnsformations) is used to model the homogenization kinetics as a function of time, temperature and microstructural scale. We will discuss this approach as it is applied to both Ni based superalloys as well as the more complex (computationally) case of alloys that solidify with more than one matrix phase as a result of segregation. Such is the case typically observed in martensitic steels. With these alloys it is doubly important to homogenize them correctly, especially at the laboratory scale, since they are austenitic at high temperature and thus constituent elements will diffuse slowly. The computationally designed heat treatment and the subsequent verification real castings are presented.

36 MATERIALS SCIENCE↗

Simulations of frustrated Ising Hamiltonians using quantum approximate optimization

Novel magnetic materials are important for future technological advances. Theoretical and numerical calculations of ground-state properties are essential in understanding these materials, however, computational complexity limits conventional methods for studying these states. Here we investigate an alternative approach to preparing materials ground states using the quantum approximate optimization algorithm (QAOA) on near-term quantum computers. We study classical Ising spin models on unit cells of square, Shastry-Sutherland and triangular lattices, with varying field amplitudes and couplings in the material Hamiltonian. We find relationships between the theoretical QAOA success probability and the structure of the ground state, indicating that only a modest number of measurements (≲100) are needed to find the ground state of our nine-spin Hamiltonians, even for parameters leading to frustrated magnetism. We further demonstrate the approach in calculations on a trapped-ion quantum computer and succeed in recovering each ground state of the Shastry-Sutherland unit cell with probabilities close to ideal theoretical values. The results demonstrate the viability of QAOA for materials ground state preparation in the frustrated Ising limit, giving important first steps towards larger sizes and more complex Hamiltonians where quantum computational advantage may prove essential in developing a systematic understanding of novel materials.

97 MATHEMATICS AND COMPUTING↗

Applying Quantum Computing to Simulate Power System Dynamics

Power system dynamics are generally modeled by high dimensional nonlinear differential-algebraic equations due to a large number of generators, loads, and transmission lines. Thus, its computational complexity grows exponentially with the system size. This paper demonstrates the potential use of quantum computing algorithms to model the power system dynamics. Leveraging a symbolic programming framework, we equivalently convert the power system dynamics’ differential algebraic equations (DAEs) into ordinary differential equations (ODEs), where the data of the state vector can be encoded into quantum computers via amplitude encoding. The system's nonlinearity is captured by Taylor polynomial expansion, the quantum state tensor, and Hamiltonian simulation, whereas state variables can be updated by a quantum linear equation solver. Our results show that quantum computing can simulate the dynamics of the power system with high accuracy, whereas its complexity is polynomial in the logarithm of the system dimension. Our work also illustrates the use of scientific machine learning tools for implementing scientific computing concepts, e.g., Taylor expansion, DAEs/ODEs transform, and quantum computing solver, in the field of power engineering.

Tran, Huynh↗

Deterministic point inclusion methods for computational applications with complex geometry

A fundamental problem in computation is finding practical and efficient algorithms for determining if a query point is contained within a model of a three-dimensional solid. The solid is modeled using a general boundary representation that can contain polygonal elements and/or parametric patches.We have developed two such algorithms: the first is based on a global closest feature query, and the second is based on a local intersection query. Both algorithms work for two- and three-dimensional objects. This paper presents both algorithms, as well as the spatial data structures and queries required for efficient implementation of the algorithms. Applications for these algorithms include computational geometry, mesh generation, particle simulation, multiphysics coupling, and computer graphics. These methods are deterministic in that they do not involve random perturbations of diagnostic rays cast from the query point in order to avoid ‘unclean’ or ‘singular’ intersections of the rays with the geometry. Avoiding the necessity of such random perturbations will become increasingly important as geometries become more convoluted and complex.

97 MATHEMATICS AND COMPUTING↗

Unveiling User Behavior on Summit Login Nodes as a User

We observe and analyze usage of the login nodes of the leadership class Summit supercomputer from the perspective of an ordinary user—not a system administrator—by periodically sampling user activities (job queues, running processes, etc.) for two full years (2020–2021). Our findings unveil key usage patterns that evidence misuse of the system, including gaming the policies, impairing I/O performance, and using login nodes as a sole computing resource. Our analysis highlights observed patterns for the execution of complex computations (workflows), which are key for processing large-scale applications.

Wilkinson, Sean↗

2019 Budget Request for the DOE Computational Science Graduate Fellowship (CSGF) Grant

The Department of Energy Computational Science Graduate Fellowship (DOE CSGF) is necessary to meet the continual challenging national workforce needs that arise as computational science and engineering problems continue to grow in scope and complexity. Computational science and engineering (CSE) is a multidisciplinary approach that uses scientific computing to solve practical problems methods and to supply technical tools across the scientific discovery spectrum. In particular, the DOE CSGF emphasizes high-performance computing (HPC) that enables CSE that advances science and engineering in directions important to the DOE and the economy in general. Over the past half-century, HPC has been an essential tool for DOE’s success. During this period, important missions, such as nuclear stockpile stewardship, have turned to HPC as an essential technology. Entire science disciplines, such as biology and cosmology, have been transformed through the augmentation of scientific observation via HPC. At government laboratories and in industry, DOE CSGF alumni are helping push traditional HPC boundaries while contributing to discoveries in high-energy physics, renewable energy, fusion-reactor design, additive manufacturing, nanomaterials for next-generation batteries and transistors, and turbine and advanced nuclear reactor modeling. In addition, HPC is used to address national health needs that will eventually point to cures both by helping cancer researchers manage and analyze huge troves of data, by simulating biological mechanisms, and by accelerating drug development — including continuing to rise to the challenge of pandemic-related research. A 2023 report from the ASCAC Subcommittee on American Competitiveness and Innovation to the ASCR office, “Can the United States Maintain Its Leadership in High-Performance Computing?” says of the Program, “The CSGF program provides a barometer for disciplines that will be of interest to future DOE computing.” An explosion in scientific and technological data has driven the need for increasingly sophisticated HPC to transform those data into scientific understanding. With access to more and more data and the proliferation of HPC, Machine Learning and Artificial Intelligence are experiencing a renaissance, complementing the now well-established use of computational simulation. Indeed, in its September 2020 subcommittee report on “AI/ML, Data Intensive Science and High-Performance Computing”, the DOE Advanced Scientific Computing Advisory Committee (ASCAC) explicitly called for a fellowship program to train computational and data scientists to tackle exascale and data-intensive computing challenges. This collaboration of empirical and theory-based modeling will increasingly inform federal policymakers whose decisions affect American society and future generations, and it requires highly skilled and intellectually agile computational scientists who can support the fast-moving DOE National Laboratory research environment. In fact, the DOE CSGF program has explicitly and consistently addressed this need.

97 MATHEMATICS AND COMPUTING↗

A review of computational tools for design and reconstruction of metabolic pathways

Metabolic pathways reflect an organism's chemical repertoire and hence their elucidation and design have been a primary goal in metabolic engineering. Various computational methods have been developed to design novel metabolic pathways while taking into account several prerequisites such as pathway stoichiometry, thermodynamics, host compatibility, and enzyme availability. The choice of the method is often determined by the nature of the metabolites of interest and preferred host organism, along with computational complexity and availability of software tools. In this paper, we review different computational approaches used to design metabolic pathways based on the reaction network representation of the database (i.e., graph or stoichiometric matrix) and the search algorithm (i.e., graph search, flux balance analysis, or retrosynthetic search). We also put forth a systematic workflow that can be implemented in projects requiring pathway design and highlight current limitations and obstacles in computational pathway design.

37 INORGANIC, ORGANIC, PHYSICAL, AND ANALYTICAL CH↗

A Comprehensive Informative Metric for Analyzing HPC System Status Using the LogSCAN Platform

Log processing by Spark and Cassandra-based ANalytics (LogSCAN) is a newly developed analytical platform that provides flexible and scalable data gathering, transformation and computation. One major challenge is to effectively summarize the status of a complex computer system, such as the Titan supercomputer at the Oak Ridge Leadership Computing Facility (OLCF). Although there is plenty of operational and maintenance information collected and stored in real time, which may yield insights about short- and long-term system status, it is difficult to present this information in a comprehensive form. In this work, we present system information entropy (SIE), a newly developed metric that leverages the powers of traditional machine learning techniques and information theory. By compressing the multivariant multi-dimensional event information recorded during the operation of the targeted system into a single time series of SIE, we demonstrate that the historical system status can be sensitively represented concisely and comprehensively. Given a sharp indicator as SIE, we argue that follow-up analytics based on SIE will reveal in-depth knowledge about system status using other sophisticated approaches, such as pattern recognition in the temporal domain or causality analysis incorporating extra independent metrics of the system.

Hui, Yawei↗