Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “augmenting path”

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 19 records

Computing Maximum Cardinality Matchings in Parallel on Bipartite Graphs via Tree-Grafting

It is difficult to obtain high performance when computing matchings on parallel processors because matching algorithms explicitly or implicitly search for paths in the graph, and when these paths become long, there is little concurrency. In spite of this limitation, we present a new algorithm and its shared-memory parallelization that achieves good performance and scalability in computing maximum cardinality matchings in bipartite graphs. This algorithm searches for augmenting paths via specialized breadth-first searches (BFS) from multiple source vertices, hence creating more parallelism than single source algorithms. Algorithms that employ multiple-source searches cannot discard a search tree once no augmenting path is discovered from the tree, unlike algorithms that rely on single-source searches. We describe a novel tree-grafting method that eliminates most of the redundant edge traversals resulting from this property of multiple-source searches. We also employ the recent direction-optimizing BFS algorithm as a subroutine to discover augmenting paths faster. Our algorithm compares favorably with the current best algorithms in terms of the number of edges traversed, the average augmenting path length, and the number of iterations. Here, we provide a proof of correctness for our algorithm. Our NUMA-aware implementation is scalable to 80 threads of an Intel multiprocessor and to 240 threads on an Intel Knights Corner coprocessor. On average, our parallel algorithm runs an order of magnitude faster than the fastest algorithms available. The performance improvement is more significant on graphs with small matching number.

97 MATHEMATICS AND COMPUTING↗

Methodology for Augmenting Existing Paths with Additional Parallel Transects: Visual Sample Plan

Visual Sample Plan (VSP) is sample planning software that is used, among other purposes, to plan transect sampling paths to detect areas that were potentially used for munition training. This module was developed for application on a large site where existing roads and trails were to be used as primary sampling paths. Gap areas between these primary paths needed to found and covered with parallel transect paths. These gap areas represent areas on the site that are more than a specified distance from a primary path. These added parallel paths needed to optionally be connected together into a single path—the shortest path possible. The paths also needed to optionally be attached to existing primary paths, again with the shortest possible path. Finally, the process must be repeatable and predictable so that the same inputs (primary paths, specified distance, and path options) will result in the same set of new paths every time. This methodology was developed to meet those specifications.

54 ENVIRONMENTAL SCIENCES↗

The development of advanced automatic flare and decrab for powered lift short haul aircraft using a microwave landing system

Advanced automatic flare and decrab control laws were developed for future powered lift STOL aircraft using the NASA-C-8A augmentor wing vehicle as the aircraft model. The longitudinal control laws utilize the throttle for flight path control and use the direct lift augmentor flap chokes for flight path augmentation. The elevator is used to control airspeed during the approach phase and to enhance path control during the flare. The forward slip maneuver was selected over the flat decrab technique for runway alignment because it can effectively handle the large crab angles obtained at STOL approach speeds. Performance evaluation of selected system configurations were obtained over the total landing environment. Limitations were defined and critical failure modes assessed. Pilot display concepts are discussed.

Gevaert, G.↗

Multithreaded Algorithms for Maximum Matching in Bipartite Graphs

Abstract—We design, implement, and evaluate algorithms for computing a matching of maximum cardinality in a bipartite graph on multi-core and massively multithreaded computers. As computers with larger number of slower cores dominate the commodity processor market, the design of multithreaded algorithms to solve large matching problems becomes a necessity. Recent work on serial algorithms based on searching for augmenting paths for this problem have shown that their performance is sensitive to the order in which the vertices are processed for matching. In a multithreaded environment, imposing a serial order in which vertices are considered for matching would lead to loss of concurrency and performance. But this raises the question: Would parallel matching algorithms on multithreaded machines improve performance over a serial algorithm? We answer this question in the affirmative. We report efficient multithreaded implementations of two key algorithms (Hopcroft- Karp based on breadth-first-search, and Pothen-Fan based on depth-first-search) and their variants, combined with the Karp- Sipser initialization algorithm. We report extensive results and insights using three shared-memory platforms (a 48-core AMD Opteron, a 32-core Intel Nehalem, and a 128-processor Cray XMT) on a representative set of real-world and synthetic graphs. To the best of our knowledge, this is the first extensive study of augmentation-based parallel algorithms for bipartite cardinality matching.

