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 307 records · Page 17
All sourcesNASA NTRSDOE OSTI
DOE OSTI2022

Binary Optimal Control of Single-Flux-Quantum Pulse Sequences

We introduce a binary, relaxed gradient, trust-region method for optimizing pulse sequences for single flux quanta (SFQ) control of a quantum computer. The pulse sequences are optimized with the goal of realizing unitary gate transformations. Each pulse has a fixed amplitude and duration. Here we model this process as an binary optimal control problem, constrained by Schrödinger’s equation, where the binary variables indicate whether each pulse is on or off. We introduce a first-order trust-region method, which takes advantage of a relaxed gradient to determine an optimal pulse sequence that minimizes the gate infidelity, while also suppressing leakage to higher energy levels. The proposed algorithm has a computational complexity of O(p log(p)), where p is the number of pulses in the sequence. We present numerical results for the H and X gates, where the optimized pulse sequences give gate fidelity’s better than 99.9%, in ≈ 25 trust-region iterations.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗
DOE OSTI2015

Parallel seed-based approach to multiple protein structure similarities detection

Finding similarities between protein structures is a crucial task in molecular biology. Most of the existing tools require proteins to be aligned in order-preserving way and only find single alignments even when multiple similar regions exist. We propose a new seed-based approach that discovers multiple pairs of similar regions. Its computational complexity is polynomial and it comes with a quality guarantee—the returned alignments have both root mean squared deviations (coordinate-based as well as internal-distances based) lower than a given threshold, if such exist. We do not require the alignments to be order preserving (i.e., we consider nonsequential alignments), which makes our algorithm suitable for detecting similar domains when comparing multidomain proteins as well as to detect structural repetitions within a single protein. Because the search space for nonsequential alignments is much larger than for sequential ones, the computational burden is addressed by extensive use of parallel computing techniques: a coarse-grain level parallelism making use of available CPU cores for computation and a fine-grain level parallelism exploiting bit-level concurrency as well as vector instructions.

59 BASIC BIOLOGICAL SCIENCES↗
DOE OSTI2021

Convex Optimization of Integrated Power-Gas Energy Flow Model With Applications to Probabilistic Energy Flow

Energy flow calculation is a fundamental problem of the integrated power and gas system (IPGS) operation and planning. However, the nonlinear gas flow model introduces major challenges to the energy flow calculation. In this paper, we propose a tractably convex optimization model to solve the energy flow problem in IPGSs. It is demonstrated that the proposed optimization model has the same optimal solution as the original nonlinear steady energy flow model. Also, piecewise linearization is adopted to tightly linearize the nonlinear objective function of the model, which transforms the formulated convex optimization into a linear program one. Thus, the computation complexity of the proposed energy flow model is significantly reduced as compared with the existing methods. In addition, the proposed model can be extended to probabilistic energy flow estimation. Extensive case studies are conducted to validate the effectiveness of the proposed energy flow model using three IPGSs.

42 ENGINEERING↗
DOE OSTI2013

LEISURE: Load-Balanced Network-Wide Traffic Measurement and Monitor Placement

