SEARCH · Search NASA

Results for “problem solving complexity”

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 757 records · Page 42

All sources NASA NTRS DOE OSTI

NASA NTRS1985

Parallel, iterative solution of sparse linear systems - Models and architectures

Solving large, sparse, linear systems of equations is a fundamental problem in large scale scientific and engineering computation. A model of a general class of asynchronous, iterative solution methods for linear systems is developed. In the model, the system is solved by creating several cooperating tasks that each compute a portion of the solution vector. A data transfer model predicting both the probability that data must be transferred between two tasks and the amount of data to be transferred is presented. This model is used to derive an execution time model for predicting parallel execution time and an optimal number of tasks given the dimension and sparsity of the coefficient matrix and the costs of computation, synchronization, and communication. The suitability of different parallel architectures for solving randomly sparse linear systems is discussed. Based on the complexity of task scheduling, one parallel architecture, based on a broadcast bus, is presented and analyzed.

Reed, D. A.↗

NASA NTRS1991

How far we are from the complete knowledge: Complexity of knowledge acquisition in Dempster-Shafer approach

When a knowledge base represents the experts' uncertainty, then it is reasonable to ask how far we are from the complete knowledge, that is, how many more questions do we have to ask (to these experts, to nature by means of experimenting, etc) in order to attain the complete knowledge. Of course, since we do not know what the real world is, we cannot get the precise number of questions from the very beginning: it is quite possible, for example, that we ask the right question first and thus guess the real state of the world after the first question. So we have to estimate this number and use this estimate as a natural measure of completeness for a given knowledge base. We give such estimates for Dempster-Shafer formalism. Namely, we show that this average number of questions can be obtained by solving a simple mathematical optimization problem. In principle this characteristic is not always sufficient to express the fact that sometimes we have more knowledge. For example, it has the same value if we have an event with two possible outcomes and nothing else is known, and if there is an additional knowledge that the probability of every outcome is 0.5. We'll show that from the practical viewpoint this is not a problem, because the difference between the necessary number of questions in both cases is practically negligible.

Chokr, Bassam A.↗

NASA NTRS2004

Generalized Fluid System Simulation Program

A general purpose program implemented on a computer analyzes steady state and transient flow in a complex fluid network, modeling phase changes, compressibility, mixture thermodynamics and external body forces such as gravity and centrifugal force. A preprocessor provides for the inter- active development of a fluid network simulation having nodes and branches. Mass, energy, and specie conservation equations are solved at the nodes, and momentum conservation equations are solved in the branches. Contained herein are subroutines for computing "real fluid" thermodynamic and thermophysical properties for 12 fluids, and a number of different source options are provided for model- ing momentum sources or sinks in the branches. The system of equations describing the fluid network is solved by a hybrid numerical method that is a combination of the Newton-Raphson and successive substitution methods. Application and verification of this invention are provided through an example problem, which demonstrates that the predictions of the present invention compare most reasonably with test data.

Alok Kumar Majumdar↗

NASA NTRSDate not supplied

Quantum-Accelerated Distributed Algorithms for Approximate Steiner Trees and Directed Minimum Spanning Trees

We present two algorithms in the Quantum CONGEST-CLIQUE model of distributed computation that succeed with high probability; one for producing an approximately optimal Steiner Tree, and one for producing an exact spanning arborescence of minimum weight, the analog of a Minimum Spanning Tree in a directed graph, each of which uses O~(n^(1/4)) rounds of communication and O~(n^(9/4)) messages, achieving a lower round and message complexity than any known algorithms in the classical CONGEST-CLIQUE model. The CONGEST distributed computational model allows limited-sized messages to be transmitted within a network described by a communication graph of size n in a series of rounds to address a computational problem. The size limitation for such messages isO(log(n)) bits at each edge of the communication graph per round. The communication graph in the CONGEST-CLIQUE model is fully connected. In the Quantum CONGEST-CLIQUE model, at most O(log(n)) classical and quantum bits (qubits) can be communicated across each edge of the communication graph per round. At a high level, we achieve these results by combining classical algorithms with fast quantum subroutines. These speedups further contribute to understanding what problems can be solved more efficiently when we allow quantum communication in this CONGEST-CLIQUE model of distributed computation.

