Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “algorithmic efficiency”

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 1,189 records · Page 66

A generalized reusable guidance algorithm for optimal aerobraking

A practical real-time guidance algorithm was developed for guiding aerobraking vehicles in such a way that the maximum heating rate, the maximum structural loads, and the post-aeropass delta-V requirements (for post-aeropass orbit insertion) are all minimized. The algorithm is general and reusable in the sense that a minimum of assumptions are made, thus minimizing the number of gains and mission-dependent parameters that must be laboriously determined prior to a particular mission. A particularly interesting feature is that inplane guidance performance is tuned by simply adjusting one mission-dependent parameter, the bank margin; similarly, the out-of-plane guidance performance is turned by simply adjusting a plane controller time constant. Other objectives in the algorithm development are simplicity, efficiency, and ease of use. The algorithm is developed for, but not necessarily restricted to, a single pass mission and a trimmed vehicle with a bank angle modulation as the method of trajectory control. Guidance performance is demonstrated via results obtained using this algorithm integrated into an aerobraking test-bed program. Comparisons are made with numerical results from a version of the aerobraking guidance algorithm that was to be flown onboard NASA's aeroassist flight experiment (AFE) vehicle. Promising results are obtained with a minimum of development effort.

Dukeman, G. A.↗

An advancing front Delaunay triangulation algorithm designed for robustness

A new algorithm is described for generating an unstructured mesh about an arbitrary two-dimensional configuration. Mesh points are generated automatically by the algorithm in a manner which ensures a smooth variation of elements, and the resulting triangulation constitutes the Delaunay triangulation of these points. The algorithm combines the mathematical elegance and efficiency of Delaunay triangulation algorithms with the desirable point placement features, boundary integrity, and robustness traditionally associated with advancing-front-type mesh generation strategies. The method offers increased robustness over previous algorithms in that it cannot fail regardless of the initial boundary point distribution and the prescribed cell size distribution throughout the flow-field.

Mavriplis, D. J.↗

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

An advancing front Delaunay triangulation algorithm designed for robustness

A new algorithm is described for generating an unstructured mesh about an arbitrary two-dimensional configuration. Mesh points are generated automatically by the algorithm in a manner which ensures a smooth variation of elements, and the resulting triangulation constitutes the Delaunay triangulation of these points. The algorithm combines the mathematical elegance and efficiency of Delaunay triangulation algorithms with the desirable point placement features, boundary integrity, and robustness traditionally associated with advancing-front-type mesh generation strategies. The method offers increased robustness over previous algorithms in that it cannot fail regardless of the initial boundary point distribution and the prescribed cell size distribution throughout the flow-field.

Mavriplis, D. J.↗

Mathematical Foundation for Plane Covering Using Hexagons

This work is to indicate the development and mathematical underpinnings of the algorithms previously developed for covering the plane and the addressing of the elements of the covering. The algorithms are of interest in that they provides a simple systematic way of increasing or decreasing resolution, in the sense that if we have the covering in place and there is an image superimposed upon the covering, then we may view the image in a rough form or in a very detailed form with minimal effort. Such ability allows for quick searches of crude forms to determine a class in which to make a detailed search. In addition, the addressing algorithms provide an efficient way to process large data sets that have related subsets. The algorithms produced were based in part upon the work of D. Lucas "A Multiplication in N Space" which suggested a set of three vectors, any two of which would serve as a bases for the plane and also that the hexagon is the natural geometric object to be used in a covering with a suggested bases. The second portion is a refinement of the eyeball vision system, the globular viewer.

Johnson, Gordon G.↗

Algorithms and Application of Sparse Matrix Assembly and Equation Solvers for Aeroacoustics

An algorithm for symmetric sparse equation solutions on an unstructured grid is described. Efficient, sequential sparse algorithms for degree-of-freedom reordering, supernodes, symbolic/numerical factorization, and forward backward solution phases are reviewed. Three sparse algorithms for the generation and assembly of symmetric systems of matrix equations are presented. The accuracy and numerical performance of the sequential version of the sparse algorithms are evaluated over the frequency range of interest in a three-dimensional aeroacoustics application. Results show that the solver solutions are accurate using a discretization of 12 points per wavelength. Results also show that the first assembly algorithm is impractical for high-frequency noise calculations. The second and third assembly algorithms have nearly equal performance at low values of source frequencies, but at higher values of source frequencies the third algorithm saves CPU time and RAM. The CPU time and the RAM required by the second and third assembly algorithms are two orders of magnitude smaller than that required by the sparse equation solver. A sequential version of these sparse algorithms can, therefore, be conveniently incorporated into a substructuring for domain decomposition formulation to achieve parallel computation, where different substructures are handles by different parallel processors.

Watson, W. R.↗

An Efficient, Multi-Layered Crown Delineation Algorithm for Mapping Individual Tree Structure Across Multiple Ecosystems

