Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “algorithmic efficiency”

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 73 records · Page 4

Adapting Wave-front Algorithms to Efficiently Utilize Systems with Deep Communication Hierarchies

Large-scale systems increasingly exhibit a differential between intra-chip and inter-chip communication performance especially in hybrid systems using accelerators. Processorcores on the same socket are able to communicate at lower latencies, and with higher bandwidths, than cores on different sockets either within the same node or between nodes. A key challenge is to efficiently use this communication hierarchy and hence optimize performance. We consider here the class of applications that contains wavefront processing. In these applications data can only be processed after their upstream neighbors have been processed. Similar dependencies result between processors in which communication is required to pass boundary data downstream and whose cost is typically impacted by the slowest communication channel in use. In this work we develop a novel hierarchical wave-front approach that reduces the use of slower communications in the hierarchy but at the cost of additional steps in the parallel computation and higher use of on-chip communications. This tradeoff is explored using a performance model. An implementation using the Reverse-acceleration programming model on the petascale Roadrunner system demonstrates a 27% performance improvement at full system-scale on a kernel application. The approach is generally applicable to large-scale multi-core and accelerated systems where a differential in system communication performance exists.

43 PARTICLE ACCELERATORS↗

Efficient numerical algorithm for multi-level ionization of high-atomic-number gases

An efficient numerical algorithm for laser driven multi-level ionization of high-atomic-number gases is proposed and implemented in an electromagnetic particle-in-cell code SPACE. The algorithm is based on analytical solutions to the system of differential equations describing ionization evolution. Using analytical solutions resolves the multiscale issue of ionization due to different characteristic time scales of ionization processes and the main code time step. Algorithm efficiency and memory requirements are significantly improved by using a locally reduced system of differential equations. The algorithm also assigns proper orbital quantum numbers and their projections to ionization states. The algorithm is verified and validated using experimental data.

Cheng, A. (ORCID:000000021945282X)↗

An algorithm for efficient metal artifact reductions in permanent seed implants

Purpose: In permanent seed implants, 60 to more than 100 small metal capsules are inserted in the prostate, creating artifacts in x-ray computed tomography (CT) imaging. The goal of this work is to develop an automatic method for metal artifact reduction (MAR) from small objects such as brachytherapy seeds for clinical applications. Methods: The approach for MAR is based on the interpolation of missing projections by directly using raw helical CT data (sinogram). First, an initial image is reconstructed from the raw CT data. Then, the metal objects segmented from the reconstructed image are reprojected back into the sinogram space to produce a metal-only sinogram. The Steger method is used to determine precisely the position and edges of the seed traces in the raw CT data. By combining the use of Steger detection and reprojections, the missing projections are detected and replaced by interpolation of non-missing neighboring projections. Results: In both phantom experiments and patient studies, the missing projections have been detected successfully and the artifacts caused by metallic objects have been substantially reduced. The performance of the algorithm has been quantified by comparing the uniformity between the uncorrected and the corrected phantom images. The results of the artifact reduction algorithm are indistinguishable from the true background value. Conclusions: An efficient algorithm for MAR in seed brachytherapy was developed. The test results obtained using raw helical CT data for both phantom and clinical cases have demonstrated that the proposed MAR method is capable of accurately detecting and correcting artifacts caused by a large number of very small metal objects (seeds) in sinogram space. This should enable a more accurate use of advanced brachytherapy dose calculations, such as Monte Carlo simulations.

60 APPLIED LIFE SCIENCES↗

Parallel Algorithms for Efficient Computation of High-Order Line Graphs of Hypergraphs

