Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “Scalable 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.

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

At least 271 records · Page 15
All sourcesNASA NTRSDOE OSTI
DOE OSTI2014

Geotagging one hundred million Twitter accounts with total variation minimization

Geographically annotated social media is extremely valuable for modern information retrieval. However, when researchers can only access publicly-visible data, one quickly finds that social media users rarely publish location information. In this work, we provide a method which can geolocate the overwhelming majority of active Twitter users, independent of their location sharing preferences, using only publicly-visible Twitter data. Our method infers an unknown user's location by examining their friend's locations. We frame the geotagging problem as an optimization over a social network with a total variation-based objective and provide a scalable and distributed algorithm for its solution. Furthermore, we show how a robust estimate of the geographic dispersion of each user's ego network can be used as a per-user accuracy measure which is effective at removing outlying errors. Leave-many-out evaluation shows that our method is able to infer location for 101, 846, 236 Twitter users at a median error of 6.38 km, allowing us to geotag over 80% of public tweets.

Compton, Ryan↗
DOE OSTI2012

A Novel Multithreaded Algorithm For Extracting Maximal Chordal Subgraphs

Chordal graphs are triangulated graphs where any cycle larger than three is bisected by a chord. Many combinatorial optimization problems such as computing the minimum fill-in, the size of the maximum clique and the chromatic number are NP-hard on general graphs but have polynomial time solutions on chordal graphs. In this paper, we present a novel multithreaded algorithm to extract a maximal chordal subgraph from a general graph. Our algorithm is based on an iterative approach where each thread can asynchronously update a subset of edges that are dynamically assigned to it. We implement our algorithm on two different multithreaded architectures – Cray XMT, a massively multithreaded platform, and AMD Magny-Cours, a shared memory multicore platform. In addition to the proof of correctness, we present the performance of our algorithm using a testset of carefully generated synthetical graphs with up to half-a-billion edges and real world networks from gene correlation studies. We demonstrate that our algorithm achieves high scalability for all inputs on both types of architectures.

Halappanavar, Mahantesh↗
DOE OSTI2015

Rapid Small-Signal Stability Assessment and Enhancement Following Changes in Topology

The paper proposes a scalable and tractable algorithm for dynamic topology optimization of power systems involving changes in branch on/off status, while respecting small-signal stability (SSS) constraints. A procedure for fast updates of the system matrices (in descriptor form) and without additional full matrix inversions is proposed. To additionally reduce the computation time, only critical eigenvalues (right-most or those in a specified damping ratio and frequency range) are calculated. A quadratic optimization approach is proposed for optimized generation re-dispatch to satisfy SSS constraints. The approach is applied to two (medium- and large-scale) real-world test power systems.

Saric, AT↗
DOE OSTI2025

FIRE: A Failure-Adaptive RL Framework for Edge Computing Migrations

In edge computing, users' service profiles are migrated between edge servers due to user mobility. Reinforcement Learning (RL) frameworks have been proposed to do so, often trained on simulated data. However, existing RL frameworks overlook occasional server failures, which although rare, impact latency-sensitive applications like AR/VR and real- time obstacle detection. These rare failures, being not adequately represented in historical training data, pose a challenge for data-driven RL algorithms. We introduce FIRE, a framework that adapts to rare events by training a RL policy in an edge computing digital twin environment. We propose FIRE-ImRE, an importance sampling-based Q-learning algorithm, which samples rare events proportionally to their impact on the value function. FIRE considers delay, migration, failure, and backup placement costs across individual and shared service profiles. We prove FIRE-ImRE's boundedness and convergence to optimality. Next, we introduce novel deep Q-learning (FIRE-ImDQL) and actor critic (FIRE-ImACRE) versions of our algorithm to enhance scalability. Here, we extend our framework to accommodate users with varying risk tolerances of rare failure events. Through trace-driven experiments, we show that FIRE reduces edge computing costs compared to vanilla RL and the greedy baseline in the event of failures.

Edge computing↗
DOE OSTI2018

A Fast Scalable Quasi-Static Time Series Analysis Method for PV Impact Studies Using Linear Sensitivity Model

