Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “sampling 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 163 records · Page 9

Trigger Detection for Adaptive Scientific Workflows Using Percentile Sampling

The increasing complexity of both scientific simulations and high-performance computing system architectures are driving the need for adaptive workflows, in which the composition and execution of computational and data manipulation steps dynamically depend on the evolutionary state of the simulation itself. Consider, for example, the frequency of data storage. Critical phases of the simulation should be captured with high frequency and with high fidelity for postanalysis; however, we cannot afford to retain the same frequency for the full simulation due to the high cost of data movement. We can instead look for triggers, indicators that the simulation will be entering a critical phase, and adapt the workflow accordingly. In this paper, we present a methodology for detecting triggers and demonstrate its use in the context of direct numerical simulations of turbulent combustion using S3D. We show that chemical explosive mode analysis (CEMA) can be used to devise a noise-tolerant indicator for rapid increase in heat release. However, exhaustive computation of CEMA values dominates the total simulation, and thus is prohibitively expensive. To overcome this computational bottleneck, we propose a quantile sampling approach. Our sampling-based algorithm comes with provable error/confidence bounds, as a function of the number of samples. Most importantly, the number of samples is independent of the problem size, and thus our proposed sampling algorithm offers perfect scalability. Our experiments on homogeneous charge compression ignition and reactivity controlled compression ignition simulations show that the proposed method can detect rapid increases in heat release, and its computational overhead is negligible. Our results will be used to make dynamic workflow decisions regarding data storage and mesh resolution in future combustion simulations.

97 MATHEMATICS AND COMPUTING↗

Note: A pure-sampling quantum Monte Carlo algorithm with independent Metropolis

Recently, Ospadov and Rothstein published a pure-sampling quantum Monte Carlo algorithm (PSQMC) that features an auxiliary Path Z that connects the midpoints of the current and proposed Paths X and Y, respectively. When sufficiently long, Path Z provides statistical independence of Paths X and Y. Under those conditions, the Metropolis decision used in PSQMC is done without any approximation, i.e., not requiring microscopic reversibility and without having to introduce any G(x → x′; τ) factors into its decision function. This is a unique feature that contrasts with all competing reptation algorithms in the literature. An example illustrates that dependence of Paths X and Y has adverse consequences for pure sampling.

37 INORGANIC, ORGANIC, PHYSICAL, AND ANALYTICAL CH↗

Sampling-Based Motion Planning Algorithms for Replanning and Spatial Load Balancing

The common theme of this dissertation is sampling-based motion planning with the two key contributions being in the area of replanning and spatial load balancing for robotic systems. Here, we begin by recalling two sampling-based motion planners: the asymptotically optimal rapidly-exploring random tree (RRT*), and the asymptotically optimal probabilistic roadmap (PRM*). We also provide a brief background on collision cones and the Distributed Reactive Collision Avoidance (DRCA) algorithm. The next four chapters detail novel contributions for motion replanning in environments with unexpected static obstacles, for multi-agent collision avoidance, and spatial load balancing. First, we show improved performance of the RRT* when using the proposed Grandparent-Connection (GP) or Focused-Refinement (FR) algorithms. Next, the Goal Tree algorithm for replanning with unexpected static obstacles is detailed and proven to be asymptotically optimal. A multi-agent collision avoidance problem in obstacle environments is approached via the RRT*, leading to the novel Sampling-Based Collision Avoidance (SBCA) algorithm. The SBCA algorithm is proven to guarantee collision free trajectories for all of the agents, even when subject to uncertainties in the knowledge of the other agents’ positions and velocities. Given that a solution exists, we prove that livelocks and deadlock will lead to the cost to the goal being decreased. We introduce a new deconfliction maneuver that decreases the cost-to-come at each step. This new maneuver removes the possibility of livelocks and allows a result to be formed that proves convergence to the goal configurations. Finally, we present a limited range Graph-based Spatial Load Balancing (GSLB) algorithm which fairly divides a non-convex space among multiple agents that are subject to differential constraints and have a limited travel distance. The GSLB is proven to converge to a solution when maximizing the area covered by the agents. The analysis for each of the above mentioned algorithms is confirmed in simulations.

97 MATHEMATICS AND COMPUTING↗

