Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “approximation 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 127 records · Page 7

A continuous analogue of the tensor-train decomposition

We develop new approximation algorithms and data structures for representing and computing with multivariate functions using the functional tensor-train (FT), a continuous extension of the tensor-train (TT) decomposition. The FT represents functions using a tensor-train ansatz by replacing the three-dimensional TT cores with univariate matrix-valued functions. The main contribution of this paper is a framework to compute the FT that employs adaptive approximations of univariate fibers, and that is not connected to any tensorized discretization. The algorithm can be coupled with any univariate linear or nonlinear approximation procedure. We demonstrate that this approach can generate multivariate function approximations that are several orders of magnitude more accurate, for the same cost, than those based on the conventional approach of compressing the coefficient tensor of a tensor-product basis. Our approach is in the spirit of other continuous computation packages such as Chebfun, and yields an algorithm which requires the computation of “continuous” matrix factorizations such as the LU and QR decompositions of vector-valued functions. To support these developments, we describe continuous versions of an approximate maximum-volume cross approximation algorithm and of a rounding algorithm that re-approximates an FT by one of lower ranks. We demonstrate that our technique improves accuracy and robustness, compared to TT and quantics-TT approaches with fixed parameterizations, of high-dimensional integration, differentiation, and approximation of functions with local features such as discontinuities and other nonlinearities.

42 ENGINEERING↗

A fast, space-efficient average-case algorithm for the 'Greedy' Triangulation of a point set, and a proof that the Greedy Triangulation is not approximately optimal

The paper addresses the problem of how to find the Greedy Triangulation (GT) efficiently in the average case. It is noted that the problem is open whether there exists an efficient approximation algorithm to the Optimum Triangulation. It is first shown how in the worst case, the GT may be obtained in time O(n to the 3) and space O(n). Attention is then given to how the algorithm may be slightly modified to produce a time O(n to the 2), space O(n) solution in the average case. Finally, it is mentioned that Gilbert has found a worst case solution using totally different techniques that require space O(n to the 2) and time O(n to the 2 log n).

Manacher, G. K.↗

Simulation-based optimal Bayesian experimental design for nonlinear systems

The optimal selection of experimental conditions is essential to maximizing the value of data for inference and prediction, particularly in situations where experiments are time-consuming and expensive to conduct. We propose a general mathematical framework and an algorithmic approach for optimal experimental design with nonlinear simulation-based models; in particular, we focus on finding sets of experiments that provide the most information about targeted sets of parameters. Our framework employs a Bayesian statistical setting, which provides a foundation for inference from noisy, indirect, and incomplete data, and a natural mechanism for incorporating heterogeneous sources of information. An objective function is constructed from information theoretic measures, reflecting expected information gain from proposed combinations of experiments. Polynomial chaos approximations and a two-stage Monte Carlo sampling method are used to evaluate the expected information gain. Stochastic approximation algorithms are then used to make optimization feasible in computationally intensive and high-dimensional settings. These algorithms are demonstrated on model problems and on nonlinear parameter inference problems arising in detailed combustion kinetics.

97 MATHEMATICS AND COMPUTING↗

Stochastic Programming Approach for Resource Selection under Demand Uncertainty

Cost-efficient selection and scheduling of a subset of geographically distributed resources to meet the demands of a scientific workflow is a challenging problem. The problem is exacerbated by uncertainties in demand and availability of resources. In this paper, we present a stochastic optimization based framework for robust decision making in the selection of distributed resources over a planning horizon under demand uncertainty. We present a novel two-stage stochastic programming model for resource selection, and implement an L-shaped decomposition algorithm to solve this model. A Sample Average Approximation algorithm is integrated to enable stochastic optimization to solve problems with a large number of scenarios. Using the metric of stochastic solution, we demonstrate up to 30% cost reduction relative to solutions without explicit consideration of demand uncertainty for a 24-month problem. We also demonstrate up to 54% cost reduction relative to a previously developed solution for a 36-month problem. We further argue that the composition of resources selected is superior to solutions computed without explicit consideration of uncertainties. Given the importance of resource selection and scheduling of complex scientific workflows, especially in the context of commercial cloud computing, we believe that our novel stochastic programming framework will benefit many researchers as well as users of distributed computing resources.

