Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “Recursion”

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 505 records · Page 28
All sourcesNASA NTRSDOE OSTI
DOE OSTI2018

Multi‐dimensional lock‐free arrays for multithreaded mode‐directed tabling in Prolog

Summary This work proposes a new design for the supporting data structures used to implement multithreaded tabling in Prolog systems. Tabling is an implementation technique that improves the expressiveness of traditional Prolog systems in dealing with recursion and redundant computations. Mode‐directed tabling is an extension to the tabling technique that supports the definition of alternative criteria for specifying how answers are aggregated, thus being very suitable for problems where the goal is to dynamically calculate optimal or selective answers. In this work, we leverage the intrinsic potential that mode‐directed tabling has to express dynamic programming problems by creating a new design that improves the representation of multi‐dimensional arrays in the context of multithreaded tabling. To do so, we introduce a new mode for indexing arguments in mode‐directed tabled evaluations, named dim , where each dim argument features a uni‐dimensional lock‐free array. Experimental results using well‐known dynamic programming problems on a 32‐core machine show that the new design introduces less overheads and clearly improves the execution time for sequential and multithreaded tabled evaluations.

Areias, Miguel↗
DOE OSTI2022

Resident and transient coyotes exhibit differential patterns of movement behavior across heterogeneous landscapes in the southeastern United States

Coyotes (Canis latrans) are a highly adaptable canid species whose behavioral plasticity has allowed them to persist in a wide array of habitats throughout North America. As generalists, coyotes can alter movement patterns and change territorial strategies between residency (high site fidelity) and transiency (low site fidelity) to maximize fitness. Uncertainty remains about resident and transient coyote movement patterns and habitat use because research has reached conflicting conclusions regarding patterns of habitat use by both groups. We quantified effects of habitat on resident and transient coyote movement behavior using first passage time (FPT) analysis, which assesses recursive movement along an individual's movement path to delineate where they exhibit area-restricted search (ARS) behaviors relative to habitat attributes. We quantified monthly movement rates for 171 coyotes (76 residents and 53 transients) and then used estimated FPT values in generalized linear mixed models to quantify monthly habitat use for resident and transient coyotes. Transients had greater movement rates than residents across all months except January. Resident FPT values were positively correlated with agricultural land cover during fall and winter, but negatively correlated with agriculture during spring. Resident FPT values were also negatively correlated with developed habitats during May–August, deciduous land cover during June–August, and wetlands during September–January except November. FPT values of transient coyotes were positively correlated with developed areas throughout much of the year and near wetlands during July–September. Transient FPT values were negatively correlated with agriculture during all months except June and July. High FPT values (ARS behavior) of residents and transients were generally correlated with greater densities of edge habitat. Although we observed high individual variation in space use, our study found substantive differences in habitat use between residents and transients, providing further evidence that complexity and plasticity of coyote habitat use is influenced by territorial strategy.

54 ENVIRONMENTAL SCIENCES↗
DOE OSTI2015

A Parallel Computing Framework for Finding the Supported Solutions to a Biobjective Network Optimization Problem

Abstract Solving multi‐objective combinatorial optimization problems can quickly become computationally challenging when applied to large networks generated from big data. Present‐day first‐rate Mixed Integer Programming (MIP) solvers have parallelism built‐in to take advantage of multicore architectures; but specialized network optimization algorithms that can often solve graph problems more efficiently than a general MIP solver are typically programmed serially. Thus, these network algorithm implementations do not take full advantage of modern multicore computer capabilities. Many parallel computing languages include a fork/join framework into their concurrency packages that allow for simple conversion of recursive serial algorithms to operate in parallel without having to use complicated low‐level message‐passing interfaces. Fork/join is particularly well suited to divide and conquer algorithms such as Non‐Inferior Set Estimation (NISE) method for computing the supported Pareto front of a multi‐objective optimization problem. This work develops a simple general parallel NISE (pNISE) implementation using the Java 7 concurrency tools, and then offers results from a specific implementation of solving a bi‐objective shortest path problem. The results indicate that this method is capable of sizeable speed‐ups on both small‐scale personal computers as well as large‐scale shared memory supercomputers. Finally, other network problems suitable to this method are discussed, including multi‐objective variants of the minimum spanning tree problem, transportation problem, assignment problem, maximum flow problem, and the minimum‐cost flow problem. Copyright © 2015 John Wiley & Sons, Ltd.