Deriving individual tree information from discrete return, small footprint LiDAR data may improve forest above ground biomass estimates, and provide tree-level information that is important in many ecological studies. Several crown delineation algorithms have been developed to extract individual tree information from LiDAR point clouds or rasterized canopy height models (CHM), but many of these algorithms have difficulty discriminating between overlapping crowns, and also may fail to detect understory trees. Our approach uses a watershed based delineation of a CHM, which is subsequently refined using the LiDAR point cloud. Individual tree detection was validated with stem mapped field data from the Smithsonian Environmental Research Center (SERC), Maryland, and on a plot and stand level through comparisons of stem density and basal area to delineated metrics at both SERC and a study area in the Sierra Nevada, California. For individual tree detection, the algorithm correctly identified 70% of dominant trees, 58% of co-dominant trees, 35% of intermediate trees and 21% of suppressed trees at SERC. The algorithm had difficulty distinguishing between crowns of small, dense understory trees of approximately the same height. Delineated crown volume alone explained 53% and 84% of the variability in basal area at the SERC and Sierra Nevada sites, respectively. The algorithm produced crown area distributions comparable to diameter at breast height (DBH) size class distributions observed in the field in both study sites. The algorithm detected understory crowns better in the conifer-dominated Sierra Nevada site than in the closed-canopy deciduous site in Maryland. The ability for the algorithm to reproduce both accurate tree size distributions and individual crown geometries in two dissimilar and complex forests suggests great promise for applicability to a wide range of forest systems.

LiDAR↗

An Efficient, FPGA-Based, Cluster Detection Algorithm Implementation for a Strip Detector Readout System in a Time Projection Chamber Polarimeter

A fundamental challenge in a spaceborne application of a gas-based Time Projection Chamber (TPC) for observation of X-ray polarization is handling the large amount of data collected. The TPC polarimeter described uses the APV-25 Application Specific Integrated Circuit (ASIC) to readout a strip detector. Two dimensional photoelectron track images are created with a time projection technique and used to determine the polarization of the incident X-rays. The detector produces a 128x30 pixel image per photon interaction with each pixel registering 12 bits of collected charge. This creates challenging requirements for data storage and downlink bandwidth with only a modest incidence of photons and can have a significant impact on the overall mission cost. An approach is described for locating and isolating the photoelectron track within the detector image, yielding a much smaller data product, typically between 8x8 pixels and 20x20 pixels. This approach is implemented using a Microsemi RT-ProASIC3-3000 Field-Programmable Gate Array (FPGA), clocked at 20 MHz and utilizing 10.7k logic gates (14% of FPGA), 20 Block RAMs (17% of FPGA), and no external RAM. Results will be presented, demonstrating successful photoelectron track cluster detection with minimal impact to detector dead-time.

Polarimeter↗

Comparison of First-Come First-Served and Optimization Based Scheduling Algorithms for Integrated Departure and Arrival Management

Korea Aerospace Research Institute (KARI) and National Aeronautics and Space Administration (NASA) are investigating scheduling algorithms that will be a part of an integrated arrival and departure management system. Inha University, one of the Korean collaborators of KARI, developed an Extended First-Come First-Served (EFCFS) algorithm that is robust and efficient. However, since the EFCFS algorithm sequentially computes the schedule based on priority, the end results may not be optimal for system efficiency. The approach based on Mixed Integer Linear Programming (MILP) originally developed by NASA and modified by KARI is known to produce better schedules at the expense of computational cost. In this paper, the two different scheduling approaches are compared using common traffic scenarios and constraints at Incheon International Airport. Capabilities to apply weight class based wake turbulence runway separation minima and Miles-in-Trail (MIT) restrictions at selected meter fixes are added to the previously developed EFCFS scheduler. Based on historic data, 40 departures and 20 arrivals are chosen in a one-hour period and 100 scenarios were created by randomly assigning gate numbers, gate departure times, and runway landing times. With the current runway separation requirements, MILP resulted in about ten to twenty percent smaller average delays depending on the constraints. With artificially increased separation minima, the difference between MILP and EFCFS became more noticeable. However, the EFCFS was about ten times faster with smaller variations among different scenarios and constraints. The comparison suggests that the MILP-based algorithm has a small advantage at the current traffic level; however, has potential to be more effective in higher demand or severe weather situations. The EFCFS algorithm may be better suited for real-time applications or investigating larger scale scheduling problems.

air traffic optimization↗

A robust and efficient stepwise regression method for building sparse polynomial chaos expansions

