Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “fast algorithm”

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 19 records
All sourcesNASA NTRSDOE OSTI
NASA NTRS1995

Development of Fast Algorithms Using Recursion, Nesting and Iterations for Computational Electromagnetics

In the first phase of our work, we have concentrated on laying the foundation to develop fast algorithms, including the use of recursive structure like the recursive aggregate interaction matrix algorithm (RAIMA), the nested equivalence principle algorithm (NEPAL), the ray-propagation fast multipole algorithm (RPFMA), and the multi-level fast multipole algorithm (MLFMA). We have also investigated the use of curvilinear patches to build a basic method of moments code where these acceleration techniques can be used later. In the second phase, which is mainly reported on here, we have concentrated on implementing three-dimensional NEPAL on a massively parallel machine, the Connection Machine CM-5, and have been able to obtain some 3D scattering results. In order to understand the parallelization of codes on the Connection Machine, we have also studied the parallelization of 3D finite-difference time-domain (FDTD) code with PML material absorbing boundary condition (ABC). We found that simple algorithms like the FDTD with material ABC can be parallelized very well allowing us to solve within a minute a problem of over a million nodes. In addition, we have studied the use of the fast multipole method and the ray-propagation fast multipole algorithm to expedite matrix-vector multiplication in a conjugate-gradient solution to integral equations of scattering. We find that these methods are faster than LU decomposition for one incident angle, but are slower than LU decomposition when many incident angles are needed as in the monostatic RCS calculations.

Chew, W. C.↗
NASA NTRS1971

A fast algorithm for the calculation of junction capacitance and its application for impurity profile determination

A fast algorithm is described which calculates the space charge layer width and junction capacitance for an arbitrary impurity profile and for plane, cylindrical and spherical junctions. The algorithm is based on the abrupt space charge edge (ASCE) approximation. A method to use the algorithm for the determination of impurity profiles for two-sided junctions is presented. An expression is derived for the built-in voltage to be used for capacitance calculations with the ASCE approximation. Experimental evidence is given that the algorithm permits very accurate capacitance calculations and also predicts the exact temperature dependence of the junction capacitance.

Deman, H. J. J.↗
NASA NTRS1972

A fast algorithm for the calculation of junction capacitance and its application for impurity profile determination.

A fast algorithm is described which calculates the space charge layer width and junction capacitance for an arbitrary impurity profile and for plane, cylindrical and spherical junctions. The algorithm is based on the abrupt space charge edge (ASCE) approximation. A method to use the algorithm for the determination of impurity profiles for two-sided junctions is presented. An expression is derived for the built-in voltage to be used for capacitance calculations with the ASCE approximation. Experimental evidence is given that the algorithm permits very accurate capacitance calculations and also predicts the exact temperature dependence of the junction capacitance.

De Man, H. J. J.↗
NASA NTRS2000

A New Fast Algorithm to Completely Account for Non-Lambertian Surface Reflection of The Earth

Surface bidirectional reflectance distribution function (BRDF) influences not only radiance just about the surface, but that emerging from the top of the atmosphere (TOA). In this study we propose a new, fast and accurate, algorithm CASBIR (correction for anisotropic surface bidirectional reflection) to account for such influences on radiance measured above TOA. This new algorithm is based on a 4-stream theory that separates the radiation field into direct and diffuse components in both upwelling and downwelling directions. This is important because the direct component accounts for a substantial portion of incident radiation under a clear sky, and the BRDF effect is strongest in the reflection of the direct radiation reaching the surface. The model is validated by comparison with a full-scale, vector radiation transfer model for the atmosphere-surface system. The result demonstrates that CASBIR performs very well (with overall relative difference of less than one percent) for all solar and viewing zenith and azimuth angles considered in wavelengths from ultraviolet to near-infrared over three typical, but very different surface types. Application of this algorithm includes both accounting for non-Lambertian surface scattering on the emergent radiation above TOA and a potential approach for surface BRDF retrieval from satellite measured radiance.

Qin, Wen-Han↗
NASA NTRS1986

Fast algorithm for calculating chemical kinetics in turbulent reacting flow

This paper addresses the need for a fast batch chemistry solver to perform the kinetics part of a split operator formulation of turbulent reacting flows, with special attention focused on the solution of the ordinary differential equations governing a homogeneous gas-phase chemical reaction. For this purpose, a two-part predictor-corrector algorithm which incorporates an exponentially fitted trapezoidal method was developed. The algorithm performs filtering of ill-posed initial conditions, automatic step-size selection, and automatic selection of Jacobi-Newton or Newton-Raphson iteration for convergence to achieve maximum computational efficiency while observing a prescribed error tolerance. The new algorithm, termed CREK1D (combustion reaction kinetics, one-dimensional), compared favorably with the code LSODE when tested on two representative problems drawn from combustion kinetics, and is faster than LSODE.

