Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “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 37 records · Page 2
All sourcesNASA NTRSDOE OSTI
NASA NTRS2005

Motion Cueing Algorithm Development: Piloted Performance Testing of the Cueing Algorithms

The relative effectiveness in simulating aircraft maneuvers with both current and newly developed motion cueing algorithms was assessed with an eleven-subject piloted performance evaluation conducted on the NASA Langley Visual Motion Simulator (VMS). In addition to the current NASA adaptive algorithm, two new cueing algorithms were evaluated: the optimal algorithm and the nonlinear algorithm. The test maneuvers included a straight-in approach with a rotating wind vector, an offset approach with severe turbulence and an on/off lateral gust that occurs as the aircraft approaches the runway threshold, and a takeoff both with and without engine failure after liftoff. The maneuvers were executed with each cueing algorithm with added visual display delay conditions ranging from zero to 200 msec. Two methods, the quasi-objective NASA Task Load Index (TLX), and power spectral density analysis of pilot control, were used to assess pilot workload. Piloted performance parameters for the approach maneuvers, the vertical velocity upon touchdown and the runway touchdown position, were also analyzed but did not show any noticeable difference among the cueing algorithms. TLX analysis reveals, in most cases, less workload and variation among pilots with the nonlinear algorithm. Control input analysis shows pilot-induced oscillations on a straight-in approach were less prevalent compared to the optimal algorithm. The augmented turbulence cues increased workload on an offset approach that the pilots deemed more realistic compared to the NASA adaptive algorithm. The takeoff with engine failure showed the least roll activity for the nonlinear algorithm, with the least rudder pedal activity for the optimal algorithm.

Houck, Jacob A.↗
DOE OSTI2021

Randomized Algorithms for Scientific Computing (RASC)

Randomized algorithms have propelled advances in artificial intelligence (AI) and represent a foundational research area in advancing AI for Science. Future advancements in DOE Office of Science priority areas such as climate science, astrophysics, fusion, advanced materials, combustion, and quantum computing all require randomized algorithms for surmounting challenges of complexity, robustness, and scalability. Advances in data collection and numerical simulation have changed the dynamics of scientific research and motivate the need for randomized algorithms. For instance, advances in imaging technologies such as X-ray ptychography, electron microscopy, electron energy loss spectroscopy, or adaptive optics lattice light-sheet microscopy collect hyperspectral imaging and scattering data in terabytes, at breakneck speed enabled by state-of-the-art detectors. The data collection is exceptionally fast compared with its analysis. Likewise, advances in high-performance architectures have made exascale computing a reality and changed the economies of scientific computing in the process. Floating-point operations that create data are essentially free in comparison with data movement. Thus far, most approaches have focused on creating faster hardware. Ironically, this faster hardware has exacerbated the problem by making data still easier to create. Under such an onslaught, scientists often resort to heuristic deterministic sampling schemes (e.g., low-precision arithmetic, sampling every nth element) and sacrifice potentially valuable accuracy. Dramatically better results can be achieved via randomized algorithms, reducing the data size as much as or more than naive deterministic subsampling can achieve, while retaining the high accuracy of computing on the full data set. By randomized algorithms we mean those algorithms that employ some form of randomness in internal algorithmic decisions to accelerate time to solution, increase scalability, or improve reliability. Examples include matrix sketching for solving large-scale least-squares problems (see Figure 1) and stochastic gradient descent for training machine learning models. We are not recommending heuristic methods but rather randomized algorithms that have certificates of correctness and probabilistic guarantees of optimality and near-optimality. Such approaches can be useful beyond acceleration, for example, in understanding how to avoid measure zero worst-case scenarios that plague methods such as QR matrix factorization.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2014

An efficient polyenergetic SART (pSART) reconstruction algorithm for quantitative myocardial CT perfusion

