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 613 records · Page 34

An Efficient Image Recovery Algorithm for Diffraction Tomography Systems

A diffraction tomography system has potential application in ultrasonic medical imaging area. It is capable of achieving imagery with the ultimate resolution of one quarter the wavelength by collecting ultrasonic backscattering data from a circular array of sensors and reconstructing the object reflectivity using a digital image recovery algorithm performed by a computer. One advantage of such a system is that is allows a relatively lower frequency wave to penetrate more deeply into the object and still achieve imagery with a reasonable resolution. An efficient image recovery algorithm for the diffraction tomography system was originally developed for processing a wide beam spaceborne SAR data...

Jin, Michael Y.↗

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

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

97 MATHEMATICS AND COMPUTING↗

Reliable and Efficient Parallel Processing Algorithms and Architectures for Modern Signal Processing

Least-squares (LS) estimations and spectral decomposition algorithms constitute the heart of modern signal processing and communication problems. Implementations of recursive LS and spectral decomposition algorithms onto parallel processing architectures such as systolic arrays with efficient fault-tolerant schemes are the major concerns of this dissertation. There are four major results in this dissertation. First, we propose the systolic block Householder transformation with application to the recursive least-squares minimization. It is successfully implemented on a systolic array with a two-level pipelined implementation at the vector level as well as at the word level. Second, a real-time algorithm-based concurrent error detection scheme based on the residual method is proposed for the QRD RLS systolic array. The fault diagnosis, order degraded reconfiguration, and performance analysis are also considered. Third, the dynamic range, stability, error detection capability under finite-precision implementation, order degraded performance, and residual estimation under faulty situations for the QRD RLS systolic array are studied in details. Finally, we propose the use of multi-phase systolic algorithms for spectral decomposition based on the QR algorithm. Two systolic architectures, one based on triangular array and another based on rectangular array, are presented for the multiphase operations with fault-tolerant considerations. Eigenvectors and singular vectors can be easily obtained by using the multi-pase operations. Performance issues are also considered.

Liu, Kuojuey Ray↗

Computationally Efficient Motion Planning Algorithms for Agile Autonomous Vehicles in Cluttered Environments

Fast, real-time motion planning of an agile, autonomous vehicle in a cluttered environment, with many geometrically-fixed obstacles, is a very complex problem, especially because of the vehicle dynamics constraints and resource constrained computational capabilities onboard the vehicle. In this paper, we present computationally-efficient versions of our novel motion planning algorithm called the Spherical Expansion and Sequential Convex Programming (SE–SCP) algorithm. The SE–SCP algorithm first uses a spherical-expansion-based randomized sampling algorithm to explore the workspace. Oncea path is found from the start position to the goal position, the algorithm computes a locally optimal trajectory, within its homotopy class for a desired cost function, by solving a sequence of convex optimization problems. Thus, the SE–SCP algorithm is anytime locally optimal and the trajectory is globally optimal if the number of samples tends to infinity. In this paper, we further enhance the computational efficiency of the SE–SCP algorithm using uni-directional and bi-directional rewiring techniques. We also present a detailed proof of the local optimality characteristics of the new SE–SCP algorithms for aspecial case of vehicle dynamics. Simulation examples involving quadrotor and spacecraft help demonstrate the effectiveness of our new algorithms.

Bandyopadhyay, Saptarshi↗

SU-E-T-477: An Efficient Dose Correction Algorithm Accounting for Tissue Heterogeneities in LDR Brachytherapy