Radhakrishnan, K.↗
NASA NTRS1991

A fast algorithm for image-based ranging

Image-based ranging has emerged as a critical issue in the low altitude operation of flight vehicles such as rotorcraft and planetary landers. These flight regimes require ranging systems for recovering the geometry of the terrain and obstacles for use with guidance algorithms. The development of a ranging equation combining image irradiance together with various order spatial partial derivatives and the vehicle motion parameters is discussed. The ranging equation is in the form of a polynomial in scene depth. Two-dimensional linear filters are then used to compute the coefficients of this polynomial to result in a fast image-based ranging algorithm. Performance of the algorithm is demonstrated using laboratory images.

Menon, P. K. A.↗
DOE OSTI2021

Revisiting the ODE Method for Recursive Algorithms: Fast Convergence Using Quasi Stochastic Approximation

Several decades ago, Profs. Sean Meyn and Lei Guo were postdoctoral fellows at ANU, where they shared interest in recursive algorithms. It seems fitting to celebrate Lei Guo's 60th birthday with a review of the ODE Method and its recent evolution. The method has been regarded as a technique for algorithm analysis. It is argued that this viewpoint is backwards: The original stochastic approximation method was surely motivated by an ODE, and tools for analysis came much later (based on establishing robustness of Euler approximations). The paper presents a brief survey of recent research in machine learning that shows the power of algorithm design in continuous time, following by careful approximation to obtain a practical recursive algorithm. While these methods are usually presented in a stochastic setting, this is not a prerequisite. In fact, recent theory shows that rates of convergence can be dramatically accelerated by applying techniques inspired by quasi Monte-Carlo. Subject to conditions, the optimal rate of convergence can be obtained by applying the averaging technique of Polyak and Ruppert. The conditions are not universal, but theory suggests alternatives to achieve acceleration. The theory is illustrated with applications to gradient-free optimization, and policy gradient algorithms for reinforcement learning.

learning and adaptive systems in artificial intell↗
NASA NTRS1991

A fast algorithm for control and estimation using a polynomial state-space structure

One of the major problems associated with the control of flexible structures is the estimation of system states. Since the parameters of the structures are not constant under varying loads and conditions, conventional fixed parameter state estimators can not be used to effectively estimate the states of the system. One alternative is to use a state estimator which adapts to the condition of the system. One such estimator is the Kalman filter. This filter is a time varying recursive digital filter which is based upon a model of the system being measured. This filter adapts the model according to the output of the system. Previously, the Kalman filter has only been used in an off-line capacity due to the computational time required for implementation. With recent advances in computer technology, it is becoming a viable tool for use in the on-line environment. A distributed Kalman filter implementation is described for fast estimation of the state of a flexible arm. A key issue, is the sensor structure and initial work on a distributed sensor that could be used with the Kalman filter is presented.

Shults, James R.↗
DOE OSTI2021

SDSS-V Algorithms: Fast, Collision-free Trajectory Planning for Heavily Overlapping Robotic Fiber Positioners

Robotic fiber positioner (RFP) arrays are becoming heavily adopted in wide-field massively multiplexed spectroscopic survey instruments. RFP arrays decrease nightly operational overheads through rapid reconfiguration between fields and exposures. In comparison to similar instruments, SDSS-V has selected a very dense RFP packing scheme where any point in a field is typically accessible to three or more robots. This design provides flexibility in target assignment. However, the task of collisionless trajectory planning is especially challenging. We present two multiagent distributed control strategies that are highly efficient and computationally inexpensive for determining collision-free paths for RFPs in heavily overlapping workspaces. We demonstrate that a reconfiguration path between two arbitrary robot configurations can be efficiently found if a “folded” state, in which all robot arms are retracted and aligned in a lattice-like orientation, is inserted between the initial and final states. Although developed for SDSS-V, the approach we describe is generic and thus applicable to a wide range of RFP designs and layouts. Robotic fiber positioner technology continues to advance rapidly, and in the near future ultra-densely packed RFP designs may be feasible. Our algorithms are especially capable in routing paths in very crowded environments, where we see efficient results even in regimes significantly more crowded than the SDSS-V RFP design.

42 ENGINEERING↗
DOE OSTI2026

A Fast Algorithm for Computing Zigzag Representatives

