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 1,243 records · Page 69
All sourcesNASA NTRSDOE OSTI
NASA NTRS1992

Generating effective project scheduling heuristics by abstraction and reconstitution

A project scheduling problem consists of a finite set of jobs, each with fixed integer duration, requiring one or more resources such as personnel or equipment, and each subject to a set of precedence relations, which specify allowable job orderings, and a set of mutual exclusion relations, which specify jobs that cannot overlap. No job can be interrupted once started. The objective is to minimize project duration. This objective arises in nearly every large construction project--from software to hardware to buildings. Because such project scheduling problems are NP-hard, they are typically solved by branch-and-bound algorithms. In these algorithms, lower-bound duration estimates (admissible heuristics) are used to improve efficiency. One way to obtain an admissible heuristic is to remove (abstract) all resources and mutual exclusion constraints and then obtain the minimal project duration for the abstracted problem; this minimal duration is the admissible heuristic. Although such abstracted problems can be solved efficiently, they yield inaccurate admissible heuristics precisely because those constraints that are central to solving the original problem are abstracted. This paper describes a method to reconstitute the abstracted constraints back into the solution to the abstracted problem while maintaining efficiency, thereby generating better admissible heuristics. Our results suggest that reconstitution can make good admissible heuristics even better.

Janakiraman, Bhaskar↗
NASA NTRS1993

Isomorphic routing on a toroidal mesh

We study a routing problem that arises on SIMD parallel architectures whose communication network forms a toroidal mesh. We assume there exists a set of k message descriptors (xi, yi), where (xi, yi) indicates that the ith message's recipient is offset from its sender by xi hops in one mesh dimension, and yi hops in the other. Every processor has k messages to send, and all processors use the same set of message routing descriptors. The SIMD constraint implies that at any routing step, every processor is actively routing messages with the same descriptors as any other processor. We call this isomorphic routing. Our objective is to find the isomorphic routing schedule with least makespan. We consider a number of variations on the problem, yielding complexity results from O(k) to NP-complete. Most of our results follow after we transform the problem into a scheduling problem, where it is related to other well-known scheduling problems.

Mao, Weizhen↗
NASA NTRS1993

Nuclear Propulsion Technical Interchange Meeting, volume 1

The Nuclear Propulsion Technical Interchange Meeting (NP-TIM-92) was sponsored and hosted by the Nuclear Propulsion Office at the NASA Lewis Research Center. The purpose of the meeting was to review the work performed in fiscal year 1992 in the areas of nuclear thermal and nuclear electric propulsion technology development. These proceedings are a compilation of the presentations given at the meeting (many of the papers are presented in outline or viewgraph form). Volume 1 covers the introductory presentations and the system concepts and technology developments related to nuclear thermal propulsion.

Source record↗
NASA NTRS1992

Inference in fuzzy rule bases with conflicting evidence

Inference based on fuzzy 'If ... then' rules has played a very important role since when Zadeh proposed the Compositional Rule of Inference and, especially, since the first successful application presented by Mamdani. From the mid-1980's when the 'fuzzy boom' started in Japan, numerous industrial applications appeared, all using simplified techniques because of the high levels of computational complexity. Another feature is that antecedents in the rules are distributed densely in the input space, so the conclusion can be calculated by some weighted combination of the consequents of the matching (fired) rules. The CRI works in the following way: If R is a rule and A* is an observation, the conclusion is computed by B* = R o A* (o stands for the max-min composition). Algorithms implementing this idea directly have an exponential time complexity (maybe the problem is NP-hard) as the rules are relations in X x Y, a k1 x k2 dimensional space, if X is k1, Y is k2 dimensional. The simplified techniques usually decompose the relation into k1 projections in X(sub i) and measure in some way the degree of similarity between observation and antecedent by some parameter of the overlapping. These parameters are aggregated to a single value in (0,1) which is applied as a resulting weight for the given rule. The projections of rules in dimensions Y(sub i) are weighted by these aggregated values and then they are combined in order to obtain a resulting conclusion separately in every dimension. This method is unapplicable with sparse bases as there is no guarantee that an arbitrary observation matches with any of the antecedents. Then, the degree of similarity is 0 and all consequents are weighted by 0. Some considerations for such a situation are summarized in the next sections.