Azad, Md Ariful↗

Parallel Maximum Cardinality Matchings via Tree-Grafting

This software implements a new algorithm and its shared-memory parallelization for computing maximum cardinality matchings in bipartite graphs. The algorithm searches for augmenting paths via specialized breadth-first searches (BFS) from multiple source vertices, hence creating more parallelism than single source algorithms.

Buluc, Aydin↗

Path-Based Dictionary Augmentation: A Framework for Improving $k$ -Sparse Image Processing

In this study, we have previously shown that augmenting orthogonal matching pursuit (OMP) with an additional step in the identification stage of each pursuit iteration yields improved $k$ -sparse reconstruction and denoising performance relative to baseline OMP. At each iteration a “path” or geodesic, is generated between the two dictionary atoms that are most correlated with the residual and from this path a new atom that has a greater correlation to the residual than either of the two bracketing atoms is selected. Here, we provide new computational results illustrating improvements in sparse coding and denoising on canonical datasets using both learned and structured dictionaries. The two methods of constructing a path are investigated for each dictionary type: the Euclidean geodesic formed by a linear combination of the two atoms and the 2-Wasserstein geodesic corresponding to the optimal transport map between the atoms. We prove here the existence of a higher-correlation atom in the Euclidean case under assumptions on the two bracketing atoms and introduce algorithmic modifications to improve the likelihood that the bracketing atoms meet those conditions. Although, we demonstrate our augmentation on OMP alone, in general it may be applied to any reconstruction algorithm that relies on the selection and sorting of high-similarity atoms during an analysis or identification phase.

97 MATHEMATICS AND COMPUTING↗

On Parallel Push-Relabel based Algorithms for Bipartite Maximum Matching

We study multithreaded push-relabel based algorithms for computing maximum cardinality matching in bipartite graphs. Matching is a fundamental combinatorial (graph) problem with applications in a wide variety of problems in science and engineering. We are motivated by its use in the context of sparse linear solvers for computing maximum transversal of a matrix. We implement and test our algorithms on several multi-socket multicore systems and compare their performance to state-of-the-art augmenting path-based serial and parallel algorithms using a testset comprised of a wide range of real-world instances. Building on several heuristics for enhancing performance, we demonstrate good scaling for the parallel push-relabel algorithm. We show that it is comparable to the best augmenting path-based algorithms for bipartite matching. To the best of our knowledge, this is the first extensive study of multithreaded push-relabel based algorithms. In addition to a direct impact on the applications using matching, the proposed algorithmic techniques can be extended to preflow-push based algorithms for computing maximum flow in graphs.

Push-relabel, matching, bipartite↗

A program-management plan with critical-path definition for Combustion Augmentation with Thermionic Energy Conversion (CATEC)

Thermionic energy conversion (TEC) is discussed. In recent TEC-topping analyses, overall plant efficiency (OPE) and cost of electricity (COE) improved slightly with current capabilities and substantially with fully matured technologies. Enhanced credibility derives from proven hot-corrosion protection for TEC by silicon-carbide clads in fossil fuel combustion products. Combustion augmentation with TEC (CATEC) affords minimal cost and plant perturbation, but with smaller OPE and COE improvements than more conventional topping applications. Risk minimization as well as comparative simplicity and convenience, favor CATEC for early market penetration. A program-management plan is proposed. Inputs, characteristics, outputs and capabilities are discussed.

Morris, J. F.↗

Global centroid moment tensor solutions in a heterogeneous earth: the CMT3D catalogue

