Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “heuristic”

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 343 records · Page 19
All sourcesNASA NTRSDOE OSTI
DOE OSTI2014

Efficient algorithm for locating and sizing series compensation devices in large power transmission grids: II. Solutions and applications

In a companion manuscript, we developed a novel optimization method for placement, sizing, and operation of Flexible Alternating Current Transmission System (FACTS) devices to relieve transmission network congestion. Specifically, we addressed FACTS that provide Series Compensation (SC) via modification of line inductance. In this manuscript, this heuristic algorithm and its solutions are explored on a number of test cases: a 30-bus test network and a realistically-sized model of the Polish grid (~ 2700 nodes and ~ 3300 lines). The results on the 30-bus network are used to study the general properties of the solutions including non-locality and sparsity. The Polish grid is used as a demonstration of the computational efficiency of the heuristics that leverages sequential linearization of power flow constraints and cutting plane methods that take advantage of the sparse nature of the SC placement solutions. Using these approaches, the algorithm is able to solve an instance of Polish grid in tens of seconds. We explore the utility of the algorithm by analyzing transmission networks congested by (a) uniform load growth, (b) multiple overloaded configurations, and (c) sequential generator retirements.

24 POWER TRANSMISSION AND DISTRIBUTION↗
DOE OSTI2015

On the possibility of large axion moduli spaces

We study the diameters of axion moduli spaces, focusing primarily on type IIB compactifications on Calabi-Yau three-folds. In this case, we derive a stringent bound on the diameter in the large volume region of parameter space for Calabi-Yaus with simplicial Kähler cone. This bound can be violated by Calabi-Yaus with non-simplicial Kähler cones, but additional contributions are introduced to the effective action which can restrict the field range accessible to the axions. We perform a statistical analysis of simulated moduli spaces, finding in all cases that these additional contributions restrict the diameter so that these moduli spaces are no more likely to yield successful inflation than those with simplicial Kähler cone or with far fewer axions. Further heuristic arguments for axions in other corners of the duality web suggest that the difficulty observed in http://dx.doi.org/10.1088/1475-7516/2003/06/001 of finding an axion decay constant parametrically larger than M{sub p} applies not only to individual axions, but to the diagonals of axion moduli space as well. This observation is shown to follow from the weak gravity conjecture of http://dx.doi.org/10.1088/1126-6708/2007/06/060, so it likely applies not only to axions in string theory, but also to axions in any consistent theory of quantum gravity.

72 PHYSICS OF ELEMENTARY PARTICLES AND FIELDS↗
DOE OSTI2024

Characterizing and communicating uncertainty: lessons from NASA’s Carbon Monitoring System

Navigating uncertainty is a critical challenge in all fields of science, especially when translating knowledge into real-world policies or management decisions. However, the wide variance in concepts and definitions of uncertainty across scientific fields hinders effective communication. As a microcosm of diverse fields within Earth Science, NASA’s Carbon Monitoring System (CMS) provides a useful crucible in which to identify cross-cutting concepts of uncertainty. The CMS convened the Uncertainty Working Group (UWG), a group of specialists across disciplines, to evaluate and synthesize efforts to characterize uncertainty in CMS projects. This paper represents efforts by the UWG to build a heuristic framework designed to evaluate data products and communicate uncertainty to both scientific and non-scientific end users. We consider four pillars of uncertainty: origins, severity, stochasticity versus incomplete knowledge, and spatial and temporal autocorrelation. Using a common vocabulary and a generalized workflow, the framework introduces a graphical heuristic accompanied by a narrative, exemplified through contrasting case studies. Envisioned as a versatile tool, this framework provides clarity in reporting uncertainty, guiding users and tempering expectations. Beyond CMS, it stands as a simple yet powerful means to communicate uncertainty across diverse scientific communities.

54 ENVIRONMENTAL SCIENCES↗
DOE OSTI2021

Optimal calibration of gates in trapped-ion quantum computers

Abstract To harness the power of quantum computing, it is essential that a quantum computer provide maximal possible fidelity for a quantum circuit. To this end, much work has been done in the context of qubit routing or embedding, i.e., mapping circuit qubits to physical qubits based on gate performance metrics to optimize the fidelity of execution. Here, we take an alternative approach that leverages a unique capability of a trapped-ion quantum computer, i.e., the all-to-all qubit connectivity. We develop a method to determine a fixed number (budget) of quantum gates that, when calibrated, will maximize the fidelity of a batch of input quantum programs. This dynamic allocation of calibration resources on randomly accessible gates, determined using our heuristics, increases, for a wide range of calibration budget, the average fidelity from 70% or lower to 90% or higher for a typical batch of jobs on an 11-qubit device, in which the fidelity of calibrated and uncalibrated gates are taken to be 99% and 90%, respectively. Our heuristics are scalable, more than 2.5 orders of magnitude faster than a randomized method for synthetic benchmark circuits generated based on real-world use cases.