Koczy, Laszlo T.↗
NASA NTRS1991

mu analysis with real parametric uncertainty

The authors give a broad overview, from a LFT (linear fractional transformation)/mu perspective, of some of the theoretical and practical issues associated with robustness in the presence of real parametric uncertainty, with a focus on computation. Recent results on the properties of mu in the mixed case are reviewed, including issues of NP completeness, continuity, computation of bounds, the equivalence of mu and its bounds, and some direct comparisons with Kharitonov-type analysis methods. In addition, some advances in the computational aspects of the problem, including a novel branch and bound algorithm, are briefly presented together with numerical results. The results suggest that while the mixed mu problem may have inherently combinatoric worst-case behavior, practical algorithms with modest computational requirements can be developed for problems of medium size (less than 100 parameters) that are of engineering interest.

Young, Peter M.↗
NASA NTRS1992

Traffic routing for multicomputer networks with virtual cut-through capability

Consideration is given to the problem of selecting routes for interprocess communication in a network with virtual cut-through capability, while balancing the network load and minimizing the number of times that a message gets buffered. An approach is proposed that formulates the route selection problem as a minimization problem with a link cost function that depends upon the traffic through the link. The form of this cost function is derived using the probability of establishing a virtual cut-through route. The route selection problem is shown to be NP-hard, and an algorithm is developed to incrementally reduce the cost by rerouting the traffic. The performance of this algorithm is exemplified by two network topologies: the hypercube and the C-wrapped hexagonal mesh.

Kandlur, Dilip D.↗
NASA NTRS1992

Site partitioning for distributed redundant disk arrays

Distributed redundant disk arrays can be used in a distributed computing system or database system to provide recovery in the presence of temporary and permanent failures of single sites. In this paper, we look at the problem of partitioning the sites into redundant arrays in such way that the communication costs for maintaining the parity information are minimized. We show that the partitioning problem is NP-complete and we propose two heuristic algorithms for finding approximate solutions.

Mourad, Antoine N.↗
NASA NTRS1987

NASA Position Classification Handbook

The NASA Position Classification Handbook provides: a concise unitary reference document covering most aspects of position classification within NASA, information regarding the characteristics of NASA's own position classification program--the NASA Supplemental Classification System--and its origins, information concerning responsibilities of various levels of NASA management for position classification, and information concerning overall operation of a classification program. The provisions of this handbook pertain to the position classification function agency-wide. Although it will be particularly useful to personnel specialists, it also can serve as a convenient reference on position classification for line managers and supervisors and administrative personnel who deal with personnel management matters. Recommendations or questions concerning the content of this handbook should be directed to Director, Personnel Programs Division (Code NP), NASA Headquarters.

Source record↗
NASA NTRS1994

Hematite formed from pyroxene on Mars by meteoritic impact

In earlier work, we showed using Mossbauer data that the mineralogy of iron-bearing phases in impact melt rocks from Manicouagan Crater (Quebec, Canada) is to a first approximation hematite and pyroxene. The visible and near-IR reflectivity data for these impact melt rocks show a continuous trend in band position from approximately 850 to approximately 1000 nm, which corresponds to the positions for the hematite and pyroxene endmembers, respectively. The oxidation is thought to occur shortly after the impact when oxidizing vapors and/or solutions reacted with the impact melt which was below its solidus temperature but still relatively hot. The reflectance data have important implications for Mars because band positions which occur between approximately 850 and 1000 nm bands observed for Mars can be attributed to hematite-pyroxene assemblages and not necessarily to different ferric mineralogy. Because oxidation of impact melt rocks at Manicouagan is thought to occur subsolidus, precursors for the hematite include oxides such as magnetite and ilmenite and silicates such as pyroxene and olivine. To determine if the Manicouagan impact-melt rocks are related to each other by simple thermal subsolidus oxidation, we calcined in air a relatively unoxidized Manicouagan impact-melt rock (MAN-74-608A). Previous work has shown that np-Hm (nanophase hematite) particles can be derived by calcination of iron-bearing silicates.

Morris, Richard V.↗
NASA NTRS1994

Aligning parallel arrays to reduce communication

