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 559 records · Page 31

Recent Advances in PyROS: The Pyomo Solver for Two-Stage Nonconvex Robust Optimization

The slides present recent algorithmic and implementation advances of the two-stage robust optimization (RO) solver PyROS, and a benchmarking study which demonstrates the utility of PyROS for two-stage RO problems. The advances include extensions of the scope of PyROS to models with uncertain variable bounds, improvements to the initializations of the subproblems used by the underlying cutting set algorithm, and extensions of the uncertainty set interfaces. The benchmarking study is performed on a library of over 8,500 instances, with variations in the nonlinearities, degree-of-freedom partitioning, uncertainty sets, and polynomial decision rule approximations. Overall, the results highlight the effectiveness of PyROS for obtaining robust solutions to optimization problems with uncertain equality constraints.

Sherman, Jason↗

Recent Advances in PyROS: The Pyomo Solver for Two-Stage Nonconvex Robust Optimization

The slides present recent algorithmic and implementation advances of the two-stage robust optimization (RO) solver PyROS, and a benchmarking study which demonstrates the utility of PyROS for two-stage RO problems. The advances include extensions of the scope of PyROS to models with uncertain variable bounds, improvements to the initializations of the subproblems used by the underlying cutting set algorithm, and extensions of the uncertainty set interfaces. The benchmarking study is performed on a library of over 8,500 instances, with variations in the nonlinearities, degree-of-freedom partitioning, uncertainty sets, and polynomial decision rule approximations. Overall, the results highlight the effectiveness of PyROS for obtaining robust solutions to optimization problems with uncertain equality constraints.

Sherman, Jason↗

Enabling Efficient Sparse Computations using Linear Algebra Aware Compilers

This project developed the LAPIS compiler framework, built on the Multilevel Intermediate Representation (MLIR), to optimize sparse linear algebra operations and support performance portability across diverse architectures. The main innovation of LAPIS is the Kokkos dialect, which allows for lowering codes from a high productivity language to different architectures in an elegant way. The dialect also allows the conversion of lower-level MLIR code to C++ Kokkos code, facilitating the integration of scientific machine learning (SciML) models into applications. To extend LAPIS for distributed memory architectures, a new partition dialect was created to manage the distribution of sparse tensors and express communication patterns for sparse linear algebra operations. This dialect also supports the distributed execution of operators and includes algorithmic optimizations to minimize communication to improve performance. The project also demonstrates that MLIR can enable effective linear algebra-level optimizations, improving performance on different GPUs for both sparse and dense linear algebra kernels. Key applications of LAPIS include sparse linear algebra and graph kernels, TenSQL, a relational database management solution built on GraphBLAS, and the development of subgraph isomorphism and monomorphism kernels, showcasing performance portability. In summary, the LAPIS framework supports productivity, performance, portability, and distributed memory execution, while also enabling linear algebra-level optimizations that are challenging in traditional programming languages, with successful applications ranging from simple sparse linear algebra to complex graph kernels.

97 MATHEMATICS AND COMPUTING↗

Crossed grid anode and its image partitioning

Measurements on an imaging crossed grid anode following a pair of microchannel plates indicate fast charge propagation via wire-to-wire capacitances, suggesting a temporal resolution of 100 ns. A figure of merit for partitioned systems has been suggested that provides an estimate of the position uncertainty of photoelectrons in the image plane of an anode. Solutions for two-, three-, and four-amplifier position algorithms are given, and basic system requirements are discussed.

Knapp, G.↗

Decentralized hierarchical partitioning of centralized integrated controllers

A framework for a decentralized hierarchical controller partitioning structure is developed. This structure allows for the design of separate airframe and propulsion controllers which, when assembled, will meet the overall design criterion for the integrated airframe/propulsion system. An algorithm based on parameter optimization of the state-space representation for the subsystem controllers is described. The algorithm is currently being applied to an integrated flight propulsion control design example.

Schmidt, Phillip↗

NASA Tech Briefs, March 2013

