Search NASA⌕ Search

SEARCH · Search NASA

Results for “computational 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.

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

At least 613 records · Page 34
All sourcesNASA NTRSDOE OSTI
NASA NTRS2002

A review of some exact solutions to the planar equations of motion of a thrusting spacecraft

With the complexities in computing optimal low thrust trajectories, easily-computed, good sub-optimal trajectories provide both a practical alternative for mission designers and a starting point for optimisation. The present paper collects in one place for easy reference and comparison several exact solutions that have been obtained in the literature over the last few decades: the logarithmic spiral, Pinkham's variant thereof, Forbes spiral, the exponential sinusoid, the case of constant radial thrust, Markopoulos's Keplerian thrust arcs, Lawden's spiral, and the analogous Bishop and Azimov spiral.

low-thrust trajectories electric propulsion solar ↗
NASA NTRS2002

A correction to a highly accurate voight function algorithm

An algorithm for rapidly computing the complex Voigt function was published by Shippony and Read. Its claimed accuracy was 1 part in 10^8. It was brought to our attention by Wells that Shippony and Read was not meeting its claimed accuracy for extremely small but non zero y values. Although true, the fix to the code is so trivial to warrant this note for those who use this algorithm.

voight integral faddeeva function↗
NASA NTRS2006

Nano Goes Magnetic to Attract Big Business

Glenn Research Center has combined state-of-the-art electrical designs with complex, computer-aided analyses to develop some of today s most advanced power systems, in space and on Earth. The center s Power and On-Board Propulsion Technology Division is the brain behind many of these power systems. For space, this division builds technologies that help power the International Space Station, the Hubble Space Telescope, and Earth-orbiting satellites. For Earth, it has woven advanced aerospace power concepts into commercial energy applications that include solar and nuclear power generation, battery and fuel cell energy storage, communications and telecommunications satellites, cryocoolers, hybrid and electric vehicles, and heating and air-conditioning systems.

Source record↗
NASA NTRS2009

Discrete Adjoint-Based Design Optimization of Unsteady Turbulent Flows on Dynamic Unstructured Grids

An adjoint-based methodology for design optimization of unsteady turbulent flows on dynamic unstructured grids is described. The implementation relies on an existing unsteady three-dimensional unstructured grid solver capable of dynamic mesh simulations and discrete adjoint capabilities previously developed for steady flows. The discrete equations for the primal and adjoint systems are presented for the backward-difference family of time-integration schemes on both static and dynamic grids. The consistency of sensitivity derivatives is established via comparisons with complex-variable computations. The current work is believed to be the first verified implementation of an adjoint-based optimization methodology for the true time-dependent formulation of the Navier-Stokes equations in a practical computational code. Large-scale shape optimizations are demonstrated for turbulent flows over a tiltrotor geometry and a simulated aeroelastic motion of a fighter jet.

Nielsen, Eric J.↗
NASA NTRS2009

On DESTINY Science Instrument Electrical and Electronics Subsystem Framework

