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 829 records · Page 46

Simulation of laser-plasma interactions and fast-electron transport in inhomogeneous plasma

A new framework is introduced for kinetic simulation of laser-plasma interactions in an inhomogeneous plasma motivated by the goal of performing integrated kinetic simulations of fast-ignition laser fusion. The algorithm addresses the propagation and absorption of an intense electromagnetic wave in an ionized plasma leading to the generation and transport of an energetic electron component. The energetic electrons propagate farther into the plasma to much higher densities where Coulomb collisions become important. The high-density plasma supports an energetic electron current, return currents, self-consistent electric fields associated with maintaining quasi-neutrality, and self-consistent magnetic fields due to the currents. Collisions of the electrons and ions are calculated accurately to track the energetic electrons and model their interactions with the background plasma. Up to a density well above critical density, where the laser electromagnetic field is evanescent, Maxwell's equations are solved with a conventional particle-based, finite-difference scheme. In the higher-density plasma, Maxwell's equations are solved using an Ohm's law neglecting the inertia of the background electrons with the option of omitting the displacement current in Ampere's law. Particle equations of motion with binary collisions are solved for all electrons and ions throughout the system using weighted particles to resolve the density gradient efficiently. The algorithm is analyzed and demonstrated in simulation examples. The simulation scheme introduced here achieves significantly improved efficiencies.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

Hybrid Simulation of Laser-Plasma Interactions and Fast Electron Transport in Inhomogeneous Plasma

A new framework is introduced for kinetic simulation of laser-plasma interactions in an inhomogenous plasma motivated by the goal of performing integrated kinetic simulations of fast-ignition laser fusion. The algorithm addresses the propagation and absorption of an intense electromagnetic wave in an ionized plasma leading to the generation and transport of an energetic electron component. The energetic electrons propagate farther into the plasma to much higher densities where Coulomb collisions become important. The high-density plasma supports an energetic electron current, return currents, self-consistent electric fields associated with maintaining quasi-neutrality, and self-consistent magnetic fields due to the currents. Collisions of the electrons and ions are calculated accurately to track the energetic electrons and model their interactions with the background plasma. Up to a density well above critical density, where the laser electromagnetic field is evanescent, Maxwell's equations are solved with a conventional particle-based, finite-difference scheme. In the higher-density plasma, Maxwell's equations are solved using an Ohm's law neglecting the inertia of the background electrons with the option of omitting the displacement current in Ampere's law. Particle equations of motion with binary collisions are solved for all electrons and ions throughout the system using weighted particles to resolve the density gradient efficiently. The algorithm is analyzed and demonstrated in simulation examples. The simulation scheme introduced here achieves significantly improved efficiencies.

70 PLASMA PHYSICS AND FUSION TECHNOLOGY↗

Robust and efficient overset grid assembly for partitioned unstructured meshes

This paper presents a method to perform efficient and automated Overset Grid Assembly (OGA) on a system of overlapping unstructured meshes in a parallel computing environment where all meshes are partitioned into multiple mesh-blocks and processed on multiple cores. The main task of the overset grid assembler is to identify, in parallel, among all points in the overlapping mesh system, at which points the flow solution should be computed (field points), interpolated (receptor points), or ignored (hole points). Point containment search or donor search, an algorithm to efficiently determine the cell that contains a given point, is the core procedure necessary for accomplishing this task. Donor search is particularly challenging for partitioned unstructured meshes because of the complex irregular boundaries that are often created during partitioning. Another challenge arises because of the large variation in the type of mesh-block overlap and the resulting large load imbalance on multiple processors. Desirable traits for the grid assembly method are efficiency (requiring only a small fraction of the solver time), robustness (correct identification of all point types), and full automation (no user input required other than the mesh system). Additionally, the method should be scalable, which is an important challenge due to the inherent load imbalance. This paper describes a fully-automated grid assembly method, which can use two different donor search algorithms. One is based on the use of auxiliary grids and Exact Inverse Maps (EIM), and the other is based on the use of Alternating Digital Trees (ADT). The EIM method is demonstrated to be more efficient than the ADT method, while retaining robustness. An adaptive load re-balance algorithm is also designed and implemented, which considerably improves the scalability of the method.

97 MATHEMATICS AND COMPUTING↗

HPC-NMF: A High-Performance Parallel Algorithm for Nonnegative Matrix Factorization

NMF is a useful tool for many applications in different domains such as topic modeling in text mining, background separation in video analysis, and community detection in social networks. Despite its popularity in the data mining community, there is a lack of efficient distributed algorithms to solve the problem for big data sets. We propose a high-performance distributed-memory parallel algorithm that computes the factorization by iteratively solving alternating non-negative least squares (NLS) subproblems for $\WW$ and $\HH$. It maintains the data and factor matrices in memory (distributed across processors), uses MPI for interprocessor communication, and, in the dense case, provably minimizes communication costs (under mild assumptions). As opposed to previous implementation, our algorithm is also flexible: It performs well for both dense and sparse matrices, and allows the user to choose any one of the multiple algorithms for solving the updates to low rank factors $\WW$ and $\HH$ within the alternating iterations.