Topics covered include: Remote Data Access with IDL Data Compression Algorithm Architecture for Large Depth-of-Field Particle Image Velocimeters Vectorized Rebinning Algorithm for Fast Data Down-Sampling Display Provides Pilots with Real-Time Sonic-Boom Information Onboard Algorithms for Data Prioritization and Summarization of Aerial Imagery Monitoring and Acquisition Real-time System (MARS) Analog Signal Correlating Using an Analog-Based Signal Conditioning Front End Micro-Textured Black Silicon Wick for Silicon Heat Pipe Array Robust Multivariable Optimization and Performance Simulation for ASIC Design; Castable Amorphous Metal Mirrors and Mirror Assemblies; Sandwich Core Heat-Pipe Radiator for Power and Propulsion Systems; Apparatus for Pumping a Fluid; Cobra Fiber-Optic Positioner Upgrade; Improved Wide Operating Temperature Range of Li-Ion Cells; Non-Toxic, Non-Flammable, -80 C Phase Change Materials; Soft-Bake Purification of SWCNTs Produced by Pulsed Laser Vaporization; Improved Cell Culture Method for Growing Contracting Skeletal Muscle Models; Hand-Based Biometric Analysis; The Next Generation of Cold Immersion Dry Suit Design Evolution for Hypothermia Prevention; Integrated Lunar Information Architecture for Decision Support Version 3.0 (ILIADS 3.0); Relay Forward-Link File Management Services (MaROS Phase 2); Two Mechanisms to Avoid Control Conflicts Resulting from Uncoordinated Intent; XTCE GOVSAT Tool Suite 1.0; Determining Temperature Differential to Prevent Hardware Cross-Contamination in a Vacuum Chamber; SequenceL: Automated Parallel Algorithms Derived from CSP-NT Computational Laws; Remote Data Exploration with the Interactive Data Language (IDL); Mixture-Tuned, Clutter Matched Filter for Remote Detection of Subpixel Spectral Signals; Partitioned-Interval Quantum Optical Communications Receiver; and Practical UAV Optical Sensor Bench with Minimal Adjustability.

Source record↗

A Comparison of PETSC Library and HPF Implementations of an Archetypal PDE Computation

Two paradigms for distributed-memory parallel computation that free the application programmer from the details of message passing are compared for an archetypal structured scientific computation a nonlinear, structured-grid partial differential equation boundary value problem using the same algorithm on the same hardware. Both paradigms, parallel libraries represented by Argonne's PETSC, and parallel languages represented by the Portland Group's HPF, are found to be easy to use for this problem class, and both are reasonably effective in exploiting concurrency after a short learning curve. The level of involvement required by the application programmer under either paradigm includes specification of the data partitioning (corresponding to a geometrically simple decomposition of the domain of the PDE). Programming in SPAM style for the PETSC library requires writing the routines that discretize the PDE and its Jacobian, managing subdomain-to-processor mappings (affine global- to-local index mappings), and interfacing to library solver routines. Programming for HPF requires a complete sequential implementation of the same algorithm, introducing concurrency through subdomain blocking (an effort similar to the index mapping), and modest experimentation with rewriting loops to elucidate to the compiler the latent concurrency. Correctness and scalability are cross-validated on up to 32 nodes of an IBM SP2.

Hayder, M. Ehtesham↗

Energy cascade with small-scale thermalization, counterflow metastability, and anomalous velocity of vortex rings in Fourier-truncated Gross-Pitaevskii equation

