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 343 records · Page 19
All sourcesNASA NTRSDOE OSTI
NASA NTRS1995

Algorithms for parallel flow solvers on message passing architectures

The purpose of this project has been to identify and test suitable technologies for implementation of fluid flow solvers -- possibly coupled with structures and heat equation solvers -- on MIMD parallel computers. In the course of this investigation much attention has been paid to efficient domain decomposition strategies for ADI-type algorithms. Multi-partitioning derives its efficiency from the assignment of several blocks of grid points to each processor in the parallel computer. A coarse-grain parallelism is obtained, and a near-perfect load balance results. In uni-partitioning every processor receives responsibility for exactly one block of grid points instead of several. This necessitates fine-grain pipelined program execution in order to obtain a reasonable load balance. Although fine-grain parallelism is less desirable on many systems, especially high-latency networks of workstations, uni-partition methods are still in wide use in production codes for flow problems. Consequently, it remains important to achieve good efficiency with this technique that has essentially been superseded by multi-partitioning for parallel ADI-type algorithms. Another reason for the concentration on improving the performance of pipeline methods is their applicability in other types of flow solver kernels with stronger implied data dependence. Analytical expressions can be derived for the size of the dynamic load imbalance incurred in traditional pipelines. From these it can be determined what is the optimal first-processor retardation that leads to the shortest total completion time for the pipeline process. Theoretical predictions of pipeline performance with and without optimization match experimental observations on the iPSC/860 very well. Analysis of pipeline performance also highlights the effect of uncareful grid partitioning in flow solvers that employ pipeline algorithms. If grid blocks at boundaries are not at least as large in the wall-normal direction as those immediately adjacent to them, then the first processor in the pipeline will receive a computational load that is less than that of subsequent processors, magnifying the pipeline slowdown effect. Extra compensation is needed for grid boundary effects, even if all grid blocks are equally sized.

Vanderwijngaart, Rob F.↗
DOE OSTI2017

Exploring the interplay of resilience and energy consumption for a task-based partial differential equations preconditioner

Here, we discuss algorithm-based resilience to silent data corruptions (SDCs) in a task-based domain-decomposition preconditioner for partial differential equations (PDEs). The algorithm exploits a reformulation of the PDE as a sampling problem, followed by a solution update through data manipulation that is resilient to SDCs. The implementation is based on a server-client model where all state information is held by the servers, while clients are designed solely as computational units. Scalability tests run up to ~51K cores show a parallel efficiency greater than 90%. We use a 2D elliptic PDE and a fault model based on random single and double bit-flip to demonstrate the resilience of the application to synthetically injected SDC. We discuss two fault scenarios: one based on the corruption of all data of a target task, and the other involving the corruption of a single data point. We show that for our application, given the test problem considered, a four-fold increase in the number of faults only yields a 2% change in the overhead to overcome their presence, from 7% to 9%. We then discuss potential savings in energy consumption via dynamic voltage/frequency scaling, and its interplay with fault-rates, and application overhead.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2024

Lifting MGARD: Construction of (pre)wavelets on the interval using polynomial predictors of arbitrary order

MGARD (MultiGrid Adaptive Reduction of Data) is an algorithm for compressing and refactoring scientific data, based on the theory of multigrid methods. The core algorithm is built around stable multilevel decompositions of conforming piecewise linear $C^0$ finite element spaces, enabling accurate error control in various norms and derived quantities of interest. In this work, we extend this construction to arbitrary order Lagrange finite elements $\mathbb{Q}_p$, $p \geq 0$, and propose a reformulation of the algorithm as a lifting scheme with polynomial predictors of arbitrary order. Additionally, a new formulation using a compactly supported wavelet basis is discussed, and an explicit construction of the proposed wavelet transform for uniform dyadic grids is described.

