SEARCH · Engineering Papers

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

SourceResearch connectionFrom yearThrough year

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

At least 73 records · Page 4

All sources NASA NTRS DOE OSTI

DOE OSTI2020

First-principles calculation of the configurational energy density of states for a solid-state ion conductor with a variant of the Wang and Landau algorithm

In this work, a variant of the Wang and Landau algorithm for calculation of the configurational energy density of states is proposed. The algorithm was developed for the purpose of using first-principles simulations, such as density functional theory, to calculate the partition function of disordered sublattices in crystal materials. The expensive calculations of first-principles methods make a parallel algorithm necessary for a practical computation of the configurational energy density of states within a supercell approximation of a solid-state material. The algorithm developed in this work is tested with the two-dimensional (2d) Ising model to bench mark the algorithm and to help provide insight for implementation to a materials science application. Tests with the 2d Ising model revealed that the algorithm has good performance compared to the original Wang and Landau algorithm and the 1/$\textit{t}$ algorithm, in particular the short iteration performance. Further, a proof of convergence is presented within an adiabatic assumption, and the analysis is able to correctly predict the time dependence of the modification factor to the density of states. The algorithm was then applied to the lithium and lanthanum sublattice of the solid-state lithium ion conductor Li 0.5 La 0.5 TiO 3 . This was done to help understand the disordered nature of the lithium and lanthanum. The results find, overall, that the algorithm performs very well for the 2d Ising model and that the results for Li 0.5 La 0.5 TiO 3 are consistent with experiment while providing additional insight into the lithium and lanthanum ordering in the material. The primary result is that the lithium and lanthanum become more mixed between layers along the c axis for increasing temperature. In part, the simulation of the disordered Li 0.5 La 0.5 TiO 3 system serves as a benchmark for what size systems are currently and in the near future practical to calculate with density functional theory methods.

75 CONDENSED MATTER PHYSICS, SUPERCONDUCTIVITY AND↗

DOE OSTI2023

Preliminary IHLW Formulation Algorithm Description

This report documents the initial algorithm that could be used by the Waste Treatment and Immobilization Plant (WTP) in batching high-level waste (HLW) and glass-forming chemicals (GFCs) in the HLW melter feed preparation vessel (MFPV) (HFP-VSL-00001 and -00005). Not all Hanford tank waste can be accommodated by the models developed for this report and significant expansion of the model boundaries could be achievable to reduce the WTP mission life and total canister production count. The immobilized HLW (IHLW) must meet a series of constraints to be acceptable for disposal in the Monitored Geologic Repository, which are contained in the Specification 1 of the Contract (DOE 2000), the Waste Acceptance Product Specifications (WAPS, DOE 1996), and the Waste Acceptance System Requirements Document (WASRD, DOE 2007). The IHLW Waste Form Compliance Plan (WCP, 24590-HLW-PL-RT-07-0001, Rev 3) specifies that the formulation algorithm will be developed and used to comply with the constraints associated with glass composition and properties. This report is not an engineering calculation, does not provide design input, and is not an engineering study. Algorithm inputs include the chemical analyses of the blended HLW in the HLW blend vessel (HBV) (HLP-VSL-00028, the volume and composition of the MFPV heel, the volume and composition of the MFPV after waste addition, the volume and composition of MFPV batch after GFC addition, the compositions of individual GFCs, and the mass of glass in each canister. In addition to these inputs, uncertainties in the HLW composition and processing parameters are included in the algorithm. Using the above inputs, the algorithm calculates the following outputs: 1) the volume of HLW to be transferred from the HBV to the MFPV, 2) the mass of each GFC for addition to the MFPV, 3) the composition of the glass that will be produced along with uncertainties, and 4) the predicted properties, with associated uncertainties, of the resulting IHLW. The algorithm uses the property-composition models to calculate properties with associated uncertainties and compares them with various constraints to ensure that a processable feed is formulated and a compliant IHLW is produced. The GFC additions are determined using an optimization approach to provide high confidence that the HLW glass will meet all product quality requirements and key processing constraints. For most HLW batches there are many possible glass compositions that meet all constraints. In these cases, the glass composition is optimized for a series of target component concentrations and target property values. The algorithm also incorporates process measurement and product quality uncertainties, based on the work of Piepel et al. (2005). Estimates of the various process and measurement uncertainties that affect glass compositions and predicted glass properties have been previously reported (Piepel et al. 2005, 2006) and the impacts of these estimated uncertainties on the IHLW composition envelope that meets product quality and processing-related properties with sufficient confidence were evaluated. The details of work performed to date to develop this initial GFC addition and batching algorithm are summarized in Sections 4 and 5. An example data set is used to illustrate the calculations of the algorithm summarized in Section 6. Finally, in Section 7, there is a statement of the required work to achieve a final operational IHLW formulation control algorithm. This report is not an engineering calculation, does not provide design input, and is not an engineering study.