Understanding the impact of distributed photovoltaic (PV) resources on various elements of the distribution feeder is imperative for their cost effective integration. A year-long quasi-static time series (QSTS) simulation at 1-second granularity is often necessary to fully study these impacts. However, the significant computational burden associated with running QSTS simulations is a major challenge to their adoption. In this paper, we propose a fast scalable QSTS simulation algorithm that is based on a linear sensitivity model for estimating voltage-related PV impact metrics of a three-phase unbalanced, nonradial distribution system with various discrete step control elements including tap changing transformers and capacitor banks. Here, the algorithm relies on computing voltage sensitivities while taking into account all the effects of discrete controllable elements in the circuit. Consequently, the proposed sensitivity model can accurately estimate the state of controllers at each time step and the number of control actions throughout the year. For the test case of a real distribution feeder with 2969 buses (5469 nodes), 6 load/PV time series power profiles, and 9 voltage regulating elements including controller delays, the proposed algorithm demonstrates a dramatic time reduction, more than 180 times faster than traditional QSTS techniques.

14 SOLAR ENERGY↗
DOE OSTI2025

Efficient Neural Network Approaches for Conditional Optimal Transport with Applications in Bayesian Inference

In this work, we present two neural network approaches that approximate the solutions of static and dynamic conditional optimal transport (COT) problems. Both approaches enable conditional sampling and conditional density estimation, which are core tasks in Bayesian inference—particularly in the simulation-based (“likelihood-free”) setting. Our methods represent the target conditional distribution as a transformation of a tractable reference distribution. Obtaining such a transformation, chosen here to be an approximation of the COT map, is computationally challenging even in moderate dimensions. To improve scalability, our numerical algorithms use neural networks to parameterize candidate maps and further exploit the structure of the COT problem. Our static approach approximates the map as the gradient of a partially input convex neural network. It uses a novel numerical implementation to increase computational efficiency compared to state-of-the-art alternatives. Our dynamic approach approximates the conditional optimal transport via the flow map of a regularized neural ODE; compared to the static approach, it is slower to train but offers more modeling choices and can lead to faster sampling. We demonstrate both algorithms numerically, comparing them with competing state-of-the-art approaches, using benchmark datasets and simulation-based Bayesian inverse problems.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2017

HotSpots: Failure Cascades on Heterogeneous Critical Infrastructure Networks

Critical Infrastructure Systems such as transportation, water and power grid systems are vital to our national security, economy, and public safety. Recent events, like the 2012 hurricane Sandy, show how the interdependencies among different CI networks lead to catastrophic failures among the whole system. Hence, analyzing these CI networks, and modeling failure cascades on them becomes a very important problem. However, traditional models either do not take multiple CIs or the dynamics of the system into account, or model it simplistically. In this paper, we study this problem using a heterogeneous network viewpoint. We first construct heterogeneous CI networks with multiple components using national-level datasets. Then we study novel failure maximization problems on these networks, to compute critical nodes in such systems. We then provide HotSpots, a scalable and effective algorithm for these problems, based on careful transformations. Finally, we conduct extensive experiments on real CIS data from multiple US states, and show that our method HotSpots outperforms non-trivial baselines, gives meaningful results and that our approach gives immediate benefits in providing situational-awareness during large-scale failures.

Chen, Liangzhe↗
DOE OSTI2014

Master-Slave Control Scheme in Electric Vehicle Smart Charging Infrastructure

WINSmartEV is a software based plug-in electric vehicle (PEV) monitoring, control, and management system. It not only incorporates intelligence at every level so that charge scheduling can avoid grid bottlenecks, but it also multiplies the number of PEVs that can be plugged into a single circuit. This paper proposes, designs, and executes many upgrades to WINSmartEV. These upgrades include new hardware that makes the level 1 and level 2 chargers faster, more robust, and more scalable. It includes algorithms that provide a more optimal charge scheduling for the level 2 (EVSE) and an enhanced vehicle monitoring/identification module (VMM) system that can automatically identify PEVs and authorize charging.

42 ENGINEERING↗
DOE OSTI2016

TagDigger: user-friendly extraction of read counts from GBS and RAD-seq data

