Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “decomposition algorithms”

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 721 records · Page 40
All sourcesNASA NTRSDOE OSTI
NASA NTRS2000

Airbreathing Propulsion System Analysis Using Multithreaded Parallel Processing

In this paper, parallel processing is used to analyze the mixing, and combustion behavior of hypersonic flow. Preliminary work for a sonic transverse hydrogen jet injected from a slot into a Mach 4 airstream in a two-dimensional duct combustor has been completed [Moon and Chung, 1996]. Our aim is to extend this work to three-dimensional domain using multithreaded domain decomposition parallel processing based on the flowfield-dependent variation theory. Numerical simulations of chemically reacting flows are difficult because of the strong interactions between the turbulent hydrodynamic and chemical processes. The algorithm must provide an accurate representation of the flowfield, since unphysical flowfield calculations will lead to the faulty loss or creation of species mass fraction, or even premature ignition, which in turn alters the flowfield information. Another difficulty arises from the disparity in time scales between the flowfield and chemical reactions, which may require the use of finite rate chemistry. The situations are more complex when there is a disparity in length scales involved in turbulence. In order to cope with these complicated physical phenomena, it is our plan to utilize the flowfield-dependent variation theory mentioned above, facilitated by large eddy simulation. Undoubtedly, the proposed computation requires the most sophisticated computational strategies. The multithreaded domain decomposition parallel processing will be necessary in order to reduce both computational time and storage. Without special treatments involved in computer engineering, our attempt to analyze the airbreathing combustion appears to be difficult, if not impossible.

Schunk, Richard Gregory↗
NASA NTRS1998

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↗
DOE OSTI2022

Quantum annealing algorithms for Boolean tensor networks

Abstract Quantum annealers manufactured by D-Wave Systems, Inc., are computational devices capable of finding high-quality heuristic solutions of NP-hard problems. In this contribution, we explore the potential and effectiveness of such quantum annealers for computing Boolean tensor networks. Tensors offer a natural way to model high-dimensional data commonplace in many scientific fields, and representing a binary tensor as a Boolean tensor network is the task of expressing a tensor containing categorical (i.e., $$\{0, 1\}$$ { 0 , 1 } ) values as a product of low dimensional binary tensors. A Boolean tensor network is computed by Boolean tensor decomposition, and it is usually not exact. The aim of such decomposition is to minimize the given distance measure between the high-dimensional input tensor and the product of lower-dimensional (usually three-dimensional) tensors and matrices representing the tensor network. In this paper, we introduce and analyze three general algorithms for Boolean tensor networks: Tucker, Tensor Train, and Hierarchical Tucker networks. The computation of a Boolean tensor network is reduced to a sequence of Boolean matrix factorizations, which we show can be expressed as a quadratic unconstrained binary optimization problem suitable for solving on a quantum annealer. By using a novel method we introduce called parallel quantum annealing, we demonstrate that Boolean tensor’s with up to millions of elements can be decomposed efficiently using a DWave 2000Q quantum annealer.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2014

Extended temperature-accelerated dynamics: Enabling long-time full-scale modeling of large rare-event systems

A new method, the Extended Temperature-Accelerated Dynamics (XTAD), is introduced for modeling long-timescale evolution of large rare-event systems. The method is based on the Temperature-Accelerated Dynamics approach [M. Sørensen and A. Voter, J. Chem. Phys. 112, 9599 (2000)], but uses full-scale parallel molecular dynamics simulations to probe a potential energy surface of an entire system, combined with the adaptive on-the-fly system decomposition for analyzing the energetics of rare events. The method removes limitations on a feasible system size and enables to handle simultaneous diffusion events, including both large-scale concerted and local transitions. Due to the intrinsically parallel algorithm, XTAD not only allows studies of various diffusion mechanisms in solid state physics, but also opens the avenue for atomistic simulations of a range of technologically relevant processes in material science, such as thin film growth on nano- and microstructured surfaces.

37 INORGANIC, ORGANIC, PHYSICAL, AND ANALYTICAL CH↗
DOE OSTI2021

Parallel physics-informed neural networks via domain decomposition