Motion Planning Algorithms for Safety and Quantum Computing Efficiency

Motion planning remains a fundamental problem in robotics. Sampling-based algorithms use randomization to allow efficient solutions to this complex problem. As mobile robots and autonomous vehicles become more prevalent in everyday life, motion planning must be applied to increasingly challenging scenarios. Safety has become a paramount concern in motion planning for ensuring robotic applications enrich human lives. To date, many motion planning techniques to increase safety in the face of uncertain and dynamic environments have been developed. This dissertation first addresses distributional safety of Rapidly-Exploring Random Trees (RRT) through our algorithm W-Safe RRT. To acknowledge distributional uncertainty and poor modeling, W-Safe RRT uses the Wasserstein metric to provide a probabilistic bound on the distributional distance between a robot and obstacles. Human-interpretable environmental agent classification allows online safety margin adaptation. We propose and analyze an integrating region method for online classification that increases actor labeling accuracy based on behavioral feature values when compared to state of the art methods. The method performs class assignments based on local maximum likelihood in a created behavioral feature-space, allowing a notion of classification uncertainty. Model-based methods with safety guarantees can quickly become computationally in tractable, especially with multiple agents, higher dimensions, and plentiful unknowns. Sampling based algorithms have been parallelized for computation with multi-core computers and GPUs. We consider the use of quantum algorithms and computers for sampling-based motion planning for the first time. Quantum computing performs operations on superpositions of states and can solve certain problems much more efficiently than classical computers, but introduces previously unseen challenges. With Quantum-RRT, we recast the motion planning problem into a database-search structure and use Quantum Amplitude Amplification to find reachable states in the database with a quadratic performance increase over classical methods. We address two error sources with this method: quantum measurement and quantum oracle errors. We then extend this method to Parallel Quantum-RRT, which uses a manager-worker architecture with multiple parallel quantum workers to increase database search efficiency. We compare algorithm architectures and characterize probabilities of multiple workers finding solutions. Lastly, we test in simulation the quantum algorithms against classical versions in a wide variety of scenarios, concluding that a similar parallelization improvement is to be found in the quantum case as was found in the parallelization of classical RRT.

97 MATHEMATICS AND COMPUTING↗

Annealed Importance Sampling Reversible Jump MCMC algorithms

It will soon be 20 years since reversible jump Markov chain Monte Carlo (RJ-MCMC) algorithms have been proposed. They have significantly extended the scope of Markov chain Monte Carlo simulation methods, offering the promise to be able to routinely tackle transdimensional sampling problems, as encountered in Bayesian model selection problems for example, in a principled and flexible fashion. Their practical efficient implementation, however, still remains a challenge. A particular difficulty encountered in practice is in the choice of the dimension matching variables (both their nature and their distribution) and the reversible transformations which allow one to define the one-to-one mappings underpinning the design of these algorithms. Indeed, even seemingly sensible choices can lead to algorithms with very poor performance. The focus of this paper is the development and performance evaluation of a method, annealed importance sampling RJ-MCMC (aisRJ), which addresses this problem by mitigating the sensitivity of RJ-MCMC algorithms to the aforementioned poor design. As we shall see the algorithm can be understood as being an “exact approximation” of an idealized MCMC algorithm that would sample from the model probabilities directly in a model selection set-up. Such an idealized algorithm may have good theoretical convergence properties, but typically cannot be implemented, and our algorithms can approximate the performance of such idealized algorithms to an arbitrary degree while not introducing any bias for any degree of approximation. Our approach combines the dimension matching ideas of RJ-MCMC with annealed importance sampling and its Markov chain Monte Carlo implementation. We illustrate the performance of the algorithm with numerical simulations which indicate that, although the approach may at first appear computationally involved, it is in fact competitive.

annealed importance sampling↗

Using full configuration interaction quantum Monte Carlo in a seniority zero space to investigate the correlation energy equivalence of pair coupled cluster doubles and doubly occupied configuration interaction