12 MANAGEMENT OF RADIOACTIVE AND NON-RADIOACTIVE W↗

DOE OSTI2024

Efficient First-Order Algorithms for Large-Scale, Non-Smooth Maximum Entropy Models with Application to Wildfire Science

Maximum entropy (MaxEnt) models are a class of statistical models that use the maximum entropy principle to estimate probability distributions from data. Due to the size of modern data sets, MaxEnt models need efficient optimization algorithms to scale well for big data applications. State-of-the-art algorithms for MaxEnt models, however, were not originally designed to handle big data sets; these algorithms either rely on technical devices that may yield unreliable numerical results, scale poorly, or require smoothness assumptions that many practical MaxEnt models lack. In this paper, we present novel optimization algorithms that overcome the shortcomings of state-of-the-art algorithms for training large-scale, non-smooth MaxEnt models. Our proposed first-order algorithms leverage the Kullback–Leibler divergence to train large-scale and non-smooth MaxEnt models efficiently. For MaxEnt models with discrete probability distribution of n elements built from samples, each containing m features, the stepsize parameter estimation and iterations in our algorithms scale on the order of O(mn) operations and can be trivially parallelized. Moreover, the strong ℓ1 convexity of the Kullback–Leibler divergence allows for larger stepsize parameters, thereby speeding up the convergence rate of our algorithms. To illustrate the efficiency of our novel algorithms, we consider the problem of estimating probabilities of fire occurrences as a function of ecological features in the Western US MTBS-Interagency wildfire data set. Our numerical results show that our algorithms outperform the state of the art by one order of magnitude and yield results that agree with physical models of wildfire occurrence and previous statistical analyses of wildfire drivers.

Physics↗

DOE OSTI2022

Integrating a ponderomotive guiding center algorithm into a quasi-static particle-in-cell code based on azimuthal mode decomposition

High fidelity modeling of plasma based acceleration (PBA) requires the use of three dimensional, fully nonlinear, and kinetic descriptions based on the particle-in-cell (PIC) method. In PBA an intense particle beam or laser (driver) propagates through a tenuous plasma whereby it excites a plasma wave wake. Three-dimensional PIC algorithms based on the quasi-static approximation (QSA) have been successfully applied to efficiently model the interaction between relativistic charged particle beams and plasma. In a QSA PIC algorithm, the plasma response to a charged particle beam or laser driver is calculated based on forces from the driver and self-consistent forces from the QSA form of Maxwell's equations. These fields are then used to advance the charged particle beam or laser forward by a large time step. Since the time step is not limited by the regular Courant-Friedrichs-Lewy (CFL) condition that constrains a standard 3D fully electromagnetic PIC code, a 3D QSA PIC code can achieve orders of magnitude speedup in performance. Recently, a new hybrid QSA PIC algorithm that combines another speedup technique known as an azimuthal Fourier decomposition has been proposed and implemented. This hybrid algorithm decomposes the electromagnetic fields, charge and current density into azimuthal harmonics and only the Fourier coefficients need to be updated, which can reduce the algorithmic complexity of a 3D code to that of a 2D code. Modeling the laser-plasma interaction in a full 3D electromagnetic PIC algorithm is very computationally expensive due the enormous disparity of physical scales to be resolved. In the QSA the laser is modeled using the ponderomotive guiding center (PGC) approach. We describe how to implement a PGC algorithm compatible for the QSA PIC algorithms based on the azimuthal mode expansion. Here this algorithm permits time steps orders of magnitude larger than the cell size and it can be asynchronously parallelized. Details on how this is implemented into the QSA PIC code that utilizes an azimuthal mode expansion, QPAD, are also described. Benchmarks and comparisons between a fully 3D explicit PIC code (OSIRIS), as well as a few examples related to laser wakefield acceleration, are presented.