Reshniak, Viktor [Oak Ridge National Laboratory (O↗
NASA NTRS1995

Newton-Krylov-Schwarz: An implicit solver for CFD

Newton-Krylov methods and Krylov-Schwarz (domain decomposition) methods have begun to become established in computational fluid dynamics (CFD) over the past decade. The former employ a Krylov method inside of Newton's method in a Jacobian-free manner, through directional differencing. The latter employ an overlapping Schwarz domain decomposition to derive a preconditioner for the Krylov accelerator that relies primarily on local information, for data-parallel concurrency. They may be composed as Newton-Krylov-Schwarz (NKS) methods, which seem particularly well suited for solving nonlinear elliptic systems in high-latency, distributed-memory environments. We give a brief description of this family of algorithms, with an emphasis on domain decomposition iterative aspects. We then describe numerical simulations with Newton-Krylov-Schwarz methods on aerodynamics applications emphasizing comparisons with a standard defect-correction approach, subdomain preconditioner consistency, subdomain preconditioner quality, and the effect of a coarse grid.

Cai, Xiao-Chuan↗
NASA NTRS2000

Parallel CE/SE Computations via Domain Decomposition

This paper describes the parallelization strategy and achieved parallel efficiency of an explicit time-marching algorithm for solving conservation laws. The Space-Time Conservation Element and Solution Element (CE/SE) algorithm for solving the 2D and 3D Euler equations is parallelized with the aid of domain decomposition. The parallel efficiency of the resultant algorithm on a Silicon Graphics Origin 2000 parallel computer is checked.

Himansu, Ananda↗
DOE OSTI2021

A Cyber-Physical Anomaly Detection for Wide-Area Protection Using Machine Learning

Wide-area protection scheme (WAPS) provides system-wide protection by detecting and mitigating small and large-scale disturbances that are difficult to resolve using local protection schemes. As this protection scheme is evolving from a substation-based distributed remedial action scheme (DRAS) to the control center-based centralized RAS (CRAS), it presents severe challenges to their cybersecurity because of its heavy reliance on an insecure grid communication, and its compromise would lead to system failure. This article presents an architecture and methodology for developing a cyber-physical anomaly detection system (CPADS) that utilizes synchrophasor measurements and properties of network packets to detect data integrity and communication failure attacks on measurement and control signals in CRAS. The proposed machine leaning-based methodology applies a rules-based approach to select relevant input features, utilizes variational mode decomposition (VMD) and decision tree (DT) algorithms to develop multiple classification models, and performs final event identification using a rules-based decision logic. Here, we have evaluated the proposed methodology of CPADS using the IEEE 39 bus system for several performance measures (accuracy, recall, precision, and F-measure) in a cyber-physical testbed environment. Furthermore, our experimental results reveal that the proposed algorithm (VMD-DT) of CPADS outperforms the existing machine learning classifiers during noisy and noise-free measurements while incurring an acceptable processing overhead.

24 POWER TRANSMISSION AND DISTRIBUTION↗
DOE OSTI2018

Wide ranging equation of state with Tartarus: A hybrid Green’s function/orbital based average atom code

Average atom models are widely used to make equation of state tables and for calculating other properties of materials over a wide range of conditions, from zero temperature isolated atom to fully ionized free electron gases. The numerical challenge of making these density functional theory based models work for any temperature, density or nuclear species is formidable. Here we present in detail a hybrid Green’s function/orbital based approach that has proved to be stable and accurate for wide ranging conditions. Algorithmic strategies are discussed. In particular the decomposition of the electron density into numerically advantageous parts is presented and a robust and rapid self consistent field method based on a quasi-Newton algorithm is given. Example application to the equation of state of lutetium (Z = 71) is explored in detail, including the effect of relativity, finite temperature exchange and correlation, and a comparison to a less approximate method. Furthermore, the hybrid scheme is found to be numerically stable and accurate for lutetium over at least 6 orders of magnitude in density and 5 orders of magnitude in temperature.

74 ATOMIC AND MOLECULAR PHYSICS↗
DOE OSTI2014

Combined iterative reconstruction and image-domain decomposition for dual energy CT using total-variation regularization

Purpose: Dual-energy CT (DECT) is being increasingly used for its capability of material decomposition and energy-selective imaging. A generic problem of DECT, however, is that the decomposition process is unstable in the sense that the relative magnitude of decomposed signals is reduced due to signal cancellation while the image noise is accumulating from the two CT images of independent scans. Direct image decomposition, therefore, leads to severe degradation of signal-to-noise ratio on the resultant images. Existing noise suppression techniques are typically implemented in DECT with the procedures of reconstruction and decomposition performed independently, which do not explore the statistical properties of decomposed images during the reconstruction for noise reduction. In this work, the authors propose an iterative approach that combines the reconstruction and the signal decomposition procedures to minimize the DECT image noise without noticeable loss of resolution. Methods: The proposed algorithm is formulated as an optimization problem, which balances the data fidelity and total variation of decomposed images in one framework, and the decomposition step is carried out iteratively together with reconstruction. The noise in the CT images from the proposed algorithm becomes well correlated even though the noise of the raw projections is independent on the two CT scans. Due to this feature, the proposed algorithm avoids noise accumulation during the decomposition process. The authors evaluate the method performance on noise suppression and spatial resolution using phantom studies and compare the algorithm with conventional denoising approaches as well as combined iterative reconstruction methods with different forms of regularization. Results: On the Catphan©600 phantom, the proposed method outperforms the existing denoising methods on preserving spatial resolution at the same level of noise suppression, i.e., a reduction of noise standard deviation by one order of magnitude. This improvement is mainly attributed to the high noise correlation in the CT images reconstructed by the proposed algorithm. Iterative reconstruction using different regularization, including quadratic orq-generalized Gaussian Markov random field regularization, achieves similar noise suppression from high noise correlation. However, the proposed TV regularization obtains a better edge preserving performance. Studies of electron density measurement also show that our method reduces the average estimation error from 9.5% to 7.1%. On the anthropomorphic head phantom, the proposed method suppresses the noise standard deviation of the decomposed images by a factor of ∼14 without blurring the fine structures in the sinus area. Conclusions: The authors propose a practical method for DECT imaging reconstruction, which combines the image reconstruction and material decomposition into one optimization framework. Compared to the existing approaches, our method achieves a superior performance on DECT imaging with respect to decomposition accuracy, noise reduction, and spatial resolution.

62 RADIOLOGY AND NUCLEAR MEDICINE↗
DOE OSTI2022

A Lagrangian dual method for two-stage robust optimization with binary uncertainties

This report presents a new exact method to calculate worst-case parameter realizations in two-stage robust optimization problems with categorical or binary-valued uncertain data. Traditional exact algorithms for these problems, notably Benders decomposition and column-and-constraint generation, compute worst-case parameter realizations by solving mixed-integer bilinear optimization subproblems. However, their numerical solution can be computationally expensive not only due to their resulting large size after reformulating the bilinear terms, but also because decision-independent bounds on their variables are typically unknown. We propose an alternative Lagrangian dual method that circumvents these difficulties and is readily integrated in either algorithm. We specialize the method to problems where the binary parameters switch on or off constraints as these are commonly encountered in applications, and discuss extensions to problems that lack relatively complete recourse and to those with integer recourse. Numerical experiments provide evidence of significant computational improvements over existing methods.

42 ENGINEERING↗
DOE OSTI2021

stacked predictive sparse decomposition (SPSD) v1.0

It is an unsupervised representation algorithm used to learn morphometric properties from cellular objects. Many similar/identical open source implementations are widely available in tensorflow, pytorch, etc. And ours is implemented in matlab.

Chang, Hang↗
DOE OSTI2023

Relativistic resolution-of-the-identity with Cholesky integral decomposition

In this study, we present an efficient integral decomposition approach called the restricted-kinetic-balance resolution-of-the-identity (RKB-RI) algorithm, which utilizes a tunable RI method based on the Cholesky integral decomposition for in-core relativistic quantum chemistry calculations. The RKB-RI algorithm incorporates the restricted-kinetic-balance condition and offers a versatile framework for accurate computations. Notably, the Cholesky integral decomposition is employed not only to approximate symmetric large-component electron repulsion integrals but also those involving small-component basis functions. In addition to comprehensive error analysis, we investigate crucial conditions, such as the kinetic balance condition and variational stability, which underlie the applicability of Dirac relativistic electronic structure theory. Here we compare the computational cost of the RKB-RI approach with the full in-core method to assess its efficiency. To evaluate the accuracy and reliability of the RKB-RI method proposed in this work, we employ actinyl oxides as benchmark systems, leveraging their properties for validation purposes. This investigation provides valuable insights into the capabilities and performance of the RKB-RI algorithm and establishes its potential as a powerful tool in the field of relativistic quantum chemistry.

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

A multiresolution wavelet representation in two or more dimensions

In the multiresolution approximation, a signal is examined on a hierarchy of resolution scales by projection onto sets of smoothing functions. Wavelets are used to carry the detail information connecting adjacent sets in the resolution hierarchy. An algorithm has been implemented to perform a multiresolution decomposition in n greater than or equal to 2 dimensions based on wavelets generated from products of 1-D wavelets and smoothing functions. The functions are chosen so that an n-D wavelet may be associated with a single resolution scale and orientation. The algorithm enables complete reconstruction of a high resolution signal from decomposition coefficients. The signal may be oversampled to accommodate non-orthogonal wavelet systems, or to provide approximate translational invariance in the decomposition arrays.

Bromley, B. C.↗
DOE OSTI2016

An Efficient Multicore Implementation of a Novel HSS-Structured Multifrontal Solver Using Randomized Sampling

Here, we present a sparse linear system solver that is based on a multifrontal variant of Gaussian elimination and exploits low-rank approximation of the resulting dense frontal matrices. We use hierarchically semiseparable (HSS) matrices, which have low-rank off-diagonal blocks, to approximate the frontal matrices. For HSS matrix construction, a randomized sampling algorithm is used together with interpolative decompositions. The combination of the randomized compression with a fast ULV HSS factoriz ation leads to a solver with lower computational complexity than the standard multifrontal method for many applications, resulting in speedups up to 7 fold for problems in our test suite. The implementation targets many-core systems by using task parallelism with dynamic runtime scheduling. Numerical experiments show performance improvements over state-of-the-art sparse direct solvers. The implementation achieves high performance and good scalability on a range of modern shared memory parallel systems, including the Intel Xeon Phi (MIC). The code is part of a software package called STRUMPACK - STRUctured Matrices PACKage, which also has a distributed memory component for dense rank-structured matrices.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2021

Scalable FBP decomposition for cone-beam CT reconstruction

Filtered Back-Projection (FBP) is a fundamental compute intense algorithm used in tomographic image reconstruction. Cone-Beam Computed Tomography (CBCT) devices use a cone-shaped X-ray beam, in comparison to the parallel beam used in older CT generations. Distributed image reconstruction of cone-beam datasets typically relies on dividing batches of images into different nodes. This simple input decomposition, however, introduces limits on input/output sizes and scalability.We propose a novel decomposition scheme and reconstruction algorithm for distributed FPB. This scheme enables arbitrarily large input/output sizes, eliminates the redundancy arising in the end-to-end pipeline and improves the scalability by replacing two communication collectives with only one segmented reduction. Finally, we implement the proposed decomposition scheme in a framework that is useful for all current-generation CT devices (7th gen). In our experiments using up to 1024 GPUs, our framework can construct 40963 volumes, for real-world datasets, in under 16 seconds (including I/O).

Chen, Peng↗
DOE OSTI2014

Properties OF M31. V. 298 eclipsing binaries from PAndromeda

The goal of this work is to conduct a photometric study of eclipsing binaries in M31. We apply a modified box-fitting algorithm to search for eclipsing binary candidates and determine their period. We classify these candidates into detached, semi-detached, and contact systems using the Fourier decomposition method. We cross-match the position of our detached candidates with the photometry from Local Group Survey and select 13 candidates brighter than 20.5 mag in V. The relative physical parameters of these detached candidates are further characterized with the Detached Eclipsing Binary Light curve fitter (DEBiL) by Devor. We will follow up the detached eclipsing binaries spectroscopically and determine the distance to M31.

79 ASTRONOMY AND ASTROPHYSICS↗
NASA NTRS1996

A New Coarsening Operator for the Optimal Preconditioning of the Dual and Primal Domain Decomposition Methods: Application to Problems with Severe Coefficient Jumps

We present an optimal preconditioning algorithm that is equally applicable to the dual (FETI) and primal (Balancing) Schur complement domain decomposition methods, and which successfully addresses the problems of subdomain heterogeneities including the effects of large jumps of coefficients. The proposed preconditioner is derived from energy principles and embeds a new coarsening operator that propagates the error globally and accelerates convergence. The resulting iterative solver is illustrated with the solution of highly heterogeneous elasticity problems.

Farhat, Charbel↗
DOE OSTI2020

Quantum Fourier transform revisited

Summary The fast Fourier transform (FFT) is one of the most successful numerical algorithms of the 20th century and has found numerous applications in many branches of computational science and engineering. The FFT algorithm can be derived from a particular matrix decomposition of the discrete Fourier transform (DFT) matrix. In this paper, we show that the quantum Fourier transform (QFT) can be derived by further decomposing the diagonal factors of the FFT matrix decomposition into products of matrices with Kronecker product structure. We analyze the implication of this Kronecker product structure on the discrete Fourier transform of rank‐1 tensors on a classical computer. We also explain why such a structure can take advantage of an important quantum computer feature that enables the QFT algorithm to attain an exponential speedup on a quantum computer over the FFT algorithm on a classical computer. Further, the connection between the matrix decomposition of the DFT matrix and a quantum circuit is made. We also discuss a natural extension of a radix‐2 QFT decomposition to a radix‐ d QFT decomposition. No prior knowledge of quantum computing is required to understand what is presented in this paper. Yet, we believe this paper may help readers to gain some rudimentary understanding of the nature of quantum computing from a matrix computation point of view.

Camps, Daan↗
NASA NTRS1998

A Domain-Decomposed Multi-Level Method for Adaptively Refined Cartesian Grids with Embedded Boundaries

The work presents a new method for on-the-fly domain decomposition technique for mapping grids and solution algorithms to parallel machines, and is applicable to both shared-memory and message-passing architectures. It will be demonstrated on the Cray T3E, HP Exemplar, and SGI Origin 2000. Computing time has been secured on all these platforms. The decomposition technique is an outgrowth of techniques used in computational physics for simulations of N-body problems and the event horizons of black holes, and has not been previously used by the CFD community. Since the technique offers on-the-fly partitioning, it offers a substantial increase in flexibility for computing in heterogeneous environments, where the number of available processors may not be known at the time of job submission. In addition, since it is dynamic it permits the job to be repartitioned without global communication in cases where additional processors become available after the simulation has begun, or in cases where dynamic mesh adaptation changes the mesh size during the course of a simulation. The platform for this partitioning strategy is a completely new Cartesian Euler solver tarcreted at parallel machines which may be used in conjunction with Ames' "Cart3D" arbitrary geometry simulation package.

Aftosmis, M. J.↗