Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “algorithmic efficiency”

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 91 records · Page 5

A Faster Parallel Algorithm and Efficient Multithreaded Implementations for Evaluating Betweenness Centrality on Massive Datasets

We present a new lock-free parallel algorithm for computing betweenness centralityof massive small-world networks. With minor changes to the data structures, ouralgorithm also achieves better spatial cache locality compared to previous approaches. Betweenness centrality is a key algorithm kernel in HPCS SSCA#2, a benchmark extensively used to evaluate the performance of emerging high-performance computing architectures for graph-theoretic computations. We design optimized implementations of betweenness centrality and the SSCA#2 benchmark for two hardware multithreaded systems: a Cray XMT system with the Threadstorm processor, and a single-socket Sun multicore server with the UltraSPARC T2 processor. For a small-world network of 134 million vertices and 1.073 billion edges, the 16-processor XMT system and the 8-core Sun Fire T5120 server achieve TEPS scores (an algorithmic performance count for the SSCA#2 benchmark) of 160 million and 90 million respectively, which corresponds to more than a 2X performance improvement over the previous parallel implementations. To better characterize the performance of these multithreaded systems, we correlate the SSCA#2 performance results with data from the memory-intensive STREAM and RandomAccess benchmarks. Finally, we demonstrate the applicability of our implementation to analyze massive real-world datasets by computing approximate betweenness centrality for a large-scale IMDb movie-actor network.

97 MATHEMATICS AND COMPUTING↗

A Faster Parallel Algorithm and Efficient Multithreaded Implementations for Evaluating Betweenness Centrality on Massive Datasets

We present a new lock-free parallel algorithm for computing betweenness centrality of massive small-world networks. With minor changes to the data structures, our algorithm also achieves better spatial cache locality compared to previous approaches. Betweenness centrality is a key algorithm kernel in the HPCS SSCA#2 Graph Analysis benchmark, which has been extensively used to evaluate the performance of emerging high-performance computing architectures for graph-theoretic computations. We design optimized implementations of betweenness centrality and the SSCA#2 benchmark for two hardware multithreaded systems: a Cray XMT system with the ThreadStorm processor, and a single-socket Sun multicore server with the UltraSparc T2 processor. For a small-world network of 134 million vertices and 1.073 billion edges, the 16-processor XMT system and the 8-core Sun Fire T5120 server achieve TEPS scores (an algorithmic performance count for the SSCA#2 benchmark) of 160 million and 90 million respectively, which corresponds to more than a 2X performance improvement over the previous parallel implementations. To better characterize the performance of these multithreaded systems, we correlate the SSCA#2 performance results with data from the memory-intensive STREAM and RandomAccess benchmarks. Finally, we demonstrate the applicability of our implementation to analyze massive real-world datasets by computing approximate betweenness centrality for a large-scale IMDb movie-actor network.

architecture comparison↗

Parallel FETI‐DP algorithm for efficient simulation of large‐scale EM problems

Summary An efficient parallelization of the dual‐primal finite‐element tearing and interconnecting (FETI‐DP) algorithm is presented for large‐scale electromagnetic simulations. As a nonoverlapping domain decomposition method, the FETI‐DP algorithm formulates a global interface problem, whose iterative solution is accelerated with a solution of a global corner problem. To achieve a good load balance for parallel computation, the original computational domain is decomposed into subdomains with similar sizes and shapes. The subdomains are then distributed to processors based on their close proximity to minimize inter‐processor communication. The parallel generalized minimal residual method, enhanced with the iterative classical Gram‐Schmidt orthogonalization scheme to reduce global communication, is adopted to solve the global interface problem with a fast convergence rate. The global corner‐related coarse problem is solved iteratively with a parallel communication‐avoiding biconjugate gradient stabilized method to minimize global communication, and its convergence is accelerated by a diagonal preconditioner constructed from the coarse system matrix. To alleviate neighboring communication overhead, the non‐blocking communication approach is employed in both generalized minimal residual and communication‐avoiding biconjugate gradient stabilized iterative solutions. Three numerical examples are presented to demonstrate the accuracy, scalability, and capability of the proposed parallel FETI‐DP algorithm for electromagnetic modeling of general objects and antenna arrays. Copyright © 2016 John Wiley & Sons, Ltd.