Maksymov, Andrii (ORCID:0000000282442851)↗
DOE OSTI2017

Kmer-SSR: a fast and exhaustive SSR search algorithm

Motivation: One of the main challenges with bioinformatics software is that the size and complexity of datasets necessitate trading speed for accuracy, or completeness. To combat this problem of computational complexity, a plethora of heuristic algorithms have arisen that report a ‘good enough’ solution to biological questions. However, in instances such as Simple Sequence Repeats (SSRs), a ‘good enough’ solution may not accurately portray results in population genetics, phylogenetics and forensics, which require accurate SSRs to calculate intra- and inter-species interactions. Results: We present Kmer-SSR, which finds all SSRs faster than most heuristic SSR identification algorithms in a parallelized, easy-to-use manner. The exhaustive Kmer-SSR option has 100% precision and 100% recall and accurately identifies every SSR of any specified length. To identify more biologically pertinent SSRs, we also developed several filters that allow users to easily view a subset of SSRs based on user input. Kmer-SSR, coupled with the filter options, accurately and intuitively identifies SSRs quickly and in a more user-friendly manner than any other SSR identification algorithm. Availability and implementation: The source code is freely available on GitHub at https://github. com/ridgelab/Kmer-SSR.

59 BASIC BIOLOGICAL SCIENCES↗
DOE OSTI2020

Comparison of linear regression, k-nearest neighbour and random forest methods in airborne laser-scanning-based prediction of growing stock

Abstract In this study, for five sites around the world, we look at the effects of different model types and variable selection approaches on forest yield modelling performances in an area-based approach (ABA). We compared ordinary least squares regression (OLS), k-nearest neighbours (kNN) and random forest (RF). Our objective was to test if there are systematic differences in accuracy between OLS, kNN and RF in ABA predictions of growing stock volume. The analyses are based on a 5-fold cross-validation at five study sites: an eucalyptus plantation, a temperate forest and three different boreal forests. Two completely independent validation datasets were also available for two of the boreal sites. For the kNN, we evaluated multiple measures of distance including Euclidean, Mahalanobis, most similar neighbour (MSN) and an RF-based distance metric. The variable selection approaches we examined included a heuristic approach (for OLS, kNN and RF), exhaustive search among all combinations (OLS only) and all variables together (RF only). Performances varied by model type and variable selection approaches among sites. OLS and RF had similar accuracies and were more efficient than any of the kNN variants. Variable selection did not affect RF performance. Heuristic and exhaustive variable selection performed similarly for OLS. kNN fared the poorest amongst model types, and kNN with RF distance was prone to overfitting when compared with a validation dataset. Additional caution is therefore required when building kNN models for volume prediction though ABA, being preferable instead to opt for models based on OLS with some variable selection, or RF with all variables together.

Cosenza, Diogo N.↗
DOE OSTI2018

A physical model of mass ejection in failed supernovae

During the core collapse of massive stars, the formation of the proto-neutron star is accompanied by the emission of a significant amount of mass energy (~0.3M ⊙ ) in the form of neutrinos. This mass-energy loss generates an outward-propagating pressure wave that steepens into a shock near the stellar surface, potentially powering a weak transient associated with an otherwise-failed supernova. We analytically investigate this mass-loss-induced wave generation and propagation. Heuristic arguments provide an accurate estimate of the amount of energy contained in the outgoing sound pulse. We then develop a general formalism for analysing the response of the star to centrally concentrated mass loss in linear perturbation theory. To build intuition, we apply this formalism to polytropic stellar models, finding qualitative and quantitative agreement with simulations and heuristic arguments. We also apply our results to realistic pre-collapse massive star progenitors (both giants and compact stars). Our analytic results for the sound pulse energy, excitation radius, and steepening in the stellar envelope are in good agreement with full time-dependent hydrodynamic simulations.We show that prior to the sound pulses arrival at the stellar photosphere, the photosphere has already reached velocities ~20–100 per cent of the local sound speed, thus likely modestly decreasing the stellar effective temperature prior to the star disappearing. Our results provide important constraints on the physical properties and observational appearance of failed supernovae.

