Search NASA⌕ Search

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.

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

At least 739 records · Page 41
All sourcesNASA NTRSDOE OSTI
NASA NTRS2001

The AutoBayes Program Synthesis System: System Description

AUTOBAYES is a fully automatic program synthesis system for the statistical data analysis domain. Its input is a concise description of a data analysis problem in the form of a statistical model; its output is optimized and fully documented C/C++ code which can be linked dynamically into the Matlab and Octave environments. AUTOBAYES synthesizes code by a schema-guided deductive process. Schemas (i.e., code templates with associated semantic constraints) are applied to the original problem and recursively to emerging subproblems. AUTOBAYES complements this approach by symbolic computation to derive closed-form solutions whenever possible. In this paper, we concentrate on the interaction between the symbolic computations and the deductive synthesis process. A statistical model specifies for each problem variable (i.e., data or parameter) its properties and dependencies in the form of a probability distribution, A typical data analysis task is to estimate the best possible parameter values from the given observations or measurements. The following example models normal-distributed data but takes prior information (e.g., from previous experiments) on the data's mean value and variance into account.

Fischer, Bernd↗
NASA NTRS2001

Circular Coinduction

Circular coinduction is a technique for behavioral reasoning that extends cobasis coinduction to specifications with circularities. Because behavioral satisfaction is not recursively enumerable, no algorithm can work for every behavioral statement. However. algorithms using circular coinduction can prove every practical behavioral result that we know. This paper proves the correctness of circular coinduction and some consequences.

Rosu, Grigore↗
NASA NTRS1994

Parallel Preconditioning for CFD Problems on the CM-5

Up to today, preconditioning methods on massively parallel systems have faced a major difficulty. The most successful preconditioning methods in terms of accelerating the convergence of the iterative solver such as incomplete LU factorizations are notoriously difficult to implement on parallel machines for two reasons: (1) the actual computation of the preconditioner is not very floating-point intensive, but requires a large amount of unstructured communication, and (2) the application of the preconditioning matrix in the iteration phase (i.e. triangular solves) are difficult to parallelize because of the recursive nature of the computation. Here we present a new approach to preconditioning for very large, sparse, unsymmetric, linear systems, which avoids both difficulties. We explicitly compute an approximate inverse to our original matrix. This new preconditioning matrix can be applied most efficiently for iterative methods on massively parallel machines, since the preconditioning phase involves only a matrix-vector multiplication, with possibly a dense matrix. Furthermore the actual computation of the preconditioning matrix has natural parallelism. For a problem of size n, the preconditioning matrix can be computed by solving n independent small least squares problems. The algorithm and its implementation on the Connection Machine CM-5 are discussed in detail and supported by extensive timings obtained from real problem data.

Simon, Horst D.↗
NASA NTRS1995

Parallel CFD Algorithms for Aerodynamical Flow Solvers on Unstructured Meshes

The Advisory Group for Aerospace Research and Development (AGARD) has requested my participation in the lecture series entitled Parallel Computing in Computational Fluid Dynamics to be held at the von Karman Institute in Brussels, Belgium on May 15-19, 1995. In addition, a request has been made from the US Coordinator for AGARD at the Pentagon for NASA Ames to hold a repetition of the lecture series on October 16-20, 1995. I have been asked to be a local coordinator for the Ames event. All AGARD lecture series events have attendance limited to NATO allied countries. A brief of the lecture series is provided in the attached enclosure. Specifically, I have been asked to give two lectures of approximately 75 minutes each on the subject of parallel solution techniques for the fluid flow equations on unstructured meshes. The title of my lectures is "Parallel CFD Algorithms for Aerodynamical Flow Solvers on Unstructured Meshes" (Parts I-II). The contents of these lectures will be largely review in nature and will draw upon previously published work in this area. Topics of my lectures will include: (1) Mesh partitioning algorithms. Recursive techniques based on coordinate bisection, Cuthill-McKee level structures, and spectral bisection. (2) Newton's method for large scale CFD problems. Size and complexity estimates for Newton's method, modifications for insuring global convergence. (3) Techniques for constructing the Jacobian matrix. Analytic and numerical techniques for Jacobian matrix-vector products, constructing the transposed matrix, extensions to optimization and homotopy theories. (4) Iterative solution algorithms. Practical experience with GIVIRES and BICG-STAB matrix solvers. (5) Parallel matrix preconditioning. Incomplete Lower-Upper (ILU) factorization, domain-decomposed ILU, approximate Schur complement strategies.

