Search NASA⌕ Search

SEARCH · Search NASA

Results for “Sparse Matrix”

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.

262 records · Page 15

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↗

An incremental strategy for calculating consistent discrete CFD sensitivity derivatives

In this preliminary study involving advanced computational fluid dynamic (CFD) codes, an incremental formulation, also known as the 'delta' or 'correction' form, is presented for solving the very large sparse systems of linear equations which are associated with aerodynamic sensitivity analysis. For typical problems in 2D, a direct solution method can be applied to these linear equations which are associated with aerodynamic sensitivity analysis. For typical problems in 2D, a direct solution method can be applied to these linear equations in either the standard or the incremental form, in which case the two are equivalent. Iterative methods appear to be needed for future 3D applications; however, because direct solver methods require much more computer memory than is currently available. Iterative methods for solving these equations in the standard form result in certain difficulties, such as ill-conditioning of the coefficient matrix, which can be overcome when these equations are cast in the incremental form; these and other benefits are discussed. The methodology is successfully implemented and tested in 2D using an upwind, cell-centered, finite volume formulation applied to the thin-layer Navier-Stokes equations. Results are presented for two laminar sample problems: (1) transonic flow through a double-throat nozzle; and (2) flow over an isolated airfoil.

Korivi, Vamshi Mohan↗

NASA Tech Briefs, August 2005

Topics include: Hidden Identification on Parts: Magnetic Machine-Readable Matrix Symbols; System for Processing Coded OFDM Under Doppler and Fading; Multipurpose Hyperspectral Imaging System; Magnetic-Flux-Compensated Voltage Divider; High-Performance Satellite/Terrestrial-Network Gateway; Internet-Based System for Voice Communication With the ISS; Stripline/Microstrip Transition in Multilayer Circuit Board; Dual-Band Feed for a Microwave Reflector Antenna; Quadratic Programming for Allocating Control Effort; Range Process Simulation Tool; Simulator of Space Communication Networks; Computing Q-D Relationships for Storage of Rocket Fuels; Contour Error Map Algorithm; Portfolio Analysis Tool; Glass Frit Filters for Collecting Metal Oxide Nanoparticles; Anhydrous Proton-Conducting Membranes for Fuel Cells; Portable Electron-Beam Free-Form Fabrication System; Miniature Laboratory for Detecting Sparse Biomolecules; Multicompartment Liquid-Cooling/Warming Protective Garments; Laser Metrology for an Optical-Path-Length Modulator; PCM Passive Cooling System Containing Active Subsystems; Automated Electrostatics Environmental Chamber; Estimating Aeroheating of a 3D Body Using a 2D Flow Solver; Artificial Immune System for Recognizing Patterns; Computing the Thermodynamic State of a Cryogenic Fluid; Safety and Mission Assurance Performance Metric; Magnetic Control of Concentration Gradient in Microgravity; Avionics for a Small Robotic Inspection Spacecraft; and Simulation of Dynamics of a Flexible Miniature Airplane.

Source record↗

Evaluating the Limits of QAOA Parameter Transfer at High-Rounds on Sparse Ising Models With Geometrically Local Cubic Terms

The emergent practical applicability of the Quantum Approximate Optimization Algorithm (QAOA) for approximate combinatorial optimization is a subject of considerable interest. One of the primary limitations of QAOA is the task of finding a set of good parameters, which is usually done using a variational optimization loop. Parameter transfer, or parameter concentration, is a phenomenon where QAOA angles trained on problem instances that are self-similar tend to perform well for other problem instances from that similar class. This suggests a potentially highly efficient and scalable non-variational learning method for QAOA angle finding. In this work, we systematically study QAOA parameter transferability from small problem sizes (16 and 27 decision variables) onto large problem instances (up to 156 qubits) for heavy-hex graph Ising models with geometrically local higher order terms using the Julia based QAOA simulation tool \texttt{JuliQAOA} to perform classical angle finding for up to $49$ QAOA layers ($p$). Parameter transfer of the fixed angles is validated using a combination of full statevector, Projected Entangled Pair States (PEPS), Matrix Product State (MPS), and LOWESA numerical simulations. We find that the QAOA parameter transfer from single instances applied to other (unseen) problem instances does not in general provide monotonically improving performance as a function of $p$ - there are many cases where the performance temporarily decreases as a function of $p$ - but despite this the transferred angles have a general trend of improved expectation value as the QAOA depth increases, in many cases converging close to the true ground-state energy of the $100+$ qubit instances. We also sample the hardware-compatible Ising models using the ensemble of transfer-learned QAOA parameters on several superconducting qubit IBM Quantum processors with 127, 133, and 156 qubits. We find continuous solution quality improvement of the hardware-compatible QAOA circuits run on the IBM NISQ processors up to $p=5$ on \texttt{ibm\_fez}, up to $p=9$ on \texttt{ibm\_torino}, and up to $p=10$ on \texttt{ibm\_pittsburgh}.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

