SEARCH · Search NASA

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.

SourceResearch connectionFrom yearThrough year

Quote a phrase for an exact phrase match. Source license links do not imply unrestricted reuse.

At least 37 records · Page 2

All sources NASA NTRS DOE OSTI

NASA NTRS1981

Recursive algorithms for two-dimensional smoothing using bicubic hermite polynomial

It is noted that in the past, smoothing splines originated from approximation theory have been successfully applied to data filtering and image smoothing problems. Even though the nonrecursive technique of smoothing splines gives an optimal solution, the amount of computation increases rapidly with the size of the two-dimensional data. A derivation is presented here of quarter-plane filtering algorithms that provide smoothed estimates of function values and their derivatives by fitting two-dimensional smoothing splines in a recursive manner. The derivation procedure sheds light on specific problems encountered in two-dimensional filtering problems. What is more, the amount of computation for this recursive processor increases only linearly with the size of the two-dimensional data. Because of certain approximations introduced in its derivation, this recursive processor becomes suboptimal.

Kim, C. S.↗

NASA NTRS1987

Deterministic properties of the recursive separable median filter

The recursive separable median filter has been successfully used to extract features from noisy two-dimensional signals. In many applications, it gives better noise suppression and edge preservation than the standard separable median filter. In this paper, a new approach is used for studying the deterministic properties of separable median filters. In particular, using threshold decomposition, the root structure of the recursive separable median filter is derived, where a root is a signal invariant to further filtering. It is shown that these root structures differ from those of their nonrecursive counterparts. It is also shown that any two-dimensional signal will converge to a root after repeated passes of the recursive separable median filter.

Mcloughlin, Michael P.↗

NASA NTRS1989

Recursive form of the eigensystem realization algorithm for system identification

An algorithm is developed for recursively calculating the minimum realization of a linear system from sampled impulse response data. The Gram-Schmidt orthonormalization technique is used to generate an orthonormal basis for factorization of the data matrix. The system matrix thus identified is in upper Hessenberg form, which has advantages for the identification of modal parameters including damping coefficients, frequencies, mode shapes, and modal participation factors. It also has the property that once an element of the system matrix is computed, it is never altered as the dimension of the model is increased in the recursive process. Numerical examples are presented for comparison of the recursive and nonrecursive forms of the eigensystem realization algorithm.

Longman, Richard W.↗

NASA NTRS1989

Recursive linearization of multibody dynamics equations of motion

The equations of motion of a multibody system are nonlinear in nature, and thus pose a difficult problem in linear control design. One approach is to have a first-order approximation through the numerical perturbations at a given configuration, and to design a control law based on the linearized model. Here, a linearized model is generated analytically by following the footsteps of the recursive derivation of the equations of motion. The equations of motion are first written in a Newton-Euler form, which is systematic and easy to construct; then, they are transformed into a relative coordinate representation, which is more efficient in computation. A new computational method for linearization is obtained by applying a series of first-order analytical approximations to the recursive kinematic relationships. The method has proved to be computationally more efficient because of its recursive nature. It has also turned out to be more accurate because of the fact that analytical perturbation circumvents numerical differentiation and other associated numerical operations that may accumulate computational error, thus requiring only analytical operations of matrices and vectors. The power of the proposed linearization algorithm is demonstrated, in comparison to a numerical perturbation method, with a two-link manipulator and a seven degrees of freedom robotic manipulator. Its application to control design is also demonstrated.

Lin, Tsung-Chieh↗

NASA NTRS1990

Recursive calculation of geared robot manipulator dynamics

A recursive formulation is presented for the calculation of the inverse and forward dynamics of rigid robot manipulators with gear systems on each joint. The complete effects of the gear ratios and the gyroscopic effects of the spinning motor/gear are included in the recursive formulation. The forward dynamics solution recursively calculates the joint accelerations when given motor torques, and the number of computations grows linearly with the number of links.

Murphy, Steve H.↗

NASA NTRS1990

Recursive dynamics for flexible multibody systems using spatial operators

Due to their structural flexibility, spacecraft and space manipulators are multibody systems with complex dynamics and possess a large number of degrees of freedom. Here the spatial operator algebra methodology is used to develop a new dynamics formulation and spatially recursive algorithms for such flexible multibody systems. A key feature of the formulation is that the operator description of the flexible system dynamics is identical in form to the corresponding operator description of the dynamics of rigid multibody systems. A significant advantage of this unifying approach is that it allows ideas and techniques for rigid multibody systems to be easily applied to flexible multibody systems. The algorithms use standard finite-element and assumed modes models for the individual body deformation. A Newton-Euler Operator Factorization of the mass matrix of the multibody system is first developed. It forms the basis for recursive algorithms such as for the inverse dynamics, the computation of the mass matrix, and the composite body forward dynamics for the system. Subsequently, an alternative Innovations Operator Factorization of the mass matrix, each of whose factors is invertible, is developed. It leads to an operator expression for the inverse of the mass matrix, and forms the basis for the recursive articulated body forward dynamics algorithm for the flexible multibody system. For simplicity, most of the development here focuses on serial chain multibody systems. However, extensions of the algorithms to general topology flexible multibody systems are described. While the computational cost of the algorithms depends on factors such as the topology and the amount of flexibility in the multibody system, in general, it appears that in contrast to the rigid multibody case, the articulated body forward dynamics algorithm is the more efficient algorithm for flexible multibody systems containing even a small number of flexible bodies. The variety of algorithms described here permits a user to choose the algorithm which is optimal for the multibody system at hand. The availability of a number of algorithms is even more important for real-time applications, where implementation on parallel processors or custom computing hardware is often necessary to maximize speed.

