SEARCH · Engineering Papers

Results for “distributed 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 1,009 records · Page 56

All sources NASA NTRS DOE OSTI

DOE OSTI2017

Summer Proceedings 2016: The Center for Computing Research at Sandia National Laboratories

Solving sparse linear systems from the discretization of elliptic partial differential equations (PDEs) is an important building block in many engineering applications. Sparse direct solvers can solve general linear systems, but are usually slower and use much more memory than effective iterative solvers. To overcome these two disadvantages, a hierarchical solver (LoRaSp) based on H2-matrices was introduced in [22]. Here, we have developed a parallel version of the algorithm in LoRaSp to solve large sparse matrices on distributed memory machines. On a single processor, the factorization time of our parallel solver scales almost linearly with the problem size for three-dimensional problems, as opposed to the quadratic scalability of many existing sparse direct solvers. Moreover, our solver leads to almost constant numbers of iterations, when used as a preconditioner for Poisson problems. On more than one processor, our algorithm has significant speedups compared to sequential runs. With this parallel algorithm, we are able to solve large problems much faster than many existing packages as demonstrated by the numerical experiments.

97 MATHEMATICS AND COMPUTING↗

DOE OSTI2020

Distribution Feeder-Scale Fast Frequency Response via Optimal Coordination of Net-load Resources Part II: Large-Scale Demonstration

This work is the second of a two-part series in which we develop and experimentally demonstrate a hierarchical control solution for optimally coordinating thousands of deferrable loads and distributed energy resources (DERs) to provide fast frequency response (FFR) from an entire distribution feeder. In Part I, we developed and proved practical algorithms for fast, cost-based optimal dispatch and for determining the optimal amount of headroom to operate solar inverters with to support FFR dispatch while minimizing opportunity cost. Simulation results in Part I demonstrated the advantages of the hierarchical dispatch approach in being able to maintain fast solution times needed for FFR even when the problem size increases. In Part II, we implement the algorithms developed in Part I in a novel, large-scale power hardware-in-the-loop experiment including embedded controllers and more than 100 powered appliance loads and DER connected to a simulated real-world distribution system with more than 10,000 controlled devices. Experimental results from multiple scenarios confirm that the optimal FFR dispatch approach scales well and can optimally coordinate more than 10,000 net-load resources across a distribution network while achieving hardware response times within 500 ms, which is not possible using state-of-the-art optimal coordination approaches.

24 POWER TRANSMISSION AND DISTRIBUTION↗

DOE OSTI2016

Implementation of Dynamic Extensible Adaptive Locally Exchangeable Measures (IDEALEM) v 0.1

Handling large streaming data is essential for various applications such as network traffic analysis, social networks, energy cost trends, and environment modeling. However, it is in general intractable to store, compute, search, and retrieve large streaming data. This software addresses a fundamental issue, which is to reduce the size of large streaming data and still obtain accurate statistical analysis. As an example, when a high-speed network such as 100 Gbps network is monitored, the collected measurement data rapidly grows so that polynomial time algorithms (e.g., Gaussian processes) become intractable. One possible solution to reduce the storage of vast amounts of measured data is to store a random sample, such as one out of 1000 network packets. However, such static sampling methods (linear sampling) have drawbacks: (1) it is not scalable for high-rate streaming data, and (2) there is no guarantee of reflecting the underlying distribution. In this software, we implemented a dynamic sampling algorithm, based on the recent technology from the relational dynamic bayesian online locally exchangeable measures, that reduces the storage of data records in a large scale, and still provides accurate analysis of large streaming data. The software can be used for both online and offline data records.

Sim, Alex↗

DOE OSTI2014

Efficient Extraction of High Centrality Vertices in Distributed Graphs

Betweenness centrality (BC) is an important measure for identifying high value or critical vertices in graphs, in variety of domains such as communication networks, road networks, and social graphs. However, calculating betweenness values is prohibitively expensive and, more often, domain experts are interested only in the vertices with the highest centrality values. In this paper, we first propose a partition-centric algorithm (MS-BC) to calculate BC for a large distributed graph that optimizes resource utilization and improves overall performance. Further, we extend the notion of approximate BC by pruning the graph and removing a subset of edges and vertices that contribute the least to the betweenness values of other vertices (MSL-BC), which further improves the runtime performance. We evaluate the proposed algorithms using a mix of real-world and synthetic graphs on an HPC cluster and analyze its strengths and weaknesses. The experimental results show an improvement in performance of upto 12x for large sparse graphs as compared to the state-of-the-art, and at the same time highlights the need for better partitioning methods to enable a balanced workload across partitions for unbalanced graphs such as small-world or power-law graphs.