quantum distributed algorithms↗

NASA NTRS2001

The CE/SE Method: a CFD Framework for the Challenges of the New Millennium

The space-time conservation element and solution element (CE/SE) method, which was originated and is continuously being developed at NASA Glenn Research Center, is a high-resolution, genuinely multidimensional and unstructured-mesh compatible numerical method for solving conservation laws. Since its inception in 1991, the CE/SE method has been used to obtain highly accurate numerical solutions for 1D, 2D and 3D flow problems involving shocks, contact discontinuities, acoustic waves, vortices, shock/acoustic waves/vortices interactions, shock/boundary layers interactions and chemical reactions. Without the aid of preconditioning or other special techniques, it has been applied to both steady and unsteady flows with speeds ranging from Mach number = 0.00288 to 10. In addition, the method has unique features that allow for (i) the use of very simple non-reflecting boundary conditions, and (ii) a unified wall boundary treatment for viscous and inviscid flows. The CE/SE method was developed with the conviction that, with a solid foundation in physics, a robust, coherent and accurate numerical framework can be built without involving overly complex mathematics. As a result, the method was constructed using a set of design principles that facilitate simplicity, robustness and accuracy. The most important among them are: (i) enforcing both local and global flux conservation in space and time, with flux evaluation at an interface being an integral part of the solution procedure and requiring no interpolation or extrapolation; (ii) unifying space and time and treating them as a single entity; and (iii) requiring that a numerical scheme be built from a nondissipative core scheme such that the numerical dissipation can be effectively controlled and, as a result, will not overwhelm the physical dissipation. Part I of the workshop will be devoted to a discussion of these principles along with a description of how the ID, 2D and 3D CE/SE schemes are constructed. In Part II, various applications of the CE/SE method, particularly those involving chemical reactions and acoustics, will be presented. The workshop will be concluded with a sketch of the future research directions.

Chang, Sin-Chung↗

NASA NTRS1992

Volume 2: Explicit, multistage upwind schemes for Euler and Navier-Stokes equations

The objective of this study was to develop a high-resolution-explicit-multi-block numerical algorithm, suitable for efficient computation of the three-dimensional, time-dependent Euler and Navier-Stokes equations. The resulting algorithm has employed a finite volume approach, using monotonic upstream schemes for conservation laws (MUSCL)-type differencing to obtain state variables at cell interface. Variable interpolations were written in the k-scheme formulation. Inviscid fluxes were calculated via Roe's flux-difference splitting, and van Leer's flux-vector splitting techniques, which are considered state of the art. The viscous terms were discretized using a second-order, central-difference operator. Two classes of explicit time integration has been investigated for solving the compressible inviscid/viscous flow problems--two-state predictor-corrector schemes, and multistage time-stepping schemes. The coefficients of the multistage time-stepping schemes have been modified successfully to achieve better performance with upwind differencing. A technique was developed to optimize the coefficients for good high-frequency damping at relatively high CFL numbers. Local time-stepping, implicit residual smoothing, and multigrid procedure were added to the explicit time stepping scheme to accelerate convergence to steady-state. The developed algorithm was implemented successfully in a multi-block code, which provides complete topological and geometric flexibility. The only requirement is C degree continuity of the grid across the block interface. The algorithm has been validated on a diverse set of three-dimensional test cases of increasing complexity. The cases studied were: (1) supersonic corner flow; (2) supersonic plume flow; (3) laminar and turbulent flow over a flat plate; (4) transonic flow over an ONERA M6 wing; and (5) unsteady flow of a compressible jet impinging on a ground plane (with and without cross flow). The emphasis of the test cases was validation of code, and assessment of performance, as well as demonstration of flexibility.

Elmiligui, Alaa↗

NASA NTRS1993

The combustion program at CTR