Purpose: In quantitative myocardial CT perfusion imaging, beam hardening effect due to dense bone and high concentration iodinated contrast agent can result in visible artifacts and inaccurate CT numbers. In this paper, an efficient polyenergetic Simultaneous Algebraic Reconstruction Technique (pSART) was presented to eliminate the beam hardening artifacts and to improve the CT quantitative imaging ability. Methods: Our algorithm made threea priori assumptions: (1) the human body is composed of several base materials (e.g., fat, breast, soft tissue, bone, and iodine); (2) images can be coarsely segmented to two types of regions, i.e., nonbone regions and noniodine regions; and (3) each voxel can be decomposed into a mixture of two most suitable base materials according to its attenuation value and its corresponding region type information. Based on the above assumptions, energy-independent accumulated effective lengths of all base materials can be fast computed in the forward ray-tracing process and be used repeatedly to obtain accurate polyenergetic projections, with which a SART-based equation can correctly update each voxel in the backward projecting process to iteratively reconstruct artifact-free images. This approach effectively reduces the influence of polyenergetic x-ray sources and it further enables monoenergetic images to be reconstructed at any arbitrarily preselected target energies. A series of simulation tests were performed on a size-variable cylindrical phantom and a realistic anthropomorphic thorax phantom. In addition, a phantom experiment was also performed on a clinical CT scanner to further quantitatively validate the proposed algorithm. Results: The simulations with the cylindrical phantom and the anthropomorphic thorax phantom showed that the proposed algorithm completely eliminated beam hardening artifacts and enabled quantitative imaging across different materials, phantom sizes, and spectra, as the absolute relative errors were reduced from [−7.5%, 12.1%] for SART to [−0.1%, 0.1%] for pSART. When using low kVp spectra and high reference energies, pSART also showed improved reconstruction efficiency in terms of convergence speed compared to the conventional SART algorithm. The phantom experiment on a clinical CT scanner indicated that the quantitative advantage of pSART is realizable in experimental CT acquisition, as the absolute relative errors across material inserts were less than 0.4%. Conclusions: By incorporatinga priori information (material attenuation coefficients, x-ray source spectrum, and region type information) into the reconstruction process, the proposed pSART algorithm could effectively eliminate beam hardening artifacts, reconstruct the accurate attenuation coefficients for precise quantitative imaging, and accelerate the reconstruction process.

62 RADIOLOGY AND NUCLEAR MEDICINE↗
DOE OSTI2022

Precise ROCOF estimation algorithm for low inertia power grids

The precise estimation of Rate Of Change Of Frequencies (ROCOFs) in a generation trip event can be helpful on power system inertia estimation, fast system response, and accurate event capturing. However, the ROCOF estimations from the existing Synchronized Measurement Devices (SMDs) are usually simply calculated by the finite difference between two adjacent frequency measurement points. The ineluctable noises, disturbances, and spikes from real-world frequency measurements can bring large dynamics to the ROCOF estimation and thus can result in an inaccurate estimation of the initial ROCOF. This issue becomes more serious when the target power grid has low inertia, and a large amount of distributed energy sources are deployed. To address this issue, a precise ROCOF estimation algorithm is designed based on least square method with flexible window size. In addition, a median filter is also designed and applied on the frequency measurements before using the proposed algorithm. The window size and thresholds in the proposed algorithm are determined with historical event data analysis. The proposed algorithm is deployed in a low cost, flexible, and distribution level universal grid analyzer (UGA) platform. In conclusion, multiple experiments are conducted in both a laboratory and the Hawaiian Islands to verify the effectiveness of the proposed algorithm.

24 POWER TRANSMISSION AND DISTRIBUTION↗
DOE OSTI2022

A weighted state redistribution algorithm for embedded boundary grids

State redistribution is an algorithm that stabilizes cut cells for embedded boundary grid methods. This work extends the earlier algorithm in several important ways. First, state redistribution is extended to three spatial dimensions. Second, we discuss several algorithmic changes and improvements motivated by the more complicated cut cell geometries that can occur in higher dimensions. In particular, we introduce a weighted version with less dissipation in an easily generalizable framework. Third, we demonstrate that state redistribution can also stabilize a solution update that includes both advective and diffusive contributions. Notably, the stabilization algorithm is shown to be effective for incompressible as well as compressible reacting flows. Finally, we discuss the implementation of the algorithm for several exascale-ready simulation codes based on AMReX, demonstrating ease of use in combination with domain decomposition, hybrid parallelism and complex physics.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2015