The statistical equilibria of the (conservative) dynamics of the Gross-Pitaevskii equation (GPE) with a finite range of spatial Fourier modes are characterized using a new algorithm, based on a stochastically forced Ginzburg-Landau equation (SGLE), that directly generates grand-canonical distributions. The SGLE-generated distributions are validated against finite-temperature GPE-thermalized states and exact (low-temperature) results obtained by steepest descent on the (grand-canonical) partition function. A standard finite-temperature second-order {lambda} transition is exhibited. A mechanism of GPE thermalization through a direct cascade of energy is found using initial conditions with mass and energy distributed at large scales. A long transient with partial thermalization at small scales is observed before the system reaches equilibrium. Vortices are shown to disappear as a prelude to final thermalization and their annihilation is related to the contraction of vortex rings due to mutual friction. Increasing the amount of dispersion at the truncation wave number is shown to slow thermalization and vortex annihilation. A bottleneck that produces spontaneous effective self-truncation with partial thermalization is characterized in the limit of large dispersive effects. Metastable counterflow states, with nonzero values of momentum, are generated using the SGLE algorithm. Spontaneous nucleation of the vortex ring is observed and the corresponding Arrhenius law is characterized. Dynamical counterflow effects on vortex evolution are investigated using two exact solutions of the GPE: traveling vortex rings and a motionless crystal-like lattice of vortex lines. Longitudinal effects are produced and measured on the crystal lattice. A dilatation of vortex rings is obtained for counterflows larger than their translational velocity. The vortex ring translational velocity has a dependence on temperature that is an order of magnitude above that of the crystal lattice, an effect that is related to the presence of finite-amplitude Kelvin waves. This anomalous vortex ring velocity is quantitatively reproduced by assuming equipartition of energy of the Kelvin waves. Orders of magnitude are given for the predicted effects in weakly interacting Bose-Einstein condensates and superfluid {sup 4}He.

72 PHYSICS OF ELEMENTARY PARTICLES AND FIELDS↗

Exploration of efficient reduced-order modeling and a posteriori error estimation

Efficient algorithms are considered for the computation of a reduced-order model based on the proper orthogonal decomposition methodology for the solution of parameterized elliptic partial differential equations. The method relies on partitioning the parameter space into subdomains based on the properties of the solution space and then forming a reduced basis for each of the subdomains. This yields more efficient offline and online stages for the proper orthogonal decomposition method. We extend these ideas for inexpensive adjoint based a posteriori error estimation of both the expensive finite element method solutions and the reduced-order model solutions, for a single and multiple quantities of interest. Finally, various numerical results indicate the efficacy of the approach.

42 ENGINEERING↗

Learning linear optical circuits with coherent states

We analyze the energy and training data requirements for supervised learning of an M-mode linear optical circuit by minimizing an empirical risk defined solely from the action of the circuit on coherent states. When the linear optical circuit acts non-trivially only on k < M unknown modes (i.e. a linear optical k-junta), we provide an energy-efficient, adaptive algorithm that identifies the junta set and learns the circuit. We compare two schemes for allocating a total energy, E, to the learning algorithm. In the first scheme, each of the T random training coherent states has energy E/T. In the second scheme, a single random MT-mode coherent state with energy E is partitioned into T training coherent states. The latter scheme exhibits a polynomial advantage in training data size sufficient for convergence of the empirical risk to the full risk due to concentration of measure on the $(2MT-1)$-sphere. Specifically, generalization bounds for both schemes are proven, which indicate that for ε-approximation of the full risk by the empirical risk with high probability, $O(E^{2/3}M^{2/3}/\epsilon^{2/3})$ training states are sufficient for the first scheme and $O(E^{1/3}M^{1/3}/\epsilon^{2/3})$ training states are sufficient for the second scheme.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

PROBABILISTIC CROSS-IDENTIFICATION IN CROWDED FIELDS AS AN ASSIGNMENT PROBLEM

One of the outstanding challenges of cross-identification is multiplicity: detections in crowded regions of the sky are often linked to more than one candidate associations of similar likelihoods. We map the resulting maximum likelihood partitioning to the fundamental assignment problem of discrete mathematics and efficiently solve the two-way catalog-level matching in the realm of combinatorial optimization using the so-called Hungarian algorithm. We introduce the method, demonstrate its performance in a mock universe where the true associations are known, and discuss the applicability of the new procedure to large surveys.

79 ASTRONOMY AND ASTROPHYSICS↗

A Large-Grain Mapping Approach for Multiprocessor Systems Through Data Flow Model Ph.D. Thesis