We report that network-wide traffic measurement is of interest to network operators to uncover global network behavior for the management tasks of traffic accounting, debugging or troubleshooting, security, and traffic engineering. Increasingly, sophisticated network measurement tasks such as anomaly detection and security forensic analysis are requiring in-depth fine-grained flow-level measurements. However, performing in-depth per-flow measurements (e.g., detailed payload analysis) is often an expensive process. Given the fast-changing Internet traffic landscape and large traffic volume, a single monitor is not capable of accomplishing the measurement tasks for all applications of interest due to its resource constraint. Moreover, uncovering global network behavior requires network-wide traffic measurements at multiple monitors across the network since traffic measured at any single monitor only provides a partial view and may not be sufficient or accurate. These factors call for coordinated measurements among multiple distributed monitors. In this paper, we present a centralized optimization framework, LEISURE (Load- EqualIzed meaSUREment), for load-balancing network measurement workloads across distributed monitors. Specifically, we consider various load-balancing problems under different objectives and study their extensions to support both fixed and flexible monitor deployment scenarios. We formulate the latter flexible monitor deployment case as an MILP (Mixed Integer Linear Programming) problem and propose several heuristic algorithms to approximate the optimal solution and reduce the computation complexity. We evaluate LEISURE via detailed simulations on Abilene and GEANT network traces to show that LEISURE can achieve much better load-balanced performance (e.g., 4.75 × smaller peak workload and 70 × smaller variance in workloads) across all coordinated monitors in comparison to a naive solution (uniform assignment) to accomplish network-wide traffic measurement tasks under the fixed monitor deployment scenario. Lastly, we also show that under the flexible monitor deployment setting, our heuristic solutions can achieve almost the same load-balancing performance as the optimal solution while reducing the computation times by a factor up to 22.5 × in Abilene and 800 × in GEANT.

42 ENGINEERING↗
DOE OSTI2021

IDAES Enterprise: Generation Expansion Planning with Enhanced Requirements for Capacity Adequacy Under Renewable Intermittency

Achieving net zero carbon emissions likely requires future power systems to integrate new, flexible energy technologies to accommodate higher levels of capacity from variable renewable energy sources. To determine the optimal deployment of new electricity capacity and to study the likelihood of deployments of new energy technologies, an expansion planning model has been developed as part of the IDAES-Enterprise suite of grid models. The Generation Expansion Planning (GEP) model is a multi-period model in which investment decisions occur yearly, and a Unit Commitment (UC) problem is examined on an hourly timescale. To reduce computational complexity of the GEP model, the UC problem is solved for average “representative days” which leaves out extreme, but relatively common, scenarios in which low renewable generation occurs, leaving the system with inadequacy in capacity. The IDAES-Enterprise GEP model has been modified to include these extreme scenarios while keeping the model reasonably tractable. Specifically, a lazy constraint technique was implemented to check for capacity adequacy on an hourly basis over a large data set of aligned load-wind-solar profiles. As a vast majority of the capacity constraints will not be violated, the technique lowers computational expense by searching for violated capacity constraints over an “iterative manner,” adding those infeasible constraints back into the model. Results on a test case of the Southwest Power Pool shows that the lazy constraint technique significantly reduces retirements and increases installments of natural gas combined cycles and flexible natural gas units. It also reduces some retirements of coal units. These modifications provide a more reasonable estimation of required dispatchable power generation capacity to ensure feasibility during peak net load.

Liu, Peng↗
DOE OSTI2019

Approximate Scheduling of DERs with Discrete Complex Injections

Rapid penetration of renewable energy based Distributed Energy Resources (DER) has the potential to exacerbate the challenges inherent in grid frequency and voltage regulation. However, their real time controllability can be leveraged to not only mitigate such challenges, but improve the economics and quality of grid operations. A plethora of DER scheduling algorithms have been developed for fast and efficient scheduling of these resources. These algorithms schedule the complex - real and reactive power injected into (or drawn from) the grid by the DERs under various cost objective functions and grid constraints. However, a vast majority of such algorithms assume the feasible range of power injections to be continuous. In reality, the control options available for several DERs form a discrete space. This implies that the feasible range of power injections also forms a discrete space. This makes DER scheduling an NP-hard problem. Integer/Mixed Integer program based algorithms, which guarantee optimality in the objective value, have been developed. But these are prohibitively expensive in terms of computational time requirements. On the other hand, fast heuristic based solutions have also been developed. But as they do not provide any guarantee on the optimality of the objective, or on satisfying the constraints, they are unreliable for grid operations. Recent works have developed approximation algorithms which offer the best of both the approaches above: (near) optimality and low computational complexity, both of which are governed by a user defined accuracy parameter ϵ. In this work, we significantly improve upon such existing works by developing an approximation algorithm which schedules DERs with complex injections (as opposed to only real injection) and whose runtime is polynomial (as opposed to exponential) in 1/ϵ. We provide theoretical analysis and support them with experimental results to validate the guarantees provided by our approximation algorithm.

