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 379 records · Page 21
All sourcesNASA NTRSDOE OSTI
NASA NTRS1985

Improving the Effectiveness of Integral Property Calculation in a CSG Solid Modeling System by Exploiting Predictability

Integral property calculation is an important application for solid modeling systems. Algorithms for computing integral properties for various solid representation schemes are fairly well known. It is important to deigners and users of solid modeling systems to understand the behavior of such algorithms. Specifically the trade-off between execution time and accuracy is critical to effective use of integral property calculation. The average behavior of two algorithms for Constructive Solid Geometry (CSG) representations is investigated. Experimental results from the PADL-2 solid modeling system show that coarse decompositions can be used to predict execution time and error estimates for finer decompositions. Exploiting this predictability allow effective use of the algorithms in a solid modeling system.

Clark, A. L.↗
NASA NTRS1993

Parallel O(log n) algorithms for open- and closed-chain rigid multibody systems based on a new mass matrix factorization technique

In this paper, parallel O(log n) algorithms for computation of rigid multibody dynamics are developed. These parallel algorithms are derived by parallelization of new O(n) algorithms for the problem. The underlying feature of these O(n) algorithms is a drastically different strategy for decomposition of interbody force which leads to a new factorization of the mass matrix (M). Specifically, it is shown that a factorization of the inverse of the mass matrix in the form of the Schur Complement is derived as M(exp -1) = C - B(exp *)A(exp -1)B, wherein matrices C, A, and B are block tridiagonal matrices. The new O(n) algorithm is then derived as a recursive implementation of this factorization of M(exp -1). For the closed-chain systems, similar factorizations and O(n) algorithms for computation of Operational Space Mass Matrix lambda and its inverse lambda(exp -1) are also derived. It is shown that these O(n) algorithms are strictly parallel, that is, they are less efficient than other algorithms for serial computation of the problem. But, to our knowledge, they are the only known algorithms that can be parallelized and that lead to both time- and processor-optimal parallel algorithms for the problem, i.e., parallel O(log n) algorithms with O(n) processors. The developed parallel algorithms, in addition to their theoretical significance, are also practical from an implementation point of view due to their simple architectural requirements.

Fijany, Amir↗
DOE OSTI2020

Randomized Projection for Rank-Revealing Matrix Factorizations and Low-Rank Approximations

Rank-revealing matrix decompositions provide an essential tool in spectral analysis of matrices, including the Singular Value Decomposition (SVD) and related low-rank approximation techniques. QR with Column Pivoting (QRCP) is usually suitable for these purposes, but it can be much slower than the unpivoted QR algorithm. For large matrices, the difference in performance is due to increased communication between the processor and slow memory, which QRCP needs in order to choose pivots during decomposition. Our main algorithm, Randomized QR with Column Pivoting (RQRCP), uses randomized projection to make pivot decisions from a much smaller sample matrix, which we can construct to reside in a faster level of memory than the original matrix. This technique may be understood as trading vastly reduced communication for a controlled increase in uncertainty during the decision process. Furthermore, for rank-revealing purposes, the selection mechanism in RQRCP produces results that are the same quality as the standard algorithm, but with performance near that of unpivoted QR (often an order of magnitude faster for large matrices). Additionally, we also propose two formulas that facilitate further performance improvements. The first efficiently updates sample matrices to avoid computing new randomized projections. The second avoids large trailing updates during the decomposition in truncated low-rank approximations. Our truncated version of RQRCP also provides a key initial step in our truncated SVD approximation, TUXV. These advances open up a new performance domain for large matrix factorizations that will support efficient problem-solving techniques for challenging applications in science, engineering, and data analysis.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2020

Computationally Efficient Decompositions of Oblique Projection Matrices

Oblique projection matrices arise in problems in weighted least squares, signal processing, and optimization. While these matrices can be potentially very large, their low-rank structure can be exploited for efficient computation. Here, we propose fast and scalable algorithms for computing their eigendecomposition and singular value decomposition (SVD). Numerical experiments that compare our proposed approaches to existing methods, including randomized SVD, are presented. In addition, we test their accuracy on linear systems from equality constrained optimization problems.

