Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “weighted independent set”

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 19 records
All sourcesNASA NTRSDOE OSTI
DOE OSTI2012

Parallel Algorithms for Graph Optimization Using Tree Decompositions

Although many $\cal{NP}$-hard graph optimization problems can be solved in polynomial time on graphs of bounded tree-width, the adoption of these techniques into mainstream scientific computation has been limited due to the high memory requirements of the necessary dynamic programming tables and excessive runtimes of sequential implementations. This work addresses both challenges by proposing a set of new parallel algorithms for all steps of a tree decomposition-based approach to solve the maximum weighted independent set problem. A hybrid OpenMP/MPI implementation includes a highly scalable parallel dynamic programming algorithm leveraging the MADNESS task-based runtime, and computational results demonstrate scaling. This work enables a significant expansion of the scale of graphs on which exact solutions to maximum weighted independent set can be obtained, and forms a framework for solving additional graph optimization problems with similar techniques.

99 GENERAL AND MISCELLANEOUS↗
DOE OSTI2013

Parallel Algorithms for Graph Optimization using Tree Decompositions

Although many NP-hard graph optimization problems can be solved in polynomial time on graphs of bounded tree-width, the adoption of these techniques into mainstream scientific computation has been limited due to the high memory requirements of required dynamic programming tables and excessive running times of sequential implementations. This work addresses both challenges by proposing a set of new parallel algorithms for all steps of a tree-decomposition based approach to solve maximum weighted independent set. A hybrid OpenMP/MPI implementation includes a highly scalable parallel dynamic programming algorithm leveraging the MADNESS task-based runtime, and computational results demonstrate scaling. This work enables a significant expansion of the scale of graphs on which exact solutions to maximum weighted independent set can be obtained, and forms a framework for solving additional graph optimization problems with similar techniques.

Weerapurage, Dinesh P↗
DOE OSTI2012

INDDGO: Integrated Network Decomposition & Dynamic programming for Graph Optimization

It is well-known that dynamic programming algorithms can utilize tree decompositions to provide a way to solve some NP -hard problems on graphs where the complexity is polynomial in the number of nodes and edges in the graph, but exponential in the width of the underlying tree decomposition. However, there has been relatively little computational work done to determine the practical utility of such dynamic programming algorithms. We have developed software to construct tree decompositions using various heuristics and have created a fast, memory-efficient dynamic programming implementation for solving maximum weighted independent set. We describe our software and the algorithms we have implemented, focusing on memory saving techniques for the dynamic programming. We compare the running time and memory usage of our implementation with other techniques for solving maximum weighted independent set, including a commercial integer programming solver and a semi-definite programming solver. Our results indicate that it is possible to solve some instances where the underlying decomposition has width much larger than suggested by the literature. For certain types of problems, our dynamic programming code runs several times faster than these other methods.

Groër, Christopher S.↗
DOE OSTI2022

Network-Level Traffic Signal Cooperation: A Higher-Order Conflict Graph Approach

Traffic signal control and cooperation are extremely important to alleviate traffic congestion in a large traffic network. This study develops a higher-order conflict graph approach for network-wide traffic signal control and cooperation. A conflict graph is applied to model the traffic signal configurations, which identifies the conflict and unconflicted movements for each intersection. In conflict graph, the node represents each movement. The weight of each node can be defined as traffic volume, queue length, fuel consumption, or any weighted combinations of these measurements. The calculation of the optimal green light duration and green light sequence (for different movements) is equivalent to sequentially finding the maximum weight independent set (MWIS) in the conflict graph. The conflict graph also provides a uniform and efficient way to connect traffic signal operations among nearby intersections spatially. Then, we introduced the concept of the k -th order neighborhood to model the degree of connectivity between each movement to the movements at upstream or downstream intersections. The weight of each node in the higher-order conflict graph not only represents its own congestion level, but also relates to the traffic conditions of nearby intersections. Through this approach, the cooperation of multiple intersections can be realized by incorporating their spatial connectivity into conflict graph and solving the MWIS problem. A simulation network is built in SUMO to test the effectiveness of the proposed method. Results suggested that the proposed model outperformed other state-of-the-art signal control methods. Also, the scheme maintains good performance under varying traffic demands.

