Search NASA⌕ Search

SEARCH · Search NASA

Results for “generalized 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 289 records · Page 16

The generalized zero-mode supersymmetry scheme and the confluent algorithm

We show the relationship between the mathematical framework used in recent papers by Rosu et al. (2014) [1–3] and the second-order confluent supersymmetric quantum mechanics. In addition, we point out several immediate generalizations of the approach taken in the latter references. Furthermore, it is shown how to apply the generalized scheme to the Dirac and to the Fokker–Planck equation.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

Biased degenerate ground-state sampling of small Ising models with converged quantum approximate optimization algorithm

The quantum alternating operator ansatz, a generalization of the quantum approximate optimization algorithm (QAOA), is a quantum algorithm used for approximately solving combinatorial optimization problems. QAOA typically uses the transverse field mixer as the driving Hamiltonian. One of the interesting properties of the transverse field driving Hamiltonian is that it results in nonuniform sampling of degenerate ground states of optimization problems. In this study, we numerically examine the fair sampling properties of the transverse field mixer QAOA, and Grover mixer QAOA (GM-QAOA), which provides theoretical guarantees of fair sampling of degenerate optimal solutions, up to a large enough p such that the mean expectation value converges to an optimal approximation ratio of 1. This comparison is performed with high-quality heuristically computed, but not necessarily optimal, QAOA angles, which give strictly monotonically improving solution quality as p increases. These angles are computed using the Julia based numerical simulation software JuliQAOA. Fair sampling of degenerate ground states is quantified using the Shannon entropy of the ground-state amplitudes distribution. The fair sampling properties are reported on several quantum signature Hamiltonians from previous quantum annealing fair sampling studies. Small random fully connected spin glasses are shown, which exhibit exponential suppression of some degenerate ground states with transverse field mixer QAOA. The transverse field mixer QAOA simulations show that some problem instances clearly saturate the Shannon entropy of 0 with a maximally biased distribution that occurs when the learning converges to an approximation ratio of 1 while other problem instances never deviate from a maximum Shannon entropy (uniform distribution) at any p step. Published by the American Physical Society 2025

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

Invited Review Article: Measurement uncertainty of linear phase-stepping algorithms

Phase retrieval techniques are widely used in optics, imaging and electronics. Originating in signal theory, they were introduced to interferometry around 1970. Over the years, many robust phase-stepping techniques have been developed that minimize specific experimental influence quantities such as phase step errors or higher harmonic components of the signal. However, optimizing a technique for a specific influence quantity can compromise its performance with regard to others. We present a consistent quantitative analysis of phase measurement uncertainty for the generalized linear phase stepping algorithm with nominally equal phase stepping angles thereby reviewing and generalizing several results that have been reported in literature. All influence quantities are treated on equal footing, and correlations between them are described in a consistent way. For the special case of classical N-bucket algorithms, we present analytical formulae that describe the combined variance as a function of the phase angle values. For the general Arctan algorithms, we derive expressions for the measurement uncertainty averaged over the full 2{pi}-range of phase angles. We also give an upper bound for the measurement uncertainty which can be expressed as being proportional to an algorithm specific factor. Tabular compilations help the reader to quickly assess the uncertainties that are involved with his or her technique.

46 INSTRUMENTATION RELATED TO NUCLEAR SCIENCE AND ↗

A Quantum-Inspired Tensor Network Algorithm for Constrained Combinatorial Optimization Problems

Combinatorial optimization is of general interest for both theoretical study and real-world applications. Fast-developing quantum algorithms provide a different perspective on solving combinatorial optimization problems. In this paper, we propose a quantum-inspired tensor-network-based algorithm for general locally constrained combinatorial optimization problems. Our algorithm constructs a Hamiltonian for the problem of interest, effectively mapping it to a quantum problem, then encodes the constraints directly into a tensor network state and solves the optimal solution by evolving the system to the ground state of the Hamiltonian. We demonstrate our algorithm with the open-pit mining problem, which results in a quadratic asymptotic time complexity. Our numerical results show the effectiveness of this construction and potential applications in further studies for general combinatorial optimization problems.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

An efficient global optimization algorithm for maximizing the sum of two generalized Rayleigh quotients

Maximizing the sum of two generalized Rayleigh quotients (SRQ) can be reformulated as a one-dimensional optimization problem, where the function value evaluations are reduced to solving semi-definite programming (SDP) subproblems. In this paper, we first use the dual SDP subproblem to construct an explicit overestimation and then propose a branch-and-bound algorithm to globally solve (SRQ). Numerical results demonstrate that it is even more efficient than the recent SDP-based heuristic algorithm.