14 SOLAR ENERGY↗
DOE OSTI2022

Learning Distributed Geometric Koopman Operator for Sparse Networked Dynamical Systems

Koopman operator theory provides an alternative to study nonlinear networked dynamical systems by mapping the state space to an abstract higher dimensional space where the system evolution is linear. Recent works show the application of graph neural networks (GNNs) to learn state to object-centric embeddings and achieve centralized block-wise computation of Koopman operator (KO) under additional assumptions on the underlying agents properties and constraints on the KO structure. However, the computational complexity of learning the Koopman increases exponentially for networked systems where the number of possible system states grows in a combinatorial fashion with the number of nodes. The learning challenge is further amplified for sparse networks by two factors: 1) sample sparsity for learning the Koopman operator in the non-linear space, and 2) the divergence in the dynamics of individual nodes or from one subgraph to another. Our work aims to address these challenge by formulating the representation learning of networked dynamical systems into a multi-agent paradigm and learning the Koopman operator in a distributive manner. The computational as well as performance advantages of distributed Koopman is predominant for sparse networks whereas for fully connected networks, it is shown to coincide with the centralized one. The empirical study on rope system, network of oscillators and a synthetic power system show comparable and superior performance along with computational benefits with the state-of-the-art methods.

Mukherjee, Sayak↗
DOE OSTI2022

Seamless Wireless Communication Platform for Internet of Things Applications

The rapid growth of the Internet of Things (IoT) devices resulted in the proliferation of wireless technologies to cater to their increasing data rate requirements and support multiple applications. However, such ever-increasing wireless technologies present numerous challenges such as incompatible wireless standards, increased energy consumption, and insecure communication. The traditional gateways proposed in the literature suffers from limitations such as computational complexity, resource requirements, increased cost, and device size. We vision an era of seamless wireless communication to alleviate the aforementioned challenges in IoT applications. through three inter-dependent functionalities namely detection and identification of wireless technologies, energy-efficient transmit power control, and secure end-to-end communication. To prove the concept, a new gateway is proposed to achieve these three functionalities with only physical layer measurements so that the different communication protocols in the higher layers can be avoided. Novel schemes are conceptualized for resource-limited seamless IoT applications. Moreover, the conceptual seamless IoT platform is validated through software-based computer simulation and software-defined radio-based testbed implementation. Finally, the preliminary analysis demonstrates that the proposed platform has great potential in advancing seamless IoT applications.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2020

Symmetry reduction of tensor networks in many-body theory: I. Automated symbolic evaluation of SU(2) algebra

Abstract The ongoing progress in (nuclear) many-body theory is accompanied by an ever-rising increase in complexity of the underlying formalisms used to solve the stationary Schrödinger equation. The associated working equations at play in state-of-the-art ab initio nuclear many-body methods can be analytically reduced with respect to angular-momentum, i.e. SU (2), quantum numbers whenever they are effectively employed in a symmetry-restricted context. The corresponding procedure constitutes a tedious and error-prone but yet an integral part of the implementation of those many-body frameworks. Indeed, this symmetry reduction is a key step to advance modern simulations to higher accuracy since the use of symmetry-adapted tensors can decrease the computational complexity by orders of magnitude. While attempts have been made in the past to automate the (anti-) commutation rules linked to Fermionic and Bosonic algebras at play in the derivation of the working equations, there is no systematic account to achieve the same goal for their symmetry reduction. In this work, the first version of an automated tool performing graph-theory-based angular-momentum reduction is presented. Taking the symmetry-unrestricted expressions of a generic tensor network as an input, the code provides their angular-momentum-reduced form in an error-safe way in a matter of seconds. Several state-of-the-art many-body methods serve as examples to demonstrate the generality of the approach and to highlight the potential impact on the many-body community.

Tichai, A.↗
DOE OSTI2022

Model-Based Reconstruction for Collimated Beam Ultrasound Systems

