Search NASA⌕ Search

SEARCH · Search NASA

Results for “Random walk”

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

Node-degree aware edge sampling mitigates inflated classification performance in biomedical random walk-based graph representation learning

Motivation: Graph representation learning is a family of related approaches that learn low-dimensional vector representations of nodes and other graph elements called embeddings. Embeddings approximate characteristics of the graph and can be used for a variety of machine-learning tasks such as novel edge prediction. For many biomedical applications, partial knowledge exists about positive edges that represent relationships between pairs of entities, but little to no knowledge is available about negative edges that represent the explicit lack of a relationship between two nodes. For this reason, classification procedures are forced to assume that the vast majority of unlabeled edges are negative. Existing approaches to sampling negative edges for training and evaluating classifiers do so by uniformly sampling pairs of nodes. Results: We show here that this sampling strategy typically leads to sets of positive and negative examples with imbalanced node degree distributions. Using representative heterogeneous biomedical knowledge graph and random walk-based graph machine learning, we show that this strategy substantially impacts classification performance. If users of graph machine-learning models apply the models to prioritize examples that are drawn from approximately the same distribution as the positive examples are, then performance of models as estimated in the validation phase may be artificially inflated. We present a degree-aware node sampling approach that mitigates this effect and is simple to implement. Availability and implementation: Our code and data are publicly available at https://github.com/monarch-initiative/negativeExampleSelection.

59 BASIC BIOLOGICAL SCIENCES↗

A spectral analysis of the domain decomposed Monte Carlo method for linear systems

The domain decomposed behavior of the adjoint Neumann-Ulam Monte Carlo method for solving linear systems is analyzed using the spectral properties of the linear oper- ator. Relationships for the average length of the adjoint random walks, a measure of convergence speed and serial performance, are made with respect to the eigenvalues of the linear operator. In addition, relationships for the effective optical thickness of a domain in the decomposition are presented based on the spectral analysis and diffusion theory. Using the effective optical thickness, the Wigner rational approxi- mation and the mean chord approximation are applied to estimate the leakage frac- tion of random walks from a domain in the decomposition as a measure of parallel performance and potential communication costs. The one-speed, two-dimensional neutron diffusion equation is used as a model problem in numerical experiments to test the models for symmetric operators with spectral qualities similar to light water reactor problems. We find, in general, the derived approximations show good agreement with random walk lengths and leakage fractions computed by the numerical experiments.

97 MATHEMATICS AND COMPUTING↗

WE-AB-209-06: Dynamic Collimator Trajectory Algorithm for Use in VMAT Treatment Deliveries

Purpose: To develop advanced dynamic collimator positioning algorithms for optimal beam’s-eye-view (BEV) fitting of targets in VMAT procedures, including multiple metastases stereotactic radiosurgery procedures. Methods: A trajectory algorithm was developed, which can dynamically modify the angle of the collimator as a function of VMAT control point to provide optimized collimation of target volume(s). Central to this algorithm is a concept denoted “whitespace”, defined as area within the jaw-defined BEV field, outside of the PTV, and not shielded by the MLC when fit to the PTV. Calculating whitespace at all collimator angles and every control point, a two-dimensional topographical map depicting the tightness-of-fit of the MLC was generated. A variety of novel searching algorithms identified a number of candidate trajectories of continuous collimator motion. Ranking these candidate trajectories according to their accrued whitespace value produced an optimal solution for navigation of this map. Results: All trajectories were normalized to minimum possible (i.e. calculated without consideration of collimator motion constraints) accrued whitespace. On an acoustic neuroma case, a random walk algorithm generated a trajectory with 151% whitespace; random walk including a mandatory anchor point improved this to 148%; gradient search produced a trajectory with 137%; and bi-directional gradient search generated a trajectory with 130% whitespace. For comparison, a fixed collimator angle of 30° and 330° accumulated 272% and 228% of whitespace, respectively. The algorithm was tested on a clinical case with two metastases (single isocentre) and identified collimator angles that allow for simultaneous irradiation of the PTVs while minimizing normal tissue irradiation. Conclusion: Dynamic collimator trajectories have the potential to improve VMAT deliveries through increased efficiency and reduced normal tissue dose, especially in treatment of multiple cranial metastases, without significant safety concerns that hinder immediate clinical implementation.

