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 199 records · Page 11
All sourcesNASA NTRSDOE OSTI
NASA NTRS2003

Iterative pass optimization of sequence data

The problem of determining the minimum-cost hypothetical ancestral sequences for a given cladogram is known to be NP-complete. This "tree alignment" problem has motivated the considerable effort placed in multiple sequence alignment procedures. Wheeler in 1996 proposed a heuristic method, direct optimization, to calculate cladogram costs without the intervention of multiple sequence alignment. This method, though more efficient in time and more effective in cladogram length than many alignment-based procedures, greedily optimizes nodes based on descendent information only. In their proposal of an exact multiple alignment solution, Sankoff et al. in 1976 described a heuristic procedure--the iterative improvement method--to create alignments at internal nodes by solving a series of median problems. The combination of a three-sequence direct optimization with iterative improvement and a branch-length-based cladogram cost procedure, provides an algorithm that frequently results in superior (i.e., lower) cladogram costs. This iterative pass optimization is both computation and memory intensive, but economies can be made to reduce this burden. An example in arthropod systematics is discussed. c2003 The Willi Hennig Society. Published by Elsevier Science (USA). All rights reserved.

NASA Discipline Evolutionary Biology↗
NASA NTRS2002

Haemodynamic changes during neck pressure and suction in seated and supine positions

We sought to quantify the contribution of cardiac output (Q) and total vascular conductance (TVC) to carotid baroreflex-mediated changes in mean arterial pressure (MAP) in the upright seated and supine positions. Acute changes in carotid sinus transmural pressure were evoked using brief 5 s pulses of neck pressure and neck suction (NP/NS) via a simplified paired neck chamber that was developed to enable beat-to-beat measurements of stroke volume using pulse-doppler ultrasound. Percentage contributions of Q and TVC were achieved by calculating the predicted change in MAP during carotid baroreflex stimulation if only the individual changes in Q or TVC occurred and all other parameters remained at control values. All NP and NS stimuli from +40 to -80 Torr (+5.33 to -10.67 kPa) induced significant changes in Q and TVC in both the upright seated and supine positions (P < 0.001). Cardiopulmonary baroreceptor loading with the supine position appeared to cause a greater reliance on carotid baroreflex-mediated changes in Q. Nevertheless, in both the seated and supine positions the changes in MAP were primarily mediated by alterations in TVC (percentage contribution of TVC at the time-of-peak MAP, seated 95 +/- 13, supine 76 +/- 17 %). These data indicate that alterations in vasomotor activity are the primary means by which the carotid baroreflex regulates blood pressure during acute changes in carotid sinus transmural pressure.

Clinical Trial↗
NASA NTRS1993

The nanophase iron mineral(s) in Mars soil

A series of surface-modified clays containing nanophase (np) iron oxide/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 clay acted as an effective matrix, both chemically and sterically, preventing the major part of the synthesized iron oxides from ripening, i.e., growing and developing larger crystals. The precipitated iron oxides appear as isodiametric or slightly elongated particles in the size range 1-10 nm, having large specific surface area. 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) hydroxy mineral such as "green rust," or ferrosic hydroxide. Magnetic measurements suggested that lepidocrocite converted to the more stable maghemite (gamma-Fe2O3) by mild heat treatment and then to nanophase hematite (alpha-Fe2O3) by extensive heat treatment. After mild heating, the iron-enriched clay became slightly magnetic, to the extent that it adheres to a hand-held magnet, as was observed with Mars soil. The chemical reactivity of the iron-enriched clays strongly resembles, and 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/oxyhydroxides and silicate phase surfaces. The reflectance spectrum of the clay-iron preparations in the visible range is generally similar to the reflectance curves of bright regions on Mars. This strengthens the evidence for the predominance of nanophase iron oxides/oxyhydroxides in Mars soil. The mode of formation of these nanophase iron oxides on Mars is still unknown. It is puzzling that despite the long period of time since aqueous weathering took place on Mars, they have not developed from their transitory stage to well-crystallized end-members. The possibility is suggested that these phases represent a continuously on-going, extremely slow weathering process.

NASA Program Exobiology↗
NASA NTRS2005

High Quality GaAs Growth by MBE on Si Using GeSi Buffers and Prospects for Space Photovoltaics