Kannan, Ramakrishnan↗

A primal–dual algorithm for risk minimization

In this paper, we develop an algorithm to efficiently solve risk-averse optimization problems posed in reflexive Banach space. Such problems often arise in many practical applications as, e.g., optimization problems constrained by partial differential equations with uncertain inputs. Unfortunately, for many popular risk models including the coherent risk measures, the resulting risk-averse objective function is nonsmooth. Here, this lack of differentiability complicates the numerical approximation of the objective function as well as the numerical solution of the optimization problem. To address these challenges, we propose a primal–dual algorithm for solving large-scale nonsmooth risk-averse optimization problems. This algorithm is motivated by the classical method of multipliers and by epigraphical regularization of risk measures. As a result, the algorithm solves a sequence of smooth optimization problems using derivative-based methods. We prove convergence of the algorithm even when the subproblems are solved inexactly and conclude with numerical examples demonstrating the efficiency of our method.

97 MATHEMATICS AND COMPUTING↗

MCCCS-MN

The MCCCS‒MN (Monte Carlo for Complex Chemical Systems‒Minnesota) software is developed by the Siepmann research group at the University of Minnesota. MCCCS‒MN allows for the simulation of multi-component molecular systems in the canonical, isobaric-isothermal (including constant stress for solids), grand-canonical, semi-grand, and Gibbs (NVT, NPT, and more than two simulation boxes) ensembles. It uses the configurational-bias Monte Carlo method to efficiently sample phase space for linear, branched and cyclic chain molecules, the adiabatic nuclear and electronic sampling Monte Carlo method to treat many-body polarization effects, and the aggregation-volume-bias Monte Carlo algorithm to efficiently sample the spatial distribution of associating molecules. MCCCS-MN employs a molecular representation of the system where force fields contain bonded and non-bonded terms. Funding for the development of MCCCS-MN through grants from the National Science Foundation (simulation of fluid phase equilibria and chromatography) and the Department of Energy (simulation of adsorption equilibria) is gratefully acknowledged.