97 MATHEMATICS AND COMPUTING↗

DOE OSTI2021

Grand Unification of Quantum Algorithms

Quantum algorithms offer significant speed-ups over their classical counterparts for a variety of problems. The strongest arguments for this advantage are borne by algorithms for quantum search, quantum phase estimation, and Hamiltonian simulation, which appear as subroutines for large families of composite quantum algorithms. A number of these quantum algorithms have recently been tied together by a novel technique known as the quantum singular value transformation (QSVT), which enables one to perform a polynomial transformation of the singular values of a linear operator embedded in a unitary matrix. In the seminal GSLW’19 paper on the QSVT [Gilyén et al., ACM STOC 2019], many algorithms are encompassed, including amplitude amplification, methods for the quantum linear systems problem, and quantum simulation. Here, we provide a pedagogical tutorial through these developments, first illustrating how quantum signal processing may be generalized to the quantum eigenvalue transform, from which the QSVT naturally emerges. Paralleling GSLW’19, we then employ the QSVT to construct intuitive quantum algorithms for search, phase estimation, and Hamiltonian simulation, and also showcase algorithms for the eigenvalue threshold problem and matrix inversion. This overview illustrates how the QSVT is a single framework comprising the three major quantum algorithms, suggesting a grand unification of quantum algorithms.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

DOE OSTI2021

Evaluation of KDP Estimation Algorithm Performance in Rain Using a Known-Truth Framework

Accurate estimation of specific differential phase ( K DP ) is necessary for rain rate estimation, attenuation correction, and hydrometeor classification algorithms. There are numerous published methods to process polarimetric radar observations of propagation differential phase shift (Φ DP ) and estimate K DP , but the corresponding K DP estimate uncertainty is unquantified. This study provides guidance on how commonly used K DP estimation algorithms perform in various environments. Here, we create numerous synthetic (“true”) K DP profiles, integrate over them to obtain “smoothed” Φ DP , and then add noise typical of S-band operational weather radar measurements. Each algorithm is applied to our noisy Φ DP profiles and compared to the true K DP profile such that the errors and uncertainty are quantified. The synthetic K DP profiles are Gaussian in shape, which allows systematic variations in their magnitude and width to determine how each algorithm performs in smooth, slowly changing K DP profiles, as well as steep profiles. Results demonstrate that algorithm performance is dependent on the Φ DP field received. These results are further supported by an error analysis of each algorithm for two more complicated synthetic K DP profiles. Some K DP algorithms allow users to change various tuning parameters; a subset of these tuning parameters is tested to provide guidance on how changing these parameters impacts algorithm performance. We then provide evidence that our known-truth framework provides insight into algorithm performance in observed data through two case studies.

54 ENVIRONMENTAL SCIENCES↗

DOE OSTI2023

Sensitivity analysis of an automated fault detection algorithm for residential air-conditioning systems

The state of the art of fault detection and diagnosis (FDD) for residential air-conditioning systems is expensive and not yet amenable to widespread implementation. FDD for homes can significantly reduce utility costs, and increase the lifespan of the equipment. The cost barriers currently, however, make FDD for homes economically unviable for large scale implementation. In prior work, we offered a solution to reduce FDD costs by proposing an automated fault detection algorithm to serve as a screening step before more expensive FDD tests can be conducted. The algorithm uses only the home thermostat and local weather information to identify thermodynamic parameters and detect high-impact air-conditioning faults, including those that occur during equipment installation. We had tested the algorithm on a single EnergyPlus™ model of a home in Orlando, Florida. The thermodynamic parameter identification process is highly nonconvex involving several local optimal solutions. In this paper we propose a novel method to select the best model for fault detection from among the list of local optimal solutions to make the algorithm more robust to homes of different construction, without which the fault detection process would be infeasible. Another unique contribution of the paper is implementing the solution on real-world data. We also bring the algorithm closer to market by testing it on real-world data. We implement the algorithm on data obtained from experiments conducted by the Florida Solar Energy Center (FSEC) on a laboratory home equipped with a heat pump where faults were intentionally added for a period of seven months. The algorithm successfully detected an undercharge fault with 70.6% accuracy, concurrent duct leakage and undercharge faults with 85.2% accuracy, and duct leakage faults with 69.1% accuracy. A sensitivity analysis is also performed on EnergyPlus models of nine types of homes that vary in construction to demonstrate the robustness of the algorithm. Finally, the algorithm achieves an average accuracy of 71% for no-fault condition, 77% for 40% undercharge fault, and 76% for duct-leak fault.