Collimated beam ultrasound systems are a novel technology for imaging inside multi-layered structures such as geothermal wells. Such systems include a transmitter and multiple receivers to capture reflected signals. Common algorithms for ultrasound reconstruction use delay-and-sum (DAS) approaches; these have low computational complexity but produce inaccurate images in the presence of complex structures and specialized geometries such as collimated beams.In this paper, we propose a multi-layer, ultrasonic, model-based iterative reconstruction algorithm designed for collimated beam systems. We introduce a physics-based forward model to accurately ac-count for the propagation of a collimated ultrasonic beam in multi-layer media and describe an efficient implementation using binary search. We model direct arrival signals, detector noise, and a spatially varying image prior, then cast the reconstruction as a maximum a posteriori estimation problem. Using simulated and experimental data we obtain significantly fewer artifacts relative to DAS while running in near real time using commodity compute resources.

Alanazi, Abdulrahman M.↗
DOE OSTI2023

Enabling Hyper-Differential Sensitivity Analysis for Ill-Posed Inverse Problems

Inverse problems constrained by partial differential equations (PDEs) play a critical role in model development and calibration. In many applications, there are multiple uncertain parameters in a model that must be estimated. However, high dimensionality of the parameters and computational complexity of the PDE solves make such problems challenging. A common approach is to reduce the dimension by fixing some parameters (which we will call auxiliary parameters) to a best estimate and use techniques from PDE-constrained optimization to estimate the other parameters. In this article, hyper-differential sensitivity analysis (HDSA) is used to assess the sensitivity of the solution of the PDE-constrained optimization problem to changes in the auxiliary parameters. Foundational assumptions for HDSA require satisfaction of the optimality conditions which are not always practically feasible as a result of ill-posedness in the inverse problem. Here we introduce novel theoretical and computational approaches to justify and enable HDSA for ill-posed inverse problems by projecting the sensitivities on likelihood informed subspaces and defining a posteriori updates. Our proposed framework is demonstrated on a nonlinear multiphysics inverse problem motivated by estimation of spatially heterogeneous material properties in the presence of spatially distributed parametric modeling uncertainties.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2017

8760-Based Method for Representing Variable Generation Capacity Value in Capacity Expansion Models: Preprint

Capacity expansion models (CEMs) are widely used to evaluate the least-cost portfolio of electricity generators, transmission, and storage needed to reliably serve demand over the evolution of many years or decades. Various CEM formulations are used to evaluate systems ranging in scale from states or utility service territories to national or multi-national systems. CEMs can be computationally complex, and to achieve acceptable solve times, key parameters are often estimated using simplified methods. In this paper, we focus on two of these key parameters associated with the integration of variable generation (VG) resources: capacity value and curtailment. We first discuss common modeling simplifications used in CEMs to estimate capacity value and curtailment, many of which are based on a representative subset of hours that can miss important tail events or which require assumptions about the load and resource distributions that may not match actual distributions. We then present an alternate approach that captures key elements of chronological operation over all hours of the year without the computationally intensive economic dispatch optimization typically employed within more detailed operational models. The updated methodology characterizes the (1) contribution of VG to system capacity during high load and net load hours, (2) the curtailment level of VG, and (3) the potential reductions in curtailments enabled through deployment of storage and more flexible operation of select thermal generators. We apply this alternate methodology to an existing CEM, the Regional Energy Deployment System (ReEDS). Results demonstrate that this alternate approach provides more accurate estimates of capacity value and curtailments by explicitly capturing system interactions across all hours of the year. This approach could be applied more broadly to CEMs at many different scales where hourly resource and load data is available, greatly improving the representation of challenges associate with integration of variable generation resources.

14 SOLAR ENERGY↗
DOE OSTI2018

Toward improving drought monitoring using the remotely sensed soil moisture assimilation: A parallel particle filtering framework