In genotyping-by-sequencing (GBS) and restriction site-associated DNA sequencing (RAD-seq), read depth is important for assessing the quality of genotype calls and estimating allele dosage in polyploids. However, existing pipelines for GBS and RAD-seq do not provide read counts in formats that are both accurate and easy to access. Additionally, although existing pipelines allow previously-mined SNPs to be genotyped on new samples, they do not allow the user to manually specify a subset of loci to examine. Pipelines that do not use a reference genome assign arbitrary names to SNPs, making meta-analysis across projects difficult. We created the software TagDigger, which includes three programs for analyzing GBS and RAD-seq data. The first script, tagdigger_interactive.py, rapidly extracts read counts and genotypes from FASTQ files using user supplied sets of barcodes and tags. Input and output is in CSV format so that it can be opened by spreadsheet software. Tag sequences can also be imported from the Stacks, TASSEL-GBSv2, TASSEL-UNEAK, or pyRAD pipelines, and a separate file can be imported listing the names of markers to retain. A second script, tag_manager.py, consolidates marker names and sequences across multiple projects. A third script, barcode_splitter.py, assists with preparing FASTQ data for deposit in a public archive by splitting FASTQ files by barcode and generating MD5 checksums for the resulting files. TagDigger is open-source and freely available software written in Python 3. It uses a scalable, rapid search algorithm that can process over 100 million FASTQ reads per hour. TagDigger will run on a laptop with any operating system, does not consume hard drive space with intermediate files, and does not require programming skill to use.

59 BASIC BIOLOGICAL SCIENCES↗
DOE OSTI2020

NAPAbench 2: A network synthesis algorithm for generating realistic protein-protein interaction (PPI) network families

Comparative network analysis provides effective computational means for gaining novel insights into the structural and functional compositions of biological networks. In recent years, various methods have been developed for biological network alignment, whose main goal is to identify important similarities and critical differences between networks in terms of their topology and composition. A major impediment to advancing network alignment techniques has been the lack of gold-standard benchmarks that can be used for accurate and comprehensive performance assessment of such algorithms. The original NAPAbench (network alignment performance assessment benchmark) was developed to address this problem, and it has been widely utilized by many researchers for the development, evaluation, and comparison of novel network alignment techniques. In this work, we introduce NAPAbench 2—a major update of the original NAPAbench that was introduced in 2012. NAPAbench 2 includes a completely redesigned network synthesis algorithm that can generate protein-protein interaction (PPI) network families whose characteristics closely match those of the latest real PPI networks. Furthermore, the network synthesis algorithm comes with an intuitive GUI that allows users to easily generate PPI network families with an arbitrary number of networks of any size, according to a flexible user-defined phylogeny. In addition, NAPAbench 2 provides updated benchmark datasets—created using the redesigned network synthesis algorithm—which can be used for comprehensive performance assessment of network alignment algorithms and their scalability.

42 ENGINEERING↗
DOE OSTI2014

SciDAC Institute: Combinatorial Scientific Computing and Petascale Simulations (CSCAPES) (Final Report)

Throughout the project we focused on six research areas. In accordance with the specific goals, we developed novel models to solve some of these. Some of the problems required scalable distributed memory algorithms, where as some required sequential solutions. Although several graduate students and collaborators were actively involved in all of these activities, only one PhD student was directly supported by the grant. Below is a brief overview of the research carried out in each of these areas.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2014

SciDAC Institute for Ultra-Scale Visualization: Activity Recognition for Ultra-Scale Visualization

Understanding the science behind ultra-scale simulations requires extracting meaning from data sets of hundreds of terabytes or more. Developing scalable parallel visualization algorithms is a key step enabling scientists to interact and visualize their data at this scale. However, at extreme scales, the datasets are so huge, there is not even enough time to view the data, let alone explore it with basic visualization methods. Automated tools are necessary for knowledge discovery -- to help sift through the information and isolate characteristic patterns, thereby enabling the scientist to study local interactions, the origin of features and their evolution in large volumes of data. These tools must be able to operate on data of this scale and work with the visualization process. In this project, we developed a framework for activity detection to allow scientists to model and extract spatio-temporal patterns from time-varying data.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2016

Mimetic Finite Differences and Algebraic Multilevel Methods for Reservoir Performance Predictions: CRADA Final Report