scientific workflows, task scheduling, optimizatio↗

LOGAN: High-Performance GPU-Based X-Drop Long-Read Alignment

Pairwise sequence alignment is one of the most computationally intensive kernels in genomic data analysis, accounting for more than 90% of the runtime for key bioinformatics applications. This method is particularly expensive for third-generation sequences due to the high computational cost of analyzing sequences of length between 1Kb and 1Mb. Given the quadratic overhead of exact pairwise algorithms for long alignments, the community primarily relies on approximate algorithms that search only for high-quality alignments and stop early when one is not found. In this work, we present the first GPU optimization of the popular X-drop alignment algorithm, that we named LOGAN. Results show that our high-performance multi-GPU implementation achieves up to 181.6 GCUPS and speed-ups up to 6.6× and 30.7× using 1 and 6 NVIDIA Tesla V100, respectively, over the state-of-the-art software running on two IBM Power9 processors using 168 CPU threads, with equivalent accuracy. We also demonstrate a 2.3× LOGAN speed-up versus ksw2, a state-of-art vectorized algorithm for sequence alignment implemented in minimap2, a long-read mapping software. Furthermore, to highlight the impact of our work on a real-world application, we couple LOGAN with a many-to-many long-read alignment software called BELLA, and demonstrate that our implementation improves the overall BELLA runtime by up to 10.6×. Finally, we adapt the Roofline model for LOGAN and demonstrate that our implementation is near optimal on the NVIDIA Tesla V100s.

97 MATHEMATICS AND COMPUTING↗

Quantum Spectral Methods for Differential Equations

Recently developed quantum algorithms address computational challenges in numerical analysis by performing linear algebra in Hilbert space. Such algorithms can produce a quantum state proportional to the solution of a d-dimensional system of linear equations or linear differential equations with complexity poly(logd). While several of these algorithms approximate the solution to within ϵ with complexity poly(log(1/ϵ)), no such algorithm was previously known for differential equations with time-dependent coefficients. In this work, we develop a quantum algorithm for linear ordinary differential equations based on so-called spectral methods, an alternative to finite difference methods that approximates the solution globally. Using this approach, we give a quantum algorithm for time-dependent initial and boundary value problems with complexity poly(logd, log(1/ϵ)).

97 MATHEMATICS AND COMPUTING↗

Single-Scattering Properties of Ellipsoidal Dust Aerosols Constrained By Measured Dust Shape Distributions

Most global aerosol models approximate dust as spherical particles, whereas most remote sensing retrieval algorithms approximate dust as spheroidal particles with a shape distribution that conflicts with measurements. These inconsistent and inaccurate shape assumptions generate biases in dust single-scattering properties. Here, we obtain dust single-scattering properties by approximating dust as triaxial ellipsoidal particles with observationally constrained shape distributions. We find that, relative to the ellipsoidal dust optics obtained here, the spherical dust optics used in most aerosol models underestimate dust single-scattering albedo, mass extinction efficiency, and asymmetry parameter for almost all dust sizes in both the shortwave and longwave spectra. We further find that the ellipsoidal dust optics are in substantially better agreement with observations of the scattering matrix and linear depolarization ratio than the spheroidal dust optics used in most retrieval algorithms. However, relative to observations, the ellipsoidal dust optics overestimate the lidar ratio by underestimating the backscattering intensity by a factor of ∼2. This occurs largely because the computational method used to simulate ellipsoidal dust optics (i.e., the improved geometric optics method) underestimates the backscattering intensity by a factor of ∼2 relative to other computational methods (e.g., the physical geometric optics method). We conclude that the ellipsoidal dust optics with observationally constrained shape distributions can help improve global aerosol models and possibly remote sensing retrieval algorithms that do not use the backscattering signal.

