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 451 records · Page 25

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↗

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↗

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↗

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↗

Trellises and Trellis-Based Decoding Algorithms for Linear Block Codes

A code trellis is a graphical representation of a code, block or convolutional, in which every path represents a codeword (or a code sequence for a convolutional code). This representation makes it possible to implement Maximum Likelihood Decoding (MLD) of a code with reduced decoding complexity. The most well known trellis-based MLD algorithm is the Viterbi algorithm. The trellis representation was first introduced and used for convolutional codes [23]. This representation, together with the Viterbi decoding algorithm, has resulted in a wide range of applications of convolutional codes for error control in digital communications over the last two decades. There are two major reasons for this inactive period of research in this area. First, most coding theorists at that time believed that block codes did not have simple trellis structure like convolutional codes and maximum likelihood decoding of linear block codes using the Viterbi algorithm was practically impossible, except for very short block codes. Second, since almost all of the linear block codes are constructed algebraically or based on finite geometries, it was the belief of many coding theorists that algebraic decoding was the only way to decode these codes. These two reasons seriously hindered the development of efficient soft-decision decoding methods for linear block codes and their applications to error control in digital communications. This led to a general belief that block codes are inferior to convolutional codes and hence, that they were not useful. Chapter 2 gives a brief review of linear block codes. The goal is to provide the essential background material for the development of trellis structure and trellis-based decoding algorithms for linear block codes in the later chapters. Chapters 3 through 6 present the fundamental concepts, finite-state machine model, state space formulation, basic structural properties, state labeling, construction procedures, complexity, minimality, and sectionalization of trellises. Chapter 7 discusses trellis decomposition and subtrellises for low-weight codewords. Chapter 8 first presents well known methods for constructing long powerful codes from short component codes or component codes of smaller dimensions, and then provides methods for constructing their trellises which include Shannon and Cartesian product techniques. Chapter 9 deals with convolutional codes, puncturing, zero-tail termination and tail-biting.Chapters 10 through 13 present various trellis-based decoding algorithms, old and new. Chapter 10 first discusses the application of the well known Viterbi decoding algorithm to linear block codes, optimum sectionalization of a code trellis to minimize computation complexity, and design issues for IC (integrated circuit) implementation of a Viterbi decoder. Then it presents a new decoding algorithm for convolutional codes, named Differential Trellis Decoding (DTD) algorithm. Chapter 12 presents a suboptimum reliability-based iterative decoding algorithm with a low-weight trellis search for the most likely codeword. This decoding algorithm provides a good trade-off between error performance and decoding complexity. All the decoding algorithms presented in Chapters 10 through 12 are devised to minimize word error probability. Chapter 13 presents decoding algorithms that minimize bit error probability and provide the corresponding soft (reliability) information at the output of the decoder. Decoding algorithms presented are the MAP (maximum a posteriori probability) decoding algorithm and the Soft-Output Viterbi Algorithm (SOVA) algorithm. Finally, the minimization of bit error probability in trellis-based MLD is discussed.

Lin, Shu↗

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

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

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↗

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↗

Analysis of a parallelized nonlinear elliptic boundary value problem solver with application to reacting flows

A parallelized finite difference code based on the Newton method for systems of nonlinear elliptic boundary value problems in two dimensions is analyzed in terms of computational complexity and parallel efficiency. An approximate cost function depending on 15 dimensionless parameters is derived for algorithms based on stripwise and boxwise decompositions of the domain and a one-to-one assignment of the strip or box subdomains to processors. The sensitivity of the cost functions to the parameters is explored in regions of parameter space corresponding to model small-order systems with inexpensive function evaluations and also a coupled system of nineteen equations with very expensive function evaluations. The algorithm was implemented on the Intel Hypercube, and some experimental results for the model problems with stripwise decompositions are presented and compared with the theory. In the context of computational combustion problems, multiprocessors of either message-passing or shared-memory type may be employed with stripwise decompositions to realize speedup of O(n), where n is mesh resolution in one direction, for reasonable n.

Keyes, David E.↗

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↗

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↗

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↗

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↗

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↗

Approximate tensor-product preconditioners for very high order discontinuous Galerkin methods

In this study, we develop a new tensor-product based preconditioner for discontinuous Galerkin methods with polynomial degrees higher than those typically employed. This preconditioner uses an automatic, purely algebraic method to approximate the exact block Jacobi preconditioner by Kronecker products of several small, one-dimensional matrices. Traditional matrix-based preconditioners require O ( p 2d ) storage and O ( p 3d ) computational work, where p is the degree of basis polynomials used, and d is the spatial dimension. Our SVD-based tensor-product preconditioner requires O ( p d+1 ) storage, O ( p d+1 ) work in two spatial dimensions, and O ( p d+2 ) work in three spatial dimensions. Combined with a matrix-free Newton–Krylov solver, these preconditioners allow for the solution of DG systems in linear time in p per degree of freedom in 2D, and reduce the computational complexity from O ( p 9 ) to O ( p 5 ) in 3D. Numerical results are shown in 2D and 3D for the advection, Euler, and Navier–Stokes equations, using polynomials of degree up to p = 30. For many test cases, the preconditioner results in similar iteration counts when compared with the exact block Jacobi preconditioner, and performance is significantly improved for high polynomial degrees p .

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

Experimental Setup and Learning-Based AI Model for Developing Accurate PV Inverter Models [Slides]

The integration of power electronics-based interfaces presents challenges due to the absence of detailed models and the high computational complexity. Generic models used in system studies lack accuracy in capturing converter dynamics. This paper proposes a data-driven approach developed from experimental setup data. This approach enhances accuracy in photovoltaic inverter modeling. We used two types of PV inverters in the experiment. The recorded experimental data undergo processing through a machine learning model. Results from the model trained through machine learning is also presented.

14 SOLAR ENERGY↗

miniVite: A Graph Analytics Benchmarking Tool for Massively Parallel Systems

Benchmarking of high performance computing sys-tems can help provide critical insights for ef?cient design of computing systems and software applications. Although a large number of tools for benchmarking exist, there is a lack of rep-resentative benchmarks for the class of irregular computations as exempli?ed by graph analytics. In this paper, we propose miniVite as a representative graph analytics benchmark tool to test a variety of distributed-memory systems. Graph clustering, popularly known as community detection, is a prototypical graph operation used in numerous scienti?c computing and analytics applications. The goal of clustering is to partition a graph into clusters (or communities) such that each cluster consists of vertices that are densely connected within the cluster and sparsely connected to the rest of the graph. Modu-larity optimization is a popular technique for identifying clusters in a graph. Ef?cient parallelization of modularity optimization-based algorithms is challenging. One successful approach was conceived in Vite, a distributed-memory implementation of the Louvain algorithm that incorporates several heuristics. We introduce miniVite as a representative but simpli?ed variant of Vite, to serve as a prototypical graph analytics benchmarking tool. Unlike other graph-based methods such as breadth-?rst search and betweenness centrality, miniVite represents highly complex computational patterns stressing a variety of system features, which can provide crucial insight for co-design of future computing systems.

community detection, parallel, MPI↗