Search NASA⌕ Search

SEARCH · Search NASA

Results for “Decomposition algorithm”

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

Beam correction for multi-pass arcs in FFA@CEBAF: status update

This work examines the multi-pass steering of six electron beams in an FFA arc ranging from approximately 10.5 GeV to 22 GeV. Shown here is an algorithm based on singular value decomposition (SVD) to successfully steer all six beams through the arc given precise knowledge of all beam positions at each of one hundred and one diagnostic locations with one hundred individual corrector magnets: that is successive application of SVD to different 100 × 101 response matrices—one for each beam energy. Further, a machine learning scheme is developed which only requires knowledge of the energy-averaged beam position at each location to provide equivalent steering. Extension of this scheme to other beam optics quantities as well as transverse and longitudinal coupling is explored.

Accelerator Physics↗

Reduction of matrix wavefront for NASTRAN

The three grid point resequencing algorithms most often run by NASTRAN users are compared for their ability to reduce matrix root-mean-square (rms) wavefront, which is the most critical parameter in determining matrix decomposition time in NASTRAN. The three algorithms are Cuthill-McKee (CM), Gibbs-Poole-Stockmeyer (GPS), and Levy. The first two (CM and GPS) are in the BANDIT program, and the Levy algorithm is in WAVEFRONT. Results are presented for a diversified collection of 30 test problems ranging in size from 59 to 2680 nodes. It is concluded that GPS is exceptionally fast and, for the conditions under which the test was made, the algorithm best able to reduce rms wavefront consistently well.

Everstine, G. C.↗

Asynchronous interactive control systems

A class of interactive control systems is derived by generalizing interactive manipulator control systems. The general structural properties of such systems are discussed and an appropriate general software implementation is proposed. This is based on the fact that tasks of interactive control systems can be represented as a network of a finite set of actions which have specific operational characteristics and specific resource requirements, and which are of limited duration. This has enabled the decomposition of the overall control algorithm into a set of subalgorithms, called subcontrollers, which can operate simultaneously and asynchronously. Coordinate transformations of sensor feedback data and actuator set-points have enabled the further simplification of the subcontrollers and have reduced their conflicting resource requirements. The modules of the decomposed control system are implemented as parallel processes with disjoint memory space communicating only by I/O. The synchronization mechanisms for dynamic resource allocation among subcontrollers and other synchronization mechanisms are also discussed in this paper. Such a software organization is suitable for the general form of multiprocessing using computer networks with distributed storage.

Vuskovic, M. I.↗

A study of interactive control scheduling and economic assessment for robotic systems

A class of interactive control systems is derived by generalizing interactive manipulator control systems. Tasks of interactive control systems can be represented as a network of a finite set of actions which have specific operational characteristics and specific resource requirements, and which are of limited duration. This has enabled the decomposition of the overall control algorithm simultaneously and asynchronously. The performance benefits of sensor referenced and computer-aided control of manipulators in a complex environment is evaluated. The first phase of the CURV arm control system software development and the basic features of the control algorithms and their software implementation are presented. An optimal solution for a production scheduling problem that will be easy to implement in practical situations is investigated.

Source record↗

3D Electromagnetic Plasma Particle Simulations on the Intel Delta Parallel Computer

A three-dimensional electromagnetic PIC code has been developed on the 512 node Intel Touchstone Delta MIMD parallel computer. This code is based on the General Concurrent PIC algorithm which uses a domain decomposition to divide the computation among the processors. The 3D simulation domain can be partitioned into 1-, 2-, or 3-dimensional subdomains. Particles must be exchanged between processors as they move among the subdomains.

PIC↗

Active Thermography Based on Tensor Rank Decomposition

Principal Component Thermography applies Singular Value Decomposition (SVD) to post-process data that are derived from active thermographic inspections. SVD provides useful compression of the data and allows for better understanding of substructure and indications of potential damage. In the standard approach, SVD is applied to a certain reshaping of a three-dimensional data stack into a two-dimensional array. This work applies the CANDECOMP-PARAFAC (CP) tensor rank decomposition directly to the three-dimensional data to avoid the initial reshaping step in order to begin to develop an inspection method that can more accurately detect defects in non-homogeneous and anisotropic materials. Tests against simulated data that compare the CP decomposition method with traditional Principal Component Thermography based on SVD are described. Finally, the method of Proper Generalized Decomposition (PGD) is used to derive the CP decomposition, and its performance against other algorithms is also discussed.