Understanding and modeling of turbulent combustion are key problems in the computation of numerous practical systems. Because of the lack of analytical theories in this field and of the difficulty of performing precise experiments, direct numerical simulation (DNS) appears to be one of the most attractive tools to use in addressing this problem. The general objective of DNS of reacting flows is to improve our knowledge of turbulent combustion but also to use this information for turbulent combustion models. For the foreseeable future, numerical simulation of the full three-dimensional governing partial differential equations with variable density and transport properties as well as complex chemistry will remain intractable; thus, various levels of simplification will remain necessary. On one hand, the requirement to simplify is not necessarily a handicap: numerical simulations allow the researcher a degree of control in isolating specific physical phenomena that is inaccessible in experiments. CTR has pursued an intensive research program in the field of DNS for turbulent reacting flows since 1987. DNS of reacting flows is quite different from DNS of non-reacting flows: without reaction, the equations to solve are clearly the five conservation equations of the Navier Stokes system for compressible situations (four for incompressible cases), and the limitation of the approach is the Reynolds number (or in other words the number of points in the computation). For reacting flows, the choice of the equations, the species (each species will require one additional conservation equation), the chemical scheme, and the configuration itself is more complex.

Poinsot, Thierry J.↗

NASA NTRS2001

Application of Aeroelastic Solvers Based on Navier Stokes Equations

The propulsion element of the NASA Advanced Subsonic Technology (AST) initiative is directed towards increasing the overall efficiency of current aircraft engines. This effort requires an increase in the efficiency of various components, such as fans, compressors, turbines etc. Improvement in engine efficiency can be accomplished through the use of lighter materials, larger diameter fans and/or higher-pressure ratio compressors. However, each of these has the potential to result in aeroelastic problems such as flutter or forced response. To address the aeroelastic problems, the Structural Dynamics Branch of NASA Glenn has been involved in the development of numerical capabilities for analyzing the aeroelastic stability characteristics and forced response of wide chord fans, multi-stage compressors and turbines. In order to design an engine to safely perform a set of desired tasks, accurate information of the stresses on the blade during the entire cycle of blade motion is required. This requirement in turn demands that accurate knowledge of steady and unsteady blade loading is available. To obtain the steady and unsteady aerodynamic forces for the complex flows around the engine components, for the flow regimes encountered by the rotor, an advanced compressible Navier-Stokes solver is required. A finite volume based Navier-Stokes solver has been developed at Mississippi State University (MSU) for solving the flow field around multistage rotors. The focus of the current research effort, under NASA Cooperative Agreement NCC3- 596 was on developing an aeroelastic analysis code (entitled TURBO-AE) based on the Navier-Stokes solver developed by MSU. The TURBO-AE code has been developed for flutter analysis of turbomachine components and delivered to NASA and its industry partners. The code has been verified. validated and is being applied by NASA Glenn and by aircraft engine manufacturers to analyze the aeroelastic stability characteristics of modem fans, compressors and turbines.

Keith, Theo G., Jr.↗

NASA NTRS1993

The effect of dissipative inhomogeneous medium on the statistics of the wave intensity

One of the main theoretical points in the theory of wave propagation in random medium is the derivation of closed form equations to describe the statistics of the propagating waves. In particular, in one dimensional problems, the closed form representation of the multiple scattering effects is important since it contributes in understanding such problems like wave localization, backscattering enhancement, and intensity fluctuations. In this the propagation of plane waves in a layer of one-dimensional dissipative random medium is considered. The medium is modeled by a complex permittivity whose real part is a constant representing the absorption. The one dimensional problem is mathematically equivalent to the analysis of a transmission line with randomly perturbed distributed parameters and a single mode lossy waveguide and the results can be used to study the propagation of radio waves through atmosphere and the remote sensing of geophysical media. It is assumed the scattering medium consists of an ensemble of one-dimensional point scatterers randomly positioned in a layer of thickness L with diffuse boundaries. A Poisson impulse process with density lambda is used to model the position of scatterers in the medium. By employing the Markov properties of this process an exact closed form equation of Kolmogorov-Feller type was obtained for the probability density of the reflection coefficient. This equation was solved by combining two limiting cases: (1) when the density of scatterers is small; and (2) when the medium is weakly dissipative. A two variable perturbation method for small lambda was used to obtain solutions valid for thick layers. These solutions are then asymptotically evaluated for small dissipation. To show the effect of dissipation, the mean and fluctuations of the reflected power are obtained. The results were compared with a lossy homogeneous medium and with a lossless inhomogeneous medium and the regions where the effect of absorption is not essential were discussed.