III-V solar cells on Si substrates are of interest for space photovoltaics since this would combine high performance space cells with a strong, lightweight and inexpensive substrate. However, the primary obstacles blocking III-V/Si cells from achieving high performance to date have been fundamental materials incompatabilities, namely the 4% lattice mismatch between GaAs and Si, and the large mismatch in thermal expansion coefficient. In this paper, we report on the molecular beam epitaxial (MBE) growth and properties of GaAs layers and single junction GaAs cells on Si wafers which utilize compositionally graded GeSi Intermediate buffers grown by ultra-high vacuum chemical vapor deposition (UHVCVD) to mitigate the large lattice mismatch between GaAs and Si. Ga As cell structures were found to incorporate a threading dislocation density of 0.9-1.5 x 10 (exp 6) per square centimeter, identical to the underlying relaxed Ge cap of the graded buffer, via a combination of transmission electron microscopy, electron beam induced current, and etch pit density measurements. AlGaAs/GaAs double heterostructures wre grown on the GeSi/Si substrates for time-resolved photoluminescence measurements, which revealed a bulk GaAs minority carrier lifetime in excess of 10 ns, the highest lifetime ever reported for GaAs on Si. A series of growth were performed to ass3ss the impact of a GaAs buffer to a thickness of only 0.1 micrometer. Secondary ion mass spectroscopy studies revealed that there is negligible cross diffusion of Ga, As and Ge at he III-V/Ge interface, identical to our earlier findings for GaAs grown on Ge wafers using MBE. This indicates that there is no need for a buffer to "bury" regions of high autodopjing,a nd that either pn or np configuration cells are easily accomodated by these substrates. Preliminary diodes and single junction Al Ga As heteroface cells were grown and fabricated on the Ge/GeSi/Si substrates for the first time. Diodes fabricated on GaAs, Ge and Ge/GeSi/Si substrate show nearly identical I-V characteristics in both forward and reverse bias regions. External quantum efficiencies of AlGaAs/GaAs cell structures grown on Ge/GeSi/Si and Ge substrates demonstrated nearly identical photoresponse, which indicates that high lifetimes, diffusion lengths and efficient minority carrier collection is maintained after complete cell processing.

Carlin, J. A.↗
NASA NTRS2005

Mapping Galactic 60Fe Synthesis in Cen CIR Region

This included a 1 year no cost time extension. The grant was for research into the origin of radioactive 60Fe, whose detection was a mission goal for INTEGRAL and RHESSI. During the grant period, both missions ultimately discovered gamma-line emission from this long lived radioactivity at precisely the value that had been predicted years before by Timmes and Woosley (ApJ, 449,204 (1995)). Unfortunately, using "revised" stellar models and cross sections Rauscher et a1 (ApJ, 576, 323 (2002)), had meanwhile predicted a much larger value. During the grant period, Dieter Hartmann (PI on the complementary grant at Clemson) and Woosley corresponded on this discrepancy and Hartmann visited Santa Cruz (November 20 - 28,2004). All of the grant funds in NAG513659 paid for the expenses of that visit. Subsequently, partly motivated by conversations with Hartmann and Diehl, Woosley re-investigated the production of 60Fe and 26A1 in massive stars from 12 - 120 solar masses, with an eye towards determining the relevant, uncertain physics. The chief changes in Rauscher et a1 were "new" Hauser Feshbach cross sections for 59,60Fe(ng) and 26Al(np)26Mg. The latter has an experimental evaluation which was actually better represented in the study of Timmes and Woosley. The iron (ng) cross sections are from theory and the Timmes and Woosley values were just as reliable as those from Rauscher. Experiments need to be done to resolve who is right. In addition uncertainties in stellar winds, opacities and the IMF were explored. The bottom line is that the value predicted by Timmes and Woosley could well be the correct one, but the experimental error bar is larger than was realized. At least half of the uncertainty is nuclear cross sections that can, and should be measured in the laboratory.

Woosley, Stanford↗
NASA NTRS2006

Implementing Scientific Simulation Codes Highly Tailored for Vector Architectures Using Custom Configurable Computing Machines