60 APPLIED LIFE SCIENCES↗

Boundary conditions for the subdiffusion equation

The boundary conditions for the subdiffusion equations are formulated using the continuous-time random walk model, as well as several versions of the random walk model on an irregular lattice. It is shown that the boundary conditions for the same equation in different models have different forms, and this difference considerably affects the solutions of this equation.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

Atomic motion from the mean square displacement in a monatomic liquid

V-T theory is constructed in the many-body Hamiltonian formulation, and is being developed as a novel approach to liquid dynamics theory. In this theory the liquid atomic motion consists of two contributions, normal mode vibrations in a single representative potential energy valley, and transits, which carry the system across boundaries between valleys. The mean square displacement time correlation function (the MSD) is a direct measure of the atomic motion, and our goal is to determine if the V-T formalism can produce a physically sensible account of this motion. We employ molecular dynamics (MD) data for a system representing liquid Na, and find the motion evolves in three successive time intervals: on the first 'vibrational' interval, the vibrational motion alone gives a highly accurate account of the MD data; on the second 'crossover' interval, the vibrational MSD saturates to a constant while the transit motion builds up from zero; on the third 'random walk' interval, the transit motion produces a purely diffusive random walk of the vibrational equilibrium positions. Furthermore, this motional evolution agrees with, and adds refinement to, the MSD atomic motion as described by current liquid dynamics theories.

74 ATOMIC AND MOLECULAR PHYSICS↗

Delocalization of a non-Hermitian quantum walk on random media in one dimension

Highlights: • We study the localization-delocalization transition of a non-Hermitian quantum walk. • We find that the phase transition is similar to the one in the Hatano-Nelson model. • All eigenvectors get extended and all eigenvalues become complex at the transition. • This implies that the localization lengths of all eigenvectors are the same. We first review the localization–delocalization transition of a non-Hermitian random tight-binding Anderson model, called the Hatano–Nelson model. We then report a new result for a non-Hermitian extension of a discrete-time quantum walk on a one-dimensional random medium; we numerically find a delocalization transition similar to one of the Hatano–Nelson model. As a common feature to both models, at the transition point, an eigenvector gets delocalized and at the same time the corresponding energy eigenvalue (for the latter quantum-walk model, the imaginary unit times the phase of the eigenvalue of the time-evolution operator) becomes complex. One of the unique properties of the present non-Hermitian quantum walk is that the localization length of all eigenvectors is the same, and thereby all eigenstates simultaneously undergo the delocalization transition and all energy eigenvalues become complex at the same time when we turn up a non-Hermitian parameter.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

Real time visualization of quantum walk

Time evolution of quantum particles like electrons is described by time-dependent Schrödinger equation (TDSE). The TDSE is regarded as the diffusion equation of electrons with imaginary diffusion coefficients. And the TDSE is solved by quantum walk (QW) which is regarded as a quantum version of a classical random walk. The diffusion equation is solved in discretized space/time as in the case of classical random walk with additional unitary transformation of internal degree of freedom typical for quantum particles. We call the QW for solution of the TDSE a Schrödinger walk (SW). For observation of one quantum particle evolution under a given potential in atto-second scale, we attempt a successive computation and visualization of the SW. Using Pure Data programming, we observe the correct behavior of a probability distribution under the given potential in real time for observers of atto-second scale.

97 MATHEMATICS AND COMPUTING↗

A finite difference informed random walker (FDiRW) solver for strongly inhomogeneous diffusion problems