Saatchi, Sasan S.↗

NASA NTRS1979

Combustor modelling for scramjet engines

A system of computer programs is being developed to analyse and predict the complex flow fields found in hydrogen-fueled scramjet combustors. Each program is designed to solve the governing equation system for the type of flow present in a particular combustor region. A two-dimensional parabolic program has been found to be valuable in the development and experimental evaluation of turbulence and chemistry models for supersonic flow, and in the development of a program to model supersonic flow downstream of the fuel injection struts by means of solutions to the three-dimensional parabolic Navier-Stokes equations and species equations. A partially elliptic code has been derived to account for local subsonic flow regions, and fully elliptic programs have been developed by the consideration of streamwise diffusion effects for the recirculating flow fields near transverse fuel injectors. The programs are currently being applied to problems of scramjet engine development.

Drummond, J. P.↗

NASA NTRS1993

LSENS, a general chemical kinetics and sensitivity analysis code for gas-phase reactions: User's guide

A general chemical kinetics and sensitivity analysis code for complex, homogeneous, gas-phase reactions is described. The main features of the code, LSENS, are its flexibility, efficiency and convenience in treating many different chemical reaction models. The models include static system, steady, one-dimensional, inviscid flow, shock initiated reaction, and a perfectly stirred reactor. In addition, equilibrium computations can be performed for several assigned states. An implicit numerical integration method, which works efficiently for the extremes of very fast and very slow reaction, is used for solving the 'stiff' differential equation systems that arise in chemical kinetics. For static reactions, sensitivity coefficients of all dependent variables and their temporal derivatives with respect to the initial values of dependent variables and/or the rate coefficient parameters can be computed. This paper presents descriptions of the code and its usage, and includes several illustrative example problems.

Radhakrishnan, Krishnan↗

NASA NTRSDate not supplied

Analyzing Launch Operations using the Spaceport Throughput Analysis Resource (STAR)

NASA’s Kennedy Space Center (KSC) and Cape CanaveralSpace Force Station (CCSFS) are the world’s preeminent multi-user spaceport, providing facilities and launch capabilities to the agency, NASA’s commercial partners, and other government agencies. KSC works to ensure an environment in which NASA’s programs and other users can safely and effectively carry out their operations. Approximately 100 launches are expected to take place in 2024. KSC needs to meet the needs of customers who request launches based on their own schedules, but who may not be aware of KSC-wide resource limitations and external constraints on launch operations. KSC-wide resources include telecommunications, range tracking, commodities such as Helium and Nitrogen, and special equipment needed to support launches. External constraints include seasonal launch operations. Since space vehicles are complex and launch operations are uncertain, unexpected events can also cause delays in operations. The Spaceport Throughput AnalysisResource (STAR) assesses whether a specific set of pro-posed launches and associated activities can be performed given the resources KSC currently has available, and external constraints imposed on KSC operations. STAR integrates short-horizon scheduling and simulation of launches using a monte-carlo approach driven by configurable probabilities of different classes of event outcomes, including de-lays and worst-case use of resources. The resulting analyses inform stakeholders of key constraints preventing customers from being able to perform their missions as desired, and give insight into how to improve spaceport throughput. The rest of the paper is organized as follows. In 2 we de-scribe the problem STAR is intended to solve. In Section3 we formally describe the scheduling problem ingredients. In Section 4 we describe how manifests are simulated. InSection 5 we describe the constraints problem that is solved when rescheduling. In Section 6 we describe what information is recorded during manifest simulation in order to evaluate delays. In Section 7 we describe the specific problem solved for KSC. In Section 8 we describe the challenges of knowledge engineering for STAR.

Planning Scheduling Analysis↗

NASA NTRS1983

Parallel architectures for iterative methods on adaptive, block structured grids