The motivation for this work comes from an observation that amidst the push for Massively Parallel (MP) solutions to high-end computing problems such as numerical physical simulations, large amounts of legacy code exist that are highly optimized for vector supercomputers. Because re-hosting legacy code often requires a complete re-write of the original code, which can be a very long and expensive effort, this work examines the potential to exploit reconfigurable computing machines in place of a vector supercomputer to implement an essentially unmodified legacy source code. Custom and reconfigurable computing resources could be used to emulate an original application's target platform to the extent required to achieve high performance. To arrive at an architecture that delivers the desired performance subject to limited resources involves solving a multi-variable optimization problem with constraints. Prior research in the area of reconfigurable computing has demonstrated that designing an optimum hardware implementation of a given application under hardware resource constraints is an NP-complete problem. The premise of the approach is that the general issue of applying reconfigurable computing resources to the implementation of an application, maximizing the performance of the computation subject to physical resource constraints, can be made a tractable problem by assuming a computational paradigm, such as vector processing. This research contributes a formulation of the problem and a methodology to design a reconfigurable vector processing implementation of a given application that satisfies a performance metric. A generic, parametric, architectural framework for vector processing implemented in reconfigurable logic is developed as a target for a scheduling/mapping algorithm that maps an input computation to a given instance of the architecture. This algorithm is integrated with an optimization framework to arrive at a specification of the architecture parameters that attempts to minimize execution time, while staying within resource constraints. The flexibility of using a custom reconfigurable implementation is exploited in a unique manner to leverage the lessons learned in vector supercomputer development. The vector processing framework is tailored to the application, with variable parameters that are fixed in traditional vector processing. Benchmark data that demonstrates the functionality and utility of the approach is presented. The benchmark data includes an identified bottleneck in a real case study example vector code, the NASA Langley Terminal Area Simulation System (TASS) application.

Rutishauser, David↗
NASA NTRS2003

A Graph Based Backtracking Algorithm for Solving General CSPs

Many AI tasks can be formalized as constraint satisfaction problems (CSPs), which involve finding values for variables subject to constraints. While solving a CSP is an NP-complete task in general, tractable classes of CSPs have been identified based on the structure of the underlying constraint graphs. Much effort has been spent on exploiting structural properties of the constraint graph to improve the efficiency of finding a solution. These efforts contributed to development of a class of CSP solving algorithms called decomposition algorithms. The strength of CSP decomposition is that its worst-case complexity depends on the structural properties of the constraint graph and is usually better than the worst-case complexity of search methods. Its practical application is limited, however, since it cannot be applied if the CSP is not decomposable. In this paper, we propose a graph based backtracking algorithm called omega-CDBT, which shares merits and overcomes the weaknesses of both decomposition and search approaches.

Pang, Wanlin↗
NASA NTRS2006

Results from the Gas Chromatograph Mass Spectrometer (GCMS) Experiment on the Cassini-Huygens Probe

The GCMS was part of the instrument complement on the Cassini-Huygens Probe to measure in situ the chemical composition of the atmosphere during the probe descent and coupled with the Aerosol Collector Pyrolyser (ACP) experiment by serving as detector for the pyrolization products to determine the composition of the aerosol particles. The GCMS employed a quadrupole mass filter with a secondary electron multiplier detection system and a gas sampling system providing continuous direct atmospheric composition measurements and batch sampling through three gas chromatographic (GC) columns, a chemical scrubber and a hydrocarbon enrichment cell. The GCMS gas inlet was heated to prevent condensation, and to evaporate volatiles from the surface after impact. The GCMS collected data from an altitude of 146 km to ground impact. The Probe and the GCMS survived impact and collected data for 1 hour and 9 minutes on the surface. Mass spectra were collected during descent and on the ground over a range of m/z from 2 to 141. The major constituents of the lower atmosphere were confirmed to be NP and CH4. The methane mole fraction was uniform in the stratosphere. It increased below the tropopause, at about 32 km altitude, monotonically toward the surface, reaching a plateau at about 8 km at a level near saturation. After surface impact a steep increase of the methane signal was observed, suggesting evaporation of surface condensed methane due to heating by the GCMS sample inlet heater. The measured mole fraction of Ar-40 is 4.3 x 10(exp-5) and of Ar-36 is 2.8 x 10(exp -7). The other primordial noble gases were below mole fraction. The isotope ratios of C-12/C-13 determined from methane measurements are 82.3 and of N-14/N-15 determined from molecular nitrogen are 183. The D/H isotope ratio determined from the H2 and HD measurements is 2.3 x l0(exp -4). Carbon dioxide, ethane, acetylene and cyanogen were detected evaporating from the surface in addition to methane.

