Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “Np”

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 181 records · Page 10
All sourcesNASA NTRSDOE OSTI
NASA NTRS1997

Sequential Test Strategies for Multiple Fault Isolation

In this paper, we consider the problem of constructing near optimal test sequencing algorithms for diagnosing multiple faults in redundant (fault-tolerant) systems. The computational complexity of solving the optimal multiple-fault isolation problem is super-exponential, that is, it is much more difficult than the single-fault isolation problem, which, by itself, is NP-hard. By employing concepts from information theory and Lagrangian relaxation, we present several static and dynamic (on-line or interactive) test sequencing algorithms for the multiple fault isolation problem that provide a trade-off between the degree of suboptimality and computational complexity. Furthermore, we present novel diagnostic strategies that generate a static diagnostic directed graph (digraph), instead of a static diagnostic tree, for multiple fault diagnosis. Using this approach, the storage complexity of the overall diagnostic strategy reduces substantially. Computational results based on real-world systems indicate that the size of a static multiple fault strategy is strictly related to the structure of the system, and that the use of an on-line multiple fault strategy can diagnose faults in systems with as many as 10,000 failure sources.

Shakeri, M.↗
NASA NTRS1997

Sequential Testing Algorithms for Multiple Fault Diagnosis

In this paper, we consider the problem of constructing optimal and near-optimal test sequencing algorithms for multiple fault diagnosis. The computational complexity of solving the optimal multiple-fault isolation problem is super-exponential, that is, it is much more difficult than the single-fault isolation problem, which, by itself, is NP-hard. By employing concepts from information theory and AND/OR graph search, we present several test sequencing algorithms for the multiple fault isolation problem. These algorithms provide a trade-off between the degree of suboptimality and computational complexity. Furthermore, we present novel diagnostic strategies that generate a diagnostic directed graph (digraph), instead of a diagnostic tree, for multiple fault diagnosis. Using this approach, the storage complexity of the overall diagnostic strategy reduces substantially. The algorithms developed herein have been successfully applied to several real-world systems. Computational results indicate that the size of a multiple fault strategy is strictly related to the structure of the system.

Shakeri, Mojdeh↗
NASA NTRS1997

Algorithms for Multiple Fault Diagnosis With Unreliable Tests

In this paper, we consider the problem of constructing optimal and near-optimal multiple fault diagnosis (MFD) in bipartite systems with unreliable (imperfect) tests. It is known that exact computation of conditional probabilities for multiple fault diagnosis is NP-hard. The novel feature of our diagnostic algorithms is the use of Lagrangian relaxation and subgradient optimization methods to provide: (1) near optimal solutions for the MFD problem, and (2) upper bounds for an optimal branch-and-bound algorithm. The proposed method is illustrated using several examples. Computational results indicate that: (1) our algorithm has superior computational performance to the existing algorithms (approximately three orders of magnitude improvement), (2) the near optimal algorithm generates the most likely candidates with a very high accuracy, and (3) our algorithm can find the most likely candidates in systems with as many as 1000 faults.

Shakeri, Mojdeh↗
NASA NTRS1998

Data Understanding Applied to Optimization

The goal of this research is to explore and develop software for supporting visualization and data analysis of search and optimization. Optimization is an ever-present problem in science. The theory of NP-completeness implies that the problems can only be resolved by increasingly smarter problem specific knowledge, possibly for use in some general purpose algorithms. Visualization and data analysis offers an opportunity to accelerate our understanding of key computational bottlenecks in optimization and to automatically tune aspects of the computation for specific problems. We will prototype systems to demonstrate how data understanding can be successfully applied to problems characteristic of NASA's key science optimization tasks, such as central tasks for parallel processing, spacecraft scheduling, and data transmission from a remote satellite.

Buntine, Wray↗
NASA NTRS1999

Spectral Behavior of Hematite at Visible/Near Infrared and Midinfrared Wavelengths