This paper considers structures of systems beyond dyadic (pairwise) interactions and investigates mathematical modeling of multi-way interactions and connections as hypergraphs, where captured relationships among system entities are set-valued. To date, in most situations, entities in a hypergraph are considered connected as long as there is at least one common ``neighbor''. However, minimal commonality sometimes discards the ``strength'' of connections and interactions among groups. To this end, considering the ``width'' of a connection, referred to as the \emph{$s$-overlap} of neighbors, provides more meaningful insights into how closely the communities or entities interact with each other. In addition, $s$-overlap computation is the fundamental kernel to construct the line graph of a hypergraph, a low-order approximation of the hypergraph which can carry significant information about the original hypergraph. Subsequent stages of a data analytics pipeline then can apply highly-tuned graph algorithms on the line graph to reveal important features. Given a hypergraph, computing the $s$-overlaps by exhaustively considering all pairwise entities can be computationally prohibitive. To tackle this challenge, we develop efficient algorithms to compute $s$-overlaps and the corresponding line graph of a hypergraph. We propose several heuristics to avoid execution of redundant work and improve performance of the $s$-overlap computation. Our parallel algorithm, combined with these heuristics, is orders of magnitude (more than $10\times$) faster than the naive algorithm in all cases and the SpGEMM algorithm with filtration in most cases (especially with large $s$ value).

hypergraph algorithms, graph algorithms, parallel ↗

Cholesky-based experimental design for Gaussian process and kernel-based emulation and calibration.

Gaussian processes and other kernel-based methods are used extensively to construct approximations of multivariate data sets. The accuracy of these approximations is dependent on the data used. This paper presents a computationally efficient algorithm to greedily select training samples that minimize the weighted L p error of kernel-based approximations for a given number of data. The method successively generates nested samples, with the goal of minimizing the error in high probability regions of densities specified by users. The algorithm presented is extremely simple and can be implemented using existing pivoted Cholesky factorization methods. Training samples are generated in batches which allows training data to be evaluated (labeled) in parallel. For smooth kernels, the algorithm performs comparably with the greedy integrated variance design but has significantly lower complexity. Numerical experiments demonstrate the efficacy of the approach for bounded, unbounded, multi-modal and non-tensor product densities. We also show how to use the proposed algorithm to efficiently generate surrogates for inferring unknown model parameters from data using Bayesian inference.

97 MATHEMATICS AND COMPUTING↗

An implementation analysis of the linear discontinuous finite element method

This paper provides an implementation analysis of the linear discontinuous finite element method (LD-FEM) that spans the space of (l, x, y, z). A practical implementation of LD includes 1) selecting a computationally efficient algorithm to solve the 4 x 4 matrix system Ax = b that describes the angular flux in a mesh element, and 2) choosing how to store the data used to construct the matrix A and the vector b to either reduce memory consumption or increase computational speed. To analyze the first of these, three algorithms were selected to solve the 4 x 4 matrix equation: Cramer's rule, a streamlined implementation of Gaussian elimination, and LAPACK's Gaussian elimination subroutine dgesv. The results indicate that Cramer's rule and the streamlined Gaussian elimination algorithm perform nearly equivalently and outperform LAPACK's implementation of Gaussian elimination by a factor of 2. To analyze the second implementation detail, three formulations of the discretized LD-FEM equations were provided for implementation in a transport solver: 1) a low-memory formulation, which relies heavily on 'on-the-fly' calculations and less on the storage of pre-computed data, 2) a high-memory formulation, which pre-computes much of the data used to construct A and b, and 3) a reduced-memory formulation, which lies between the low - and high-memory formulations. These three formulations were assessed in the Jaguar transport solver based on relative memory footprint and computational speed for increasing mesh size and quadrature order. The results indicated that the memory savings of the low-memory formulation were not sufficient to warrant its implementation. The high-memory formulation resulted in a significant speed advantage over the reduced-memory option (10-50%), but also resulted in a proportional increase in memory consumption (5-45%) for increasing quadrature order and mesh count; therefore, the practitioner should weigh the system memory constraints against any required runtime constraints to determine which option is more suitable for his or her specific applications. (authors)

97 MATHEMATICS AND COMPUTING↗

An efficient iterative algorithm for computation of scattering from dielectric objects.