Future space missions are going to require large focal planes with many sensing arrays and hundreds of millions of pixels all read out at high data rates'' . This will place unique demands on the electrical and electronics (EE) subsystem design and it will be critically important to have high technology readiness level (TRL) EE concepts ready to support such missions. One such omission is the Joint Dark Energy Mission (JDEM) charged with making precise measurements of the expansion rate of the universe to reveal vital clues about the nature of dark energy - a hypothetical form of energy that permeates all of space and tends to increase the rate of the expansion. One of three JDEM concept studies - the Dark Energy Space Telescope (DESTINY) was conducted in 2008 at the NASA's Goddard Space Flight Center (GSFC) in Greenbelt, Maryland. This paper presents the EE subsystem framework, which evolved from the DESTINY science instrument study. It describes the main challenges and implementation concepts related to the design of an EE subsystem featuring multiple focal planes populated with dozens of large arrays and millions of pixels. The focal planes are passively cooled to cryogenic temperatures (below 140 K). The sensor mosaic is controlled by a large number of Readout Integrated Circuits and Application Specific Integrated Circuits - the ROICs/ASICs in near proximity to their sensor focal planes. The ASICs, in turn, are serviced by a set of "warm" EE subsystem boxes performing Field Programmable Gate Array (FPGA) based digital signal processing (DSP) computations of complex algorithms, such as sampling-up-the-ramp algorithm (SUTR), over large volumes of fast data streams. The SUTR boxes are supported by the Instrument Control/Command and Data Handling box (ICDH Primary and Backup boxes) for lossless data compression, command and low volume telemetry handling, power conversion and for communications with the spacecraft. The paper outlines how the JDEM DESTINY concept instrument EE subsystem can be built now, a design; which is generally U.S. Government work not protected by U.S. copyright IEEEAC paper # 1429. Version 4. Updated October 19, 2009 applicable to a wide variety of missions using large focal planes with lar ge mosaics of sensors.

Kizhner, Semion↗
NASA NTRS2005

Task Description Language

Task Description Language (TDL) is an extension of the C++ programming language that enables programmers to quickly and easily write complex, concurrent computer programs for controlling real-time autonomous systems, including robots and spacecraft. TDL is based on earlier work (circa 1984 through 1989) on the Task Control Architecture (TCA). TDL provides syntactic support for hierarchical task-level control functions, including task decomposition, synchronization, execution monitoring, and exception handling. A Java-language-based compiler transforms TDL programs into pure C++ code that includes calls to a platform-independent task-control-management (TCM) library. TDL has been used to control and coordinate multiple heterogeneous robots in projects sponsored by NASA and the Defense Advanced Research Projects Agency (DARPA). It has also been used in Brazil to control an autonomous airship and in Canada to control a robotic manipulator.

Simmons, Reid↗
NASA NTRS2012

Supersonic Retropropulsion Technology Development in NASA's Entry, Descent, and Landing Project

NASA's Entry, Descent, and Landing (EDL) space technology roadmap calls for new technologies to achieve human exploration of Mars in the coming decades [1]. One of those technologies, termed Supersonic Retropropulsion (SRP), involves initiation of propulsive deceleration at supersonic Mach numbers. The potential benefits afforded by SRP to improve payload mass and landing precision make the technology attractive for future EDL missions. NASA's EDL project spent two years advancing the technological maturity of SRP for Mars exploration [2-15]. This paper summarizes the technical accomplishments from the project and highlights challenges and recommendations for future SRP technology development programs. These challenges include: developing sufficiently large SRP engines for use on human-scale entry systems; testing and computationally modelling complex and unsteady SRP fluid dynamics; understanding the effects of SRP on entry vehicle stability and controllability; and demonstrating sub-scale SRP entry systems in Earth's atmosphere.

Edquist, Karl T.↗
NASA NTRS2011

Frame Synchronization Without Attached Sync Markers

We describe a method to synchronize codeword frames without making use of attached synchronization markers (ASMs). Instead, the synchronizer identifies the code structure present in the received symbols, by operating the decoder for a handful of iterations at each possible symbol offset and forming an appropriate metric. This method is computationally more complex and doesn't perform as well as frame synchronizers that utilize an ASM; nevertheless, the new synchronizer acquires frame synchronization in about two seconds when using a 600 kbps software decoder, and would take about 15 milliseconds on prototype hardware. It also eliminates the need for the ASMs, which is an attractive feature for short uplink codes whose coding gain would be diminished by the overheard of ASM bits. The lack of ASMs also would simplify clock distribution for the AR4JA low-density parity-check (LDPC) codes and adds a small amount to the coding gain as well (up to 0.2 dB).

Hamkins, Jon↗
NASA NTRS2015

Tetrahedral-Mesh Simulation of Turbulent Flows with the Space-Time Conservative Schemes