In nature, many complex multi-physics coupling problems exhibit strong diffusivity inhomogeneity. For instance, in the context of radionuclide absorption by porous wasteform materials within a flowing waste stream, the difference of species’ diffusivity in solid and liquid phases spans by 3~8 orders of magnitude. To solve the diffusion equations with strongly inhomogeneous diffusivity, traditional discretization-based methods, such as the Finite Difference Method (FDM), require infinitesimally small time steps (<10 -10 ) as high spatial resolutions are employed in most microstructure evolution processes, leading to prohibitively high computational costs. Here, this work developed an integrated numerical approach (FDiRW: Finite Difference informed Random Walk) to tackle this challenge. The idea is that utilizing the Random Walk concept, the fast diffusion is modeled as a superposition of point source’s solution for a concentration distribution while FDM is used to obtain the point source’s solution at each node. A mesh-coarsening algorithm is developed to generate an exclusive coarse mesh for FDiRW approach to maximize its efficiency. The effectiveness of the coarse mesh-based FDiRW approach is validated by benchmarking Finite Difference solutions. Numerical results demonstrated that FDiRW achieves a remarkable 1000x computational efficiency improvement over FDM while preserving desired accuracy for a medium-sized model of 192 × 192 × 192 grids. Finally, as models scale up, a floating-point operations (PLOPs) analysis of the FDiRW algorithm reveals that its computational complexity grows quadratically in terms of the number of nodes employed in computation.

36 MATERIALS SCIENCE↗

Intrepid MCMC: Metropolis-Hastings with exploration

In engineering examples, one often encounters the need to sample from unnormalized distributions with complex shapes that may also be implicitly defined through a physical or numerical simulation model, making it computationally expensive to evaluate the associated density function. For such cases, MCMC has proven to be an invaluable tool. Random-walk Metropolis Methods (also known as Metropolis-Hastings (MH)), in particular, are highly popular for their simplicity, flexibility, and ease of implementation. However, most MH algorithms suffer from significant limitations when attempting to sample from distributions with multiple modes (particularly disconnected ones). Here, in this paper, we present Intrepid MCMC - a novel MH scheme that utilizes a simple coordinate transformation to significantly improve the mode-finding ability and convergence rate to the target distribution of random-walk Markov chains while retaining most of the simplicity of the vanilla MH paradigm. Through multiple examples, we showcase the improvement in the performance of Intrepid MCMC over vanilla MH for a wide variety of target distribution shapes. We also provide an analysis of the mixing behavior of the Intrepid Markov chain, as well as the efficiency of our algorithm for increasing dimensions. A thorough discussion is presented on the practical implementation of the Intrepid MCMC algorithm. Finally, its utility is highlighted through a Bayesian parameter inference problem for a two-degree-of-freedom oscillator under free vibration.

97 - MATHEMATICS AND COMPUTING↗

Neutron Next-Event Estimators Kinematics (Rev.2)

This paper reviews the kinematics of neutron elastic and inelastic scattering with moving and stationary targets for contributions to Neutron Next-Event Estimators (NEEs). NEEs are often used for simulating the response of detectors in locations that have few random walk particles. Contributions to NEEs from collisions differ from sampling the outgoing particle state in standard random walk collisions as the location of the estimator is fixed, thus fixing the scattering angle between the incoming and outgoing directions. To calculate contributions to NEEs, the outgoing energies and probabilities of scatter toward the estimator must be calculated. This paper presents the most general case that encompasses elastic and inelastic scattering with both moving and stationary targets. The moving target case is required for elastic scattering with thermal motion due to the free gas thermal treatment approximation. The stationary target equations are presented for comparison with equations presented in canonical Monte Carlo texts.

73 NUCLEAR PHYSICS AND RADIATION PHYSICS↗

Dendritic Assembly of Gold Nanoparticles during Fuel-Forming Electrocatalysis

We report on the dendritic assembly of alkanethiol-capped gold nanoparticles on a glassy carbon support during electrochemical reduction of protons and CO 2 . We discovered that the primary mechanism by which surfactant-ligated gold nanoparticles lose surface area is by taking a random walk along the support, colliding with their neighbors, and fusing to form dendrites, a type of fractal aggregate. A random walk model reproduces the fractal dimensionality of the dendrites observed experimentally. The rate at which the dendrites form is strongly dependent on the solubility of the surfactant in the electrochemical double layer under the conditions of electrolysis. Since alkanethiolate surfactants reductively desorb at potentials close to the onset of CO 2 reduction, they do not poison the catalytic activity of the gold nanoparticles. While catalyst mobility is typically thought to be limited for room-temperature electrochemistry, our results reflect that nanoparticle mobility is significant under conditions at which they electrochemically catalyze gas evolution, even in the presence of a high surface area carbon and binder. A careful understanding of the electrolyte- and polarization-dependent nanoparticle aggregation kinetics informs strategies for maintaining catalyst dispersion during fuel-forming electrocatalysis.