Zhang, Kedi↗

An Iterative Local Updating Ensemble Smoother for Estimation and Uncertainty Assessment of Hydrologic Model Parameters With Multimodal Distributions

Abstract Ensemble smoother (ES) has been widely used in inverse modeling of hydrologic systems. However, for problems where the distribution of model parameters is multimodal, using ES directly would be problematic. One popular solution is to use a clustering algorithm to identify each mode and update the clusters with ES separately. However, this strategy may not be very efficient when the dimension of parameter space is high or the number of modes is large. Alternatively, we propose in this paper a very simple and efficient algorithm, i.e., the iterative local updating ensemble smoother (ILUES), to explore multimodal distributions of model parameters in nonlinear hydrologic systems. The ILUES algorithm works by updating local ensembles of each sample with ES to explore possible multimodal distributions. To achieve satisfactory data matches in nonlinear problems, we adopt an iterative form of ES to assimilate the measurements multiple times. Numerical cases involving nonlinearity and multimodality are tested to illustrate the performance of the proposed method. It is shown that overall the ILUES algorithm can well quantify the parametric uncertainties of complex hydrologic models, no matter whether the multimodal distribution exists.

Zhang, Jiangjiang↗

Efficient Optimization of Large Wind Farms for Real-Time Control: Preprint

Wind turbines in a wind farm typically operate individually to maximize their own performance regardless of the impact of aerodynamic interactions on neighboring turbines. Properly coordinating turbines, by operating some turbines suboptimally, within a wind farm has the potential to improve overall wind farm performance. Computing the optimal control strategy under varying atmospheric conditions can be computationally intense for large wind farms. As wind power farms increase in size and related models become more complex, computationally efficient algorithms are needed to perform real-time optimization and control. This study proposes a distributed optimization framework and computationally efficient wake steering wind farm control strategy that uses the yaw angle of a turbine to alter the behavior of a turbine wake and minimize turbine interactions. This computational efficiency allows the strategy to be feasible for real-time control.

17 WIND ENERGY↗

GPU algorithms for Efficient Exascale Discretizations

In this paper we describe the research and development activities in the Center for Efficient Exascale Discretization within the US Exascale Computing Project, targeting state-of-the-art high-order finite-element algorithms for high-order applications on GPU-accelerated platforms. Furthermore, we discuss the GPU developments in several components of the CEED software stack, including the libCEED, MAGMA, MFEM, libParanumal, and Nek projects. We report performance and capability improvements in several CEED-enabled applications on both NVIDIA and AMD GPU systems.

97 MATHEMATICS AND COMPUTING↗

A matrix completion algorithm for efficient calculation of quantum and variational effects in chemical reactions