Polynomial Chaos (PC) expansions are widely used in various engineering fields for quantifying uncertainties arising from uncertain parameters. The computational cost of classical PC solution schemes is unaffordable as the number of deterministic simulations to be calculated grows dramatically with the number of stochastic dimension. This considerably restricts the practical use of PC at the industrial level. A common approach to address such problems is to make use of sparse PC expansions. This paper presents a non-intrusive regression-based method for building sparse PC expansions. The most important PC contributions are detected sequentially through an automatic search procedure. The variable selection criterion is based on efficient tools relevant to probabilistic method. Two benchmark analytical functions are used to validate the proposed algorithm. The computational efficiency of the method is then illustrated by a more realistic CFD application, consisting of the non-deterministic flow around a transonic airfoil subject to geometrical uncertainties. To assess the performance of the developed methodology, a detailed comparison is made with the well established LAR-based selection technique. The results show that the developed sparse regression technique is able to identify the most significant PC contributions describing the problem. Moreover, the most important stochastic features are captured at a reduced computational cost compared to the LAR method. The results also demonstrate the superior robustness of the method by repeating the analyses using random experimental designs.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

Performance of the rigorous renormalization group for first-order phase transitions and topological phases

Expanding and improving the repertoire of numerical methods for studying quantum lattice models is an ongoing focus in many-body physics. While the density matrix renormalization group (DMRG) has been established as a practically useful algorithm for finding the ground state in one-dimensional systems, a provably efficient and accurate algorithm remained elusive until the introduction of the rigorous renormalization group (RRG) by Landau [Nat. Phys. 11, 566 (2015)1745-247310.1038/nphys3345]. In this paper, we study the accuracy and performance of a numerical implementation of RRG at first-order phase transitions and in symmetry-protected topological phases. Our study is motivated by the question of when RRG might provide a useful complement to the more established DMRG technique. In particular, despite its general utility, DMRG can give unreliable results near first-order phase transitions and in topological phases, since its local update procedure can fail to adequately explore (near-)degenerate manifolds. Furthermore, the rigorous theoretical underpinnings of RRG, meanwhile, suggest that it should not suffer from the same difficulties. We show this optimism is justified, and that RRG indeed determines well-ordered, accurate energies even when DMRG does not. Moreover, our performance analysis indicates that in certain circumstances seeding DMRG with states determined by coarse runs of RRG may provide an advantage over simply performing DMRG.

75 CONDENSED MATTER PHYSICS, SUPERCONDUCTIVITY AND↗

On-board attitude determination for the Explorer Platform satellite

This paper describes the attitude determination algorithm for the Explorer Platform satellite. The algorithm, which is baselined on the Landsat code, is a six-element linear quadratic state estimation processor, in the form of a Kalman filter augmented by an adaptive filter process. Improvements to the original Landsat algorithm were required to meet mission pointing requirements. These consisted of a more efficient sensor processing algorithm and the addition of an adaptive filter which acts as a check on the Kalman filter during satellite slew maneuvers. A 1750A processor will be flown on board the satellite for the first time as a coprocessor (COP) in addition to the NASA Standard Spacecraft Computer. The attitude determination algorithm, which will be resident in the COP's memory, will make full use of its improved processing capabilities to meet mission requirements. Additional benefits were gained by writing the attitude determination code in Ada.

Jayaraman, C.↗

UAV Path Planning for Wildfires - Sustainably Fighting Wildfires with Automated Path Planning for UAVs

As the severity and frequency of wildfires increase, infrastructure, properties, national parks, animal habitats, and human lives (civilians and firefighters) are put at greater risk. This paper examines the possible application of algorithmic path planning for UAV reconnaissance to reduce damage and safety risks, as aforementioned. When the location of a wildfire is known, UAVs are immediately dispatched from an operating base to fly to the fire and support the firefighters as quickly as possible. Then, the algorithm incrementally analyzes different environmental factors to create a path for the UAV to follow. This work focuses on generating a path for the UAV to follow given a set of polygons representing obstacles. The most important features of this algorithm are its fast response time and obstacle maneuverability. The use of an efficient path planning algorithm could potentially save lives, infrastructure, and acres of forest destruction.

UAV↗

The FADE mass-stat: A technique for inserting or deleting particles in molecular dynamics simulations

The emergence of new applications of molecular dynamics (MD) simulation calls for the development of mass-statting procedures that insert or delete particles on-the-fly. In this paper we present a new mass-stat which we term FADE, because it gradually “fades-in” (inserts) or “fades-out” (deletes) molecules over a short relaxation period within a MD simulation. FADE applies a time-weighted relaxation to the intermolecular pair forces between the inserting/deleting molecule and any neighbouring molecules. The weighting function we propose in this paper is a piece-wise polynomial that can be described entirely by two parameters: the relaxation time scale and the order of the polynomial. FADE inherently conserves overall system momentum independent of the form of the weighting function. We demonstrate various simulations of insertions of atomic argon, polyatomic TIP4P water, polymer strands, and C{sub 60} Buckminsterfullerene molecules. We propose FADE parameters and a maximum density variation per insertion-instance that restricts spurious potential energy changes entering the system within desired tolerances. We also demonstrate in this paper that FADE compares very well to an existing insertion algorithm called USHER, in terms of accuracy, insertion rate (in dense fluids), and computational efficiency. The USHER algorithm is applicable to monatomic and water molecules only, but we demonstrate that FADE can be generally applied to various forms and sizes of molecules, such as polymeric molecules of long aspect ratio, and spherical carbon fullerenes with hollow interiors.