Over the past few years, pair coupled cluster doubles (pCCD) has shown promise for the description of strong correlation. This promise is related to its apparent ability to match results from doubly occupied configuration interaction (DOCI), even though the latter method has exponential computational cost. Here, by modifying the full configuration interaction quantum Monte Carlo algorithm to sample only the seniority zero sector of Hilbert space, we show that the DOCI and pCCD energies are in agreement for a variety of 2D Hubbard models, including for systems well out of reach for conventional configuration interaction algorithms. Our calculations are aided by the sign problem being much reduced in the seniority zero space compared with the full space. We present evidence for this and then discuss the sign problem in terms of the wave function of the system which appears to have a simplified sign structure.

37 INORGANIC, ORGANIC, PHYSICAL, AND ANALYTICAL CH↗

nautilus : boosting Bayesian importance nested sampling with deep learning

ABSTRACT We introduce a novel approach to boost the efficiency of the importance nested sampling (INS) technique for Bayesian posterior and evidence estimation using deep learning. Unlike rejection-based sampling methods such as vanilla nested sampling (NS) or Markov chain Monte Carlo (MCMC) algorithms, importance sampling techniques can use all likelihood evaluations for posterior and evidence estimation. However, for efficient importance sampling, one needs proposal distributions that closely mimic the posterior distributions. We show how to combine INS with deep learning via neural network regression to accomplish this task. We also introduce nautilus, a reference open-source python implementation of this technique for Bayesian posterior and evidence estimation. We compare nautilus against popular NS and MCMC packages, including emcee, dynesty, ultranest, and pocomc, on a variety of challenging synthetic problems and real-world applications in exoplanet detection, galaxy SED fitting and cosmology. In all applications, the sampling efficiency of nautilus is substantially higher than that of all other samplers, often by more than an order of magnitude. Simultaneously, nautilus delivers highly accurate results and needs fewer likelihood evaluations than all other samplers tested. We also show that nautilus has good scaling with the dimensionality of the likelihood and is easily parallelizable to many CPUs.

97 MATHEMATICS AND COMPUTING↗

Matrix diagonalization algorithm and its applicability to the nuclear shell model

An importance-sampling iterative algorithm for diagonalizing shell model Hamiltonian matrices is reviewed and implemented in a spin uncoupled basis. Shell model spaces of dimensions up to N < or approx.10{sup 9} are considered. The analysis shows that about 10% of the basis states are enough to bring the eigenvalues to convergence. This fraction of states, however, is insufficient to lead to convergence of the transition strengths, thereby limiting the applicability of the method to not too large spaces. In its domain of validity, the method yields a large number of eigensolutions and can be usefully adopted for rather complete studies of low-energy spectroscopy. This is done here for {sup 132,134}Xe isotopes. The calculation yields spectra and electromagnetic responses in fairly good agreement with the available experimental data and unveils the properties of the low-energy states of these isotopes, including their proton-neutron symmetry.

73 NUCLEAR PHYSICS AND RADIATION PHYSICS↗

Efficient Sampling of Complex Interdependent and Multiplex Networks

Efficient sampling of interdependent and multiplex infrastructure networks is critical for effectively applying failure and recovery algorithms in real-world settings, as well as to generate property-preserving reduced-order graph-based ensembles that address topological uncertainties. In this paper, we first explore the performance, i.e. the success in preserving graph properties, of graph sampling algorithms for interdependent and multiplex networks with synthetic and real-world graphs. We simulate sampling algorithms under different parameter settings. These settings include probabilistic graph generators, coupling patterns, and various performance metrics. Our results show that while Random Node and Random Walk sampling algorithms perform best for interdependent networks, Random Edge and Forest Fire sampling algorithms perform best for multiplex networks. Second, we propose and implement a novel similarity-based sampling algorithm for multiplex networks that samples only log(N) number of layers of an N-layer multiplex network while yielding computational savings with performance guarantees. Experimental results show that similarity sampling outperforms complete sampling of all layers while decreasing performance costs from a linear scale to a logarithmic one. Our results also indicate that similarity-based sampling outperforms complete sampling and random selection in nearly all scenarios when tested with real-world data.

Subasi, Omer↗

Dark Energy Survey Year 3 results: galaxy clustering and systematics treatment for lens galaxy samples