A large-grain level mapping method is presented of numerical oriented applications onto multiprocessor systems. The method is based on the large-grain data flow representation of the input application and it assumes a general interconnection topology of the multiprocessor system. The large-grain data flow model was used because such representation best exhibits inherited parallelism in many important applications, e.g., CFD models based on partial differential equations can be presented in large-grain data flow format, very effectively. A generalized interconnection topology of the multiprocessor architecture is considered, including such architectural issues as interprocessor communication cost, with the aim to identify the 'best matching' between the application and the multiprocessor structure. The objective is to minimize the total execution time of the input algorithm running on the target system. The mapping strategy consists of the following: (1) large-grain data flow graph generation from the input application using compilation techniques; (2) data flow graph partitioning into basic computation blocks; and (3) physical mapping onto the target multiprocessor using a priority allocation scheme for the computation blocks.

Kim, Hwa-Soo↗

Porting Gravitational Wave Signal Extraction to Parallel Virtual Machine (PVM)

Laser Interferometer Space Antenna (LISA) is a planned NASA-ESA mission to be launched around 2012. The Gravitational Wave detection is fundamentally the determination of frequency, source parameters, and waveform amplitude derived in a specific order from the interferometric time-series of the rotating LISA spacecrafts. The LISA Science Team has developed a Mock LISA Data Challenge intended to promote the testing of complicated nested search algorithms to detect the 100-1 millihertz frequency signals at amplitudes of 10E-21. However, it has become clear that, sequential search of the parameters is very time consuming and ultra-sensitive; hence, a new strategy has been developed. Parallelization of existing sequential search algorithms of Gravitational Wave signal identification consists of decomposing sequential search loops, beginning with outermost loops and working inward. In this process, the main challenge is to detect interdependencies among loops and partitioning the loops so as to preserve concurrency. Existing parallel programs are based upon either shared memory or distributed memory paradigms. In PVM, master and node programs are used to execute parallelization and process spawning. The PVM can handle process management and process addressing schemes using a virtual machine configuration. The task scheduling and the messaging and signaling can be implemented efficiently for the LISA Gravitational Wave search process using a master and 6 nodes. This approach is accomplished using a server that is available at NASA Ames Research Center, and has been dedicated to the LISA Data Challenge Competition. Historically, gravitational wave and source identification parameters have taken around 7 days in this dedicated single thread Linux based server. Using PVM approach, the parameter extraction problem can be reduced to within a day. The low frequency computation and a proxy signal-to-noise ratio are calculated in separate nodes that are controlled by the master using message and vector of data passing. The message passing among nodes follows a pattern of synchronous and asynchronous send-and-receive protocols. The communication model and the message buffers are allocated dynamically to address rapid search of gravitational wave source information in the Mock LISA data sets.

Thirumalainambi, Rajkumar↗

A Locally Adaptive Method for Boundary Detection

Edge detection techniques predict boundaries between objects or regions in an image. Many classical methods rely on sharp changes in luminance, chromaticity, or texture, and images without these features are difficult to partition correctly. We present a supervised boundary detection method named Locally Adaptive Discriminant Analysis (LADA) that finds edges in images containing high noise and gradual changes between classes. The user trains the algorithm by providing locations of known materials within the image, but no assumptions are made on the material geometries in the image. The algorithm then uses statistics of anisotropic local data to place each pixel in the most probable class. The algorithm’s success is demonstrated on an optical image of a laser-induced shockwave.

47 OTHER INSTRUMENTATION↗

Post-transition state dynamics and product energy partitioning following thermal excitation of the F∙∙∙HCH 2 CN transition state: Disagreement with experiment