Barth, Timothy J.↗
NASA NTRS1996

Generating Voronoi Diagrams for Curved Shapes with Divide-and-Conquer

Voronoi diagrams have been used in many practical applications including solid modeling, Numerical Control machining, Finite Element mesh generation, etc. Investigating the properties of these diagrams is an active research topic with many fruitful results. Computational techniques for Voronoi diagrams, however, have been concentrated on low order elements, for points, lines, polygons, quadratic curves and surfaces. This paper presents a divide-and-conquer scheme computing the diagrams for planar shapes bounded by closed curves commonly encountered in Computer Aided Design. These curves include analytical curves and splines. The algorithm first divides the boundary curve into sections, delimited by curve points with the minimal curvatures. Bisector branches for these sections are then generated and merged recursively to obtain the final diagram. A detailed example in the paper shows the steps of the generation and merging of the bisectors. A simple analysis of the complexity of the algorithm is also presented.

Chou, Jin J.↗
NASA NTRS2001

Facility Concepts for Mars Returned Sample Handling

Samples returned from Mars must be held in quarantine until their biological safety has been determined. A significant challenge, unique to NASA's needs, is how to contain the samples (to protect the blaspheme) while simultaneously protecting their pristine nature. This paper presents a comparative analysis of several quarantine facility concepts for handling and analyzing these samples. The considerations in this design analysis include: modes of manipulation; capability for destructive as well as non-destructive testing; avoidance of cross-contamination; linear versus recursive processing; and sample storage and retrieval within a closed system. The ability to rigorously contain biologically hazardous materials has been amply demonstrated by facilities that meet the specifications of the Center for Disease Control Biosafety Level 4. The newly defined Planetary Protection Level Alpha must provide comparable containment while assuring that the samples remain pristine; the latter requirement is based on the need to avoid compromising science analyses by instrumentation of the highest possible sensitivity (among other things this will assure that there is no false positive detection of organisms or organic molecules - a situation that would delay or prevent the release of the samples from quarantine). Protection of the samples against contamination by terrestrial organisms and organic molecules makes a considerable impact upon the sample handling facility. The use of glove boxes appears to be impractical because of their tendency to leak and to surges. As a result, a returned sample quarantine facility must consider the use of automation and remote manipulation to carry out the various functions of sample handling and transfer within the system. The problem of maintaining sensitive and bulky instrumentation under the constraints of simultaneous sample containment and contamination protection also places demands on the architectural configuration of the facility that houses it.

Cohen, Marc M.↗
NASA NTRS2001

Visualization of CFD Results in Immersive Virtual Environments

An object-oriented event-driven immersive virtual environment (VE) is described for the visualization of computational fluid dynamics (CFD) results. The VE incorporates the following types of primitive software objects: interface objects, support objects, geometric entities, and finite elements. The fluid domain is discretized using either a multi-block structured grid or an unstructured finite element mesh. The VE allows natural 'fly-through' visualization of the model, the CFD grid, and the model's surroundings. In order to help visualize the flow and its effects on the model, the VE incorporates the following objects: stream objects (lines, surface-restricted lines. ribbons. and volumes); colored surfaces; elevation surfaces; surface arrows; global and local iso-surfaces; vortex cores; and separation/attachment surfaces and lines. Most of these objects can be used for dynamically probing the flow. Particles and arrow animations can be displayed on top of stream objects. Primitive response quantities as well as derived quantities can be used. A recursive tree search algorithm is used for real-time point and value search in the CFD grid.

Wasfy, Tamer M.↗
NASA NTRS2002

System IDentification Programs for AirCraft (SIDPAC)

A collection of computer programs for aircraft system identification is described and demonstrated. The programs, collectively called System IDentification Programs for AirCraft, or SIDPAC, were developed in MATLAB as m-file functions. SIDPAC has been used successfully at NASA Langley Research Center with data from many different flight test programs and wind tunnel experiments. SIDPAC includes routines for experiment design, data conditioning, data compatibility analysis, model structure determination, equation-error and output-error parameter estimation in both the time and frequency domains, real-time and recursive parameter estimation, low order equivalent system identification, estimated parameter error calculation, linear and nonlinear simulation, plotting, and 3-D visualization. An overview of SIDPAC capabilities is provided, along with a demonstration of the use of SIDPAC with real flight test data from the NASA Glenn Twin Otter aircraft. The SIDPAC software is available without charge to U.S. citizens by request to the author, contingent on the requestor completing a NASA software usage agreement.