32 ENERGY CONSERVATION, CONSUMPTION, AND UTILIZATI↗

DOE OSTI2023

Performance evaluation of cosmic ray muon trajectory estimation algorithms

Muons, being elementary particles with minimal interaction with nuclear materials and abundant at sea level, have sparked interest in utilizing them for imaging various applications, such as mining [Borselli et al., Sci. Rep. 12, 22329 (2022)], volcano imaging [Nagamine et al., Nucl. Instrum. Meth. A, 356, 585(1995)], and underground tunnel detection [Guardincerri et al., Pure Appl. Geophys. 174, 2133 (2017)]. Recently, their use in nuclear nonproliferation and safeguard verification has gained attention, particularly in cargo screening for nuclear waste smuggling [Baesso et al., J. Instrum. 9, C10041 (2014)], source localization [L. J. Schultz et al., Nucl. Instrum. Meth. A 519, 687 (2004)], and locating nuclear fuel debris in reactors [Borozdin et al., Phys. Rev. Let. 109, 152501 (2012)]. However, the resolution of muon image reconstruction techniques is limited due to multiple Coulomb scattering (MCS) within the target object. To achieve robust muon tomography, it is crucial to develop efficient and flexible physics-based algorithms that can model the MCS process accurately and estimate the most probable trajectory of muons as they pass through the target object. To address this limitation, in this study, a novel algorithmic approach utilizing the Bayesian probability theory and Gaussian approximation of MCS is chosen. Different energy levels, materials, and target sizes were considered in the evaluations. The results demonstrate that the Generalized Muon Trajectory Estimation (GMTE) algorithm offers significant improvements over currently used algorithms. Across all test scenarios, the GMTE algorithm demonstrated ~50% and 38% increase in precision compared to Straight Line Path (SLP) and Point of Closest Approach (PoCA) algorithms, respectively. Furthermore, it exhibited 10%–35% and 10%–15% increases in muon flux utilization for high and medium Z materials, respectively, compared to the PoCA algorithm. In conclusion, the extensive simulations confirm the enhanced performance and efficiency of the GMTE algorithm, offering improved resolution and reduced measurement time for cosmic ray muon imaging compared to the current SLP and PoCA algorithms.

79 ASTRONOMY AND ASTROPHYSICS↗

DOE OSTI2021

High-precision quantum algorithms for partial differential equations

Quantum computers can produce a quantum encoding of the solution of a system of differential equations exponentially faster than a classical algorithm can produce an explicit description. However, while high-precision quantum algorithms for linear ordinary differential equations are well established, the best previous quantum algorithms for linear partial differential equations (PDEs) have complexity poly(1/ϵ), where ϵ is the error tolerance. By developing quantum algorithms based on adaptive-order finite difference methods and spectral methods, we improve the complexity of quantum algorithms for linear PDEs to be poly(d,log(1/ϵ)), where d is the spatial dimension. Our algorithms apply high-precision quantum linear system algorithms to systems whose condition numbers and approximation errors we bound. We develop a finite difference algorithm for the Poisson equation and a spectral algorithm for more general second-order elliptic equations.

97 MATHEMATICS AND COMPUTING↗

DOE OSTI2022

Hybrid quantum-classical algorithms for approximate graph coloring