Drought is the costliest hazard among all natural disasters. Despite the significant improvements in drought modeling over the last decade, accurate provisions of drought conditions in a timely manner is still one of the major research challenges. In order to improve the current drought monitoring skills, this study presents a land data assimilation system by merging the remotely sensed surface soil moisture with the use of recently developed particle Markov chain Monte Carlo (PMCMC) method. To cope with the computational complexity, a modular parallel particle filtering framework (PPFF) is developed which allows a large ensemble size in PMCMC applications. The implementation of the proposed system is demonstrated with the 2012 summer flash drought case study over the Contiguous United States (CONUS). Results from both synthetic and real case studies suggest that the land data assimilation system significantly improves the soil moisture predictions and the drought monitoring skills. Compared with the U.S. Drought Monitoring (USDM), the land data assimilation can better capture the drought onset on May 2012 and the drought severity in June and July 2012. Finally, this study recommends that the proposed land data assimilation system under a high-performance computing (HPC) infrastructure can better facilitate the drought preparation and response actions.

42 ENGINEERING↗
DOE OSTI2019

Origin of band gaps in 3d perovskite oxides

With their broad range of properties, ABO3 transition metal perovskite oxides have long served as a platform for device applications and as a testing bed for different condensed matter theories. Their insulating character and structural distortions are often ascribed to dynamical electronic correlations within a universal, symmetry-conserving paradigm. This view restricts predictive theory to complex computational schemes, going beyond density functional theory (DFT). Here, we show that, if one allows symmetry-breaking energy-lowering crystal symmetry reductions and electronic instabilities within DFT, one successfully and systematically recovers the trends in the observed band gaps, magnetic moments, type of magnetic and crystallographic ground state, bond disproportionation and ligand hole effects, Mott vs. charge transfer insulator behaviors, and the amplitude of structural deformation modes including Jahn-Teller in low temperature spin-ordered and high temperature disordered paramagnetic phases. We then provide a classification of the four mechanisms of gap formation and establish DFT as a reliable base platform to study the ground state properties in complex oxides.

36 MATERIALS SCIENCE↗
DOE OSTI2014

Parallel computation safety analysis irradiation targets fission product molybdenum in neutronic aspect using the successive over-relaxation algorithm

One of the research activities in support of commercial radioisotope production program is a safety research on target FPM (Fission Product Molybdenum) irradiation. FPM targets form a tube made of stainless steel which contains nuclear-grade high-enrichment uranium. The FPM irradiation tube is intended to obtain fission products. Fission materials such as Mo{sup 99} used widely the form of kits in the medical world. The neutronics problem is solved using first-order perturbation theory derived from the diffusion equation for four groups. In contrast, Mo isotopes have longer half-lives, about 3 days (66 hours), so the delivery of radioisotopes to consumer centers and storage is possible though still limited. The production of this isotope potentially gives significant economic value. The criticality and flux in multigroup diffusion model was calculated for various irradiation positions and uranium contents. This model involves complex computation, with large and sparse matrix system. Several parallel algorithms have been developed for the sparse and large matrix solution. In this paper, a successive over-relaxation (SOR) algorithm was implemented for the calculation of reactivity coefficients which can be done in parallel. Previous works performed reactivity calculations serially with Gauss-Seidel iteratives. The parallel method can be used to solve multigroup diffusion equation system and calculate the criticality and reactivity coefficients. In this research a computer code was developed to exploit parallel processing to perform reactivity calculations which were to be used in safety analysis. The parallel processing in the multicore computer system allows the calculation to be performed more quickly. This code was applied for the safety limits calculation of irradiated FPM targets containing highly enriched uranium. The results of calculations neutron show that for uranium contents of 1.7676 g and 6.1866 g (× 10{sup 6} cm{sup −1}) in a tube, their delta reactivities are the still within safety limits; however, for 7.9542 g and 8.838 g (× 10{sup 6} cm{sup −1}) the limits were exceeded.

07 ISOTOPE AND RADIATION SOURCES↗
DOE OSTI2022

Quantum algorithmic measurement