This work examines the viability of matrix completion methods as cost-effective alternatives to full nuclear Hessians for calculating quantum and variational effects in chemical reactions. The harmonic variety-based matrix completion (HVMC) algorithm, developed in a previous study (https://doi.org/10.1063/5.0018326), exploits the low-rank character of the polynomial expansion of potential energy to recover, using a small sample, vibrational frequencies (square roots of nuclear Hessian eigenvalues) constituting the reaction path. Furthermore, these frequencies are essential for calculating rate coefficients using variational transition state theory with multidimensional tunneling (VTST-MT). HVMC performance is examined for four SN2 reactions and five hydrogen transfer reactions, with each H-transfer reaction consisting of at least one vibrational mode strongly coupled to the reaction coordinate. HVMC is robust and captures zero-point energies, vibrational free energies, zero-curvature tunneling, and adiabatic ground state and free energy barriers as well as their positions on the reaction coordinate. For medium to large reactions involving H-transfer, with the exception of the most complex Ir catalysis system, less than 35% of total eigenvalue information is necessary for accurate recovery of key VTST-MT observables.

37 INORGANIC, ORGANIC, PHYSICAL, AND ANALYTICAL CH↗

Linear embedding of nonlinear dynamical systems and prospects for efficient quantum algorithms

The simulation of large nonlinear dynamical systems, including systems generated by discretization of hyperbolic partial differential equations, can be computationally demanding. Such systems are important in both fluid and kinetic computational plasma physics. This motivates exploring whether a future error-corrected quantum computer could perform these simulations more efficiently than any classical computer. In this work, we describe a method for mapping any finite nonlinear dynamical system to an infinite linear dynamical system (embedding) and detail three specific cases of this method that correspond to previously studied mappings. Then we explore an approach for approximating the resulting infinite linear system with finite linear systems (truncation). Using a number of qubits only logarithmic in the number of variables of the nonlinear system, a quantum computer could simulate truncated systems to approximate output quantities if the nonlinearity is sufficiently weak. Other aspects of the computational efficiency of the three detailed embedding strategies are also discussed.

97 MATHEMATICS AND COMPUTING↗

Configurational-Bias Monte Carlo Back-Mapping Algorithm for Efficient and Rapid Conversion of Coarse-Grained Water Structures into Atomistic Models

Coarse-grained molecular dynamics (MD) simulations represent a powerful approach to simulate longer time scale and larger length scale phenomena than those accessible to all-atom models. The gain in efficiency, however, comes at the cost of atomistic details. The reverse transformation, also known as back-mapping, of coarse grained beads into their atomistic constituents represents a major challenge. Most existing approaches are limited to specific molecules or specific force-fields and often rely on running a long time atomistic MD of the back-mapped configuration to arrive at an optimal solution. Such approaches are problematic when dealing with systems with high diffusion barriers. Here, we introduce a new extension of the configurational-bias-Monte-Carlo (CBMC) algorithm, which we term the crystalline-configurational-bias-Monte-Carlo (C-CBMC) algortihm, that allows rapid and efficient conversion of a coarse-grained model back into its atomistic representation. Although the method is generic, we use a coarse-grained water model as a representative example and demonstrate the back-mapping or reverse transformation for model systems ranging from the ice-liquid water interface to amorphous and crystalline ice configurations. A series of simulations using the TIP4P/Ice model are performed to compare the new CBMC method to several other standard Monte Carlo and Molecular Dynamics based back-mapping techniques. In all the cases, the C-CBMC algorithm is able to find optimal hydrogen bonded configuration many thousand evaluations/steps sooner than the other methods compared within this paper. For crystalline ice structures such as a hexagonal, cubic, and cubic-hexagonal stacking disorder structures, the C-CBMC was able to find structures that were between 0.05 and 0.1 eV/water molecule lower in energy than the ground state energies predicted by the other methods. Detailed analysis of the atomistic structures show a significantly better global hydrogen positioning when contrasted with the existing simpler back-mapping methods. The error in the RDFs of backmapped relative to reference configuration for the CCBMC, MD, and MC were found to be 6.9, 8.7, and 12.9 respectively for the hexagonal system. For the cubic system the relative error of the RDFs for the CCBMC, MD, and MC were found to be 18.2, 34.6, and 39.0 respectively. Finally, our results demonstrate the efficiency and efficacy of our new back-mapping approach, especially for crystalline systems where simple force-field based relaxations have a tendency to get trapped in local minima.

74 ATOMIC AND MOLECULAR PHYSICS↗

An efficient computational algorithm for pricing European, barrier and American options

In this work, we use the spectral collocation technique for spatial derivatives and predictor–corrector method for time integration to solve the Black–Scholes (B–S) equation. If the spectral collocation method is worked properly, then we get high accuracy in the numerical solutions. Firstly, theory of application of Chebyshev spectral collocation technique and domain decomposition method on the B–S equation is presented. This method gets a stiff system of differential equations. Secondly, by using the predictor–corrector method with variable step size, we obtain the high accuracy approximate solution in the numerical integration of the stiff system of DEs. We present the order of accuracy for the proposed method. The numerical results show the efficiency and validity of the method.

97 MATHEMATICS AND COMPUTING↗

Algorithms for Efficient Reproducible Floating Point Summation

We define “reproducibility” as getting bitwise identical results from multiple runs of the same program, perhaps with different hardware resources or other changes that should not affect the answer. Many users depend on reproducibility for debugging or correctness. However, dynamic scheduling of parallel computing resources, combined with nonassociative floating point addition, makes reproducibility challenging even for summation, or operations like the BLAS. We describe a “reproducible accumulator” data structure (the “binned number”) and associated algorithms to reproducibly sum binary floating point numbers, independent of summation order. We use a subset of the IEEE Floating Point Standard 754-2008 and bitwise operations on the standard representations in memory. Our approach requires only one read-only pass over the data, and one reduction in parallel, using a 6-word reproducible accumulator (more words can be used for higher accuracy), enabling standard tiling optimization techniques. Summing n words with a 6-word reproducible accumulator requires approximately 9 n floating point operations (arithmetic, comparison, and absolute value) and approximately 3 n bitwise operations. The final error bound with a 6-word reproducible accumulator and our default settings can be up to 2 29 times smaller than the error bound for conventional (recursive) summation on ill-conditioned double-precision inputs.

Computer Science↗

Retrieving Top-k Hyperedge Triplets: Models and Applications

Complex systems frequently exhibit multi-way, rather than pairwise, interactions. These group interactions can- not be faithfully modeled as collections of pairwise interactions using graphs and instead require hypergraphs. However, methods that analyze hypergraphs directly, rather than via lossy graph reductions, remain limited. Hypergraph motifs hold promise in this regard, as motif patterns serve as building blocks for larger group interactions which are inexpressible by graphs. Recent work has focused on categorizing and counting hypergraph motifs based on the existence of nodes in hyperedge intersection regions. Here, we argue that the relative sizes of hyperedge inter- sections within motifs contain varied and valuable information. We propose a suite of efficient algorithms for finding top-k triplets of hyperedges based on optimizing the sizes of these intersection patterns. This formulation uncovers interesting local patterns of interaction, finding hyperedge triplets that either (1) are the least similar with each other, (2) have the highest pairwise but not groupwise correlation, or (3) are the most similar with each other. We formalize this as a combinatorial optimization problem and design efficient algorithms based on filtering hyperedges. Our comprehensive experimental evaluation shows that the resulting hyperedge triplets yield insightful information on real-world hypergraphs. Our approach is also orders of magnitude faster than a naive baseline implementation.

hypergraphs, motifs, Combinatorial Algorithms↗

Fast Computational Algorithms for Partial Differential Equations and Uncertainty Quantifications

This project concerned the construction, testing and analysis of computational algorithms for solving parameterized and stochastic partial differential equations. The study and understanding of equations of this type is of fundamental importance in numerous engineering and scientific applications. Examples include simulation of plasma dynamics in models of electric propulsion and nuclear fusion, simulation of multiphase flows, such as the flow of water, gas and oil in reservoirs, and structural analysis of the dependence of structures on materials. Parametrization is used in such settings when properties of the models such as viscosity of fluids or electric resistivity of materials are not precisely understood and instead are treated as random variables. The resulting solutions are themselves random, and having such solutions will enable engineers to use probabilistic methods to assess the likelihood of events, for example, whether a pollutant in a liquid will exceed a limit, and to use such analyses to develop ways to ensure positive outcomes. Construction of accurate (high resolution) computational solutions is expensive, requiring significant computer time and computational resources, and there is need to reduce computational cost to make simulation useful and effective. The aim of the project was to construct algorithms to efficiently compute surrogate solutions to parameterized problems to allow for efficient and accurate simulation. The technical approach used focused on two related strategies, based on rank-reduction methods and reduced-order models. These methods construct surrogate solutions of parameter-dependent models by projection or interpolation into low-dimensional approximation spaces. Cost savings are achieved if the low-dimensional spaces can be identified and constructed efficiently and if the resulting low-dimensional algebraic systems can be solved cheaply. Accomplishments include: Theoretical and empirical demonstration of the effectiveness of fast multigrid solution strategies for computing low-rank representations of parameter-dependent solutions to discrete partial differential equations, including the first proof establishing so-called textbook convergence properties for low-rank methods. Development of efficient solution algorithms for solving nonlinear parameter-dependent partial differential equations used in models of fluid dynamics. Developent of efficient algorithms for low-rank representation of solutions of time-dependent simulations of fluid dynamics using multi-dimensional tensor representations of solutions.

97 MATHEMATICS AND COMPUTING↗

The nanostructure problem

Diffraction techniques are making progress in tackling the difficult problem of solving the structures of nanoparticles and nanoscale materials. The great gift of x-ray crystallography has made us almost complacent in our ability to locate the three-dimensional coordinates of atoms in a crystal with a precision of around 10{sup -4} nm. However, the powerful methods of crystallography break down for structures in which order only extends over a few nanometers. In fact, as we near the one hundred year mark since the birth of crystallography, we face a resilient frontier in condensed matter physics: our inability to routinely and robustly determine the structure of complex nanostructured and amorphous materials. Knowing the structure and arrangement of atoms in a solid is so fundamental to understanding its properties that the topic routinely occupies the early chapters of every solid-state physics textbook. Yet what has become clear with the emergence of nanotechnology is that diffraction data alone may not be enough to uniquely solve the structure of nanomaterials. As part of a growing effort to incorporate the results of other techniques to constrain x-ray refinements - a method called 'complex modeling' which is a simple but elegant approach for combining information from spectroscopy with diffraction data to solve the structure of several amorphous and nanostructured materials. Crystallography just works, so we rarely question how and why this is so, yet understanding the physics of diffraction can be very helpful as we consider the nanostructure problem. The relationship between the electron density distribution in three dimensions (i.e., the crystal structure) and an x-ray diffraction pattern is well established: the measured intensity distribution in reciprocal space is the square of the Fourier transform of the autocorrelation function <{rho}(r){rho}(r+r')> of the electron density distribution {rho}(r). The fact that we get the autocorrelation function (rather than just the density distribution) by Fourier transforming the measured intensity leaves us with a very tricky inverse problem: we have to extract the density from its autocorrelation function. The direct problem of predicting the diffraction intensity given a particular density distribution is trivial, but the inverse, unraveling from the intensity distribution the density that gives rise to it, is a highly nontrivial problem in global optimization. In crystallography, this challenging, nontrivial task is sometimes referred to as the 'phase problem.' The diffraction pattern is a wave-interference pattern, but we measure only the intensities (the squares of the waves) not the wave amplitudes. To get the amplitude, you take the square root of the intensity I, but in so doing you lose any knowledge of the phase of the wave {phi}, and half the information needed to reconstruct the density is lost. When solving such inverse problems, you hope you can start with a uniqueness theorem that reassures you that, under ideal conditions, there is only one solution: one density distribution that corresponds to the measured intensity. Then you have to establish that your data set contains sufficient information to constrain that unique solution. This is a problem from information theory that originated with Reverend Thomas Bayes work in the 18th century, and the work of Nyquist and Shannon in the 20 th century, and describes the fact that the degrees of freedom in the model must not exceed the number of pieces of independent information in the data. Finally, you need an efficient algorithm for doing the reconstruction. This is exactly how crystallography works. The information is in the form of Bragg peak intensities and the degrees of freedom are the atomic coordinates. Crystal symmetry lets us confine the model to the contents of a unit cell, rather than all of the atoms in the crystal, keeping the degrees of freedom admirably small in number. A measurement yields a multitude of Bragg peak intensities, providing ample redundant intensity information to make up for the lost phases. Finally, there are highly efficient algorithms, such as 'direct methods,' that make excellent use of the available information and constraints to find the solution quickly from a horrendously large search space. The problem is often so overconstrained that we can cavalierly throw away lots of directional information. In particular, even though Bragg peaks are orientationally averaged to a 1D function in a powder diffraction measurement, we still can get a 3D structural solution. Now it becomes easy to understand the enormous challenge of solving nanostructures: the information content in the data is degraded while the complexity of the model is much greater.

75 CONDENSED MATTER PHYSICS, SUPERCONDUCTIVITY AND↗

ROM-based Subset Selection Algorithm for Efficient Surrogate Modeling

This summary discusses a new methodology to support the construction of surrogate models for computationally expensive models with many input parameters and output responses. In realistic engineering calculations, such as thermal-hydraulics simulation, the cost of the simulation is typically expensive, especially when detailed models are employed to describe system behavior, thereby justifying the need for surrogate models. The cost of surrogate model construction is typically a function of the number of model parameters and the degree of model nonlinearity. For sufficiently complex models, the cost of constructing the surrogate model could be by itself overwhelmingly expensive, thereby diminishing its value. One key requirement of surrogate model construction is the ability to preselect the best parametric form to describe the model behavior over the expected range of parameter variations. This summary presents a new algorithm to help select the best approximation out of a template of functions using recent advances in reduced order modeling (ROM) techniques. The idea of selecting functions out of a template is typically referred to as subset selection in the statistical and applied mathematics community. Different from existing subset selection algorithms, we rely on ROM to help identify the most influential functions for the surrogate model. Previous work has shown that ROM can help reduce the effective dimensionality of the parameter space, which can help reduce the cost of surrogate model construction. In this summary, we adopt a different philosophy, where the fitting functions are treated as pseudo parameters and ROM is applied on the pseudo parameter space, with the result now being a ranked list of the pseudo parameters along with their contribution to the quality of the surrogate model fit. This approach allows the analyst to discard all terms that have negligible impact on the quantity of interest. A relap5 model is employed to demonstrate the application of the proposed methodology. (authors)

42 ENGINEERING↗

Plasma Science and Innovation Center at Washington, Wisconsin, and Utah State: Final Scientific Report for the University of Wisconsin-Madison

The University of Wisconsin-Madison component of the Plasma Science and Innovation Center (PSI Center) contributed to modeling capabilities and algorithmic efficiency of the Non-Ideal Magnetohydrodynamics with Rotation (NIMROD) Code, which is widely used to model macroscopic dynamics of magnetically confined plasma. It also contributed to the understanding of direct-current (DC) injection of electrical current for initiating and sustaining plasma in three spherical torus experiments: the Helicity Injected Torus-II (HIT-II), the Pegasus Toroidal Experiment, and the National Spherical Torus Experiment (NSTX). The effort was funded through the PSI Center's cooperative agreement with the University of Washington and Utah State University over the period of March 1, 2005 - August 31, 2016. In addition to the computational and physics accomplishments, the Wisconsin effort contributed to the professional education of four graduate students and two postdoctoral research associates. The modeling for HIT-II and Pegasus was directly supported by the cooperative agreement, and contributions to the NSTX modeling were in support of work by Dr. Bickford Hooper, who was funded through a separate grant. Our primary contribution to model development is the implementation of detailed closure relations for collisional plasma. Postdoctoral associate Adam Bayliss implemented the temperature-dependent effects of Braginskii's parallel collisional ion viscosity. As a graduate student, John O'Bryan added runtime options for Braginskii's models and Ji's K2 models of thermal conduction with magnetization effects and thermal equilibration. As a postdoctoral associate, O'Bryan added the magnetization effects for ion viscosity. Another area of model development completed through the PSI-Center is the implementation of Chodura's phenomenological resistivity model. Finally, we investigated and tested linear electron parallel viscosity, leveraged by support from the Center for Extended Magnetohydrodynamic Modeling (CEMM). Work on algorithmic efficiency improved NIMROD's element-based computations. We reordered arrays and eliminated a level of looping for computations over the data points that are used for numerical integration over elements. Moreover, the reordering allows fewer and larger communication calls when using distributed-memory parallel computation, thereby avoiding a data starvation problem that limited parallel scaling over NIMROD's Fourier components for the periodic coordinate. Together with improved parallel preconditioning, work that was supported by CEMM, these developments allowed NIMROD's first scaling to over 10,000 processor cores. Another algorithm improvement supported by the PSI Center is nonlinear numerical diffusivities for implicit advection. We also developed the Stitch code to enhance the flexibility of NIMROD's preprocessing. Our simulations of HIT-II considered conditions with and without fluctuation-induced amplification of poloidal flux, but our validation efforts focused on conditions without amplification. A significant finding is that NIMROD reproduces the dependence of net plasma current as the imposed poloidal flux is varied. The modeling of Pegasus startup from localized DC injectors predicted that development of a tokamak-like configuration occurs through a sequence of current-filament merger events. Comparison of experimentally measured and numerically computed cross-power spectra enhance confidence in NIMROD's simulation of magnetic fluctuations; however, energy confinement remains an open area for further research. Our contributions to the NSTX study include adaptation of the helicity-injection boundary conditions from the HIT-II simulations and support for linear analysis and computation of 3D current-driven instabilities.

70 PLASMA PHYSICS AND FUSION TECHNOLOGY↗