Zigzag filtrations of simplicial complexes generalize the usual filtrations by allowing simplex deletions in addition to simplex insertions. The barcodes computed from zigzag filtrations encode the evolution of homological features. Although one can locate a particular feature at any index in the filtration using existing algorithms, the resulting representatives may not be compatible with the zigzag: a representative cycle at one index may not map into a representative cycle at its neighbor. For this, one needs to compute compatible representative cycles along each bar in the barcode. It is known that the barcode for a zigzag filtration with m insertions and deletions can be computed $O(m^ω)$ in time, where $ω < 2.373$ is the matrix multiplication exponent. However, it is not known how to compute the compatible representatives so efficiently. For a non-zigzag filtration, the classical matrix-based algorithm provides representatives in $O(m^3)$ time, which can be improved to $O(m^ω)$. However, no known algorithm for zigzag filtrations computes the representatives with the $O(m^3)$ time bound. We present an $O(m^3 n)$ time algorithm for this problem, where $n ≤ m$ is the size of the largest complex in the filtration.

Persistent homology↗
DOE OSTI2021

A Fast Algorithm for Scanning Transmission Electron Microscopy Imaging and 4D-STEM Diffraction Simulations

Scanning transmission electron microscopy (STEM) is an extremely versatile method for studying materials on the atomic scale. Many STEM experiments are supported or validated with electron scattering simulations. However, using the conventional multislice algorithm to perform these simulations can require extremely large calculation times, particularly for experiments with millions of probe positions as each probe position must be simulated independently. Recently, the plane-wave reciprocal-space interpolated scattering matrix (PRISM) algorithm was developed to reduce calculation times for large STEM simulations. Here, we introduce a new method for STEM simulation: partitioning of the STEM probe into “beamlets,” given by a natural neighbor interpolation of the parent beams. This idea is compatible with PRISM simulations and can lead to even larger improvements in simulation time, as well requiring significantly less computer random access memory (RAM). We have performed various simulations to demonstrate the advantages and disadvantages of partitioned PRISM STEM simulations. We find that this new algorithm is particularly useful for 4D-STEM simulations of large fields of view. We also provide a reference implementation of the multislice, PRISM, and partitioned PRISM algorithms.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2023

Fast Algorithms for Scientific Data Compression

Many scientific simulations and experiments generate terabytes to petabytes of data daily, necessitating data compression techniques. Unlike video and image compression, scientists require methods that accurately preserve primary data (PD) and derived quantities of interest (QoIs). In our previous work, we demonstrated the effectiveness of hybrid compression techniques that combine machine learning with traditional approaches. This paper presents innovative computational techniques aimed at expediting the compression pipeline. Our experiments, conducted on two distinct platforms with a large-scale XGC-based fusion simulation, demonstrate that the overhead incurred by these new approaches is less than one percent of the computational resources needed for the simulation.

Banerjee, Tania↗
NASA NTRS1981

Theory and implementation of a fast algorithm linear equalizer

The theory and implementation of a multiplication-free linear mean-square error criterion equalizer for data transmission are considered. For many real-time signal processing situations, a large number of multiplications is objectionable. The linear estimation problem on a binary computer is considered where the estimation parameters are constrained to be powers of two and thus all multiplications are replaced by shifts. The optimal solution is obtained from an integer-programming-like problem except that the allowable discrete points are non-integers. The branch-and-bound algorithm is used to obtain the coefficients of the equalization TDL. Specific experimental performance results are given for an equalizer implemented with a 12 bit A/D device and a 8080 microprocessor.

Yan, T. Y.↗
NASA NTRS1984

Fast algorithms for combustion kinetics calculations: A comparison

To identify the fastest algorithm currently available for the numerical integration of chemical kinetic rate equations, several algorithms were examined. Findings to date are summarized. The algorithms examined include two general-purpose codes EPISODE and LSODE and three special-purpose (for chemical kinetic calculations) codes CHEMEQ, CRK1D, and GCKP84. In addition, an explicit Runge-Kutta-Merson differential equation solver (IMSL Routine DASCRU) is used to illustrate the problems associated with integrating chemical kinetic rate equations by a classical method. Algorithms were applied to two test problems drawn from combustion kinetics. These problems included all three combustion regimes: induction, heat release and equilibration. Variations of the temperature and species mole fraction are given with time for test problems 1 and 2, respectively. Both test problems were integrated over a time interval of 1 ms in order to obtain near-equilibration of all species and temperature. Of the codes examined in this study, only CREK1D and GCDP84 were written explicitly for integrating exothermic, non-isothermal combustion rate equations. These therefore have built-in procedures for calculating the temperature.

Radhakrishnan, K.↗