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 271 records · Page 15
All sourcesNASA NTRSDOE OSTI
DOE OSTI2023

Logical quantum processor based on reconfigurable atom arrays

Suppressing errors is the central challenge for useful quantum computing, requiring quantum error correction (QEC) for large-scale processing. However, the overhead in the realization of error-corrected ‘logical’ qubits, in which information is encoded across many physical qubits for redundancy, poses substantial challenges to large-scale logical quantum computing. Here we report the realization of a programmable quantum processor based on encoded logical qubits operating with up to 280 physical qubits. Using logical-level control and a zoned architecture in reconfigurable neutral-atom arrays, our system combines high two-qubit gate fidelities, arbitrary connectivity, as well as fully programmable single-qubit rotations and mid-circuit readout. Operating this logical processor with various types of encoding, we demonstrate improvement of a two-qubit logic gate by scaling surface-code distance from d = 3 to d = 7, preparation of colour-code qubits with break-even fidelities, fault-tolerant creation of logical Greenberger–Horne–Zeilinger (GHZ) states and feedforward entanglement teleportation, as well as operation of 40 colour-code qubits. Finally, using 3D [[8,3,2]] code blocks, we realize computationally complex sampling circuits with up to 48 logical qubits entangled with hypercube connectivity with 228 logical two-qubit gates and 48 logical CCZ gates. We find that this logical encoding substantially improves algorithmic performance with error detection, outperforming physical-qubit fidelities at both cross-entropy benchmarking and quantum simulations of fast scrambling. These results herald the advent of early error-corrected quantum computation and chart a path towards large-scale logical processors.

74 ATOMIC AND MOLECULAR PHYSICS↗
DOE OSTI2016

Prime factorization using magnonic holographic devices

Determining the prime factors of a given number $N$ is a problem that requires super-polynomial time for conventional digital computers. A polynomial-time algorithm was invented by Shor for quantum computers. In this paper, we present experimental data that demonstrate prime factorization using spin-wave interference but without quantum entanglement. Prime factorization includes three major steps. First, a general-type computer calculates the sequence of numbers m k mod($N$), where $N$ is the number to be factorized, m is a randomly chosen positive integer, and k = 1, 2, 3, 4, 5, 6…. Next, the period of the calculated sequence $r$ is determined by exploiting spin-wave interference. Finally, the general-type computer determines the primes based on the obtained $r$. The experiment for period finding was conducted on a six-terminal Y 3 Fe 2 (FeO 4 ) 3 device. We chose number 15 for testing and determined its primes using a sequence of measurements. The obtained experimental data for a micrometer-sized prototype aimed to demonstrate the benefits of using spin-wave devices to solve complex computational problems. Scalability is one of the major strengths inherent in this type of wave-based device, which may provide a route to nanometer-sized logic circuits. We discuss the physical and technological limitations of this approach, which define the maximum size of N and the computational speed. Although this classical approach cannot compete with the quantum algorithm in terms of efficiency, magnonic holographic devices can potentially be used as complementary logic units aimed at speeding up prime factorization for classical computers.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2022

Adaptive Generation of Training Data for ML Reduced Model Creation

Machine learning proxy models are often used to speed up or completely replace complex computational models. The greatly reduced and deterministic computational costs enable new use cases such as digital twin control systems and global optimization. The challenge of building these proxy models is generating the training data. A naive uniform sampling of the input space can result in a non-uniform sampling of the output space of a model. This can cause gaps in the training data coverage that can miss finer scale details resulting in poor accuracy. While larger and larger data sets could eventually fill in these gaps, the computational burden of full-scale simulation codes can make this prohibitive. In this paper, we present an adaptive data generation method that utilizes uncertainty estimation to identify regions where training data should be augmented. By targeting data generation to areas of need, representative data sets can be generated efficiently. The effectiveness of this method will be demonstrated on a simple one-dimensional function and a complex multidimensional physics model.

Cianciosa, Mark↗
DOE OSTI2022

A Tanks-in-Series Approach to Estimate Parameters for Lithium-Ion Battery Models

Advanced Battery Management Systems (BMS) play a vital role in monitoring, predicting, and controlling the performance of lithium-ion batteries. BMS employing sophisticated electrochemical models can help increase battery cycle life and minimize charging time. However, in order to realize the full potential of electrochemical model-based BMS, it is critical to ensure accurate predictions and proper model parameterization. The accuracy of the predictions of an electrochemical model is dependent on the accuracy of its parameters, the values of which might change with battery cycling and aging. Parameter estimation for an electrochemical model is generally challenging due to the nonlinear nature and computational complexity of the model equations. To this end, this work utilizes the recently proposed Tanks-in-Series model for Li-ion batteries (J.Electrochem. Soc., 167, 013534 (2020)) to perform parameter estimation. The Tanks-in-Series approach allows for substantially faster parameter estimation compared to the original pseudo two-dimensional (p2D) model. The objective of this work is thus to demonstrate the gain in computational efficiency from the Tanks-in-Series approach. A sensitivity analysis of model parameters is also performed to benchmark the fidelity of the Tanks-in-Series model.