ABSTRACT In this work, we present the galaxy clustering measurements of the two DES lens galaxy samples: a magnitude-limited sample optimized for the measurement of cosmological parameters, maglim, and a sample of luminous red galaxies selected with the redmagic algorithm. maglim/redmagic sample contains over 10 million/2.5 million galaxies and is divided into six/five photometric redshift bins spanning the range z ∈ [0.20, 1.05]/z ∈ [0.15, 0.90]. Both samples cover 4143 $\deg ^2$ over which we perform our analysis blind, measuring the angular correlation function with an S/N ∼ 63 for both samples. In a companion paper, these measurements of galaxy clustering are combined with the correlation functions of cosmic shear and galaxy–galaxy lensing of each sample to place cosmological constraints with a 3 × 2pt analysis. We conduct a thorough study of the mitigation of systematic effects caused by the spatially varying survey properties and we correct the measurements to remove artificial clustering signals. We employ several decontamination methods with different configurations to ensure the robustness of our corrections and to determine the systematic uncertainty that needs to be considered for the final cosmology analyses. We validate our fiducial methodology using lognormal mocks, showing that our decontamination procedure induces biases no greater than 0.5σ in the (Ωm, b) plane, where b is the galaxy bias.

79 ASTRONOMY AND ASTROPHYSICS↗

Application-Specific Graph Sampling for Frequent Subgraph Mining and Community Detection

Graph mining is an important data analysis methodology, but struggles as the input graph size increases. The scalability and usability challenges posed by such large graphs make it imperative to sample the input graph and reduce its size. The critical challenge in sampling is to identify the appropriate algorithm to insure the resulting analysis does not suffer heavily from the data reduction. Predicting the expected performance degradation for a given graph and sampling algorithm is also useful. In this paper, we present different sampling approaches for graph mining applications such as Frequent Subgrpah Mining (FSM), and Community Detection (CD). We explore graph metrics such as PageRank, Triangles, and Diversity to sample a graph and conclude that for heterogeneous graphs Triangles and Diversity perform better than degree based metrics. We also present two new sampling variations for targeted graph mining applications. We present empirical results to show that knowledge of the target application, along with input graph properties can be used to select the best sampling algorithm. We also conclude that performance degradation is an abrupt, rather than gradual phenomena, as the sample size decreases. We present the empirical results to show that the performance degradation follows a logistic function.

Purohit, Sumit↗

Immunophenotype Discovery, Hierarchical Organization, and Template-Based Classification of Flow Cytometry Samples

We describe algorithms for discovering immunophenotypes from large collections of flow cytometry samples and using them to organize the samples into a hierarchy based on phenotypic similarity. The hierarchical organization is helpful for effective and robust cytometry data mining, including the creation of collections of cell populations’ characteristic of different classes of samples, robust classification, and anomaly detection. We summarize a set of samples belonging to a biological class or category with a statistically derived template for the class. Whereas individual samples are represented in terms of their cell populations (clusters), a template consists of generic meta-populations (a group of homogeneous cell populations obtained from the samples in a class) that describe key phenotypes shared among all those samples. We organize an FC data collection in a hierarchical data structure that supports the identification of immunophenotypes relevant to clinical diagnosis. A robust template-based classification scheme is also developed, but our primary focus is in the discovery of phenotypic signatures and inter-sample relationships in an FC data collection. This collective analysis approach is more efficient and robust since templates describe phenotypic signatures common to cell populations in several samples while ignoring noise and small sample-specific variations. We have applied the template-based scheme to analyze several datasets, including one representing a healthy immune system and one of acute myeloid leukemia (AML) samples. The last task is challenging due to the phenotypic heterogeneity of the several subtypes of AML. However, we identified thirteen immunophenotypes corresponding to subtypes of AML and were able to distinguish acute promyelocytic leukemia (APL) samples with the markers provided. Clinically, this is helpful since APL has a different treatment regimen from other subtypes of AML. Core algorithms used in our data analysis are available in the flowMatch package at www.bioconductor.org. It has been downloaded nearly 6,000 times since 2014.

59 BASIC BIOLOGICAL SCIENCES↗

Computing the partition function, ensemble averages, and density of states for lattice spin systems by sampling the mean