79 ASTRONOMY AND ASTROPHYSICS↗
DOE OSTI2019

Taming convergence in the determinant approach for x-ray excitation spectra

A determinant formalism in combination with ab initio calculations was proposed recently and has paved a way for simulating and interpreting x-ray excitation spectra in condensed-phase systems. The method systematically takes into account many-electron effects in the Mahan-Noziéres-De Dominicis (MND) theory, including core-level excitonic effects, the Fermi-edge singularity, shakeup excitations, and wave function overlap effects such as the orthogonality catastrophe, all within a universal framework using many-electron configurations. A heuristic search algorithm was introduced to search for the configurations that are important for defining the x-ray spectral line shape, instead of enumerating them in a brute-force way. The algorithm has proven to be efficient for calculating O K edges of transition metal oxides, which converge at the second excitation order (denoted as $f^{(n)}$ with n = 2), i.e., the final-state configurations with two e-h pairs (with one hole being the core hole). However, it remains unknown how the determinant x-ray spectra converge for general cases and at which excitation order n should one stop the determinant calculation. Even with the heuristic algorithm, the number of many-electron configurations still grows exponentially with the excitation order n. In this work we prove two theorems that can indicate the order of magnitude of the contribution of the $f^{(n)}$ configurations, so that one can estimate their contribution very quickly without actually calculating their amplitudes. The two theorems are based on singular-value decomposition (SVD) analysis, a method that is widely used to quantify entanglement between two quantum many-body systems. Finally, we examine the K edges of several metallic systems with the determinant formalism up to $f^{(5)}$ to illustrate the usefulness of the theorems.

75 CONDENSED MATTER PHYSICS, SUPERCONDUCTIVITY AND↗
DOE OSTI2022

Data-centric framework for crystal structure identification in atomistic simulations using machine learning

Atomic-level modeling performed at large scales enables the investigation of mesoscale materials properties with atom-by-atom resolution. The spatial complexity of such cross-scale simulations renders them unsuitable for simple human visual inspection. Instead, specialized structure characterization techniques are required to aid interpretation. These have historically been challenging to construct, requiring significant intuition and effort. Here we propose an alternative framework for a fundamental structural characterization task: classifying atoms according to the crystal structure to which they belong. Our approach is data-centric and favors the employment of Machine Learning over heuristic rules of classification. A group of data-science tools and simple local descriptors of atomic structure are employed together with an efficient synthetic training set. We also introduce the first standard and publicly available benchmark data set for evaluation of algorithms for crystal-structure classification. Further, it is demonstrated that our data-centric framework outperforms all of the most popular heuristic methods—especially at high temperatures when lattices are the most distorted—while introducing a systematic route for generalization to new crystal structures. Moreover, through the use of outlier detection algorithms our approach is capable of discerning between amorphous atomic motifs (i.e., noncrystalline phases) and unknown crystal structures, making it uniquely suited for exploratory materials synthesis simulations.

36 MATERIALS SCIENCE↗
DOE OSTI2013

Ant Colony Optimization for Mapping, Scheduling and Placing in Reconfigurable Systems

Modern heterogeneous embedded platforms, com- posed of several digital signal, application specific and general purpose processors, also include reconfigurable devices support- ing partial dynamic reconfiguration. These devices can change the behavior of some of their parts during execution, allowing hardware acceleration of more sections of the applications. Never- theless, partial dynamic reconfiguration imposes severe overheads in terms of latency. For such systems, a critical part of the design phase is deciding on which processing elements (mapping) and when (scheduling) executing a task, but also how to place them on the reconfigurable device to guarantee the most efficient reuse of the programmable logic. In this paper we propose an algorithm based on Ant Colony Optimization (ACO) that simultaneously executes the scheduling, the mapping and the linear placing of tasks, hiding reconfiguration overheads through prefetching. Our heuristic gradually constructs solutions and then searches around the best ones, cutting out non-promising areas of the design space. We show how to consider the partial dynamic reconfiguration constraints in the scheduling, placing and mapping problems and compare our formulation to other heuristics that address the same problems. We demonstrate that our proposal is more general and robust, and finds better solutions (16.5% in average) with respect to competing solutions.

Ant Colony Optimization↗
DOE OSTI2015

Time Series Discord Detection in Medical Data using a Parallel Relational Database [PowerPoint]

