Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “approximation 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 379 records · Page 21

Parallel algorithm for determining motion vectors in ice floe images by matching edge features

A parallel algorithm is described to determine motion vectors of ice floes using time sequences of images of the Arctic ocean obtained from the Synthetic Aperture Radar (SAR) instrument flown on-board the SEASAT spacecraft. Researchers describe a parallel algorithm which is implemented on the MPP for locating corresponding objects based on their translationally and rotationally invariant features. The algorithm first approximates the edges in the images by polygons or sets of connected straight-line segments. Each such edge structure is then reduced to a seed point. Associated with each seed point are the descriptions (lengths, orientations and sequence numbers) of the lines constituting the corresponding edge structure. A parallel matching algorithm is used to match packed arrays of such descriptions to identify corresponding seed points in the two images. The matching algorithm is designed such that fragmentation and merging of ice floes are taken into account by accepting partial matches. The technique has been demonstrated to work on synthetic test patterns and real image pairs from SEASAT in times ranging from .5 to 0.7 seconds for 128 x 128 images.

Manohar, M.↗

A mixed quantum-classical Liouville study of the population dynamics in a model photo-induced condensed phase electron transfer reaction

We apply two approximate solutions of the quantum-classical Liouville equation (QCLE) in the mapping representation to the simulation of the laser-induced response of a quantum subsystem coupled to a classical environment. These solutions, known as the Poisson Bracket Mapping Equation (PBME) and the Forward-Backward (FB) trajectory solutions, involve simple algorithms in which the dynamics of both the quantum and classical degrees of freedom are described in terms of continuous variables, as opposed to standard surface-hopping solutions in which the classical degrees of freedom hop between potential energy surfaces dictated by the discrete adiabatic state of the quantum subsystem. The validity of these QCLE-based solutions is tested on a non-trivial electron transfer model involving more than two quantum states, a time-dependent Hamiltonian, strong subsystem-bath coupling, and an initial energy shift between the donor and acceptor states that depends on the strength of the subsystem-bath coupling. In particular, we calculate the time-dependent population of the photoexcited donor state in response to an ultrafast, on-resonance pump pulse in a three-state model of an electron transfer complex that is coupled asymmetrically to a bath of harmonic oscillators through the optically dark acceptor state. Within this approach, the three-state electron transfer complex is treated quantum mechanically, while the bath oscillators are treated classically. When compared to the more accurate QCLE-based surface-hopping solution and to the numerically exact quantum results, we find that the PBME solution is not capable of qualitatively capturing the population dynamics, whereas the FB solution is. However, when the subsystem-bath coupling is decreased (which also decreases the initial energy shift between the donor and acceptor states) or the initial shift is removed altogether, both the PBME and FB results agree better with the QCLE-based surface-hopping results. These findings highlight the challenges posed by various conditions such as a time-dependent external field, the strength of the subsystem-bath coupling, and the degree of asymmetry on the accuracy of the PBME and FB algorithms.

74 ATOMIC AND MOLECULAR PHYSICS↗

A Preconditioned Low-Rank Projection Method with a Rank-Reduction Scheme for Stochastic Partial Differential Equations

Herein, we consider the numerical solution of large systems of linear equations obtained from the stochastic Galerkin formulation of stochastic partial differential equations. We propose an iterative algorithm that exploits the Kronecker product structure of the linear systems. The proposed algorithm efficiently approximates the solutions in low-rank tensor format. Using standard Krylov subspace methods for the data in tensor format is computationally prohibitive due to the rapid growth of tensor ranks during the iterations. To keep tensor ranks low over the entire iteration process, we devise a rank-reduction scheme that can be combined with the iterative algorithm. The proposed rank-reduction scheme identifies an important subspace in the stochastic domain and compresses tensors of high rank on-the-fly during the iterations. The proposed reduction scheme is a coarse-grid method in that the important subspace can be identified inexpensively in a coarse spatial grid setting. The efficiency of the present method is displayed by numerical experiments on benchmark problems.

