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 55 records · Page 3
All sourcesNASA NTRSDOE OSTI
NASA NTRSDate not supplied

Formal Verification of Termination Criteria for​ First-Order Recursive Functions

This talk presents a formalization of several termination criteria for first-order recursive functions. The formalization, which is developed in the Prototype Verification System (PVS), includes the specification and proof of equivalence of semantic termination, Turing termination, size change principle, calling context graphs, and matrix-weighted graphs. These termination criteria are defined on a computational model that consists of a basic functional language called PVS0, which is an embedding of recursive first-order functions. Through this embedding, the native mechanism for checking termination of recursive functions in PVS could be soundly extended with semi-automatic termination criteria such as calling contexts graphs.

Termination↗
DOE OSTI2014

An Accelerated Recursive Doubling Algorithm for Block Tridiagonal Systems

Block tridiagonal systems of linear equations arise in a wide variety of scientific and engineering applications. Recursive doubling algorithm is a well-known prefix computation-based numerical algorithm that requires O(M^3(N/P + log P)) work to compute the solution of a block tridiagonal system with N block rows and block size M on P processors. In real-world applications, solutions of tridiagonal systems are most often sought with multiple, often hundreds and thousands, of different right hand sides but with the same tridiagonal matrix. Here, we show that a recursive doubling algorithm is sub-optimal when computing solutions of block tridiagonal systems with multiple right hand sides and present a novel algorithm, called the accelerated recursive doubling algorithm, that delivers O(R) improvement when solving block tridiagonal systems with R distinct right hand sides. Since R is typically about 100 1000, this improvement translates to very significant speedups in practice. Detailed complexity analyses of the new algorithm with empirical confirmation of runtime improvements are presented. To the best of our knowledge, this algorithm has not been reported before in the literature.

Seal, Sudip K↗
DOE OSTI2022

Application of Recursive Estimation to Heat Tracing for Groundwater/Surface‐Water Exchange

Abstract We present and demonstrate a recursive‐estimation framework to infer groundwater/surface‐water exchange based on temperature time series collected at different vertical depths below the sediment/water interface. We formulate the heat‐transport problem as a state‐space model (SSM), in which the spatial derivatives in the convection/conduction equation are approximated using finite differences. The SSM is calibrated to estimate time‐varying specific discharge using the Extended Kalman Filter (EKF) and Extended Rauch‐Tung‐Striebel Smoother (ERTSS). Whereas the EKF is suited to real‐time (“online”) applications and uses only the past and current measurements for estimation (filtering), the ERTSS is intended for near‐real time or batch‐processing (“offline”) applications and uses a window of data for batch estimation (smoothing). The two algorithms are demonstrated with synthetic and field‐experimental data and are shown to be efficient and rapid for the estimation of time‐varying flux over seasonal periods; further, the recursive approaches are effective in the presence of rapidly changing flux and (or) nonperiodic thermal boundary conditions, both of which are problematic for existing approaches to heat tracing of time‐varying groundwater/surface‐water exchange.

54 ENVIRONMENTAL SCIENCES↗
DOE OSTI2012

The recursion relation in Lagrangian perturbation theory

We derive a recursion relation in the framework of Lagrangian perturbation theory, appropriate for studying the inhomogeneities of the large scale structure of the universe. We use the fact that the perturbative expansion of the matter density contrast is in one-to-one correspondence with standard perturbation theory (SPT) at any order. This correspondence has been recently shown to be valid up to fourth order for a non-relativistic, irrotational and dust-like component. Assuming it to be valid at arbitrary (higher) order, we express the Lagrangian displacement field in terms of the perturbative kernels of SPT, which are itself given by their own and well-known recursion relation. We argue that the Lagrangian solution always contains more non-linear information in comparison with the SPT solution, (mainly) if the non-perturbative density contrast is restored after the displacement field is obtained.

79 ASTRONOMY AND ASTROPHYSICS↗
DOE OSTI2016

A Recursive Hypergraph Bipartitioning Framework for Reducing Bandwidth and Latency Costs Simultaneously