Purpose: Seed brachytherapy is currently used for adjuvant radiotherapy of early stage prostate and breast cancer patients. The current standard for calculation of dose surrounding the brachytherapy seeds is based on American Association of Physicist in Medicine Task Group No. 43 (TG-43 formalism) which generates the dose in homogeneous water medium. Recently, AAPM Task Group No. 186 emphasized the importance of accounting for tissue heterogeneities. This can be done using Monte Carlo (MC) methods, but it requires knowing the source structure and tissue atomic composition accurately. In this work we describe an efficient analytical dose inhomogeneity correction algorithm implemented using MIM Symphony treatment planning platform to calculate dose distributions in heterogeneous media. Methods: An Inhomogeneity Correction Factor (ICF) is introduced as the ratio of absorbed dose in tissue to that in water medium. ICF is a function of tissue properties and independent of source structure. The ICF is extracted using CT images and the absorbed dose in tissue can then be calculated by multiplying the dose as calculated by the TG-43 formalism times ICF. To evaluate the methodology, we compared our results with Monte Carlo simulations as well as experiments in phantoms with known density and atomic compositions. Results: The dose distributions obtained through applying ICF to TG-43 protocol agreed very well with those of Monte Carlo simulations as well as experiments in all phantoms. In all cases, the mean relative error was reduced by at least 50% when ICF correction factor was applied to the TG-43 protocol. Conclusion: We have developed a new analytical dose calculation method which enables personalized dose calculations in heterogeneous media. The advantages over stochastic methods are computational efficiency and the ease of integration into clinical setting as detailed source structure and tissue segmentation are not needed. University of Toronto, Natural Sciences and Engineering Research Council of Canada.

60 APPLIED LIFE SCIENCES↗

Maximum likelihood algorithm using an efficient scheme for computing sensitivities and parameter confidence intervals

Improved techniques for estimating airplane stability and control derivatives and their standard errors are presented. A maximum likelihood estimation algorithm is developed which relies on an optimization scheme referred to as a modified Newton-Raphson scheme with estimated sensitivities (MNRES). MNRES determines sensitivities by using slope information from local surface approximations of each output variable in parameter space. The fitted surface allows sensitivity information to be updated at each iteration with a significant reduction in computational effort compared to integrating the analytically-determined sensitivity equations or using a finite difference scheme. An aircraft estimation problem is solved using real flight data to compare MNRES with the commonly used modified Newton-Raphson technique; MNRES is found to be faster and more generally applicable. Parameter standard errors are determined using a random search technique. The confidence intervals obtained are compared with Cramer-Rao lower bounds at the same confidence level. It is observed that the nonlinearity of the cost function is an important factor in the relationship between Cramer-Rao bounds and the error bounds determined by the search technique.

Murphy, P. C.↗

An efficient and robust algorithm for two dimensional time dependent incompressible Navier-Stokes equations: High Reynolds number flows

An algorithm is presented for unsteady two-dimensional incompressible Navier-Stokes calculations. This algorithm is based on the fourth order partial differential equation for incompressible fluid flow which uses the streamfunction as the only dependent variable. The algorithm is second order accurate in both time and space. It uses a multigrid solver at each time step. It is extremely efficient with respect to the use of both CPU time and physical memory. It is extremely robust with respect to Reynolds number.

Goodrich, John W.↗

An efficient and robust algorithm for two dimensional time dependent incompressible Navier-Stokes equations - High Reynolds number flows

An algorithm is presented for unsteady two-dimensional incompressible Navier-Stokes calculations. This algorithm is based on the fourth order partial differential equation for incompressible fluid flow which uses the streamfunction as the only dependent variable. The algorithm is second order accurate in both time and space. It uses a multigrid solver at each time step. It is extremely efficient with respect to the use of both CPU time and physical memory. It is extremely robust with respect to Reynolds number.

Goodrich, John W.↗

An efficient advancing front algorithm for Delaunay triangulation

There has been some recent interest in fluid dynamics calculations on unstructured meshes. One method of unstructured mesh generation involves Delaunay triangulation. This method has certain advantages but it can be expensive to implement. Furthermore, there can be problems with crossing grid lines near boundaries. A method shown here avoids many of the robustness and efficiency problems previously associated with Delaunay triangulation. As an added feature, a simple algorithm is shown which allows removal of diagonal edges from cells that are nearly rectangular. This can result in significant savings in the cost per iteration of a flow solver using this grid.

Merriam, Marshal L.↗

New Efficient Sparse Space Time Algorithms for Superparameterization on Mesoscales