Distribution of centrality measures on undirected random networks via the cavity method

The Katz centrality of a node in a complex network is a measure of the node’s importance as far as the flow of information across the network is concerned. For ensembles of locally tree-like undirected random graphs, this observable is a random variable. Its full probability distribution is of interest but difficult to handle analytically because of its “global” character and its definition in terms of a matrix inverse. Leveraging a fast Gaussian Belief Propagation-Cavity algorithm to solve linear systems on tree-like structures, we show that i) the Katz centrality of a single instance can be computed recursively in a very fast way, and ii) the probability P ( K ) that a random node in the ensemble of undirected random graphs has centrality K satisfies a set of recursive distributional equations, which can be analytically characterized and efficiently solved using a population dynamics algorithm. We test our solution on ensembles of Erdős-Rényi and Scale Free networks in the locally tree-like regime, with excellent agreement. The analytical distribution of centrality for the configuration model conditioned on the degree of each node can be employed as a benchmark to identify nodes of empirical networks with over- and underexpressed centrality relative to a null baseline. We also provide an approximate formula based on a rank- 1 projection that works well if the network is not too sparse, and we argue that an extension of our method could be efficiently extended to tackle analytical distributions of other centrality measures such as PageRank for directed networks in a transparent and user-friendly way.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

Telescope Alignment From Sparsely Sampled Wavefront Measurements Over Pupil Subapertures

Alignment of two-element telescopes is a classic problem. During recent integration and test of the Space Interferometry Mission s (SIM s) Astrometric Beam Combiner (ABC), the innovators were faced with aligning two such telescope subsystems in the presence of a further complication: only two small subapertures in each telescope s pupil were accessible for measuring the wavefront with a Fizeau interferometer. This meant that the familiar aberrations that might be interpreted to infer system misalignments could be viewed only over small sub-regions of the pupil, making them hard to recognize. Further, there was no contiguous surface of the pupil connecting these two subapertures, so relative phase piston information was lost; the underlying full-aperture aberrations therefore had an additional degree of ambiguity. The solution presented here is to recognize that, in the absence of phase piston, the Zygo measurements primarily provide phase tilt in the subaperture windows of interest. Because these windows are small and situated far from the center of the (inaccessible) unobscured full aperture, any aberrations that are higher-order than tilt will be extremely high-order on the full aperture, and so not necessary or helpful to the alignment. Knowledge of the telescope s optical prescription allows straightforward evaluation of sensitivities (subap mode strength per unit full-aperture aberration), and these can be used in a predictive matrix approach to move with assurance to an aligned state. The technique is novel in every operational way compared to the standard approach of alignment based on full-aperture aberrations or searching for best rms wavefront. This approach is closely grounded in the observable quantities most appropriate to the problem. It is also more intuitive than inverting full phase maps (or subaperture Zernike spectra) with a ray-tracing program, which must certainly work in principle, but in practice met with limited success. Even if such classical alignment techniques became practical, the techniques reported here form a reassuringly transparent and intuitive check on the course of the alignment with very little computational effort.

Bloemhof, Eric E.↗

Analog Systems for Edge Optimization

Over the past decade, analog computing has the subject of substantial research interest providing a path toward improved computational efficiency in the post-Dennard era. Analog matrix vector multiplication (MVM) accelerators provide a popular approach given the ubiquity of MVM operations in numerous applications. However, historically analog computing systems can struggle with applications requiring high precision due to the inherent susceptibility of these systems to analog non-idealities. Therefore, prior work on analog systems has focused either on applications known to be tolerant of limited precision (e.g., neural network inference), or using expensive techniques to emulate high-precision using many analog MVM operations. In this work, we propose an alternative approach. Motivated by recent advances in inexact nonlinear solvers and optimizers, we explore the potential of co-designing optimization algorithms which can take full advantage of the fundamentally inexact analog MVM operations. To enable these co-designed algorithms we also develop a general mathematical theory of the precision and energy efficiency of analog operations, and a new system architecture for tightly-coupled analog and digital computation. Finally, we examine the applicability of analog computing to a wider class of symmetric positive definite systems and find potential in using analog operations as a sparse approximate inverse preconditioner. With these core innovations, this project provides a path toward effectively implementing optimization algorithms on power-constrained autonomous and semi-autonomous systems.

