SEARCH · Engineering Papers

Results for “Algorithms”

Search indexed NASA NTRS and DOE OSTI research on propulsion, heat transfer, battery materials and energy systems. Follow report and document links to the original sources.

SourceResearch connectionFrom yearThrough year

Quote a phrase for an exact phrase match. Source license links do not imply unrestricted reuse.

At least 757 records · Page 42

All sources NASA NTRS DOE OSTI

NASA NTRS2003

Phasor algorithms of the SIM fringe estimation

The Space Interferometry Mission (SIM) will provide unprecedented micro-arcsecond (pas) precision to search for extra-solar planets and possible life in the universe. SIM will also revolutionize our understanding of the dynamics and evolutions of the local universe through hundred-fold improvements of inertial astrometry measurements. SIM has two so-called guide interferometers to provide stable inertial orientation knowledge of the baseline, and a science interferometer to measure target fringes. The guide and science measurements are based on the fringe phase measurements using a CCD detector. One of the key issues with SIM is to develop a new algorithm for calculation of fringe parameters. Not only astrometric results need that new algorithm, but also real-time fringe tracking requires a new method to calculate phase and visibility fast and accurately. The formulas for the phasor algorithms for fringe estimation are presented. The signal-noise ratio performances of the fringe quadratures are demonstrated. The advantages of phasor algorithms for application of fast fringe tracking and on-board data compression are discussed.

interferometry↗

NASA NTRS2014

Next Generation Aura-OMI SO2 Retrieval Algorithm: Introduction and Implementation Status

We introduce our next generation algorithm to retrieve SO2 using radiance measurements from the Aura Ozone Monitoring Instrument (OMI). We employ a principal component analysis technique to analyze OMI radiance spectral in 310.5-340 nm acquired over regions with no significant SO2. The resulting principal components (PCs) capture radiance variability caused by both physical processes (e.g., Rayleigh and Raman scattering, and ozone absorption) and measurement artifacts, enabling us to account for these various interferences in SO2 retrievals. By fitting these PCs along with SO2 Jacobians calculated with a radiative transfer model to OMI-measured radiance spectra, we directly estimate SO2 vertical column density in one step. As compared with the previous generation operational OMSO2 PBL (Planetary Boundary Layer) SO2 product, our new algorithm greatly reduces unphysical biases and decreases the noise by a factor of two, providing greater sensitivity to anthropogenic emissions. The new algorithm is fast, eliminates the need for instrument-specific radiance correction schemes, and can be easily adapted to other sensors. These attributes make it a promising technique for producing long-term, consistent SO2 records for air quality and climate research. We have operationally implemented this new algorithm on OMI SIPS for producing the new generation standard OMI SO2 products.

Sulfur dioxide↗

NASA NTRS2019

Chlorophyll Algorithms for Ocean Color Sensors - OC4, OC5 and OC6

A high degree of consistency and comparability among chlorophyll algorithms is necessary to meet the goals of merging data from concurrent overlapping ocean color missions for increased coverage of the global ocean and to extend existing time series to encompass data from recently launched missions and those planned for the near future, such as PACE, OLCI, HawkEye, EnMAP and SABIA-MAR. To accomplish these goals, we developed 65 empirical ocean color (OC) chlorophyll algorithms for 25 satellite instruments using the largest available and most globally representative database of coincident in situ chlorophyll a and remote sensing reflectances. Excellent internal consistency was achieved across these OC ‘Version -7’ algorithms, as demonstrated by a median regression slope and coefficient of determination (R (sup 2)) of 0.985 and 0.859, respectively, among 903 pairwise comparisons of OC-modeled chlorophyll. SeaWiFS and MODIS-Aqua satellite-to-in situ match-up results indicated equivalent, and sometimes superior, performance to current heritage chlorophyll algorithms.

ocean color↗

NASA NTRS2021

Progress in Scheduling Algorithms for a Collaborative Distributed System for Flight Planning

This Technical Memorandum describes four contributions made by the authors to a larger team effort toward developing a distributed system for scheduling commercial flights at navigation fixes and/or airport runways. These contributions are as follows: (1) a proof of correctness for a scheduling algorithm published previously by Meyn, (2) an improvement of Meyn's algorithm from quadratic to linear time, (3) two independent implementations of the algorithm with test results identical to those published, and (4) an extension of Meyn's algorithm to support minimum usable time intervals.

arrival scheduling↗

NASA NTRS2022

A Quantum Algorithm to Simulate Open Quantum Systems