97 MATHEMATICS AND COMPUTING↗
NASA NTRS1989

Novel techniques for data decomposition and load balancing for parallel processing of vision systems: Implementation and evaluation using a motion estimation system

Computer vision systems employ a sequence of vision algorithms in which the output of an algorithm is the input of the next algorithm in the sequence. Algorithms that constitute such systems exhibit vastly different computational characteristics, and therefore, require different data decomposition techniques and efficient load balancing techniques for parallel implementation. However, since the input data for a task is produced as the output data of the previous task, this information can be exploited to perform knowledge based data decomposition and load balancing. Presented here are algorithms for a motion estimation system. The motion estimation is based on the point correspondence between the involved images which are a sequence of stereo image pairs. Researchers propose algorithms to obtain point correspondences by matching feature points among stereo image pairs at any two consecutive time instants. Furthermore, the proposed algorithms employ non-iterative procedures, which results in saving considerable amounts of computation time. The system consists of the following steps: (1) extraction of features; (2) stereo match of images in one time instant; (3) time match of images from consecutive time instants; (4) stereo match to compute final unambiguous points; and (5) computation of motion parameters.

Choudhary, Alok Nidhi↗
NASA NTRS1992

A transient FETI methodology for large-scale parallel implicit computations in structural mechanics

Explicit codes are often used to simulate the nonlinear dynamics of large-scale structural systems, even for low frequency response, because the storage and CPU requirements entailed by the repeated factorizations traditionally found in implicit codes rapidly overwhelm the available computing resources. With the advent of parallel processing, this trend is accelerating because explicit schemes are also easier to parallelize than implicit ones. However, the time step restriction imposed by the Courant stability condition on all explicit schemes cannot yet -- and perhaps will never -- be offset by the speed of parallel hardware. Therefore, it is essential to develop efficient and robust alternatives to direct methods that are also amenable to massively parallel processing because implicit codes using unconditionally stable time-integration algorithms are computationally more efficient when simulating low-frequency dynamics. Here we present a domain decomposition method for implicit schemes that requires significantly less storage than factorization algorithms, that is several times faster than other popular direct and iterative methods, that can be easily implemented on both shared and local memory parallel processors, and that is both computationally and communication-wise efficient. The proposed transient domain decomposition method is an extension of the method of Finite Element Tearing and Interconnecting (FETI) developed by Farhat and Roux for the solution of static problems. Serial and parallel performance results on the CRAY Y-MP/8 and the iPSC-860/128 systems are reported and analyzed for realistic structural dynamics problems. These results establish the superiority of the FETI method over both the serial/parallel conjugate gradient algorithm with diagonal scaling and the serial/parallel direct method, and contrast the computational power of the iPSC-860/128 parallel processor with that of the CRAY Y-MP/8 system.

Farhat, Charbel↗
DOE OSTI2018

Optimizing adiabatic quantum program compilation using a graph-theoretic framework

Adiabatic quantum computing has evolved in recent years from a theoretical field into an immensely practical area, a change partially sparked by D-Wave System’s quantum annealing hardware. These multimillion-dollar quantum annealers offer the potential to solve optimization problems millions of times faster than classical heuristics, prompting researchers at Google, NASA and Lockheed Martin to study how these computers can be applied to complex real-world problems such as NASA rover missions. Unfortunately, compiling (embedding) an optimization problem into the annealing hardware is itself a difficult optimization problem and a major bottleneck currently preventing widespread adoption. Additionally, while finding a single embedding is difficult, no generalized method is known for tuning embeddings to use minimal hardware resources. To address these barriers, we introduce a graph-theoretic framework for developing structured embedding algorithms. Using this framework, we introduce a biclique virtual hardware layer to provide a simplified interface to the physical hardware. Additionally, we exploit bipartite structure in quantum programs using odd cycle transversal (OCT) decompositions. By coupling an OCT-based embedding algorithm with new, generalized reduction methods, we develop a new baseline for embedding a wide range of optimization problems into fault-free D-Wave annealing hardware. Furthermore, to encourage the reuse and extension of these techniques, we provide an implementation of the framework and embedding algorithms.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2015