25 ENERGY STORAGE↗
DOE OSTI2019

An Eigenvector-Based Method of Radio Array Calibration and Its Application to the Tianlai Cylinder Pathfinder

We propose an eigenvector-based formalism for the calibration of radio interferometer arrays. In the presence of a strong dominant point source, the complex gains of the array can be obtained by taking the first eigenvector of the visibility matrix. We use the stable principle component analysis method to help separate outliers and noise from the calibrator signal to improve the performance of the method. This method can be applied with poorly known beam model of the antenna, is insensitive to outliers or imperfections in the data, and has low computational complexity. It thus is particularly suitable for the initial calibration of the array, which can serve as the initial point for more accurate calibrations. We demonstrate this method by applying it to the cylinder pathfinder of the Tianlai experiment, which aims to measure the dark energy equation of state using the baryon acoustic oscillation features in the large-scale structure by making intensity mapping observation of the redshifted 21 cm emission of the neutral hydrogen (H i). The complex gain of the array elements and the beam profile in the east–west direction (short axis of the cylinder) are successfully obtained by applying this method to the transit data of bright radio sources.

79 ASTRONOMY AND ASTROPHYSICS↗
DOE OSTI2017

Bayesian K-SVD Using Fast Variational Inference

Recent work in signal processing in general and image processing in particular deals with sparse representation related problems. Two such problems are of paramount importance: an overriding need for designing a well-suited overcomplete dictionary containing a redundant set of atoms— i.e., basis signals—and how to find a sparse representation of a given signal with respect to the chosen dictionary. Dictionary learning techniques, among which we find the popular K-singular value decomposition algorithm, tackle these problems by adapting a dictionary to a set of training data. A common drawback of such techniques is the need for parameter-tuning. In order to overcome this limitation, we propose a fullyautomated Bayesian method that considers the uncertainty of the estimates and produces a sparse representation of the data without prior information on the number of non-zeros in each representation vector. We follow a Bayesian approach that uses a three-tiered hierarchical prior to enforce sparsity on the representations and develop an efficient variational inference framework that reduces computational complexity. Furthermore, we describe a greedy approach that speeds up the whole process. Lastly, we present experimental results that show superior performance on two different applications with real images: denoising and inpainting.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2017

Zonal wavefront reconstruction in quadrilateral geometry for phase measuring deflectometry

There are wide applications for zonal reconstruction methods in slope-based metrology due to its good capability of reconstructing the local details on surface profile. It was noticed in the literature that large reconstruction errors occur when using zonal reconstruction methods designed for rectangular geometry to process slopes in a quadrilateral geometry, which is a more general geometry with phase measuring deflectometry. In this paper, we present a new idea for the zonal methods for quadrilateral geometry. Instead of employing the intermediate slopes to set up height-slope equations, we consider the height increment as a more general connector to establish the height-slope relations for least-squares regression. The classical zonal methods and interpolation-assisted zonal methods are compared with our proposal. Results of both simulation and experiment demonstrate the effectiveness of the proposed idea. In implementation, the modification on the classical zonal methods is addressed. Finally, the new methods preserve many good aspects of the classical ones, such as the ability to handle a large incomplete slope dataset in an arbitrary aperture, and the low computational complexity comparable with the classical zonal method. Of course, the accuracy of the new methods is much higher when integrating the slopes in quadrilateral geometry.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗
DOE OSTI2024

Compressing branch-and-bound trees

A branch-and-bound (BB) tree certifies a dual bound on the value of an integer program. In this work, we introduce the tree compression problem (TCP): Given a BB tree T that certifies a dual bound, can we obtain a smaller tree with the same (or stronger) bound by either (1) applying a different disjunction at some node in T or (2) removing leaves from T? Here we believe such post-hoc analysis of BB trees may assist in identifying helpful general disjunctions in BB algorithms. We initiate our study by considering computational complexity and limitations of TCP. We then conduct experiments to evaluate the compressibility of realistic branch-and-bound trees generated by commonly-used branching strategies, using both an exact and a heuristic compression algorithm.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2021

Quantum Computational Advantage with String Order Parameters of One-Dimensional Symmetry-Protected Topological Order