Morelli, Eugene A.↗
NASA NTRS2004

Pseudo Linear Attitude Determination of Spinning Spacecraft

This paper presents the overall mathematical model and results from pseudo linear recursive estimators of attitude and rate for a spinning spacecraft. The measurements considered are vector measurements obtained by sun-sensors, fixed head star trackers, horizon sensors, and three axis magnetometers. Two filters are proposed for estimating the attitude as well as the angular rate vector. One filter, called the q-Filter, yields the attitude estimate as a quaternion estimate, and the other filter, called the D-Filter, yields the estimated direction cosine matrix. Because the spacecraft is gyro-less, Euler's equation of angular motion of rigid bodies is used to enable the estimation of the angular velocity. A simpler Markov model is suggested as a replacement for Euler's equation in the case where the vector measurements are obtained at high rates relative to the spacecraft angular rate.

Harman, Richard R.↗
NASA NTRS2003

Motion-Based System Identification and Fault Detection and Isolation Technologies for Thruster Controlled Spacecraft

By analyzing the motions of a thruster-controlled spacecraft, it is possible to provide on-line (1) thruster fault detection and isolation (FDI), and (2) vehicle mass- and thruster-property identification (ID). Technologies developed recently at NASA Ames have significantly improved the speed and accuracy of these ID and FDI capabilities, making them feasible for application to a broad class of spacecraft. Since these technologies use existing sensors, the improved system robustness and performance that comes with the thruster fault tolerance and system ID can be achieved through a software-only implementation. This contrasts with the added cost, mass, and hardware complexity commonly required by FDI. Originally developed in partnership with NASA - Johnson Space Center to provide thruster FDI capability for the X-38 during re-entry, these technologies are most recently being applied to the MIT SPHERES experimental spacecraft to fly on the International Space Station in 2004. The model-based FDI uses a maximum-likelihood calculation at its core, while the ID is based upon recursive least squares estimation. Flight test results from the SPHERES implementation, as flown aboard the NASA KC-1 35A 0-g simulator aircraft in November 2003 are presented.

Wilson, Edward↗
NASA NTRS2004

Contributions of Spherical Harmonics to Magnetic and Gravitational Fields

Gravitational forces are of cardinal importance in the dynamics of spacecraft; magnetic attractions sometime play a significant role also, as was the case with the Long Duration Exposure Facility, and as is now true for the first segment of Space Station Freedom. Both satellites depend on gravitational moment and a device known as a magnetic damper to stabilize their orientation. Magnetic fields are mathematically similar to gravitational fields in one important respect: each can be regarded as a gradient of a potential function that, in turn, can be described as an infinite series of spherical harmonics. Consequently, the two fields can be computed, in part, with quantities that need only be evaluated once, resulting in a savings of time when both fields are needed. The objective of this material is to present magnetic field and gravitational force expressions, and point out the terms that belong to both this is accomplished in Section 1 and 2. Section 3 contains the deductive reasoning with which one obtains the expressions of interest. Finally, examples in Section 4 show these equations can be used to reproduce others that arise in connection with special cases such as the magnetic field produced by a tilted dipole, and gravitational force exerted by an oblate spheroid. The mathematics are discussed in the context of terrestrial fields; however, by substituting appropriate constants, the results can be made applicable to fields belonging to other celestial bodies. The expressions presented here share the characteristics of algorithms set forth for computing gravitational force. In particular, computation is performed speedily by means of recursion formulae, and the expressions do not suffer from the shortcoming of a singularity when evaluated at points that lie on the polar axis.

Roithmayr, Carlos M.↗
NASA NTRS2004

From Present Surveying to Future Prospecting of the Asteroid Belt