97 MATHEMATICS AND COMPUTING↗

Predicting High‐Resolution Spatial and Spectral Features in Mass Spectrometry Imaging with Machine Learning and Multimodal Data Fusion

Recent advancements in molecular Mass Spectrometry Imaging have sparked interest in integrating high spatial resolution methods with molecular mass-spectrometry-based chemical imaging. Fusion-based algorithms have proven effective in generating high spatial-resolution molecular mass spectra. However, a significant challenge stems from the differing physical mechanisms underlying image generation and data upsampling techniques, potentially leading to discrepancies in integrated information channels. Integrating physical constraints into data processing workflows is essential to tackle this issue. In this study, we propose an innovative approach that merges data from Fourier transform ion cyclotron resonance (FTICR), time-of-flight matrix-assisted laser desorption/ionization, and time-of-flight secondary ion mass spectrometry imaging techniques. By leveraging FT-ICR's unparalleled spectral resolution and ToF-SIMS's exceptional spatial resolution, we achieve submicron spatial resolution, enabling the observation of intact molecular species with remarkable spectral precision. Canonical correlation analysis is employed to incorporate physical constraints. Through sophisticated image processing and machine learning techniques, the results of this fusion hold significant promise for advancing our comprehension of complex systems and unveiling concealed molecular intricacies.

canonical correlation analysis↗

On a Simplified Approach to Achieve Parallel Performance and Portability Across CPU and GPU Architectures

This paper presents software advances to easily exploit computer architectures consisting of a multi-core CPU and CPU+GPU to accelerate diverse types of high-performance computing (HPC) applications using a single code implementation. The paper describes and demonstrates the performance of the open-source C++ matrix and array (MATAR) library that uniquely offers: (1) a straightforward syntax for programming productivity, (2) usable data structures for data-oriented programming (DOP) for performance, and (3) a simple interface to the open-source C++ Kokkos library for portability and memory management across CPUs and GPUs. The portability across architectures with a single code implementation is achieved by automatically switching between diverse fine-grained parallelism backends (e.g., CUDA, HIP, OpenMP, pthreads, etc.) at compile time. The MATAR library solves many longstanding challenges associated with easily writing software that can run in parallel on any computer architecture. This work benefits projects seeking to write new C++ codes while also addressing the challenges of quickly making existing Fortran codes performant and portable over modern computer architectures with minimal syntactical changes from Fortran to C++. We demonstrate the feasibility of readily writing new C++ codes and modernizing existing codes with MATAR to be performant, parallel, and portable across diverse computer architectures.

97 MATHEMATICS AND COMPUTING↗

Investigating Low-Altitude Constellations of Ad-Hoc Lunar PNT System for Distributed Spacecraft Autonomy