SUMMARY For over 40 yr, the global centroid-moment tensor (GCMT) project has determined location and source parameters for globally recorded earthquakes larger than magnitude 5.0. The GCMT database remains a trusted staple for the geophysical community. Its point-source moment-tensor solutions are the result of inversions that model long-period observed seismic waveforms via normal-mode summation for a 1-D reference earth model, augmented by path corrections to capture 3-D variations in surface wave phase speeds, and to account for crustal structure. While this methodology remains essentially unchanged for the ongoing GCMT catalogue, source inversions based on waveform modelling in low-resolution 3-D earth models have revealed small but persistent biases in the standard modelling approach. Keeping pace with the increased capacity and demands of global tomography requires a revised catalogue of centroid-moment tensors (CMT), automatically and reproducibly computed using Green's functions from a state-of-the-art 3-D earth model. In this paper, we modify the current procedure for the full-waveform inversion of seismic traces for the six moment-tensor parameters, centroid latitude, longitude, depth and centroid time of global earthquakes. We take the GCMT solutions as a point of departure but update them to account for the effects of a heterogeneous earth, using the global 3-D wave speed model GLAD-M25. We generate synthetic seismograms from Green's functions computed by the spectral-element method in the 3-D model, select observed seismic data and remove their instrument response, process synthetic and observed data, select segments of observed and synthetic data based on similarity, and invert for new model parameters of the earthquake’s centroid location, time and moment tensor. The events in our new, preliminary database containing 9382 global event solutions, called CMT3D for ‘3-D centroid-moment tensors’, are on average 4 km shallower, about 1 s earlier, about 5 per cent larger in scalar moment, and more double-couple in nature than in the GCMT catalogue. We discuss in detail the geographical and statistical distributions of the updated solutions, and place them in the context of earlier work. We plan to disseminate our CMT3D solutions via the online ShakeMovie platform.

58 GEOSCIENCES↗

Status of Sundstrand research

Wind shear detection status is presented in the form of view-graphs. The following subject areas are covered: second generation detection (Q-bias, gamma bias, temperature biases, maneuvering flight modulation, and altitude modulation); third generation wind shear detection (use wind shear computation to augment flight path and terrain alerts, modulation of alert thresholds based on wind/terrain data base, incorporate wind shear/terrain alert enhancements from predictive sensor data); and future research and development.

Bateman, Don↗

Simulator evaluation of the flying qualities of externally blown flap and augmentor wing transport configurations

Concurrent simulations of powered-lift STOL transport aircraft having either an externally blown flap configuration or an augmentor wing configuration were conducted. The following types of simulators of varying sophistication were used: (1) a simple fixed-base simulation with a simple visual display, (2) a more complex fixed-base simulation using a realistic transport cockpit and a high-quality visual display, and (3) a six-degree-of-freedom motion simulator that had a realistic transport cockpit and a sophisticated visual display. The unaugmented flying qualities determined from these simulations were rated as unacceptable for both the externally blown flap and augmentor wing configurations. The longitudinal, lateral-directional, and single-engine-failure characteristics were rated satisfactory with extensive augmentation, including pitch and roll command systems, flight-path (or speed) augmentation, turn coordination, and effective yaw damping. However, the flare and landing characteristics from any approach glide-path angle in excess of 4 deg were rated as unsatisfactory but acceptable.

Kier, D. A.↗

Flight evaluation of an integrated control and display system for high-precision manual landing flare of powered-lift STOL aircraft

An account is given of the features and performance of a manual landing flare and touchdown system capable of great precision, as demonstrated by its installation in the NASA Quiet Short-haul Research Aircraft (QSRA). The integrated cockpit display and closed-loop control employed constitutes a trajectory-augmentation system that extends QSRA flight control from augmentation of altitude, flight path angle, and airspeed, to the augmentation of the trajectory itself. The + or - 18 ft touchdown dispersion achieved is approximately equal to that obtained during aircraft carrier trials of the same aircraft.

Hynes, Charles S.↗

Space Shuttle flying qualities and flight control system assessment

This paper reviews issues, data, and analyses relevant to the longitudinal flying qualities of the Space Shuttle in approach and landing. The manual control of attitude and path are first examined theoretically to demonstrate the unconventional nature of the Shuttle's augmented pitch and path response characteristics. The time domain pitch rate transient response criterion used for design of the Shuttle flight control system is examined in context with data from recent flying qualities experiments and operational aircraft. Questions arising from this examination are addressed through comparisons with MIL-F-8785C and other proposed flying qualities criteria which indicate potential longitudinal flying qualities problems. However, it is shown that these criteria, based largely on data from conventional aircraft, may be inappropriate for assessing the Shuttle.

Myers, T. T.↗

Secure information transmission in filter bank multi-carrier spread spectrum systems

