Search NASA⌕ Search

SEARCH · Search NASA

Results for “partitioning 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.

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

At least 577 records · Page 32

Possibilistic clustering for shape recognition

Clustering methods have been used extensively in computer vision and pattern recognition. Fuzzy clustering has been shown to be advantageous over crisp (or traditional) clustering in that total commitment of a vector to a given class is not required at each iteration. Recently fuzzy clustering methods have shown spectacular ability to detect not only hypervolume clusters, but also clusters which are actually 'thin shells', i.e., curves and surfaces. Most analytic fuzzy clustering approaches are derived from Bezdek's Fuzzy C-Means (FCM) algorithm. The FCM uses the probabilistic constraint that the memberships of a data point across classes sum to one. This constraint was used to generate the membership update equations for an iterative algorithm. Unfortunately, the memberships resulting from FCM and its derivatives do not correspond to the intuitive concept of degree of belonging, and moreover, the algorithms have considerable trouble in noisy environments. Recently, the clustering problem was cast into the framework of possibility theory. Our approach was radically different from the existing clustering methods in that the resulting partition of the data can be interpreted as a possibilistic partition, and the membership values may be interpreted as degrees of possibility of the points belonging to the classes. An appropriate objective function whose minimum will characterize a good possibilistic partition of the data was constructed, and the membership and prototype update equations from necessary conditions for minimization of our criterion function were derived. The ability of this approach to detect linear and quartic curves in the presence of considerable noise is shown.

Keller, James M.↗

The Kepler Science Operations Center Pipeline Framework Extensions

The Kepler Science Operations Center (SOC) is responsible for several aspects of the Kepler Mission, including managing targets, generating on-board data compression tables, monitoring photometer health and status, processing the science data, and exporting the pipeline products to the mission archive. We describe how the generic pipeline framework software developed for Kepler is extended to achieve these goals, including pipeline configurations for processing science data and other support roles, and custom unit of work generators that control how the Kepler data are partitioned and distributed across the computing cluster. We describe the interface between the Java software that manages the retrieval and storage of the data for a given unit of work and the MATLAB algorithms that process these data. The data for each unit of work are packaged into a single file that contains everything needed by the science algorithms, allowing these files to be used to debug and evolve the algorithms offline.

Klaus, Todd C.↗

Formal Verification of Safety Properties for Aerospace Systems Through Algorithms Based on Exhaustive State-Space Exploration

The Runway Safety Monitor (RSM) designed by Lockheed Martin is part of NASA's effort to reduce aviation accidents. We developed a Petri net model of the RSM protocol and used the model checking functions of our tool SMART to investigate a number of safety properties in RSM. To mitigate the impact of state-space explosion, we built a highly discretized model of the system, obtained by partitioning the monitored runway zone into a grid of smaller volumes and by considering scenarios involving only two aircraft. The model also assumes that there are no communication failures, such as bad input from radar or lack of incoming data, thus it relies on a consistent view of reality by all participants. In spite of these simplifications, we were able to expose potential problems in the RSM conceptual design. Our findings were forwarded to the design engineers, who undertook corrective action. Additionally, the results stress the efficiency attained by the new model checking algorithms implemented in SMART, and demonstrate their applicability to real-world systems. Attempts to verify RSM with NuSMV and SPIN have failed due to excessive memory consumption.

Ciardo, Gianfranco↗

Electrolyte pore/solution partitioning by expanded grand canonical ensemble Monte Carlo simulation

Using a newly developed grand canonical Monte Carlo approach based on fractional exchanges of dissolved ions and water molecules, we studied equilibrium partitioning of both components between laterally extended apolar confinements and surrounding electrolyte solution. Accurate calculations of the Hamiltonian and tensorial pressure components at anisotropic conditions in the pore required the development of a novel algorithm for a self-consistent correction of nonelectrostatic cut-off effects. At pore widths above the kinetic threshold to capillary evaporation, the molality of the salt inside the confinement grows in parallel with that of the bulk phase, but presents a nonuniform width-dependence, being depleted at some and elevated at other separations. The presence of the salt enhances the layered structure in the slit and lengthens the range of inter-wall pressure exerted by the metastable liquid. Solvation pressure becomes increasingly repulsive with growing salt molality in the surrounding bath. Depending on the sign of the excess molality in the pore, the wetting free energy of pore walls is either increased or decreased by the presence of the salt. Because of simultaneous rise in the solution surface tension, which increases the free-energy cost of vapor nucleation, the rise in the apparent hydrophobicity of the walls has not been shown to enhance the volatility of the metastable liquid in the pores.