Recent advances in sensor technology have made continuous real-time health monitoring available in both hospital and non-hospital settings. Since data collected from high frequency medical sensors includes a huge amount of data, storing and processing continuous medical data is an emerging big data area. Especially detecting anomaly in real time is important for patients’ emergency detection and prevention. A time series discord indicates a subsequence that has the maximum difference to the rest of the time series subsequences, meaning that it has abnormal or unusual data trends. In this study, we implemented two versions of time series discord detection algorithms on a high performance parallel database management system (DBMS) and applied them to 240 Hz waveform data collected from 9,723 patients. The initial brute force version of the discord detection algorithm takes each possible subsequence and calculates a distance to the nearest non-self match to find the biggest discords in time series. For the heuristic version of the algorithm, a combination of an array and a trie structure was applied to order time series data for enhancing time efficiency. The study results showed efficient data loading, decoding and discord searches in a large amount of data, benefiting from the time series discord detection algorithm and the architectural characteristics of the parallel DBMS including data compression, data pipe-lining, and task scheduling.

47 OTHER INSTRUMENTATION↗
DOE OSTI2014

PLAStiCC: Predictive Look-Ahead Scheduling for Continuous dataflows on Clouds

Scalable stream processing and continuous dataflow systems are gaining traction with the rise of big data due to the need for processing high velocity data in near real time. Unlike batch processing systems such as MapReduce and workflows, static scheduling strategies fall short for continuous dataflows due to the variations in the input data rates and the need for sustained throughput. The elastic resource provisioning of cloud infrastructure is valuable to meet the changing resource needs of such continuous applications. However, multi-tenant cloud resources introduce yet another dimension of performance variability that impacts the application’s throughput. In this paper we propose PLAStiCC, an adaptive scheduling algorithm that balances resource cost and application throughput using a prediction-based look-ahead approach. It not only addresses variations in the input data rates but also the underlying cloud infrastructure. In addition, we also propose several simpler static scheduling heuristics that operate in the absence of accurate performance prediction model. These static and adaptive heuristics are evaluated through extensive simulations using performance traces obtained from public and private IaaS clouds. Our results show an improvement of up to 20% in the overall profit as compared to the reactive adaptation algorithm.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2020

Pufferscale: Rescaling HPC Data Services for High Energy Physics Applications

User-space HPC data services are emerging as an appealing alternative to traditional parallel file systems, because of their ability to be tailored to application needs while eliminating unnecessary overheads incurred by POSIX compliance. The High Energy Physics (HEP) community is progressively turning towards such services to enable high-throughput accesses under heavy concurrency to billions of event data produced by instruments and consumed by subsequent analysis workflows. Such services would benefit from the possibility to be rescaled up and down to adapt to changing workloads, as experimental campaigns progress, in order to optimize resource usage. This paper formalizes rescaling a distributed storage system as a multi objective optimization problem considering three criteria: load balance, data balance, and duration of the rescaling operation. We propose a heuristic for rapidly finding a good approximate solution, while allowing users to weight the criteria as needed. The heuristic is evaluated with Pufferscale, a new rescaling manager for microservice-based distributed storage systems. To validate our approach in a real-world ecosystem, we showcase the use of Pufferscale as a means to enable storage malleability in the HEPnOS storage system for HEP applications.

Distributed Storage System↗
DOE OSTI2018

A Heterogeneity-Aware Task Scheduler for Spark

Big data processing systems such as Spark are employed in an increasing number of diverse applications-such as machine learning, graph computation, and scientific computing-each with dynamic and different resource needs. These applications increasingly run on heterogeneous hardware, e.g., with out-of-core accelerators. However, big data platforms do not factor in the multi-dimensional heterogeneity of applications and hardware. This leads to a fundamental mismatch between the application and hardware characteristics, and the resource scheduling adopted in big data platforms. For example, Hadoop and Spark consider only data locality when assigning tasks to nodes, and typically disregard the hardware capabilities and suitability to specific application requirements. In this paper, we present RUPAM, a heterogeneity-aware task scheduling system for big data platforms, which considers both task-level resource characteristics and underlying hardware characteristics, as well as preserves data locality. RUPAM adopts a simple yet effective heuristic to decide the dominant scheduling factor (e.g., CPU, memory, or I/O), given a task in a particular stage. Our experiments show that RUPAM is able to improve the performance of representative applications by up to 62.3% compared to the standard Spark scheduler.

Computer Science↗
DOE OSTI2015