42 ENGINEERING↗
DOE OSTI2024

Modeling injection-induced fault slip using long short-term memory networks

Stress changes due to changes in fluid pressure and temperature in a faulted formation may lead to the opening/shearing of the fault. This can be due to subsurface (geo)engineering activities such as fluid injections and geologic disposal of nuclear waste. Such activities are expected to rise in the future making it necessary to assess their short- and long-term safety. Here, a new machine learning (ML) approach to model pore pressure and fault displacements in response to high-pressure fluid injection cycles is developed. The focus is on fault behavior near the injection borehole. To capture the temporal dependencies in the data, long short-term memory (LSTM) networks are utilized. To prevent error accumulation within the forecast window, four critical measures to train a robust LSTM model for predicting fault response are highlighted: (i) setting an appropriate value of LSTM lag, (ii) calibrating the LSTM cell dimension, (iii) learning rate reduction during weight optimization, and (iv) not adopting an independent injection cycle as a validation set. Several numerical experiments were conducted, which demonstrated that the ML model can capture peaks in pressure and associated fault displacement that accompany an increase in fluid injection. The model also captured the decay in pressure and displacement during the injection shut-in period. Further, the ability of an ML model to highlight key changes in fault hydromechanical activation processes was investigated, which shows that ML can be used to monitor risk of fault activation and leakage during high pressure fluid injections.

58 GEOSCIENCES↗
DOE OSTI2018

Bayesian Static Parameter Estimation for Partially Observed Diffusions via Multilevel Monte Carlo

In this article we consider static Bayesian parameter estimation for partially observed diffusions that are discretely observed. We work under the assumption that one must resort to discretizing the underlying diffusion process, for instance, using the Euler--Maruyama method. Given this assumption, we show how one can use Markov chain Monte Carlo (MCMC) and particularly particle MCMC [C. Andrieu, A. Doucet, and R. Holenstein, J. R. Stat. Soc. Ser. B Stat. Methodol., 72 (2010), 269--342] to implement a new approximation of the multilevel (ML) Monte Carlo (MC) collapsing sum identity. Our approach comprises constructing an approximate coupling of the posterior density of the joint distribution over parameter and hidden variables at two different discretization levels and then correcting by an importance sampling method. The variance of the weights are independent of the length of the observed data set. The utility of such a method is that, for a prescribed level of mean square error, the cost of this MLMC method is provably less than i.i.d. sampling from the posterior associated to the most precise discretization. However the method here comprises using only known and efficient simulation methodologies. Finally, the theoretical results are illustrated by inference of the parameters of two prototypical processes given noisy partial observations of the process: the first is an Ornstein--Uhlenbeck process and the second is a more general Langevin equation.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2014

Seismic Modeling Workshop - Joint inversion [Slides]

Why joint inversion? It enables spanning spatial and data scales! Multiple benefits: Different data sets have different spatial coverage and resolution. “Standard” geophysical models are developed only to fit one type of data. Different data types have different strengths. Multiple challenges: Deal with different data bandwidths. Design responsive misfit norms; relative weighting of data sets. Make assumptions to model the different data; relationships between independent data sets.

58 GEOSCIENCES↗
DOE OSTI2021

Improving probabilistic infectious disease forecasting through coherence

With an estimated $10.4 billion in medical costs and 31.4 million outpatient visits each year, influenza poses a serious burden of disease in the United States. To provide insights and advance warning into the spread of influenza, the U.S. Centers for Disease Control and Prevention (CDC) runs a challenge for forecasting weighted influenza-like illness (wILI) at the national and regional level. Many models produce independent forecasts for each geographical unit, ignoring the constraint that the national wILI is a weighted sum of regional wILI, where the weights correspond to the population size of the region. We propose a novel algorithm that transforms a set of independent forecast distributions to obey this constraint, which we refer to as probabilistically coherent. Enforcing probabilistic coherence led to an increase in forecast skill for 79% of the models we tested over multiple flu seasons, highlighting the importance of respecting the forecasting system’s geographical hierarchy.

59 BASIC BIOLOGICAL SCIENCES↗
DOE OSTI2026

Online LIBS–ML Framework for Dynamic Characterization of Heterogeneous Waste-Derived Gasification Feedstocks