Nonlocal games with advantageous quantum strategies give arguably the most fundamental demonstration of the power of quantum resources over their classical counterparts. Recently, certain multiplayer generalizations of nonlocal games have been used to prove unconditional separations between limited computational complexity classes of shallow-depth circuits. Here, we show advantageous strategies for these nonlocal games for generic ground states of one-dimensional symmetry-protected topological orders (SPTOs), when a discrete invariant of a SPTO known as a twist phase is nontrivial and -1. Finally, our construction demonstrates that sufficiently large string order parameters of such SPTOs are indicative of globally constrained correlations useful for the unconditional computational separation.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗
DOE OSTI2018

An Eigenvector-based Method of Radio Array Calibration and Its Application to the Tianlai Cylinder Pathfinder

We propose an eigenvector-based formalism for the calibration of radio interferometer arrays. In the presence of a strong dominant point source, the complex gains of the array can be obtained by taking the first eigenvector of the visibility matrix. We use the stable principle component analysis (SPCA) method to help separate outliers and noise from the calibrator signal to improve the performance of the method. This method can be applied with poorly known beam model of the antenna, and is insensitive to outliers or imperfections in the data, and has low computational complexity. It thus is particularly suitable for the initial calibration of the array, which can serve as the initial point for more accurate calibrations. We demonstrate this method by applying it to the cylinder pathfinder of the Tianlai experiment, which aims to measure the dark energy equation of state using the baryon acoustic oscillation (BAO) features in the large scale structure by making intensity mapping observation of the redshifted 21~cm emission of the neutral hydrogen (HI). The complex gain of the array elements and the beam profile in the East-West direction (short axis of the cylinder) are successfully obtained by applying this method to the transit data of bright radio sources.

46 INSTRUMENTATION RELATED TO NUCLEAR SCIENCE AND ↗
DOE OSTI2024

Forecasting high-dimensional spatio-temporal systems from sparse measurements

This paper introduces a new neural network architecture designed to forecast high-dimensional spatio-temporal data using only sparse measurements. The architecture uses a two-stage end-to-end framework that combines neural ordinary differential equations (NODEs) with vision transformers. Initially, our approach models the underlying dynamics of complex systems within a low-dimensional space; and then it reconstructs the corresponding high-dimensional spatial fields. Many traditional methods involve decoding high-dimensional spatial fields before modeling the dynamics, while some other methods use an encoder to transition from high-dimensional observations to a latent space for dynamic modeling. In contrast, our approach directly uses sparse measurements to model the dynamics, bypassing the need for an encoder. This direct approach simplifies the modeling process, reduces computational complexity, and enhances the efficiency and scalability of the method for large datasets. We demonstrate the effectiveness of our framework through applications to various spatio-temporal systems, including fluid flows and global weather patterns. Although sparse measurements have limitations, our experiments reveal that they are sufficient to forecast system dynamics accurately over long time horizons. Our results also indicate that the performance of our proposed method remains robust across different sensor placement strategies, with further improvements as the number of sensors increases. This robustness underscores the flexibility of our architecture, particularly in real-world scenarios where sensor data is often sparse and unevenly distributed.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2020

Parallel performance of algebraic multigrid domain decomposition

Algebraic multigrid (AMG) is a widely used scalable solver and preconditioner for large-scale linear systems resulting from the discretization of a wide class of elliptic PDEs. While AMG has optimal computational complexity, the cost of communication has become a significant bottleneck that limits its scalability as processor counts continue to grow on modern machines. This article examines the design, implementation, and parallel performance of a novel algorithm, algebraic multigrid domain decomposition (AMG-DD), designed specifically to limit communication. The goal of AMG-DD is to provide a low-communication alternative to standard AMG V-cycles by trading some additional computational overhead for a significant reduction in communication cost. Numerical results show that AMG-DD achieves superior accuracy per communication cost compared with AMG, and speedup over AMG is demonstrated on a large GPU cluster.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2025

Physics-Informed Graph Neural Networks for Collaborative Dynamic Reconfiguration and Voltage Regulation in Unbalanced Distribution Systems

Network reconfiguration has long been employed as a strategic approach to minimize power distribution system losses and effectively regulate voltage levels. Tap-changing voltage regulators are also critical for controlling bus voltages, especially in accommodating the increasing integration of distributed energy resources (DERs) with intermittent outputs. This paper introduces novel methodologies to address the challenges of dynamic reconfiguration and optimal tap setting in unbalanced three-phase distribution systems. We propose an approximated mixed-integer quadratically constrained program (MIQCP) to model dynamic reconfiguration, along with a pioneering formulation for voltage regulator (VR) tap-setting based on Special Ordered Set type 1 (SOS1). To mitigate computational complexity, we propose a physics-informed spatial-temporal graph convolutional network (STGCN) with an integrated link classifier. The proposed approach enables efficient solution generation by fixing specific variables in the MIQCP instance and solving the simplified sub-MIP using an MIP solver. Numerical studies demonstrate the superior prediction accuracy of our STGCN model compared to baseline neural network models, resulting in reduced DER curtailment and voltage deviation with shorter computation time.