Thermography↗

True Load Balancing for Matricized Tensor Times Khatri-Rao Product

MTTKRP is the bottleneck operation in algorithms used to compute the CP tensor decomposition. For sparse tensors, utilizing the compressed sparse fibers (CSF) storage format and the CSF-oriented MTTKRP algorithms is important for both memory and computational efficiency on distributed-memory architectures. Existing intelligent tensor partitioning models assume the computational cost of MTTKRP to be proportional to the total number of nonzeros in the tensor. However, this is not the case for the CSF-oriented MTTKRP on distributed-memory architectures. We outline two deficiencies of nonzero-based intelligent partitioning models when CSF-oriented MTTKRP operations are performed locally: failure to encode processors' computational loads and increase in total computation due to fiber fragmentation. We focus on existing fine-grain hypergraph model and propose a novel vertex weighting scheme that enables this model encode correct computational loads of processors. We also propose to augment the fine-grain model by fiber nets for reducing the increase in total computational load via minimizing fiber fragmentation. In this way, the proposed model encodes minimizing the load of the bottleneck processor. In conclusion, parallel experiments with real-world sparse tensors on up to 1024 processors prove the validity of the outlined deficiencies and demonstrate the merit of our proposed improvements in terms of parallel runtimes.

97 MATHEMATICS AND COMPUTING↗

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

Event-Based Parareal: A data-flow based implementation of parareal

Parareal is an iterative algorithm that, in effect, achieves temporal decomposition for a time-dependent system of differential or partial differential equations. A solution is obtained in a shorter wall-clock time, but at the expense of increased compute cycles. The algorithm combines a fine solver that solves the system to acceptable accuracy with an approximate coarse solver. The critical task for the successful implementation of parareal on any system is the development of a coarse solver that leads to convergence in a small number of iterations compared to the number of time slices in the full time interval, and is, at the same time, much faster than the fine solver. Fast coarse solvers may not lead to sufficiently rapid convergence, and slow coarse solvers may not lead to significant gains even if the number of iterations to convergence is satisfactory. We find that the difficulty of meeting these conflicting demands can be substantially eased by using a data-driven, event-based implementation of parareal instead of the conventional algorithm where solver tasks are executed sequentially. For given convergence properties, the event-based approach relaxes the speed requirements on the coarse solver by a factor of , where is the number of iterations required for a converged solution. This may, for many problems, lead to an efficient parareal implementation that would otherwise not be possible or would require substantial coarse solver development.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

Exploring the Interplay of Resilience and Energy Consumption for a Task-Based Partial Differential Equations Preconditioner

We discuss algorithm-based resilience to silent data corruption (SDC) 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 SDC. 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 ~ 51 K cores show a parallel efficiency greater than 90%. We use a 2D elliptic PDE and a fault model based on random single 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 dynamics voltage/frequency scaling, and its interplay with fault-rates, and application overhead.

97 MATHEMATICS AND COMPUTING↗

Fixed-point error analysis of Winograd Fourier transform algorithms

The quantization error introduced by the Winograd Fourier transform algorithm (WFTA) when implemented in fixed-point arithmetic is studied and compared with that of the fast Fourier transform (FFT). The effect of ordering the computational modules and the relative contributions of data quantization error and coefficient quantization error are determined. In addition, the quantization error introduced by the Good-Winograd (GW) algorithm, which uses Good's prime-factor decomposition for the discrete Fourier transform (DFT) together with Winograd's short length DFT algorithms, is studied. Error introduced by the WFTA is, in all cases, worse than that of the FFT. In general, the WFTA requires one or two more bits for data representation to give an error similar to that of the FFT. Error introduced by the GW algorithm is approximately the same as that of the FFT.

Patterson, R. W.↗

MatRIS: Addressing the Challenges for Portability and Heterogeneity Using Tasking for Matrix Decomposition (Cholesky)