Dust↗

An evaluation of solution algorithms and numerical approximation methods for modeling an ion exchange process

The focus of this work is on the modeling of an ion exchange process that occurs in drinking water treatment applications. The model formulation consists of a two-scale model in which a set of microscale diffusion equations representing ion exchange resin particles that vary in size and age are coupled through a boundary condition with a macroscopic ordinary differential equation (ODE), which represents the concentration of a species in a well-mixed reactor. We introduce a new age-averaged model (AAM) that averages all ion exchange particle ages for a given size particle to avoid the expensive Monte-Carlo simulation associated with previous modeling applications. We discuss two different numerical schemes to approximate both the original Monte-Carlo algorithm and the new AAM for this two-scale problem. The first scheme is based on the finite element formulation in space coupled with an existing backward difference formula-based ODE solver in time. The second scheme uses an integral equation based Krylov deferred correction (KDC) method and a fast elliptic solver (FES) for the resulting elliptic equations. Numerical results are presented to validate the new AAM algorithm, which is also shown to be more computationally efficient than the original Monte-Carlo algorithm. We also demonstrate that the higher order KDC scheme is more efficient than the traditional finite element solution approach and this advantage becomes increasingly important as the desired accuracy of the solution increases. We also discuss issues of smoothness, which affect the efficiency of the KDC-FES approach, and outline additional algorithmic changes that would further improve the efficiency of these developing methods for a wide range of applications.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

Algorithms for Multiple Fault Diagnosis With Unreliable Tests

In this paper, we consider the problem of constructing optimal and near-optimal multiple fault diagnosis (MFD) in bipartite systems with unreliable (imperfect) tests. It is known that exact computation of conditional probabilities for multiple fault diagnosis is NP-hard. The novel feature of our diagnostic algorithms is the use of Lagrangian relaxation and subgradient optimization methods to provide: (1) near optimal solutions for the MFD problem, and (2) upper bounds for an optimal branch-and-bound algorithm. The proposed method is illustrated using several examples. Computational results indicate that: (1) our algorithm has superior computational performance to the existing algorithms (approximately three orders of magnitude improvement), (2) the near optimal algorithm generates the most likely candidates with a very high accuracy, and (3) our algorithm can find the most likely candidates in systems with as many as 1000 faults.

Shakeri, Mojdeh↗

A Fast Algorithm for the Convolution of Functions with Compact Support Using Fourier Extensions

In this paper, we present a new algorithm for computing the convolution of two compactly supported functions. The algorithm approximates the functions to be convolved using Fourier extensions and then uses the fast Fourier transform to efficiently compute Fourier extension approximations to the pieces of the result. Finally, the complexity of the algorithm is O(N(log N) 2 ), where N is the number of degrees of freedom used in each of the Fourier extensions.

97 MATHEMATICS AND COMPUTING↗

A MIMO AAA Agorithm for Frequency Dependent Line Modeling

Modeling of power distribution system components that are valid for a wide range of frequencies are crucial for highly accurate modeling of electromagnetic transient (EMT) events. This has recently become of interest due to the improvements needed for the resilient operation of distribution systems. Vector fitting (VF) is a very popular and commonly used algorithm for wide band representations of power system components in EMT simulations. In this research, we present a new multi-input rational approximation algorithm (MIAAA) and illustrate its advantages with respect to VF using examples of approximations of admittance matrices discussed in the literature. We show that MIAAA not only outperforms VF in terms of achieving better accuracy using lesser number of poles, but also has no numerical issues achieving convergence. In contrast to VF, MIAAA is not sensitive to the location of input sample points and it does not require good estimates for the location of the desired approximation poles. The novelty of this research work is the use of recent mathematical results to solve existing challenges in distribution system modeling and to develop rational approximations for power system models that intend to be optimal in terms of accuracy and performance.

AAA algorithm↗