LIBS−ML framework for real time feedstock characterization during continuous conveyor transport Heterogeneous waste derived feedstocks (e.g., waste coal, biomass and blends) introduce rapid variability in heating value and ash chemistry that affect gasifier operation, yet conventional laboratory characterization techniques are too slow to support proactive control. To address this gap, this study reports on an online, in situ, dynamic characterization framework that couple’s laser-induced breakdown spectroscopy (LIBS) with leakage safe machine learning (ML) regression to deliver real time, decision quality predictions of gasifier relevant properties. A controlled sample matrix spanning two different waste coals, two different biomasses, and engineered blends under two particle size conditions were constructed and benchmarked using standardized laboratory analyses for proximate/ultimate properties and ash composition. LIBS spectra were acquired dynamically as material flowed on a conveyor belt, using high energy 1064 nm laser ablation and shot averaging to improve repeatability and precision. Supervised regression models (multi layer perceptron (MLP) /artificial neural network (ANN), random forest (RF), and support vector regression (SVR)) and an optimized weighted ensemble were trained on emission line feature sets using nested cross validation with Bayesian hyperparameter tuning and validated against an independent hold out set. The proposed LIBS−ML workflow achieves near laboratory predictive fidelity across parametric targets (including higher heating value (HHV), ash content, fixed carbon, sulfur, major ash forming oxides, and initial deformation temperature (IDT)), with the weighted ensemble providing a robust default predictor under dynamic measurement conditions. These results demonstrate a practical pathway for real time feedstock characterization that can enable feedforward adjustments and more resilient gasifier operation for variable quality waste derived fuels.

Biomass↗
NASA NTRS1993

Integrated fiber optic probe for dynamic light scattering

An integrated fiber optic probe, comprising a monomode optical fiber fusion spliced to a short length of a graded-index multimode fiber, is fabricated for use as a coherent receiver in dynamic light scattering. The multimode fiber is cleaved to provide a gradient-index fiber lens with a focal length of 125 microns and an f-number close to unity. An integrated fiber receiver is used to measure the intensity-intensity autocorrelation data from a 0.05 percent by weight concentration of an aqueous suspension of polystyrene latex spheres. Analysis of 100 independent data sets indicates that the particle size can be recovered with an accuracy of +/- 1 percent.

Dhadwal, Harbans S.↗
DOE OSTI2017

Halo-independence with quantified maximum entropy at DAMA/LIBRA

Using the DAMA/LIBRA anomaly as an example, we formalise the notion of halo-independence in the context of Bayesian statistics and quantified maximum entropy. We consider an infinite set of possible profiles, weighted by an entropic prior and constrained by a likelihood describing noisy measurements of modulated moments by DAMA/LIBRA. Assuming an isotropic dark matter (DM) profile in the galactic rest frame, we find the most plausible DM profiles and predictions for unmodulated signal rates at DAMA/LIBRA. The entropic prior contains an a priori unknown regularisation factor, β, that describes the strength of our conviction that the profile is approximately Maxwellian. By varying β, we smoothly interpolate between a halo-independent and a halo-dependent analysis, thus exploring the impact of prior information about the DM profile.

79 ASTRONOMY AND ASTROPHYSICS↗
NASA NTRSDate not supplied

Uncertainty Estimates for Fitting Zernike Polynomials to Discrete Data

Zernike polynomials are a widely used metric in modern optical analysis. They conveniently represent surfaces as a series of weighted terms corresponding to various optical aberrations. Ideally, each term is independent of others in the series, but Zernike polynomials lose this property when working with sets of discrete data. This gives rise to uncertainty in each polynomial’s actual contribution and affects metrology and simulation estimates of their relative weights. Several factors influencing these estimates are the number and arrangement of sample locations, the method for calculating the weights, and the total number of Zernike terms used in the calculation. Discussed is the uncertainty associated with linear regression using random sampling. Other topics reviewed are complex Zernike polynomials and vector spaces of functions.

Zernike Polynomials↗
DOE OSTI2025

Modeling inter‐reader variability in clinical target volume delineation for soft tissue sarcomas using diffusion model