37 INORGANIC, ORGANIC, PHYSICAL, AND ANALYTICAL CH↗

Spread-spectrum code acquisition in the presence of Doppler shift and data modulation

A spread-spectrum code acquisition technique for a direct-sequence (DS) system in the presence of Doppler effect and data modulation is investigated. Both the carrier-frequency offset and code-frequency offset due to severe Doppler effect are considered. The code-chip slipping during the correlation process caused by code-frequency offset can degrade the acquisition performance significantly. However, this issue can be alleviated by compensating code-frequency offset in an appropriate manner. Results are presented for the cases with and without data modulation. Coherent detection is considered when there is no data modulation. If data modulation is present, the authors partition the correlation time into subintervals and the integration results in these subintervals are square-law noncoherently combined for detection. The implementation of this code acquisition technique using the fast Fourier transform (FFT) algorithm is described. The use of theoretical results to estimate the hardware complexity of an actual system is illustrated step by step, showing that implementation is feasible with existing technology. The tradeoff between hardware complexity and acquisition performance is discussed.

Cheng, Unjeng↗

Parallel DSMC Solution of Three-Dimensional Flow Over a Finite Flat Plate

This paper describes a parallel implementation of the direct simulation Monte Carlo (DSMC) method. Runtime library support is used for scheduling and execution of communication between nodes, and domain decomposition is performed dynamically to maintain a good load balance. Performance tests are conducted using the code to evaluate various remapping and remapping-interval policies, and it is shown that a one-dimensional chain-partitioning method works best for the problems considered. The parallel code is then used to simulate the Mach 20 nitrogen flow over a finite-thickness flat plate. It is shown that the parallel algorithm produces results which compare well with experimental data. Moreover, it yields significantly faster execution times than the scalar code, as well as very good load-balance characteristics.

Nance, Robert P.↗

Robust Multi-fidelity Bayesian Optimization with Deep Kernel and Partition

Multi-fidelity Bayesian optimization (MFBO) is a powerful approach that utilizes lowfidelity, cost-effective sources to expedite the exploration and exploitation of a high-fidelity objective function. Existing MFBO methods with theoretical foundations either lack justification for performance improvements over single-fidelity optimization or rely on strong assumptions about the relationships between fidelity sources to construct surrogate models and direct queries to low-fidelity sources. To mitigate the dependency on cross-fidelity assumptions while maintaining the advantages of low-fidelity queries, we introduce a random sampling and partition-based MFBO framework with deep kernel learning. This framework is robust to cross-fidelity model misspecification and explicitly illustrates the benefits of low-fidelity queries. Our results demonstrate that the proposed algorithm effectively manages complex cross-fidelity relationships and efficiently optimizes the target fidelity function.