Niemann, Hasso B.↗
NASA NTRS1993

Learning Search Control Knowledge for Deep Space Network Scheduling

While the general class of most scheduling problems is NP-hard in worst-case complexity, in practice, for specific distributions of problems and constraints, domain-specific solutions have been shown to perform in much better than exponential time.

Deep Space Network Search Control↗
NASA NTRS2007

Fire Fighting from High Altitude

A viewgraph presentation on high altitude fire fighting is shown. The topics include: 1) Yellowstone Fire - 1988; 2) 2006 Western States Fire Mission Over-View; 3) AMS-Wildfire Scanner; 4) October 24-25 Mission: Yosemite NP and NF; 5) October 24-25 Mission MODIS Overpass; 6) October 24-25 Mission Highlights; 7) October 28-29 Mission Esperanza Fire, California; 8) Response to the Esperanza Fire in Southern California -- Timeline Oct 27-29 2006; 9) October 28-29 Mission Esperanza Fire Altair Flight Routing; 10) October 28-29 Mission Esperanza Fire Altair Over-Flights; 11) October 28-29 Mission Highlights; 12) Results from the Esperanza Fire Response; 13) 2007 Western States Fire Mission; and 14) Western States UAS Fire Mission 2007

Cobleigh, Brent↗
NASA NTRS2003

Electron Collisional Excitation Rates for OI USING the B-Spline R-Matrix Approach

The B-spline R-matrix approach has been used to calculate electron collisional excitation strengths and rates for transitions between the 3P, 1D, and 1S states of ground configuration and from these states to the states of the excited 2s(sup 2)2p(sup 3)ns (n = 3-5), 2s(sup 2)2p(sup 3)np (n = 3-4), 2s(sup 2)2p(sup 3)nd (n = 3-4), 2s(sup 2)2p(sup 3)4f, and 2s2p(sup 5) configurations. The nonorthogonal orbitals are used for an accurate description of both the target wave functions and the R-matrix basis functions. The thermally averaged collision strengths are obtained from the collision strengths by integrating over a Maxwellian velocity distribution of electron energies, and these are tabulated over a temperature range from 1000 to 60,000 K. The parametric functions of scaled energy have also been obtained to represent collision strengths over a wide energy range or thermally averaged collision strengths at any desired temperature.

Zatsarinny, O.↗
NASA NTRS2007

Slow Mode Waves in the Heliospheric Plasma Sheet

We report the results of a search for waves/turbulence in the Heliospheric Plasma Sheet (HPS) surrounding the Heliospheric Current Sheet (HCS). The HPS is treated as a distinctive heliospheric structure distinguished by relatively high Beta, slow speed plasma. The data used in the investigation are from a previously published study of the thicknesses of the HPS and HCS that were obtained in January to May 2004 when Ulysses was near aphelion at 5 AU. The advantage of using these data is that the HPS is thicker at large radial distances and the spacecraft spends longer intervals inside the plasma sheet. From the study of the magnetic field and solar wind velocity components, we conclude that, if Alfven waves are present, they are weak and are dominated by variations in the field magnitude, B, and solar wind density, NP, that are anti-correlated.

heliospheric magnetic field↗
NASA NTRS2008

Quantum-Inspired Maximizer

A report discusses an algorithm for a new kind of dynamics based on a quantum- classical hybrid-quantum-inspired maximizer. The model is represented by a modified Madelung equation in which the quantum potential is replaced by different, specially chosen 'computational' potential. As a result, the dynamics attains both quantum and classical properties: it preserves superposition and entanglement of random solutions, while allowing one to measure its state variables, using classical methods. Such optimal combination of characteristics is a perfect match for quantum-inspired computing. As an application, an algorithm for global maximum of an arbitrary integrable function is proposed. The idea of the proposed algorithm is very simple: based upon the Quantum-inspired Maximizer (QIM), introduce a positive function to be maximized as the probability density to which the solution is attracted. Then the larger value of this function will have the higher probability to appear. Special attention is paid to simulation of integer programming and NP-complete problems. It is demonstrated that the problem of global maximum of an integrable function can be found in polynomial time by using the proposed quantum- classical hybrid. The result is extended to a constrained maximum with applications to integer programming and TSP (Traveling Salesman Problem).