Intelligent partitioning models are commonly used for efficient parallelization of irregular applications on distributed systems. These models usually aim to minimize a single communication cost metric, which is either related to communication volume or message count. However, both volume- and message-related metrics should be taken into account during partitioning for a more efficient parallelization. There are only a few works that consider both of them and they usually address each in separate phases of a two-phase approach. In this work, we propose a recursive hypergraph bipartitioning framework that reduces the total volume and total message count in a single phase. In this framework, the standard hypergraph models, nets of which already capture the bandwidth cost, are augmented with message nets. The message nets encode the message count so that minimizing conventional cutsize captures the minimization of bandwidth and latency costs together. Our model provides a more accurate representation of the overall communication cost by incorporating both the bandwidth and the latency components into the partitioning objective. The use of the widely-adopted successful recursive bipartitioning framework provides the flexibility of using any existing hypergraph partitioner. In conclusion, the experiments on instances from different domains show that our model on the average achieves up to 52 percent reduction in total message count and hence results in 29 percent reduction in parallel running time compared to the model that considers only the total volume.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2022

Recursive Gaussian Process over graphs for Integrating Multi-timescale Measurements in Low-Observable Distribution Systems

The transition to a smarter grid is empowered by enhanced sensor deployments and smart metering infrastructure in the distribution system. Measurements from these sensors and meters can be used for many applications, including distribution system state estimation (DSSE). However, these measurements are typically sampled at different rates and could be intermittent due to losses during the aggregation process. These multi timescale measurements should be reconciled in real-time to perform accurate grid monitoring. This paper tackles this problem by formulating a recursive multi-task Gaussian process (RGP-G) approach that sequentially aggregates sensor measurements. Specifically, we formulate a recursive multi-task GP with and without network connectivity information to reconcile the multi time-scale measurements in distribution systems. Here, the proposed framework is capable of aggregating the multi-time scale measurements batch-wise or in real-time. Following the aggregation of the multi time-scale measurements, the spatial states of the consistent time-series are estimated using matrix completion based DSSE approach. Simulation results on IEEE 37 and IEEE 123 bus test systems illustrate the efficiency of the proposed methods from the standpoint of both multi time-scale data aggregation and DSSE.

42 ENGINEERING↗
DOE OSTI2025

Data-Driven Mean-Corrected Recursive Estimation-Based Optimal DER Dispatch for Distribution System Voltage Control

Recent advances in smart inverters offer opportunities to mitigate adverse grid impacts caused by high penetrations of distributed photovoltaics (PV) in distribution grids, such as voltage violations. Here, this paper proposes a novel measurement-driven optimal power flow (OPF)-based distributed energy resource management system (DERMS) voltage regulation via recursive sensitivity estimation informed coordinated control of distributed PV inverters. The proposed approach leverages available grid and controllable DER measurements, eliminating reliance on system model information while being adaptive and robust to volatile operating conditions. A mean-corrected recursive ridge regression (MCRRR) algorithm is proposed for sensitivity estimation, continuously refining the sensitivity model through a closed-form solution. It effectively manages varying grid operating conditions, such as changes in power injections and topology reconfiguration, to facilitate a time-varying update of the Load Sensitivity Factors (LSF). The proposed approach is formulated as a linear programming (LP) problem and is thus scalable to larger-scale distribution systems. Its effectiveness and efficiency are demonstrated on a realistic distribution feeder with high PV penetrations in Southern California, USA.

14 SOLAR ENERGY↗
DOE OSTI2013

Efficient Scheduling of Recursive Control Flow on GPUs

Graphics processing units (GPUs) have rapidly emerged as a very significant player in high performance computing. Single instruction multiple thread (SIMT) pipelines are typically used in GPUs to exploit parallelism and maximize performance. Although support for unstructured control flow has been included in GPUs, efficiently managing thread divergence for arbitrary parallel programs remains a critical challenge. In this paper, we focus on the problem of supporting recursion in modern GPUs. We design and comparatively evaluate various algorithms to manage thread divergence encountered in recursive programs. The results improve upon traditional post-dominator based reconvergence mechanisms designed to handle thread divergence due to control flow within a procedure.

GPUs↗
DOE OSTI2019

Extracting SIMD Parallelism from Recursive Task-Parallel Programs

The pursuit of computational efficiency has led to the proliferation of throughput-oriented hardware, from GPUs to increasingly wide vector units on commodity processors and accelerators. This hardware is designed to efficiently execute data-parallel computations in a vectorized manner. However, many algorithms are more naturally expressed as divide-and-conquer, recursive, task-parallel computations. In the absence of data parallelism, it seems that such algorithms are not well suited to throughput-oriented architectures. This paper presents a set of novel code transformations that expose the data parallelism latent in recursive, task- parallel programs. These transformations facilitate straightforward vectorization of task-parallel programs on commodity hardware. We also present scheduling policies that maintain high utilization of vector resources while limiting space usage. Across several task-parallel benchmarks, we demonstrate both efficient vector resource utilization and substantial speedup on chips using Intel’s SSE4.2 vector units, as well as accelerators using Intel’s AVX512 units. We then show through rigorous sampling that, in practice, our vectorization techniques are effective for a much larger class of programs.