Medrano, Fernando Antonio↗
DOE OSTI2019

Implementation of the Crank‐Nicolson Douglas‐Gunn finite‐difference time domain with complex frequency‐shifted perfectly matched layer for modeling unbounded isotropic dispersive media in two dimensions

Abstract To model open‐domain problems with Drude, Lorentz, and Debye media, the complex frequency‐shifted perfectly matched layer (CFS‐PML) is adopted to truncate the Crank‐Nicolson Douglas‐Gunn finite‐difference time‐domain (CNDG‐FDTD) region. The auxiliary differential equation (ADE) and the bilinear Z ‐transform methods are incorporated separately into the implementations of CNDG‐CFS‐PML formulations, while the ADE, piecewise linear recursive convolution (RC), and trapezoidal RC methods are utilized to model dispersive media. The proposed formulations can not only circumvent the stability condition, but also have the advantages of the CFS‐PML in attenuating the evanescent waves and reducing the late‐time reflection. Three numerical examples have been carried out to validate these formulations. The simulation results show that the proposed CNDG‐CFS‐PML algorithm is efficient in absorbing performance and saving more computational time compared with the conventional FDTD method, which leads to extensive applicability and acts as a very good prospect.

Shi, Xue‐Yang↗
DOE OSTI2013

Commuting projections on graphs

For a given (connected) graph, we consider vector spaces of (discrete) functions defined on its vertices and its edges. These two spaces are related by a discrete gradient operator, Grad and its adjoint, ₋Div, referred to as (negative) discrete divergence. We also consider a coarse graph obtained by aggregation of vertices of the original one. Then a coarse vertex space is identified with the subspace of piecewise constant functions over the aggregates. We consider the ℓ 2 -projection Q H onto the space of these piecewise constants. In the present paper, our main result is the construction of a projection π H from the original edge-space onto a properly constructed coarse edge-space associated with the edges of the coarse graph. The projections π H and Q H commute with the discrete divergence operator, i.e., we have div π H = Q H div. The respective pair of coarse edge-space and coarse vertexspace offer the potential to construct two-level, and by recursion, multilevel methods for the mixed formulation of the graph Laplacian which utilizes the discrete divergence operator. The performance of one two-level method with overlapping Schwarz smoothing and correction based on the constructed coarse spaces for solving such mixed graph Laplacian systems is illustrated on a number of graph examples.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2014

Adaptive h -refinement for reduced-order models: ADAPTIVE h -refinement for reduced-order models

Our work presents a method to adaptively refine reduced-order models a posteriori without requiring additional full-order-model solves. The technique is analogous to mesh-adaptive h-refinement: it enriches the reduced-basis space online by ‘splitting’ a given basis vector into several vectors with disjoint support. The splitting scheme is defined by a tree structure constructed offline via recursive k-means clustering of the state variables using snapshot data. This method identifies the vectors to split online using a dual-weighted-residual approach that aims to reduce error in an output quantity of interest. The resulting method generates a hierarchy of subspaces online without requiring large-scale operations or full-order-model solves. Furthermore, it enables the reduced-order model to satisfy any prescribed error tolerance regardless of its original fidelity, as a completely refined reduced-order model is mathematically equivalent to the original full-order model. Experiments on a parameterized inviscid Burgers equation highlight the ability of the method to capture phenomena (e.g., moving shocks) not contained in the span of the original reduced basis.

42 ENGINEERING↗
DOE OSTI2019

Domain-specific virtual processors as a portable programming and execution model for parallel computational workloads on modern heterogeneous high-performance computing architectures