dendrons↗

Improvements to the macroscopic-microscopic approach of nuclear fission

The well-established macroscopic-microscopic (mac-mic) description of nuclear fission enables the prediction of fission-fragment yields for a broad range of fissioning systems. In this work, we present several key enhancements to this approach. We improve upon the microscopic sector of nuclear potential-energy surfaces by magnifying the resolution of the Lipkin-Nogami equations and strengthening the Strutinsky procedure, thus reducing spurious effects from the continuum. We further present a novel deterministic method for calculating fission dynamics under the assumption of strongly damped nucleonic motion. Our technique directly determines the evolution of the scissioned shape distribution according to the number of random-walk steps rather than the statistical accumulation of fission events. We show that our new technique is equivalent to the Metropolis random walk pioneered over the past decade by Randrup and colleagues. It further improves upon it because we remove the need for altering the nuclear landscape via a biased potential. With our final improvement, we calculate fission fragments mass and charge distributions using particle number projection, which affords the simultaneous calculation of both mass- and charge-yield distributions. Fission fragments are thus calculated from the quantum-mechanical A -body states of the potential-energy surface rather than from the collective mass asymmetry variable α g of the finite-range liquid-drop model used in past work. We highlight the success of our enhancements by predicting the odd-even staggering and the charge polarization for the neutron-induced fission of 233 U and 235 U .

73 NUCLEAR PHYSICS AND RADIATION PHYSICS↗

How Large is an [alpha]-Helix? Studies of the Radii of Gyration of Helical Peptides by Small-angle X-ray Scattering and Molecular Dynamics

Using synchrotron radiation and the small-angle X-ray scattering technique we have measured the radii of gyration of a series of alanine-based alpha-helix-forming peptides of the composition Ace-(AAKAA)(n)-GY-NH(2), n=2-7, in aqueous solvent at 10(+/-1) degrees C. In contrast to other techniques typically used to study alpha-helices in isolation (such as nuclear magnetic resonance and circular dichroism), small-angle X-ray scattering reports on the global structure of a molecule and, as such, provides complementary information to these other, more sequence-local measuring techniques. The radii of gyration that we measure are, except for the 12-mer, lower than the radii of gyration of ideal alpha-helices or helices with frayed ends of the equivalent sequence-length. For example, the measured radius of gyration of the 37-mer is 14.2(+/-0.6)A, which is to be compared with the radius of gyration of an ideal 37-mer alpha-helix of 17.6A. Attempts are made to analyze the origin of this discrepancy in terms of the analytical Zimm-Bragg-Nagai (ZBN) theory, as well as distributed computing explicit solvent molecular dynamics simulations using two variants of the AMBER force-field. The ZBN theory, which treats helices as cylinders connected by random walk segments, predicts markedly larger radii of gyration than those measured. This is true even when the persistence length of the random walk parts is taken to be extremely short (about one residue). Similarly, the molecular dynamics simulations, at the level of sampling available to us, give inaccurate values of the radii of gyration of the molecules (by overestimating them by around 25% for longer peptides) and/or their helical content. We conclude that even at the short sequences examined here (< or =37 amino acid residues), these alpha-helical peptides behave as fluctuating semi-broken rods rather than straight cylinders with frayed ends.

43 PARTICLE ACCELERATORS↗

MAXIMUM LIKELIHOOD FITTING OF X-RAY POWER DENSITY SPECTRA: APPLICATION TO HIGH-FREQUENCY QUASI-PERIODIC OSCILLATIONS FROM THE NEUTRON STAR X-RAY BINARY 4U1608-522