97 MATHEMATICS AND COMPUTING↗

A Note on Euler Approximations for Stochastic Differential Equations with Delay

An existence and uniqueness theorem for a class of stochastic delay differential equations is presented, and the convergence of Euler approximations for these equations is proved under general conditions. Moreover, the rate of almost sure convergence is obtained under local Lipschitz and also under monotonicity conditions.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

Laser-plasma interactions with a Fourier-Bessel particle-in-cell method

A new spectral particle-in-cell (PIC) method for plasma modeling is presented and discussed. In the proposed scheme, the Fourier-Bessel transform is used to translate the Maxwell equations to the quasi-cylindrical spectral domain. In this domain, the equations are solved analytically in time, and the spatial derivatives are approximated with high accuracy. In contrast to the finite-difference time domain (FDTD) methods, that are used commonly in PIC, the developed method does not produce numerical dispersion and does not involve grid staggering for the electric and magnetic fields. These features are especially valuable in modeling the wakefield acceleration of particles in plasmas. The proposed algorithm is implemented in the code PLARES-PIC, and the test simulations of laser plasma interactions are compared to the ones done with the quasi-cylindrical FDTD PIC code CALDER-CIRC.

70 PLASMA PHYSICS AND FUSION TECHNOLOGY↗

Multi-qubit entanglement and algorithms on a neutral-atom quantum computer

Gate model quantum computers promise to solve currently intractable computational problems if they can be operated at scale with long coherence times and high fidelity logic. Neutral atom hyperfine qubits provide inherent scalability due to their identical characteristics, long coherence times, and ability to be trapped in dense multi-dimensional arrays. Combined with the strong entangling interactions provided by Rydberg states, all the necessary characteristics for quantum computation are available. Here we demonstrate several quantum algorithms on a programmable gate model neutral atom quantum computer in an architecture based on individual addressing of single atoms with tightly focused optical beams scanned across a two-dimensional array of qubits. Preparation of entangled Greenberger-Horne-Zeilinger (GHZ) states with up to 6 qubits, quantum phase estimation for a chemistry problem, and the Quantum Approximate Optimization Algorithm (QAOA) for the MaxCut graph problem are demonstrated. These results highlight the emergent capability of neutral atom qubit arrays for universal, programmable quantum computation, as well as preparation of non-classical states of use for quantum enhanced sensing.

97 MATHEMATICS AND COMPUTING↗

Distributed approximate minimal Steiner trees with millions of seed vertices on billion-edge graphs

In this report, we present a parallel 2-approximation Steiner minimal tree algorithm and its MPI-based distributed implementation. In place of expensive distance computations between all pairs of seed vertices, the solution we employ exploits a cheaper Voronoi cell computation. Our design leverages asynchronous processing and message prioritization to accelerate convergence of distance computations, and harnesses vertex and edge centric processing to offer fast time-to-solution. We demonstrate scalability and performance using real-world graphs with up to 128 billion edges and 512 compute nodes, and show the ability to find Steiner trees with up to one million seed vertices. Using 12 data instances, we present comparison with the state-of-the-art exact solver, SCIP-Jack, and two sequential 2-approximate algorithms. We empirically show that, on average, the total distance of the Steiner tree identified by our solution is 1.1290 times greater than the Steiner minimal tree – well within the theoretical approximation bound of 2.

97 MATHEMATICS AND COMPUTING↗

Approximate Bayesian computation for forward modeling in cosmology

