Search NASA⌕ Search

SEARCH · Search NASA

Results for “combinatorial 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 55 records · Page 3

Combinatorial geometry domain decomposition strategies for Monte Carlo simulations

Analysis and modeling of nuclear reactors can lead to memory overload for a single core processor when it comes to refined modeling. A method to solve this problem is called 'domain decomposition'. In the current work, domain decomposition algorithms for a combinatorial geometry Monte Carlo transport code are developed on the JCOGIN (J Combinatorial Geometry Monte Carlo transport INfrastructure). Tree-based decomposition and asynchronous communication of particle information between domains are described in the paper. Combination of domain decomposition and domain replication (particle parallelism) is demonstrated and compared with that of MERCURY code. A full-core reactor model is simulated to verify the domain decomposition algorithms using the Monte Carlo particle transport code JMCT (J Monte Carlo Transport Code), which has being developed on the JCOGIN infrastructure. Besides, influences of the domain decomposition algorithms to tally variances are discussed. (authors)

97 MATHEMATICS AND COMPUTING↗

OpenGraphGym: A Parallel Reinforcement Learning Framework for Graph Optimization Problems

This paper presents an open-source, parallel AI environment (named OpenGraphGym) to facilitate the application of reinforcement learning (RL) algorithms to address combinatorial graph optimization problems. This environment incorporates a basic deep reinforcement learning method, and several graph embeddings to capture graph features, it also allows users to rapidly plug in and test new RL algorithms and graph embeddings for graph optimization problems. This new open-source RL framework is targeted at achieving both high performance and high quality of the computed graph solutions. This RL framework forms the foundation of several ongoing research directions, including 1) benchmark works on different RL algorithms and embedding methods for classic graph problems; 2) advanced parallel strategies for extreme-scale graph computations, as well as 3) performance evaluation on real-world graph solutions.

Zheng, Weijian↗

Using machine learning for particle track identification in the CLAS12 detector

Particle track reconstruction is the most computationally intensive process in nuclear physics experiments. Traditional algorithms use a combinatorial approach that exhaustively tests track measurements ("hits") to identify those that form an actual particle trajectory. In this article, we describe the development of four machine learning (ML) models that assist the tracking algorithm by identifying valid track candidates from the measurements in drift chambers. Several types of machine learning models were tested, including: Convolutional Neural Networks (CNN), Multi-Layer Perceptrons (MLP), Extremely Randomized Trees (ERT) and Recurrent Neural Networks (RNN). As a result of this work, an MLP network classifier was implemented as part of the CLAS12 reconstruction software to provide the tracking code with recommended track candidates. The resulting software achieved accuracy of greater than 99% and resulted in an end-to-end speedup of 35% compared to existing algorithms.

73 NUCLEAR PHYSICS AND RADIATION PHYSICS↗

Approximate Weighted Matching On Emerging Manycore and Multithreaded Architectures

Graph matching is a prototypical combinatorial problem with many applications in computer science and scientific computing, but algorithms for computing optimal matchings are challenging to parallelize. Approximate matching algorithms provide an alternate route for parallelization, and in many contexts compute near-optimal matchings for large-scale graphs. We present sharedmemory parallel implementations for computing half-approximate weighted matching on state-of-the-art multicore (Intel Nehalem and AMD Magny-Cours), manycore (Nvidia Tesla and Nvidia Fermi) and massively multithreaded (Cray XMT) platforms. We provide two implementations: the first implementation uses shared work queues, and is suited to all these platforms; the second implementation is based on dataflow principles, and exploits the architectural features of the Cray XMT. Using a carefully chosen dataset that exhibits characteristics from a wide range of real-world applications, we show scalable performance across different platforms. In particular, for one instance of the input, an R-MAT graph (RMAT-G), we show speedups of: about 32 on 48 cores of an AMD Magny-Cours; 7 on 8 cores of Intel Nehalem; 3 on Nvidia Tesla and 10 on Nvidia Fermi relative to one core of Intel Nehalem; and 60 on 128 processors of Cray XMT. We demonstrate good weak and strong scaling for graphs with up to a billion edges using up to 12, 800 threads. Given the breadth of this work, we focus on simplicity and portability of software rather than excessive fine-tuning for each platform. To the best of our knowledge, this is the first such large-scale study of the half-approximate weighted matching problem on shared-memory platforms. Driven by the critical enabling role of combinatorial algorithms such as matching in scientific computing and the emergence of informatics applications, there is a growing demand to support irregular computations on current and future computing platforms. In this context, we evaluate the capability of emerging multithreaded platforms to tolerate latency induced by irregular memory access patterns, and to support fine-grained parallelism via light-weight synchronization mechanisms. By contrasting the architectural features of these platforms against the Cray XMT, which is specifically designed to support irregular memory-intensive applications, we delineate the impact of these choices on performance.