37 INORGANIC, ORGANIC, PHYSICAL, AND ANALYTICAL CH↗

An h-adaptive mesh method for Boltzmann-BGK/hydrodynamics coupling

We introduce a coupled method for hydrodynamic and kinetic equations on 2-dimensional h-adaptive meshes. We adopt the Euler equations with a fast kinetic solver in the region near thermodynamical equilibrium, while use the Boltzmann-BGK equation in kinetic regions where fluids are far from equilibrium. A buffer zone is created around the kinetic regions, on which a gradually varying numerical flux is adopted. Based on the property of a continuously discretized cut-off function which describes how the flux varies, the coupling will be conservative. In order for the conservative 2-dimensional specularly reflective boundary condition to be implemented conveniently, the discrete Maxwellian is approximated by a high order continuous formula with improved accuracy on a disc instead of on a square domain. The h-adaptive method can work smoothly with a time-split numerical scheme. Through h-adaptation, the cell number is greatly reduced. This method is particularly suitable for problems with hydrodynamics breakdown on only a small part of the whole domain, so that the total efficiency of the algorithm can be greatly improved. Three numerical examples are presented to validate the proposed method and demonstrate its efficiency.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

Comparison of Planning Quality and Efficiency Between Conventional and Knowledge-based Algorithms in Nasopharyngeal Cancer Patients Using Intensity Modulated Radiation Therapy

Purpose: Intensity modulated radiation therapy (IMRT) is widely used to achieve a highly conformal dose and improve treatment outcome. However, plan quality and planning time are institute and planner dependent, and no standardized tool exists to recognize an optimal plan. RapidPlan, a knowledge-based algorithm, can generate constraints to assist optimization and produce high-quality IMRT plans. This report evaluated the quality and efficiency of using RapidPlan in nasopharyngeal carcinoma (NPC) IMRT planning. Methods and Materials: RapidPlan was configured using 79 radical IMRT plans for NPC; 20 consecutive NPC patients indicated for radical radiation therapy between October 2014 and May 2015 were then recruited to assess its performance. The ability of RapidPlan to produce acceptable plans was evaluated. For plans that could not achieve clinical acceptance, manual touch-up was performed. The IMRT plans produced without RapidPlan (manual plans) and with RapidPlan (RP-2 plans, including those with manual touch-up) were compared in terms of dosimetric quality and planning efficiency. Results: RapidPlan by itself could produce clinically acceptable plans for 9 of the 20 patients; manual touch-up increased the number of acceptable plans (RP-2 plans) to 19. The target dose coverage and conformity were very similar. No difference was found in the maximum dose to the brainstem and optic chiasm. RP-2 plans delivered a higher maximum dose to the spinal cord (46.4 Gy vs 43.9 Gy, P=.002) but a lower dose to the parotid (mean dose to right parotid, 37.3 Gy vs 45.4 Gy; left, 34.4 Gy vs 43.1 Gy; P<.001) and the right cochlea (mean dose, 48.6 Gy vs 52.6 Gy; P=.02). The total planning time for RP-2 plans was significantly less than that for manual plans (64 minutes vs 295 minutes, P<.001). Conclusions: This study shows that RapidPlan can significantly improve planning efficiency and produce quality IMRT plans for NPC patients.

62 RADIOLOGY AND NUCLEAR MEDICINE↗

Reducing Earth Topography Resolution for SMAP Mission Ground Tracks Using K-Means Clustering

The K-means clustering algorithm is used to reduce Earth topography resolution for the SMAP mission ground tracks. As SMAP propagates in orbit, knowledge of the radar antenna footprints on Earth is required for the antenna misalignment calibration. Each antenna footprint contains a latitude and longitude location pair on the Earth surface. There are 400 pairs in one data set for the calibration model. It is computationally expensive to calculate corresponding Earth elevation for these data pairs. Thus, the antenna footprint resolution is reduced. Similar topographical data pairs are grouped together with the K-means clustering algorithm. The resolution is reduced to the mean of each topographical cluster called the cluster centroid. The corresponding Earth elevation for each cluster centroid is assigned to the entire group. Results show that 400 data points are reduced to 60 while still maintaining algorithm performance and computational efficiency. In this work, sensitivity analysis is also performed to show a trade-off between algorithm performance versus computational efficiency as the number of cluster centroids and algorithm iterations are increased.

ground tracks↗