97 MATHEMATICS AND COMPUTING↗

Optimizing adiabatic quantum program compilation using a graph-theoretic framework

Adiabatic quantum computing has evolved in recent years from a theoretical field into an immensely practical area, a change partially sparked by D-Wave System’s quantum annealing hardware. These multimillion-dollar quantum annealers offer the potential to solve optimization problems millions of times faster than classical heuristics, prompting researchers at Google, NASA and Lockheed Martin to study how these computers can be applied to complex real-world problems such as NASA rover missions. Unfortunately, compiling (embedding) an optimization problem into the annealing hardware is itself a difficult optimization problem and a major bottleneck currently preventing widespread adoption. Additionally, while finding a single embedding is difficult, no generalized method is known for tuning embeddings to use minimal hardware resources. To address these barriers, we introduce a graph-theoretic framework for developing structured embedding algorithms. Using this framework, we introduce a biclique virtual hardware layer to provide a simplified interface to the physical hardware. Additionally, we exploit bipartite structure in quantum programs using odd cycle transversal (OCT) decompositions. By coupling an OCT-based embedding algorithm with new, generalized reduction methods, we develop a new baseline for embedding a wide range of optimization problems into fault-free D-Wave annealing hardware. Furthermore, to encourage the reuse and extension of these techniques, we provide an implementation of the framework and embedding algorithms.

97 MATHEMATICS AND COMPUTING↗

Non-Intrusive Parallel-in-Time Solvers for Partial Differential Equations (Final Report)

Many time-dependent problems and simulations are often modeled using Partial Differential Equations. Traditional modeling approaches that use sequential time-stepping are reaching a bottleneck in optimizing efficiency. The Center of Applied Science and Computing at Lawrence Livermore National Laboratory extensively works on parallelizing these algorithms to leverage the increasing computational power from the growing number of processors in computer hardware. In particular, they aim to design non-intrusive algorithms that can generalize to a variety of problems and sizes without requiring additional information from or modifications on the original problems. Multigrid Reduction in Time (MGRIT) is a parallel-in-time algorithm that is designed to be non-intrusive. This project focuses on increasing the efficiency of MGRIT by approximating the coarse-grid operator using machine learning approaches as a means to find the most non-intrusive, or general, solution.

97 MATHEMATICS AND COMPUTING↗

Quantum algorithm for simulating the wave equation

We present a quantum algorithm for simulating the wave equation under Dirichlet and Neumann boundary conditions. The algorithm uses Hamiltonian simulation and quantum linear system algorithms as subroutines. It relies on factorizations of discretized Laplacian operators to allow for polynomially improved scaling in truncation errors and improved scaling for state preparation relative to general purpose quantum algorithms for solving linear differential equations. Relative to classical algorithms for simulating the D-dimensional wave equation, our quantum algorithm achieves exponential space savings and achieves a speedup which is polynomial for fixed D and exponential in D. Furthermore, we also consider using Hamiltonian simulation for Klein-Gordon equations and Maxwell's equations.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

Discrete Event Execution with One-Sided and Two-Sided GVT Algorithms on 216,000 Processor Cores

Global virtual time (GVT) computation is a key determinant of the efficiency and runtime dynamics of parallel discrete event simulations (PDES), especially on large-scale parallel platforms. Here, three execution modes of a generalized GVT computation algorithm are studied on high-performance parallel computing systems: (1) a synchronous GVT algorithm that affords ease of implementation, (2) an asynchronous GVT algorithm that is more complex to implement but can relieve blocking latencies, and (3) a variant of the asynchronous GVT algorithm to exploit one-sided communication in extant supercomputing platforms. Performance results are presented of implementations of these algorithms on up to 216,000 cores of a Cray XT5 system, exercised on a range of parameters: optimistic and conservative synchronization, fine- to medium-grained event computation, synthetic and non-synthetic applications, and different lookahead values. Performance of up to 54 billion events executed per second is registered. Detailed PDES-specific runtime metrics are presented to further the understanding of tightly-coupled discrete event dynamics on massively parallel platforms.

Perumalla, Kalyan S↗

A Particle-Based Conditional Sampling Scheme for the Simulation of Transport in Fractured Rock With Diffusion Into Stagnant Water and Rock Matrix