Efficient Algorithms for Estimating the Absorption Spectrum within Linear Response TDDFT

We present a special symmetric Lanczos algorithm and a kernel polynomial method (KPM) for approximating the absorption spectrum of molecules within the linear response time-dependent density functional theory (TDDFT) framework in the product form. In contrast to existing algorithms, the new algorithms are based on reformulating the original non-Hermitian eigenvalue problem as a product eigenvalue problem and the observation that the product eigenvalue problem is self-adjoint with respect to an appropriately chosen inner product. This allows a simple symmetric Lanczos algorithm to be used to compute the desired absorption spectrum. The use of a symmetric Lanczos algorithm only requires half of the memory compared with the nonsymmetric variant of the Lanczos algorithm. The symmetric Lanczos algorithm is also numerically more stable than the nonsymmetric version. The KPM algorithm is also presented as a low-memory alternative to the Lanczos approach, but the algorithm may require more matrix-vector multiplications in practice. We discuss the pros and cons of these methods in terms of their accuracy as well as their computational and storage cost. Applications to a set of small and medium-sized molecules are also presented.

37 INORGANIC, ORGANIC, PHYSICAL, AND ANALYTICAL CH↗
DOE OSTI2018

Polar Liquid Cloud Base Detection Algorithms for High Spectral Resolution or Micropulse Lidar Data

Liquid layers in clouds affect their microphysical processes, as well as the atmospheric energy budget. However, explicit liquid cloud base height (LCBH) detection algorithms using ground-based instruments (e.g., lidars) are currently absent in the literature. Most studies use either fixed lidar parameter thresholds or cloud base height data products that do not distinguish between ice and liquid, all of which might introduce inconsistencies and errors in the resolved LCBHs. In this paper, two LCBH detection algorithms are presented; the first algorithm uses the high spectral resolution lidar (HSRL) data, and yields satisfactory results. The second algorithm incorporates micropulse lidar (MPL) data for the LCBH detection. A 1-year long comparison of data gathered at Barrow, Alaska, and McMurdo Station, Antarctica, which includes other cloud base detection methodologies (ceilometer, MPL value-added product cloud base height, LCBHs detected using a fixed MPL depolarization threshold) emphasize the merits of the MPL algorithm.

Silber, Israel↗
DOE OSTI2019

A Structured Quasi-Newton Algorithm for Optimizing with Incomplete Hessian Information

We present a structured quasi-Newton algorithm for unconstrained optimization problems that have unavailable second-order derivatives or Hessian terms. We provide a formal derivation of the well-known Broyden--Fletcher--Goldfarb--Shanno (BFGS) secant update formula that approximates only the missing Hessian terms, and we propose a linesearch quasi-Newton algorithm based on a modification of Wolfe conditions that converges to first-order optimality conditions. We also analyze the local convergence properties of the structured BFGS algorithm and show that it achieves superlinear convergence under the standard assumptions used by quasi-Newton methods using secant updates. In conclusion, we provide a thorough study of the practical performance of the algorithm on the CUTEr suite of test problems and show that our structured BFGS-based quasi-Newton algorithm outperforms the unstructured counterpart(s).

97 MATHEMATICS AND COMPUTING↗
NASA NTRS1992

Interface of an uncoupled boundary layer algorithm with an inviscid core flow algorithm for unsteady supersonic engine inlets

An uncoupled boundary layer algorithm was combined with an inviscid core flow algorithm to model flows within supersonic engine inlets. The inviscid flow algorithm that was used was the LArge Perturbation INlet Code (LAPIN). The boundary layer and inviscid core flow algorithms were formulated in different manners. The boundary layer algorithm was two dimensional and solved in nonconservation form, while the core flow algorithm was one dimensional and solved in conservation form. In order to interface the two codes, the following modifications were important. The coordinate system was set up to maintain the parabolic nature of the boundary layer algorithm while approaching the one dimensional core flow solution far from a wall. The pressure gradient used in the boundary layer equation was calculated using the core flow values and the boundary layer equations, so the boundary layer solution smoothly approached the core flow values far from the wall. Flaring was used for the advection terms perpendicular to the core flow to maintain the stability of the algorithm. With these modifications, the combined viscous/inviscid algorithm matched well with experimental observations of pressure distributions with a supersonic inlet.