We advocate domain-specific virtual processors (DSVP) as a portability layer for expressing and executing domain-specific computational workloads on modern heterogeneous HPC architectures, with applications in quantum chemistry. Specifically, in this article we extend, generalize and better formalize the concept of a domain-specific virtual processor as applied to scientific high-performance computing. In particular, we introduce a system-wide recursive (hierarchical) hardware encapsulation mechanism into the DSVP architecture and specify a concrete microarchitectural design of an abstract DSVP from which specialized DSVP implementations can be derived for specific scientific domains. Furthermore, we demonstrate, an example of a domain-specific virtual processor specialized to numerical tensor algebra workloads, which is implemented in the ExaTENSOR library developed by the author with a primary focus on the quantum many-body computational workloads on large-scale GPU-accelerated HPC platforms.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2014

Hierarchical computation in the SPMD programming model

Large-scale parallel machines are programmed mainly with the single program, multiple data (SPMD) model of parallelism. While this model has advantages of scalability and simplicity, it does not fit well with divide-and-conquer parallelism or hierarchical machines that mix shared and distributed memory. In this paper, we define the recursive single program, multiple data model (RSPMD) that extends SPMD with a hierarchical team mechanism to support hierarchical algorithms and machines. We implement this model in the Titanium language and describe how to eliminate a class of deadlocks by ensuring alignment of collective operations. We present application case studies evaluating the RSPMD model, showing that it enables divide-and-conquer algorithms such as sorting to be elegantly expressed and that team collective operations increase performance of conjugate gradient by up to a factor of two. The model also facilitates optimizations for hierarchical machines, improving scalability of particle in cell by 8x and performance of sorting and a stencil code by up to 40% and 14%, respectively.

Kamil, A↗
DOE OSTI2017

Parallelizing Single Source Shortest Path with OpenSHMEM

Single Source Shortest Path (SSSP) is one of the widely occurring graph problems where the paths are discovered from an origin vertex to all other vertices in the graph. In this paper, we discuss our experience parallelizing SSSP using OpenSHMEM. We start with the serial Dijkstra and Bellman-Ford algorithms, parallelize these algorithms, and adapt them to the Partitioned Global Address Space (PGAS) programming model. We implement the parallel algorithms using OpenSHMEM and introduce a series of optimizations to achieve higher scaling and performance characteristics. The implementation is evaluated on Titan with various graphs including synthetic Recursive Matrix (R-MAT) and small-world network graphs as well as real-world graphs from Facebook, Twitter, LiveJournal, and the road maps of California and Texas.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2012

Assessing the Performance and Scalability of a Novel Multilevel K-Nomial Allgather on CORE-Direct Systems

In this paper, we propose a novel allgather algorithm, Reindexed Recursive K-ing (RRK), which leverages flexibility in the algorithm’s tree topology and ability to make asynchronous progress coupled with Core-Direct communication offload capability to optimize the MPI_Allgather for Core-Direct enabled systems. In particular, the RRK introduces a reindexing scheme which ensures contiguous data transfers while adding only a single additional send and receive operation for any radix, k, or communicator size, N. This allows us to improve algorithm scalability by avoiding the use of a scatter/gather elements (SGE) list on InfiniBand networks. The implementations of the RRK algorithm and its evaluation shows that it performs and scales well on Core-Direct systems for a wide range of message sizes and various communicator configurations.

Allgather↗
DOE OSTI2022

Celestial operator product expansions and w 1+∞ symmetry for all spins

The operator product expansion of massless celestial primary operators of arbitrary spin is investigated. Poincaré symmetry is found to imply a set of recursion relations on the operator product expansion coefficients of the leading singular terms at tree-level in a holomorphic limit. The symmetry constraints are solved by an Euler beta function with arguments that depend simply on the right-moving conformal weights of the operators in the product. These symmetry-derived coefficients are shown not only to match precisely those arising from momentum-space tree-level collinear limits, but also to obey an infinite number of additional symmetry transformations that respect the algebra of w 1+∞ . In tree-level minimally-coupled gravitational theories, celestial currents are constructed from light transforms of conformally soft gravitons and found to generate the action of w 1+∞ on arbitrary massless celestial primaries. Results include operator product expansion coefficients for fermions as well as those arising from higher-derivative non-minimal couplings of gluons and gravitons.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗
DOE OSTI2024