Siepmann, J.Ilja [University of Minnesota - Twin C↗

Generating Massive Scale-free Networks: Novel Parallel Algorithms using the Preferential Attachment Model

Recently, there has been substantial interest in the study of various random networks as mathematical models of complex systems. As real-life complex systems grow larger, the ability to generate progressively large random networks becomes all the more important. This motivates the need for efficient parallel algorithms for generating such networks. Naïve parallelization of sequential algorithms for generating random networks is inefficient due to inherent dependencies among the edges and the possibility of creating duplicate (parallel) edges. In this article, we present message passing interface-based distributed memory parallel algorithms for generating random scale-free networks using the preferential-attachment model. Our algorithms are experimentally verified to scale very well to a large number of processing elements (PEs), providing near-linear speedups. The algorithms have been exercised with regard to scale and speed to generate scale-free networks with one trillion edges in 6 minutes using 1,000 PEs.

97 MATHEMATICS AND COMPUTING↗

Online eco-routing for electric vehicles using combinatorial multi-armed bandit with estimated covariance

Identifying energy-efficient routes in real-time has significant implications for the energy-optimal operations of electric vehicles (EVs). Here, this study proposes a novel model for EV online eco-routing problem, which obtains the minimal expected energy consumption paths (MECPs) for multiple origin-destination (OD) pairs simultaneously. Specifically, we formulate the routing problem as a bandit problem and solve it with online algorithms. We extend the algorithms by implementing a path elimination mechanism to reduce the candidate path set and introducing the variance and covariance of the energy consumption to reduce the uncertainties. The numerical results show that the proposed algorithms can efficiently obtain near-optimal MECPs, and the solution is significantly better than the widely used shortest trip time path algorithm (STTP) and shortest trip distance path algorithm (SDP). The variation considering link energy covariance and path elimination generates paths that save 4.1% of energy compared to the SDP and 5.4% to the STTP.

33 ADVANCED PROPULSION SYSTEMS↗

Genetic algorithm optimization of nuclear criticality experiment for reduction of intermediate-energy 239 Pu nuclear data uncertainties

Nuclear criticality experiments are conducted to investigate specific nuclear data important for safe handling and storage of fissile materials, reactor design and operation, and the validation of radiation transport codes. Incorrect or uncertain nuclear data can prohibitively impact operational safety limits, reactor licensing, and predictive simulation capability; therefore, integral measurements from criticality experiments are necessary and should be performed frequently. To maximize the impact of the integral measurements, it is important to consider experiment geometry, material selection, and component dimensions. When taking these considerations into account, the experiment design process becomes iterative and very time intensive. This work utilizes a genetic algorithm to efficiently explore potential nuclear criticality experiment designs for the Laboratory Directed Research & Development project PARADIGM (PARallel Approach of Differential and InteGral Measurements) at Los Alamos National Laboratory. In this paper, the building blocks of the genetic algorithm are discussed in detail, the genetic algorithm methodology is verified, and the genetic algorithm is used to produce three candidate experiment models for the final PARADIGM design. The three candidate models produced by the genetic algorithm consist of copper-reflected assemblies containing 14 repeating units of alumina, graphite, boron, and plutonium plates. Furthermore, in addition to the optimization results, final design considerations are also discussed for designs with a height and/or weight very close to or slightly above assembly machine operational limits.

22 GENERAL STUDIES OF NUCLEAR REACTORS↗

Searching the landscape of flux vacua with genetic algorithms

In this paper, we employ genetic algorithms to explore the landscape of type IIB flux vacua. We show that genetic algorithms can efficiently scan the landscape for viable solutions satisfying various criteria. More specifically, we consider a symmetric T 6 as well as the conifold region of a Calabi-Yau hypersurface. We argue that in both cases genetic algorithms are powerful tools for finding flux vacua with interesting phenomenological properties. We also compare genetic algorithms to algorithms based on different breeding mechanisms as well as random walk approaches.

79 ASTRONOMY AND ASTROPHYSICS↗

Study of aircraft centered navigation, guidance, and traffic situation system concept for terminal area operation

A concept for automating the control of air traffic in the terminal area in which the primary man-machine interface is the cockpit is described. The ground and airborne inputs required for implementing this concept are discussed. Digital data link requirements of 10,000 bits per second are explained. A particular implementation of this concept including a sequencing and separation algorithm which generates flight paths and implements a natural order landing sequence is presented. Onboard computer/display avionics utilizing a traffic situation display is described. A preliminary simulation of this concept has been developed which includes a simple, efficient sequencing algorithm and a complete aircraft dynamics model. This simulated jet transport was flown through automated terminal-area traffic situations by pilots using relatively sophisticated displays, and pilot performance and observations are discussed.

Anderson, W. W.↗

Inverse transport calculations in optical imaging with subspace optimization algorithms

Inverse boundary value problems for the radiative transport equation play an important role in optics-based medical imaging techniques such as diffuse optical tomography (DOT) and fluorescence optical tomography (FOT). Despite the rapid progress in the mathematical theory and numerical computation of these inverse problems in recent years, developing robust and efficient reconstruction algorithms remains a challenging task and an active research topic. We propose here a robust reconstruction method that is based on subspace minimization techniques. The method splits the unknown transport solution (or a functional of it) into low-frequency and high-frequency components, and uses singular value decomposition to analytically recover part of low-frequency information. Minimization is then applied to recover part of the high-frequency components of the unknowns. We present some numerical simulations with synthetic data to demonstrate the performance of the proposed algorithm.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

On the efficiency of the Orthogonal Matching Pursuit in compressed sensing

The paper shows that if a matrix {Phi} has the restricted isometry property (RIP) of order [CK{sup 1.2}] with isometry constant {delta}=cK{sup -0.2} and if its coherence is less than 1/(20K{sup 0.8}), then the Orthogonal Matching Pursuit (the Orthogonal Greedy Algorithm) is capable to exactly recover an arbitrary K-sparse signal from the compressed sensing y={Phi}x in at most [CK{sup 1.2}] iterations. As a result, an arbitrary K-sparse signal can be recovered by the Orthogonal Matching Pursuit from M=O(K{sup 1.6} log N) measurements. Bibliography: 23 titles.

97 MATHEMATICS AND COMPUTING↗

Time-domain analysis of planar microstrip devices using a generalized Yee-algorithm based on unstructured grids

The generalized Yee-algorithm is presented for the temporal full-wave analysis of planar microstrip devices. This algorithm has the significant advantage over the traditional Yee-algorithm in that it is based on unstructured and irregular grids. The robustness of the generalized Yee-algorithm is that structures that contain curved conductors or complex three-dimensional geometries can be more accurately, and much more conveniently modeled using standard automatic grid generation techniques. This generalized Yee-algorithm is based on the the time-marching solution of the discrete form of Maxwell's equations in their integral form. To this end, the electric and magnetic fields are discretized over a dual, irregular, and unstructured grid. The primary grid is assumed to be composed of general fitted polyhedra distributed throughout the volume. The secondary grid (or dual grid) is built up of the closed polyhedra whose edges connect the centroid's of adjacent primary cells, penetrating shared faces. Faraday's law and Ampere's law are used to update the fields normal to the primary and secondary grid faces, respectively. Subsequently, a correction scheme is introduced to project the normal fields onto the grid edges. It is shown that this scheme is stable, maintains second-order accuracy, and preserves the divergenceless nature of the flux densities. Finally, for computational efficiency the algorithm is structured as a series of sparse matrix-vector multiplications. Based on this scheme, the generalized Yee-algorithm has been implemented on vector and parallel high performance computers in a highly efficient manner.

Gedney, Stephen D.↗

Characterization of CLYC Detectors for a Next-Generation Unattended Sensor

We are developing a next-generation unattended sensor for detecting anomalous radiation sources. The system uses a scintillator material with dual sensitivity to gamma rays and neutrons, Cs 2 LiYCl 6 :Ce (CLYC), to reduce the size and complexity of the design. CLYC also offers a best-case energy resolution under 4% full width at half maximum at 662 keV, and allows for particle discrimination by pulse amplitude as well as pulse shape. The unattended sensor features sixteen one-inch CLYC detectors, each read out by a photomultiplier tube and custom readout electronics. A field-programmable gate array implements a suite of efficient processing algorithms for anomaly detection and isotope identification, and transmits alarm information to a base station via a wireless link. The system is designed to operate on battery power for several weeks. In this paper, we report the energy resolution, linearity, detection efficiency, and temperature stability of the first CLYC detectors acquired for the project. Rather than characterizing the scintillator material under ideal conditions, we evaluate the detectors with the components selected for the unattended sensor, acknowledging the tradeoffs imposed by small size, limited power budget, and uncontrolled environmental conditions.

46 INSTRUMENTATION RELATED TO NUCLEAR SCIENCE AND ↗

Reconstructing householder vectors from Tall-Skinny QR

The Tall-Skinny QR (TSQR) algorithm is more communication efficient than the standard Householder algorithm for QR decomposition of matrices with many more rows than columns. However, TSQR produces a different representation of the orthogonal factor and therefore requires more software development to support the new representation. Further, implicitly applying the orthogonal factor to the trailing matrix in the context of factoring a square matrix is more complicated and costly than with the Householder representation. We show how to perform TSQR and then reconstruct the Householder vector representation with the same asymptotic communication efficiency and little extra computational cost. We demonstrate the high performance and numerical stability of this algorithm both theoretically and empirically. The new Householder reconstruction algorithm allows us to design more efficient parallel QR algorithms, with significantly lower latency cost compared to Householder QR and lower bandwidth and latency costs compared with Communication-Avoiding QR (CAQR) algorithm. Experiments on supercomputers demonstrate the benefits of the communication cost improvements: in particular, our experiments show substantial improvements over tuned library implementations for tall-and-skinny matrices. Furthermore, we also provide algorithmic improvements to the Householder QR and CAQR algorithms, and we investigate several alternatives to the Householder reconstruction algorithm that sacrifice guarantees on numerical stability in some cases in order to obtain higher performance.

97 MATHEMATICS AND COMPUTING↗

HPC formulations of optimization algorithms for tensor completion

Tensor completion is a powerful tool used to estimate or recover missing values in multi-way data. It has seen great success in domains such as product recommendation and healthcare. Tensor completion is most often accomplished via low-rank sparse tensor factorization, a computationally expensive non-convex optimization problem which has only recently been studied in the context of parallel computing. In this work, we study three optimization algorithms that have been successfully applied to tensor completion: alternating least squares (ALS), stochastic gradient descent (SGD), and coordinate descent (CCD++). We explore opportunities for parallelism on shared- and distributed-memory systems and address challenges such as memory- and operation-efficiency, load balance, cache locality, and communication. Among our advancements are a communication-efficient CCD++ algorithm, an ALS algorithm rich in level-3 BLAS routines, and an SGD algorithm which combines stratification with asynchronous communication. Furthermore, we show that introducing randomization during ALS and CCD++ can accelerate convergence. We evaluate our parallel formulations on a variety of real datasets on a modern supercomputer and demonstrate speedups through 16384 cores. Further, these improvements reduce time-to-solution from hours to seconds on real-world datasets. We show that after our optimizations, ALS is advantageous on parallel systems of small-to-moderate scale, while both ALS and CCD++ provide the lowest time-to-solution on large-scale distributed systems.

97 MATHEMATICS AND COMPUTING↗

Quantum snake walk on graphs

I introduce a continuous-time quantum walk on graphs called the quantum snake walk, the basis states of which are fixed-length paths (snakes) in the underlying graph. First, I analyze the quantum snake walk on the line, and I show that, even though most states stay localized throughout the evolution, there are specific states that most likely move on the line as wave packets with momentum inversely proportional to the length of the snake. Next, I discuss how an algorithm based on the quantum snake walk might potentially be able to solve an extended version of the glued trees problem, which asks to find a path connecting both roots of the glued trees graph. To the best of my knowledge, no efficient quantum algorithm solving this problem is known yet.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