SEARCH · Search NASA

Results for “decomposition algorithms”

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.

SourceResearch connectionFrom yearThrough year

Quote a phrase for an exact phrase match. Source license links do not imply unrestricted reuse.

At least 415 records · Page 23

All sources NASA NTRS DOE OSTI

DOE OSTI2015

Distributed Flexibility Characterization and Resource Allocation Strategies for Multi-zone Commercial Buildings in the Smart Grid

The HVAC (Heating, Ventilation, and Air- Conditioning) system of commercial buildings is a complex system with a large number of dynamically interacting components. In particular, the thermal dynamics of each zone are coupled with those of the neighboring zones. In this paper, we study a multi-agent based approach to model and control commercial building HVAC system for providing grid services. In the multi-agent system (MAS), individual zones are modeled as agents that can communicate, interact, and negotiate with one another to achieve a common objective. We first propose a distributed characterization method on the aggregated airflow (and thus fan power) flexibility that the HVAC system can provide to the ancillary service market. Then, we propose a Nash-bargaining based airflow allocation strategy to track a dispatch signal (that is within the offered flexibility limit) while respecting the preference and flexibility of individual zones. Moreover, we devise a distributed algorithm to obtain the Nash bargaining solution via dual decomposition and average consensus. Numerical simulations illustrate that the proposed distributed protocols are much more scalable than the centralized approaches especially when the system becomes larger and more complex.

Hao, He↗

NASA NTRS1992

An efficient solution procedure for the thermoelastic analysis of truss space structures

A solution procedure is proposed for the thermal and thermoelastic analysis of truss space structures in periodic motion. In this method, the spatial domain is first descretized using a consistent finite element formulation. Then the resulting semi-discrete equations in time are solved analytically by using Fourier decomposition. Geometrical symmetry is taken advantage of completely. An algorithm is presented for the calculation of heat flux distribution. The method is demonstrated via a numerical example of a cylindrically shaped space structure.

Givoli, D.↗

NASA NTRS1994

Improved Multi-Partition Method for Line-Based Iteration Schemes

Regular 3-dimensional multi-partitioning has been shown to be an efficient domain decomposition method for the parallelization of ADI-type algorithms on MIMD architectures. This paper discusses further improvements that can be made to the scheme that increase the granularity and reduce the communication density. These improvements, which are illustrated by simulation and parallel benchmark results, make multi-partitioning the method of choice on systems with relatively poor communication capabilities, such as networks of workstations, or on massively parallel machines with very fast processors, such as the IBM SP2.

Smith, Merritt H.↗

NASA NTRS1998

A Hybrid Procedural/Deductive Executive for Autonomous Spacecraft

The New Millennium Remote Agent (NMRA) will be the first AI system to control an actual spacecraft. The spacecraft domain places a strong premium on autonomy and requires dynamic recoveries and robust concurrent execution, all in the presence of tight real-time deadlines, changing goals, scarce resource constraints, and a wide variety of possible failures. To achieve this level of execution robustness, we have integrated a procedural executive based on generic procedures with a deductive model-based executive. A procedural executive provides sophisticated control constructs such as loops, parallel activity, locks, and synchronization which are used for robust schedule execution, hierarchical task decomposition, and routine configuration management. A deductive executive provides algorithms for sophisticated state inference and optimal failure recover), planning. The integrated executive enables designers to code knowledge via a combination of procedures and declarative models, yielding a rich modeling capability suitable to the challenges of real spacecraft control. The interface between the two executives ensures both that recovery sequences are smoothly merged into high-level schedule execution and that a high degree of reactivity is retained to effectively handle additional failures during recovery.

Pell, Barney↗

NASA NTRS2003

Aeroservoelastic Model Validation and Test Data Analysis of the F/A-18 Active Aeroelastic Wing