The need to better predict and control reservoir performance is driving the development of increasingly sophisticated reservoir models that use unstructured general polyhedral grids to capture highly detailed stratigraphy. However, both discretization methods and scalable iterative solution algorithms for these situations are an active area of research. In this work we compared the performance of a new Mimetic Finite Difference (MFD) method with two new Mixed Finite Element methods, and LANL and the CRADA Participant investigated the performance of Los Alamos National Laboratory’s algebraic multigrid code on realistic flow problems. Furthermore, uncertainty quantification requires rapid evaluations of reservoir models. To do this, fine-scale reservoir models need to be coarsened and yet important fine-scale features and processes that have a significant impact on flows need to be preserved. To this end, we investigated the use of multi-resolution methods, such as the Multilevel Multiscale Mimetic (M3) method, to coarsen reservoir models.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2016

Modeling and simulation of high dimensional stochastic multiscale PDE systems at the exascale

Predictive Modeling of multiscale and Multiphysics systems requires accurate data driven characterization of the input uncertainties, and understanding of how they propagate across scales and alter the final solution. This project develops a rigorous mathematical framework and scalable uncertainty quantification algorithms to efficiently construct realistic low dimensional input models, and surrogate low complexity systems for the analysis, design, and control of physical systems represented by multiscale stochastic PDEs. The work can be applied to many areas including physical and biological processes, from climate modeling to systems biology.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2022

Intelligent System Partitioning for Agent-Based Security Constrained Optimal Power Flow

This project developed scalable, computationally efficient algorithms to solve realistic large-scale power system optimization problems as part of a larger series of competitions run by ARPA-E. These problems are important because the secure and reliable operation of the power grid, especially under increased uncertainty and variability, is growing increasingly challenging. The economic feasibility of the proposed methods developed by our team is quite low, considering it’s a purely software-based solution to operate power grids more efficiently. The technical effectiveness, as evidenced by our performance in the competition, balances heuristics and approximations to provide a tradeoff between speed and accuracy.

24 POWER TRANSMISSION AND DISTRIBUTION↗
DOE OSTI2025

Fast and robust strategies for large-scale mixed-integer SCOPF

This project develops scalable, computationally efficient algorithms to solve realistic large-scale power system optimization problems, including systems with more than 8,000 buses, as part of a larger series of competitions run by ARPA-E. These problems are critical because the secure and reliable operation of the power grid is becoming increasingly challenging, especially under conditions of increased uncertainty and variability. The economic feasibility of our methods is high, given that they are purely software-based solutions designed to operate power grids more efficiently. The technical effectiveness balances heuristics and approximations to provide a trade-off between speed and accuracy.

24 POWER TRANSMISSION AND DISTRIBUTION↗
DOE OSTI2021

Algebraic Algorithms for Betweenness and Percolation Centrality

Abstract In this paper, we explored different ways to write the algebraic version of betweenness centrality algorithm. Particularly, we focused on Brandes' algorithm. We aimed for algebraic betweenness centrality that can be parallelized easily. We proposed 3-tuple geodetic semiring as an extension to the usual geodetic semiring with 2-tuples. Using the 3-tuple geodetic semiring, Dijkstra's and Brandes' algorithm, we wrote more concise and general algebraic betweenness centrality (ABC) algorithm which is valid for weighted and directed graphs. We also proposed an alternative version of ABC using the usual geodetic semiring with 2-tuple where we used a simple way to construct shortest path tree after computing shortest path distances in the usual geodetic semiring. This allows us to avoid computational complexity of ABC implementation using 3-tuple geodetic semiring. We used numba to optimize and parallelize ABC. We evaluated the performance of ABC using 2-tuple geodetic semiring as compared to NetworkX, a common python package for graph algorithms. We did scalability experiments on parallel ABC and showed its total speedup. We also showed that with small modification, ABC can be adapted to algebraicly compute other centrality measures such as percolation centrality.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2024

Learning of networked spreading models from noisy and incomplete data

Recent years have seen a lot of progress in algorithms for learning parameters of spreading dynamics from both full and partial data. Some of the remaining challenges include model selection under the scenarios of unknown network structure, noisy data, missing observations in time, as well as an efficient incorporation of prior information to minimize the number of samples required for an accurate learning. Here, in this work, we introduce a universal learning method based on a scalable dynamic message-passing technique that addresses these challenges often encountered in real data. The algorithm leverages available prior knowledge on the model and on the data, and reconstructs both network structure and parameters of a spreading model. We show that a linear computational complexity of the method with the key model parameters makes the algorithm scalable to large network instances.

97 MATHEMATICS AND COMPUTING↗