97 MATHEMATICS AND COMPUTING↗

DOE OSTI2017

Comparative evaluation of atom mapping algorithms for balanced metabolic reactions: application to Recon 3D

The mechanism of each chemical reaction in a metabolic network can be represented as a set of atom mappings, each of which relates an atom in a substrate metabolite to an atom of the same element in a product metabolite. Genome-scale metabolic network reconstructions typically represent biochemistry at the level of reaction stoichiometry. However, a more detailed representation at the underlying level of atom mappings opens the possibility for a broader range of biological, biomedical and biotechnological applications than with stoichiometry alone. Complete manual acquisition of atom mapping data for a genome-scale metabolic network is a laborious process. However, many algorithms exist to predict atom mappings. How do their predictions compare to each other and to manually curated atom mappings? For more than four thousand metabolic reactions in the latest human metabolic reconstruction, Recon 3D, we compared the atom mappings predicted by six atom mapping algorithms. We also compared these predictions to those obtained by manual curation of atom mappings for over five hundred reactions distributed among all top level Enzyme Commission number classes. Five of the evaluated algorithms had similarly high prediction accuracy of over 91% when compared to manually curated atom mapped reactions. On average, the accuracy of the prediction was highest for reactions catalysed by oxidoreductases and lowest for reactions catalysed by ligases. In addition to prediction accuracy, the algorithms were evaluated on their accessibility, their advanced features, such as the ability to identify equivalent atoms, and their ability to map hydrogen atoms. In addition to prediction accuracy, we found that software accessibility and advanced features were fundamental to the selection of an atom mapping algorithm in practice.

37 INORGANIC, ORGANIC, PHYSICAL, AND ANALYTICAL CH↗

DOE OSTI2024

Efficient First-Order Algorithms for Large-Scale, Non-Smooth Maximum Entropy Models with Application to Wildfire Science

Maximum entropy (MaxEnt) models are a class of statistical models that use the maximum entropy principle to estimate probability distributions from data. Due to the size of modern data sets, MaxEnt models need efficient optimization algorithms to scale well for big data applications. State-of-the-art algorithms for MaxEnt models, however, were not originally designed to handle big data sets; these algorithms either rely on technical devices that may yield unreliable numerical results, scale poorly, or require smoothness assumptions that many practical MaxEnt models lack. In this paper, we present novel optimization algorithms that overcome the shortcomings of state-of-the-art algorithms for training large-scale, non-smooth MaxEnt models. Our proposed first-order algorithms leverage the Kullback–Leibler divergence to train large-scale and non-smooth MaxEnt models efficiently. For MaxEnt models with discrete probability distribution of n elements built from samples, each containing m features, the stepsize parameter estimation and iterations in our algorithms scale on the order of O(mn) operations and can be trivially parallelized. Moreover, the strong ℓ1 convexity of the Kullback–Leibler divergence allows for larger stepsize parameters, thereby speeding up the convergence rate of our algorithms. To illustrate the efficiency of our novel algorithms, we consider the problem of estimating probabilities of fire occurrences as a function of ecological features in the Western US MTBS-Interagency wildfire data set. Our numerical results show that our algorithms outperform the state of the art by one order of magnitude and yield results that agree with physical models of wildfire occurrence and previous statistical analyses of wildfire drivers.

Physics↗

DOE OSTI2014

The identification of filaments on far-infrared and submillimiter images: Morphology, physical conditions and relation with star formation of filamentary structure

Observations of molecular clouds reveal a complex structure, with gas and dust often arranged in filamentary, rather than spherical geometries. The association of pre- and proto-stellar cores with the filaments suggests a direct link with the process of star formation. Any study of the properties of such filaments requires representative samples from different environments for an unbiased detection method. We developed such an approach using the Hessian matrix of a surface-brightness distribution to identify filaments and determine their physical and morphological properties. After testing the method on simulated, but realistic, filaments, we apply the algorithms to column-density maps computed from Herschel observations of the Galactic plane obtained by the Hi-GAL project. We identified ∼500 filaments, in the longitude range of l = 216.°5 to l = 225.°5, with lengths from ∼1 pc up to ∼30 pc and widths between 0.1 pc and 2.5 pc. Average column densities are between 10{sup 20} cm{sup –2} and 10{sup 22} cm{sup –2}. Filaments include the majority of dense material with N{sub H{sub 2}} > 6 × 10{sup 21} cm{sup –2}. We find that the pre- and proto-stellar compact sources already identified in the same region are mostly associated with filaments. However, surface densities in excess of the expected critical values for high-mass star formation are only found on the filaments, indicating that these structures are necessary to channel material into the clumps. Furthermore, we analyze the gravitational stability of filaments and discuss their relationship with star formation.