Bayesian inference is often used in cosmology and astrophysics to derive constraints on model parameters from observations. This approach relies on the ability to compute the likelihood of the data given a choice of model parameters. In many practical situations, the likelihood function may however be unavailable or intractable due to non-gaussian errors, non-linear measurements processes, or complex data formats such as catalogs and maps. In these cases, the simulation of mock data sets can often be made through forward modeling. We discuss how Approximate Bayesian Computation (ABC) can be used in these cases to derive an approximation to the posterior constraints using simulated data sets. This technique relies on the sampling of the parameter set, a distance metric to quantify the difference between the observation and the simulations and summary statistics to compress the information in the data. We first review the principles of ABC and discuss its implementation using a Population Monte-Carlo (PMC) algorithm and the Mahalanobis distance metric. We test the performance of the implementation using a Gaussian toy model. We then apply the ABC technique to the practical case of the calibration of image simulations for wide field cosmological surveys. We find that the ABC analysis is able to provide reliable parameter constraints for this problem and is therefore a promising technique for other applications in cosmology and astrophysics. Our implementation of the ABC PMC method is made available via a public code release.

79 ASTRONOMY AND ASTROPHYSICS↗

SU-E-I-01: A Fast, Analytical Pencil Beam Based Method for First Order X-Ray Scatter Estimation of Kilovoltage Cone Beam X-Rays

Purpose: To analytically estimate first-order x-ray scatter for kV cone beam x-ray imaging with high computational efficiency. Methods: In calculating first-order scatter using the Klein-Nishina formula, we found that by integrating the point-to-point scatter along an interaction line, a “pencil-beam” scatter kernel (BSK) can be approximated to a quartic expression when the imaging field is small. This BSK model for monoenergetic, 100keV x-rays has been verified on homogeneous cube and cylinder water phantoms by comparing with the exact implementation of KN formula. For heterogeneous medium, the water-equivalent length of a BSK was acquired with an improved Siddon's ray-tracing algorithm, which was also used in calculating pre- and post- scattering attenuation. To include the electron binding effect for scattering of low-kV photons, the mean corresponding scattering angle is determined from the effective point of scattered photons of a BSK. The behavior of polyenergetic x-rays was also investigated for 120kV x-rays incident to a sandwiched infinite heterogeneous slab phantom, with the electron binding effect incorporated. Exact computation and Monte Carlo simulations were performed for comparisons, using the EGSnrc code package. Results: By reducing the 3D volumetric target (o(n{sup 3})) to 2D pencil-beams (o(n{sup 2})), the computation expense can be generally lowered by n times, which our experience verifies. The scatter distribution on a flat detector shows high agreement between the analytic BSK model and exact calculations. The pixel-to-pixel differences are within (-2%, 2%) for the homogeneous cube and cylinder phantoms and within (0, 6%) for the heterogeneous slab phantom. However, the Monte Carlo simulation shows increased deviation of the BSK model toward detector periphery. Conclusion: The proposed BSK model, accommodating polyenergetic x-rays and electron binding effect at low kV, shows great potential in efficiently estimating the first-order scatter from small imaging fields. We are investigating more thoroughly to improve performance and explore applications.

07 ISOTOPE AND RADIATION SOURCES↗

Simulation of biochemical reactions with time-dependent rates by the rejection-based algorithm

We address the problem of simulating biochemical reaction networks with time-dependent rates and propose a new algorithm based on our rejection-based stochastic simulation algorithm (RSSA) [Thanh et al., J. Chem. Phys. 141(13), 134116 (2014)]. The computation for selecting next reaction firings by our time-dependent RSSA (tRSSA) is computationally efficient. Furthermore, the generated trajectory is exact by exploiting the rejection-based mechanism. We benchmark tRSSA on different biological systems with varying forms of reaction rates to demonstrate its applicability and efficiency. We reveal that for nontrivial cases, the selection of reaction firings in existing algorithms introduces approximations because the integration of reaction rates is very computationally demanding and simplifying assumptions are introduced. The selection of the next reaction firing by our approach is easier while preserving the exactness.

37 INORGANIC, ORGANIC, PHYSICAL, AND ANALYTICAL CH↗

Quantum Simulators and Applications on Quantum Framework