High-frequency quasi-periodic oscillations (QPOs) from weakly magnetized neutron stars display rapid frequency variability (second timescales) and high coherence with quality factors up to at least 200 at frequencies about 800-850 Hz. Their parameters have been estimated so far from standard min({chi}{sup 2}) fitting techniques, after combining a large number of power density spectra (PDS), to have the powers normally distributed (the so-called Gaussian regime). Before combining PDS, different methods to minimize the effects of the frequency drift to the estimates of the QPO parameters have been proposed, but none of them relied on fitting the individual PDS. Accounting for the statistical properties of PDS, we apply a maximum likelihood method to derive the QPO parameters in the non-Gaussian regime. The method presented is general, easy to implement, and can be applied to fitting individual PDS, several PDS simultaneously, or their average, and is obviously not specific to the analysis of kHz QPO data. It applies to the analysis of any PDS optimized in frequency resolution and for low-frequency variability or PDS containing features whose parameters vary on short timescales, as is the case for kHz QPOs. It is equivalent to the standard {chi}{sup 2} minimization fitting when the number of PDS fitted is large. The accuracy, reliability, and superiority of the method is demonstrated with simulations of synthetic PDS, containing Lorentzian QPOs of known parameters. Accounting for the broadening of the QPO profile, due to the leakage of power inherent to windowed Fourier transforms, the maximum likelihood estimates of the QPO parameters are asymptotically unbiased and have negligible bias when the QPO is reasonably well detected. By contrast, we show that the standard min({chi}{sup 2}) fitting method gives biased parameters with larger uncertainties. The maximum likelihood fitting method is applied to a subset of archival Rossi X-ray Timing Explorer data of the neutron star X-ray binary 4U1608-522, for which we show that the lower kHz QPO parameters can be measured on timescales as short as 8 s. To demonstrate the potential use of the results of the maximum likelihood method, we show that in the observation analyzed the time evolution of the frequency is consistent with a random walk. We then show that the broadening of the QPO due to the frequency drift scales as {radical}T, as expected from a random walk (T is the integration time of the PDS). This enables us to estimate the intrinsic quality factor of the QPO to be {approx}260, whereas previous analysis indicated a maximum value around 200.

79 ASTRONOMY AND ASTROPHYSICS↗

SUPERDIFFUSIVE SHOCK ACCELERATION

The theory of diffusive shock acceleration is extended to the case of superdiffusive transport, i.e., when the mean square deviation grows proportionally to t{sup {alpha}}, with {alpha} > 1. Superdiffusion can be described by a statistical process called Levy random walk, in which the propagator is not a Gaussian but it exhibits power-law tails. By using the propagator appropriate for Levy random walk, it is found that the indices of energy spectra of particles are harder than those obtained where a normal diffusion is envisaged, with the spectral index decreasing with the increase of {alpha}. A new scaling for the acceleration time is also found, allowing substantially shorter times than in the case of normal diffusion. Within this framework we can explain a number of observations of flat spectra in various astrophysical and heliospheric contexts, for instance, for the Crab Nebula and the termination shock of the solar wind.

79 ASTRONOMY AND ASTROPHYSICS↗

Neural Algorithms for Low Power Implementation of Partial Differential Equations

The rise of low-power neuromorphic hardware has the potential to change high-performance computing; however much of the focus on brain-inspired hardware has been on machine learning applications. A low-power solution for solving partial differential equations could radically change how we approach large-scale computing in the future. The random walk is a fundamental stochastic process that underlies many numerical tasks in scientific computing applications. We consider here two neural algorithms that can be used to efficiently implement random walks on spiking neuromorphic hardware. The first method tracks the positions of individual walkers independently by using a modular code inspired by grid cells in the brain. The second method tracks the densities of random walkers at each spatial location directly. We present the scaling complexity of each of these methods and illustrate their ability to model random walkers under different probabilistic conditions. Finally, we present implementations of these algorithms on neuromorphic hardware.

97 MATHEMATICS AND COMPUTING↗

Quantum walk computation

Quantum versions of random walks have diverse applications that are motivating experimental implementations as well as theoretical studies. Recent results showing quantum walks are “universal for quantum computation” relate to algorithms, to be run on quantum computers. We consider whether an experimental implementation of a quantum walk could provide useful computation before we have a universal quantum computer.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