Model validation and flight test data analysis require careful consideration of the effects of uncertainty, noise, and nonlinearity. Uncertainty prevails in the data analysis techniques and results in a composite model uncertainty from unmodeled dynamics, assumptions and mechanics of the estimation procedures, noise, and nonlinearity. A fundamental requirement for reliable and robust model development is an attempt to account for each of these sources of error, in particular, for model validation, robust stability prediction, and flight control system development. This paper is concerned with data processing procedures for uncertainty reduction in model validation for stability estimation and nonlinear identification. F/A-18 Active Aeroelastic Wing (AAW) aircraft data is used to demonstrate signal representation effects on uncertain model development, stability estimation, and nonlinear identification. Data is decomposed using adaptive orthonormal best-basis and wavelet-basis signal decompositions for signal denoising into linear and nonlinear identification algorithms. Nonlinear identification from a wavelet-based Volterra kernel procedure is used to extract nonlinear dynamics from aeroelastic responses, and to assist model development and uncertainty reduction for model validation and stability prediction by removing a class of nonlinearity from the uncertainty.

Brenner, Martin J.↗

NASA NTRS2009

A Framework for Parallel Unstructured Grid Generation for Complex Aerodynamic Simulations

A framework for parallel unstructured grid generation targeting both shared memory multi-processors and distributed memory architectures is presented. The two fundamental building-blocks of the framework consist of: (1) the Advancing-Partition (AP) method used for domain decomposition and (2) the Advancing Front (AF) method used for mesh generation. Starting from the surface mesh of the computational domain, the AP method is applied recursively to generate a set of sub-domains. Next, the sub-domains are meshed in parallel using the AF method. The recursive nature of domain decomposition naturally maps to a divide-and-conquer algorithm which exhibits inherent parallelism. For the parallel implementation, the Master/Worker pattern is employed to dynamically balance the varying workloads of each task on the set of available CPUs. Performance results by this approach are presented and discussed in detail as well as future work and improvements.

Zagaris, George↗

DOE OSTI2024

Tensor decompositions for count data that leverage stochastic and deterministic optimization

There is growing interest to extend low-rank matrix decompositions to multi-way arrays, or tensors. One fundamental low-rank tensor decomposition is the canonical polyadic decomposition (CPD). The challenge of fitting a low-rank, nonnegative CPD model to Poisson-distributed count data is of particular interest. Several popular algorithms use local search methods to approximate the maximum likelihood estimator (MLE) of the Poisson CPD model. Here, this work presents two new algorithms that extend state-of-the-art local methods for Poisson CPD. Hybrid GCP-CPAPR combines Generalized Canonical Decomposition (GCP) with stochastic optimization and CP Alternating Poisson Regression (CPAPR), a deterministic algorithm, to increase the probability of converging to the MLE over either method used alone. Restarted CPAPR with SVDrop uses a heuristic based on the singular values of the CPD model unfoldings to identify convergence toward optimizers that are not the MLE and restarts within the feasible domain of the optimization problem, thus reducing overall computational cost when using a multi-start strategy. We provide empirical evidence that indicates our approaches outperform existing methods with respect to converging to the Poisson CPD MLE.

CPAPR↗

DOE OSTI2018

A Galerkin method with two-dimensional Haar basis functions for the computation of the Karhunen–Loève expansion

We study the numerical approximation of a homogeneous Fredholm integral equation of second kind associated with the Karhunen–Loève expansion of Gaussian random fields. We develop, validate, and discuss an algorithm based on the Galerkin method with two-dimensional Haar wavelets as basis functions. The shape functions are constructed from the orthogonal decomposition of tensor-product spaces of one-dimensional Haar functions, and a recursive algorithm is employed to compute the matrix of the discrete eigenvalue system without the explicit calculation of integrals, allowing the implementation of a fast and efficient algorithm that provides considerable reduction in CPU time, when compared with classical Galerkin methods. Numerical experiments confirm the convergence rate of the method and assess the approximation error and the sparsity of the eigenvalue system when the wavelet expansion is truncated. We illustrate the numerical solution of a diffusion problem with random input data with the present method. In this problem, accuracy was retained after dropping the coefficients below a threshold value that was numerically determined. A similar method with scaling functions rather than wavelet functions does not need a discrete wavelet transform and leads to eigenvalue systems with better conditioning but lower sparsity.

97 MATHEMATICS AND COMPUTING↗

NASA NTRS1993