We show how to apply the recursive quantum approximate optimization algorithm (RQAOA) to MAX- k -CUT, the problem of finding an approximate k -vertex coloring of a graph. We compare this proposal to the best known classical and hybrid classical-quantum algorithms. First, we show that the standard (non-recursive) QAOA fails to solve this optimization problem for most regular bipartite graphs at any constant level p : the approximation ratio achieved by QAOA is hardly better than assigning colors to vertices at random. Second, we construct an efficient classical simulation algorithm which simulates level- 1 QAOA and level- 1 RQAOA for arbitrary graphs. In particular, these hybrid algorithms give rise to efficient classical algorithms, and no benefit arising from the use of quantum mechanics is to be expected. Nevertheless, they provide a suitable testbed for assessing the potential benefit of hybrid algorithm: We use the simulation algorithm to perform large-scale simulation of level- 1 QAOA and RQAOA with up to 300 qutrits applied to ensembles of randomly generated 3 -colorable constant-degree graphs. We find that level- 1 RQAOA is surprisingly competitive: for the ensembles considered, its approximation ratios are often higher than those achieved by the best known generic classical algorithm based on rounding an SDP relaxation. This suggests the intriguing possibility that higher-level RQAOA may be a potentially useful algorithm for NISQ devices.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

DOE OSTI2025

Resilience–runtime tradeoff relations for quantum algorithms

Abstract A leading approach to algorithm design aims to minimize the number of operations in an algorithm’s compilation. One intuitively expects that reducing the number of operations may decrease the chance of errors. This paradigm is particularly prevalent in quantum computing, where gates are hard to implement and noise rapidly decreases a quantum computer’s potential to outperform classical computers. Here, we find that minimizing the number of operations in a quantum algorithm can be counterproductive, leading to a noise sensitivity that induces errors when running the algorithm in non-ideal conditions. To show this, we develop a framework to characterize the resilience of an algorithm to perturbative noises (including coherent errors, dephasing, and depolarizing noise). Some compilations of an algorithm can be resilient against certain noise sources while being unstable against other noises. We condense these results into a tradeoff relation between an algorithm’s number of operations and its noise resilience. We also show how this framework can be leveraged to identify compilations of an algorithm that are better suited to withstand certain noises.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

DOE OSTI2020

Finite spatial-grid effects in energy-conserving particle-in-cell algorithms

Finite-grid (or aliasing) instabilities are pervasive in particle-in-cell (PIC) plasma simulation algorithms, and force the modeler to resolve the smallest (Debye) length scale in the problem regardless of dynamical relevance. These instabilities originate in the aliasing of interpolation errors between mesh quantities and particles (which live in the space–time continuum). Recently, strictly energy-conserving PIC (EC-PIC) algorithms have been developed that promise enhanced robustness against aliasing instabilities. In this study, we confirm by analysis that EC-PIC is stable against aliasing instabilities for stationary plasmas. For drifting plasmas, we demonstrate by analysis and numerical experiments that, while EC-PIC algorithms are not free from these instabilities in principle, they feature a benign stability threshold for finite-temperature plasmas that make them usable in practice for a large class of problems (featuring ambipolarity and realistic ion-electron mass ratios) without the need to consider the size of the Debye length. We also demonstrate that this threshold is absent for the popular momentum-conserving PIC algorithms, which are therefore unstable for both drifting and stationary plasmas beyond a threshold in cell size compared to Debye length. Finite-grid (or aliasing) instabilities are pervasive in particle-in-cell (PIC) plasma simulation algorithms, and force the modeler to resolve the smallest (Debye) length scale in the problem regardless of dynamical relevance. These instabilities originate in the aliasing of interpolation errors between mesh quantities and particles (which live in the space–time continuum). Recently, strictly energy-conserving PIC (EC-PIC) algorithms have been developed that promise enhanced robustness against aliasing instabilities. In this study, we confirm by analysis that EC-PIC is stable against aliasing instabilities for stationary plasmas. For drifting plasmas, we demonstrate by analysis and numerical experiments that, while EC-PIC algorithms are not free from these instabilities in principle, they feature a benign stability threshold for finite-temperature plasmas that make them usable in practice for a large class of problems (featuring ambipolarity and realistic ion-electron mass ratios) without the need to consider the size of the Debye length. Finally, we also demonstrate that this threshold is absent for the popular momentum-conserving PIC algorithms, which are therefore unstable for both drifting and stationary plasmas beyond a threshold in cell size compared to Debye length.