Simulating quantum circuits is essential for validating quantum algorithms. However, no single simulator consistently performs best - efficiency depends on circuit structure, entanglement, and depth. In this work, we integrate Qiskit-Aer (state-vector and matrix product state) and QTensor, a tree-tensor-network based simulator, into the Quantum Framework (QFw), a modular platform that supports multiple quantum backends via a unified interface. We also enable distributed quantum approximate optimization algorithm (DQAOA) application compatibility with QFw, allowing sub-problems to be solved in parallel at scale. We then benchmark DQAOA and TFIM (transverse field Ising model) circuits across supported simulators, showing how performance varies significantly with problem type. All simulations are deployed on the Frontier supercomputer using QFw's MPI-based orchestration for distributed, multinode execution. These results underscore the need for simulatoragnostic infrastructure to enable systematic evaluation and highperformance scaling of quantum workloads. QFw provides a practical and extensible path toward reproducible quantum algorithm development across diverse application domains.

Chundury, Srikar [ORNL] (ORCID:0009000183359259)↗

Solving numerically nonlinear systems of balance laws by multivariate sigmoidal functions approximation

A numerical method for solving systems of nonlinear one-dimensional balance laws, based on multivariate sigmoidal functions approximation, is developed. Constructive approximation theorems are first established in both, uniform and L{sup p} norms. A priori as well as a posteriori error estimates are derived for the numerical solutions, when various kinds of sigmoidal functions, such as unit step, logistic and Gompertz functions, are chosen. The residual of the numerical method is also estimated. Numerical examples are given to test the performance of the algorithm, a comparison with the Godunov method is made concerning accuracy and computational cost. Finally, the numerical stability of the method is analyzed.

97 MATHEMATICS AND COMPUTING↗

Towards Robustness Guarantees for Feedback-Based Optimization

Feedback-based online optimization algorithms have gained traction in recent years because of their simple implementation, their ability to reject disturbances in real time, and their increased robustness to model mismatch. While the robustness properties have been observed both in simulation and experimental results, the theoretical analysis in the literature is mostly limited to nominal conditions. In this work, we propose a framework to systematically assess the robust stability of feedback-based online optimization algorithms. We leverage tools from monotone operator theory, variational inequalities and classical robust control to obtain tractable numerical tests that guarantee robust convergence properties of online algorithms in feedback with a physical system, even in the presence of disturbances and model uncertainty. The results are illustrated via an academic example and a case study of a power distribution system.

approximation algorithms↗

IBS for non-gaussian distributions

In many situations distribution can significantly deviate from Gaussian which requires accurate treatment of IBS. Our original interest in this problem was motivated by the need to have an accurate description of beam evolution due to IBS while distribution is strongly affected by the external electron cooling force. A variety of models with various degrees of approximation were developed and implemented in BETACOOL in the past to address this topic. A more complete treatment based on the friction coefficient and full 3-D diffusion tensor was introduced in BETACOOL at the end of 2007 under the name 'local IBS model'. Such a model allowed us calculation of IBS for an arbitrary beam distribution. The numerical benchmarking of this local IBS algorithm and its comparison with other models was reported before. In this paper, after briefly describing the model and its limitations, they present its comparison with available experimental data.

43 PARTICLE ACCELERATORS↗

The Best Rank-(R{sub 1},R{sub 2},R{sub 3}) Approximation of Tensors by Means of a Geometric Newton Method

In the matrix case, the best low-rank approximation can be obtained directly from the truncated singular value decomposition. However, the best rank-(R{sub 1},R{sub 2},...,R{sub N}) approximation of higher-order tensors cannot be computed in a straightforward way. An additional difficulty comes from an invariance property of the cost function by the action of the orthogonal group. This means that the zeros of the cost function are not isolated and the plain Newton method might have difficulties. In this paper, we derive a geometric Newton method using the theory of quotient manifolds. Our algorithm has fast convergence in a neighborhood of the solution and is useful for a large class of problems. We mention some applications.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

Automated temporal tracking and segmentation of lymphoma on serial CT examinations