Zak, Michail↗
NASA NTRS2009

Understanding the Scalability of Bayesian Network Inference using Clique Tree Growth Curves

Bayesian networks (BNs) are used to represent and efficiently compute with multi-variate probability distributions in a wide range of disciplines. One of the main approaches to perform computation in BNs is clique tree clustering and propagation. In this approach, BN computation consists of propagation in a clique tree compiled from a Bayesian network. There is a lack of understanding of how clique tree computation time, and BN computation time in more general, depends on variations in BN size and structure. On the one hand, complexity results tell us that many interesting BN queries are NP-hard or worse to answer, and it is not hard to find application BNs where the clique tree approach in practice cannot be used. On the other hand, it is well-known that tree-structured BNs can be used to answer probabilistic queries in polynomial time. In this article, we develop an approach to characterizing clique tree growth as a function of parameters that can be computed in polynomial time from BNs, specifically: (i) the ratio of the number of a BN's non-root nodes to the number of root nodes, or (ii) the expected number of moral edges in their moral graphs. Our approach is based on combining analytical and experimental results. Analytically, we partition the set of cliques in a clique tree into different sets, and introduce a growth curve for each set. For the special case of bipartite BNs, we consequently have two growth curves, a mixed clique growth curve and a root clique growth curve. In experiments, we systematically increase the degree of the root nodes in bipartite Bayesian networks, and find that root clique growth is well-approximated by Gompertz growth curves. It is believed that this research improves the understanding of the scaling behavior of clique tree clustering, provides a foundation for benchmarking and developing improved BN inference and machine learning algorithms, and presents an aid for analytical trade-off studies of clique tree clustering using growth curves.

Mengshoel, Ole Jakob↗
NASA NTRS2010

The HYTHIRM Project: Flight Thermography of the Space Shuttle During the Hypersonic Re-entry

This report describes a NASA Langley led endeavor sponsored by the NASA Engineering Safety Center, the Space Shuttle Program Office and the NASA Aeronautics Research Mission Directorate to demonstrate a quantitative thermal imaging capability. A background and an overview of several multidisciplinary efforts that culminated in the acquisition of high resolution calibrated infrared imagery of the Space Shuttle during hypervelocity atmospheric entry is presented. The successful collection of thermal data has demonstrated the feasibility of obtaining remote high-resolution infrared imagery during hypersonic flight for the accurate measurement of surface temperature. To maximize science and engineering return, the acquisition of quantitative thermal imagery and capability demonstration was targeted towards three recent Shuttle flights - two of which involved flight experiments flown on Discovery. In coordination with these two Shuttle flight experiments, a US Navy NP-3D aircraft was flown between 26-41 nautical miles below Discovery and remotely monitored surface temperature of the Orbiter at Mach 8.4 (STS-119) and Mach 14.7 (STS-128) using a long-range infrared optical package referred to as Cast Glance. This same Navy aircraft successfully monitored the Orbiter Atlantis traveling at approximately Mach 14.3 during its return from the successful Hubble repair mission (STS-125). The purpose of this paper is to describe the systematic approach used by the Hypersonic Thermodynamic Infrared Measurements team to develop and implement a set of mission planning tools designed to establish confidence in the ability of an imaging platform to reliably acquire, track and return global quantitative surface temperatures of the Shuttle during entry. The mission planning tools included a pre-flight capability to predict the infrared signature of the Shuttle. Such tools permitted optimization of the hardware configuration to increase signal-to-noise and to maximize the available dynamic range while mitigating the potential for saturation. Post flight, analysis tools were used to assess atmospheric effects and to convert the 2-D intensity images to 3-D temperature maps of the windward surface. Comparison of the spatially resolved global thermal measurements to surface thermocouples and CFD prediction is made. Successful demonstration of a quantitative, spatially resolved, global temperature measurement on the Shuttle suggests future applications towards hypersonic flight test programs within NASA, DoD and DARPA along with flight test opportunities supporting NASA's project Constellation.

Horvath, Thomas J.↗
NASA NTRS2010

Application of a Near Infrared Imaging System for Thermographic Imaging of the Space Shuttle during Hypersonic Re-Entry