Direct numerical simulations of turbulent flows are predominantly carried out using structured, hexahedral meshes despite decades of development in unstructured mesh methods. Tetrahedral meshes offer ease of mesh generation around complex geometries and the potential of an orientation free grid that would provide un-biased small-scale dissipation and more accurate intermediate scale solutions. However, due to the lack of consistent multi-dimensional numerical formulations in conventional schemes for triangular and tetrahedral meshes at the cell interfaces, numerical issues exist when flow discontinuities or stagnation regions are present. The space-time conservative conservation element solution element (CESE) method - due to its Riemann-solver-free shock capturing capabilities, non-dissipative baseline schemes, and flux conservation in time as well as space - has the potential to more accurately simulate turbulent flows using unstructured tetrahedral meshes. To pave the way towards accurate simulation of shock/turbulent boundary-layer interaction, a series of wave and shock interaction benchmark problems that increase in complexity, are computed in this paper with triangular/tetrahedral meshes. Preliminary computations for the normal shock/turbulence interactions are carried out with a relatively coarse mesh, by direct numerical simulations standards, in order to assess other effects such as boundary conditions and the necessity of a buffer domain. The results indicate that qualitative agreement with previous studies can be obtained for flows where, strong shocks co-exist along with unsteady waves that display a broad range of scales, with a relatively compact computational domain and less stringent requirements for grid clustering near the shock. With the space-time conservation properties, stable solutions without any spurious wave reflections can be obtained without a need for buffer domains near the outflow/farfield boundaries. Computational results for the isotropic turbulent flow decay, at a relatively high turbulent Mach number, show a nicely behaved spectral decay rate for medium to high wave numbers. The high-order CESE schemes offer very robust solutions even with the presence of strong shocks or widespread shocklets. The explicit formulation in conjunction with a close to unity theoretical upper Courant number bound has the potential to offer an efficient numerical framework for general compressible turbulent flow simulations with unstructured meshes.

Chang, Chau-Lyan↗
NASA NTRS2017

Applying Graph Theory to Problems in Air Traffic Management

Graph theory is used to investigate three different problems arising in air traffic management. First, using a polynomial reduction from a graph partitioning problem, it is shown that both the airspace sectorization problem and its incremental counterpart, the sector combination problem are NP-hard, in general, under several simple workload models. Second, using a polynomial time reduction from maximum independent set in graphs, it is shown that for any fixed e, the problem of finding a solution to the minimum delay scheduling problem in traffic flow management that is guaranteed to be within n1-e of the optimal, where n is the number of aircraft in the problem instance, is NP-hard. Finally, a problem arising in precision arrival scheduling is formulated and solved using graph reachability. These results demonstrate that graph theory provides a powerful framework for modeling, reasoning about, and devising algorithmic solutions to diverse problems arising in air traffic management.

precision arrival scheduling↗
NASA NTRS2017

Applying Graph Theory to Problems in Air Traffic Management

Graph theory is used to investigate three different problems arising in air traffic management. First, using a polynomial reduction from a graph partitioning problem, it isshown that both the airspace sectorization problem and its incremental counterpart, the sector combination problem are NP-hard, in general, under several simple workload models. Second, using a polynomial time reduction from maximum independent set in graphs, it is shown that for any fixed e, the problem of finding a solution to the minimum delay scheduling problem in traffic flow management that is guaranteed to be within n1-e of the optimal, where n is the number of aircraft in the problem instance, is NP-hard. Finally, a problem arising in precision arrival scheduling is formulated and solved using graph reachability. These results demonstrate that graph theory provides a powerful framework for modeling, reasoning about, and devising algorithmic solutions to diverse problems arising in air traffic management.

computational complexity↗
NASA NTRS2014

Cultivating an Emergent Earth Observation Analytics Ecosystem in the Cloud