Abstract Background Accurate delineation of the clinical target volume (CTV) is essential in the radiotherapy treatment of soft tissue sarcomas. However, this process is subject to inter‐reader variability due to the need for clinical assessment of risk and extent of potential microscopic spread. This can lead to inconsistencies in treatment planning, potentially impacting treatment outcomes. Most existing automatic CTV delineation methods do not account for this variability and can only generate a single CTV for each case. Purpose This study aims to develop a deep learning‐based technique to generate multiple CTV contours for each case, simulating the inter‐reader variability in the clinical practice. Methods We employed a publicly available dataset consisting of fluorodeoxyglucose positron emission tomography (FDG‐PET), x‐ray computed tomography (CT), and pre‐contrast T1‐weighted magnetic resonance imaging (MRI) scans from 51 patients with soft tissue sarcoma, along with an independent validation set containing five additional patients. An experienced reader drew a contour of the gross tumor volume (GTV) for each patient based on multi‐modality images. Subsequently, two additional readers, together with the first one, were responsible for contouring three CTVs in total based on the GTV. We developed a diffusion model‐based deep learning method that is capable of generating arbitrary number of different and plausible CTVs to mimic the inter‐reader variability in CTV delineation. The proposed model incorporates a separate encoder to extract features from the GTV masks, leveraging the critical role of GTV information in accurate CTV delineation. Results The proposed diffusion model demonstrated superior performance with the highest Dice Index (0.902 compared to values below 0.881 for state‐of‐the‐art models) and the best generalized energy distance (GED) (0.209 compared to values exceeding 0.221 for state‐of‐the‐art models). It also achieved the second‐highest recall and precision metrics among the compared ambiguous image segmentation models. Results from both datasets exhibited consistent trends, reinforcing the reliability of our findings. Additionally, ablation studies exploring different model structures and input configurations highlighted the significance of incorporating prior GTV information for accurate CTV delineation. Conclusions The proposed diffusion model successfully generates multiple plausible CTV contours for soft tissue sarcomas, effectively capturing inter‐reader variability in CTV delineation.