Jain, A.↗

NASA NTRS1991

Efficient control with an order (n) recursive inversion of the Jacobian for an n-link serial manipulator

A method is presented to order (n) recursively invert the Jacobian matrix for a serial n-link manipulator. By realizing that the Jacobian relationship involving accelerations is a special case for the forward dynamics problem, it is possible to obtain the Jacobian inverse by directly applying Rodriguez's (1987) recursive forward dynamics algorithm. In this technique, the n-link robot equation is formulated as a spatially recursive algorithm in the form of a filtering and smoothing problem. To compute the Jacobian inverse via this algorithm, the n-link manipulator is modeled with only a unit end-point mass and zero applied torques.

Meldrum, D. R.↗

NASA NTRS1992

Recursive flexible multibody system dynamics using spatial operators

This paper uses spatial operators to develop new spatially recursive dynamics algorithms for flexible multibody systems. The operator description of the dynamics is identical to that for rigid multibody systems. Assumed-mode models are used for the deformation of each individual body. The algorithms are based on two spatial operator factorizations of the system mass matrix. The first (Newton-Euler) factorization of the mass matrix leads to recursive algorithms for the inverse dynamics, mass matrix evaluation, and composite-body forward dynamics for the systems. The second (innovations) factorization of the mass matrix, leads to an operator expression for the mass matrix inverse and to a recursive articulated-body forward dynamics algorithm. The primary focus is on serial chains, but extensions to general topologies are also described. A comparison of computational costs shows that the articulated-body, forward dynamics algorithm is much more efficient than the composite-body algorithm for most flexible multibody systems.

Jain, A.↗

NASA NTRS1997

Recursive Deadbeat Controller Design

This paper presents a recursive algorithm for a deadbeat predictive controller design. The method combines together the concepts of system identification and deadbeat controller designs. It starts with the multi-step output prediction equation and derives the control force in terms of past input and output time histories. The formulation thus derived satisfies simultaneously system identification and deadbeat controller design requirements. As soon as the coefficient matrices are identified satisfying the output prediction equation, no further work is required to compute the deadbeat control gain matrices. The method can be implemented recursively just as any typical recursive system identification techniques.

Juang, Jer-Nan↗

NASA NTRS2002

Recursive Hierarchical Image Segmentation by Region Growing and Constrained Spectral Clustering

This paper describes an algorithm for hierarchical image segmentation (referred to as HSEG) and its recursive formulation (referred to as RHSEG). The HSEG algorithm is a hybrid of region growing and constrained spectral clustering that produces a hierarchical set of image segmentations based on detected convergence points. In the main, HSEG employs the hierarchical stepwise optimization (HS WO) approach to region growing, which seeks to produce segmentations that are more optimized than those produced by more classic approaches to region growing. In addition, HSEG optionally interjects between HSWO region growing iterations merges between spatially non-adjacent regions (i.e., spectrally based merging or clustering) constrained by a threshold derived from the previous HSWO region growing iteration. While the addition of constrained spectral clustering improves the segmentation results, especially for larger images, it also significantly increases HSEG's computational requirements. To counteract this, a computationally efficient recursive, divide-and-conquer, implementation of HSEG (RHSEG) has been devised and is described herein. Included in this description is special code that is required to avoid processing artifacts caused by RHSEG s recursive subdivision of the image data. Implementations for single processor and for multiple processor computer systems are described. Results with Landsat TM data are included comparing HSEG with classic region growing. Finally, an application to image information mining and knowledge discovery is discussed.

Tilton, James C.↗

NASA NTRS2016

Parameter Uncertainty for Aircraft Aerodynamic Modeling using Recursive Least Squares

A real-time method was demonstrated for determining accurate uncertainty levels of stability and control derivatives estimated using recursive least squares and time-domain data. The method uses a recursive formulation of the residual autocorrelation to account for colored residuals, which are routinely encountered in aircraft parameter estimation and change the predicted uncertainties. Simulation data and flight test data for a subscale jet transport aircraft were used to demonstrate the approach. Results showed that the corrected uncertainties matched the observed scatter in the parameter estimates, and did so more accurately than conventional uncertainty estimates that assume white residuals. Only small differences were observed between batch estimates and recursive estimates at the end of the maneuver. It was also demonstrated that the autocorrelation could be reduced to a small number of lags to minimize computation and memory storage requirements without significantly degrading the accuracy of predicted uncertainty levels.

Grauer, Jared A.↗

NASA NTRSDate not supplied

Formal Verification of Termination Criteria for First-Order Recursive Functions

This paper 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. As a proof of concept, this paper illustrates how such an extension can be implemented using proof strategies based on computational reflection.

Formal Verification↗

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 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 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 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 ↗