This report discusses the issue of secure information transmission for a spread-spectrum system, which in our case is Filter-Bank Multi-Carrier spread spectrum (FB-MC SS). We develop a novel method for generating a secret key to augment the security of the spread spectrum system. The proposed key generation takes advantage of the channel reciprocity exhibited between two communicating parties.We validate the key generation aspect of our system by using real-world measurements. It is found that our augmentation of strongest path cancellation (SPC) is shown to be highly effective in our measurement scenarios where the adversary’s key would otherwise be significantly correlated with the legitimate nodes. Our approach in using the proposed key generation method as a part of FB-MC SS allows for it to be fault tolerant and it is not necessarily limited to FB-MC SS or spread-spectrum system in general. However, the advantage that our approach has in the domain of spread-spectrum security is that it significantly decorrelates the adversary’s key from the authentic parties. This aspect is crucial because if the adversary’s key is similar to the legitamate parties, then the adversary obtains a sizable advantage due to the fault tolerance nature of the developed spread spectrum key.

45 MILITARY TECHNOLOGY, WEAPONRY, AND NATIONAL DEF↗

Fault Tolerant Key Generation and Secure Spread Spectrum Communication

This study presents a secure information transmission system compromised of two main parts. The first component makes use of the principle of reciprocity in frequency-selective wireless channels to derive a pair of keys for two legitimate parties. The proposed key generation algorithm allows for two asynchronous transceivers to derive a pair of similar keys. Moreover, we apply a unique augmentation - called strongest path cancellation (SPC) - to the keys and have validated through simulation and real-world measurements that this technique significantly boosts the security level of the overall design. In the second part of the secure information transmission system, we introduce the concept of artificial noise to multi-carrier spread-spectrum (MC-SS) systems. The keys generated in the first part are used as spreading code sequences for MC-SS and artificial noise is added to further enhance the security of this communication setup. Two different attacks on our proposed system are evaluated. First, a passive adversary who follows the exact same steps as the legitimate users to detect confidential information is considered. In the second attack, we evaluate the design in presence of an adversary with significant blind detection capabilities.

99 GENERAL AND MISCELLANEOUS↗

Symbology Development for General Aviation Synthetic Vision Primary Flight Displays for the Approach and Missed-Approach Modes of Flight

Spatial disorientation induced by inadvertent flight into instrument meteorological conditions (IMC) continues to be a leading cause of fatal accidents in general aviation. The Synthetic Vision Systems General Aviation (SVS-GA) research element, an integral part of NASA s Aviation Safety and Security Program (AvSSP), is investigating a revolutionary display technology designed to mitigate low visibility events such as controlled flight into terrain (CFIT) and low-visibility loss of control (LVLoC). The integrated SVS Primary Flight Display (SVS-PFD) utilizes computer generated 3-dimensional imagery of the surrounding terrain augmented with flight path guidance symbology. This unique combination will provide GA pilots with an accurate representation of their environment and projection of their flight path, regardless of time of day or out-the-window (OTW) visibility. The initial Symbology Development for Head-Down Displays (SD-HDD) simulation experiment examined 16 display configurations on a centrally located high-resolution PFD installed in NASA s General Aviation Work Station (GAWS) flight simulator. The results of the experiment indicate that situation awareness (SA) can be enhanced without having a negative impact on flight technical error (FTE), by providing a general aviation pilot with an integrated SVS display to use when OTW visibility is obscured.

Bartolone, Anthony P.↗

Multiplier-continuation algorthms for constrained optimization

Several path following algorithms based on the combination of three smooth penalty functions, the quadratic penalty for equality constraints and the quadratic loss and log barrier for inequality constraints, their modern counterparts, augmented Lagrangian or multiplier methods, sequential quadratic programming, and predictor-corrector continuation are described. In the first phase of this methodology, one minimizes the unconstrained or linearly constrained penalty function or augmented Lagrangian. A homotopy path generated from the functions is then followed to optimality using efficient predictor-corrector continuation methods. The continuation steps are asymptotic to those taken by sequential quadratic programming which can be used in the final steps. Numerical test results show the method to be efficient, robust, and a competitive alternative to sequential quadratic programming.

Lundberg, Bruce N.↗