97 MATHEMATICS AND COMPUTING↗

DOE OSTI2021

Intercomparison of Thermal Regime Algorithms in 1-D Lake Models

Lakes are an important component of the global weather and climate system, but the modeling of their thermal regimes has shown large uncertainties due to the highly diverse lake properties and model configurations. Here we evaluate the algorithms of four key lake thermal processes including turbulent heat fluxes, wind-driven mixing, light extinction, and snow density, using a highly diverse lake dataset provided by the Inter-sectoral Impact Model Intercomparison Project (ISIMIP) 2a lake sector. Algorithm codes are configured and run separately within the same parent model to rule out any interference from factors apart from the algorithms examined. Evaluations are based on both simulation accuracy and recalibration complexity for application to global lakes. For turbulent heat fluxes, the non-Monin-Obukhov similarity (MOS) based, more simplified algorithms perform better in predicting lake epilimnion temperatures and achieve high convergence in the values of the calibrated parameters. For wind-driven mixing, a two-algorithm strategy considering lake shape and season is suggested with the regular mixing algorithm used for spring and earlier summer and the mixing-enhanced algorithm for summer steady stratification and fall overturn periods. There are no evident differences in the simulated thermocline depths using different light extinction algorithms or the observation. Finally, for lake ice phenology, a constant snow density at around 110 kg m-3 is found to be sufficient for most northern lakes while the Arctic lakes require a higher value. Our study provides highly practical guides for improving 1-D lake models and feasible parameterization strategies to better simulate global lake thermal regimes.

58 GEOSCIENCES↗

DOE OSTI2023

Efficient fully-coherent quantum signal processing algorithms for real-time dynamics simulation

Simulating the unitary dynamics of a quantum system is a fundamental problem of quantum mechanics, in which quantum computers are believed to have significant advantage over their classical counterparts. One prominent such instance is the simulation of electronic dynamics, which plays an essential role in chemical reactions, non-equilibrium dynamics, and material design. These systems are time-dependent, which requires that the corresponding simulation algorithm can be successfully concatenated with itself over different time intervals to reproduce the overall coherent quantum dynamics of the system. In this paper, we quantify such simulation algorithms by the property of being fully-coherent: the algorithm succeeds with arbitrarily high success probability 1 − δ while only requiring a single copy of the initial state. Here we subsequently develop fully-coherent simulation algorithms based on quantum signal processing (QSP), including a novel algorithm that circumvents the use of amplitude amplification while also achieving a query complexity additive in time t, ln(1/δ), and ln(1/ϵ) for error tolerance ϵ: $Θ‖\mathscr{H}‖|t|+ln(1/ϵ)+ln(1/δ)$. Furthermore, we numerically analyze these algorithms by applying them to the simulation of the spin dynamics of the Heisenberg model and the correlated electronic dynamics of an H2 molecule. Since any electronic Hamiltonian can be mapped to a spin Hamiltonian, our algorithm can efficiently simulate time-dependent ab initio electronic dynamics in the circuit model of quantum computation. Accordingly, it is also our hope that the present work serves as a bridge between QSP-based quantum algorithms and chemical dynamics, stimulating a cross-fertilization between these exciting fields.

37 INORGANIC, ORGANIC, PHYSICAL, AND ANALYTICAL CH↗

DOE OSTI2022

Inexact Newton-CG algorithms with complexity guarantees

Abstract We consider variants of a recently developed Newton-CG algorithm for nonconvex problems (Royer, C. W. & Wright, S. J. (2018) Complexity analysis of second-order line-search algorithms for smooth nonconvex optimization. SIAM J. Optim., 28, 1448–1477) in which inexact estimates of the gradient and the Hessian information are used for various steps. Under certain conditions on the inexactness measures, we derive iteration complexity bounds for achieving $\epsilon $-approximate second-order optimality that match best-known lower bounds. Our inexactness condition on the gradient is adaptive, allowing for crude accuracy in regions with large gradients. We describe two variants of our approach, one in which the step size along the computed search direction is chosen adaptively, and another in which the step size is pre-defined. To obtain second-order optimality, our algorithms will make use of a negative curvature direction on some steps. These directions can be obtained, with high probability, using the randomized Lanczos algorithm. In this sense, all of our results hold with high probability over the run of the algorithm. We evaluate the performance of our proposed algorithms empirically on several machine learning models. Our approach is a first attempt to introduce inexact Hessian and/or gradient information into the Newton-CG algorithm of Royer & Wright (2018, Complexity analysis of second-order line-search algorithms for smooth nonconvex optimization. SIAM J. Optim., 28, 1448–1477).