Superparameterization (SP) is a large-scale modeling system with explicit representation of small-scale and mesoscale processes provided by a cloud-resolving model (CRM) embedded in each column of a large-scale model. New efficient sparse space-time algorithms based on the original idea of SP are presented. The large-scale dynamics are unchanged, but the small-scale model is solved in a reduced spatially periodic domain to save the computation cost following a similar idea applied by one of the authors for aquaplanet simulations. In addition, the time interval of integration of the small-scale model is reduced systematically for the same purpose, which results in a different coupling mechanism between the small- and large-scale models. The new algorithms have been applied to a stringent two-dimensional test suite involving moist convection interacting with shear with regimes ranging from strong free and forced squall lines to dying scattered convection as the shear strength varies. The numerical results are compared with the CRM and original SP. It is shown here that for all of the regimes of propagation and dying scattered convection, the large-scale variables such as horizontal velocity and specific humidity are captured in a statistically accurate way (pattern correlations above 0.75) based on space-time reduction of the small-scale models by a factor of 1/3; thus, the new efficient algorithms for SP result in a gain of roughly a factor of 10 in efficiency while retaining a statistical accuracy on the large-scale variables. Even the models with 1/6 reduction in space-time with a gain of 36 in efficiency are able to distinguish between propagating squall lines and dying scattered convection with a pattern correlation above 0.6 for horizontal velocity and specific humidity. These encouraging results suggest the possibility of using these efficient new algorithms for limited-area mesoscale ensemble forecasting.

99 GENERAL AND MISCELLANEOUS↗

Robustness, generality and efficiency of optimization algorithms in practical applications

The theoretical foundations of two approaches, sequential quadratic programming (SQP) and optimality criteria (OC), are analyzed and compared, with emphasis on the critical importance of parameters such as accuracy, generality, robustness, efficiency, and ease of use in large scale structural optimization. A simplified fighter wing and active control of space structures are considered with other example problems. When applied to general system identification problems, the OC methods are shown to lose simplicity and demonstrate lack of generality, accuracy and robustness. It is concluded that the SQP method with a potential constraint strategy is a better choice as compared to the currently prevalent mathematical programming and OC approaches.

Thanedar, P. B.↗

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↗

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↗

Scaling behavior of quantum nanosystems: Emergence of quasi-particles, collective modes, and mixed exchange symmetry states

Examples of quantum nanosystems are graphene nanoribbons, molecular wires, and superconducting nanoparticles. The objective of the multiscale theory presented here is to provide a new perspective on the coupling of processes across scales in space and time underlying the dynamics of these systems. The long range objective for this multiscale approach is to serve as an efficient computational algorithm. Long space-time dynamics is derived using a perturbation expansion in the ratio {epsilon} of the nearest-neighbor distance to a nanometer-scale characteristic length and a theorem on the equivalence of long time-averages and expectation values. This dynamics is shown to satisfy a coarse-grained wave equation (CGWE) which takes a Schroedinger-like form with modified masses and interactions. The scaling of space and time is determined by the orders of magnitude of various contributions to the N-body potential. If the spatial scale of the coarse-graining is too large, the CGWE would imply an unbounded growth of gradients; if it is too short, the system's size would display uncontrolled growth inappropriate for the bound states of interest, i.e., collective motion or migration within a stable nanoassembly. The balance of these two extremes removes arbitrariness in the choice of the scaling of space-time. Since the long-scale dynamics of each Fermion involves its interaction with many others, we hypothesize that the solutions of the CGWE have mean-field character to good approximation, i.e., can be factorized into single-particle functions. This leads to a coarse-grained mean-field approximation that is distinct in character from traditional Hartree-Fock theory. A variational principle is used to derive equations for the single-particle functions. This theme is developed and used to derive an equation for low-lying disturbances from the ground state corresponding to long wavelength density disturbances or long-scale migration. An algorithm for the efficient simulation of quantum nanosystems is suggested.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

Algorithm Plans Collision-Free Path for Robotic Manipulator