Zhang, Fengxue [University of Chicago, Illinois, U↗

Uncertainty Quantification and Parameter Tuning in the CAM5 Zhang-McFarlane Convection Scheme and Impact of Improved Convection on the Global Circulation and Climate

In this study, we applied an uncertainty quantification (UQ) technique to improve convective precipitation in the global climate model, the Community Atmosphere Model version 5 (CAM5), in which the convective and stratiform precipitation partitioning is very different from observational estimates. We examined the sensitivity of precipitation and circulation to several key parameters in the Zhang-McFarlane deep convection scheme in CAM5, using a stochastic importance-sampling algorithm that can progressively converge to optimal parameter values. The impact of improved deep convection on the global circulation and climate was subsequently evaluated. Our results show that the simulated convective precipitation is most sensitive to the parameters of the convective available potential energy consumption time scale, parcel fractional mass entrainment rate, and maximum downdraft mass flux fraction. Using the optimal parameters constrained by the observed Tropical Rainfall Measuring Mission, convective precipitation improves the simulation of convective to stratiform precipitation ratio and rain-rate spectrum remarkably. When convection is suppressed, precipitation tends to be more confined to the regions with strong atmospheric convergence. As the optimal parameters are used, positive impacts on some aspects of the atmospheric circulation and climate, including reduction of the double Intertropical Convergence Zone, improved East Asian monsoon precipitation, and improved annual cycles of the cross-equatorial jets, are found as a result of the vertical and horizontal redistribution of latent heat release from the revised parameterization. Positive impacts of the optimal parameters derived from the 2 simulations are found to transfer to the 1 simulations to some extent.

CAM5↗

An Approach to Quad Meshing Based On Cross Valued Maps and the Ginzburg-Landau Theory

A generalization of vector fields, referred to as N-direction fields or cross fields when N=4, has been recently introduced and studied for geometry processing, with applications in quadrilateral (quad) meshing, texture mapping, and parameterization. We make the observation that cross field design for two-dimensional quad meshing is related to the well-known Ginzburg-Landau problem from mathematical physics. This identification yields a variety of theoretical tools for efficiently computing boundary-aligned quad meshes, with provable guarantees on the resulting mesh, for example, the number of mesh defects and bounds on the defect locations. The procedure for generating the quad mesh is to (i) find a complex-valued "representation" field that minimizes the Dirichlet energy subject to a boundary constraint, (ii) convert the representation field into a boundary-aligned, smooth cross field, (iii) use separatrices of the cross field to partition the domain into four sided regions, and (iv) mesh each of these four-sided regions using standard techniques. Under certain assumptions on the geometry of the domain, we prove that this procedure can be used to produce a cross field whose separatrices partition the domain into four sided regions. To solve the energy minimization problem for the representation field, we use an extension of the Merriman-Bence-Osher (MBO) threshold dynamics method, originally conceived as an algorithm to simulate motion by mean curvature, to minimize the Ginzburg-Landau energy for the optimal representation field. Lastly, we demonstrate the method on a variety of test domains.

Computational Geometry↗

Limited range spatial load balancing in non-convex environments using sampling-based motion planners

This paper analyzes the limited range, spatial load balancing problem for agents deployed in non-convex environments and subject to differential constraints which restricts how the agents can move. First, the (unlimited range) spatial load balancing problem is introduced and the minimization problem with area constraints is defined. Then, to extend the problem for limited ranges, two cost functions and a sub-partition are defined. The problems are then analyzed and the results prove the existence of a partition that satisfies the area constraints. The non-convex environment makes the problem difficult to solve in continuous-space. Therefore, a probabilistic roadmap is used to approximate agents’ cells via a graph. A distributed algorithm is proven to converge to an approximate solution. Lastly, the convergence of the algorithm is shown in simulation.

42 ENGINEERING↗

Mapping a battlefield simulation onto message-passing parallel architectures

Perhaps the most critical problem in distributed simulation is that of mapping: without an effective mapping of workload to processors the speedup potential of parallel processing cannot be realized. Mapping a simulation onto a message-passing architecture is especially difficult when the computational workload dynamically changes as a function of time and space; this is exactly the situation faced by battlefield simulations. This paper studies an approach where the simulated battlefield domain is first partitioned into many regions of equal size; typically there are more regions than processors. The regions are then assigned to processors; a processor is responsible for performing all simulation activity associated with the regions. The assignment algorithm is quite simple and attempts to balance load by exploiting locality of workload intensity. The performance of this technique is studied on a simple battlefield simulation implemented on the Flex/32 multiprocessor. Measurements show that the proposed method achieves reasonable processor efficiencies. Furthermore, the method shows promise for use in dynamic remapping of the simulation.

Nicol, David M.↗

Automated detection and analysis of particle beams in laser-plasma accelerator simulations

Numerical simulations of laser-plasma wakefield (particle) accelerators model the acceleration of electrons trapped in plasma oscillations (wakes) left behind when an intense laser pulse propagates through the plasma. The goal of these simulations is to better understand the process involved in plasma wake generation and how electrons are trapped and accelerated by the wake. Understanding of such accelerators, and their development, offer high accelerating gradients, potentially reducing size and cost of new accelerators. One operating regime of interest is where a trapped subset of electrons loads the wake and forms an isolated group of accelerated particles with low spread in momentum and position, desirable characteristics for many applications. The electrons trapped in the wake may be accelerated to high energies, the plasma gradient in the wake reaching up to a gigaelectronvolt per centimeter. High-energy electron accelerators power intense X-ray radiation to terahertz sources, and are used in many applications including medical radiotherapy and imaging. To extract information from the simulation about the quality of the beam, a typical approach is to examine plots of the entire dataset, visually determining the adequate parameters necessary to select a subset of particles, which is then further analyzed. This procedure requires laborious examination of massive data sets over many time steps using several plots, a routine that is unfeasible for large data collections. Demand for automated analysis is growing along with the volume and size of simulations. Current 2D LWFA simulation datasets are typically between 1GB and 100GB in size, but simulations in 3D are of the order of TBs. The increase in the number of datasets and dataset sizes leads to a need for automatic routines to recognize particle patterns as particle bunches (beam of electrons) for subsequent analysis. Because of the growth in dataset size, the application of machine learning techniques for scientific data mining is increasingly considered. In plasma simulations, Bagherjeiran et al. presented a comprehensive report on applying graph-based techniques for orbit classification. They used the KAM classifier to label points and components in single and multiple orbits. Love et al. conducted an image space analysis of coherent structures in plasma simulations. They used a number of segmentation and region-growing techniques to isolate regions of interest in orbit plots. Both approaches analyzed particle accelerator data, targeting the system dynamics in terms of particle orbits. However, they did not address particle dynamics as a function of time or inspected the behavior of bunches of particles. Ruebel et al. addressed the visual analysis of massive laser wakefield acceleration (LWFA) simulation data using interactive procedures to query the data. Sophisticated visualization tools were provided to inspect the data manually. Ruebel et al. have integrated these tools to the visualization and analysis system VisIt, in addition to utilizing efficient data management based on HDF5, H5Part, and the index/query tool FastBit. In Ruebel et al. proposed automatic beam path analysis using a suite of methods to classify particles in simulation data and to analyze their temporal evolution. To enable researchers to accurately define particle beams, the method computes a set of measures based on the path of particles relative to the distance of the particles to a beam. To achieve good performance, this framework uses an analysis pipeline designed to quickly reduce the amount of data that needs to be considered in the actual path distance computation. As part of this process, region-growing methods are utilized to detect particle bunches at single time steps. Efficient data reduction is essential to enable automated analysis of large data sets as described in the next section, where data reduction methods are steered to the particular requirements of our clustering analysis. Previously, we have described the application of a set of algorithms to automate the data analysis and classification of particle beams in the LWFA simulation data, identifying locations with high density of high energy particles. These algorithms detected high density locations (nodes) in each time step, i.e. maximum points on the particle distribution for only one spatial variable. Each node was correlated to a node in previous or later time steps by linking these nodes according to a pruned minimum spanning tree (PMST). We call the PMST representation 'a lifetime diagram', which is a graphical tool to show temporal information of high dense groups of particles in the longitudinal direction for the time series. Electron bunch compactness was described by another step of the processing, designed to partition each time step, using fuzzy clustering, into a fixed number of clusters.

43 PARTICLE ACCELERATORS↗

Automated Multiscale Approach To Predict Self-Diffusion from a Potential Energy Field

For large-scale screening studies there is a need to estimate the diffusion of gas molecules in nanoporous materials more efficiently than (brute force) molecular dynamics. In particular for systems with low diffusion coefficients molecular dynamics can be prohibitively expensive. An alternative is to compute the hopping rates between adsorption sites using transition state theory. For large-scale screening this requires the automatic detection of the transition states between the adsorption sites along the different diffusion paths. Here an algorithm is presented that analyzes energy grids for the moving particles. It detects the energies at which diffusion paths are formed, together with their directions. This allows for easy identification of nondiffusive systems. For diffusive systems, it partitions the grid coordinates assigned to energy basins and transitions states, permitting a transition state theory based analysis of the diffusion. We test our method on CH 4 diffusion in zeolites, using a standard kinetic Monte Carlo simulation based on the output of our grid analysis. We find that it is accurate, fast, and rigorous without limitations to the geometries of the diffusion tunnels or transition states.

37 INORGANIC, ORGANIC, PHYSICAL, AND ANALYTICAL CH↗

Evolving bipartite authentication graph partitions

As large scale enterprise computer networks become more ubiquitous, finding the appropriate balance between user convenience and user access control is an increasingly challenging proposition. Suboptimal partitioning of users’ access and available services contributes to the vulnerability of enterprise networks. Previous edge-cut partitioning methods unduly restrict users’ access to network resources. This paper introduces a novel method of network partitioning superior to the current state-of-the-art which minimizes user impact by providing alternate avenues for access that reduce vulnerability. Networks are modeled as bipartite authentication access graphs and a multi-objective evolutionary algorithm is used to simultaneously minimize the size of large connected components while minimizing overall restrictions on network users. Lastly, results are presented on a real world data set that demonstrate the effectiveness of the introduced method compared to previous naive methods.

97 MATHEMATICS AND COMPUTING↗

Designing Metabolic Division of Labor in Microbial Communities

ABSTRACT Microbes face a trade-off between being metabolically independent and relying on neighboring organisms for the supply of some essential metabolites. This balance of conflicting strategies affects microbial community structure and dynamics, with important implications for microbiome research and synthetic ecology. A “gedanken” (thought) experiment to investigate this trade-off would involve monitoring the rise of mutual dependence as the number of metabolic reactions allowed in an organism is increasingly constrained. The expectation is that below a certain number of reactions, no individual organism would be able to grow in isolation and cross-feeding partnerships and division of labor would emerge. We implemented this idealized experiment using in silico genome-scale models. In particular, we used mixed-integer linear programming to identify trade-off solutions in communities of Escherichia coli strains. The strategies that we found revealed a large space of opportunities in nuanced and nonintuitive metabolic division of labor, including, for example, splitting the tricarboxylic acid (TCA) cycle into two separate halves. The systematic computation of possible solutions in division of labor for 1-, 2-, and 3-strain consortia resulted in a rich and complex landscape. This landscape displayed a nonlinear boundary, indicating that the loss of an intracellular reaction was not necessarily compensated for by a single imported metabolite. Different regions in this landscape were associated with specific solutions and patterns of exchanged metabolites. Our approach also predicts the existence of regions in this landscape where independent bacteria are viable but are outcompeted by cross-feeding pairs, providing a possible incentive for the rise of division of labor. IMPORTANCE Understanding how microbes assemble into communities is a fundamental open issue in biology, relevant to human health, metabolic engineering, and environmental sustainability. A possible mechanism for interactions of microbes is through cross-feeding, i.e., the exchange of small molecules. These metabolic exchanges may allow different microbes to specialize in distinct tasks and evolve division of labor. To systematically explore the space of possible strategies for division of labor, we applied advanced optimization algorithms to computational models of cellular metabolism. Specifically, we searched for communities able to survive under constraints (such as a limited number of reactions) that would not be sustainable by individual species. We found that predicted consortia partition metabolic pathways in ways that would be difficult to identify manually, possibly providing a competitive advantage over individual organisms. In addition to helping understand diversity in natural microbial communities, our approach could assist in the design of synthetic consortia.

59 BASIC BIOLOGICAL SCIENCES↗

Space shuttle propulsion parameter estimation using optional estimation techniques

A regression analyses on tabular aerodynamic data provided. A representative aerodynamic model for coefficient estimation. It also reduced the storage requirements for the "normal' model used to check out the estimation algorithms. The results of the regression analyses are presented. The computer routines for the filter portion of the estimation algorithm and the :"bringing-up' of the SRB predictive program on the computer was developed. For the filter program, approximately 54 routines were developed. The routines were highly subsegmented to facilitate overlaying program segments within the partitioned storage space on the computer.

Source record↗

A computational procedure for large rotational motions in multibody dynamics

A computational procedure suitable for the solution of equations of motion for multibody systems is presented. The present procedure adopts a differential partitioning of the translational motions and the rotational motions. The translational equations of motion are then treated by either a conventional explicit or implicit direct integration method. A principal feature of this procedure is a nonlinearly implicit algorithm for updating rotations via the Euler four-parameter representation. This procedure is applied to the rolling of a sphere through a specific trajectory, which shows that it yields robust solutions.

Park, K. C.↗

A simple hydrologically based model of land surface water and energy fluxes for general circulation models

A generalization of the single soil layer variable infiltration capacity (VIC) land surface hydrological model previously implemented in the Geophysical Fluid Dynamics Laboratory (GFDL) general circulation model (GCM) is described. The new model is comprised of a two-layer characterization of the soil column, and uses an aerodynamic representation of the latent and sensible heat fluxes at the land surface. The infiltration algorithm for the upper layer is essentially the same as for the single layer VIC model, while the lower layer drainage formulation is of the form previously implemented in the Max-Planck-Institut GCM. The model partitions the area of interest (e.g., grid cell) into multiple land surface cover types; for each land cover type the fraction of roots in the upper and lower zone is specified. Evapotranspiration consists of three components: canopy evaporation, evaporation from bare soils, and transpiration, which is represented using a canopy and architectural resistance formulation. Once the latent heat flux has been computed, the surface energy balance is iterated to solve for the land surface temperature at each time step. The model was tested using long-term hydrologic and climatological data for Kings Creek, Kansas to estimate and validate the hydrological parameters, and surface flux data from three First International Satellite Land Surface Climatology Project Field Experiment (FIFE) intensive field campaigns in the summer-fall of 1987 to validate the surface energy fluxes.

Liang, XU↗