On the spectral stability of time integration algorithms for a class of constrained dynamics problems

Incomplete field formulations have recently been the subject of intense research because of their potential in coupled analysis of independently modeled substructures, adaptive refinement, domain decomposition, and parallel processing. This paper discusses the design and analysis of time-integration algorithms for these formulations and emphasizes the treatment of their inter-subdomain constraint equations. These constraints are shown to introduce a destabilizing effect in the dynamic system that can be analyzed by investigating the behavior of the time-integration algorithm at infinite and zero frequencies. Three different approaches for constructing penalty-free unconditionally stable second-order accurate solution procedures for this class of hybrid formulations are presented, discussed and illustrated with numerical examples. The theoretical results presented in this paper also apply to a large family of nonlinear multibody dynamics formulations. Some of the algorithms outlined herein are important alternatives to the popular technique consisting of transforming differential/algebraic equations into ordinary differential equations via the introduction of a stabilization term that depends on arbitrary constants and that influences the computed so1ution.

Farhat, Charbel↗

NASA NTRS1996

Integrating a Genetic Algorithm Into a Knowledge-Based System for Ordering Complex Design Processes

The design cycle associated with large engineering systems requires an initial decomposition of the complex system into design processes which are coupled through the transference of output data. Some of these design processes may be grouped into iterative subcycles. In analyzing or optimizing such a coupled system, it is essential to be able to determine the best ordering of the processes within these subcycles to reduce design cycle time and cost. Many decomposition approaches assume the capability is available to determine what design processes and couplings exist and what order of execution will be imposed during the design cycle. Unfortunately, this is often a complex problem and beyond the capabilities of a human design manager. A new feature, a genetic algorithm, has been added to DeMAID (Design Manager's Aid for Intelligent Decomposition) to allow the design manager to rapidly examine many different combinations of ordering processes in an iterative subcycle and to optimize the ordering based on cost, time, and iteration requirements. Two sample test cases are presented to show the effects of optimizing the ordering with a genetic algorithm.

Rogers, James L.↗

DOE OSTI2025

Quantum Algorithms for Representation-Theoretic Multiplicities

Kostka, Littlewood-Richardson, Plethysm, and Kronecker coefficients are the multiplicities of irreducible representations in the decomposition of representations of the symmetric group that play an important role in representation theory, geometric complexity, and algebraic combinatorics. We give quantum algorithms for computing these coefficients whenever the ratio of dimensions of the representations is polynomial. We show that there is an efficient classical algorithm for computing the Kostka numbers under this restriction and conjecture the existence of an analogous algorithm for the Littlewood-Richardson coefficients. We argue why such classical algorithm does not straightforwardly work for the Plethysm and Kronecker coefficients and conjecture that our quantum algorithms lead to superpolynomial speedups. The conjecture about Kronecker coefficients was disproved by Panova [Polynomial time classical versus quantum algorithms for representation theoretic multiplicities, arXiv:2502.20253] with a classical algorithm which, if optimal, points to a 𝒪⁡(𝑛 4+2⁢𝑘 ) vs $\tilde{Ω}$⁡(𝑛 4⁢𝑘 2 +1 ) polynomial gap in quantum vs classical computational complexity for an integer parameter 𝑘.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

DOE OSTI2021

Tuning Multigrid Methods with Robust Optimization and Local Fourier Analysis

Local Fourier analysis is a useful tool for predicting and analyzing the performance of many efficient algorithms for the solution of discretized PDEs, such as multigrid and domain decomposition methods. The crucial aspect of local Fourier analysis is that it can be used to minimize an estimate of the spectral radius of a stationary iteration, or the condition number of a preconditioned system, in terms of a symbol representation of the algorithm. In practice, this is a “minimax” problem, minimizing with respect to solver parameters the appropriate measure of work, which involves maximizing over the Fourier frequency. Often, several algorithmic parameters may be determined by local Fourier analysis in order to obtain efficient algorithms. Analytical solutions to minimax problems are rarely possible beyond simple problems; the status quo in local Fourier analysis involves grid sampling, which is prohibitively expensive in high dimensions. In this paper, we propose and explore optimization algorithms to solve these problems efficiently. Finally, several examples, with known and unknown analytical solutions, are presented to show the effectiveness of these approaches.

97 MATHEMATICS AND COMPUTING↗

NASA NTRS2003

Enhancing and Archiving the APS Catalog of the POSS I

We have worked on two different projects: 1) Archiving the APS Catalog of the POSS I for distribution to NASA's NED at IPAC, SIMBAD in France, and individual astronomers and 2) The automated morphological classification of galaxies. We have completed archiving the Catalog into easily readable binary files. The database together with the software to read it has been distributed on DVD's to the national and international data centers and to individual astronomers. The archived Catalog contains more than 89 million objects in 632 fields in the first epoch Palomar Observatory Sky Survey. Additional image parameters not available in the original on-line version are also included in the archived version. The archived Catalog is also available and can be queried at the APS web site (URL: http://aps.umn.edu) which has been improved with a much faster and more efficient querying system. The Catalog can be downloaded as binary datafiles with the source code for reading it. It is also being integrated into the SkyQuery system which includes the Sloan Digital Sky Survey, 2MASS, and the FIRST radio sky survey. We experimented with different classification algorithms to automate the morphological classification of galaxies. This is an especially difficult problem because there are not only a large number of attributes or parameters and measurement uncertainties, but also the added complication of human disagreement about the adopted types. To solve this problem we used 837 galaxy images from nine POSS I fields at the North Galactic Pole classified by two independent astronomers for which they agree on the morphological types. The initial goal was to separate the galaxies into the three broad classes relevant to issues of large scale structure and galaxy formation and evolution: early (ellipticals and lenticulars), spirals, and late (irregulars) with an accuracy or success rate that rivals the best astronomer classifiers. We also needed to identify a set of parameters derived from the digitized images that separate the galaxies by type. The human eye can easily recognize complicated patterns in images such as spiral arms which can be spotty, blotchy affairs that are difficult for automated techniques. A galaxy image can potentially be described by hundreds of parameters, all of which may have some relation to the morphological type. In the set of initial experiments we used 624 such parameters, in two colors, blue and red. These parameters include the surface brightness and color measured at different radii, ratios of these parameters at different radii, concentration indices, Fourier transforms and wavelet decomposition coefficients. We experimented with three different classes of classification algorithms; decision trees, k-nearest neighbors, and support vector machines (SVM). A range of experiments were conducted and we eventually narrowed the parameters to 23 selected parameters. SVM consistently outperformed the other algorithms with both sets of features. By combining the results from the different algorithms in a weighted scheme we achieved an overall classification success of 86%.

Humphreys, Roberta M.↗

DOE OSTI2019

A Hybrid Approach for Solving Optimization Problems on Small Quantum Computers

Solving larger-sized problems is an important area of research in quantum computing. Designing hybrid quantum-classical algorithms is a promising approach to solving this. We discuss decomposition-based hybrid approaches for solving optimization problems and demonstrate them for applications related to community detection.

97 MATHEMATICS AND COMPUTING↗

NASA NTRSDate not supplied

Direct Reconstruction of Ablative Thermal Protection System Aeroheating Using A Green's Function Approach

A Green’s function inverse heat transfer (IHT) approach is used to reconstruct the surface heating conditions on ablative thermal protection system (TPS) materials from embedded heat flux sensor and temperature probe measurements. The approach models the temperature time-history at the measurement location as a discrete linear system, allowing for the heat flux boundary condition to be recovered directly without the need for time-marching schemes. The effects of material decomposition and pyrolysis gas transport are modeled using an energy source/sink analogue. The performance of the reconstruction approach is analyzed on a 1D test case representative of an atmospheric entry heating scenario. The approach can recover the TPS surface heat flux to within 4% of the input heating condition with a computation time of 2-3 seconds (>3 orders of magnitude faster than current time-marching IHT methods). As a byproduct of the surface heating reconstruction, the algorithm also captures the surface pyrolysis gas mass flux and solid decomposition at multiple through-thickness locations within the TPS.

Kenneth McAfee↗

DOE OSTI2018

Identification of mixed sources with an organic scintillator-based radiation portal monitor

We have developed radionuclide identification algorithms for radiation portal monitor applications. One algorithm uses a spectral angle mapper to match the power spectral density of modified cumulative distribution functions of measured pulse height distributions to reference spectra, while the others rely on the decomposition of the observed spectrum as a linear mixture of known radionuclide spectra. Three algorithms were then tested for their ability to perform on-the-fly radionuclide identification on datasets acquired with a liquid organic scintillator-based pedestrian radiation portal monitor on moving special nuclear material and industrial radiological sources, as well as common medical isotopes. We quantified and compared the relative efficacies of the algorithms considered using F-score analysis. Measured radiation sources included 51 g of highly enriched uranium, 6.6 g of weapons grade plutonium, 241 Am, 133 Ba, 57 Co and 137 Cs sources with activities of several hundred kBq, as well as 260 kBq liquid solution samples of the medical isotopes 99m Tc, 111 In, 67 Ga, 123 I, 131 I, and 201 Tl. We achieved 100% positive identification, for three-second measurements of single sources moving at a source-transit speed of 1.2 m/s. For mixed sources with strongest and weakest sources having no more than a 5:1 ratio of detected counts, encouraging positive identification results were achieved with the un-mixing algorithms. Current radiation portal monitor designs suffer from a high incidence rate of nuisance radiation alarms caused in radiation portal monitor primary screenings by recent nuclear medicine patients and cargo containing large amounts of naturally occurring radioactive materials. Integrating reliable on-the-fly radionuclide identification into the radiation portal monitors could lower the number of nuisance alarms requiring time-consuming secondary inspections.

47 OTHER INSTRUMENTATION↗

DOE OSTI2015

GOTTCHA Database, Version 1

One major challenge in the field of shotgun metagenomics is the accurate identification of the organisms present within the community, based on classification of short sequence reads. Though microbial community profiling methods have emerged to attempt to rapidly classify the millions of reads output from contemporary sequencers, the combination of incomplete databases, similarity among otherwise divergent genomes, and the large volumes of sequencing data required for metagenome sequencing has led to unacceptably high false discovery rates (FDR). Here we present the application of a novel, gene-independent and signature-based metagenomic taxonomic profiling tool with significantly smaller FDR, which is also capable of classifying never-before seen genomes into the appropriate parent taxa.The algorithm is based upon three primary computational phases: (I) genomic decomposition into bit vectors, (II) bit vector intersections to identify shared regions, and (III) bit vector subtractions to remove shared regions and reveal unique, signature regions.In the Decomposition phase, genomic data is first masked to highlight only the valid (non-ambiguous) regions and then decomposed into overlapping 24-mers. The k-mers are sorted along with their start positions, de-replicated, and then prefixed, to minimize data duplication. The prefixes are indexed and an identical data structure is created for the start positions to mimic that of the k-mer data structure.During the Intersection phase -- which is the most computationally intensive phase -- as an all-vs-all comparison is made, the number of comparisons is first reduced by four methods: (a) Prefix restriction, (b) Overlap detection, (c) Overlap restriction, and (d) Result recording. In Prefix restriction, only k-mers of the same prefix are compared. Within that group, potential overlap of k-mer suffixes that would result in a non-empty set intersection are screened for. If such an overlap exists, the region which intersects is first reduced by performing a binary search of the boundary suffixes of the smaller set into the larger set, which defines the limits of the zipper-based intersection process. Rather than recording the actual k-mers of the intersection, another data structure of identical "shape" is created which consists of only bit vectors so that only a 1 or 0 will be stored in the location of the k-mer suffix that was found in the intersection. This reduces the amount of data generated and stored considerably.During the Subtraction phase, relevant intersection bitmasks are first unionized together to form a single bitmask which is then applied over the original genome to reveal only those regions of the genome that are unique. These regions are then exported to disk in FASTA format and used in the application of determining the constituents of an unknown metagenomic community.The DATABASE provided is the result of the algorithm described.

Freitas, Tracey↗

DOE OSTI2015

GOTTCHA Database, Version 1

Freitas, Tracey↗