The ubiquitous in-node heterogeneity of HPC and cloud computing platforms makes software portability and performance optimization extremely challenging. Described here, the MatRIS multilevel math library abstraction framework employs tasking to alleviate these difficulties. MatRIS includes the IRIS task-based runtime on the bottom level and exposes different layers of abstraction to render algorithms architecturally agnostic. MatRIS ensures the decomposition and creation of tasks that represent the necessary encapsulation of the optimized kernels from both vendor and open-source math libraries. Once built, MatRIS can select different combinations of accelerators at runtime, making it portable even on diverse heterogeneous architectures. By leveraging the IRIS runtime’s features for managing heterogeneity, MatRIS deploys algorithms that remove the need to specify orchestration and data transfer. This study describes how the serial task abstraction of a tiled Cholesky factorization is made portable and scalable in the case of multi-device and multi-vendor heterogeneity on a node with NVIDIA and AMD GPUs by using MatRIS. First, we demonstrate that Cholesky in MatRIS provides multi-GPU scalability that offers competitive performance versus cuSolverMG. Then, we present the challenges and opportunities for heterogeneous execution.

Monil, M. A. H.↗

Domain decomposition: A bridge between nature and parallel computers

Domain decomposition is an intuitive organizing principle for a partial differential equation (PDE) computation, both physically and architecturally. However, its significance extends beyond the readily apparent issues of geometry and discretization, on one hand, and of modular software and distributed hardware, on the other. Engineering and computer science aspects are bridged by an old but recently enriched mathematical theory that offers the subject not only unity, but also tools for analysis and generalization. Domain decomposition induces function-space and operator decompositions with valuable properties. Function-space bases and operator splittings that are not derived from domain decompositions generally lack one or more of these properties. The evolution of domain decomposition methods for elliptically dominated problems has linked two major algorithmic developments of the last 15 years: multilevel and Krylov methods. Domain decomposition methods may be considered descendants of both classes with an inheritance from each: they are nearly optimal and at the same time efficiently parallelizable. Many computationally driven application areas are ripe for these developments. A progression is made from a mathematically informal motivation for domain decomposition methods to a specific focus on fluid dynamics applications. To be introductory rather than comprehensive, simple examples are provided while convergence proofs and algorithmic details are left to the original references; however, an attempt is made to convey their most salient features, especially where this leads to algorithmic insight.

Keyes, David E.↗

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

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↗

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↗

Multiscale registration of planning CT and daily cone beam CT images for adaptive radiation therapy

Adaptive radiation therapy (ART) is the incorporation of daily images in the radiotherapy treatment process so that the treatment plan can be evaluated and modified to maximize the amount of radiation dose to the tumor while minimizing the amount of radiation delivered to healthy tissue. Registration of planning images with daily images is thus an important component of ART. In this article, the authors report their research on multiscale registration of planning computed tomography (CT) images with daily cone beam CT (CBCT) images. The multiscale algorithm is based on the hierarchical multiscale image decomposition of E. Tadmor, S. Nezzar, and L. Vese [Multiscale Model. Simul. 2(4), pp. 554-579 (2004)]. Registration is achieved by decomposing the images to be registered into a series of scales using the (BV, L{sup 2}) decomposition and initially registering the coarsest scales of the image using a landmark-based registration algorithm. The resulting transformation is then used as a starting point to deformably register the next coarse scales with one another. This procedure is iterated at each stage using the transformation computed by the previous scale registration as the starting point for the current registration. The authors present the results of studies of rectum, head-neck, and prostate CT-CBCT registration, and validate their registration method quantitatively using synthetic results in which the exact transformations our known, and qualitatively using clinical deformations in which the exact results are not known.

62 RADIOLOGY AND NUCLEAR MEDICINE↗

A generalized implicit algorithm for multi-dimensional particle-in-cell simulations in Cartesian geometry

An implicit multi-dimensional particle-in-cell (PIC) code is developed to study the interaction of ultrashort pulse lasers with matter. The algorithm is based on current density decomposition and is only marginally more complicated compared to explicit PIC codes, but it completely eliminates grid heating and possesses good energy conserving properties with relaxed time step and grid resolution. This is demonstrated in a test case study, in which high-energy protons are generated from a thin carbon foil at solid density using linear and circular polarizations. The grid heating rate is estimated to be 1-10 eV/ps.

36 MATERIALS SCIENCE↗