Here we develop a distributed framework for the physics-informed neural networks (PINNs) based on two recent extensions, namely conservative PINNs (cPINNs) and extended PINNs (XPINNs), which employ domain decomposition in space and in time-space, respectively. This domain decomposition endows cPINNs and XPINNs with several advantages over the vanilla PINNs, such as parallelization capacity, large representation capacity, efficient hyperparameter tuning, and is particularly effective for multi-scale and multi-physics problems. Here, we present a parallel algorithm for cPINNs and XPINNs constructed with a hybrid programming model described by MPI + X, where X ∈ {CPUs, GPUs}. The main advantage of cPINN and XPINN over the more classical data and model parallel approaches is the flexibility of optimizing all hyperparameters of each neural network separately in each subdomain. We compare the performance of distributed cPINNs and XPINNs for various forward problems, using both weak and strong scalings. Our results indicate that for space domain decomposition, cPINNs are more efficient in terms of communication cost but XPINNs provide greater flexibility as they can also handle time-domain decomposition for any differential equations, and can deal with any arbitrarily shaped complex subdomains. To this end, we also present an application of the parallel XPINN method for solving an inverse diffusion problem with variable conductivity on the United States map, using ten regions as subdomains.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗
DOE OSTI2015

Modeling Rare Events in High Dimensional Stochastics Systems

The main issue addressed in this note is the study of an algorithm to accelerate the computation of kinetic rates in the context of molecular dynamics(MD). It is based on parallel simulations of short-time trajectories and its main components are: a decomposition of phase space into macrostates or cells, a resampling procedure that ensures that the number of parallel replicas (MD simulations) in each macro-state remains constant, the use of multiple populations (colored replicas) to compute multiple rates (e.g., forward and backward rates) in one simulation. The method leads to enhancing the sampling of macro-states associated to the transition states, since in traditional MD these are likely to be depleted even after short-time simulations. By allowing parallel replicas to carry different probabilistic weights, the number of replicas within each macro-state can be maintained constant without introducing any bias. The empirical variance of the estimated reaction rate, defined as a probability flux, is expectedly diminished. This note is a first attempt towards a better mathematical and numerical understanding of this method. It provides first a mathematical formalization of the notion of colors. Then, the link between this algorithm and a set of closely related methods having been proposed in the literature within the past few years is discussed. Lastly, numerical results are provided that illustrate the efficiency of the method.

59 BASIC BIOLOGICAL SCIENCES↗
DOE OSTI2014

TU-A-12A-12: Improved Airway Measurement Accuracy for Low Dose Quantitative CT (qCT) Using Statistical (ASIR), at Reduced DFOV, and High Resolution Kernels in a Phantom and Swine Model

Purpose: Quantitative accuracy of Iodine Hounsfield Unit (HU) in conventional single-kVp scanning is susceptible to beam-hardening effect. Dual-energy CT has unique capabilities of quantification using monochromatic CT images, but this scanning mode requires the availability of the state-of-the-art CT scanner and, therefore, is limited in routine clinical practice. Purpose of this work was to develop a beam-hardening-correction (BHC) for single-kVp CT that can linearize Iodine projections at any nominal energy, apply this approach to study Iodine response with respect to keV, and compare with dual-energy based monochromatic images obtained from material-decomposition using 80kVp and 140kVp. Methods: Tissue characterization phantoms (Gammex Inc.), containing solid-Iodine inserts of different concentrations, were scanned using GE multi-slice CT scanner at 80, 100, 120, and 140 kVp. A model-based BHC algorithm was developed where Iodine was estimated using re-projection of image volume and corrected through an iterative process. In the correction, the re-projected Iodine was linearized using a polynomial mapping between monochromatic path-lengths at various nominal energies (40 to 140 keV) and physically modeled polychromatic path-lengths. The beam-hardening-corrected 80kVp and 140kVp images (linearized approximately at effective energy of the beam) were used for dual-energy material-decomposition in Water-Iodine basis-pair followed by generation of monochromatic images. Characterization of Iodine HU and noise in the images obtained from singlekVp with BHC at various nominal keV, and corresponding dual-energy monochromatic images, was carried out. Results: Iodine HU vs. keV response from single-kVp with BHC and dual-energy monochromatic images were found to be very similar, indicating that single-kVp data may be used to create material specific monochromatic equivalent using modelbased projection linearization. Conclusion: This approach may enable quantification of Iodine contrast enhancement and potential reduction in injected contrast without using dual-energy scanning. However, in general, dual-energy scanning has unique value in material characterization and quantification, and its value cannot be discounted. GE Healthcare Employee.

62 RADIOLOGY AND NUCLEAR MEDICINE↗
NASA NTRS2013