Halappanavar, Mahantesh↗

Zoltan2

Zoltan2 is a refactoring of the open-source Zoltan library that enables Zoltan users to take better advantage of current and emerging high performance computing architectures and software tools. Like Zoltan, Zoltan2 is a toolkit of combinatorial scientific computing algorithms that enable better performance of scientific codes via improved data locality and parallel scalability. Specifically Zoltan2 partitions data, colors graphs, and orders matrices. Zoltan2 is a software library written in template C++; it supports a wider range of data types and problem sizes than Zoltan. It will be available as part of Sandia's Trilinos framework of scientific computing packages.

Riesen, Lee Ann↗

Consistent Feature Extraction From Vector Fields: Combinatorial Representations and Analysis Under Local Reference Frames

This dissertation presents research on addressing some of the contemporary challenges in the analysis of vector fields—an important type of scientific data useful for representing a multitude of physical phenomena, such as wind flow and ocean currents. In particular, new theories and computational frameworks to enable consistent feature extraction from vector fields are presented. One of the most fundamental challenges in the analysis of vector fields is that their features are defined with respect to reference frames. Unfortunately, there is no single “correct” reference frame for analysis, and an unsuitable frame may cause features of interest to remain undetected, thus creating serious physical consequences. This work develops new reference frames that enable extraction of localized features that other techniques and frames fail to detect. As a result, these reference frames objectify the notion of “correctness” of features for certain goals by revealing the phenomena of importance from the underlying data. An important consequence of using these local frames is that the analysis of unsteady (time-varying) vector fields can be reduced to the analysis of sequences of steady (timeindependent) vector fields, which can be performed using simpler and scalable techniques that allow better data management by accessing the data on a per-time-step basis. Nevertheless, the state-of-the-art analysis of steady vector fields is not robust, as most techniques are numerical in nature. The residing numerical errors can violate consistency with the underlying theory by breaching important fundamental laws, which may lead to serious physical consequences. This dissertation considers consistency as the most fundamental characteristic of computational analysis that must always be preserved, and presents a new discrete theory that uses combinatorial representations and algorithms to provide consistency guarantees during vector field analysis along with the uncertainty visualization of unavoidable discretization errors. Together, the two main contributions of this dissertation address two important concerns regarding feature extraction from scientific data: correctness and precision. The work presented here also opens new avenues for further research by exploring more-general reference frames and more-sophisticated domain discretizations.

97 MATHEMATICS AND COMPUTING↗

Near-Term Application Engineering Challenges in Emerging Superconducting Qudit Processors

We review the prospects to build quantum processors based on superconducting transmons and radiofrequency cavities for testing applications in the NISQ era. We identify engineering opportunities and challenges for implementation of algorithms in simulation, combinatorial optimization, and quantum machine learning in qudit-based quantum computers.