The oxide mineral hematite alpha-Fe2O3) is present on Mars as evidenced by spectroscopy using visible/near infrared (VNIR) and midinfrared (MIR) wavelengths. The physical nature of this surficial hematite varies from fine-grained, crystalline red hematite (red-Hm) in certain martian bright regions, to coarser-grained, crystalline gray hematite (gray-Hm) in the Sinus Meridiani equatorial site discovered in the Mars Global Surveyor Thermal Emission Spectrometer (MGS-TES) data. The VNIR spectra require that the red hematite is present in amounts subordinate to a second ferric pigment, which accounts for the general shape and position of the martian ferric absorption edge. By analogy with palagonitic tephra and synthetic samples, the pigment is a nanophase ferric oxide, possibly nanophase hematite (np-Hm). The purpose of this abstract is to document the physicospectral properties of hematite in the VNIR (0.35 to 2.2 microns) and MIR (5 to 25 microns) with respect to the terms "nanophase" and "crystalline", "red" and "gray", and "fine-grained" and "coarse-grained". We will show that different "types" of hematite (no-, red-, and gray-Hm) have different spectral responses in the VNIR and MIR regions and that these differences are important for inferring the types of hematite and their relative proportions from remotely sensed spectra of Mars. Because hematite is an alteration product that forms through many different geologic processes, determination of the type of hematite provides important clues about the style and diversity of martian weathering processes.

Lane, Melissa D.↗
NASA NTRS2000

Nebular Hydrogen Absorption in the Ejecta of Eta Carinae

Space Telescope Imaging Spectrograph (STIS) observations of Eta Carinae and immediate ejecta reveal narrow Balmer absorption lines in addition to the nebular-scattered broad P-Cygni absorptions. The narrow absorption correlates with apparent disk structure that separates the two Homunculus lobes. We trace these features about half way up the Northern lobe until the scattered stellar Balmer line doppler-shifts redward beyond the nebular absorption feature. Three-dimensional data cubes, made by mapping the Homunculus at Balmer alpha and Balmer beta with the 52 x 0.1 arcsecond aperture and about 5000 spectral resolving power, demonstrate that the absorption feature changes slowly in velocity with nebular position. We have monitored the stellar Balmer alpha line profile of the central source over the past four years. The equivalent width of the nebular absorption feature changes considerably between observations. The changes do not correlate with measured brightness of Eta Carinae. Likely clumps of neutral hydrogen with a scale size comparable to the stellar disk diameter are passing through the intervening light path on the timescales less than several months. The excitation mechanism involves Lyman alpha radiation (possibly the Lyman series plus Lyman continuum) and collisions leading to populating the 2S metastable state. Before the electron can jump to the ground state by two photon emission (lifetime about 1/8 second), a stellar Balmer photon is absorbed and the electron shifts to an NP level. We see the absorption feature in higher Balmer lines, and but not in Paschen lines. Indeed we see narrow nebular Paschen emission lines. At present, we do not completely understand the details of the absorption. Better understanding should lead to improved insight of the unique conditions around Eta Carinae that leads to these absorptions.

Gull, Theodore R.↗
NASA NTRS2001

Temporal Constraint Reasoning With Preferences

A number of reasoning problems involving the manipulation of temporal information can naturally be viewed as implicitly inducing an ordering of potential local decisions involving time (specifically, associated with durations or orderings of events) on the basis of preferences. For example. a pair of events might be constrained to occur in a certain order, and, in addition. it might be preferable that the delay between them be as large, or as small, as possible. This paper explores problems in which a set of temporal constraints is specified, where each constraint is associated with preference criteria for making local decisions about the events involved in the constraint, and a reasoner must infer a complete solution to the problem such that, to the extent possible, these local preferences are met in the best way. A constraint framework for reasoning about time is generalized to allow for preferences over event distances and durations, and we study the complexity of solving problems in the resulting formalism. It is shown that while in general such problems are NP-hard, some restrictions on the shape of the preference functions, and on the structure of the preference set, can be enforced to achieve tractability. In these cases, a simple generalization of a single-source shortest path algorithm can be used to compute a globally preferred solution in polynomial time.