A Multi-Function AAA Algorithm Applied to Frequency Dependent Line Modeling

Modeling of power distribution system components that are valid for a wide range of frequencies are crucial for highly accurate modeling of electromagnetic transient (EMT) events. This has recently become of interest due to the improvements needed for the resilient operation of distribution systems. Vector fitting (VF) is a very popular and commonly used algorithm for wide band representations of power system components in EMT simulations. In this research, we present a new multi-input rational approximation algorithm (MIAAA) and illustrate its advantages with respect to VF using examples of approximations of admittance matrices discussed in the literature. We show that MIAAA not only outperforms VF in terms of achieving better accuracy using lesser number of poles, but also has no numerical issues achieving convergence. In contrast to VF, MIAAA is not sensitive to the location of input sample points and it does not require good estimates for the location of the desired approximation poles. The novelty of this research work is the use of recent mathematical results to solve existing challenges in distribution system modeling and to develop rational approximations for power system models that intend to be optimal in terms of accuracy and performance.

41 EE - Solar Energy Technologies Office (EE-4S)↗

Automated Dynamic Demand Response Implementation on a Micro-grid

In this paper, we describe a system for real-time automated Dynamic and Sustainable Demand Response with sparse data consumption prediction implemented on the University of Southern California campus microgrid. Supply side approaches to resolving energy supply-load imbalance do not work at high levels of renewable energy penetration. Dynamic Demand Response (D 2 R) is a widely used demand-side technique to dynamically adjust electricity consumption during peak load periods. Our D 2 R system consists of accurate machine learning based energy consumption forecasting models that work with sparse data coupled with fast and sustainable load curtailment optimization algorithms that provide the ability to dynamically adapt to changing supply-load imbalances in near real-time. Our Sustainable DR (SDR) algorithms attempt to distribute customer curtailment evenly across sub-intervals during a DR event and avoid expensive demand peaks during a few sub-intervals. It also ensures that each customer is penalized fairly in order to achieve the targeted curtailment. We develop near linear-time constant-factor approximation algorithms along with Polynomial Time Approximation Schemes (PTAS) for SDR curtailment that minimizes the curtailment error defined as the difference between the target and achieved curtailment values. Our SDR curtailment problem is formulated as an Integer Linear Program that optimally matches customers to curtailment strategies during a DR event while also explicitly accounting for customer strategy switching overhead as a constraint. We demonstrate the results of our D 2 R system using real data from experiments performed on the USC smartgrid and show that 1) our prediction algorithms can very accurately predict energy consumption even with noisy or missing data and 2) our curtailment algorithms deliver DR with extremely low curtailment errors in the 0.01-0.05 kWh range.

Kuppannagari, Sanmukh R.↗

LOGAN: High-Performance X-Drop Pairwise Alignment on GPU (LOGAN) v1.0

Pairwise sequence alignment is one of the most computationally intensive kernels in genomic data analysis, accounting for more than 90% of the run time for key bioinformatics applications. This method is particularly expensive for third-generation sequences due to the high computational expense of analyzing these long read lengths (1Kb-1Mb). Given the quadratic overhead of exact pairwise algorithms such as Smith-Waterman, for long alignments, the community primarily relies on approximate algorithms that search only for high-quality alignments and stop early when one is not found. In this work, we present the first GPU optimization of the popular X-drop alignment algorithm, named LOGAN. Results show that our high-performance multi-GPU LOGAN implementation achieves up to 181.6 GCUPS and speed-ups up to 6.6x and 30.7x using 1 and 6 NVIDIA Tesla V100, respectively, over the state-of-the-art software running on two IBM Power9 processors using 168 threads, with equivalent accuracy. We also demonstrate a 2.3x LOGAN speed-up versus ksw2, a state-of-art vectorized algorithm for sequence alignment implemented in minimap2. To highlight the impact of our work on a real-world application, we couple the LOGAN aligner with a many-to-many long-read alignment software called BELLA, and demonstrate that our implementation improves the overall BELLA runtime by up to 10.6x. Finally, we adapt the Roofline model for our optimized kernel and demonstrate that our implementation is near-optimal on the NVIDIA Tesla V100s.