Efficiently evaluating loop integrals in the EFTofLSS using QFT integrals with massive propagators

We develop a new way to analytically calculate loop integrals in the Effective Field Theory of Large Scale-Structure. Previous available methods show severe limitations beyond the one-loop power spectrum due to analytical challenges and computational and memory costs. Our new method is based on fitting the linear power spectrum with cosmology-independent functions that resemble integer powers of quantum field theory massive propagators with complex masses. A remarkably small number of them is sufficient to reach enough accuracy. Similarly to former approaches, the cosmology dependence is encoded in the coordinate vector of the expansion of the linear power spectrum in our basis. We first produce cosmology-independent tensors where each entry is the loop integral evaluated on a given combination of basis vectors. For each cosmology, the evaluation of a loop integral amounts to contracting this tensor with the coordinate vector of the linear power spectrum. The 3-dimensional loop integrals for our basis functions can be evaluated using techniques familiar to particle physics, such as recursion relations and Feynman parametrization. We apply our formalism to evaluate the one-loop bispectrum of galaxies in redshift space. The final analytical expressions are quite simple and can be evaluated with little computational and memory cost. We show that the same expressions resolve the integration of all one-loop N-point function in the EFTofLSS. This method, which is originally presented here, has already been applied in the first one-loop bispectrum analysis of the BOSS data to constraint ΛCDM parameters and primordial non-Gaussianities [1, 2].

72 PHYSICS OF ELEMENTARY PARTICLES AND FIELDS↗
DOE OSTI2017

A periodic table of effective field theories

We systematically explore the space of scalar effective field theories (EFTs) consistent with a Lorentz invariant and local S-matrix. To do so we define an EFT classification based on four parameters characterizing 1) the number of derivatives per interaction, 2) the soft properties of amplitudes, 3) the leading valency of the interactions, and 4) the spacetime dimension. Carving out the allowed space of EFTs, we prove that exceptional EFTs like the non-linear sigma model, Dirac-Born-Infeld theory, and the special Galileon lie precisely on the boundary of allowed theory space. Using on-shell momentum shifts and recursion relations, we prove that EFTs with arbitrarily soft behavior are forbidden and EFTs with leading valency much greater than the spacetime dimension cannot have enhanced soft behavior. We then enumerate all single scalar EFTs in d < 6 and verify that they correspond to known theories in the literature. Finally, our results suggest that the exceptional theories are the natural EFT analogs of gauge theory and gravity because they are one-parameter theories whose interactions are strictly dictated by properties of the S-matrix.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗
DOE OSTI2018

Weight shifting operators and conformal blocks

We introduce a large class of conformally-covariant differential operators and a crossing equation that they obey. Together, these tools dramatically simplify calculations involving operators with spin in conformal field theories. As an application, we derive a formula for a general conformal block (with arbitrary internal and external representations) in terms of derivatives of blocks for external scalars. In particular, our formula gives new expressions for “seed conformal blocks” in 3d and 4d CFTs. We also find simple derivations of identities between external-scalar blocks with different dimensions and internal spins. We comment on additional applications, including deriving recursion relations for general conformal blocks, reducing inversion formulae for spinning operators to inversion formulae for scalars, and deriving identities between general 6j symbols (Racah-Wigner coefficients/“crossing kernels”) of the conformal group.

72 PHYSICS OF ELEMENTARY PARTICLES AND FIELDS↗
DOE OSTI2016

Sequencing BPS spectra