Given the advent of quantum algorithms for a wide array of problems in linear algebra and machine learning, it is important to develop general methods for the simulation of arbitrary (ie non-unitary) operators on quantum hardware. In this talk, we present a novel quantum algorithm based on the quantum singular value transformation (QSVT) to apply an arbitrary operator K to some input state and subsequently estimate the expectation value of some observable. Our construction then immediately yields a route to estimating observables of states undergoing open quantum dynamics, whose effect is captured by a set of non-unitary Kraus operators. Our algorithm succeeds deterministically given the Sz-Nagy dilation, and we provide details on the algorithm's query and gate complexity, numerical verification, and comparisons with prior methods.

Quantum computing↗

NASA NTRSDate not supplied

Bias in Planning Algorithms

Does bias exist in planning algorithms? If so, how does bias manifest, and how important is this bias? Answering this question requires a formal, mathematical definition of bias. We formally define bias as the distance between the probability distributions of solutions returned by various algorithms, and the uniform distribution over solutions. We show in this paper that deterministic algorithms are inherently biased, as they don’t return all solutions, and that this property holds even when algorithms return a set of plans instead of just one plan. Exceptions are problem instances or problem classes for which only a single solution exists. We then discuss changing the definition of bias to compare the probability distributions of properties of sets of plans instead of individual plans. We show the property bias is smaller than the bias of actual plans. Finally, we show that entropy is a proxy for the more complex and more expensive distance measurement between pairs of probability distributions. We then describe a roadmap for future investigations of bias in planning.

Planning Scheduling Algorithms↗

DOE OSTI2023

Optimization Algorithm for Criticality Experiment Design Using Whisper

Many criticality experiments performed to aid in nuclear data evaluation are designed to maximize the sensitivity of the system’s effective neutron multiplication factor to a certain nuclide reaction pair over an energy region of interest. This is typically done by evaluating possible designs in a transport code such as MCNP and selecting the one with the highest desired sensitivity. A designer has many tools to try to maximize this sensitivity such as different moderators, reflectors, fuels, and geometries. This balancing act of identifying a critical and maximally sensitive system become very computationally expensive as more variables are added and higher precisions are desired. In order to identify these optimal configurations more efficiently a Particle Swarm Optimization (PSO) algorithm coupled with MCNP has been developed by Los Alamos National Laboratory (LANL). This algorithm has been used to design two upcoming criticality experiments that will be performed at the National Criticality Experiments Research Center (NCERC), located at the Nevada National Security Site, and operated by LANL, the only general-purpose critical experiments laboratory in the United States. PSO uses a population (swarm) of candidate solutions (particles) on a search space of dimensions such as moderator and reflector thicknesses or enrichments and concentrations. These particles move around the search space from generation to generation according to simple rules. Eventually, the swarm converges on the configuration that is both critical and maximally sensitive to a piece of nuclear data. PSO is well suited for criticality experiments as the algorithm is agnostic to the underlying physics, meaning it is effective on many different experimental setups. This algorithm has been modified to maximize the nuclear data similarity coefficient between an application case and an experiment aimed at replicating the application case using WHISPER, a nuclear criticality safety analysis tool. This allows for the efficient design of critical experiments informed by nuclear data sensitives.

73 NUCLEAR PHYSICS AND RADIATION PHYSICS↗

DOE OSTI2023

A Privacy Preserving Distributed Model Identification Algorithm for Power Distribution Systems: Preprint

Distributed control/optimization is a promising approach for network systems due to its advantages over centralized schemes, such as robustness, cost-effectiveness, and improved privacy. However, distributed methods can have drawbacks, such as slower convergence rates due to limited knowledge of the overall network model. Additionally, ensuring privacy in the communication of sensitive information can pose implementation challenges. To address this issue, we propose a distributed model identification algorithm that enables each agent to identify the sub-model that characterizes the relationship between its local control and the overall system outputs. The proposed algorithm maintains the privacy of local agents by only communicating through dummy variables. We demonstrate the efficacy of our algorithm in the context of power distribution systems by applying it to the voltage regulation of a modified IEEE distribution system. The proposed algorithm is well-suited to the needs of power distribution controls and offers an effective solution to the challenges of distributed model identification in network systems.

data-driven modeling↗

DOE OSTI2021

Mixed precision s –step Lanczos and conjugate gradient algorithms

Compared to the classical Lanczos algorithm, the s-step Lanczos variant has the potential to improve performance by asymptotically decreasing the synchronization cost per iteration. However, this comes at a price; despite being mathematically equivalent, the s-step variant may behave quite differently in finite precision, potentially exhibiting greater loss of accuracy and slower convergence relative to the classical algorithm. It has previously been shown that the errors in the s-step version follow the same structure as the errors in the classical algorithm, but are amplified by a factor depending on the square of the condition number of the O(s)-dimensional Krylov bases computed in each outer loop. As the condition number of these s-step bases grows (in some cases very quickly) with s, this limits the s values that can be chosen and thus can limit the attainable performance. In this work, we show that if a select few computations in s-step Lanczos are performed in double the working precision, the error terms then depend only linearly on the conditioning of the s-step bases. This has the potential for drastically improving the numerical behavior of the algorithm with little impact on per-iteration performance. Our numerical experiments demonstrate the improved numerical behavior possible with the mixed precision approach, and also show that this improved behavior extends to mixed precision s-step CG. Here, we present preliminary performance results on NVIDIA V100 GPUs that show that the overhead of extra precision is minimal if one uses precisions implemented in hardware.