An Efficient Model-based Diagnosis Engine for Hybrid Systems Using Structural Model Decomposition

Complex hybrid systems are present in a large range of engineering applications, like mechanical systems, electrical circuits, or embedded computation systems. The behavior of these systems is made up of continuous and discrete event dynamics that increase the difficulties for accurate and timely online fault diagnosis. The Hybrid Diagnosis Engine (HyDE) offers flexibility to the diagnosis application designer to choose the modeling paradigm and the reasoning algorithms. The HyDE architecture supports the use of multiple modeling paradigms at the component and system level. However, HyDE faces some problems regarding performance in terms of complexity and time. Our focus in this paper is on developing efficient model-based methodologies for online fault diagnosis in complex hybrid systems. To do this, we propose a diagnosis framework where structural model decomposition is integrated within the HyDE diagnosis framework to reduce the computational complexity associated with the fault diagnosis of hybrid systems. As a case study, we apply our approach to a diagnostic testbed, the Advanced Diagnostics and Prognostics Testbed (ADAPT), using real data.

Structural Decomposition↗
DOE OSTI2025

Sylvester-preconditioned adaptive-rank implicit time integrators for advection-diffusion equations with variable coefficients

Here, we consider the adaptive-rank integration of multi-dimensional time-dependent advection-diffusion partial differential equations (PDEs) with variable coefficients. We employ a standard finite-difference method for spatial discretization coupled with high-order diagonally implicit Runge-Kutta temporal schemes. The discrete equation is a generalized Sylvester equation (GSE), which we solve with a projection-based adaptive-rank algorithm structured around two key strategies: (i) constructing dimension-wise subspaces using a novel atypical extended Krylov strategy, and (ii) efficiently solving the basis coefficient matrix with a preconditioned GMRES solver. The low-rank decomposition is performed in 2D using SVD and with high-order SVD (HOSVD) in 3D to represent the tensor in a compressed Tucker format. For d-dimensional problems (here, d = 2 or 3), the computational complexity and memory storage of the approach are found numerically to scale as and $\mathscr{O}(Nr^2) + \mathscr{O} (r^{d+1})$ and $\mathscr{O}(Nr) + \mathscr{O} (r^{d})$, respectively, with the one-dimensional resolution and the maximal rank during the Krylov iteration (which we find to be largely independent of on our numerical examples). We present numerical examples that illustrate the advertised properties of the algorithm.

97 MATHEMATICS AND COMPUTING↗
NASA NTRS2009

Regression Model Optimization for the Analysis of Experimental Data

A candidate math model search algorithm was developed at Ames Research Center that determines a recommended math model for the multivariate regression analysis of experimental data. The search algorithm is applicable to classical regression analysis problems as well as wind tunnel strain gage balance calibration analysis applications. The algorithm compares the predictive capability of different regression models using the standard deviation of the PRESS residuals of the responses as a search metric. This search metric is minimized during the search. Singular value decomposition is used during the search to reject math models that lead to a singular solution of the regression analysis problem. Two threshold dependent constraints are also applied. The first constraint rejects math models with insignificant terms. The second constraint rejects math models with near-linear dependencies between terms. The math term hierarchy rule may also be applied as an optional constraint during or after the candidate math model search. The final term selection of the recommended math model depends on the regressor and response values of the data set, the user s function class combination choice, the user s constraint selections, and the result of the search metric minimization. A frequently used regression analysis example from the literature is used to illustrate the application of the search algorithm to experimental data.

Ulbrich, N.↗
DOE OSTI2017

Contaminant source identification using semi-supervised machine learning

Identification of the original groundwater types present in geochemical mixtures observed in an aquifer is a challenging but very important task. Frequently, some of the groundwater types are related to different infiltration and/or contamination sources associated with various geochemical signatures and origins. The characterization of groundwater mixing processes typically requires solving complex inverse models representing groundwater flow and geochemical transport in the aquifer, where the inverse analysis accounts for available site data. Usually, the model is calibrated against the available data characterizing the spatial and temporal distribution of the observed geochemical types. Numerous different geochemical constituents and processes may need to be simulated in these models which further complicates the analyses. In this paper, we propose a new contaminant source identification approach that performs decomposition of the observation mixtures based on Non-negative Matrix Factorization (NMF) method for Blind Source Separation (BSS), coupled with a custom semi-supervised clustering algorithm. Our methodology, called NMFk, is capable of identifying (a) the unknown number of groundwater types and (b) the original geochemical concentration of the contaminant sources from measured geochemical mixtures with unknown mixing ratios without any additional site information. NMFk is tested on synthetic and real-world site data. Finally, the NMFk algorithm works with geochemical data represented in the form of concentrations, ratios (of two constituents; for example, isotope ratios), and delta notations (standard normalized stable isotope ratios).