Darling, Douglas↗
NASA NTRS1992

Interface of an uncoupled boundary layer algorithm with an inviscid core flow algorithm for unsteady supersonic engine inlets

An uncoupled boundary layer algorithm was combined with an inviscid core flow algorithm to model flows within supersonic engine inlets. The inviscid flow algorithm that was used was the LArge Perturbation INlet Code (LAPIN). The boundary layer and inviscid core flow algorithms were formulated in different manners. The boundary layer algorithm was two dimensional and solved in nonconservation form, while the core flow algorithm was one dimensional and solved in conservation form. In order to interface the two codes, the following modifications were important. The coordinate system was set up to maintain the parabolic nature of the boundary layer algorithm while approaching the one dimensional core flow solution far from a wall. The pressure gradient used in the boundary layer equation was calculated using the core flow values and the boundary layer equations, so the boundary layer solution smoothly approached the core flow values far from the wall. Flaring was used for the advection terms perpendicular to the core flow to maintain the stability of the algorithm. With these modifications, the combined viscous/inviscid algorithm matched well experimental observations of pressure distributions with a supersonic inlet.

Darling, Douglas↗
DOE OSTI2021

Data-Driven Distributed Algorithms for Estimating Eigenvalues and Eigenvectors of Interconnected Dynamical Systems

Here, the paper presents data-driven algorithms to estimate in a distributed manner the eigenvalues, right and left eigenvectors of an unknown linear (or linearized) interconnected dynamic system. In particular, the proposed algorithms do not require the identification of the system model in advance before performing the estimation. As a first step, we consider interconnected dynamical system with distinct eigenvalues. The proposed strategy first estimates the eigenvalues using the well-known Prony method. The right and left eigenvectors are then estimated by solving distributively a set of linear equations. One important feature of the proposed algorithms is that the topology of communication network used to perform the distributed estimation can be chosen arbitrarily, given that it is connected, and is also independent of the structure or sparsity of the system (state) matrix. The proposed distributed algorithms are demonstrated via a numerical example.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2022

Entanglement perspective on the quantum approximate optimization algorithm

Many quantum algorithms seek to output a specific bitstring solving the problem of interest—or a few if the solution is degenerate. It is the case for the quantum approximate optimization algorithm (QAOA) in the limit of large circuit depth, which aims to solve quadratic unconstrained binary optimization problems. Hence, the expected final state for these algorithms is either a product state or a low-entangled superposition involving a few bitstrings. What happens in between the initial N -qubit product state | 0 〉 ⊗ N and the final one regarding entanglement? Here, we consider the QAOA algorithm for solving the paradigmatic MaxCut problem on different types of graphs. We study the entanglement growth and spread resulting from randomized and optimized QAOA circuits and find that there is a volume-law entanglement barrier between the initial and final states. We also investigate the entanglement spectrum in connection with random matrix theory. In addition, we compare the entanglement production with a quantum annealing protocol aiming to solve the same MaxCut problems. Finally, we discuss the implications of our results for the simulation of QAOA circuits with tensor network-based methods relying on low-entanglement for efficiency, such as matrix product states.

Dupont, Maxime↗
DOE OSTI2017

Automatic Regionalization Algorithm for Distributed State Estimation in Power Systems

The deregulation of the power system and the incorporation of generation from renewable energy sources recessitates faster state estimation in the smart grid. Distributed state estimation (DSE) has become a promising and scalable solution to this urgent demand. In this paper, we investigate the regionalization algorithms for the power system, a necessary step before distributed state estimation can be performed. To the best of the authors' knowledge, this is the first investigation on automatic regionalization (AR). We propose three spectral clustering based AR algorithms. Simulations show that our proposed algorithms outperform the two investigated manual regionalization cases. With the help of AR algorithms, we also show how the number of regions impacts the accuracy and convergence speed of the DSE and conclude that the number of regions needs to be chosen carefully to improve the convergence speed of DSEs.