Khatib, Lina↗
NASA NTRS2001

Survey of Header Compression Techniques

This report provides a summary of several different header compression techniques. The different techniques included are: (1) Van Jacobson's header compression (RFC 1144); (2) SCPS (Space Communications Protocol Standards) header compression (SCPS-TP, SCPS-NP); (3) Robust header compression (ROHC); and (4) The header compression techniques in RFC2507 and RFC2508. The methodology for compression and error correction for these schemes are described in the remainder of this document. All of the header compression schemes support compression over simplex links, provided that the end receiver has some means of sending data back to the sender. However, if that return path does not exist, then neither Van Jacobson's nor SCPS can be used, since both rely on TCP (Transmission Control Protocol). In addition, under link conditions of low delay and low error, all of the schemes perform as expected. However, based on the methodology of the schemes, each scheme is likely to behave differently as conditions degrade. Van Jacobson's header compression relies heavily on the TCP retransmission timer and would suffer an increase in loss propagation should the link possess a high delay and/or bit error rate (BER). The SCPS header compression scheme protects against high delay environments by avoiding delta encoding between packets. Thus, loss propagation is avoided. However, SCPS is still affected by an increased BER (bit-error-rate) since the lack of delta encoding results in larger header sizes. Next, the schemes found in RFC2507 and RFC2508 perform well for non-TCP connections in poor conditions. RFC2507 performance with TCP connections is improved by various techniques over Van Jacobson's, but still suffers a performance hit with poor link properties. Also, RFC2507 offers the ability to send TCP data without delta encoding, similar to what SCPS offers. ROHC is similar to the previous two schemes, but adds additional CRCs (cyclic redundancy check) into headers and improves compression schemes which provide better tolerances in conditions with a high BER.

Ishac, Joseph↗
NASA NTRS1994

The Algorithm Selection Problem

Work on NP-hard problems has shown that many instances of these theoretically computationally difficult problems are quite easy. The field has also shown that choosing the right algorithm for the problem can have a profound effect on the time needed to find a solution. However, to date there has been little work showing how to select the right algorithm for solving any particular problem. The paper refers to this as the algorithm selection problem. It describes some of the aspects that make this problem difficult, as well as proposes a technique for addressing it.

Minton, Steve↗
NASA NTRS2002

Number Partitioning via Quantum Adiabatic Computation

We study both analytically and numerically the complexity of the adiabatic quantum evolution algorithm applied to random instances of combinatorial optimization problems. We use as an example the NP-complete set partition problem and obtain an asymptotic expression for the minimal gap separating the ground and exited states of a system during the execution of the algorithm. We show that for computationally hard problem instances the size of the minimal gap scales exponentially with the problem size. This result is in qualitative agreement with the direct numerical simulation of the algorithm for small instances of the set partition problem. We describe the statistical properties of the optimization problem that are responsible for the exponential behavior of the algorithm.

Smelyanskiy, Vadim N.↗
NASA NTRS2002

Dynamics of Quantum Adiabatic Evolution Algorithm for Number Partitioning

We have developed a general technique to study the dynamics of the quantum adiabatic evolution algorithm applied to random combinatorial optimization problems in the asymptotic limit of large problem size n. We use as an example the NP-complete Number Partitioning problem and map the algorithm dynamics to that of an auxiliary quantum spin glass system with the slowly varying Hamiltonian. We use a Green function method to obtain the adiabatic eigenstates and the minimum exitation gap, gmin = O(n2(sup -n/2)), corresponding to the exponential complexity of the algorithm for Number Partitioning. The key element of the analysis is the conditional energy distribution computed for the set of all spin configurations generated from a given (ancestor) configuration by simultaneous flipping of a fixed number of spins. For the problem in question this distribution is shown to depend on the ancestor spin configuration only via a certain parameter related to the energy of the configuration. As the result, the algorithm dynamics can be described in terms of one-dimensional quantum diffusion in the energy space. This effect provides a general limitation of a quantum adiabatic computation in random optimization problems. Analytical results are in agreement with the numerical simulation of the algorithm.