54 ENVIRONMENTAL SCIENCES↗
DOE OSTI2014

The metallization and superconductivity of dense hydrogen sulfide

Hydrogen sulfide (H{sub 2}S) is a prototype molecular system and a sister molecule of water (H{sub 2}O). The phase diagram of solid H{sub 2}S at high pressures remains largely unexplored arising from the challenges in dealing with the pressure-induced weakening of S–H bond and larger atomic core difference between H and S. Metallization is yet achieved for H{sub 2}O, but it was observed for H{sub 2}S above 96 GPa. However, the metallic structure of H{sub 2}S remains elusive, greatly impeding the understanding of its metallicity and the potential superconductivity. We have performed an extensive structural study on solid H{sub 2}S at pressure ranges of 10–200 GPa through an unbiased structure prediction method based on particle swarm optimization algorithm. Besides the findings of candidate structures for nonmetallic phases IV and V, we are able to establish stable metallic structures violating an earlier proposal of elemental decomposition into sulfur and hydrogen [R. Rousseau, M. Boero, M. Bernasconi, M. Parrinello, and K. Terakura, Phys. Rev. Lett. 85, 1254 (2000)]. Our study unravels a superconductive potential of metallic H{sub 2}S with an estimated maximal transition temperature of ∼80 K at 160 GPa, higher than those predicted for most archetypal hydrogen-containing compounds (e.g., SiH{sub 4}, GeH{sub 4}, etc.)

37 INORGANIC, ORGANIC, PHYSICAL, AND ANALYTICAL CH↗
NASA NTRS1995

Development of Fast Algorithms Using Recursion, Nesting and Iterations for Computational Electromagnetics

In the first phase of our work, we have concentrated on laying the foundation to develop fast algorithms, including the use of recursive structure like the recursive aggregate interaction matrix algorithm (RAIMA), the nested equivalence principle algorithm (NEPAL), the ray-propagation fast multipole algorithm (RPFMA), and the multi-level fast multipole algorithm (MLFMA). We have also investigated the use of curvilinear patches to build a basic method of moments code where these acceleration techniques can be used later. In the second phase, which is mainly reported on here, we have concentrated on implementing three-dimensional NEPAL on a massively parallel machine, the Connection Machine CM-5, and have been able to obtain some 3D scattering results. In order to understand the parallelization of codes on the Connection Machine, we have also studied the parallelization of 3D finite-difference time-domain (FDTD) code with PML material absorbing boundary condition (ABC). We found that simple algorithms like the FDTD with material ABC can be parallelized very well allowing us to solve within a minute a problem of over a million nodes. In addition, we have studied the use of the fast multipole method and the ray-propagation fast multipole algorithm to expedite matrix-vector multiplication in a conjugate-gradient solution to integral equations of scattering. We find that these methods are faster than LU decomposition for one incident angle, but are slower than LU decomposition when many incident angles are needed as in the monostatic RCS calculations.

Chew, W. C.↗
DOE OSTI2022

A Hybrid Method for Tensor Decompositions that Leverages Stochastic and Deterministic Optimization

In this paper, we propose a hybrid method that uses stochastic and deterministic search to compute the maximum likelihood estimator of a low-rank count tensor with Poisson loss via state-of-theart local methods. Our approach is inspired by Simulated Annealing for global optimization and allows for fine-grain parameter tuning as well as adaptive updates to algorithm parameters. We present numerical results that indicate our hybrid approach can compute better approximations to the maximum likelihood estimator with less computation than the state-of-the-art methods by themselves.

97 MATHEMATICS AND COMPUTING↗
NASA NTRS2021

Small UAV Flight Planning in Urban Environments