24 POWER TRANSMISSION AND DISTRIBUTION↗
DOE OSTI2017

Extreme-Scale Algorithms & Software Resilience (EASIR) Architecture-Aware Algorithms for Scalable Performance and Resilience on Heterogeneous Architectures

This project addresses both communication-avoiding algorithms, and reproducible floating-point computation. Communication, i.e. moving data, either between levels of memory or processors over a network, is much more expensive per operation than arithmetic (measured in time or energy), so we seek algorithms that greatly reduce communication. We developed many new algorithms for both dense and sparse, and both direct and iterative linear algebra, attaining new communication lower bounds, and getting large speedups in many cases. We also extended this work in several ways: (1) We minimize writes separately from reads, since writes may be much more expensive than reads on emerging memory technologies, like Flash, sometimes doing asymptotically fewer writes than reads. (2) We extend the lower bounds and optimal algorithms to arbitrary algorithms that may be expressed as perfectly nested loops accessing arrays, where the array subscripts may be arbitrary affine functions of the loop indices (eg A(i), B(i,j+k, k+3*m-7, …) etc.). (3) We extend our communication-avoiding approach to some machine learning algorithms, such as support vector machines. This work has won a number of awards. We also address reproducible floating-point computation. We define reproducibility to mean getting bitwise identical results from multiple runs of the same program, perhaps with different hardware resources or other changes that should ideally not change the answer. Many users depend on reproducibility for debugging or correctness. However, dynamic scheduling of parallel computing resources, combined with nonassociativity of floating point addition, makes attaining reproducibility a challenge even for simple operations like summing a vector of numbers, or more complicated operations like the Basic Linear Algebra Subprograms (BLAS). We describe an algorithm that computes a reproducible sum of floating point numbers, independent of the order of summation. The algorithm depends only on a subset of the IEEE Floating Point Standard 754-2008, uses just 6 words to represent a “reproducible accumulator,” and requires just one read-only pass over the data, or one reduction in parallel. New instructions based on this work are being considered for inclusion in the future IEEE 754-2018 floating-point standard, and new reproducible BLAS are being considered for the next version of the BLAS standard.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2016

Aerosol Plume Detection Algorithm Based on Image Segmentation of Scanning Atmospheric Lidar Data

An image-processing algorithm has been developed to identify aerosol plumes in scanning lidar backscatter data. The images in this case consist of lidar data in a polar coordinate system. Each full lidar scan is taken as a fixed image in time, and sequences of such scans are considered functions of time. The data are analyzed in both the original backscatter polar coordinate system and a lagged coordinate system. The lagged coordinate system is a scatterplot of two datasets, such as subregions taken from the same lidar scan (spatial delay), or two sequential scans in time (time delay). The lagged coordinate system processing allows for finding and classifying clusters of data. The classification step is important in determining which clusters are valid aerosol plumes and which are from artifacts such as noise, hard targets, or background fields. These cluster classification techniques have skill since both local and global properties are used. Furthermore, more information is available since both the original data and the lag data are used. Performance statistics are presented for a limited set of data processed by the algorithm, where results from the algorithm were compared to subjective truth data identified by a human.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2016

PolyPole-1: An accurate numerical algorithm for intra-granular fission gas release