Parallel Computation of Persistent Homology using the Blowup Complex

We describe a parallel algorithm that computes persistent homology, an algebraic descriptor of a filtered topological space. Our algorithm is distinguished by operating on a spatial decomposition of the domain, as opposed to a decomposition with respect to the filtration. We rely on a classical construction, called the Mayer--Vietoris blowup complex, to glue global topological information about a space from its disjoint subsets. We introduce an efficient algorithm to perform this gluing operation, which may be of independent interest, and describe how to process the domain hierarchically. We report on a set of experiments that help assess the strengths and identify the limitations of our method.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2020

Rendezvous algorithms for large-scale modeling and simulation

Rendezvous algorithms encode a communication pattern that is useful when processors sending data do not know who the receiving processors should be, or vice versa. The idea is to define an intermediate decomposition where datums from different sending processors can ”rendezvous” to perform a computation, in a manner that both the senders and eventual receivers of the results can identify the appropriate rendezvous processor. Though they were originally designed for interpolating between overlaid grids with independent parallel decompositions (Plimpton et al., 2004), we have recently found rendezvous algorithms useful for a variety of operations in particle- or grid-based simulation codes when running large problems on large numbers of processors. In particular, we show they can perform well when a load-balanced intermediate decomposition is randomized and not spatial, requiring all-to-all communication to move data between processors. In this case rendezvous algorithms leverage the large bisection communication bandwidths which parallel machines provide. We describe how rendezvous algorithms work in a scientific computing context and give specific examples for molecular dynamics and Direct Simulation Monte Carlo codes which result in dramatic performance improvements versus simpler algorithms which do not scale as well. We explain how a generic rendezvous algorithm can be implemented, and also point out similarities with the MapReduce paradigm popularized by Google and Hadoop.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2018

Parallel Nonnegative CP Decomposition of Dense Tensors

The CP tensor decomposition is a low-rank approximation of a tensor. We present a distributed-memory parallel algorithm and implementation of an alternating optimization method for computing a CP decomposition of dense tensors that can enforce nonnegativity of the computed low-rank factors. The principal task is to parallelize the Matricized-Tensor Times Khatri-Rao Product (MTTKRP) bottleneck subcomputation. The algorithm is computation efficient, using dimension trees to avoid redundant computation across MTTKRPs within the alternating method. Our approach is also communication efficient, using a data distribution and parallel algorithm across a multidimensional processor grid that can be tuned to minimize communication. We benchmark our software on synthetic as well as hyperspectral image and neuroscience dynamic functional connectivity data, demonstrating that our algorithm scales well to 100s of nodes (up to 4096 cores) and is faster and more general than the currently available parallel software.

Ballard, Grey↗
DOE OSTI2015

Algorithms for propagating uncertainty across heterogeneous domains

We address an important research area in stochastic multi-scale modeling, namely the propagation of uncertainty across heterogeneous domains characterized by partially correlated processes with vastly different correlation lengths. This class of problems arise very often when computing stochastic PDEs and particle models with stochastic/stochastic domain interaction but also with stochastic/deterministic coupling. The domains may be fully embedded, adjacent or partially overlapping. The fundamental open question we address is the construction of proper transmission boundary conditions that preserve global statistical properties of the solution across different subdomains. Often, the codes that model different parts of the domains are black-box and hence a domain decomposition technique is required. No rigorous theory or even effective empirical algorithms have yet been developed for this purpose, although interfaces defined in terms of functionals of random fields (e.g., multi-point cumulants) can overcome the computationally prohibitive problem of preserving sample-path continuity across domains. The key idea of the different methods we propose relies on combining local reduced-order representations of random fields with multi-level domain decomposition. Specifically, we propose two new algorithms: The first one enforces the continuity of the conditional mean and variance of the solution across adjacent subdomains by using Schwarz iterations. The second algorithm is based on PDE-constrained multi-objective optimization, and it allows us to set more general interface conditions. The effectiveness of these new algorithms is demonstrated in numerical examples involving elliptic problems with random diffusion coefficients, stochastically advected scalar fields, and nonlinear advection-reaction problems with random reaction rates.