We have applied a future mission architecture, the Autonomous Nano-Technology Swarm (ANTS), to a proposed mission for in situ survey, or prospecting, of the asteroid belt, the Prospecting Asteroid Mission (PAM) as part of a NASA 2003 Revolutionary Aerospace Concept (RASC) study. ANTS architecture builds on and advances recent trends in robotics, artificial intelligence, and materials processing to minimize costs and maximize effectiveness of space operations. PAM and other applications have been proposed for the survey of inaccessible, high surface area populations of great interest from the standpoint of resources and/or solar system origin. The ANTS architecture is inspired by the success of social insect colonies, a success based on the division of labor within the colonies in two key ways: 1) within their specialties, individual specialists generally outperform generalists, and 2) with sufficiently efficient social interaction and coordination, the group of specialists generally outperforms the group of generalists. Thus systems designed as ANTS are built from potentially very large numbers of highly autonomous, yet socially interactive, elements. The architecture is self-similar in that elements and sub-elements of the system may also be recursively structured as ANTS on scales ranging from microscopic to interplanetary distances. Here, we analyze requirements for the mission application at the low gravity target end of the spectrum, the Prospecting Asteroid Mission (PAM), and for specialized autonomous operations which would support this mission. ANTS as applied to PAM involves the activities of hundreds of individual specialist 'sciencecraft'. Most of them, called Workers, carry and operate eight to nine different scientific instruments, as listed in the table, including spectrometers, ranging and radio science devices, and imagers. The remaining specialists, Messenger/Rulers, provide communication and coordination functions among specialists operating autonomously as individuals, team members, and subswarms.

Clark, P. E.↗
NASA NTRS2004

Sensor Web for Spatio-Temporal Monitoring of a Hydrological Environment

The Sensor Web is a macroinstrument concept that allows for the spatio-temporal understanding of an environment through coordinated efforts between multiple numbers and types of sensing platforms, including, in its most general form, both orbital and terrestrial and both fixed and mobile. Each of these platforms, or pods, communicates within its local neighborhood and thus distributes information to the instrument as a whole. The result of sharing and continual processing of this information among all the Sensor Web elements will result in an information flow and a global perception of and reactive capability to the environment. As illustrated, the Sensor Web concept also allows for the recursive notion of a web of webs with individual distributed instruments possibly playing the role of a single node point on a larger Sensor Web instrument. In particular, the fusion of inexpensive, yet sophisticated, commercial technology from both the computation and telecommunication revolutions has enabled the development of practical, fielded, and embedded in situ systems that have been the focus of the NASA/JPL Sensor Webs Project (http://sensorwebs.jpl.nasa.gov/). These Sensor Webs are complete systems consisting of not only the pod elements that wirelessly communicate among themselves, but also interfacing and archiving software that allows for easy use by the end-user. Previous successful deployments have included environments as diverse as coastal regions, Antarctica, and desert areas. The Sensor Web has broad implications for Earth and planetary science and will revolutionize the way experiments and missions are conceived and performed. As part of our current efforts to develop a macrointelligence within the system, we have deployed a Sensor Web at the Central Avra Valley Storage and Recovery Project (CAVSARP) facility located west of Tucson, AZ. This particular site was selected because it is ideal for studying spatio-temporal phenomena and for providing a test site for more sophisticated hydrological studies in the future.

Delin, K. A.↗
NASA NTRS2004

Telescoping Mechanics: A New Paradigm for Composite Behavior Simulation

This report reviews the application of telescoping mechanics to composites using recursive laminate theory. The elemental scale is the fiber-matrix slice, the behavior of which propagates to laminate. The results from using applications for typical, hybrid, and smart composites and composite-enhanced reinforced concrete structures illustrate the versatility and generality of telescoping scale mechanics. Comparisons with approximate, single-cell, and two- and three-dimensional finite-element methods demonstrate the accuracy and computational effectiveness of telescoping scale mechanics for predicting complex composite behavior.

Chamis, C. C.↗
NASA NTRS2004

Automatic Generation of Algorithms for the Statistical Analysis of Planetary Nebulae Images

Analyzing data sets collected in experiments or by observations is a Core scientific activity. Typically, experimentd and observational data are &aught with uncertainty, and the analysis is based on a statistical model of the conjectured underlying processes, The large data volumes collected by modern instruments make computer support indispensible for this. Consequently, scientists spend significant amounts of their time with the development and refinement of the data analysis programs. AutoBayes [GF+02, FS03] is a fully automatic synthesis system for generating statistical data analysis programs. Externally, it looks like a compiler: it takes an abstract problem specification and translates it into executable code. Its input is a concise description of a data analysis problem in the form of a statistical model as shown in Figure 1; its output is optimized and fully documented C/C++ code which can be linked dynamically into the Matlab and Octave environments. Internally, however, it is quite different: AutoBayes derives a customized algorithm implementing the given model using a schema-based process, and then further refines and optimizes the algorithm into code. A schema is a parameterized code template with associated semantic constraints which define and restrict the template s applicability. The schema parameters are instantiated in a problem-specific way during synthesis as AutoBayes checks the constraints against the original model or, recursively, against emerging sub-problems. AutoBayes schema library contains problem decomposition operators (which are justified by theorems in a formal logic in the domain of Bayesian networks) as well as machine learning algorithms (e.g., EM, k-Means) and nu- meric optimization methods (e.g., Nelder-Mead simplex, conjugate gradient). AutoBayes augments this schema-based approach by symbolic computation to derive closed-form solutions whenever possible. This is a major advantage over other statistical data analysis systems which use numerical approximations even in cases where closed-form solutions exist. AutoBayes is implemented in Prolog and comprises approximately 75.000 lines of code. In this paper, we take one typical scientific data analysis problem-analyzing planetary nebulae images taken by the Hubble Space Telescope-and show how AutoBayes can be used to automate the implementation of the necessary anal- ysis programs. We initially follow the analysis described by Knuth and Hajian [KHO2] and use AutoBayes to derive code for the published models. We show the details of the code derivation process, including the symbolic computations and automatic integration of library procedures, and compare the results of the automatically generated and manually implemented code. We then go beyond the original analysis and use AutoBayes to derive code for a simple image segmentation procedure based on a mixture model which can be used to automate a manual preproceesing step. Finally, we combine the original approach with the simple segmentation which yields a more detailed analysis. This also demonstrates that AutoBayes makes it easy to combine different aspects of data analysis.

Fischer, Bernd↗
NASA NTRS1999

Real-Time Parameter Estimation in the Frequency Domain

A method for real-time estimation of parameters in a linear dynamic state space model was developed and studied. The application is aircraft dynamic model parameter estimation from measured data in flight for indirect adaptive or reconfigurable control. Equation error in the frequency domain was used with a recursive Fourier transform for the real-time data analysis. Linear and nonlinear simulation examples and flight test data from the F-18 High Alpha Research Vehicle HARV) were used to demonstrate that the technique produces accurate model parameter estimates with appropriate error bounds. Parameter estimates converged in less than 1 cycle of the dominant dynamic mode natural frequencies, using control surface inputs measured in flight during ordinary piloted maneuvers. The real-time parameter estimation method has low computational requirements, and could be implemented aboard an aircraft in real time.