A parallel computer architecture well suited to the solution of partial differential equations in complicated geometries is proposed. Algorithms for partial differential equations contain a great deal of parallelism. But this parallelism can be difficult to exploit, particularly on complex problems. One approach to extraction of this parallelism is the use of special purpose architectures tuned to a given problem class. The architecture proposed here is tuned to boundary value problems on complex domains. An adaptive elliptic algorithm which maps effectively onto the proposed architecture is considered in detail. Two levels of parallelism are exploited by the proposed architecture. First, by making use of the freedom one has in grid generation, one can construct grids which are locally regular, permitting a one to one mapping of grids to systolic style processor arrays, at least over small regions. All local parallelism can be extracted by this approach. Second, though there may be a regular global structure to the grids constructed, there will be parallelism at this level. One approach to finding and exploiting this parallelism is to use an architecture having a number of processor clusters connected by a switching network. The use of such a network creates a highly flexible architecture which automatically configures to the problem being solved.

Gannon, D.↗

NASA NTRS1996

LCTV Holographic Imaging

Astronauts are required to interface with complex systems that require sophisticated displays to communicate effectively. Lightweight, head-mounted real-time displays that present holographic images for comfortable viewing may be the ideal solution. We describe an implementation of a liquid crystal television (LCTV) as a spatial light modulator (SLM) for the display of holograms. The implementation required the solution of a complex set of problems. These include field calculations, determination of the LCTV-SLM complex transmittance characteristics and a precise knowledge of the signal mapping between the LCTV and frame grabbing board that controls it. Realizing the hologram is further complicated by the coupling that occurs between the phase and amplitude in the LCTV transmittance. A single drive signal (a gray level signal from a framegrabber) determines both amplitude and phase. Since they are not independently controllable (as is true in the ideal SLM) one must deal with the problem of optimizing (in some sense) the hologram based on this constraint. Solutions for the above problems have been found. An algorithm has been for field calculations that uses an efficient outer product formulation. Juday's MEDOF 7 (Minimum Euclidean Distance Optimal Filter) algorithm used for originally for filter calculations has been successfully adapted to handle metrics appropriate for holography. This has solved the problem of optimizing the hologram to the constraints imposed by coupling. Two laboratory methods have been developed for determining an accurate mapping of framegrabber pixels to LCTV pixels. A friendly software system has been developed that integrates the hologram calculation and realization process using a simple set of instructions. The computer code and all the laboratory measurement techniques determining SLM parameters have been proven with the production of a high quality test image.

Knopp, Jerome↗

NASA NTRS1998

A Hybrid SBR/MoM Technique for Analysis of Scattering from Small Protrusions on a Large Conducting Body

For analysis of large-scale electromagnetic scattering problems, high-frequency asymptotic methods are fast but approximate, whereas low-frequency numerical methods are accurate but slow. Neither can produce an efficient and accurate solution to scattering by large bodies containing small structures. A promising approach is to combine the best features of both types of methods to produce a hybrid technique that is sufficiently fast, reasonably accurate, and applicable to a class of unsolvable problems such as the scatterers mentioned above. There are two extremes for this type of hybridization. One is simply to superimpose solutions from asymptotic and numerical methods. While this approach is most widely used in practical applications, it neglects the interactions between the two solutions, which can be significant in many problems. The other extreme is to combine an asymptotic and a numerical method in an exact manner. In this approach, the effect of a large body is included by incorporating its diffraction into the Green's function in the integral equation for the small structures, which accounts for all interactions. While this approach is accurate, it is difficult to be implemented in a general-purpose computer code because of its complex nature. A more practical approach is to develop a technique that can include all significant interactions and neglect all trivial interactions. The resulting hybrid technique can produce sufficient accuracy and can be implemented in a general-purpose computer code. In this paper, we develop a technique that combines the shooting and- bouncing-ray (SBR) method and the method of moments (MoM) to solve for the scattering by large conducting bodies with small structures mounted on their surfaces.

Jin, J. M.↗

NASA NTRS2000

Fault Tree in the Trenches, A Success Story