Mathematics↗

DOE OSTI2023

Iterative Stability Enforcement in Adaptive Antoulas–Anderson Algorithms for ${\boldsymbol{\mathcal{H}_2}}$ Model Reduction

This paper presents an extension of the Adaptive-Antoulas-Anderson (AAA) algorithm for rational modelling. Specifically, our new stable multi-input multi-output AAA (smiAAA) algorithm builds rational approximations of multi-input signals with a common set of stable poles. A new methodology is presented for iteratively enforcing stability constraints on the poles. We demonstrate the strengths of this approach compared to the stability enforcement in the FastAAA algorithm. Results using the smiAAA algorithm are compared with the commonly used Vector Fitting algorithm and the more recently published RKFIT algorithm. Vector Fitting and RKFIT both require the user to input the number of poles to use in the approximations. If the final approximation is not accurate enough, the user must re-start Vector Fitting or RKFIT with a larger number of poles and/or a new starting location for the poles. In contrast, the smiAAA algorithm is designed to allow the user to simply input the desired accuracy of the approximations, and the necessary number of poles is detected automatically. This permits users to produce approximations of a desired accuracy with no knowledge about the underlying order of the system being approximated, preventing the algorithm from ever needing to be rerun. An additional feature for preventing extraneous poles from being returned by AAA is also discussed. The cause of these extraneous poles is efficiently detected and removed by our presented methodology. In conclusion, the examples presented demonstrate that smiAAA can efficiently produce approximations of similar or better accuracy than Vector Fitting and RKFIT while requiring less input from the user.

97 MATHEMATICS AND COMPUTING↗

DOE OSTI2021

Fast tensor disentangling algorithm

Many recent tensor network algorithms apply unitary operators to parts of a tensor network in order to reduce entanglement. However, many of the previously used iterative algorithms to minimize entanglement can be slow. We introduce an approximate, fast, and simple algorithm to optimize disentangling unitary tensors. Our algorithm is asymptotically faster than previous iterative algorithms and often results in a residual entanglement entropy that is within 10 to 40% of the minimum. For certain input tensors, our algorithm returns an optimal solution. When disentangling order-4 tensors with equal bond dimensions, our algorithm achieves an entanglement spectrum where nearly half of the singular values are zero. We further validate our algorithm by showing that it can efficiently disentangle random 1D states of qubits.

Slagle, Kevin↗

DOE OSTI2021

Neuromorphic Graph Algorithms

Graph algorithms enable myriad large-scale applications including cybersecurity, social network analysis, resource allocation, and routing. The scalability of current graph algorithm implementations on conventional computing architectures are hampered by the demise of Moore’s law. We present a theoretical framework for designing and assessing the performance of graph algorithms executing in networks of spiking artificial neurons. Although spiking neural networks (SNNs) are capable of general-purpose computation, few algorithmic results with rigorous asymptotic performance analysis are known. SNNs are exceptionally well-motivated practically, as neuromorphic computing systems with 100 million spiking neurons are available, and systems with a billion neurons are anticipated in the next few years. Beyond massive parallelism and scalability, neuromorphic computing systems offer energy consumption orders of magnitude lower than conventional high-performance computing systems. We employ our framework to design and analyze new spiking algorithms for shortest path and dynamic programming problems. Our neuromorphic algorithms are message-passing algorithms relying critically on data movement for computation. For fair and rigorous comparison with conventional algorithms and architectures, which is challenging but paramount, we develop new models of data-movement in conventional computing architectures. This allows us to prove polynomial-factor advantages, even when we assume a SNN consisting of a simple grid-like network of neurons. To the best of our knowledge, this is one of the first examples of a rigorous asymptotic computational advantage for neuromorphic computing.

97 MATHEMATICS AND COMPUTING↗