Axis and stride alignment is an important optimization in compiling data-parallel programs for distributed-memory machines. We previously developed an optimal algorithm for aligning array expressions. Here, we examine alignment for more general program graphs. We show that optimal alignment is NP-complete in this setting, so we study heuristic methods. This paper makes two contributions. First, we show how local graph transformations can reduce the size of the problem significantly without changing the best solution. This allows more complex and effective heuristics to be used. Second, we give a heuristic that can explore the space of possible solutions in a number of ways. We show that some of these strategies can give better solutions than a simple greedy approach proposed earlier. Our algorithms have been implemented; we present experimental results showing their effect on the performance of some example programs running on the CM-5.

Sheffler, Thomas J.↗
NASA NTRS1995

Numerical Study of Contaminant Effects on Combustion of Hydrogen, Ethane, and Methane in Air

A numerical study was performed to assess the effects of vitiated air on the chemical kinetics of hydrogen, ethane, and methane combustion with air. A series of calculations in static reacting systems was performed, where the initial temperature was specified and reactions occurred at constant pressure. Three different types of test flow contaminants were considered: NP, H2O, and a combustion of H2O and CO2. These contaminants are present in the test flows of facilities used for hypersonic propulsion testing. The results were computed using a detailed reaction mechanism and are presented in terms of ignition and reaction times. Calculations were made for a wide range of contaminant concentrations, temperatures and pressures. The results indicate a pronounced kinetic effect over a range of temperatures, especially with NO contamination and, to a lesser degree, with H2O contamination. In all cases studied, CO2 remained kinetically inert, but had a thermodynamic effect on results by acting as a third body. The largest effect is observed with combustion using hydrogen fuel, less effect is seen with combustion of ethane, and little effect of contaminants is shown with methane combustion.

Lai, H. T.↗
NASA NTRS1994

Orbital velocities induced by surface waves

During the third intensive observational period of the Surface Wave Dynamics Experiment (SWADE), an aircraft-based experiment was conducted on 5 March 1991 by deploying slow-fall airborne expendable current profilers (AXCPs) and airborne expendable bathythermographs (AXBTs) during a scanning radar altimeter (SRA) flight on the NASA NP-3A research aircraft. As the Gulf Stream (GS) moved into the SWADE domain in late February, maximum upper-layer currents of 1.98 m/s were observed in the core of the baroclinic jet where the vertical current shears were O(10(exp -2)/s). The SRA concurrently measured the sea surface topography, which was transformed into two-dimensional directional wave spectra at 5-6-km intervals along the flight tracks. The wave spectra indicated a local wave field with wavelengths of 40-60 m propagating southward between 120 deg and 180 deg, and a northward-moving swell field from 300 deg to 70 deg associated with significant wave heights of 2-4 m. As the AXCP descended through the upper ocean, the profiler sensed orbital velocity amplitudes of 0.2-0.5 m/s due to low-frequency surface waves. These orbital velocities were isolated by fitting the observed current profiles to the three-layer model based on a monochromatic surface wave, including the steady and current shear terms within each layer. The depth-integrated differences between the observed and modeled velocity profiles were typically less than 3 cm/s. For 17 of the 21 AXCP drop sites, the rms orbital velocity amplitudes, estimated by integrating the wave spectra over direction and frequency, were correlated at a level of 0.61 with those derived from the current profiles. The direction of wave propagation inferred from the AXCP-derived orbital velocities was in the same direction observed by the SRA. These mean wave directions were highly correlated (0.87) and differed only by about 5 deg.

Shay, Lynn K.↗
NASA NTRS1993

The nanosphere iron mineral(s) in Mars soil