Recursive Programs, task parallelism, vectorizatio↗
NASA NTRS2004

An adaptable recursive binary entropy coding technique

We present a novel data compression technique, called recursive interleaved entropy coding, that is based on recursive interleaving of variable-to-variable length binary source codes.

data compression entrophy coding biliary adaptive ↗
NASA NTRSDate not supplied

Progressive Failure Analysis of 3D Woven Composites via Multiscale Recursive Micromechanics

Multiscale progressive failure simulations have been performed for a 3D woven composite considering six length scales, spanning from the woven composite repeating unit cell to the matrix material containing voids. The Multiscale Recursive Micromechanics approach, which enables micromechanics models to call other micromechanics models (or themselves recursively) to consider finer and finer length scales, has been employed. The multiscale model uses both the generalized method of cells and Mori-Tanaka micromechanics theories and considers failure and damage at the lowest length scale. A simple subvolume elimination damage model, as well as the crack band model, are employed for the matrix and their predicted composite responses compared with and without a preexisting binder tow disbond. Results are also compared with experimental data for an AS4 carbon fiber/RTM6 epoxy matrix 3D orthogonal woven PMC, with good agreement in terms of global stiffness and global failure stress.

3D woven↗
DOE OSTI2018

Recursive integral method with Cayley transformation

Summary The recently developed RIM (recursive integral method) finds eigenvalues in a region of the complex plane. It computes an indicator to test if the region contains eigenvalues using an approximate spectral projection. If the indicator shows that the region contains eigenvalues, it is subdivided into smaller regions, which are then recursively tested and subdivided until any eigenvalues are isolated to a specified precision. We propose an enhancement to RIM that uses Cayley transformations and Arnoldi's method to greatly decrease the number of factorizations required to solve the linear systems that arise from a discretized contour integral to compute the indicator, which substantially reduces the computational cost. We demonstrate the efficacy of our method with numerical examples and compare with the implicitly restarted Arnoldi method, as implemented in eigs in MATLAB.

Huang, R.↗
DOE OSTI2019

Recursive representations of arbitrary Virasoro conformal blocks

We derive recursive representations in the internal weights of N-point Virasoro conformal blocks in the sphere linear channel and the torus necklace channel, and recursive representations in the central charge of arbitrary Virasoro conformal blocks on the sphere, the torus, and higher genus Riemann surfaces in the plumbing frame.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗
DOE OSTI2021

Recursion relations for 5-point conformal blocks

We consider 5-point functions in conformal field theories in d2 dimensions. Using weight-shifting operators, we derive recursion relations which allow for the computation of arbitrary conformal blocks appearing in 5-point functions of scalar operators, reducing them to a linear combination of blocks with scalars exchanged. We additionally derive recursion relations for the conformal blocks which appear when one of the external operators in the 5-point function has spin 1 or 2. Our results allow us to formulate positivity constraints using 5-point functions which describe the expectation value of the energy operator in bilocal states created by two scalars.

72 PHYSICS OF ELEMENTARY PARTICLES AND FIELDS↗
DOE OSTI2021

Revisiting the ODE Method for Recursive Algorithms: Fast Convergence Using Quasi Stochastic Approximation

Several decades ago, Profs. Sean Meyn and Lei Guo were postdoctoral fellows at ANU, where they shared interest in recursive algorithms. It seems fitting to celebrate Lei Guo's 60th birthday with a review of the ODE Method and its recent evolution. The method has been regarded as a technique for algorithm analysis. It is argued that this viewpoint is backwards: The original stochastic approximation method was surely motivated by an ODE, and tools for analysis came much later (based on establishing robustness of Euler approximations). The paper presents a brief survey of recent research in machine learning that shows the power of algorithm design in continuous time, following by careful approximation to obtain a practical recursive algorithm. While these methods are usually presented in a stochastic setting, this is not a prerequisite. In fact, recent theory shows that rates of convergence can be dramatically accelerated by applying techniques inspired by quasi Monte-Carlo. Subject to conditions, the optimal rate of convergence can be obtained by applying the averaging technique of Polyak and Ruppert. The conditions are not universal, but theory suggests alternatives to achieve acceleration. The theory is illustrated with applications to gradient-free optimization, and policy gradient algorithms for reinforcement learning.