We have developed an efficient iterative algorithm for electromagnetic scattering of arbitrary but relatively smooth dielectric objects. The algorithm iteratively adapts the equivalent surface currents until the electromagnetic fields inside and outside the dielectric objects match the boundary conditions. Theoretical convergence is analyzed for two examples that solve scattering of plane waves incident upon air/dielectric slabs of semi-infinite and finite thicknesses. We applied the iterative algorithm for simulation of sinusoidally-perturbed dielectric slab on one side and the method converged for such unsmooth surfaces. We next simulated the shift in radiation pattern of a 6-inch dielectric lens for different offsets of the feed antenna on the focal plane. The result is compared to that of the Geometrical Optics (GO).

36 MATERIALS SCIENCE↗

Accelerated simulation of stochastic particle removal processes in particle-resolved aerosol models

Stochastic particle-resolved methods have proven useful for simulating multi-dimensional systems such as composition-resolved aerosol size distributions. While particle-resolved methods have substantial benefits for highly detailed simulations, these techniques suffer from high computational cost, motivating efforts to improve their algorithmic efficiency. Here we formulate an algorithm for accelerating particle removal processes by aggregating particles of similar size into bins. We present the Binned Algorithm for particle removal processes and analyze its performance with application to the atmospherically relevant process of aerosol dry deposition. We show that the Binned Algorithm can dramatically improve the efficiency of particle removals, particularly for low removal rates, and that computational cost is reduced without introducing additional error. In simulations of aerosol particle removal by dry deposition in atmospherically relevant conditions, we demonstrate about 50-times increase in algorithm efficiency.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

An efficient reconstruction algorithm for differential phase-contrast tomographic images from a limited number of views

The main focus of this paper is reconstruction of tomographic phase-contrast image from a set of projections. We propose an efficient reconstruction algorithm for differential phase-contrast computed tomography that can considerably reduce the number of projections required for reconstruction. The key result underlying this research is a projection theorem that states that the second derivative of the projection set is linearly related to the Laplacian of the tomographic image. The proposed algorithm first reconstructs the Laplacian image of the phase-shift distribution from the second-derivative of the projections using total variation regularization. The second step is to obtain the phase-shift distribution by solving a Poisson equation whose source is the Laplacian image previously reconstructed under the Dirichlet condition. We demonstrate the efficacy of this algorithm using both synthetically generated simulation data and projection data acquired experimentally at a synchrotron. The experimental phase data were acquired from a human coronary artery specimen using dark-field-imaging optics pioneered by our group. Our results demonstrate that the proposed algorithm can reduce the number of projections to approximately 33% as compared with the conventional filtered backprojection method, without any detrimental effect on the image quality.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

A quantum algorithm to efficiently sample from interfering binary trees

Quantum computers provide an opportunity to efficiently sample from probability distributions that include non-trivial interference effects between amplitudes. Using a simple process wherein all possible state histories can be specified by a binary tree, we construct an explicit quantum algorithm that runs in polynomial time to sample from the process once. The corresponding naive Markov Chain algorithm does not produce the correct probability distribution and an explicit classical calculation of the full distribution requires exponentially many operations. Finally, the problem can be reduced to a system of two qubits with repeated measurements, shedding light on a quantum-inspired efficient classical algorithm.

97 MATHEMATICS AND COMPUTING↗

Efficient quantum algorithm for dissipative nonlinear differential equations

Significance Nonlinear differential equations appear in many domains and are notoriously difficult to solve. Whereas previous quantum algorithms for general nonlinear differential equations have complexity exponential in the evolution time, we give the first quantum algorithm for dissipative nonlinear differential equations that is efficient provided the dissipation is sufficiently strong relative to nonlinear and forcing terms and the solution does not decay too rapidly. We also establish a lower bound showing that differential equations with sufficiently weak dissipation have worst-case complexity exponential in time, giving an almost tight classification of the quantum complexity of simulating nonlinear dynamics. Furthermore, numerical results for the Burgers equation suggest that our algorithm may potentially address complex nonlinear phenomena even in regimes with weaker dissipation.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