Morelli, Eugene A.↗
NASA NTRS1998

Efficient dynamic constraints for animating articulated figures

This paper presents an efficient dynamics-based computer animation system for simulating and controlling the motion of articulated figures. A non-trivial extension of Featherstone's O(n) recursive forward dynamics algorithm is derived which allows enforcing one or more constraints on the animated figures. We demonstrate how the constraint force evaluation algorithm we have developed makes it possible to simulate collisions between articulated figures, to compute the results of impulsive forces, to enforce joint limits, to model closed kinematic loops, and to robustly control motion at interactive rates. Particular care has been taken to make the algorithm not only fast, but also easy to implement and use. To better illustrate how the constraint force evaluation algorithm works, we provide pseudocode for its major components. Additionally, we analyze its computational complexity and finally we present examples demonstrating how our system has been used to generate interactive, physically correct complex motion with small user effort.

NASA Discipline Space Human Factors↗
NASA NTRS1998

Neural Networks for Rapid Design and Analysis

Artificial neural networks have been employed for rapid and efficient dynamics and control analysis of flexible systems. Specifically, feedforward neural networks are designed to approximate nonlinear dynamic components over prescribed input ranges, and are used in simulations as a means to speed up the overall time response analysis process. To capture the recursive nature of dynamic components with artificial neural networks, recurrent networks, which use state feedback with the appropriate number of time delays, as inputs to the networks, are employed. Once properly trained, neural networks can give very good approximations to nonlinear dynamic components, and by their judicious use in simulations, allow the analyst the potential to speed up the analysis process considerably. To illustrate this potential speed up, an existing simulation model of a spacecraft reaction wheel system is executed, first conventionally, and then with an artificial neural network in place.

Sparks, Dean W., Jr.↗