A series of surface-modified clays containing nanophase (np) iron/oxyhydroxides of extremely small particle sizes, with total iron contents as high as found in Mars soil, were prepared by iron deposition on the clay surface from ferrous chloride solution. Comprehensive studies of the iron mineralogy in these 'Mars-soil analogs' were conducted using chemical extractions, solubility analyses, pH and redox, x ray and electron diffractometry, electron microscopic imaging specific surface area and particle size determinations, differential thermal analyses, magnetic properties characterization, spectral reflectance, and Viking biology simulation experiments. The clay matrix and the procedure used for synthesis produced nanophase iron oxides containing a certain proportion of divalent iron, which slowly converts to more stable, fully oxidized iron minerals. The noncrystalline nature of the iron compounds precipitated on the surface of the clay was verified by their complete extractability in oxalate. Lepidocrocite (gamma-FeOOH) was detected by selected area electron diffraction. It is formed from a double iron Fe(II)/Fe(III) hydroxyl mineral such as 'green rust', or ferrosic hydroxide. Magnetic measurements suggested that lepidocrocite converted to the more stable meaghemite (gamma-Fe203) by mild heat treatment and then to nanophase hematite (aplha-Fe203) by extensive heat treatment. Their chemical reactivity offers a plausible mechanism for the somewhat puzzling observations of the Viking biology experiments. Their unique chemical reactivities are attributed to the combined catalytic effects of the iron oxide/oxyhydroxide and silicate phase surfaces. The mode of formation of these (nanophase) iron oxides on Mars is still unknown.

Banin, A.↗
NASA NTRS1994

Observations of the far ultraviolet airflow by the Ultraviolet Limb Imaging experiment on STS-39

The Ultraviolet Limb Imaging (UVLIM) experiment flew on STS-39 in the spring of 1991 to observe the Earth's thermospheric airglow and included a far ultraviolet (1080-1800 A) spectrometer. We present first results from this spectrometer, including a spectroscopic analysis at 6-A resolution of H, O, N, and N2 dayglow emissions and modeling of the observed limb-scan profiles of dayglow emissions. The observed N2 Lyman-Birge-Hopfield (LBH) emission reflects a vibrational population distribution in the a(1 Pi)(sub g) state that differs significantly from those predicted for direct electron excitation and excitation with cascade from the a('1 Sigma)(sub u)(-) and w(1 Delta)(sub u) states. The vibrational population distribution and LBH brightness suggest a total cascade rate 45% that of direct excitation, in contrast to laboratory measurements. For the first time, pronounced limb brightening is observed in both the N I lambda 1200 limb emission profiles, as expected for emissions excited by N2 dissociation which produces kinetically fast N fragments; however, optically thick components of these features are also observed. Preliminary modeling of the OI lambda 1356, HI lambda 1216, and OI lambda 1304 and OI lambda 1641 emissions agrees to within roughly 10% of the observed limb-scan profiles, but the models underestimate the N2 LBH profiles by a factor of 1.4-1.6, consistent with the inferred cascade effect. Other findings include: an OI lambda 1152/lambda 1356 intensity ratio that is inconsistent with the large cascade contribution to OI lambda 1356 from np 5P states required by laboratory and nightglow observations; nightglow observations of the tropical ultraviolet arcs exhibit a wide range of OI lambda 1356/lambda 1304 intensity ratios and illustrate the complicated observing geometry and radiative transfer effects that must be modeled; and we find a 3-sigma upper limit of 8.5 R to the total LBH vehicle glow emission.

Budzien, S. A.↗
NASA NTRS1992

Alterations in Skeletal Muscle Microcirculation of Head-Down Tilted Rats

In this study we assessed the function of microscopic blood vessels in skeletal muscle (cremaster muscle) for alterations which may contribute to the observed elevation of blood pressure associated with head-down tilted whole body suspension (HDT/WBS), a model of weightlessness. Arteriolar baseline diameters, vasoconstrictor responses to norepinephrine (NE) and vasodilation to nitroprusside (NP) were assessed in control rats, rats suspended for 7 or 14 day HDT/WBS rats, and rats allowed to recover for 1 day after 7 days HDT/WBS. Neither baseline diameters nor ability to dilate were influenced by HDT/WBS. Maximum vasoconstriction to norepinephrine was significantly greater in arterioles of hypertensive 14 day HDT/WBS rats. This first study of the intact microvasculature in skeletal muscle indicates that an elevated contractility of arterioles to norepinephrine in suspended rats, and suggests an elevated peripheral resistance in striated muscle may contribute to the increase in blood pressures among animals subjected to HDT/WBS.

Musacchia, X. J.↗
NASA NTRS1992

Reformulating Non-Monotonic Theories for Inference and Updating