Smelyanskiy, Vadius↗
NASA NTRS1997

The X-Ray Spectrum of the Supernova Remnant 1E 0102-72.3

In this letter we present the soft X-ray (5-35A) spectrum of the supernova remnant (SNR) IE 0102-72.3 in the Small Magellanic Cloud, acquired by the reflection grating spectrometer (RGS) aboard ESA's XMM-Newton Observatory. This extended-source X-ray spectrum of unprecedented spectral resolution (lambda/Delta(lambda) approx. 300) permits, for the first time, unabiguous identification and measurement of isolated emission lines and line complexes alike. The diagnostic power of performing spectroscopy using groups of emission lines from single ions is exemplified. In particular, the bright Lyman and helium series lines for light elements (C VI, O VII, O VIII, Ne IX, Ne X and possibly Mg XI & Mg XII) show peculiar ratios, where the values [1s - np] / [1s - (n + l)p] are systematically weaker than expected for electron impact excitation. These measured ratios resemble signatures of recombining or charge exchanging plasmas. We argue that charge exchange, given its large cross section and evidence for inhomogeneous media within the SNR, is a likely mechanism for the observed emission. Also. the well known temperature diagnostics G(T(sub e)) = (i + f)/r of helium- like triplets (O VII & Ne IX) indicate high temperatures, well above the maximum emission temperature T(sub m) for each ion, and consistent with a purely ionizing plasma. The density diagnostics R(n(sub e)) = f / i meanwhile, are consistent with the low density limit, as expected.

Rasmussen, Andrew P.↗
NASA NTRS2003

On the Critical Behaviour, Crossover Point and Complexity of the Exact Cover Problem

Research into quantum algorithms for NP-complete problems has rekindled interest in the detailed study a broad class of combinatorial problems. A recent paper applied the quantum adiabatic evolution algorithm to the Exact Cover problem for 3-sets (EC3), and provided an empirical evidence that the algorithm was polynomial. In this paper we provide a detailed study of the characteristics of the exact cover problem. We present the annealing approximation applied to EC3, which gives an over-estimate of the phase transition point. We also identify empirically the phase transition point. We also study the complexity of two classical algorithms on this problem: Davis-Putnam and Simulated Annealing. For these algorithms, EC3 is significantly easier than 3-SAT.

Morris, Robin D.↗
NASA NTRS2002

Dynamics of Quantum Adiabatic Evolution Algorithm for Number Partitioning