In this article, we provide both a detailed study of color-dependence of link homologies, as realized in physics as certain spaces of BPS states, and a broad study of the behavior of BPS states in general. We consider how the spectrum of BPS states varies as continuous parameters of a theory are perturbed. This question can be posed in a wide variety of physical contexts, and we answer it by proposing that the relationship between unperturbed and perturbed BPS spectra is described by a spectral sequence. These general considerations unify previous applications of spectral sequence techniques to physics, and explain from a physical standpoint the appearance of many spectral sequences relating various link homology theories to one another. We also study structural properties of colored HOMFLY homology for links and evaluate Poincar e polynomials in numerous examples. Among these structural properties is a novel "sliding" property, which can be explained by using (re fined) modular S-matrix. This leads to the identi fication of modular transformations in Chern-Simons theory and 3d N = 2 theory via the 3d/3d correspondence. In conclusion, we introduce the notion of associated varieties as classical limits of recursion relations of colored superpolynomials of links, and study their properties.

72 PHYSICS OF ELEMENTARY PARTICLES AND FIELDS↗
DOE OSTI2021

Decomposition of Feynman integrals by multivariate intersection numbers

We present a detailed description of the recent idea for a direct decomposition of Feynman integrals onto a basis of master integrals by projections, as well as a direct derivation of the differential equations satisfied by the master integrals, employing multivariate intersection numbers. We discuss a recursive algorithm for the computation of multivariate intersection numbers, and provide three different approaches for a direct decomposition of Feynman integrals, which we dub the straight decomposition, the bottom-up decomposition, and the top-down decomposition. These algorithms exploit the unitarity structure of Feynman integrals by computing intersection numbers supported on cuts, in various orders, thus showing the synthesis of the intersection-theory concepts with unitarity-based methods and integrand decomposition. We perform explicit computations to exemplify all of these approaches applied to Feynman integrals, paving a way towards potential applications to generic multi-loop integrals.

72 PHYSICS OF ELEMENTARY PARTICLES AND FIELDS↗
DOE OSTI2017

An algebraic approach to the analytic bootstrap

We develop an algebraic approach to the analytic bootstrap in CFTs. By acting with the Casimir operator on the crossing equation we map the problem of doing large spin sums to any desired order to the problem of solving a set of recursion relations. We compute corrections to the anomalous dimension of large spin operators due to the exchange of a primary and its descendants in the crossed channel and show that this leads to a Borel-summable expansion. Here, we analyse higher order corrections to the microscopic CFT data in the direct channel and its matching to infinite towers of operators in the crossed channel. We apply this method to the critical O(N ) model. At large N we reproduce the first few terms in the large spin expansion of the known two-loop anomalous dimensions of higher spin currents in the traceless symmetric representation of O(N ) and make further predictions. At small N we present the results for the truncated large spin expansion series of anomalous dimensions of higher spin currents.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗
DOE OSTI2021

Electromagnetic duality and D3-brane scattering amplitudes beyond leading order

We use on-shell methods to study the non-supersymmetric and supersymmetric low-energy S-matrix on a probe D3-brane, including both the 1-loop contributions of massless states as well as the effects of higher-derivative operators. Our results include: (1) A derivation of the duality invariance of Born-Infeld electrodynamics as the dimensional oxidation of the group of spatial rotations transverse to a probe M2-brane; this is done using a novel implementation of subtracted on-shell recursion. (2) The first explicit loop-level BCJ double-copy in a non-gravitational model, namely the calculation of the 4-point self-dual amplitude of non-supersymmetric Born-Infeld. (3) From previous results for n-point self-dual 1-loop BI amplitudes and the conjectured dimension-shifting relations in Yang-Mills, we obtain an explicit all-multiplicity, at all orders in E, expression for the 1-loop integrand of the MHV sector of N = 4 DBI. (4) For all n > 4, the explicitly integrated duality-violating 1-loop amplitudes (self-dual and next-to-self-dual in pure BI as well as MHV in N = 4 DBI) are shown to be removable at O(ε 0 ) by adding finite local counterterms; we propose that this may be true more generally at 1-loop order. (5) We find that in non-supersymmetric Born-Infeld, not all finite local counterterms needed to restore electromagnetic duality can be constructed using the double-copy with higher-derivative corrections, suggesting a fundamental tension between electromagnetic duality and color-kinematics duality at loop-level. Finally we comment on oxidation of duality symmetries in supergravity and the parallels it has to the M2-brane to D3-brane oxidation demonstrated in this paper.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