In situ experiments and field-scale characterization studies have pointed out that, in fractured crystalline media, groundwater flow is highly channelized. This implies that, at the scale of a single fracture, only part of the fracture surface area is in contact with flowing water, while the rest of in-plane water is essentially stagnant and can be accessed by solutes via molecular diffusion. Despite their importance for contaminant retention, to date, there are no numerical or analytical approaches that could be used to assess the implication of stagnant water zones on solute transport in realistic large-scale Discrete Fracture Network-based models. In this study, we present an efficient and flexible algorithm for the simulation of transport in fractured rock with diffusion into stagnant water and rock matrix. The algorithm is a generalization of a previously developed numerical framework for time domain particle tracking in sparsely fractured rock. The key of the generalization is that total time in fracture (τ f ) is first evaluated using a Monte Carlo sampling and then a second sampling is performed conditioned on τ f . The algorithm has been successfully validated against existing independent solutions and the implication of diffusion into stagnant water and secondary diffusion into the matrix has been assessed for a realistic modeling scenario. The results show that, due to diffusion into stagnant water, contaminants are more strongly retarded. This increased retention is more significant for sorbing species, as a larger number of sorption sites is accessible. A high sensitivity to the flowing channel/stagnant water zone geometry has also been observed.

54 ENVIRONMENTAL SCIENCES↗

A general few-projection method for tomographic reconstruction of samples consisting of several distinct materials

We present a method for tomographic reconstruction of objects containing several distinct materials, which is capable of accurately reconstructing a sample from vastly fewer angular projections than required by conventional algorithms. The algorithm is more general than many previous discrete tomography methods, as: (i) a priori knowledge of the exact number of materials is not required; (ii) the linear attenuation coefficient of each constituent material may assume a small range of a priori unknown values. We present reconstructions from an experimental x-ray computed tomography scan of cortical bone acquired at the SPring-8 synchrotron.

62 RADIOLOGY AND NUCLEAR MEDICINE↗

HHL algorithm with mapping function and enhanced sampling for model predictive control in microgrids

Here, this paper presents a refined quantum Harrow Hassidim Lloyd (HHL) algorithm for microgrid control. The first novelty of the developed method is that a mapping shift function enables the original HHL algorithm to handle general linear equations with non-singular and indefinite matrix. Second, a method of Matrix Extension for Amplifying Sampling Probabilities of Intended Solution (ME-ASPI) is proposed to design the reformulated linear algebraic equations, allowing for improved sampling efficiency of the quantum tomography in the refined HHL algorithm. Then, we applied the method to solve the model predictive control (MPC) problem in nonlinear dynamical microgrids. Specifically, with the ME-ASPI method, the refined HHL algorithm can effectively obtain the intended partial optimal control inputs for MPC. The optimization of quadratic programming problem in each time step of MPC is transformed into a linear system problem, which is addressed by the proposed quantum solver through using only partial information, with the time complexity improved from $\mathscr{O}(\mathscr{N}^{2.37286})$ classically to $\mathscr{O}(\mathscr{N}^{2} log \mathscr{N}$ x $p$ log $p)$ in quantum. Numerical examples have validated the effectiveness of the refined HHL algorithm with the proposed mapping function and the ME-ASPI method. By leveraging quantum properties, the proposed method provides a hybrid quantum–classical framework for microgrid control. This generic method can also potentially tackle many other challenges in analyzing and controlling general complex engineered systems.

24 POWER TRANSMISSION AND DISTRIBUTION↗

Three Dimensional Characterization of Defects by Ultrasonic Time-of-Flight Diffraction (ToFD) Technique

Ultrasonic time-of-flight diffraction (ToFD) technique has high accuracy in locating and sizing discontinuities. The primary reason for this accuracy is the use of time instead of amplitude for measurement of the depth and size of discontinuities. Despite the many advantages of ToFD, it suffers from a number of shortcomings, the most notable one being its two-dimensional character. The goal of this paper is to develop an algorithm, as a prerequisite, to extend ToFD measurements to a three-dimensional space. For this purpose, a combination of multiple transmitting and receiving probes is proposed instead of just one pair commonly used in ToFD measurements. The approach for locating and sizing defects in a 3D space follows the methods used in radar and acoustic positioning systems. Non-iterative techniques are used for positioning a single source (defect) based on signals collected by several transducers. The estimation formula, in the form of a closed-form solution, is derived by linear least-squares minimization. In addition to existing conventional passive algorithms, a new active algorithm is also proposed for the general arrangement of transducers. This algorithm is tested on a steel specimen having an artificially implanted discontinuity and the three-dimensional location of the defect is estimated.