Venturelli, Davide [RIACS, Mtn. View] (ORCID:00000↗

A Review of Quantum Computing Technologies in Power System Optimization

As modern power grids increasingly integrate variable renewable generation, distributed energy resources, and energy storage systems, classical optimization techniques are facing unprecedented challenges. This review examines the emerging application of quantum computing to overcome these challenges in power system optimization, including optimal power flow (OPF), unit commitment (UC), economic dispatch (ED), and intelligent switching and topology optimization (IS-TO). Recent research has introduced various quantum methodologies—such as gate-based, annealing-based, variational algorithms, and quantum-inspired algorithms—to address the combinatorial complexity inherent in grid reconfiguration and energy management. The review summaries the quantum algorithms, quantum devices and the power system test cases, highlighting hybrid quantum–classical strategies that leverage the complementary strengths of both paradigms. Some quantum advantages have been observed, including theoretical speedup, accurate simulation results, scalable qubit usage, efficient QUBO mapping. In particular, the review emphasizes the importance of integrating quantum optimization techniques with classical control frameworks, these hybrid approaches demonstrate the potential to improve real-time grid management and operational reliability. A significant portion of the analysis is devoted to the practical limitations of current quantum devices. Present-day quantum hardware, operating in the noisy intermediate-scale quantum (NISQ) era, remains highly sensitive to noise and limited in qubit connectivity, which constrains the scale and accuracy of implemented algorithms. The review delves into specific challenges such as the need for qubit-efficient encoding techniques and error mitigation strategies that are critical for handling real-world grid optimization problems. In addition, the work draws attention to the performance discrepancies between theoretical quantum speedups and experimental validations, underscoring the importance of rigorous benchmark studies using representative power grid test cases. In summary, this review highlights both the promise and limitations of quantum computing for power system optimization. It provides a comprehensive overview of the state-of-the-art technologies, categorizes recent advancements in algorithm design, and discusses practical considerations for implementation, and serves as an informative resource on current research. Future research directions include developing robust hybrid frameworks, advancing qubit-efficient formulations, and scaling up experimental demonstrations to confirm the theoretical advantages of quantum methods in large-scale power system operations.

24 POWER TRANSMISSION AND DISTRIBUTION↗

New Effective Multithreaded Matching Algorithms

Matching is an important combinatorial problem with a number of applications in areas such as community detection, sparse linear algebra, and network alignment. Since computing optimal matchings can be very time consuming, several fast approximation algorithms, both sequential and parallel, have been suggested. Common to the algorithms giving the best solutions is that they tend to be sequential by nature, while algorithms more suitable for parallel computation give solutions of less quality. We present a new simple 1 2 -approximation algorithm for the weighted matching problem. This algorithm is both faster than any other suggested sequential 1 2 -approximation algorithm on almost all inputs and also scales better than previous multithreaded algorithms. We further extend this to a general scalable multithreaded algorithm that computes matchings of weight comparable with the best sequential algorithms. The performance of the suggested algorithms is documented through extensive experiments on different multithreaded architectures.

matching, parallel algorithms↗

Retrieving Top-k Hyperedge Triplets: Models and Applications

Complex systems frequently exhibit multi-way, rather than pairwise, interactions. These group interactions can- not be faithfully modeled as collections of pairwise interactions using graphs and instead require hypergraphs. However, methods that analyze hypergraphs directly, rather than via lossy graph reductions, remain limited. Hypergraph motifs hold promise in this regard, as motif patterns serve as building blocks for larger group interactions which are inexpressible by graphs. Recent work has focused on categorizing and counting hypergraph motifs based on the existence of nodes in hyperedge intersection regions. Here, we argue that the relative sizes of hyperedge inter- sections within motifs contain varied and valuable information. We propose a suite of efficient algorithms for finding top-k triplets of hyperedges based on optimizing the sizes of these intersection patterns. This formulation uncovers interesting local patterns of interaction, finding hyperedge triplets that either (1) are the least similar with each other, (2) have the highest pairwise but not groupwise correlation, or (3) are the most similar with each other. We formalize this as a combinatorial optimization problem and design efficient algorithms based on filtering hyperedges. Our comprehensive experimental evaluation shows that the resulting hyperedge triplets yield insightful information on real-world hypergraphs. Our approach is also orders of magnitude faster than a naive baseline implementation.

hypergraphs, motifs, Combinatorial Algorithms↗

Learning to Optimize Variational Quantum Circuits to Solve Combinatorial Problems

Quantum computing is a computational paradigm with the potential to outperform classical methods for a variety of problems. Proposed recently, the Quantum Approximate Optimization Algorithm (QAOA) is considered as one of the leading candidates for demonstrating quantum advantage in the near term. QAOA is a variational hybrid quantum-classical algorithm for approximately solving combinatorial optimization problems. The quality of the solution obtained by QAOA for a given problem instance depends on the performance of the classical optimizer used to optimize the variational parameters. In this paper, we formulate the problem of finding optimal QAOA parameters as a learning task in which the knowledge gained from solving training instances can be leveraged to find high-quality solutions for unseen test instances. To this end, we develop two machine-learning-based approaches. Our first approach adopts a reinforcement learning (RL) framework to learn a policy network to optimize QAOA circuits. Our second approach adopts a kernel density estimation (KDE) technique to learn a generative model of optimal QAOA parameters. In both approaches, the training procedure is performed on small-sized problem instances that can be simulated on a classical computer; yet the learned RL policy and the generative model can be used to efficiently solve larger problems. Furthermore, extensive simulations using the IBM Qiskit Aer quantum circuit simulator demonstrate that our proposed RL- and KDE-based approaches reduce the optimality gap by factors up to 30.15 when compared with other commonly used off-the-shelf optimizers.

97 MATHEMATICS AND COMPUTING↗

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

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

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

Quantum computational phase transition in combinatorial problems

Quantum Approximate Optimization algorithm (QAOA) aims to search for approximate solutions to discrete optimization problems with near-term quantum computers. As there are no algorithmic guarantee possible for QAOA to outperform classical computers, without a proof that bounded-error quantum polynomial time (BQP) ≠ nondeterministic polynomial time (NP), it is necessary to investigate the empirical advantages of QAOA. We identify a computational phase transition of QAOA when solving hard problems such as SAT—random instances are most difficult to train at a critical problem density. We connect the transition to the controllability and the complexity of QAOA circuits. Moreover, we find that the critical problem density in general deviates from the SAT-UNSAT phase transition, where the hardest instances for classical algorithms lies. Then, we show that the high problem density region, which limits QAOA’s performance in hard optimization problems (reachability deficits), is actually a good place to utilize QAOA: its approximation ratio has a much slower decay with the problem density, compared to classical approximate algorithms. Indeed, it is exactly in this region that quantum advantages of QAOA over classical approximate algorithms can be identified.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

Heuristic optimization of the scanning path of particle therapy beams

Quasidiscrete scanning is a delivery strategy for proton and ion beam therapy in which the beam is turned off when a slice is finished and a new energy must be set but not during the scanning between consecutive spots. Different scanning paths lead to different dose distributions due to the contribution of the unintended transit dose between spots. In this work an algorithm to optimize the scanning path for quasidiscrete scanned beams is presented. The classical simulated annealing algorithm is used. It is a heuristic algorithm frequently used in combinatorial optimization problems, which allows us to obtain nearly optimal solutions in acceptable running times. A study focused on the best choice of operational parameters on which the algorithm performance depends is presented. The convergence properties of the algorithm have been further improved by using the next-neighbor algorithm to generate the starting paths. Scanning paths for two clinical treatments have been optimized. The optimized paths are found to be shorter than the back-and-forth, top-to-bottom (zigzag) paths generally provided by the treatment planning systems. The gamma method has been applied to quantify the improvement achieved on the dose distribution. Results show a reduction of the transit dose when the optimized paths are used. The benefit is clear especially when the fluence per spot is low, as in the case of repainting. The minimization of the transit dose can potentially allow the use of higher beam intensities, thus decreasing the treatment time. The algorithm implemented for this work can optimize efficiently the scanning path of quasidiscrete scanned particle beams. Optimized scanning paths decrease the transit dose and lead to better dose distributions.

61 RADIATION PROTECTION AND DOSIMETRY↗

Ridge-Valley Graphs: Combinatorial Ridge Detection Using Jacobi Sets

Ridges are one of the key feature of interest in areas such as computer vision and image processing. Even though a significant amount of research has been directed to defining and extracting ridges some fundamental challenges remain. For example, the most popular ridge definition (height ridge) is not invariant under monotonic transformations and its global structure is typically ignored during numerical computations. Furthermore, many existing algorithm are based on numerical heuristics and are rarely guaranteed to produce consistent results. In this paper a small change to the height ridge definition gives a definition that is consistent with the desired invariants. Nevertheless, we show that this definition results in similar structures compared to the most common traditional approach and that both formulations are equivalent for quadratic functions. Furthermore, this definition can be cast in the form of a degenerate Jacobi set, which allows insights into the global structure of ridges. In particular, we introduce the Ridge-Valley graph as the complete description of all ridges in an image. Analyzing this graph reveals similar invariants to those found for traditional ridge formulations, such as the fact that ridges do not merge. Finally, using the connection to Jacobi sets we describe a new combinatorial algorithm to extract the Ridge-Valley graph from sampled images that is guaranteed to produce a valid structure.

97 MATHEMATICS AND COMPUTING↗

Relaxed Multibang Regularization for the Combinatorial Integral Approximation

Multibang regularization and combinatorial integral approximation decompositions are two actively researched techniques for integer optimal control. In this work, we consider a class of polyhedral functions that arise particularly as convex lower envelopes of multibang regularizers and show that they have beneficial properties with respect to regularization of relaxations of integer optimal control problems. We extend the algorithmic framework of the combinatorial integral approximation such that a subsequence of the computed discrete-valued controls converges to the infimum of the regularized integer control problem.

97 MATHEMATICS AND COMPUTING↗

The HEP.TrkX Project: Deep Learning for Particle Tracking

Charged particle reconstruction in dense environments, such as the detectors of the High Luminosity Large Hadron Collider (HL-LHC) is a challenging pattern recognition problem. Traditional tracking algorithms, such as the combinatorial Kalman Filter, have been used with great success in HEP experiments for years. However, these state-of-the-art techniques are inherently sequential and scale quadratically or worse with increased detector occupancy. The HEP.TrkX project is a pilot project with the aim to identify and develop cross-experiment solutions based on machine learning algorithms for track reconstruction. Machine learning algorithms bring a lot of potential to this problem thanks to their capability to model complex non-linear data dependencies, to learn effective representations of high-dimensional data through training, and to parallelize easily on high-throughput architectures such as FPGAs or GPUs. In this paper we present the evolution and performance of our recurrent (LSTM) and convolutional neural networks moving from basic 2D models to more complex models and the challenges of scaling up to realistic dimensionality/sparsity.

Tsaris, Aristeidis↗

The HEP.TrkX Project: deep neural networks for HL-LHC online and offline tracking

Particle track reconstruction in dense environments such as the detectors of the High Luminosity Large Hadron Collider (HL-LHC) is a challenging pattern recognition problem. Traditional tracking algorithms such as the combinatorial Kalman Filter have been used with great success in LHC experiments for years. However, these state-of-the-art techniques are inherently sequential and scale poorly with the expected increases in detector occupancy in the HL-LHC conditions. The HEP.TrkX project is a pilot project with the aim to identify and develop cross-experiment solutions based on machine learning algorithms for track reconstruction. Machine learning algorithms bring a lot of potential to this problem thanks to their capability to model complex non-linear data dependencies, to learn effective representations of high-dimensional data through training, and to parallelize easily on high-throughput architectures such as GPUs. This contribution will describe our initial explorations into this relatively unexplored idea space. Furthermore, we will discuss the use of recurrent (LSTM) and convolutional neural networks to find and fit tracks in toy detector data.

46 INSTRUMENTATION RELATED TO NUCLEAR SCIENCE AND ↗