Guidi, Giulia↗

Quantum approximate multi-objective optimization

The goal of multi-objective optimization is to understand optimal trade-offs between competing objective functions by finding the Pareto front, that is, the set of all Pareto-optimal solutions, where no objective can be improved without degrading another one. Multi-objective optimization can be challenging classically, even if the corresponding single-objective optimization problems are efficiently solvable. Thus, multi-objective optimization represents a compelling problem class to analyze with quantum computers. Here we use a low-depth quantum approximate optimization algorithm to approximate the optimal Pareto front of certain multi-objective weighted maximum-cut problems. We demonstrate its performance on an IBM Quantum computer, as well as with matrix product state numerical simulation, and show its potential to outperform classical approaches.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

Efficient generalized boundary detection

Fast, efficient, and robust compression-based methods for detecting boundaries in arbitrary datasets, including sequences (1D datasets), are desired. The methods, each employing three simple algorithms, approximate the information distance between two adjacent sliding windows within a dataset. One of the algorithms calculates an initial ordered list of subsequences; while a second algorithm updates the ordered list of subsequences by dropping a first entry and appending a last entry rather than calculating completely new ordered lists with each iteration. Large values in the distance metric are indicative of boundary locations. A smoothed z-score or a wavelet-based algorithm may then be used to locate peaks in the distance metric, thereby identifying boundary locations. An adaptive version of the method employs a collection of window sizes and corresponding weighting functions, making it more amenable to real datasets with unknown, complex, and changing structures.

Ting, Christina↗

Scalable and Memory-Efficient Algorithms for Controlling Networked Epidemic Processes Using Multiplicative Weights Update Method

We study the problem of designing scalable algorithms to find effective intervention strategies for controlling stochastic epidemic processes on networks. This is a common problem arising in agent based models for epidemic spread. Previous approaches to this problem focus on either heuristics with no guarantees or approximation algorithms that scale only to networks corresponding to county-sized populations, typically, with less than a million nodes. In particular, the mathematical-programming based approaches need to solve the Linear Program (LP) relaxation of the problem using an LP solver, which restricts the scalability of this approach. In this work, we overcome this restriction by designing an algorithm that adapts the multiplicative weights update (MWU) framework, along with the sample average approximation (SAA) technique, to approximately solve the linear program (LP) relaxation for the problem. To scale this approach further, we provide a memory-efficient algorithm that enables scaling to large networks, corresponding to country-size populations, with over 300 million nodes and 30 billion edges. Furthermore, we show that this approach provides near-optimal solutions to the LP in practice.

Sambaturu, Prathyush↗

Efficient algorithms for robust feature matching

One of the basic building blocks in any point-based registration scheme involves matching feature points that are extracted from the sensed image to their counterparts in the reference image. This leads to the fundamental problem of point matching: given two sets of points, find the affine transformation that transforms one point set so that its distance from the other point set is minimized. Because of measurement errors and the presence of outlying data points, it is important that the distance measure between two point sets be robust to these effects. We measure distances using the generalized Hausdorff distance. Point matching can be a computationally intensive task, and there have been a number of algorithms and approaches proposed for solving this problem both theoretical and applied. We present two approaches to the point matching problem, in an attempt to reduce the computational complexity of the problem, while still providing guarantees on the quality of the final match. Our first method is an approximation algorithm, which is loosely based on a branch-and-bound approach due to Huttenlocher and Rucklidge. We show that by varying the approximation error bounds, it is possible to achieve a tradeoff between the quality of the match and the running time of the algorithm. Our second method involves a Monte Carlo method for accelerating the search process used in the first algorithm. With high probability this method succeeds in finding an approximately optimal match. We establish the efficiency of our approaches empirically.

Mount, David M.↗