42 ENGINEERING↗

Solving PDEs in Irregular Geometries with Multiresolution Methods I: Embedded Dirichlet Boundary Conditions

In this work, we develop and analyze a formalism for solving boundary value problems in arbitrarily-shaped domains using the MADNESS (multiresolution adaptive numerical environment for scientific simulation) package for adaptive computation with multiresolution algorithms. We begin by implementing a previously-reported diffuse domain approximation for embedding the domain of interest into a larger domain (Li et al., 2009 [1]). Numerical and analytical tests both demonstrate that this approximation yields non-physical solutions with zero first and second derivatives at the boundary. This excessive smoothness leads to large numerical cancellation and confounds the dynamically-adaptive, multiresolution algorithms inside MADNESS. We thus generalize the diffuse domain approximation, producing a formalism that demonstrates first-order convergence in both near- and far-field errors. We finally apply our formalism to an electrostatics problem from nanoscience with characteristic length scales ranging from 0.0001 to 300 nm.

99 GENERAL AND MISCELLANEOUS↗

Exact Reconstruction From Uniformly Attenuated Helical Cone-Beam Projections in SPECT

In recent years the development of cone-beam reconstruction algorithms has been an active research area in x-ray computed tomography (CT), and significant progress has been made in the advancement of algorithms. Theoretically exact and computationally efficient analytical algorithms can be found in the literature. However, in single photon emission computed tomography (SPECT), published cone-beam reconstruction algorithms are either approximate or involve iterative methods. The SPECT reconstruction problem is more complicated due to degradations in the imaging detection process, one of which is the effect of attenuation of gamma ray photons. Attenuation should be compensated for to obtain quantitative results. In this paper, an analytical reconstruction algorithm for uniformly attenuated cone-beam projection data is presented for SPECT imaging. The algorithm adopts the DBH method, a procedure consisting of differentiation and backprojection followed by a finite inverse cosh-weighted Hilbert transform. The significance of the proposed approach is that a selected region of interest can be reconstructed even with a detector with a reduced field of view. The algorithm is designed for a general trajectory. However, to validate the algorithm, a numerical study was performed using a helical trajectory. The implementation is efficient and the simulation result is promising.

62 RADIOLOGY AND NUCLEAR MEDICINE↗

Algebraic Algorithms for Betweenness and Percolation Centrality

Abstract In this paper, we explored different ways to write the algebraic version of betweenness centrality algorithm. Particularly, we focused on Brandes' algorithm. We aimed for algebraic betweenness centrality that can be parallelized easily. We proposed 3-tuple geodetic semiring as an extension to the usual geodetic semiring with 2-tuples. Using the 3-tuple geodetic semiring, Dijkstra's and Brandes' algorithm, we wrote more concise and general algebraic betweenness centrality (ABC) algorithm which is valid for weighted and directed graphs. We also proposed an alternative version of ABC using the usual geodetic semiring with 2-tuple where we used a simple way to construct shortest path tree after computing shortest path distances in the usual geodetic semiring. This allows us to avoid computational complexity of ABC implementation using 3-tuple geodetic semiring. We used numba to optimize and parallelize ABC. We evaluated the performance of ABC using 2-tuple geodetic semiring as compared to NetworkX, a common python package for graph algorithms. We did scalability experiments on parallel ABC and showed its total speedup. We also showed that with small modification, ABC can be adapted to algebraicly compute other centrality measures such as percolation centrality.

97 MATHEMATICS AND COMPUTING↗

Coordinated Planning Strategy for Integrated Energy Systems in a District Energy Sector

With the ever-growing integration of diverse distributed energy resources, modern district energy sectors are transitioning into integrated energy systems (IESs), which generally consist of various energy carriers such as electric power, natural gas, and heat. Instead of modeling individual energy carriers, the emergence of IESs requires comprehensive consideration of all involved energy systems in both planning and operation phases. This paper proposes a comprehensive planning strategy for a district energy sector to address the challenges of IES planning considering the coupling of power, gas, and heat systems. The proposed planning model contains an operational module that develops a steady-state optimal multi-energy flow (OMEF) for the IES considered and a multi-stage expansion module that optimizes the investment decisions. To efficiently solve the proposed planning model, which is formulated as a mixed-integer nonlinear programming problem, an improved generalized Benders decomposition algorithm that utilizes dynamic dual multipliers to improve the convergence speed is employed. The effectiveness of the proposed planning model and the feasibility of the improved Benders decomposition algorithm are verified in case studies.

coordinated planning↗