Search NASA⌕ Search

SEARCH · Search NASA

Results for “partitioned algorithm”

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 271 records · Page 15

Shallow-circuit variational quantum eigensolver based on symmetry-inspired Hilbert space partitioning for quantum chemical calculations

Development of resource-friendly quantum algorithms remains highly desirable for noisy intermediate-scale quantum computing. Based on the variational quantum eigensolver (VQE) with unitary coupled-cluster Ansatz, we demonstrate that partitioning of the Hilbert space made possible by the point-group symmetry of the molecular systems greatly reduces the number of variational operators by confining the variational search within a subspace. In addition, we found that instead of including all subterms for each excitation operator, a single-term representation suffices to reach required accuracy for various molecules tested, resulting in an additional shortening of the quantum circuit by a factor of 4–8. With these strategies, VQE calculations on a noise-free quantum simulator achieve energies within a few meVs of those obtained with the full unitary coupled-cluster Ansatz with single and double excitations for the H 4 -square, H 4 -chain, and H 6 -hexagon molecules, while the number of cnot gates, a measure of the quantum-circuit depth, is reduced by a factor of as large as 35. Furthermore, we introduced an efficient “score” parameter to rank the excitation operators, so that the operators causing larger energy reduction can be applied first. Using the H 4 square and H 4 chain as examples, We demonstrated on noisy quantum simulators that the first few variational operators can bring the energy within the chemical accuracy, while additional operators do not improve the energy since the accumulative noise outweighs the gain from the expansion of the variational Ansatz.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

An adaptive interpolation scheme for molecular potential energy surfaces

The calculation of potential energy surfaces for quantum dynamics can be a time consuming task—especially when a high level of theory for the electronic structure calculation is required. We propose an adaptive interpolation algorithm based on polyharmonic splines combined with a partition of unity approach. The adaptive node refinement allows to greatly reduce the number of sample points by employing a local error estimate. The algorithm and its scaling behavior are evaluated for a model function in 2, 3, and 4 dimensions. The developed algorithm allows for a more rapid and reliable interpolation of a potential energy surface within a given accuracy compared to the non-adaptive version.

37 INORGANIC, ORGANIC, PHYSICAL, AND ANALYTICAL CH↗

Parallel processing for nonlinear dynamics simulations of structures including rotating bladed-disk assemblies

The principal objective of this research is to develop, test, and implement coarse-grained, parallel-processing strategies for nonlinear dynamic simulations of practical structural problems. There are contributions to four main areas: finite element modeling and analysis of rotational dynamics, numerical algorithms for parallel nonlinear solutions, automatic partitioning techniques to effect load-balancing among processors, and an integrated parallel analysis system.

Hsieh, Shang-Hsien↗

A Mountaintop View Requires Minimal Sorting: A Faster Contour Tree Algorithm

Consider a scalar field f : M → R, where M is a triangulated simplicial mesh in R d . A level set, or contour, at value v is a connected component of f –1 (v). As v is changed, these contours change topology, merge into each other, or split. Contour trees are concise representations of f that track this contour behavior. The vertices of these trees are the critical points of f, where the gradient is zero. The edges represent changes in the topology of contours. It is a fundamental data structure in data analysis and visualization, and there is significant previous work (both theoretical and practical) on algorithms for constructing contour trees. Suppose M has n vertices, N facets, and t critical points. A classic result of Carr, Snoeyink, and Axen (2000) gives an algorithm that takes O(n log n+Nα(N)) time (where α(·) is the inverse Ackermann function). A further improvement to O(t log t + N) time was given by Chiang et al. All these algorithms involve a global sort of the critical points, a significant computational bottleneck. Unfortunately, lower bounds of Ω(t log t) also exist. We present the first algorithm that can avoid the global sort and has a refined time complexity that depends on the contour tree structure. Intuitively, if the tree is short and fat, we get significant improvements in running time. For a partition of the contour tree into a set of descending paths, P, our algorithm runs in O($\Sigma$ pϵP |p| log |p| + tα(t) + N). This is at most O(t log D + N), where D is the diameter of the contour tree. Moreover, it is O(tα(t) + N) for balanced trees, a significant improvement over the previous complexity. Our algorithm requires numerous ideas: partitioning the contour tree into join and split trees, a local growing procedure to iteratively build contour trees, and the use of heavy path decompositions for the time complexity analysis. There is a crucial use of a family of binomial heaps to maintain priorities, ensuring that any comparison made is between comparable nodes of the contour tree. We also prove lower bounds showing that the $\Sigma$ pϵP |p| log |p| complexity is inherent to computing contour trees.