An algorithm to approximately calculate the partition function (and subsequently ensemble averages) and density of states of lattice spin systems through non-Monte-Carlo random sampling is developed. This algorithm (called the sampling-the-mean algorithm) can be applied to models where the up or down spins at lattice nodes interact to change the spin states of other lattice nodes, especially non-Ising-like models with long-range interactions such as the biological model considered here. Because it is based on the Central Limit Theorem of probability, the sampling-the-mean algorithm also gives estimates of the error in the partition function, ensemble averages, and density of states. Easily implemented parallelization strategies and error minimizing sampling strategies are discussed. The sampling-the-mean method works especially well for relatively small systems, systems with a density of energy states that contains sharp spikes or oscillations, or systems with little a priori knowledge of the density of states.

97 MATHEMATICS AND COMPUTING↗

Pattern-matching indexing of Laue and monochromatic serial crystallography data for applications in materials science

Serial crystallography data can be challenging to index, as each frame is processed individually, rather than being processed as a whole like in conventional X-ray single-crystal crystallography. An algorithm has been developed to index still diffraction patterns arising from small-unit-cell samples. The algorithm is based on the matching of reciprocal-lattice vector pairs, as developed for Laue microdiffraction data indexing, combined with three-dimensional pattern matching using a nearest-neighbors approach. As a result, large-bandpass data (e.g. 5–24 keV energy range) and monochromatic data can be processed, the main requirement being prior knowledge of the unit cell. Furthermore, angles calculated in the vicinity of a few theoretical and experimental reciprocal-lattice vectors are compared, and only vectors with the highest number of common angles are selected as candidates to obtain the orientation matrix. Global matching on the entire pattern is then checked. Four indexing options are available, two for the ranking of the theoretical reciprocal-lattice vectors and two for reducing the number of possible candidates. Furthermore, the algorithm has been used to index several data sets collected under different experimental conditions on a series of model samples. Additionally, knowing the crystallographic structure of the sample and using this information to rank the theoretical reflections based on the structure factors helps the indexing of large-bandpass data for the largest-unit-cell samples. For small-bandpass data, shortening the candidate list to determine the orientation matrix should be based on matching pairs of reciprocal-lattice vectors instead of triplet matching.

36 MATERIALS SCIENCE↗

IMEX-a :

This report presents an efficient and accurate method for integrating a system of ordinary differential equations, particularly those arising from a spatial discretization of partially differential equations. The algorithm developed, termed the IMEX a algorithm, belongs to a class of algorithms known as implicit-explicit (IMEX) methods. The explicit step is based on a fifth order Runge-Kutta explicit step known as the Dormand-Prince algorithm, which adaptively modifies the time step by calculating the error relative to a fourth order estimation. The implicit step, which follows the explicit step, is based on a backward Euler method, a special case of the generalized trapezoidal method. Reasons for choosing both of these methods, along with the algorithm development are presented. In applications that have less stringent accuracy requirements, several other methods are available through the IMEX a toolbox, each of which simplify the fifth order Dormand-Prince explicit step: the third order Bogacki-Shampine method, the second order Midpoint method, and the first order Euler method. The performance of the algorithm is evaluated on to examples. First, a two pawl system with contact is modeled. Results predicted by the IMEX a algorithm are compared to those predicted by six widely used integration schemes. The IMEX a algorithm is demonstrated to be significantly faster (by up to an order of magnitude) and at least as accurate as all of the other methods considered. A second example, an acoustic standing wave, is presented in order to assess the accuracy of the IMEX a algorithm. Finally, sample code is given in order to demonstrate the implementation of the proposed algorithm.

Brake, Matthew Robert↗

Fast generation of sparse random kernel graphs

The development of kernel-based inhomogeneous random graphs has provided models that are flexible enough to capture many observed characteristics of real networks, and that are also mathematically tractable. We specify a class of inhomogeneous random graph models, called random kernel graphs, that produces sparse graphs with tunable graph properties, and we develop an efficient generation algorithm to sample random instances from this model. As real-world networks are usually large, it is essential that the run-time of generation algorithms scales better than quadratically in the number of vertices n. We show that for many practical kernels our algorithm runs in time at most ο(n(logn)²). As an example, we show how to generate samples of power-law degree distribution graphs with tunable assortativity.

97 MATHEMATICS AND COMPUTING↗