Purpose: It is challenging to reproducibly measure and compare cancer lesions on numerous follow-up studies; the process is time-consuming and error-prone. In this paper, we show a method to automatically and reproducibly identify and segment abnormal lymph nodes in serial computed tomography (CT) exams. Methods: Our method leverages initial identification of enlarged (abnormal) lymph nodes in the baseline scan. We then identify an approximate region for the node in the follow-up scans using nonrigid image registration. The baseline scan is also used to locate regions of normal, non-nodal tissue surrounding the lymph node and to map them onto the follow-up scans, in order to reduce the search space to locate the lymph node on the follow-up scans. Adaptive region-growing and clustering algorithms are then used to obtain the final contours for segmentation. We applied our method to 24 distinct enlarged lymph nodes at multiple time points from 14 patients. The scan at the earlier time point was used as the baseline scan to be used in evaluating the follow-up scan, resulting in 70 total test cases (e.g., a series of scans obtained at 4 time points results in 3 test cases). For each of the 70 cases, a ''reference standard'' was obtained by manual segmentation by a radiologist. Assessment according to response evaluation criteria in solid tumors (RECIST) using our method agreed with RECIST assessments made using the reference standard segmentations in all test cases, and by calculating node overlap ratio and Hausdorff distance between the computer and radiologist-generated contours. Results: Compared to the reference standard, our method made the correct RECIST assessment for all 70 cases. The average overlap ratio was 80.7 {+-} 9.7% s.d., and the average Hausdorff distance was 3.2 {+-} 1.8 mm s.d. The concordance correlation between automated and manual segmentations was 0.978 (95% confidence interval 0.962, 0.984). The 100% agreement in our sample between our method and the standard with regard to RECIST classification suggests that the true disagreement rate is no more than 6%. Conclusions: Our automated lymph node segmentation method achieves excellent overall segmentation performance and provides equivalent RECIST assessment. It potentially will be useful to streamline and improve cancer lesion measurement and tracking and to improve assessment of cancer treatment response.

62 RADIOLOGY AND NUCLEAR MEDICINE↗

Controlled Nonlinear Stochastic Delay Equations: Part I: Modeling and Approximations

This two-part paper deals with 'foundational' issues that have not been previously considered in the modeling and numerical optimization of nonlinear stochastic delay systems. There are new classes of models, such as those with nonlinear functions of several controls (such as products), each with is own delay, controlled random Poisson measure driving terms, admissions control with delayed retrials, and others. There are two basic and interconnected themes for these models. The first, dealt with in this part, concerns the definition of admissible control. The classical definition of an admissible control as a nonanticipative relaxed control is inadequate for these models and needs to be extended. This is needed for the convergence proofs of numerical approximations for optimal controls as well as to have a well-defined model. It is shown that the new classes of admissible controls do not enlarge the range of the value functions, is closed (together with the associated paths) under weak convergence, and is approximatable by ordinary controls. The second theme, dealt with in Part II, concerns transportation equation representations, and their role in the development of numerical algorithms with much reduced memory and computational requirements.

97 MATHEMATICS AND COMPUTING↗

Ab-initio Calculations of Absorption Spectra of Semiconducting Nanowires Within Many Body Perturbation Theory

We present a study of the optical absorption spectra of thin silicon nanowires using many-body perturbation theory. We solve the Bethe-Salpeter equation in the static approximation using a technique that avoids explicit calculation of empty electronic states, as well as storage and inversion of the dielectric matrix. We provide a detailed assessment of the numerical accuracy of this technique, when using plane wave basis sets and periodically repeated supercells. Our calculations show that establishing numerical error bars of computed spectra is critical, in order to draw meaningful comparisons with experiments and between results obtained within different algorithms. We also discuss the influence of surface structure on the absorption spectra of nanowires with {approx_equal}1-nm diameter. Finally, we compare our calculations with those obtained within time-dependent density functional theory and find substantial differences, more pronounced than in the case of Si nanoparticles with the same diameter.

36 MATERIALS SCIENCE↗