97 MATHEMATICS AND COMPUTING↗

DOE OSTI2025

Randomized Algorithms for Low-Rank Matrix and Tensor Decompositions

This paper surveys randomized algorithms in numerical linear algebra for low-rank decompositions of matrices and tensors. The survey begins with a review of classical matrix algorithms that can be accelerated by randomized dimensionality reduction, such as the singular value decomposition (SVD) or interpolative (ID) and CUR decompositions. Recent advances in randomized dimensionality reduction are discussed, including new methods of fast matrix sketching and sampling techniques, which are incorporated into classical matrix algorithms for fast low-rank matrix approximations. The extension of randomized matrix algorithms to tensors is then explored for several low-rank tensor decompositions in the CP and Tucker formats, including the higher-order SVD, ID, and CUR decomposition.

Pearce, Katherine J. [The University of Texas at A↗

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 OSTI2020

High precision control and deep learning-based corn stand counting algorithms for agricultural robot

This paper presents high precision control and deep learning-based corn stand counting algorithms for a low-cost, ultra-compact 3D printed and autonomous field robot for agricultural operations. Currently, plant traits, such as emergence rate, biomass, vigor, and stand counting, are measured manually. This is highly labor-intensive and prone to errors. The robot, termed TerraSentia, is designed to automate the measurement of plant traits for efficient phenotyping as an alternative to manual measurements. In this paper, we formulate a Nonlinear Moving Horizon Estimator that identifies key terrain parameters using onboard robot sensors and a learning-based Nonlinear Model Predictive Control that ensures high precision path tracking in the presence of unknown wheel-terrain interaction. Moreover, we develop a machine vision algorithm designed to enable an ultra-compact ground robot to count corn stands by driving through the fields autonomously. The algorithm leverages a deep network to detect corn plants in images, and a visual tracking model to re-identify detected objects at different time steps. We collected data from 53 corn plots in various fields for corn plants around 14 days after emergence (stage V3 - V4). The robot predictions have agreed well with the ground truth with C robot =1.02×C human -0.86 and a correlation coefficient R=0.96. The mean relative error given by the algorithm is -3.78%, and the standard deviation is 6.76%. These results indicate a first and significant step towards autonomous robot-based real-time phenotyping using low-cost, ultra-compact ground robots for corn and potentially other crops.

97 MATHEMATICS AND COMPUTING↗

DOE OSTI2025

Graph decomposition techniques for solving combinatorial optimization problems with variational quantum algorithms

The quantum approximate optimization algorithm (QAOA) has the potential to approximately solve complex combinatorial optimization problems in polynomial time. However, current noisy quantum devices cannot solve large problems due to hardware constraints. In this work, we develop an algorithm that decomposes the QAOA input problem graph into a smaller problem and solves MaxCut using QAOA on the reduced graph. The algorithm requires a subroutine that can be classical or quantum—in this work, we implement the algorithm twice on each graph. One implementation uses the classical solver Gurobi in the subroutine and the other uses QAOA. We solve these reduced problems with QAOA. On average, the reduced problems require only approximately 1/10 of the number of vertices than the original MaxCut instances. Furthermore, the average approximation ratio of the original MaxCut problems is 0.75, while the approximation ratios of the decomposed graphs are on average of 0.96 for both Gurobi and QAOA. With this decomposition, we are able to measure optimal solutions for ten 100-vertex graphs by running single-layer QAOA circuits on the Quantinuum trapped-ion quantum computer H1-1, sampling each circuit only 500 times. This approach is best suited for sparse, particularly k-regular graphs, as k-regular graphs on n vertices can be decomposed into a graph with at most $\frac{nk}{k+1}$ vertices in polynomial time. Further reductions can be obtained with a potential trade-off in computational time. In conclusion, while this paper applies the decomposition method to the MaxCut problem, it can be applied to more general classes of combinatorial optimization problems.

97 MATHEMATICS AND COMPUTING↗

DOE OSTI2020

A smooth contact algorithm for the combined finite discrete element method

From its inception, the combined finite discrete element method has used a distributed potential contact force algorithm to resolve interaction between finite elements. The contact interaction algorithm relies on evaluation of the contact force potential field. The problem with existing algorithms is that the potential field introduces artificial numerical non-smoothness in the contact force. This work introduces a smooth potential field based on the finite element topology, and a generalized contact interaction law is constructed on top of the smooth potential field. Further, a number of validation cases for the proposed algorithm, considering different shapes of discrete elements, are presented, and detailed aspects of the proposed contact interaction law are tested with numerical examples.

97 MATHEMATICS AND COMPUTING↗

DOE OSTI2021

A Range and Performance Optimized Version of the Computer-Aided Speckle Interferometry Algorithm for Real-Time Displacement-Strain Field Monitoring

Abstract This work presents an optimized implementation of the Computer-Aided Speckle Interferometry algorithm which enables full-field determination of displacements and strains on commodity Graphics Processing Units at high resolution and frame rates. By combining careful control of the average speckle size in a laser speckle pattern with a simple sampling rate conversion scheme, a compact representation of the optical speckle is achieved. This allows for optimal use of Graphics Processing Unit architecture with robust range extension. The optimal mapping of the Computer-Aided Speckle Interferometry algorithm to Graphics Processing Unit architecture is shown in detail, and a straightforward method for disambiguating large displacements is illustrated. Lastly, this paper demonstrates a two-step subimage-tapering modification to the original algorithm that enables robust range enhancement while maintaining resolution. Results from numerical simulations on synthetic speckle patterns are shown, and runtime performance metrics are provided, with performance ranging up to 60 frames per second in some cases. The method is suitable for interactive experimental mechanics research, process and testing or any application where real-time high-resolution displacement-strain monitoring is needed. A .NET Framework class library enabling the incorporation of the algorithm into 3rd -party applications is available for download.

42 ENGINEERING↗

DOE OSTI2024

Optimization-based, property-preserving algorithm for passive tracer transport

Here we present a new optimization-based property-preserving algorithm for passive tracer transport. The algorithm utilizes a semi-Lagrangian approach based on incremental remapping of the mass and the total tracer. However, unlike traditional semi-Lagrangian schemes, which remap the density and the tracer mixing ratio through monotone reconstruction or flux correction, we utilize an optimization-based remapping that enforces conservation and local bounds as optimization constraints. In so doing we separate accuracy considerations from preservation of physical properties to obtain a conservative, second-order accurate transport scheme that also has a notion of optimality. Moreover, we prove that the optimization-based algorithm preserves linear relationships between tracer mixing ratios. We illustrate the properties of the new algorithm using a series of standard tracer transport test problems in a plane and on a sphere.

97 MATHEMATICS AND COMPUTING↗

DOE OSTI2025

The latent variable proximal point algorithm for variational problems with inequality constraints

The latent variable proximal point (LVPP) algorithm is a framework for solving infinite-dimensional variational problems with pointwise inequality constraints. The algorithm is a saddle point reformulation of the Bregman proximal point algorithm. At the continuous level, the two formulations are equivalent, but the saddle point formulation is more amenable to discretization because it introduces a structure-preserving transformation between a latent function space and the feasible set. Working in this latent space is much more convenient for enforcing inequality constraints than the feasible set, as discretizations can employ general linear combinations of suitable basis functions, and nonlinear solvers can involve general additive updates. LVPP yields numerical methods with observed mesh-independence for obstacle problems, contact, fracture, plasticity, and others besides; in many cases, for the first time. The framework also extends to more complex constraints, providing means to enforce convexity in the Monge–Ampère equation and handling quasi-variational inequalities, where the underlying constraint depends implicitly on the unknown solution. Here, in this paper, we describe the LVPP algorithm in a general form and apply it to ten problems from across mathematics.

Inequality constraints↗

DOE OSTI2022

An algorithm for physics informed scan path optimization in additive manufacturing

Site specific microstructure control is a critical research area within the field of additive manufacturing due to its potential to revolutionize part performance. One way to achieve site specific microstructure control is through control of the solidification conditions via the construction of intricate scan paths; however, the search space for such a problem is large. Previous attempts only considered the solidification conditions at the top surface while also requiring either lots of manual-fine tuning or large amounts of computational resources. This paper introduces a general method for scan path optimization which considers the solidification conditions in the bulk of the material without an increase in computational expense. This method consists of three core components:1. A heat transfer model for simulating the temperature field at a given time.2. A surrogate model which takes scan pattern information and temperature data and predicts the solidification conditions of the bulk as well as the meltpool depths for a spot melt.3. A decision algorithm to decide which spot melt should be printed next based on the outputs of the surrogate model.Each of these components can be changed without changing the overall method. Within this work, this method is applied in the creation of an algorithm containing a semi-analytic heat transfer model to simulate the temperature field, a fully convolutional neural network (FCNN) as the surrogate model, and a greedy decision algorithm. The resulting algorithm produced complex scan patterns which gave strong results for simulated microstructure control.

36 MATERIALS SCIENCE↗