High resolution calibrated near infrared (NIR) imagery was obtained of the Space Shuttle s reentry during STS-119, STS-125, and STS-128 missions. The infrared imagery was collected using a US Navy NP-3D Orion aircraft using a long-range infrared optical package referred to as Cast Glance. The slant ranges between the Space Shuttle and Cast Glance were approximately 26-41 nautical miles at point of closest approach. The Hypersonic Thermodynamic Infrared Measurements (HYTHIRM) project was a NASA Langley led endeavor sponsored by the NASA Engineering Safety Center, the Space Shuttle Program Office and the NASA Aeronautics Research Mission Directorate to demonstrate a quantitative thermal imaging capability. HYTHIRM required several mission tools to acquire the imagery. These tools include pre-mission acquisition simulations of the Shuttle trajectory in relationship to the Cast Glance aircraft flight path, radiance modeling to predict the infrared response of the Shuttle, and post mission analysis tools to process the infrared imagery to quantitative temperature maps. The spatially resolved global thermal measurements made during the Shuttle s hypersonic reentry provides valuable flight data for reducing the uncertainty associated with present day ground-to-flight extrapolation techniques and current state-of-the-art empirical boundary-layer transition or turbulent heating prediction methods. Laminar and turbulent flight data is considered critical for the development of turbulence models supporting NASA s next-generation spacecraft. This paper will provide the motivation and details behind the use of an upgraded NIR imaging system used onboard a Navy Cast Glance aircraft and describe the characterizations and procedures performed to obtain quantitative temperature maps. A brief description and assessment will be provided of the previously used analog NIR camera along with image examples from Shuttle missions STS-121, STS-115, and solar tower test. These thermal observations confirmed the challenge of a long-range acquisition during re-entry. These challenges are due to unknown atmospheric conditions, image saturation, vibration etc. This provides the motivation for the use of a digital NIR sensor. The characterizations performed on the digital NIR sensor included radiometric, spatial, and spectral measurements using blackbody radiation sources and known targets. An assessment of the collected data for three Space Shuttle atmospheric re-entries, STS-119, STS-125, and STS-128, are provided along with a description of various events of interest captured using the digital NIR imaging system such as RCS firings and boundary layer transitions. Lastly the process used to convert the raw image counts to quantitative temperatures is presented along with comparisons to the Space Shuttle's onboard thermocouples.

Zalameda, Joseph N.↗
NASA NTRS2010

Fast Solution in Sparse LDA for Binary Classification

An algorithm that performs sparse linear discriminant analysis (Sparse-LDA) finds near-optimal solutions in far less time than the prior art when specialized to binary classification (of 2 classes). Sparse-LDA is a type of feature- or variable- selection problem with numerous applications in statistics, machine learning, computer vision, computational finance, operations research, and bio-informatics. Because of its combinatorial nature, feature- or variable-selection problems are NP-hard or computationally intractable in cases involving more than 30 variables or features. Therefore, one typically seeks approximate solutions by means of greedy search algorithms. The prior Sparse-LDA algorithm was a greedy algorithm that considered the best variable or feature to add/ delete to/ from its subsets in order to maximally discriminate between multiple classes of data. The present algorithm is designed for the special but prevalent case of 2-class or binary classification (e.g. 1 vs. 0, functioning vs. malfunctioning, or change versus no change). The present algorithm provides near-optimal solutions on large real-world datasets having hundreds or even thousands of variables or features (e.g. selecting the fewest wavelength bands in a hyperspectral sensor to do terrain classification) and does so in typical computation times of minutes as compared to days or weeks as taken by the prior art. Sparse LDA requires solving generalized eigenvalue problems for a large number of variable subsets (represented by the submatrices of the input within-class and between-class covariance matrices). In the general (fullrank) case, the amount of computation scales at least cubically with the number of variables and thus the size of the problems that can be solved is limited accordingly. However, in binary classification, the principal eigenvalues can be found using a special analytic formula, without resorting to costly iterative techniques. The present algorithm exploits this analytic form along with the inherent sequential nature of greedy search itself. Together this enables the use of highly-efficient partitioned-matrix-inverse techniques that result in large speedups of computation in both the forward-selection and backward-elimination stages of greedy algorithms in general.

Moghaddam, Baback↗