97 MATHEMATICS AND COMPUTING↗

Distributed memory compiler methods for irregular problems: Data copy reuse and runtime partitioning

Outlined here are two methods which we believe will play an important role in any distributed memory compiler able to handle sparse and unstructured problems. We describe how to link runtime partitioners to distributed memory compilers. In our scheme, programmers can implicitly specify how data and loop iterations are to be distributed between processors. This insulates users from having to deal explicitly with potentially complex algorithms that carry out work and data partitioning. We also describe a viable mechanism for tracking and reusing copies of off-processor data. In many programs, several loops access the same off-processor memory locations. As long as it can be verified that the values assigned to off-processor memory locations remain unmodified, we show that we can effectively reuse stored off-processor data. We present experimental data from a 3-D unstructured Euler solver run on iPSC/860 to demonstrate the usefulness of our methods.

Das, Raja↗

Control system estimation and design for aerospace vehicles with time delay

The problems of estimation and control of discrete, linear, time-varying systems are considered. Previous solutions to these problems involved either approximate techniques, open-loop control solutions, or results which required excessive computation. The estimation problem is solved by two different methods, both of which yield the identical algorithm for determining the optimal filter. The partitioned results achieve a substantial reduction in computation time and storage requirements over the expanded solution, however. The results reduce to the Kalman filter when no delays are present in the system. The control problem is also solved by two different methods, both of which yield identical algorithms for determining the optimal control gains. The stochastic control is shown to be identical to the deterministic control, thus extending the separation principle to time delay systems. The results obtained reduce to the familiar optimal control solution when no time delays are present in the system.

Allgaier, G. R.↗

TDAG: Tree-based Directed Acyclic Graph Partitioning for Quantum Circuits

We propose the Tree-based Directed Acyclic Graph (TDAG) partitioning for quantum circuits, a novel quantum circuit partitioning method which partitions circuits by viewing them as a series of binary trees and selecting the tree containing the most gates. TDAG produces results of comparable quality (number of partitions) to an existing method called ScanPartitioner (an exhaustive search algorithm) with an 95% average reduction in execution time. Furthermore, TDAG improves compared to a faster partitioning method called QuickPartitioner by 38% in terms of quality of the results with minimal overhead in execution time.

Clark, Joseph↗

Patch-based image segmentation of satellite imagery using minimum spanning tree construction

We present a method for hierarchical image segmentation and feature extraction. This method builds upon the combination of the detection of image spectral discontinuities using Canny edge detection and the image Laplacian, followed by the construction of a hierarchy of segmented images of successively reduced levels of details. These images are represented as sets of polygonized pixel patches (polygons) attributed with spectral and structural characteristics. This hierarchy forms the basis for object-oriented image analysis. To build fine level-of-detail representation of the original image, seed partitions (polygons) are built upon a triangular mesh composed of irregular sized triangles, whose spatial arrangement is adapted to the image content. This is achieved by building the triangular mesh on the top of the detected spectral discontinuities that form a network of constraints for the Delaunay triangulation. A polygonized image is represented as a spatial network in the form of a graph with vertices which correspond to the polygonal partitions and graph edges reflecting pairwise partitions relations. Image graph partitioning is based on the iterative graph oontraction using Boruvka's Minimum Spanning Tree algorithm. An important characteristic of the approach is that the agglomeration of partitions is constrained by the detected spectral discontinuities; thus the shapes of agglomerated partitions are more likely to correspond to the outlines of real-world objects.

97 MATHEMATICS AND COMPUTING↗

A two-level trajectory decomposition algorithm featuring optimal intermediate target selection

A decomposition algorithm is presented that optimizes complex missions by partitioning the trajectory into natural segments such as ascent or entry. Each segment defines a full-rank targeting subproblem. These are solved sequentially using the Newton-Raphson algorithm. The master problem, representing the complete mission, is to determine subproblem targets and master-problem controls that optimize the mission objective subject to intersegment constraints. The gradient projection algorithm solves this problem using derivatives obtained analytically from finite-difference subproblem sensitivities. Thus, the mission is optimized by coordinating the solution of tractible subproblems. Computational results for a synchronous equatorial mission are included.