dynamic reconfiguration↗
DOE OSTI2025

Survey-wide asteroid discovery with a high-performance computing enabled non-linear digital tracking framework

Modern astronomical surveys detect asteroids by linking together their appearances across multiple images taken over time. This approach faces limitations in detecting faint asteroids and handling the computational complexity of trajectory linking. Here, we present a novel method that adapts “digital tracking” – traditionally used for short-term linear asteroid motion across images – to work with large-scale synoptic surveys such as the Vera Rubin Observatory Legacy Survey of Space and Time (Rubin/LSST). Our approach combines hundreds of sparse observations of individual asteroids across their non-linear orbital paths to enhance detection sensitivity by several magnitudes. To address the computational challenges of processing massive data sets and dense orbital phase spaces, we developed a specialized high-performance computing architecture. We demonstrate the effectiveness of our method through experiments that take advantage of the extensive computational resources at Lawrence Livermore National Laboratory. This work enables the detection of significantly fainter asteroids in existing and future survey data, potentially increasing the observable asteroid population by orders of magnitude across different orbital families, from near-Earth objects (NEOs) to Kuiper belt objects (KBOs).

Asteroid discovery↗
DOE OSTI2017

A graph-based computational framework for simulation and optimisation of coupled infrastructure networks

Here, we present a computational framework that facilitates the construction, instantiation, and analysis of large-scale optimization and simulation applications of coupled energy networks. The framework integrates the optimization modeling package PLASMO and the simulation package DMNetwork (built around PETSc). These tools use a common graphbased abstraction that enables us to achieve compatibility between data structures and to build applications that use network models of different physical fidelity. We also describe how to embed these tools within complex computational workflows using SWIFT, which is a tool that facilitates parallel execution of multiple simulation runs and management of input and output data. We discuss how to use these capabilities to target coupled natural gas and electricity systems.

42 ENGINEERING↗
DOE OSTI2022

TOF-SIMS analysis of decoherence sources in superconducting qubits

Superconducting qubits have emerged as a potentially foundational platform technology for addressing complex computational problems deemed intractable with classical computing. Despite recent advances enabling multiqubit designs that exhibit coherence lifetimes on the order of hundreds of μs, material quality and interfacial structures continue to curb device performance. Two-level system defects in the thin superconducting film and adjacent dielectric regions introduce stochastic noise and dissipate electromagnetic energy at the cryogenic operating temperatures. In this study, we utilize time-of-flight secondary ion mass spectrometry to understand the role specific fabrication procedures play in introducing such dissipation mechanisms in these complex systems. We interrogated Nb thin films and transmon qubit structures fabricated through slight modifications in the processing and vacuum conditions. We find that when the Nb film is sputtered onto the Si substrate, oxide and silicide regions are generated at various interfaces. We also observe that impurity species, such as niobium hydrides and carbides, are incorporated within the niobium layer during the subsequent lithographic patterning steps. The formation of these resistive compounds likely impacts the superconducting properties of the Nb thin film. Additionally, we observe the presence of halogen species distributed throughout the patterned thin films. We conclude by hypothesizing the source of such impurities in these structures in an effort to intelligently fabricate superconducting qubits and extend coherence times moving forward.

75 CONDENSED MATTER PHYSICS, SUPERCONDUCTIVITY AND↗
DOE OSTI2020

Sneezing and asymptomatic virus transmission

The novel coronavirus disease (COVID-19) spread pattern continues to show that geographical barriers alone cannot contain a virus. Asymptomatic carriers play a critical role in the nature of this virus quickly escalating into a global pandemic. Asymptomatic carriers may transmit the virus unintentionally through sporadic sneezing. A novel Computational Fluid Dynamics (CFD) approach has been proposed with a realistic modeling of a human sneeze achieved by the combination of state-of-the-art experimental and numerical methods. This modeling approach may be suitable for future engineering analyses aimed at reshaping public spaces and common areas, with the main objective to accurately predict the spread of aerosol and droplets that may contain pathogens. This study shows that the biomechanics of a human sneeze, including complex muscle contractions and relaxations, can be accurately modeled by the angular head motion and the dynamic pressure response during sneezing. These have been considered as the human factors and were implemented in the CFD simulation by imposing a momentum source term to the coupled Eulerian–Lagrangian momentum equations. The momentum source was modeled by the measured dynamic pressure response in conjunction with the angular head motion. This approach eliminated the need to create an ad hoc set of inlet boundary conditions. With this proposed technique, it is easier to add multiple fixed and/or moving sources of sneezes in complex computational domains. Additionally, extensive sensitivity analyses based on different environmental conditions were performed, and their impact was described in terms of potential virus spread.

42 ENGINEERING↗