This work proposes a fast algorithm for generating obstacle-free and wind-efficient flight paths at a constant above-ground-level altitude in urban environments because a fast flight path planning algorithm is an essential function or service needed for enabling small unmanned aerial vehicle (sUAV) to operate in urban environments within Class G airspace. The proposed method first converts the 3D path planning problem to a 2D problem by constructing an obstacle map at a given above-ground-level altitude. A quad-tree decomposition is then used to build a search space in terms of obstacle occupancy and wind difference. The wind cost of traveling through each cell is defined based on energy consumption under various wind conditions. A repulsive potential is also adopted to make sure that the flight plans stay away from obstacles. The Theta* search algorithm, a variant of A* algorithm, is applied to mitigate the path angle change constraints introduced by grid-based graphs. With the Theta* and postsmoothing techniques, an obstacle-free, wind efficient, and constant above-ground-level flight plan can be quickly generated for sUAV operations in urban environments while meeting the lateral path angle constraints. The results showed that the path planning algorithm is efficient and can be finished within several seconds. With a proper choice of wind coefficient, the proposed path planning algorithm outperforms the multiple-shooting trajectory optimization method even in an obstacle-free environment. With the flexibility of incorporating other geo-related costs and computation efficiency, the proposed algorithm shows the potential for real-time flight path planning in complex urban environments.

Path planning↗
DOE OSTI2023

Granger Causality for prediction in Dynamic Mode Decomposition: Application to power systems

Here, the dynamic mode decomposition (DMD) technique extracts the dominant modes characterizing the innate dynamical behavior of the system within the measurement data. For appropriate identification of dominant modes from the measurement data, the DMD algorithm necessitates ensuring the quality of the input measurement data sequences. On that account, for validating the usability of the dataset for the DMD algorithm, the paper proposed two conditions: Persistence of excitation (PE) and the Granger Causality Test (GCT). The virtual data sequences are designed with the hankel matrix representation such that the dimensions of the subspace spanning the essential system modes are increased with the addition of new state variables. The PE condition provides the lower bound for the trajectory length, and the GCT provides the order of the model. Satisfying the PE condition enables estimating an approximate linear model, but the predictability with the identified model is only assured with the temporal causation among data searched with GCT. The proposed methodology is validated with the application for coherency identification (CI) in a multi-machine power system (MMPS), an essential phenomenon in transient stability analysis. The significance of PE condition and GCT is demonstrated through various case studies implemented on 22 bus six generator system.

24 POWER TRANSMISSION AND DISTRIBUTION↗
NASA NTRS2022

Alternative regularizations for Outer-Approximation algorithms for convex MINLP

In this work, we extend the regularization framework from Kronqvist et al. (Math Program 180(1):285–310, 2020) by incorporating several new regularization functions and develop a regularized single-tree search method for solving convex mixed-integer nonlinear programming (MINLP) problems. We propose a set of regularization functions based on distance metrics and Lagrangean approximations, used in the projection problem for finding new integer combinations to be used within the Outer-Approximation (OA) method. The new approach, called Regularized Outer-Approximation (ROA), has been implemented as part of the open-source Mixed-integer nonlinear decomposition toolbox for Pyomo—MindtPy. We compare the OA method with seven regularization function alternatives for ROA. Moreover, we extend the LP/NLP Branch and Bound method proposed by Quesada and Grossmann (Comput Chem Eng 16(10–11):937–947, 1992) to include regularization in an algorithm denoted RLP/NLP. We provide convergence guarantees for both ROA and RLP/NLP. Finally, we perform an extensive computational experiment considering all convex MINLP problems in the benchmark library MINLPLib. The computational results show clear advantages of using regularization combined with the OA method.

Convex Mixed-integer nonlinear programming↗
DOE OSTI2018

Partially coherent ptychography by gradient decomposition of the probe

Coherent ptychographic imaging experiments often discard the majority of the flux from a light source to define the coherence of the illumination. Even when the coherent flux is sufficient, the stability required during an exposure is another important limiting factor. Partial coherence analysis can considerably reduce these limitations. A partially coherent illumination can often be written as the superposition of a single coherent illumination convolved with a separable translational kernel. This article proposes the gradient decomposition of the probe (GDP), a model that exploits translational kernel separability, coupling the variances of the kernel with the transverse coherence. An efficient first-order splitting algorithm ( GDP-ADMM ) for solving the proposed nonlinear optimization problem is described. Numerical experiments demonstrate the effectiveness of the proposed method with Gaussian and binary kernel functions in fly-scan measurements. Remarkably, GDP-ADMM using nanoprobes produces satisfactory results even when the ratio between the kernel width and the beam size is more than one, or when the distance between successive acquisitions is twice as large as the beam width.

46 INSTRUMENTATION RELATED TO NUCLEAR SCIENCE AND ↗