79 ASTRONOMY AND ASTROPHYSICS↗

DOE OSTI2018

Integrated Transmission and Distribution Systems Restoration with Distributed Generation Scheduling

The self-healing smart grids enable system operators to quickly and efficiently recover transmission and distribution systems from outages and blackouts. The current restoration procedure solves the transmission and distribution system restoration problems separately without considering their impacts on each other, which may prolong the restoration process. However, with the emerging active distribution networks, distributed generators can contribute into the bottom-up restoration strategy. The interaction between the restoration of two interconnected systems should be taken into account. In this paper, a hybrid model of transmission and distribution systems restoration (HTDSR) is proposed by exchanging data of power and voltage between two separate optimization problems. The effectiveness of the HTDSR algorithm is demonstrated through case studies of the integrated IEEE 13-bus distribution network and IEEE 39-bus transmission grid. Simulation results demonstrate that the integrated restoration strategy with optimal scheduling of distributed generation sources can expedite the restoration process.

Distributed generation↗

DOE OSTI2015

SU-E-T-33: A Feasibility-Seeking Algorithm Applied to Planning of Intensity Modulated Proton Therapy: A Proof of Principle Study

Purpose: To investigate the applicability of feasibility-seeking cyclic orthogonal projections to the field of intensity modulated proton therapy (IMPT) inverse planning. Feasibility of constraints only, as opposed to optimization of a merit function, is less demanding algorithmically and holds a promise of parallel computations capability with non-cyclic orthogonal projections algorithms such as string-averaging or block-iterative strategies. Methods: A virtual 2D geometry was designed containing a C-shaped planning target volume (PTV) surrounding an organ at risk (OAR). The geometry was pixelized into 1 mm pixels. Four beams containing a subset of proton pencil beams were simulated in Geant4 to provide the system matrix A whose elements a-ij correspond to the dose delivered to pixel i by a unit intensity pencil beam j. A cyclic orthogonal projections algorithm was applied with the goal of finding a pencil beam intensity distribution that would meet the following dose requirements: D-OAR < 54 Gy and 57 Gy < D-PTV < 64.2 Gy. The cyclic algorithm was based on the concept of orthogonal projections onto half-spaces according to the Agmon-Motzkin-Schoenberg algorithm, also known as ‘ART for inequalities’. Results: The cyclic orthogonal projections algorithm resulted in less than 5% of the PTV pixels and less than 1% of OAR pixels violating their dose constraints, respectively. Because of the abutting OAR-PTV geometry and the realistic modelling of the pencil beam penumbra, complete satisfaction of the dose objectives was not achieved, although this would be a clinically acceptable plan for a meningioma abutting the brainstem, for example. Conclusion: The cyclic orthogonal projections algorithm was demonstrated to be an effective tool for inverse IMPT planning in the 2D test geometry described. We plan to further develop this linear algorithm to be capable of incorporating dose-volume constraints into the feasibility-seeking algorithm.

60 APPLIED LIFE SCIENCES↗

DOE OSTI2012

MixSim : An R Package for Simulating Data to Study Performance of Clustering Algorithms

The R package MixSim is a new tool that allows simulating mixtures of Gaussian distributions with different levels of overlap between mixture components. Pairwise overlap, defined as a sum of two misclassification probabilities, measures the degree of interaction between components and can be readily employed to control the clustering complexity of datasets simulated from mixtures. These datasets can then be used for systematic performance investigation of clustering and finite mixture modeling algorithms. Among other capabilities of MixSim, there are computing the exact overlap for Gaussian mixtures, simulating Gaussian and non-Gaussian data, simulating outliers and noise variables, calculating various measures of agreement between two partitionings, and constructing parallel distribution plots for the graphical display of finite mixture models. All features of the package are illustrated in great detail. The utility of the package is highlighted through a small comparison study of several popular clustering algorithms.

97 MATHEMATICS AND COMPUTING↗

DOE OSTI2025

Intrepid MCMC: Metropolis-Hastings with exploration