learning and adaptive systems in artificial intell↗
DOE OSTI2018

Target tracking via recursive Bayesian state estimation in cognitive radar networks

To cope with complicated environments and stealthier targets, incorporating intelligence and cognition cycles into target tracking is of great importance in modern sensor network management. With remarkable advances in sensor techniques and deployable platforms, a sensing system has freedom to select a subset of available radars, plan their trajectories, and transmit designed waveforms. In this paper, we propose a general framework for single target tracking in cognitive networks of radars, including consideration of waveform design, path planning, and radar selection, which are separately but not jointly taken into account in existing work. The tracking procedure, built on the theories of dynamic graphical models (DGM) and recursive Bayesian state estimation (RBSE), is formulated as two iterative steps: (i) solving a combinatorial optimization problem to select the optimal subset of radars, waveforms, and locations for the next tracking instant, and (ii) acquiring the recursive Bayesian state estimation to accurately track the target. Further, an illustrative example introduces a specific scenario in 2-D space. Simulation results based on the scenario demonstrate that the proposed framework can accurately track the target under the management of the network of radars.

47 OTHER INSTRUMENTATION↗
DOE OSTI2023

Subspace recursive Fermi-operator expansion strategies for large-scale DFT eigenvalue problems on HPC architectures

Quantum mechanical calculations for material modeling using Kohn–Sham density functional theory (DFT) involve the solution of a nonlinear eigenvalue problem for N smallest eigenvector-eigenvalue pairs, with N proportional to the number of electrons in the material system. Here, these calculations are computationally demanding and have asymptotic cubic scaling complexity with the number of electrons. Large-scale matrix eigenvalue problems arising from the discretization of the Kohn–Sham DFT equations employing a systematically convergent basis traditionally rely on iterative orthogonal projection methods, which are shown to be computationally efficient and scalable on massively parallel computing architectures. However, as the size of the material system increases, these methods are known to incur dominant computational costs through the Rayleigh–Ritz projection step of the discretized Kohn–Sham Hamiltonian matrix and the subsequent subspace diagonalization of the projected matrix. This work explores the potential of polynomial expansion approaches based on recursive Fermi-operator expansion as an alternative to the subspace diagonalization of the projected Hamiltonian matrix to reduce the computational cost. Subsequently, we perform a detailed comparison of various recursive polynomial expansion approaches to the traditional approach of explicit diagonalization on both multi-node central processing unit and graphics processing unit architectures and assess their relative performance in terms of accuracy, computational efficiency, scaling behavior, and energy efficiency.

37 INORGANIC, ORGANIC, PHYSICAL, AND ANALYTICAL CH↗
DOE OSTI2024

Structured Prompt Interrogation and Recursive Extraction of Semantics (SPIRES): a method for populating knowledge bases using zero-shot learning

Abstract Motivation Creating knowledge bases and ontologies is a time consuming task that relies on manual curation. AI/NLP approaches can assist expert curators in populating these knowledge bases, but current approaches rely on extensive training data, and are not able to populate arbitrarily complex nested knowledge schemas. Results Here we present Structured Prompt Interrogation and Recursive Extraction of Semantics (SPIRES), a Knowledge Extraction approach that relies on the ability of Large Language Models (LLMs) to perform zero-shot learning and general-purpose query answering from flexible prompts and return information conforming to a specified schema. Given a detailed, user-defined knowledge schema and an input text, SPIRES recursively performs prompt interrogation against an LLM to obtain a set of responses matching the provided schema. SPIRES uses existing ontologies and vocabularies to provide identifiers for matched elements. We present examples of applying SPIRES in different domains, including extraction of food recipes, multi-species cellular signaling pathways, disease treatments, multi-step drug mechanisms, and chemical to disease relationships. Current SPIRES accuracy is comparable to the mid-range of existing Relation Extraction methods, but greatly surpasses an LLM’s native capability of grounding entities with unique identifiers. SPIRES has the advantage of easy customization, flexibility, and, crucially, the ability to perform new tasks in the absence of any new training data. This method supports a general strategy of leveraging the language interpreting capabilities of LLMs to assemble knowledge bases, assisting manual knowledge curation and acquisition while supporting validation with publicly-available databases and ontologies external to the LLM. Availability and implementation SPIRES is available as part of the open source OntoGPT package: https://github.com/monarch-initiative/ontogpt.

59 BASIC BIOLOGICAL SCIENCES↗