A diverse set of data analytics systems for Earth Observations are sprouting up in the Earth Science community, with a wealth of processing algorithms and analysis methods. There is a similar wealth of data resources available via myriad data providers and clearinghouses, including large institutional systems like the Earth Observing System Data and Information System, Comprehensive Large Scale Array-data Stewardship System, and Federated Earth Observation Missions gateway. With Earth system science driving a need to work with more datasets together, and the community developing more analysis tools (some of them dataset-specific), how can we develop analysis workflows that incorporate far-flung datasets and leverage analysis resources from multiple organizations? Cloud computing points the way toward a solution in two different respects. Firstly, the access to and abstraction of virtually unlimited storage and computing power provides an environment that enables more straightforward means of pulling datasets and analysis resources together. Just as importantly, however, cloud computing serves as an example of an "ecosystem" of interoperating services, since the essence of cloud computing is the presentation of all resources as a service, from hardware to infrastructure to platform to software. This enables the combination of off-the-shelf, diverse services to construct entire systems that emerge out of an equally diverse community of architects and developers. This approach can be similarly applied to the data and analysis resources in the Earth Observation community. By exposing these resources via well understood services, and consuming resources in the same way, different organizations can construct bespoke analysis workflows and systems for their own purposes. The key leap the community needs to make is to develop analysis systems in components that interact with other components via services. The result would be a rich ecosystem of analytics components that can be combined to analyze datasets at scale and in conjunction with other datasets from other sources.

chaos↗
NASA NTRS2021

Progress in Scheduling Algorithms for a Collaborative Distributed System for Flight Planning

This Technical Memorandum describes four contributions made by the authors to a larger team effort toward developing a distributed system for scheduling commercial flights at navigation fixes and/or airport runways. These contributions are as follows: (1) a proof of correctness for a scheduling algorithm published previously by Meyn, (2) an improvement of Meyn's algorithm from quadratic to linear time, (3) two independent implementations of the algorithm with test results identical to those published, and (4) an extension of Meyn's algorithm to support minimum usable time intervals.

arrival scheduling↗
NASA NTRSDate not supplied

Formal Methods in the Development of Highly Assured Software for Unmanned Aircraft Systems

In traditional software development methodologies, operational and functional requirements of systems are often specified in structured natural language notations. These restricted notations provide good documentation support, but only provide limited support for semantic analysis. These notations are generally not rich enough to unambiguously specify the requirements of safety-critical systems that, for example, involve complex numerical computations or that interact with the physical environment. Examples of these safety-critical systems are autonomous vehicles such as unmanned aircraft systems. This talk advocates the use of expressive formal logics, such as higher-order logic, to specify the operational and functional requirement of unmanned systems and to prove the correctness of these requirements. Semantic analysis of requirements written in higher-order logic is supported through the use of interactive theorem provers. Formal models serve as ideal reference implementations of functional requirements. Hence, formal logics enable software validation techniques where software implementations can be checked against functional requirements in a mechanical way. The Formal Methods group in the Safety-Critical Avionics Systems Branch at NASA Langley Research Center has conducted research on the development and application of formal verification techniques to safety-critical applications of interest to NASA for more than 30 years. This talk illustrates the use of formal methods in the development of highly-assured autonomous unmanned aircraft systems.

Formal Methods↗
NASA NTRSDate not supplied

Automated Software for Crewed Spacecraft - Bridging the Gap from Sci Fi to Reality

With a voice command or a few taps on the console, the spacecraft pivots on a dime at high velocity and gently docks to an orbiting space platform. This is the image most people have of the complex software computations and integrated hardware performance necessary for a spacecraft to successfully perform an automated launch, rendezvous, and docking. Today’s reality is that while computer operations are advancing rapidly, science fiction over-simplifies and over-sells current capabilities. This paper discusses the integration of spacecraft computer automation into the operation of one of the United States’ new Commercial Crew vehicles - the Boeing CST-100 Starliner. Lessons learned by the Boeing Mission Operations team, a unique private-public partnership with NASA, from conceptual design through real-time operation of the first test flight will be discussed along with evolution of the system in preparation for the second uncrewed test flight. Focus will center on how operations has learned to use the automated software to their advantage while also knowing how to adjust the automation in response to spacecraft or mission anomalies.