In engineering examples, one often encounters the need to sample from unnormalized distributions with complex shapes that may also be implicitly defined through a physical or numerical simulation model, making it computationally expensive to evaluate the associated density function. For such cases, MCMC has proven to be an invaluable tool. Random-walk Metropolis Methods (also known as Metropolis-Hastings (MH)), in particular, are highly popular for their simplicity, flexibility, and ease of implementation. However, most MH algorithms suffer from significant limitations when attempting to sample from distributions with multiple modes (particularly disconnected ones). Here, in this paper, we present Intrepid MCMC - a novel MH scheme that utilizes a simple coordinate transformation to significantly improve the mode-finding ability and convergence rate to the target distribution of random-walk Markov chains while retaining most of the simplicity of the vanilla MH paradigm. Through multiple examples, we showcase the improvement in the performance of Intrepid MCMC over vanilla MH for a wide variety of target distribution shapes. We also provide an analysis of the mixing behavior of the Intrepid Markov chain, as well as the efficiency of our algorithm for increasing dimensions. A thorough discussion is presented on the practical implementation of the Intrepid MCMC algorithm. Finally, its utility is highlighted through a Bayesian parameter inference problem for a two-degree-of-freedom oscillator under free vibration.

97 - MATHEMATICS AND COMPUTING↗

DOE OSTI2018

Impact Studies and Cooperative Voltage Control for High PV Penetration

The drastically increasing penetration of photovoltaic (PV) has posed tremendous challenges in operation, control, and protection in distribution networks. The over-voltage issue is one of major concerns for extremely high PV penetration (e.g. 100%). It is critical to identify the most sensitive locations to high PV penetration and apply effective methods to mitigate the over-voltage issue. This paper introduced a novel greedy search algorithm to locate worst-case scenarios of over-voltage in both distributed and centralized PV configurations, as well as a cooperative voltage control method to mitigate over-voltage. The search algorithm has the computational advantage over existing stochastic approach and provides more insights in impact studies. The cooperative control method relies upon reactive power compensation to converge system voltage to a predefined value within standard limits. Moreover, a clustering strategy is applied to divide the network into several clusters, within which all nodes share information with neighboring nodes following a scalable communication architecture. The control algorithms and communication hierarchies presented in this paper have been implemented into OpenDSS to form the Multi Agent (MA) OpenDSS package, which has been made available to the reader. The effectiveness of developed methods are demonstrated through simulation studies on the IEEE 123-node test feeder under four different load levels.

Cooperative control↗

DOE OSTI2013

The effect of load imbalances on the performance of Monte Carlo algorithms in LWR analysis

A model is developed to predict the impact of particle load imbalances on the performance of domain-decomposed Monte Carlo neutron transport algorithms. Expressions for upper bound performance “penalties” are derived in terms of simple machine characteristics, material characterizations and initial particle distributions. The hope is that these relations can be used to evaluate tradeoffs among different memory decomposition strategies in next generation Monte Carlo codes, and perhaps as a metric for triggering particle redistribution in production codes.

97 MATHEMATICS AND COMPUTING↗

DOE OSTI2012

Plasma density measurements in tungsten wire-array Z-pinches

Measurements of the plasma density profile near the exploding wires in 1 MA tungsten (W) wire-array Z-pinches have been made using calibrated x-ray absorption. As many as 5 x-ray images per pulse were obtained between 65 and 160 ns after the start of the 100 ns rise time current pulse. Measured W ion densities range from above 10{sup 19}/cm{sup 3} close to the wire to {approx}10{sup 17}/cm{sup 3} about 1 mm away from the wire in the plasma stream. After accurate geometrical registration of the individual wires in each successive image in a pulse using the Genetic Algorithm, the temporal evolution of the axial modulation wavelength distribution of the ablation rate from the wires in each array and the global mass-ablation rate as a function of time are presented.

70 PLASMA PHYSICS AND FUSION TECHNOLOGY↗

DOE OSTI2016

Apparent permeability prediction of organic shale with generalized lattice Boltzmann model considering surface diffusion effect

Gas flow in shale is associated with both organic matter (OM) and inorganic matter (IOM) which contain nano-pores ranging in size from a few to hundreds of nano-meters. In addition to the non-continuum effect which leads to an apparent permeability of gas higher than the intrinsic permeability, the surface diffusion of adsorbed gas in organic pores also can influence the apparent permeability through its own transport mechanism. In this study, a generalized lattice Boltzmann model (GLBM) is employed for gas flow through the reconstructed shale matrix consisting of OM and IOM. The Expectation–Maximization (EM) algorithm is used to assign the pore size distribution to each component, and the dusty gas model (DGM) and generalized Maxwell–Stefan model (GMS) are adopted to calculate the apparent permeability accounting for multiple transport mechanisms including viscous flow, Knudsen diffusion and surface diffusion. Effects of pore radius and pressure on permeability of both IOM and OM as well as effects of Langmuir parameters on OM are investigated. The effect of total organic content and distribution on the apparent permeability of the reconstructed shale matrix at different surface diffusivity is also studied. It is found that the influence of pore size and pressure on the apparent permeability of organic matter is affected by the surface diffusion of adsorbed gas. Furthermore, surface diffusion plays a significant role in determining apparent permeability and the velocity distribution of shale matrix.