Getting caught up in the explanation of Fault Tree Analysis (FTA) minutiae is easy. In fact, most FTA literature tends to address FTA concepts and methodology. Yet there seems to be few articles addressing actual design changes resulting from the successful application of fault tree analysis. This paper demonstrates how fault tree analysis was used to identify and solve a potentially catastrophic mechanical problem at a rocket motor manufacturer. While developing the fault tree given in this example, the analyst was told by several organizations that the piece of equipment in question had been evaluated by several committees and organizations, and that the analyst was wasting his time. The fault tree/cutset analysis resulted in a joint-redesign of the control system by the tool engineering group and the fault tree analyst, as well as bragging rights for the analyst. (That the fault tree found problems where other engineering reviews had failed was not lost on the other engineering groups.) Even more interesting was that this was the analyst's first fault tree which further demonstrates how effective fault tree analysis can be in guiding (i.e., forcing) the analyst to take a methodical approach in evaluating complex systems.

Long, R. Allen↗

NASA NTRS2009

Evolvable Neural Software System

The Evolvable Neural Software System (ENSS) is composed of sets of Neural Basis Functions (NBFs), which can be totally autonomously created and removed according to the changing needs and requirements of the software system. The resulting structure is both hierarchical and self-similar in that a given set of NBFs may have a ruler NBF, which in turn communicates with other sets of NBFs. These sets of NBFs may function as nodes to a ruler node, which are also NBF constructs. In this manner, the synthetic neural system can exhibit the complexity, three-dimensional connectivity, and adaptability of biological neural systems. An added advantage of ENSS over a natural neural system is its ability to modify its core genetic code in response to environmental changes as reflected in needs and requirements. The neural system is fully adaptive and evolvable and is trainable before release. It continues to rewire itself while on the job. The NBF is a unique, bilevel intelligence neural system composed of a higher-level heuristic neural system (HNS) and a lower-level, autonomic neural system (ANS). Taken together, the HNS and the ANS give each NBF the complete capabilities of a biological neural system to match sensory inputs to actions. Another feature of the NBF is the Evolvable Neural Interface (ENI), which links the HNS and ANS. The ENI solves the interface problem between these two systems by actively adapting and evolving from a primitive initial state (a Neural Thread) to a complicated, operational ENI and successfully adapting to a training sequence of sensory input. This simulates the adaptation of a biological neural system in a developmental phase. Within the greater multi-NBF and multi-node ENSS, self-similar ENI s provide the basis for inter-NBF and inter-node connectivity.

Curtis, Steven A.↗

NASA NTRS2021

Evaluation of Higher-order Quadrature Schemes in Improving Computational Efficiency for Orientation-averaged Single-Scattering Properties of Nonspherical Ice Particles

We evaluate several high-order quadrature schemes for accuracy and efficacy in obtaining orientation-averaged single-scattering properties (SSPs). We use the highly efficient MIDAS to perform electromagnetic scattering calculations to evaluate the gain in efficiency from these schemes. MIDAS is shown to be superior to DDSCAT, a popular discrete dipole approximation (DDA) method. This study is motivated by the fact that quality physical precipitation retrievals rely on using accurate orientation-averaged SSPs derived from realistic hydrometeors as input to radiative transfer Models (RTMs). The DDA has been a popular choice for single-scattering calculations, due to its versatility with respect to target geometry. However, being iterative-solver-based (ISB), the most used DDA codes, e.g. DDSCAT and ADDA, must solve the scattering problem for each orientation of the target separately. As the size parameter and geometric anisotropy of the hydrometeor increase, the number of orientations needed to obtain accurate orientation-averages can increase drastically and so does the computation cost incurred by the ISB-DDA methods. MIDAS is a Direct-Solver-Based (DSB) code, its decomposition of the original large matrix with a high rank into multiple more manageable smaller matrices of lower ranks makes it much more computationally efficient while maintaining excellent accuracy. In addition, direct solvers consider all requested orientations at once, giving MIDAS further advantage over popular ISB-DDA methods. MIDAS, when combined with high-order quadrature for orientation averaging, can be greater than three orders of magnitude more efficient in obtaining RTM-ready SSPs of complex-shaped hydrometeors than existing ISB-DDA methods, with the native quadrature schemes they offer.

Ines Fenni↗