SEARCH · Engineering Papers
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.
This note presents recursive algorithms that are rapidly convergent and more stable for finding the principal square root of a complex matrix. Also, the developed algorithms are utilized to derive the fast and stable matrix sign algorithms which are useful in developing applications to control system problems.
This article reports the study of algorithms for non-negative matrix factorization (NMF) in various applications involving smoothly varying data such as time or temperature series diffraction data on a dense grid of points. Utilizing the continual nature of the data, a fast two-stage algorithm is developed for highly efficient and accurate NMF. In the first stage, an alternating non-negative least-squares framework is used in combination with the active set method with a warm-start strategy for the solution of subproblems. In the second stage, an interior point method is adopted to accelerate the local convergence. The convergence of the proposed algorithm is proved. The new algorithm is compared with some existing algorithms in benchmark tests using both real-world data and synthetic data. Furthermore, the results demonstrate the advantage of the algorithm in finding high-precision solutions.
An improved method of model-based diagnosis of a complex engineering system is embodied in an algorithm that involves considerably less computation than do prior such algorithms. This method and algorithm are based largely on developments reported in several NASA Tech Briefs articles: The Complexity of the Diagnosis Problem (NPO-30315), Vol. 26, No. 4 (April 2002), page 20; Fast Algorithms for Model-Based Diagnosis (NPO-30582), Vol. 29, No. 3 (March 2005), page 69; Two Methods of Efficient Solution of the Hitting-Set Problem (NPO-30584), Vol. 29, No. 3 (March 2005), page 73; and Efficient Model-Based Diagnosis Engine (NPO-40544), on the following page. Some background information from the cited articles is prerequisite to a meaningful summary of the innovative aspects of the present method and algorithm. In model-based diagnosis, the function of each component and the relationships among all the components of the engineering system to be diagnosed are represented as a logical system denoted the system description (SD). Hence, the expected normal behavior of the engineering system is the set of logical consequences of the SD. Faulty components lead to inconsistencies between the observed behaviors of the system and the SD. Diagnosis the task of finding faulty components is reduced to finding those components, the abnormalities of which could explain all the inconsistencies. The solution of the diagnosis problem should be a minimal diagnosis, which is a minimal set of faulty components. The calculation of a minimal diagnosis is inherently a hard problem, the solution of which requires amounts of computation time and memory that increase exponentially with the number of components of the engineering system. Among the developments to reduce the computational burden, as reported in the cited articles, is the mapping of the diagnosis problem onto the integer-programming (IP) problem. This mapping makes it possible to utilize a variety of algorithms developed previously for IP to solve the diagnosis problem. In the IP approach, the diagnosis problem can be formulated as a linear integer optimization problem, which can be solved by use of well-developed integer-programming algorithms. This concludes the background information.
Wavelet bases are used to generate spaces of approximation for the resolution of bidimensional elliptic and parabolic problems. Under some specific hypotheses relating the properties of the wavelets to the order of the involved operators, it is shown that an approximate solution can be built. This approximation is then stable and converges towards the exact solution. It is designed such that fast algorithms involving biorthogonal multi resolution analyses can be used to resolve the corresponding numerical problems. Detailed algorithms are provided as well as the results of numerical tests on partial differential equations defined on the bidimensional torus.
Wavelet bases are used to generate spaces of approximation for the resolution of bidimensional elliptic and parabolic problems. Under some specific hypotheses relating the properties of the wavelets to the order of the involved operators, it is shown that an approximate solution can be built. This approximation is then stable and converges towards the exact solution. It is designed such that fast algorithms involving biorthogonal multi resolution analyses can be used to resolve the corresponding numerical problems. Detailed algorithms are provided as well as the results of numerical tests on partial differential equations defined on the bidimensional torus.
A method for obtaining the complete path enumerator T(D, L, I) of a convolutional code is described. A system of algebraic equations is solved, using a new algorithm for computing determinants, to obtain T(D, L, I) for the (7,1/2) NASA standard code. Generating functions, derived from T(D, L, I) are used to upper bound Viterbi decoder error rates. This technique is currently feasible for constraint length K less than 10 codes. A practical, fast algorithm is presented for computing the leading nonzero coefficients of the generating functions used to bound the performance of constraint length K less than 20 codes. Code profiles with about 50 nonzero coefficients are obtained with this algorithm for the experimental K = 15, rate 1/4, code in the Galileo mission and for the proposed K = 15, rate 1/6, 2-dB code.
Interferometric Synthetic Aperture Radar (IFSAR) is a technique that allows an automated way to carry out terrain mapping. IFSAR is carried out by first generating a SAR image pair from two antennas that are spatially separated. The phase difference between the SAR image pair is proportional to the topography. After registering the SAR images, the difference in phase in each pixel is extracted to generate an interferogram. Since the phase can only be measured within 2pi radians, phase unwrapping is carried out to extract the absolute phase for each pixel that will be proportional to the local height. While IFSAR algorithm is typically applied to measurement data, it is useful to develop an IFSAR simulator to develop a better understanding of the IFSAR technique. The IFSAR simulator can be used in choosing system parameters, experimenting with processing procedures and mission planning. In this paper we will present an IFSAR simulation methodology to simulate the interferogram based on the shooting and bouncing ray (SBR) technique. SBR is a standard ray-tracing technique used to simulate scattering from large, complex targets. SBR is carried out by shooting rays at the target or scene. At the exit point of each ray, a ray-tube integration is done to find its contribution to the total field. A fast algorithm has been developed for the SBR for simulating SAR images of complex targets. In the IFSAR simulation, we build upon the fast SAR simulation technique. Given the antenna pair configuration, radar system parameters and the geometrical description of the scene, we first simulate two SAR images from each antenna. After post processing the two SAR images, we generate an interferogram. Phase unwrapping is then performed on the interferogram to arrive at the desired terrain map. We will present results from the SBR-based IFSAR simulator. The results will include terrain map reconstruction of urban environments. The reconstruction will be compared to the ground truth to examine the fidelity of the simulation. We will also investigate the effect of multi-bounce scattering in urban environments on phase unwrapping and reconstruction.
The Climate Absolute Radiance and Refractivity Observatory (CLARREO) Pathfinder (CPF) mission is set to launch an SI-traceable reflective solar (RS) spectrometer aboard the International Space Station to measure Earth-reflected solar radiation with a radiometric uncertainty of 0.3% (k=1). The CPF intercalibration team has devised a cutting-edge methodology to accurately transfer the benchmark CPF calibration reference to the shortwave (SW) channel (200-5000 nm) of the Clouds and the Earth’s Radiant Energy System (CERES) instrument. The spectral range of CPF measurements spans from 350-2300 nm, while the CERES SW channel measures the Earth-reflected broadband solar radiances between 200 nm to 5 μm. To conduct precise CPF-CERES intercalibration analysis, the CPF-like spectral radiances outside the CPF spectral range need to be estimated to match the CERES SW spectral range. In response, the team has developed a fast algorithm that leverages spectrally redundant information within the CPF-measured portion through principal component analysis (PCA) and utilizes pre-established spectral correlation relationships among wavelengths to extend the CPF spectrum below 350 nm and above 2300 nm. Our results show that the algorithm achieves excellent accuracy in generating the missing energy in the UV and IR portions. The RMS error in the UV region is less than 4.5x10-3 W/m2/sr/nm, while in the IR region, it is smaller than 8x10-5 W/m2/sr/nm. Our methodology was validated using measured EMIT radiance data, which covers the spectral range from 0.381 μm to 2.493 μm. We employed EMIT radiances within the wavelength range of 0.43 – 2.25 μm to generate radiances for both the shorter wavelength range (0.381 – 0.43 μm) and longer wavelength range (2.25 – 2.493 μm). The generated radiances agree very well with the measured EMIT radiances. The standard deviation in the integrated broadband radiances was about 0.1%, and the bias is less than 0.004% for over 1.5 million EMIT measured samples. These statistics show that the spectral gap filling algorithm is robust and effective in substantially reducing the spectral difference-induced uncertainty in the CPF-CERES intercalibration samples.
Standard computed tomography (CT) reconstruction algorithms such as filtered back projection (FBP) and Feldkamp-Davis-Kress (FDK) require many views for producing high-quality reconstructions, which can slow image acquisition and increase cost in non-destructive evaluation (NDE) applications. Over the past 20 years, a variety of methods have been developed for computing high-quality CT reconstructions from sparse views. However, the problem of how to select the best views for CT reconstruction remains open. In this paper, we present a novel view covariance loss (VCL) function that measures the joint information of a set of views by approximating the normalized mean squared error (NMSE) of the reconstruction. We present fast algorithms for computing the VCL along with an algorithm for selecting a subset of views that approximately minimizes its value. Our experiments on simulated and measured data indicate that for a fixed number of views our proposed view covariance loss selection (VCLS) algorithm results in reconstructions with lower NRMSE, fewer artifacts, and greater accuracy than current alternative approaches.
Many recent tensor network algorithms apply unitary operators to parts of a tensor network in order to reduce entanglement. However, many of the previously used iterative algorithms to minimize entanglement can be slow. We introduce an approximate, fast, and simple algorithm to optimize disentangling unitary tensors. Our algorithm is asymptotically faster than previous iterative algorithms and often results in a residual entanglement entropy that is within 10 to 40% of the minimum. For certain input tensors, our algorithm returns an optimal solution. When disentangling order-4 tensors with equal bond dimensions, our algorithm achieves an entanglement spectrum where nearly half of the singular values are zero. We further validate our algorithm by showing that it can efficiently disentangle random 1D states of qubits.
Cryo-electron tomography (cryo-ET) enables structural characterization of biomolecules under near-native conditions. Existing approaches for interpreting the resulting three-dimensional volumes are computationally expensive and have difficulty interpreting density associated with small proteins/complexes. To explore alternate approaches for identifying proteins in cryo-ET data we pursued a Graph Network and topologically invariant approach. Here, we report on a fast algorithm that classifies particles by searching for nuances of evolutionarily conversed motifs and the geometrical characteristics of protein structure. GRIP-Tomo 2.0 is a machine-learning pipeline that extracts interpretable topological features of protein structures within noisy experimental backgrounds. Compared to version 1.0, the new pipeline includes three upgrades that significantly improve performance including synthetic tomogram generation simulating realistic noise, graph-based persistent feature extraction as protein fingerprints, and high-performance computing acceleration. GRIP-Tomo 2.0 achieves over 90% accuracy in classifying between proteins and noise using both real and synthetic datasets which represents a foundational step toward advancing cryo-ET workflows and empowering automated visual proteomics.
In a classical scattering problem, the classical eikonal is defined as the generator of the canonical transformation that maps in-states to out-states. It can be regarded as the classical limit of the log of the quantum S-matrix. In a classical analog of the Born approximation in quantum mechanics, the classical eikonal admits an expansion in oriented tree graphs, where oriented edges denote retarded/advanced worldline propagators. The Magnus expansion, which takes the log of a time-ordered exponential integral, offers an efficient method to compute the coefficients of the tree graphs to all orders. We exploit a Hopf algebra structure behind the Magnus expansion to develop a fast algorithm which can compute the tree coefficients up to the 12th order (over half a million trees) in less than an hour. In a relativistic setting, our methods can be applied to the post-Minkowskian (PM) expansion for gravitational binaries in the worldline formalism. We demonstrate the methods by computing the 3PM eikonal and find agreement with previous results based on amplitude methods. Importantly, the Magnus expansion yields a finite eikonal, while the naïve eikonal based on the time-symmetric propagator is infrared-divergent from 3PM on.
Standard MCNP particle tracking takes place along straight-line trajectories from interaction point to interaction point. There is a feature within MCNP that is planned for deprecation that provides surface boundary conditions for approximating gravity for planetary cases, but this feature is not applicable to a cold neutron beam. A new extension has been developed to track particles along parabolic trajectories with a constant acceleration. MCNP contains 1st and 2nd-order surfaces as well as a special case of 4th-order surfaces for simple tori, and the intersection of parabolic trajectories with these surfaces becomes 2nd, 4th, and 8th-order equations in time, respectively. Solving these equations utilizes a fast algorithm for finding the roots of polynomials. Finally, the theory, MCNP input card, and examples of using this new feature will be discussed.
Fast algorithm for minimization of Boolean functions to two level and-or form
Relations between the Haar and Walsh/Hadamard (W/H) transforms, which are proved, show that for some applications the Haar transform performs as well as, and faster than, the W/H transform. These relations yield a family of orthogonal transforms including the Haar and W/H transforms with a common fast algorithm.
Mathematical techniques are described for processing EEG signals associated with varying states of alertness. Fast algorithms for implementing real-time computations of alertness estimates were developed. A realization of the phase-distortionless digital filter is presented which approaches real-time filtering and a transform for EEG signals. This transform provides information for the alertness estimates and can be performed in real time. A statistical test for stationarity in EEG signals is being developed that will provide a method for determining the duration of the EEG signals necessary for estimating the short-time power or energy spectra for nonstationary analysis of EEG signals.
A method is described for estimating low speed wind tunnel blockage, including model volume, bubble separation and viscous wake effects. A tunnel-centerline, source/sink distribution is derived from measured wall pressure signatures using fast algorithms to solve the inverse problem in three dimensions. Blockage may then be computed throughout the test volume. Correlations using scaled models or tests in two tunnels were made in all cases. In many cases model reference area exceeded 10% of the tunnel cross-sectional area. Good correlations were obtained regarding model surface pressures, lift drag and pitching moment. It is shown that blockage-induced velocity variations across the test section are relatively unimportant but axial gradients should be considered when model size is determined.
A general formulation of monocromatic radiative transfer with scattering has been developed for plane-parallel geometry. The inhomogeneous and nonisothermal medium absorbs, emits, and anisotropically scatters radiation. Surfaces can emit and scatter radiation in any specified manner. The solution procedure uses the fact that phase incoherent scattering is linear in radiative sources. Certain basic scattering functions are then defined and calculated by an adding computer code using matrix algebra. These scattering functions are weighted by the temperature field and summed (superimposed) to obtain the solution for any specific problem. Numerical results for exiting intensities and one-sided heat fluxes from general media bound by one arbitrary surface are presented. These parametric studies demonstrate the effects of scattering particles and surfaces on radiative transfer from inhomogeneous and nonisothermal media. Application of the formulation to radiative equilibrium is also discussed. The conclusion is that all problems in plane-parallel radiative transfer with scattering can be solved by a common and computationally fast algorithm based on this formulation.