02 PETROLEUM↗

DOE OSTI2014

Effect of Acuros XB algorithm on monitor units for stereotactic body radiotherapy planning of lung cancer

Stereotactic body radiotherapy (SBRT) is a curative regimen that uses hypofractionated radiation-absorbed dose to achieve a high degree of local control in early stage non–small cell lung cancer (NSCLC). In the presence of heterogeneities, the dose calculation for the lungs becomes challenging. We have evaluated the dosimetric effect of the recently introduced advanced dose-calculation algorithm, Acuros XB (AXB), for SBRT of NSCLC. A total of 97 patients with early-stage lung cancer who underwent SBRT at our cancer center during last 4 years were included. Initial clinical plans were created in Aria Eclipse version 8.9 or prior, using 6 to 10 fields with 6-MV beams, and dose was calculated using the anisotropic analytic algorithm (AAA) as implemented in Eclipse treatment planning system. The clinical plans were recalculated in Aria Eclipse 11.0.21 using both AAA and AXB algorithms. Both sets of plans were normalized to the same prescription point at the center of mass of the target. A secondary monitor unit (MU) calculation was performed using commercial program RadCalc for all of the fields. For the planning target volumes ranging from 19 to 375 cm{sup 3}, a comparison of MUs was performed for both set of algorithms on field and plan basis. In total, variation of MUs for 677 treatment fields was investigated in terms of equivalent depth and the equivalent square of the field. Overall, MUs required by AXB to deliver the prescribed dose are on an average 2% higher than AAA. Using a 2-tailed paired t-test, the MUs from the 2 algorithms were found to be significantly different (p < 0.001). The secondary independent MU calculator RadCalc underestimates the required MUs (on an average by 4% to 5%) in the lung relative to either of the 2 dose algorithms.

62 RADIOLOGY AND NUCLEAR MEDICINE↗

DOE OSTI2020

Structural evolution of two-dimensional silicates using a “bond-switching” algorithm

Silicates are the most abundant materials in the earth's crust. In recent years, two-dimensional (2D) versions of them grown on metal supports (known as bilayer silicates) have allowed their study in detail down to the atomic scale. These structures are self-containing. Furthermore, they are not covalently bound to the metal support but interact with it through van der Waals forces. Like their three-dimensional counterparts, the 2D-silicates can form both crystalline and vitreous structures. Furthermore, the interconversion between vitreous to crystalline structures has been experimentally observed at the nanoscale. While theoretical work has been carried out to try to understand these transformations, a limitation for ab initio methods, and even molecular dynamics methods, is the computational cost of studying large systems and long timescales. In this work, we present a simple and computationally inexpensive approach, that can be used to represent the evolution of bilayer silicates using a bond-switching algorithm. This approach allows reaching equilibrium ring size distributions as a function of a parameter that can be related to the ratio between temperature and the energy required for the bond-switching event. The ring size distributions are compared to experimental data available in the literature.

77 NANOSCIENCE AND NANOTECHNOLOGY↗

DOE OSTI2019

Incorporating energy storage and user experience in isolated microgrid dispatch using a multi-objective model

In order to coordinate multiple different scheduling objectives from the perspectives of economy, environment, and users, a practical multi-objective dynamic optimal dispatch model incorporating energy storage and user experience is proposed for isolated microgrids. In this model, besides microturbine units, energy storage is employed to provide spinning reserve services for microgirds; and furthermore, from the perspective of demand side management, a consumer satisfaction indicator is developed to measure the quality of user experience. A two-step solution methodology incorporating multi-objective optimisation and decision analysis is put forward to address this model. First, a powerful heuristic optimisation algorithm, called the -dominance based evolutionary algorithm, is used to find a well-distributed set of Pareto-optimal solutions of the problem. Thereby, the best compromise solutions are identified from the entire solutions with the use of decision analysis by integrating fuzzy C-means clustering and grey relation projection. The simulation results on the modified Oak Ridge National Laboratory Distributed Energy Control and Communication lab microgrid test system demonstrate the effectiveness of the proposed approach.

Li, Yang↗