Dong, Yafei [Yale Biomedical Imaging Institute Yal↗
DOE OSTI2016

The diffusion and conduction of lithium in poly(ethylene oxide)-based sulfonate ionomers

Pulsed field gradient nuclear magnetic resonance spectroscopy and dielectric relaxation spectroscopy have been utilized to investigate lithium dynamics within poly(ethylene oxide) (PEO)-based lithium sulfonate ionomers of varying ion content. The ion content is set by the fraction of sulfonated phthalates and the molecular weight of the PEO spacer, both of which can be varied independently. The molecular level dynamics of the ionomers are dominated by either Vogel-Fulcher-Tammann or Arrhenius behavior depending on ion content, spacer length, temperature, and degree of ionic aggregation. In these ionomers the main determinants of the self-diffusion of lithium and the observed conductivities are the ion content and ionic states of the lithium ion, which are profoundly affected by the interactions of the lithium ions with the ether oxygens of the polymer. Since many lithium ions move by segmental polymer motion in the ion pair state, their diffusion is significantly larger than that estimated from conductivity using the Nernst-Einstein equation.

LaFemina, Nikki H.↗
NASA NTRS1972

Corrections to star catalogues from satellite observations.

Theoretical investigation of the possibility of obtaining systematic corrections to star catalogs from observations of artificial satellites. A model is established to represent the system of equations formed when such corrections are determined simultaneously with corrections to the geocentric position of the observer. An analytical expression for the covariance matrix is set up for the two-dimensional (planar) case. The resulting correlations and weights are discussed. Since this method presents an independent way of obtaining the systematic errors in star catalogs, apart from the orientation to the equatorial system, it is related to the measurement of all quantities which depend on star positions. This institutes a completely new principle of obtaining systematic corrections to star catalogs. It is based not on rotation, but on comparing the angle subtended at the satellite by two stars to the angle subtended at the satellite by two points on the surface of the earth.

Williams, C. A.↗
DOE OSTI2015

SU-E-T-208: Comparison of MR Image Quality of Various Brachytherapy Applicators for Cervical Cancer

Purpose: To compare the quality of Magnetic Resonance (MR) images of a recently-proposed novel direction-modulated brachytherapy (DMBT) tandem applicator against two conventional clinical applicators, using the current MRI clinical protocol. Methods: Three tandem applicators were compared: (1) tungsten-based DMBT applicator, (2) conventional plastic applicator and (3) conventional stainless steel applicator. Physical dimensions were 5.4, 3.8 and 3.2 for tandems (1), (2) and (3), respectively. Each applicator was placed in the same water-phantom and independently scanned using the same parameters and coil settings on a 1.5 T 450w GE scanner. Images were acquired using T2-weighted turbo-spin-echo (TSE) with 8-channel body coil. Acquisition parameters were TR/TE =7000/108 ms; acquisition matrix = 320 x 256; 30 slices with 4 mm thickness and 0.5 gap; pixel bandwidth = 122 Hz and voxel size = 0.5 x 0.625 mm2 and number of excitations (NEX) = 4. Multiple acquisitions were obtained in para-sagittal and para-axial views (with respect to the tandem axis) for each applicator. Diameters of the tandem were measured at multiple angles and multiple locations and compared to the physical dimensions of the corresponding tandems. Results: Minimal susceptibility artifact was observed with the DMBT and the plastic tandems. The stainless steel tandem produced significantly larger artifact than the first two tandems. The average diameter of the DMBT applicator measured 5.94 ± 0.3 mm. The average diameter of the plastic tandem measured 3.9 ± 0.1 mm. The maximum extent of artifact was 1.5 mm and 0.7 mm for DMBT and plastic tandems, respectively. The susceptibility artifact induced by the stainless steel tandem prevented the measurement of its diameter, and the edges of the tandem could not be identified in any acquisition. Conclusion: This work demonstrated that the plastic and the tungsten-based DMBT tandem applicators are both suitable for MRI-guided brachytherapy of cervical cancer.

60 APPLIED LIFE SCIENCES↗
NASA NTRS1980

The use of prior probabilities in maximum likelihood classification of remotely sensed data

Possibilities for the improvement of classification accuracies by the use of prior information about the expected distribution of classes in the maximum likelihood classification of remote sensing data are examined. The modification of the maximum likelihood decision rule to take into account one or several sets of probabilities for the occurrence of classes which probabilities are based on independent knowledge of the area surveyed is demonstrated. It is then shown that the use of prior probabilities is sufficiently versatile so as to allow the prior weighting of output classes based on their anticipated sizes as well as the merging of continuously varying measurements with discrete collateral information data sets and the construction of time-sequential classification systems in which an earlier classification modifies the outcome of a latter one.

Strahler, A. H.↗
NASA NTRS2009

NDARC NASA Design and Analysis of Rotorcraft

The NASA Design and Analysis of Rotorcraft (NDARC) software is an aircraft system analysis tool intended to support both conceptual design efforts and technology impact assessments. The principal tasks are to design (or size) a rotorcraft to meet specified requirements, including vertical takeoff and landing (VTOL) operation, and then analyze the performance of the aircraft for a set of conditions. For broad and lasting utility, it is important that the code have the capability to model general rotorcraft configurations, and estimate the performance and weights of advanced rotor concepts. The architecture of the NDARC code accommodates configuration flexibility; a hierarchy of models; and ultimately multidisciplinary design, analysis, and optimization. Initially the software is implemented with lowfidelity models, typically appropriate for the conceptual design environment. An NDARC job consists of one or more cases, each case optionally performing design and analysis tasks. The design task involves sizing the rotorcraft to satisfy specified design conditions and missions. The analysis tasks can include off-design mission performance calculation, flight performance calculation for point operating conditions, and generation of subsystem or component performance maps. For analysis tasks, the aircraft description can come from the sizing task, from a previous case or a previous NDARC job, or be independently generated (typically the description of an existing aircraft). The aircraft consists of a set of components, including fuselage, rotors, wings, tails, and propulsion. For each component, attributes such as performance, drag, and weight can be calculated; and the aircraft attributes are obtained from the sum of the component attributes. Description and analysis of conventional rotorcraft configurations is facilitated, while retaining the capability to model novel and advanced concepts. Specific rotorcraft configurations considered are single main-rotor and tailrotor helicopter; tandem helicopter; coaxial helicopter; and tiltrotors. The architecture of the code accommodates addition of new or higher-fidelity attribute models for a component, as well as addition of new components.

Johnson, Wayne R.↗