Cho, Heyrim↗
NASA NTRS1990

Direct handling of equality constraints in multilevel optimization

In recent years there have been several hierarchic multilevel optimization algorithms proposed and implemented in design studies. Equality constraints are often imposed between levels in these multilevel optimizations to maintain system and subsystem variable continuity. Equality constraints of this nature will be referred to as coupling equality constraints. In many implementation studies these coupling equality constraints have been handled indirectly. This indirect handling has been accomplished using the coupling equality constraints' explicit functional relations to eliminate design variables (generally at the subsystem level), with the resulting optimization taking place in a reduced design space. In one multilevel optimization study where the coupling equality constraints were handled directly, the researchers encountered numerical difficulties which prevented their multilevel optimization from reaching the same minimum found in conventional single level solutions. The researchers did not explain the exact nature of the numerical difficulties other than to associate them with the direct handling of the coupling equality constraints. The coupling equality constraints are handled directly, by employing the Generalized Reduced Gradient (GRG) method as the optimizer within a multilevel linear decomposition scheme based on the Sobieski hierarchic algorithm. Two engineering design examples are solved using this approach. The results show that the direct handling of coupling equality constraints in a multilevel optimization does not introduce any problems when the GRG method is employed as the internal optimizer. The optimums achieved are comparable to those achieved in single level solutions and in multilevel studies where the equality constraints have been handled indirectly.

Renaud, John E.↗
DOE OSTI2026

Local reduced-order modeling for electrostatic plasmas by physics-informed solution manifold decomposition

Despite advancements in high-performance computing and modern numerical algorithms, computational cost remains prohibitive for multi-query kinetic plasma simulations. Here, in this work, we develop data-driven reduced-order models (ROMs) for collisionless electrostatic plasma dynamics, based on the kinetic Vlasov-Poisson equation. Our ROM approach projects the equation onto a linear subspace defined by the proper orthogonal decomposition (POD) modes. We introduce an efficient tensorial method to update the nonlinear term using a precomputed third-order tensor. We capture multiscale behavior with a minimal number of POD modes by decomposing the solution manifold into multiple time windows and creating temporally local ROMs. We consider two strategies for decomposition: one based on the physical time and the other based on the electric field energy. Applied to the 1D1V Vlasov–Poisson simulations, that is, prescribed E-field, Landau damping, and two-stream instability, we demonstrate that our ROMs accurately capture the total energy of the system both for parametric and time extrapolation cases. The temporally local ROMs are more efficient and accurate than the single ROM. In addition, in the two-stream instability case, we show that the energy-windowing reduced-order model (EW-ROM) is more efficient and accurate than the time-windowing reduced-order model (TW-ROM). With the tensorial approach, EW-ROM solves the equation approximately 90 times faster than Eulerian simulations while maintaining a maximum relative error of 7.5% for the training data and 11% for the testing data.

Electrostatic plasmas↗
DOE OSTI2016

Fast Parallel Stochastic Subspace Algorithms for Large-Scale Ambient Oscillation Monitoring

