How to Design a Quantum Streaming Algorithm Without Knowing Anything About Quantum Computing
Proceedings article for the SIAM Symposium on Simplicity in Algorithms (SOSA25).
Kallaugher, John Michael Goddard [Sandia National ↗
SEARCH · Engineering Papers
Results for “Computer 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.
Advances in Machine and Deep Learning for Modeling and Real-time Detection of Multi-Messenger Sources
We live in momentous times. The science community is empowered with an arsenal of cosmic messengers to study the universe in unprecedented detail. Gravitational waves, electromagnetic waves, neutrinos, and cosmic rays cover a wide range of wavelengths and timescales. Combining and processing these datasets that vary in volume, speed, and dimensionality requires new modes of instrument coordination, funding, and international collaboration with a specialized human and technological infrastructure. In tandem with the advent of large-scale scientific facilities, the last decade has experienced an unprecedented transformation in computing and signal-processing algorithms. The combination of graphics processing units, deep learning, and the availability of open source, high-quality datasets has powered the rise of artificial intelligence. This digital revolution now powers a multibillion dollar industry, with far-reaching implications in technology and society. In this chapter, we describe pioneering efforts to adapt artificial intelligence algorithms to address computational grand challenges in multi-messenger astrophysics. We review the rapid evolution of these disruptive algorithms, from the first class of algorithms introduced in early 2017 to the sophisticated algorithms that now incorporate domain expertise in their architectural design and optimization schemes. We discuss the importance of scientific visualization and extreme-scale computing in reducing time-to-insight and obtaining new knowledge from the interplay between models and data.
Artificial Intelligence↗
Navier-Stokes computations for aerodynamic configurations at high angles of attack
Navier-Stokes computations at high angles of attack over aerodynamic configurations are presented using an implicit finite-volume algorithm. The spatial differencing is upwind-biased for the convective and pressure terms and central for the shear stress and heat transfer terms. The equations are relaxed to steady state with a spatially factored implicit algorithm. In order to treat general geometries, a multiblock patched-grid framework is implemented. Applications and detailed comparisons with experimental data are made for two simple but representative geometric shapes: (1) a highly swept delta wing and (2) a prolate spheroid of 6:1 length-to-diameter. Recent extensions of the algorithm to compute the flow over an F-18 forebody-strake configuration are shown, including comparisons with wind tunnel and flight test results. Comparisons across the range of Reynolds number for all cases indicate that either low Reynolds number or high Reynolds number flows are simulated well, but that flows at intermediate Reynolds number cannot be simulated accurately without a detailed knowledge of the transitional zone between laminar and turbulent flow.
Thomas, J. L.↗
A Convex Guidance Algorithm for Formation Reconfiguration
In this paper, a reconfiguration guidance algorithm for formation flying spacecraft is presented. The formation reconfiguration guidance problem is first formulated as a continuous-time minimum-fuel or minimum-energy optimal control problem with collision avoidance and control constraints. The optimal control problem is then discretized to obtain a finite dimensional parameter optimization problem. In this formulation, the collision avoidance constraints are imposed via separating planes between each pair of spacecraft. A heuristic is introduced to choose these separating planes that leads to the convexification of the collision avoidance constraints. Additionally, convex constraints are imposed to guarantee that no collisions occur between discrete time samples. The resulting finite dimensional optimization problem is a second order cone program, for which standard algorithms can compute the global optimum with deterministic convergence and a prescribed level of accuracy. Consequently, the formation reconfiguration algorithm can be implemented onboard a spacecraft for real-time operations.
formation reconfiguration↗
Multichannel Analysis of Surface Waves Accelerated (MASWAccelerated): Software for efficient surface wave inversion using MPI and GPUs
Multichannel Analysis of Surface Waves (MASW) is a technique frequently used in geotechnical engineering and engineering geophysics to infer 1D layered models of seismic shear wave velocities in the top tens to hundreds of meters of the subsurface. We aim to accelerate MASW calculations by capitalizing on modern computer hardware available in the workstations of most engineers: multiple cores and graphics processing units (GPUs). We propose new parallel and GPU accelerated algorithms for computing 1D MASW inversion, and provide software implementations in C using Message Passing Interface (MPI) and CUDA. These algorithms take advantage of sparsity that arises in the problem, and the work balance between processes considers typical data trends. We compare our methods to an existing open source Matlab MASW tool. Our serial C implementation achieves a 2x speedup over the Matlab software, and we continue to see improvements by parallelizing the problem with MPI. Here we see nearly perfect strong and weak scaling for uniform data, and improve strong scaling for realistic data by repartitioning the problem to process mapping. By utilizing GPUs available on most modern workstations, we observe an additional 1.3x speedup over the serial C implementation on the first use of the method. We typically repeatedly evaluate theoretical dispersion curves as part of an optimization procedure, and on the GPU the kernel can be cached for faster reuse on later runs. We observe a 3.2x speedup on the cached GPU runs compared to the serial C runs. This work is the first open-source parallel or GPU-accelerated software tool for MASW imaging, and should enable geotechnical engineers to fully utilize all computer hardware at their disposal.
58 GEOSCIENCES↗
Scheme for Entering Binary Data Into a Quantum Computer
A quantum algorithm provides for the encoding of an exponentially large number of classical data bits by use of a smaller (polynomially large) number of quantum bits (qubits). The development of this algorithm was prompted by the need, heretofore not satisfied, for a means of entering real-world binary data into a quantum computer. The data format provided by this algorithm is suitable for subsequent ultrafast quantum processing of the entered data. Potential applications lie in disciplines (e.g., genomics) in which one needs to search for matches between parts of very long sequences of data. For example, the algorithm could be used to encode the N-bit-long human genome in only log2N qubits. The resulting log2N-qubit state could then be used for subsequent quantum data processing - for example, to perform rapid comparisons of sequences.
Williams, Colin↗
Leveraging dendritic complexity for neuromorphic computing
Abstract Beyond-von Neumann computing approaches are necessary to sustain the growth of microelectronics and the increasing appetite for artificial intelligence/machine learning algorithms. Neuromorphic computing is an emerging paradigm that takes inspiration from the brain to provide a path forward to improve the computational efficiency and computational density of next-generation computing architectures. In nature, we observe brains performing complex computations with a much smaller energy footprint than conventional computing approaches. Current neuromorphic systems are focused primarily on scalability, namely, increasing the number of computational units (neurons) and connections between units (synapses). However, for brain-like cognition and efficiency in next-generation computing hardware, we need increased complexity in function, as well as improved connection density for scalability. Here, we present our work that aims to incorporate dendrites for ‘compute-on-wire’ in neuromorphic architectures to increase the computational complexity (e.g. number of programmable parameters, nonlinear dynamics) as well as computational efficiency (energy/compute) of artificial neural networks (ANNs). We do this by showcasing neuromorphic dendrite elements that can be leveraged for various applications. We will present examples of neuroscience-inspired direction-selective circuits and an ANN with active dendrites leveraging shunting inhibition. We also demonstrate the benefits of using dendrites in deep neural networks. To conclude, we discuss how we can utilize emerging hardware devices in these systems and design next-generation neuromorphic architectures with dendrites.
Cardwell, Suma G. (ORCID:0000000226575545)↗
Quantum error thresholds for gauge-redundant digitizations of lattice field theories
In the quantum simulation of lattice gauge theories, gauge symmetry can be either fixed or encoded as a redundancy of the Hilbert space. While gauge-fixing reduces the number of qubits, keeping the gauge redundancy can provide code space to mitigate and correct quantum errors by checking and restoring Gauss’s law. In this work, we consider the correctable errors for generic finite gauge groups and design the quantum circuits to detect and correct them. We calculate the error thresholds below which the gauge-redundant digitization with Gauss’s law error correction has better fidelity than the gauge-fixed digitization involving only gauge-invariant states. Our results provide guidance for fault-tolerant quantum simulations of lattice gauge theories. Published by the American Physical Society 2024
97 MATHEMATICS AND COMPUTING↗
Analytical Functions for 200 West Pump-and-Treat SCADA Sensor Data
Historical operations at the U.S. Department of Energy’s Hanford Site included disposal of waste fluids to the subsurface in the 200 West Area on the Hanford Central Plateau. Subsequent infiltration of fluids has resulted in groundwater contamination with carbon tetrachloride, nitrate, uranium, technetium-99, and other contaminants. A pump-and-treat (P&T) system, with an extraction/injection well network and an aboveground treatment plant, was implemented as part of interim and final remedies in the 200 West area. The HYPATIA single-page web application (part of the SOCRATES suite) is being developed to provide access to and analysis of chemistry and treatment facility sensor data for this 200 West P&T system. For the web application, analytical algorithms were developed to perform summing, differencing, smoothing, outlier detection, change-point detection, mass flow rate, and injectivity calculations on the data. Candidate algorithms were identified and tested, with the best-performing algorithms then assembled for implementation in HYPATIA. Because HYPATIA is hosted on the Amazon Web Services (AWS) cloud computing platform, algorithms were implemented in a back-end AWS Lambda function that can be called by the HYPATIA front end. The Lambda function applies the requested data processing to specified data via functions written in R, Python, and JavaScript. Development, testing, and review of the data analysis algorithms was completed under an NQA-1 quality program. This new HYPATIA functionality will provide information to support site decisions regarding P&T system performance and optimization.
12 MANAGEMENT OF RADIOACTIVE AND NON-RADIOACTIVE W↗
Space station dynamics, attitude control and momentum management
The Space Station Attitude Control System software test-bed provides a rigorous environment for the design, development and functional verification of GN and C algorithms and software. The approach taken for the simulation of the vehicle dynamics and environmental models using a computationally efficient algorithm is discussed. The simulation includes capabilities for docking/berthing dynamics, prescribed motion dynamics associated with the Mobile Remote Manipulator System (MRMS) and microgravity disturbances. The vehicle dynamics module interfaces with the test-bed through the central Communicator facility which is in turn driven by the Station Control Simulator (SCS) Executive. The Communicator addresses issues such as the interface between the discrete flight software and the continuous vehicle dynamics, and multi-programming aspects such as the complex flow of control in real-time programs. Combined with the flight software and redundancy management modules, the facility provides a flexible, user-oriented simulation platform.
Sunkel, John W.↗
Time-Accurate Local Time Stepping and High-Order Time CESE Methods for Multi-Dimensional Flows Using Unstructured Meshes
With the wide availability of affordable multiple-core parallel supercomputers, next generation numerical simulations of flow physics are being focused on unsteady computations for problems involving multiple time scales and multiple physics. These simulations require higher solution accuracy than most algorithms and computational fluid dynamics codes currently available. This paper focuses on the developmental effort for high-fidelity multi-dimensional, unstructured-mesh flow solvers using the space-time conservation element, solution element (CESE) framework. Two approaches have been investigated in this research in order to provide high-accuracy, cross-cutting numerical simulations for a variety of flow regimes: 1) time-accurate local time stepping and 2) highorder CESE method. The first approach utilizes consistent numerical formulations in the space-time flux integration to preserve temporal conservation across the cells with different marching time steps. Such approach relieves the stringent time step constraint associated with the smallest time step in the computational domain while preserving temporal accuracy for all the cells. For flows involving multiple scales, both numerical accuracy and efficiency can be significantly enhanced. The second approach extends the current CESE solver to higher-order accuracy. Unlike other existing explicit high-order methods for unstructured meshes, the CESE framework maintains a CFL condition of one for arbitrarily high-order formulations while retaining the same compact stencil as its second-order counterpart. For large-scale unsteady computations, this feature substantially enhances numerical efficiency. Numerical formulations and validations using benchmark problems are discussed in this paper along with realistic examples.
Chang, Chau-Lyan↗
Minimum deltaV Burn Planning for the International Space Station Using a Hybrid Optimization Technique, Level 1
The International Space Station's (ISS) trajectory is coordinated and executed by the Trajectory Operations and Planning (TOPO) group at NASA's Johnson Space Center. TOPO group personnel routinely generate look-ahead trajectories for the ISS that incorporate translation burns needed to maintain its orbit over the next three to twelve months. The burns are modeled as in-plane, horizontal burns, and must meet operational trajectory constraints imposed by both NASA and the Russian Space Agency. In generating these trajectories, TOPO personnel must determine the number of burns to model, each burn's Time of Ignition (TIG), and magnitude (i.e. deltaV) that meet these constraints. The current process for targeting these burns is manually intensive, and does not take advantage of more modern techniques that can reduce the workload needed to find feasible burn solutions, i.e. solutions that simply meet the constraints, or provide optimal burn solutions that minimize the total DeltaV while simultaneously meeting the constraints. A two-level, hybrid optimization technique is proposed to find both feasible and globally optimal burn solutions for ISS trajectory planning. For optimal solutions, the technique breaks the optimization problem into two distinct sub-problems, one for choosing the optimal number of burns and each burn's optimal TIG, and the other for computing the minimum total deltaV burn solution that satisfies the trajectory constraints. Each of the two aforementioned levels uses a different optimization algorithm to solve one of the sub-problems, giving rise to a hybrid technique. Level 2, or the outer level, uses a genetic algorithm to select the number of burns and each burn's TIG. Level 1, or the inner level, uses the burn TIGs from Level 2 in a sequential quadratic programming (SQP) algorithm to compute a minimum total deltaV burn solution subject to the trajectory constraints. The total deltaV from Level 1 is then used as a fitness function by the genetic algorithm in Level 2 to select the number of burns and their TIGs for the next generation. In this manner, the two levels solve their respective sub-problems separately but collaboratively until a burn solution is found that globally minimizes the deltaV across the entire trajectory. Feasible solutions can also be found by simply using the SQP algorithm in Level 1 with a zero cost function. This paper discusses the formulation of the Level 1 sub-problem and the development of a prototype software tool to solve it. The Level 2 sub-problem will be discussed in a future work. Following the Level 1 formulation and solution, several look-ahead trajectory examples for the ISS are explored. In each case, the burn targeting results using the current process are compared against a feasible solution found using Level 1 in the proposed technique. Level 1 is then used to find a minimum deltaV solution given the fixed number of burns and burn TIGs. The optimal solution is compared with the previously found feasible solution to determine the deltaV (and therefore propellant) savings. The proposed technique seeks to both improve the current process for targeting ISS burns, and to add the capability to optimize ISS burns in a novel fashion. The optimal solutions found using this technique can potentially save hundreds of kilograms of propellant over the course of the ISS mission compared to feasible solutions alone. While the software tool being developed to implement this technique is specific to ISS, the concept is extensible to other long-duration, central-body orbiting missions that must perform orbit maintenance burns to meet operational trajectory constraints.
Brown, Aaron J.↗
Identifying and tracking bubbles and drops in simulations: A toolbox for obtaining sizes, lineages, and breakup and coalescence statistics
Knowledge of bubble and drop size distributions in two-phase flows is important for characterizing a wide range of phenomena, including combustor ignition, sonar communication, and cloud formation. The physical mechanisms driving the background flow also drive the time evolution of these distributions. Accurate and robust identification and tracking algorithms for the dispersed phase are necessary to reliably measure this evolution and thereby quantify the underlying mechanisms in interface-resolving flow simulations. The identification of individual bubbles and drops traditionally relies on an algorithm used to identify connected regions. This traditional algorithm can be sensitive to the presence of spurious structures. A cost-effective refinement is proposed to maximize volume accuracy while minimizing the identification of spurious bubbles and drops. An accurate identification scheme is crucial for distinguishing bubble and drop pairs with large size ratios. The identified bubbles and drops need to be tracked in time to obtain breakup and coalescence statistics that characterize the evolution of the size distribution, including breakup and coalescence frequencies, and the probability distributions of parent and child bubble and drop sizes. An algorithm based on mass conservation is proposed to construct bubble and drop lineages using simulation snapshots that are not necessarily from consecutive time steps. These lineages are then used to detect breakup and coalescence events, and obtain the desired statistics. Accurate identification of large-size-ratio bubble and drop pairs enables accurate detection of breakup and coalescence events over a large size range. Accurate detection of successive breakup and coalescence events requires that the snapshot interval be an order of magnitude smaller than the characteristic breakup and coalescence times to capture these successive events while minimizing the identification of repeated confounding events. Together, these algorithms serve as a toolbox for detailed analysis of two-phase simulations, and enable insights into the mechanisms behind bubble and drop formation and evolution in flows of practical importance.
71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗
Qubit-efficient entanglement spectroscopy using qubit resets
One strategy to fit larger problems on NISQ devices is to exploit a tradeoff between circuit width and circuit depth. Unfortunately, this tradeoff still limits the size of tractable problems since the increased depth is often not realizable before noise dominates. Here, we develop qubit-efficient quantum algorithms for entanglement spectroscopy which avoid this tradeoff. In particular, we develop algorithms for computing the trace of the n -th power of the density operator of a quantum system, T r ( ρ n ) , (related to the Rényi entropy of order n ) that use fewer qubits than any previous efficient algorithm while achieving similar performance in the presence of noise, thus enabling spectroscopy of larger quantum systems on NISQ devices. Our algorithms, which require a number of qubits independent of n , are variants of previous algorithms with width proportional to n , an asymptotic difference. The crucial ingredient in these new algorithms is the ability to measure and reinitialize subsets of qubits in the course of the computation, allowing us to reuse qubits and increase the circuit depth without suffering the usual noisy consequences. We also introduce the notion of effective circuit depth as a generalization of standard circuit depth suitable for circuits with qubit resets. This tool helps explain the noise-resilience of our qubit-efficient algorithms and should aid in designing future algorithms. We perform numerical simulations to compare our algorithms to the original variants and show they perform similarly when subjected to noise. Additionally, we experimentally implement one of our qubit-efficient algorithms on the Honeywell System Model H0, estimating T r ( ρ n ) for larger n than possible with previous algorithms.
71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗
Iterative computation of the optimal H(infinity) norm by using two-Riccati-equation method
The two-Riccati-equation method solution to a standard H(infinity) control problem can be used to characterize all possible stabilizing optimal or suboptimal H(infinity) controllers if the optimal or suboptimal H(infinity) norm is available in the literature. An iterative algorithm for computing the optimal H(infinity) norm is proposed. The algorithm employs fixed-point, double secant and bisection to guarantee a super linear convergence.
Chang, B. C.↗
Computer aided manual tracking
A scheme was developed to assist the human operator by augmenting an optic sight manual tracking loop with target rate estimates from a computer control algorithm which can either be a Kalman Filter or an alpha, beta, gamma filter. The idea is for the computer to provide rate tracking while the human operator is responsible for nullifying the tracking error. A simple schematic is shown to illustrate the implementation of this concept. A hybrid real-time man-in-loop simulation was used to compare the tracking performance of the same flight trajectory with or without this form of computer-aided track. Preliminary results show the advantage of computer-aided track against high speed aircraft at close range. However, good tracking before target state estimator maturity becomes more critical for aided track than without. Results are presented for a constant velocity flight trajectory.
Yin, Y. K.↗
Status of the Delco Systems Operations forward looking windshear detection program
Delco Systems Operations, a division of General Motors Hughes Electronics Corporation, is developing a Forward Looking Windshear Detection System based on the integration of infrared remote sensing and accelerometer reactive sensing technologies. The infrared sensor is a multi-spectral, scanning radiometer operating in the 8 to 14 micron region. A 2 x 5 detector array with parallel-serial scanning produces 60 degrees horizontal and 10 degrees vertical-fields of view. Using multiple wavelength signals, azimuth temperature gradients are analyzed for characteristic signatures of thermally induced windshear phenomena. Elevation temperature gradients are processed through an atmosphere model to continuously compute a stability index for arming microburst detection criteria. The atmosphere model and proprietary computer processing algorithms combine to generate coarse estimates of disturbance ranges based on multiple wavelength radiance data with different extinction coefficients. Computer outputs of atmospheric stability, disturbance intensity, and azimuth and range information provide a situation display capability. A ground operated, experimental radiometer has been developed and is being used to verify the detection and discrimination concepts at an atmospheric and simulated rain test facility in Milwaukee. A prototype airborne radiometer is being developed for flight test evaluation during the summer of 1989.
Gallagher, Brian J.↗
New Parallel Algorithms for Structural Analysis and Design of Aerospace Structures
Subspace and Lanczos iterations have been developed, well documented, and widely accepted as efficient methods for obtaining p-lowest eigen-pair solutions of large-scale, practical engineering problems. The focus of this paper is to incorporate recent developments in vectorized sparse technologies in conjunction with Subspace and Lanczos iterative algorithms for computational enhancements. Numerical performance, in terms of accuracy and efficiency of the proposed sparse strategies for Subspace and Lanczos algorithm, is demonstrated by solving for the lowest frequencies and mode shapes of structural problems on the IBM-R6000/590 and SunSparc 20 workstations.
Nguyen, Duc T.↗