There has been recent promising experimental and theoretical evidence that quantum computational tools might enhance the precision and efficiency of physical experiments. However, a systematic treatment and comprehensive framework are missing. Here we initiate the systematic study of experimental quantum physics from the perspective of computational complexity. To this end, we define the framework of quantum algorithmic measurements (QUALMs), a hybrid of black box quantum algorithms and interactive protocols. We use the QUALM framework to study two important experimental problems in quantum many-body physics: determining whether a system’s Hamiltonian is time-independent or time-dependent, and determining the symmetry class of the dynamics of the system. We study abstractions of these problems and show for both cases that if the experimentalist can use her experimental samples coherently (in both space and time), a provable exponential speedup is achieved compared to the standard situation in which each experimental sample is accessed separately. Our work suggests that quantum computers can provide a new type of exponential advantage: exponential savings in resources in quantum experiments.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗
DOE OSTI2012

Meta Parallel Coordinates For Visualizing Features in Large, High-Dimensional, Time-Varying Data

Managing computational complexity and designing effective visual representations are two important challenges for the visualization of large, complex, high-dimensional datasets. Parallel coordinates are an effective technique for visualizing high- dimensional data, but do not scale well to very large datasets. The addition of the temporal dimension leads to more uncertainty due to clutter on screen. Consequently, this poses a significant challenge for visually finding trends and patterns that maximize insight about the underlying time-varying properties of the data. To address these problems, we present meta parallel coordinates, a parallel coordinates display that is guided by perceptually mo- tivated visual metrics. These metrics describe the visual structures typically found in parallel coordinates and thus aid the user’s analysis by providing meaningful views of the data. Since they are computed in screen space, our metrics are computationally more efficient than data-based metrics. Our choice of metrics is driven by the different analytical tasks that a user typically wants to perform with time-varying multivariate data. In particular, we have worked with domain scientists who performed simulations of bioremediation experiments, and use their data and results to demonstrate the usefulness of our approach

Dasgupta, Aritra↗
DOE OSTI2019

A Cooperative Multi-Agent Deep Reinforcement Learning Framework for Real-Time Residential Load Scheduling

Internet-of-Things (IoT) enabled monitoring and control capabilities are enabling increasing numbers of household users with controllable loads to actively participate in smart grid energy management. Realizing an efficient real-time energy management system that takes advantage of these developments requires novel techniques for managing the increased complexity of the control action space in resolving multiple challenges such as the uncertainty in energy prices and renewable energy output along with the need to satisy physical grid constraints such as transformer capacity. Addressing these challenges, we develop a multi-household energy management framework for residential units connected to the same transformer and containing DERs such as PV, ESS and controllable loads. The goal of our framework is to schedule controllable household appliances and ESS such that the cost of procuring electricity from the utility over a horizon is minimized while physical grid constraints are satisfied at each scheduling step. Traditional energy management frameworks either perform global optimization to satisfy grid constraints but suffer from high computational complexity (for example Integer Program, Mixed Integer Programming frameworks and centralized reinforcement learning) or perform decentralized real-time energy management without satisfying global grid constraints (for example multi-agent reinforcement learning with no cooperation). In contrast, we propose a cooperative multiagent reinforcement learning (MARL) framework that i) operates in real-time, and ii) performs explicit collaboration to satisfy global grid constraints. The novelty in our framework is two fold. Firstly, our framework trains multiple independent learners (IL) for each household in parallel using historical data and performs real-time inferencing of control actions using the most recent system state. Secondly, our framework contains a low complexity knapsack based cooperation agent which combines the outputs of ILs to minimize cost while satisfying grid constraints. Simulation results show that our cooperative MARL approach achieves significant cost improvement over centralized reinforcement learning and day-ahead planning baselines. Moreover, our approach strictly satisfies physical constraints with no apriori knowledge of system dynamics while the baseline approaches have occasional violations. We also measure the training and inference time by ranging the number of households from 1 to 25. Results show that our cooperative MARL approach scales best among various approaches.

14 SOLAR ENERGY↗