Born-Oppenheimer direct dynamics simulations were performed to study atomistic details of the F + CH 3 CN → HF + CH 2 CN H-atom abstraction reaction. The simulation trajectories were calculated with a combined M06-2X/MP2 algorithm utilizing the 6-311++G** basis set. In accord with experiment and assuming the accuracy of transition state theory (TST), the trajectories were initiated at the F-HCH 2 CN abstraction TS with a 300 K Boltzmann distribution of energy and directed towards products. Recrossing of the TS was negligible, confirming the accuracy of TST for the simulation. HF formation was rapid, occurring within 0.014 ps of the trajectory initiation. The intrinsic reaction coordinate (IRC) for reaction involves rotation of HF about CH 2 CN and then trapping in the CH 2 CN-HF post-reaction potential energy well of ~10 kcal/mol with respect to the HF + CH 2 CN products. In contrast to this IRC, five different trajectory types were observed, with the majority involving direct dissociation and only 11% approximately following the IRC. The HF vibrational and rotational quantum numbers, n and J, were calculated when HF was initially formed and they increase as potential energy is released in forming the HF + CH 2 CN products. The population of the HF product vibrational states is only in qualitative agreement with experiment, with the simulations showing depressed and enhanced populations of the n = 1 and 2 states as compared to experiment. From the simulations and with an anharmonic zero-point energy constraint, the percentage partitioning of the product energy to relative translation, HF rotation, HF vibration, CH 2 CN rotation and CH 2 CN vibration is 5, 11, 60, 7, and 16%, respectively. In contrast the experimental energy partitioning percentages to HF rotation and vibration are 6 and 41%. Comparisons are made between the current simulation and those for other F + H-atom abstraction reactions. The simulation product energy partitioning and HF vibrational population for F + CH 3 CN → HF + CH 2 CN are similar to those for these other reactions. Finally, a detailed discussion is given of possible origins of the difference between the simulation and experimental energy partitioning dynamics for the F + CH 3 CN → HF + CH 2 CN reaction. The F + CH 3 CN reaction also forms the CH 3 C(F)N intermediate, in which the F-atom adds to the C≡N bond. However, this intermediate and the F---CH 3 CN and CH 3 CN-F van der Waals complexes are not expected to affect the F + CH 3 CN → HF + CH 2 CN product energy partitioning.

37 INORGANIC, ORGANIC, PHYSICAL, AND ANALYTICAL CH↗

A Rainbow Coverage Path Planning for a Patrolling Mobile Robot With Circular Sensing Range

In this paper, we proposed a coverage path (CP) planning approach for a mobile robot moving in a dynamically changing environment. Our family of algorithms begins by finding the first path around the center of interior obstacles/disks of a given target region (TR) through the Graham scan algorithm. The first path is then used as a foundational path to generate a collision free, first order differentiable, and observable CP through a complete set of input and output transformation algorithms which together form the rainbow CP planning approach. The last algorithm of the rainbow CP planning approach finds a sufficient number of observation points on the CP needed to observe the TR. The novelty of our rainbow CP planning approach is that it partitions the TR into different shapes with different properties needed to obtain complete coverage while achieving first order path differentiability. The main technical contributions of the proposed approach is to provide a holistic solution that segments any TR, uses triangulation to determine the line of sights and observation points, and computes the collision-free CP within a quadratic runtime. The proposed method can be readily generalized to address problems of higher dimensions, and it is scalable with respect to the size of TR and the number of robots. Computer simulations are used to illustrate the effectiveness and correctness of the proposed approach.

54 ENVIRONMENTAL SCIENCES↗

Efficient parallel architecture for highly coupled real-time linear system applications

A systematic procedure is developed for exploiting the parallel constructs of computation in a highly coupled, linear system application. An overall top-down design approach is adopted. Differential equations governing the application under consideration are partitioned into subtasks on the basis of a data flow analysis. The interconnected task units constitute a task graph which has to be computed in every update interval. Multiprocessing concepts utilizing parallel integration algorithms are then applied for efficient task graph execution. A simple scheduling routine is developed to handle task allocation while in the multiprocessor mode. Results of simulation and scheduling are compared on the basis of standard performance indices. Processor timing diagrams are developed on the basis of program output accruing to an optimal set of processors. Basic architectural attributes for implementing the system are discussed together with suggestions for processing element design. Emphasis is placed on flexible architectures capable of accommodating widely varying application specifics.

Carroll, Chester C.↗

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, we cast the clustering problem 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. We constructed an appropriate objective function whose minimum will characterize a good possibilistic partition of the data, and we derived the membership and prototype update equations from necessary conditions for minimization of our criterion function. In this paper, we show the ability of this approach to detect linear and quartic curves in the presence of considerable noise.

Keller, James M.↗