An ILP based Algorithm for Optimal Customer Selection for Demand Response in SmartGrids

Demand Response (DR) events are initiated by utilities during peak demand periods to curtail consumption. They ensure system reliability and minimize the utility’s expenditure. Selection of the right customers and strategies is critical for a DR event. An effective DR scheduling algorithm minimizes the curtailment error which is the absolute difference between the achieved curtailment value and the target. State-of-the-art heuristics exist for customer selection, however their curtailment errors are unbounded and can be as high as 70%. In this work, we develop an Integer Linear Programming (ILP) formulation for optimally selecting customers and curtailment strategies that minimize the curtailment error during DR events in SmartGrids. We perform experiments on real world data obtained from the University of Southern California’s SmartGrid and show that our algorithm achieves near exact curtailment values with errors in the range of 10 -7 to 10 -5 , which are within the range of numerical errors. We compare our results against the state-of-the-art heuristic being deployed in practice in the USC SmartGrid. We show that for the same set of available customer strategy pairs our algorithm performs 103 to 107 times better in terms of the curtailment errors incurred.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2017

Approximate Computing Techniques for Iterative Graph Algorithms

Approximate computing enables processing of large-scale graphs by trading off quality for performance. Approximate computing techniques have become critical not only due to the emergence of parallel architectures but also the availability of large scale datasets enabling data-driven discovery. Using two prototypical graph algorithms, PageRank and community detection, we present several approximate computing heuristics to scale the performance with minimal loss of accuracy. We present several heuristics including loop perforation, data caching, incomplete graph coloring and synchronization, and evaluate their efficiency. We demonstrate performance improvements of up to 83% for PageRank and up to 450x for community detection, with low impact of accuracy for both the algorithms. We expect the proposed approximate techniques will enable scalable graph analytics on data of importance to several applications in science and their subsequent adoption to scale similar graph algorithms.

Panyala, Ajay R.↗
DOE OSTI2021

Parallel Algorithms for Efficient Computation of High-Order Line Graphs of Hypergraphs

This paper considers structures of systems beyond dyadic (pairwise) interactions and investigates mathematical modeling of multi-way interactions and connections as hypergraphs, where captured relationships among system entities are set-valued. To date, in most situations, entities in a hypergraph are considered connected as long as there is at least one common ``neighbor''. However, minimal commonality sometimes discards the ``strength'' of connections and interactions among groups. To this end, considering the ``width'' of a connection, referred to as the \emph{$s$-overlap} of neighbors, provides more meaningful insights into how closely the communities or entities interact with each other. In addition, $s$-overlap computation is the fundamental kernel to construct the line graph of a hypergraph, a low-order approximation of the hypergraph which can carry significant information about the original hypergraph. Subsequent stages of a data analytics pipeline then can apply highly-tuned graph algorithms on the line graph to reveal important features. Given a hypergraph, computing the $s$-overlaps by exhaustively considering all pairwise entities can be computationally prohibitive. To tackle this challenge, we develop efficient algorithms to compute $s$-overlaps and the corresponding line graph of a hypergraph. We propose several heuristics to avoid execution of redundant work and improve performance of the $s$-overlap computation. Our parallel algorithm, combined with these heuristics, is orders of magnitude (more than $10\times$) faster than the naive algorithm in all cases and the SpGEMM algorithm with filtration in most cases (especially with large $s$ value).

hypergraph algorithms, graph algorithms, parallel ↗
DOE OSTI2018

Scalable Distributed Memory Community Detection Using Vite

Graph clustering, popularly known as community detection, is a fundamental graph operation used in several applications of relevance for network analysis and cybersecurity. Community detection is an operation of partitioning a network into an arbitrary number of “communities” such that each com munity represents a tightly-knit group of nodes with relatively sparser connections to the rest of the nodes in the network. The need to compute clustering on large-scale networks necessitates the development of efficient parallel algorithms capable of exploiting modern parallel architectures. However, due to their irregular and inherently sequential nature, many of the current algorithms for community detection are challenging to parallelize. In response to the 2018 Graph Challenge, we present Vite which is a distributed-memory parallel community detection method. Vite is a parallelization of the algorithmic template provided by a widely-used serial method (Louvain). Alongside, it uses several heuristics aimed at significantly improving parallelism and performance, while preserving output quality. Using the inputs from the 2018 Graph Challenge (static and streaming), we demonstrate superior performance and high quality solutions based on four parallelization heuristics.

community detection↗