We have developed a general technique to study the dynamics of the quantum adiabatic evolution algorithm applied to random combinatorial optimization problems in the asymptotic limit of large problem size n. We use as an example the NP-complete Number Partitioning problem and map the algorithm dynamics to that of an auxiliary quantum spin glass system with the slowly varying Hamiltonian. We use a Green function method to obtain the adiabatic eigenstates and the minimum excitation gap. g min, = O(n 2(exp -n/2), corresponding to the exponential complexity of the algorithm for Number Partitioning. The key element of the analysis is the conditional energy distribution computed for the set of all spin configurations generated from a given (ancestor) configuration by simultaneous flipping of a fixed number of spins. For the problem in question this distribution is shown to depend on the ancestor spin configuration only via a certain parameter related to 'the energy of the configuration. As the result, the algorithm dynamics can be described in terms of one-dimensional quantum diffusion in the energy space. This effect provides a general limitation of a quantum adiabatic computation in random optimization problems. Analytical results are in agreement with the numerical simulation of the algorithm.

Smelyanskiy, V. N.↗
NASA NTRS2003

Hydrothermal Alteration on Basaltic Mauna Kea Volcano as a Template for Identification of Hydrothermal Alteration on Basaltic Mars

Certain samples of palagonitic tephra from Mauna Kea Volcano (Hawaii) are spectral analogues for bright martian surface materials at visible and near-IR wavelengths because both are characterized by a ferric absorption edge extending from about 400 to 750 nm and relatively constant reflectivity extending from about 750 nm to beyond 2000 nm. Palagonite is a yellow or orange isotropic mineraloid formed by hydration and devitrification of basaltic glass. For Mars-analogue palagonite, the pigment is nanometersized ferric oxide particles (np-Ox) dispersed throughout an allophane-like hydrated basaltic glass matrix. Crystalline phyllosilicates are not generally detected, and the hydration state of the is not known. The poorly crystalline nature of glass alteration products implies relatively low temperature formation pathways. We report here x-ray diffraction, major element, Mossbauer, and VNIR data for 9 basaltic tephras. Thermal emission spectra are reported in a separate abstract. Our multidisciplinary approach both tightly constrains mineralogical interpretations and maximizes overlap with datasets available for the martian surface available now and in the future.

Morris, R. V.↗
NASA NTRS2003

Scheduling in the Face of Uncertain Resource Consumption and Utility

We discuss the problem of scheduling tasks that consume uncertain amounts of a resource with known capacity and where the tasks have uncertain utility. In these circumstances, we would like to find schedules that exceed a lower bound on the expected utility when executed. We show that the problems are NP- complete, and present some results that characterize the behavior of some simple heuristics over a variety of problem classes.

Frank, Jeremy↗
NASA NTRS2004

Random Matrix Approach to Quantum Adiabatic Evolution Algorithms

We analyze the power of quantum adiabatic evolution algorithms (Q-QA) for solving random NP-hard optimization problems within a theoretical framework based on the random matrix theory (RMT). We present two types of the driven RMT models. In the first model, the driving Hamiltonian is represented by Brownian motion in the matrix space. We use the Brownian motion model to obtain a description of multiple avoided crossing phenomena. We show that the failure mechanism of the QAA is due to the interaction of the ground state with the "cloud" formed by all the excited states, confirming that in the driven RMT models. the Landau-Zener mechanism of dissipation is not important. We show that the QAEA has a finite probability of success in a certain range of parameters. implying the polynomial complexity of the algorithm. The second model corresponds to the standard QAEA with the problem Hamiltonian taken from the Gaussian Unitary RMT ensemble (GUE). We show that the level dynamics in this model can be mapped onto the dynamics in the Brownian motion model. However, the driven RMT model always leads to the exponential complexity of the algorithm due to the presence of the long-range intertemporal correlations of the eigenvalues. Our results indicate that the weakness of effective transitions is the leading effect that can make the Markovian type QAEA successful.

Boulatov, Alexei↗
NASA NTRS1999

Aeroelastic Analysis of the NASA/ARMY/MIT Active Twist Rotor

Aeroelastic modeling procedures used in the design of a piezoelectric controllable twist helicopter rotor wind tunnel model are described. Two aeroelastic analysis methods developed for active twist rotor studies, and used in the design of the model blade, are described in this paper. The first procedure uses a simple flap-torsion dynamic representation of the active twist blade, and is intended for rapid and efficient control law and design optimization studies. The second technique employs a commercially available comprehensive rotor analysis package, and is used for more detailed analytical studies. Analytical predictions of hovering flight twist actuation frequency responses are presented for both techniques. Forward flight fixed system nP vibration suppression capabilities of the model active twist rotor system are also presented. Frequency responses predicted using both analytical procedures agree qualitatively for all design cases considered, with best correlation for cases where uniform blade properties are assumed.

Wilkie, W. Keats↗