This paper describes the development of a new numerical algorithm (called PolyPole-1) to efficiently solve the equation for intra-granular fission gas release in nuclear fuel. The work was carried out in collaboration with Politecnico di Milano and Institute for Transuranium Elements. The PolyPole-1 algorithms is being implemented in INL's fuels code BISON code as part of BISON's fission gas release model. The transport of fission gas from within the fuel grains to the grain boundaries (intra-granular fission gas release) is a fundamental controlling mechanism of fission gas release and gaseous swelling in nuclear fuel. Hence, accurate numerical solution of the corresponding mathematical problem needs to be included in fission gas behaviour models used in fuel performance codes. Under the assumption of equilibrium between trapping and resolution, the process can be described mathematically by a single diffusion equation for the gas atom concentration in a grain. In this work, we propose a new numerical algorithm (PolyPole-1) to efficiently solve the fission gas diffusion equation in time-varying conditions. The PolyPole-1 algorithm is based on the analytic modal solution of the diffusion equation for constant conditions, with the addition of polynomial corrective terms that embody the information on the deviation from constant conditions. The new algorithm is verified by comparing the results to a finite difference solution over a large number of randomly generated operation histories. Furthermore, comparison to state-of-the-art algorithms used in fuel performance codes demonstrates that the accuracy of the PolyPole-1 solution is superior to other algorithms, with similar computational effort. Finally, the concept of PolyPole-1 may be extended to the solution of the general problem of intra-granular fission gas diffusion during non-equilibrium trapping and resolution, which will be the subject of future work.

11 NUCLEAR FUEL CYCLE AND FUEL MATERIALS↗
NASA NTRS2010

Algorithm That Synthesizes Other Algorithms for Hashing

An algorithm that includes a collection of several subalgorithms has been devised as a means of synthesizing still other algorithms (which could include computer code) that utilize hashing to determine whether an element (typically, a number or other datum) is a member of a set (typically, a list of numbers). Each subalgorithm synthesizes an algorithm (e.g., a block of code) that maps a static set of key hashes to a somewhat linear monotonically increasing sequence of integers. The goal in formulating this mapping is to cause the length of the sequence thus generated to be as close as practicable to the original length of the set and thus to minimize gaps between the elements. The advantage of the approach embodied in this algorithm is that it completely avoids the traditional approach of hash-key look-ups that involve either secondary hash generation and look-up or further searching of a hash table for a desired key in the event of collisions. This algorithm guarantees that it will never be necessary to perform a search or to generate a secondary key in order to determine whether an element is a member of a set. This algorithm further guarantees that any algorithm that it synthesizes can be executed in constant time. To enforce these guarantees, the subalgorithms are formulated to employ a set of techniques, each of which works very effectively covering a certain class of hash-key values. These subalgorithms are of two types, summarized as follows: Given a list of numbers, try to find one or more solutions in which, if each number is shifted to the right by a constant number of bits and then masked with a rotating mask that isolates a set of bits, a unique number is thereby generated. In a variant of the foregoing procedure, omit the masking. Try various combinations of shifting, masking, and/or offsets until the solutions are found. From the set of solutions, select the one that provides the greatest compression for the representation and is executable in the minimum amount of time. Given a list of numbers, try to find one or more solutions in which, if each number is compressed by use of the modulo function by some value, then a unique value is generated.

James, Mark↗
DOE OSTI2015

An adaptive importance sampling algorithm for Bayesian inversion with multimodal distributions

Parametric uncertainties are encountered in the simulations of many physical systems, and may be reduced by an inverse modeling procedure that calibrates the simulation results to observations on the real system being simulated. Following Bayes' rule, a general approach for inverse modeling problems is to sample from the posterior distribution of the uncertain model parameters given the observations. However, the large number of repetitive forward simulations required in the sampling process could pose a prohibitive computational burden. This difficulty is particularly challenging when the posterior is multimodal. We present in this paper an adaptive importance sampling algorithm to tackle these challenges. Two essential ingredients of the algorithm are: 1) a Gaussian mixture (GM) model adaptively constructed as the proposal distribution to approximate the possibly multimodal target posterior, and 2) a mixture of polynomial chaos (PC) expansions, built according to the GM proposal, as a surrogate model to alleviate the computational burden caused by computational-demanding forward model evaluations. In three illustrative examples, the proposed adaptive importance sampling algorithm demonstrates its capabilities of automatically finding a GM proposal with an appropriate number of modes for the specific problem under study, and obtaining a sample accurately and efficiently representing the posterior with limited number of forward simulations.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