With the installation of synchrophasors widely across the power grid, measurement-based oscillation monitoring algorithms are becoming increasingly useful in identifying the real-time oscillatory modal properties in power systems. When the number of phasor measurement unit (PMU) channels grows, the computational time of many PMU data based algorithms is dominated by the computational burden in processing large-scale dense matrices. In order to overcome this limitation, this paper presents new formulations and computational strategies for speeding up an ambient oscillation monitoring algorithm, namely, stochastic subspace identification (SSI). Based on previous work, two fast singular value decomposition (SVD) approaches are first applied to the SVD evaluation within the SSI algorithm. Next, block structures are exploited so that the large-scale dense matrix computations can be processed in parallel. This helps in memory savings as well as in overall computational time. Experimental results from three sets of archived data of the western interconnection demonstrate that the new approaches can provide significant speedups while retaining modal estimation accuracy. With proposed fast parallel algorithms, the real-time oscillation monitoring of the large-scale system using hundreds of PMU measurements becomes feasible.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2016

Investigations on RELAP5-3D to RELAP5-3D coupling methodology by PVMEXEC

In the framework of a BEPU (Best Estimate Plus Uncertainty) approach within the licensing process of a nuclear power plant, the need to extend the resources of nuclear system thermal-hydraulics codes, such as RELAP5-3D, arises to allow more detailed simulations of the complex 3D reality of Nuclear Power Plants (NPPs), either under normal steady-state or during various accident scenarios. Currently, it is not possible to achieve the same degree of detail for a whole nuclear system when it is simulated with RELAP5-3D and this is due to the inherent limitations in the number of components and volumes to be used for the analysis. For this reason, it is of extreme interest the use of tools for codes coupling that enable the use of different codes for the simulation of different portions of a system in a unified analysis. In this paper the attention will be focused on the decomposition of the thermal-hydraulic domain of a system into subsystems to be simulated by different instances of the same code (e.g. RELAP5-3D) coupled together by means of PVMEXEC program and parallel virtual machine (PVM) technology. Explicit and semi-implicit solution algorithms were used for the analyses. Among the analyzed cases, the following will be discussed in detail with the aim to provide additional guidelines for the use of the PVMEXEC tool: (i) the Edward's pipe blowdown test, (ii) a simplified countercurrent heat exchanger, (iii) different hydraulics and heat structure coupling schemes for a shell-tube heat exchanger and (iv) a three-task coupled model of an adaptation of the Christensen subcooled boiling experiment. (authors)

22 GENERAL STUDIES OF NUCLEAR REACTORS↗
DOE OSTI2020

Attack-resilient algorithms and testbed federation for wide-area protection and control in smart grid

Today’s energy infrastructure is undergoing a massive transformation across all generation, transmission, and distribution systems to provide reliability, efficiency, and sustainability to the power system network. During the past 10 years, there has been a remarkable enhancement in developing close-loop wide-area protection and control (WAPAC) applications, such as automatic generation control (AGC), wide-area protection scheme (WAPS), synchrophasor-based wide-area voltage control system (WAVCS), etc., in the energy management system (EMS) to provide an adequate situational awareness to control center operators during physical disturbances and natural events. The rapid digitalization, unencrypted communication, and numerous data-sharing devices have increased digital access points that have exposed the grid network to countless cyberattacks pertinent to the WAPAC cybersecurity. Given the amount of complex grid network coupled with legacy infrastructures, it is untrustworthy to completely rely on information technology (IT)-based conventional security measures to defend against evolving cyberattacks. Hence, there is a compelling need to go beyond the traditional paradigm of ‘security by obscurity’ and ‘bolt-on’ security measures, and develop a suite of innovative security solutions at multiple layers to transform the current “fault-resilient” grid into “fault and attack-resilient” grid of the future. This dissertation specifically focuses on developing application-specific attack-resilient solutions for critical WAPAC applications in the smart grid. The first part of the study, Attack-Resilient Wide-Area Protection Scheme, presents a cyber-physical attack-resilient system (CPARS) for WAPS, where two anomaly detection methods are proposed to detect multi-level cyberattacks followed by the rules-based intrusion mitigation system (RIMS) to initiate effective mitigation strategies, tailored to these attacks, to restore the normal grid operation after disturbances. The first anomaly detection component, Machine learning-based Anomaly Detection for Centralized WAPS, discusses a novel architecture and methodology for developing a machine-learning-based anomaly detection system (ADS) for the centralized wide-area protection system (CWAPS) by applying the variational mode decomposition (VMD) technique and decision tree (DT) algorithms using cyber logs and synchrophasor measurements. The second component, Multi-Agent-based Anomaly Detection for Decentralized WAPS, presents a two-level hierarchical multi-agent-based decentralized WAPS against the system-aware stealthy cyber-attacks. Finally, for the RIMS, the state transition diagram-based mitigation measures are defined based on the grid operation states and experimental testing and evaluation are presented in a cyber-physical testbed environment. The second part of the study, Attack-Resilient Wide-Area Voltage Control System, addresses the existing vulnerabilities in the wide-area voltage control system (WAVCS), presents the methodology for performing an impact analysis during data integrity attacks, and proposes a data-driven attackresilient system (DARS) by incorporating machine learning-based ADS and rules-based anomaly mitigation system (RAMS) to detect these attacks and provide necessary mitigation actions to maintain the transient voltage stability after disturbances. Finally, the third part, Networked Federation Testbed (NEFTSec) for Smart Grid Cybersecurity, focuses on developing an interconnected federated testbed through a common network like the internet, describes its conceptual architectures, and also presents its design components for experimental testing, validation, and evaluation. Further, it presents the co-simulation interface algorithm (CIA) to facilitate the geographically-dispersed real-time distributed simulation (GD-RTDS) during the cyber-physical federation. In general, this dissertation presents innovative attack-resilient solutions for WAPAC applications that are experimentally tested and evaluated using the PowerCyber testbed and NEFTSec platform to accelerate the transition of state-of-the-art research works to the real-field deployments.