Tuning Multigrid Methods with Robust Optimization and Local Fourier Analysis

Local Fourier analysis is a useful tool for predicting and analyzing the performance of many efficient algorithms for the solution of discretized PDEs, such as multigrid and domain decomposition methods. The crucial aspect of local Fourier analysis is that it can be used to minimize an estimate of the spectral radius of a stationary iteration, or the condition number of a preconditioned system, in terms of a symbol representation of the algorithm. In practice, this is a “minimax” problem, minimizing with respect to solver parameters the appropriate measure of work, which involves maximizing over the Fourier frequency. Often, several algorithmic parameters may be determined by local Fourier analysis in order to obtain efficient algorithms. Analytical solutions to minimax problems are rarely possible beyond simple problems; the status quo in local Fourier analysis involves grid sampling, which is prohibitively expensive in high dimensions. In this paper, we propose and explore optimization algorithms to solve these problems efficiently. Finally, several examples, with known and unknown analytical solutions, are presented to show the effectiveness of these approaches.

97 MATHEMATICS AND COMPUTING↗

Towards provably efficient quantum algorithms for large-scale machine-learning models

Large machine learning models are revolutionary technologies of artificial intelligence whose bottlenecks include huge computational expenses, power, and time used both in the pre-training and fine-tuning process. In this work, we show that fault-tolerant quantum computing could possibly provide provably efficient resolutions for generic (stochastic) gradient descent algorithms, scaling as $\mathcal{O}$(T 2 x polylog($n$)), where n is the size of the models and T is the number of iterations in the training, as long as the models are both sufficiently dissipative and sparse, with small learning rates. Based on earlier efficient quantum algorithms for dissipative differential equations, we find and prove that similar algorithms work for (stochastic) gradient descent, the primary algorithm for machine learning. In practice, we benchmark instances of large machine learning models from 7 million to 103 million parameters. We find that, in the context of sparse training, a quantum enhancement is possible at the early stage of learning after model pruning, motivating a sparse parameter download and re-upload scheme. Our work shows solidly that fault-tolerant quantum algorithms could potentially contribute to most state-of-the-art, large-scale machine-learning problems.

97 MATHEMATICS AND COMPUTING↗

An Efficient Numerical Algorithm for Solving Coupled Time-Dependent Ginzburg-Landau Equation for Superconductivity and Elasticity

A decoupled finite element algorithm is developed for simulating the vortex dynamics on an elastic superconductor which couples the time-dependent Ginzburg- Landau equation with the complex-valued superconducting order parameter and the vector-valued magnetic potential, and the elasticity equation. We present an iterative algorithm for the decoupled system arising from the time and spatial discretization using a combination of preconditioner, algebraic multigrid method (AMG) and preconditioned conjugate gradient method (PCG). The iterative algorithm allows us to perform large-scale three-dimensional simulations of mesoscale pattern formation during superconducting phase transitions with arbitrary elastic boundary conditions. Here, the performance and efficiency of the algorithm are numerically verified by several benchmark problems, exhibiting up to two orders of magnitude improvement depending on the scale of discrete system compared to the exact solver.

Efficiency↗

An efficient reconstruction algorithm for diffusion on triangular grids using the nodal discontinuous Galerkin method