Petersen, F. M.↗

A two-level trajectory decomposition algorithm featuring optimal intermediate target selection

A decomposition algorithm is presented which optimizes complex missions by partitioning the trajectory into natural segments such as ascent or entry. Each segment defines a full-rank targeting subproblem. These are solved sequentially using the Newton-Raphson algorithm. The master problem, representing the complete mission, is to determine subproblem targets and master-problem controls that optimize the mission objective subject to intersegment constraints. The gradient projection algorithm solves this problem using derivatives obtained analytically from finite-difference subproblem sensitivities. Thus, the mission is optimized by coordinating the solution of tractible subproblems. Computational results for a synchronous equatorial mission are included.

Petersen, F. M.↗

Efficient O(N) integration for all-electron electronic structure calculation using numeric basis functions

We consider the problem of developing O(N) scaling grid-based operations needed in many central operations when performing electronic structure calculations with numeric atom-centered orbitals as basis functions. We outline the overall formulation of localized algorithms, and specifically the creation of localized grid batches. The choice of the grid partitioning scheme plays an important role in the performance and memory consumption of the grid-based operations. Three different top-down partitioning methods are investigated, and compared with formally more rigorous yet much more expensive bottom-up algorithms. We show that a conceptually simple top-down grid partitioning scheme achieves essentially the same efficiency as the more rigorous bottom-up approaches.

97 MATHEMATICS AND COMPUTING↗

Supercooled Liquid Water Detection Capabilities from Ka-Band Doppler Profiling Radars: Moment-Based Algorithm Formulation and Assessment

The occurrence of supercooled liquid water in mixed-phase cloud (MPC) affects their cloud microphysical and radiative properties. The prevalence of MPCs in the mid- and high latitudes translates these effects to significant contributions to Earth’s radiative balance and hydrological cycle. The current study develops and assesses a radar-only, moment-based phase partition technique for the demarcation of supercooled liquid water volumes in arctic, MPC conditions. The study utilizes observations from the Ka band profiling radar, the collocated high spectral resolution lidar, and ambient temperature profiles from radio sounding deployments following a statistical analysis of 5.5 years of data (January 2014–May 2019) from the Atmospheric Radiation Measurement observatory at the North Slope of Alaska. The ice/liquid phase partition occurs via a per-pixel, neighborhood-dependent algorithm based on the premise that the partitioning can be deduced by examining the mean values of locally sampled probability distributions of radar-based observables and then compare those against the means of climatologically derived, per-phase probability distributions. Analyzed radar observables include linear depolarization ratio (LDR), spectral width, and vertical gradients of reflectivity factor and radial velocity corrected for vertical air motion. Results highlight that the optimal supercooled liquid water detection skill levels are realized for the radar variable combination of spectral width and reflectivity vertical gradient, suggesting that radar-based polarimetry, in the absence of full LDR spectra, is not as critical as Doppler capabilities. The cloud phase masking technique is proven particularly reliable when applied to cloud tops with an Equitable Threat Score (ETS) of 65%; the detection of embedded supercooled layers remains much more uncertain (ETS = 27%).

54 ENVIRONMENTAL SCIENCES↗

Specular reflection treatment for the 3D radiative transfer equation solved with the discrete ordinates method

The contribution of this paper relies in the development of numerical algorithms for the mathematical treatment of specular reflection on borders when dealing with the numerical solution of radiative transfer problems. The radiative transfer equation being integro-differential, the discrete ordinates method allows to write down a set of semi-discrete equations in which weights are to be calculated. The calculation of these weights is well known to be based on either a quadrature or on angular discretization, making the use of such method straightforward for the state equation. Also, the diffuse contribution of reflection on borders is usually well taken into account. However, the calculation of accurate partition ratio coefficients is much more tricky for the specular condition applied on arbitrary geometrical borders. This paper presents algorithms that calculate analytically partition ratio coefficients needed in numerical treatments. The developed algorithms, combined with a decentered finite element scheme, are validated with the help of comparisons with analytical solutions before being applied on complex geometries.

97 MATHEMATICS AND COMPUTING↗

Parallel Computing Strategies for Irregular Algorithms