Robert C. Dempsey↗
NASA NTRS2021

A permafrost implementation in the simple carbon-climate model Hector v.2.3.pf

Permafrost currently stores more than a fourth of global soil carbon. A warming climate makes this carbon increasingly vulnerable to decomposition and release into the atmosphere in the form of greenhouse gases. The resulting climate feedback can be estimated using land surface models, but the high complexity and computational cost of these models make it challenging to use them for estimating uncertainty, exploring novel scenarios, and coupling with other models. We have added a representation of permafrost to the simple, open-source global carbon–climate model Hector, calibrated to be consistent with both historical data and 21st century Earth system model projections of permafrost thaw. We include permafrost as a separate land carbon pool that becomes available for decomposition into both methane (CH4) and carbon dioxide (CO2) once thawed; the thaw rate is controlled by region-specific air temperature increases from a preindustrial baseline. We found that by 2100 thawed permafrost carbon emissions increased Hector’s atmospheric CO2 concentration by 5 %–7 % and the atmospheric CH4 concentration by 7 %–12 %, depending on the future scenario, resulting in 0.2–0.25 ∘C of additional warming over the 21st century. The fraction of thawed permafrost carbon available for decomposition was the most significant parameter controlling the end-of-century temperature change in the model, explaining around 70 % of the temperature variance, and was distantly followed by the initial stock of permafrost carbon, which contributed to about 10 % of the temperature variance. The addition of permafrost in Hector provides a basis for the exploration of a suite of science questions, as Hector can be cheaply run over a wide range of parameter values to explore uncertainty and can be easily coupled with integrated assessment and other human system models to explore the economic consequences of warming from this feedback.

Dawn L. Woodard↗
NASA NTRS2022

Radiation Effects Characterization and System Architecture Options for the 7nm Snapdragon SA8155P Automotive Grade System on Chip (SoC)

The SA8155P SoC is a complex heterogeneous computational platform with CPUs, GPU, DSPs and NPU. The SA8155P is a 7 TOPS/7 Watts capable AI/ML platform and as such represents a game changing breakthrough in terms computational power for space applications. We characterize the TID and SEE effects of the Qualcomm SA8155P Automotive grade SoC. Individual sub-system testing as well as application specific full device testing was conducted. We also discuss the commercial and automotive recovery mechanisms that are available with the SA8155P SoC generation and how those can form the basis for resilient architecture options for use in future space missions

Allen, Greg↗
DOE OSTI2025

Evaluating Direct and Indirect Influence on EV Charging Stations Across the US

The adoption of new technology for electric vehicles (EV) and mobility applications can bring underappreciated vulnerabilities to the power grid. One area of potential fraud and adversarial influence is through the business ecosystem of startups that own and deploy EV technology. Yet, there are no models or analyses that map the network of organizations and people that have direct and indirect influence over technologies currently deployed in the grid. To fill this gap, we develop a multilayer network model to measure direct and indirect influence on EV charging stations. First, we create and adversarial socio-technical network (ASTN) model via a data fusion pipeline for different US regions of interest (ROI). Then, we develop an integrated ASTN for Chicago, Los Angeles, New York, and Philadelphia. We rank EV charging companies direct influence within each geographic region as well as indirect influence via social network analysis. While some companies have strong direct and indirect influence (i.e., ChargePoint) others show a mismatch between their influence over charging stations and their position within the social network. For example, Tesla has strong direct influence on stations and weak indirect influence over competitors. In contrast, 7Charge has weak direct influence over stations, but strong indirect influence over competitors.

29 - ENERGY PLANNING, POLICY AND ECONOMY↗