An algorithm has been developed to enable a computer aboard a robot to autonomously plan the path of the manipulator arm of the robot to avoid collisions between the arm and any obstacle, which could be another part of the robot or an external object in the vicinity of the robot. In simplified terms, the algorithm generates trial path segments and tests each segment for potential collisions in an iterative process that ends when a sequence of collision-free segments reaches from the starting point to the destination. The main advantage of this algorithm, relative to prior such algorithms, is computational efficiency: the algorithm is designed to make minimal demands upon the limited computational resources available aboard a robot. This path-planning algorithm utilizes a modified version of the collision-detection method described in "Improved Collision-Detection Method for Robotic Manipulator" (NPO-30356), NASA Tech Briefs, Vol. 27, No. 3 (June 2003), page 72. The method involves utilization of mathematical models of the robot constructed prior to operation and similar models of external objects constructed automatically from sensory data acquired during operation. This method incorporates a previously developed method, known in the art as the method of oriented bounding boxes (OBBs), in which an object is represented approximately, for computational purposes, by a box that encloses its outer boundary. Because many parts of a robotic manipulator are cylindrical, the OBB method has been extended in this method to enable the approximate representation of cylindrical parts by use of octagonal or other multiple-OBB assemblies denoted oriented bounding prisms (OBPs). A multiresolution OBB/OBP representation of the robot and its manipulator arm and a multiresolution OBB representation of external objects (including terrain) are constructed and used in a process in which collisions at successively finer resolutions are detected through computational detection of overlaps between the corresponding OBB and OBP models. For computational efficiency, the process is started at the coarsest resolution and stopped as soon as possible, preferably before reaching the finest resolution. At the coarsest resolution, there is a single OBB enclosing all relevant external objects and a single OBB enclosing the entire robot. At the next finer level of resolution, the coarsest-resolution OBB is divided into two OBBs, and so forth. If no collision is detected at the coarsest resolution, then there is no need for further computation to detect collisions. If a collision is detected at the coarsest resolution, then tests for collisions are performed at the next finer level of resolution. This process is continued to successively finer resolutions until either no more collisions are detected or the finest resolution is reached.

Backes, Paul↗

SPACE: 3D parallel solvers for Vlasov-Maxwell and Vlasov-Poisson equations for relativistic plasmas with atomic transformations

A parallel, relativistic, three-dimensional particle-in-cell code SPACE has been developed for the simulation of electromagnetic fields, relativistic particle beams, and plasmas. In addition to the standard second-order Particle-in-Cell (PIC) algorithm, SPACE includes efficient novel algorithms to resolve atomic physics processes such as multi-level ionization of plasma atoms, recombination, and electron attachment to dopants in dense neutral gases. SPACE also contains a highly adaptive particle-based method, called Adaptive Particle-in-Cloud (AP-Cloud), for solving the Vlasov-Poisson problems. It eliminates the traditional Cartesian mesh of PIC and replaces it with an adaptive octree data structure. The code's algorithms, structure, capabilities, parallelization strategy, and performance have been discussed. Additionally, typical examples of SPACE applications to accelerator science and engineering problems are described.

43 PARTICLE ACCELERATORS↗

Investigation of fast and efficient lossless compression algorithms for macromolecular crystallography experiments

Structural biology experiments benefit significantly from state-of-the-art synchrotron data collection. One can acquire macromolecular crystallography (MX) diffraction data on large-area photon-counting pixel-array detectors at framing rates exceeding 1000 frames per second, using 200 Gbps network connectivity, or higher when available. In extreme cases this represents a raw data throughput of about 25 GB s −1 , which is nearly impossible to deliver at reasonable cost without compression. Our field has used lossless compression for decades to make such data collection manageable. Many MX beamlines are now fitted with DECTRIS Eiger detectors, all of which are delivered with optimized compression algorithms by default, and they perform well with current framing rates and typical diffraction data. However, better lossless compression algorithms have been developed and are now available to the research community. Here one of the latest and most promising lossless compression algorithms is investigated on a variety of diffraction data like those routinely acquired at state-of-the-art MX beamlines.

36 MATERIALS SCIENCE↗