Parallel computing promises several orders of magnitude increase in our ability to solve realistic computationally-intensive problems, but relies on their efficient mapping and execution on large-scale multiprocessor architectures. Unfortunately, many important applications are irregular and dynamic in nature, making their effective parallel implementation a daunting task. Moreover, with the proliferation of parallel architectures and programming paradigms, the typical scientist is faced with a plethora of questions that must be answered in order to obtain an acceptable parallel implementation of the solution algorithm. In this paper, we consider three representative irregular applications: unstructured remeshing, sparse matrix computations, and N-body problems, and parallelize them using various popular programming paradigms on a wide spectrum of computer platforms ranging from state-of-the-art supercomputers to PC clusters. We present the underlying problems, the solution algorithms, and the parallel implementation strategies. Smart load-balancing, partitioning, and ordering techniques are used to enhance parallel performance. Overall results demonstrate the complexity of efficiently parallelizing irregular algorithms.

Biswas, Rupak↗

Constraint treatment techniques and parallel algorithms for multibody dynamic analysis

Computational procedures for kinematic and dynamic analysis of three-dimensional multibody dynamic (MBD) systems are developed from the differential-algebraic equations (DAE's) viewpoint. Constraint violations during the time integration process are minimized and penalty constraint stabilization techniques and partitioning schemes are developed. The governing equations of motion, a two-stage staggered explicit-implicit numerical algorithm, are treated which takes advantage of a partitioned solution procedure. A robust and parallelizable integration algorithm is developed. This algorithm uses a two-stage staggered central difference algorithm to integrate the translational coordinates and the angular velocities. The angular orientations of bodies in MBD systems are then obtained by using an implicit algorithm via the kinematic relationship between Euler parameters and angular velocities. It is shown that the combination of the present solution procedures yields a computationally more accurate solution. To speed up the computational procedures, parallel implementation of the present constraint treatment techniques, the two-stage staggered explicit-implicit numerical algorithm was efficiently carried out. The DAE's and the constraint treatment techniques were transformed into arrowhead matrices to which Schur complement form was derived. By fully exploiting the sparse matrix structural analysis techniques, a parallel preconditioned conjugate gradient numerical algorithm is used to solve the systems equations written in Schur complement form. A software testbed was designed and implemented in both sequential and parallel computers. This testbed was used to demonstrate the robustness and efficiency of the constraint treatment techniques, the accuracy of the two-stage staggered explicit-implicit numerical algorithm, and the speed up of the Schur-complement-based parallel preconditioned conjugate gradient algorithm on a parallel computer.

Chiou, Jin-Chern↗

An efficient implementation of the localized operator partitioning method for electronic energy transfer

The localized operator partitioning method [Y. Khan and P. Brumer, J. Chem. Phys. 137, 194112 (2012)] rigorously defines the electronic energy on any subsystem within a molecule and gives a precise meaning to the subsystem ground and excited electronic energies, which is crucial for investigating electronic energy transfer from first principles. However, an efficient implementation of this approach has been hindered by complicated one- and two-electron integrals arising in its formulation. Using a resolution of the identity in the definition of partitioning, we reformulate the method in a computationally efficient manner that involves standard one- and two-electron integrals. We apply the developed algorithm to the 9 − ((1 − naphthyl) − methyl) − anthracene (A1N) molecule by partitioning A1N into anthracenyl and CH{sub 2} − naphthyl groups as subsystems and examine their electronic energies and populations for several excited states using configuration interaction singles method. The implemented approach shows a wide variety of different behaviors amongst the excited electronic states.

37 INORGANIC, ORGANIC, PHYSICAL, AND ANALYTICAL CH↗

Combinatorial approximation algorithms for MAXCUT using random walks.

We give the first combinatorial approximation algorithm for MaxCut that beats the trivial 0.5 factor by a constant. The main partitioning procedure is very intuitive, natural, and easily described. It essentially performs a number of random walks and aggregates the information to provide the partition. We can control the running time to get an approximation factor-running time tradeoff. We show that for any constant b > 1.5, there is an {tilde O}(n{sup b}) algorithm that outputs a (0.5 + {delta})-approximation for MaxCut, where {delta} = {delta}(b) is some positive constant. One of the components of our algorithm is a weak local graph partitioning procedure that may be of independent interest. Given a starting vertex i and a conductance parameter {phi}, unless a random walk of length {ell} = O(log n) starting from i mixes rapidly (in terms of {phi} and {ell}), we can find a cut of conductance at most {phi} close to the vertex. The work done per vertex found in the cut is sublinear in n.

99 GENERAL AND MISCELLANEOUS↗