We aim to help build programs that do large-scale, expressive non-monotonic reasoning (NMR): especially, 'learning agents' that store, and revise, a body of conclusions while continually acquiring new, possibly defeasible, premise beliefs. Currently available procedures for forward inference and belief revision are exhaustive, and thus impractical: they compute the entire non-monotonic theory, then re-compute from scratch upon updating with new axioms. These methods are thus badly intractable. In most theories of interest, even backward reasoning is combinatoric (at least NP-hard). Here, we give theoretical results for prioritized circumscription that show how to reformulate default theories so as to make forward inference be selective, as well as concurrent; and to restrict belief revision to a part of the theory. We elaborate a detailed divide-and-conquer strategy. We develop concepts of structure in NM theories, by showing how to reformulate them in a particular fashion: to be conjunctively decomposed into a collection of smaller 'part' theories. We identify two well-behaved special cases that are easily recognized in terms of syntactic properties: disjoint appearances of predicates, and disjoint appearances of individuals (terms). As part of this, we also definitionally reformulate the global axioms, one by one, in addition to applying decomposition. We identify a broad class of prioritized default theories, generalizing default inheritance, for which our results especially bear fruit. For this asocially monadic class, decomposition permits reasoning to be localized to individuals (ground terms), and reduced to propositional. Our reformulation methods are implementable in polynomial time, and apply to several other NM formalisms beyond circumscription.

Grosof, Benjamin N.↗
NASA NTRS1996

Algorithms for Automatic Alignment of Arrays

Aggregate data objects (such as arrays) are distributed across the processor memories when compiling a data-parallel language for a distributed-memory machine. The mapping determines the amount of communication needed to bring operands of parallel operations into alignment with each other. A common approach is to break the mapping into two stages: an alignment that maps all the objects to an abstract template, followed by a distribution that maps the template to the processors. This paper describes algorithms for solving the various facets of the alignment problem: axis and stride alignment, static and mobile offset alignment, and replication labeling. We show that optimal axis and stride alignment is NP-complete for general program graphs, and give a heuristic method that can explore the space of possible solutions in a number of ways. We show that some of these strategies can give better solutions than a simple greedy approach proposed earlier. We also show how local graph contractions can reduce the size of the problem significantly without changing the best solution. This allows more complex and effective heuristics to be used. We show how to model the static offset alignment problem using linear programming, and we show that loop-dependent mobile offset alignment is sometimes necessary for optimum performance. We describe an algorithm with for determining mobile alignments for objects within do loops. We also identify situations in which replicated alignment is either required by the program itself or can be used to improve performance. We describe an algorithm based on network flow that replicates objects so as to minimize the total amount of broadcast communication in replication.

Chatterjee, Siddhartha↗
NASA NTRS1995

Interdecadal Variations in the Alaska Gyre

Climatic dynamic topography variations in the Alaska gyre during the period 1968-1990 are described with an objective analysis of more than 12000 STD and XBT stations, and COADS wind stress data Interannual the dynamic height and SST variations were correlated and were consistent with recently described large-scale climatic shifts in the North Pacific. The gyre was centered more to the east, circulation appeared stronger, and SST was lower during the early to mid-1970s than during the 1980s. The Aleutian low (NP and PNA indices) intensified during the interim, but the response did not appear as a gyre spinup. Instead, the associated wind stress anomalies forced a slowly varying dynamic height anomaly across the eastern and northern part of the gyre through Ekman convergence, which had the effect of displacing the gyre's low somewhat to the WSW in the 1980s. The wind curl spectrum was white, and the slow oceanic response was modeled as stochastic-forced climate variability with a simple first-order Markov autoregression process. Forcing was assumed to be Ekman pumping of the pycnocline, and the damping coefficient was estimated from the data to be approx. 1 yr. A hindcast with observed winds gave estimated dynamic height patterns similar to those observed, with a canonical correlation of 0.79 at 99% confidence. This response was weak in the western half of the gyre, where slow baroclinic variability may have been influenced by long Rossby wave propagation. A simple autoregression simulation using artificial white noise forcing shows the evolution of decadal variations similar in nature to those observed. This result, along with the low frequency correlation between dynamic height and SST, suggests that the upper-ocean climatic variability in this region is primarily wind forced.

Lagerloef, Gary S.E.↗