24 POWER TRANSMISSION AND DISTRIBUTION↗
DOE OSTI2020

Model-Free Data Authentication for Cyber Security in Power Systems

With the development and wide deployment of measurement equipment, data can be automatically measured and visualized for situation awareness in power systems. However, the cyber security of power systems is also threated by data spoofing attacks. This letter proposed a measurement data source authentication (MDSA) algorithm based on feature extraction techniques including ensemble empirical mode decomposition (EEMD) and fast Fourier transform (FFT), and machine learning for real-time measurement data classification. Compared with previous work, the proposed algorithm can achieve higher accuracy of MDSA using a shorter window of data from closely located synchrophasor measurement sensors.

24 POWER TRANSMISSION AND DISTRIBUTION↗
NASA NTRS1993

A transient FETI methodology for large-scale parallel implicit computations in structural mechanics, part 2

Explicit codes are often used to simulate the nonlinear dynamics of large-scale structural systems, even for low frequency response, because the storage and CPU requirements entailed by the repeated factorizations traditionally found in implicit codes rapidly overwhelm the available computing resources. With the advent of parallel processing, this trend is accelerating because explicit schemes are also easier to parallellize than implicit ones. However, the time step restriction imposed by the Courant stability condition on all explicit schemes cannot yet and perhaps will never be offset by the speed of parallel hardware. Therefore, it is essential to develop efficient and robust alternatives to direct methods that are also amenable to massively parallel processing because implicit codes using unconditionally stable time-integration algorithms are computationally more efficient than explicit codes when simulating low-frequency dynamics. Here we present a domain decomposition method for implicit schemes that requires significantly less storage than factorization algorithms, that is several times faster than other popular direct and iterative methods, that can be easily implemented on both shared and local memory parallel processors, and that is both computationally and communication-wise efficient. The proposed transient domain decomposition method is an extension of the method of Finite Element Tearing and Interconnecting (FETI) developed by Farhat and Roux for the solution of static problems. Serial and parallel performance results on the CRAY Y-MP/8 and the iPSC-860/128 systems are reported and analyzed for realistic structural dynamics problems. These results establish the superiority of the FETI method over both the serial/parallel conjugate gradient algorithm with diagonal scaling and the serial/parallel direct method, and contrast the computational power of the iPSC-860/128 parallel processor with that of the CRAY Y-MP/8 system.

Farhat, Charbel↗