In this study, we examine a low-altitude Lunar Position, Navigation, and Timing (LPNT) constellations and the localization performance of Centralized Extended Kalman Filter (CEKF) and Decentralized Extended Kalman Filter (DEKF) algorithms. The primary investigation involves a 100-node swarm operating at a 100 km altitude, in contrast to previous studies that examined a 21-node asset in a frozen-orbit at 5,500 km. The autonomous operation of large-scale swarm is based on two-way Inter-Satellite Link (ISL) measurements, which involve pseudoranges and relative velocities among swarm nodes. We perform a numerical assessment of the two filtering approaches, utilizing ‘fully sampled’ measurements from all available assets as well as ‘two ISL’ measurements where each spacecraft is restricted to only two antennas. This research includes an analysis of CEKF under 2-ISL constraints and evaluates the performance of DEKF in a 100-node swarm, which has not been explored in previous studies. In addition, we examine the impact of increasing the sampling frequency for DEKF, showing that the update cycle can be shortened from a 10-minute interval. A novel approach for ‘2-ISL limited’ DEKF will also be introduced, using a matching formulation that exhaustively enumerates all potential matches. This study provides valuable insights into large-scale distributed swarm operations, considering various filter configurations, sampling frequencies, matching strategies, and scalability of CEKF and DEKF for low-altitude LPNT applications. The Lunar PNT technology plays a key role in providing reliable and robust navigation services on the Moon's surface and the South pole, where the primary Lunar missions are planned. To support upcoming Lunar missions, including small satellites from NASA's Commercial Lunar Payload Services program, the Lunar PNT system must be adaptable to smaller platforms like CubeSats. Driven by the growing involvement of public and private exploration partnerships, the traditional low Earth orbit missions are shifting to beyond geosynchronous orbit [1]. These upcoming missions aim to foster a sustainable and innovative exploration program, in collaboration with commercial and international partners, to facilitate human expansion throughout the solar system and return new knowledge and opportunities to Earth [2]. As part of this trend, there are increasing efforts to utilize science missions in Lunar orbit to develop a non-dedicated and ad-hoc PNT network system. Two traditional approaches, the Deep Space Network (DSN) and the weak signal Global Positioning System (GPS), are established deep-space navigation technologies for missions beyond the geosynchronous orbit. Beginning in 1958, the DSN was developed to communicate with the Explorer 1 spacecraft based on the use of radiometric tracking in spacecraft navigation [3]. The DSN is capable of providing nearly unfettered coverage to spacecraft beyond low-Earth orbit (LEO), however, increased space mission volume has created concerns about future expectations of DSN usage for spacecraft navigation [4]. For cislunar mission applications, the position accuracy using DSN achieves 100 m (3σ) with at least three geometrically diverse ground stations when using radiometric tracking alone [5]. The DSN's dependence on Earth-based ground stations restricts its operational capabilities to periods of Earth visibility. This limitation, coupled with its poor localization performance, renders the DSN unsuitable for future lunar missions that demand continuous tracking and precise positioning. To satisfy the increasing requirements of DSN in Lunar applications, spacecrafts are also required to improve their onboard antenna power and efficiency of the transmission. However, there is an important aggregate cost trade between adding capabilities to every spacecraft and adding to a capacity on the ground that serves multiple spacecraft [6]. A weak GPS system can provide PNT service while the user spacecraft is bound to the Moon, leveraging a single, steerable high gain antenna with the relatively narrow beam which includes all the sources in its field of view [7]. However, the higher the altitude the receiver is above the GPS constellations, the poorer and the weaker are the relative geometry and the received signal powers, respectively, leading to a significant navigation accuracy reduction [8]. The transmitted power becomes weaker with increasing distance from the Earth as well as signals tracked from one of the side lobes of the GPS antenna pattern. As a results, the number of visible satellites and relative geometric condition of the GPS satellites at very high altitude drops dramatically and reduces the navigation solution accuracy. Therefore, the weak GPS system is also not an ideal way to provide PNT service to upcoming Lunar missions when considering its limited geometric condition and the recued navigation accuracy. Another navigation approach on the Moon is being developed, similar to the Global Navigation Satellite System (GNSS) on Earth, aiming to offer navigation service with continuous 24/7 coverage across the entire Lunar surface. For example, lunar communications relay and navigation systems (LCRNS) by NASA and Lunar navigation satellite systems (LNSS) by JAXA are designed to serve as dedicated Position, Navigation, and Timing (PNT) systems for the Moon. However, designing a dedicated LNSS and PNT service involves additional challenges, which are unique to the lunar environment, including limited payload capacity for the CubeSat platform, i.e., the size, weight, and power (SWaP) of the onboard clock, limited lunar ground monitoring stations, and limited financial investment as compared to the legacy Earth-GPS [9]. NASA’s focus on utilizing CubeSat platforms on the Moon leads to an alternative Lunar navigation platform that leverages the existing Lunar science and exploration assets. The small satellites used in Lunar missions can be used to create a low-cost, autonomous, ad-hoc, and on-demand mission-centric Lunar PNT swarm capable of providing PNT services to these low-cost lunar missions [10]. As upcoming Lunar missions will often operate at low-altitude about 30 km to 100 km for scientific observations and mapping purposes, the low-altitude orbital constellations could be employed to create an ad-hoc Lunar PNT system. However, several issues must be addressed, such as the instability of these orbits, which often require maintenance or are only suitable for short-duration missions, operating for fewer than 90 days. Additionally, at an altitude of 100 km, the satellites have a limited period during which they are above the horizon and capable of providing PNT service to users. The implementation of a non-dedicated, ad-hoc Lunar navigation constellation facilitates on-demand PNT services. A preliminary study of ad-hoc Lunar PNT system was conducted using 21 spacecraft in 5,5000 km altitude frozen orbits to test its feasibility and a basic performance of orbital asset localization among ad-hoc Lunar constellations in small satellites format [10]. These swarm assets are designed for autonomous localization with minimal Earth interaction, reducing dependency on bandwidth and ground resources. The design in [10] demonstrated the feasibility of a decentralized PNT approach, specifically employing a DEKF approach for state estimation, which helps minimize onboard operating costs. The DEKF method distributes computation across individual satellites, which lightens the computational load while maintaining accuracy in orbit ephemeris and clock offsets, similar to centralized systems [11]. In a follow-on study [12], each spacecraft was limited to 2 communications antennae, forcing the selection of measurements and scheduling spacecraft activities to perform the measurements. A matching algorithm is implemented to select the best measurements and schedule position estimation updates. The decentralized localization performance is also investigated with increasing levels of network degradation for swarm assets considering the impact of intermittent and permanent communication failure, to demonstrate the robustness and fidelity of the decentralized Lunar PNT service [13]. This study confirmed that the ad-hoc PNT constellations in frozen orbit are highly robust and resilient to communication failures. However, unlike frozen orbit swarm assets, the low-altitude satellites have a limited ground view at an altitude of 100 km, where the ad-hoc Lunar constellation consists of 98 low-altitude satellites, evenly distributed across seven circular polar orbital planes, alongside two satellites in a frozen orbit at an altitude of 5,500 km (Figure 1). Therefore, the number of satellites visible to ground users is significantly limited in low-altitude orbit constellations. As each visibility of a spacecraft remains intact for only a few ticks before it moves out of the field of view, the ground user encounters challenges in maintaining continuous navigation service, resulting in sparse availability and provision of Lunar PNT system. Consequently, service availability is primarily restricted to the Lunar South Pole region (Figure 2). Given these limitations and concerns, the localization performance of low-altitude swarm assets will be assessed in this study. We focus on the investigation of the localization performance of low-altitude swarm assets and ground users near the Lunar South Pole. The overall flow of the Lunar PNT simulation incorporates the DEKF approach of asset localization and the weighted least-squares approach in user localization (Figure 3). The autonomous Lunar PNT simulation is primarily implemented in MATLAB, where the DEKF based on the matching scheduler is implemented with Google’s OR-tools as a model builder and Gurobi optimization tool as a backend solver. The General Mission Analysis Tool (GMAT) is utilized to generate ephemeris data for swarm assets, and accounts for satellite orbital details, mass, and perturbations like solar radiation pressure and drag coefficients. Each ephemeris dataset is produced in the Moon International Celestial Reference Frame (ICRF) inertial coordinate system. For state estimation, the distributed swarm assets rely on two-way Inter-Satellite Link (ISL) measurements, which involve tracking pseudoranges and relative velocities between visible satellites and anchor nodes during each observation. Numerical evaluations of the decentralized localization process are conducted to demonstrate the feasibility of the low-altitude PNT system in providing reliable navigation services. The main approach involves using DEKF and CEKF to localize 100 satellites in low-altitude constellations, where the CEKF is implemented to serve as a baseline for comparing the performance of distributed algorithms. In both cases, we evaluate ‘fully sampled’ measurements from all available assets, and ‘two ISL’ measurements when spacecraft are constrained to have only two antennas. We test four estimation techniques: CEKF fully sampled, CEKF two ISL, DEKF fully sampled, and DEKF two ISL filters. As the DEKF update cycle is comprised of network setup, communication, and computations, a global broadcast network and 2-way ISL network setup will take from 4 to 6 minutes as maximum [12]. In this simulation, the DEKF update cycle is set to 10 minutes, including a 4-minute latency for obtaining and computing the actual measurement updates. We experiment an increased update cycle to demonstrate the feasibility and evaluate the impact on localization performance using various tuning values for measurement noise covariances (Figures 4 and 5). By comparing centralized and decentralized approaches using a matching algorithm, we analyze the influence of cross-correlation factors in the covariance matrix, assuming 100% reliability of all assets and measurements. The increased frequency and the adjustments of tuning parameters reveal distinct error patterns between the two scenarios. The localization accuracy of the swarm assets and ground users is assessed by taking the median error across 100 assets and one ground user (84.9°S, 137.5°E) over 7-day simulation period (Table 1). Since the user localization accuracy is significantly affected by the performance of the swarm assets, it is crucial to maintain high localization accuracy within the swarm. This study will continue to explore decentralized filtering for autonomous LPNT operations, with further investigation of an 'iterative' matching approach which enumerates every valid matching pair, planned for the following month.

Yeji Kim↗