High-energy-density (HED) hydrodynamics studies such as those relevant to inertial confinement fusion and astrophysics require highly disparate densities, temperatures, viscosities, and other diffusion parameters over relatively short spatial scales. This presents a challenge for high-order accurate methods to effectively resolve the hydrodynamics at these scales, particularly in the presence of highly disparate diffusion. A significant volume of engineering and physics applications use an unstructured discontinuous Galerkin (DG) method developed based on the finite element mesh generation and algorithmic framework. This work discusses the application of an affine reconstructed nodal DG method for unstructured grids of triangles. Solving the diffusion terms in the DG method is non-trivial due to the solution representations being piecewise continuous. Hence, the diffusive flux is not defined on the interface of elements. The proposed numerical approach reconstructs a smooth solution in a parallelogram that is enclosed by the quadrilateral formed by two adjacent triangle elements. The interface between these two triangles is the diagonal of the enclosed parallelogram. Similar to triangles, the mapping of parallelograms from a physical domain to a reference domain is an affine mapping, which is necessary for an accurate and efficient implementation of the numerical algorithm. Thus, all computations can still be performed on the reference domain, which promotes efficiency in computation and storage. This reconstruction does not make assumptions on choice of polynomial basis. Reconstructed DG algorithms have previously been developed for modal implementations of the convection–diffusion equations. However, to the best of the authors’ knowledge, this is the first practical guideline that has been proposed for applying the reconstructed algorithm on a nodal discontinuous Galerkin method with a focus on accuracy and efficiency. As a result, the algorithm is demonstrated on a number of benchmark cases as well as a challenging substantive problem in HED hydrodynamics with highly disparate diffusion parameters.

Computational efficiency↗

An Efficient Numerical Algorithm for Solving Data Driven Feedback Control Problems

The goal of this paper is to solve a class of stochastic optimal control problems numerically, in which the state process is governed by an Itô type stochastic differential equation with control process entering both in the drift and the diffusion, and is observed partially. The optimal control of feedback form is determined based on the available observational data. In this work, we call this type of control problems the data driven feedback control. The computational framework that we introduce to solve such type of problems aims to find the best estimate for the optimal control as a conditional expectation given the observational information. To make our method feasible in providing timely feedback to the controlled system from data, we develop an efficient stochastic optimization algorithm to implement our computational framework.

97 MATHEMATICS AND COMPUTING↗

A Pareto Algorithm for Efficient De Novo Design of Multi-functional Molecules

Here, we have introduced a Pareto sorting algorithm into Synopsis, a de novo design program that generates synthesizable molecules with desirable properties. We give a detailed description of the algorithm and illustrate its working in 2 different de novo design settings: the design of putative dual and selective FGFR and VEGFR inhibitors, and the successful design of organic structure determining agents (OSDAs) for the synthesis of zeolites. We show that the introduction of Pareto sorting not only enables the simultaneous optimization of multiple properties but also greatly improves the performance of the algorithm to generate molecules with hard-to-meet constraints. This in turn allows us to suggest approaches to address the problem of false positive hits in de novo structure based drug design by introducing structural and physicochemical constraints in the designed molecules, and by forcing essential interactions between these molecules and their target receptor.

60 APPLIED LIFE SCIENCES↗

Demonstration of the rodeo algorithm on a quantum computer

The rodeo algorithm is an efficient algorithm for eigenstate preparation and eigenvalue estimation for any observable on a quantum computer. This makes it a promising tool for studying the spectrum and structure of atomic nuclei as well as other fields of quantum many-body physics. The only requirement is that the initial state has sufficient overlap probability with the desired eigenstate. While it is exponentially faster than well-known algorithms such as phase estimation and adiabatic evolution for eigenstate preparation, it has yet to be implemented on an actual quantum device. In this work, we apply the rodeo algorithm to determine the energy levels of a random one-qubit Hamiltonian, resulting in a relative error of 0.08% using mid-circuit measurements on the IBM Q device Casablanca. This surpasses the accuracy of directly-prepared eigenvector expectation values using the same quantum device. We take advantage of the high-accuracy energy determination and use the Hellmann-Feynman theorem to compute eigenvector expectation values for a different random one-qubit observable. For the Hellmann-Feynman calculations, we find a relative error of 0.7%. Here, we conclude by discussing possible future applications of the rodeo algorithm for multi-qubit Hamiltonians.

algorithm↗