Search NASA⌕ Search

SEARCH · Search NASA

Results for “partitioning 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 757 records · Page 42

Performance Analysis of Speculative Parallel Adaptive Local Timestepping for Conservation Laws

Stable simulation of conservation laws, such as those used to model fluid dynamics and plasma physics applications, requires the satisfaction of the so-called Courant-Friedrichs-Lewy condition. By allowing regions of the mesh to advance with different timesteps that locally satisfy this stability constraint, significant work reduction can be attained when compared to a time integration scheme using a single timestep size. However, parallelizing this algorithm presents considerable difficulty. Since the stability condition depends on the state of the system, dependencies become dynamic and potentially non-local. In this article, we present an adaptive local timestepping algorithm using an optimistic (Timewarp-based) parallel discrete event simulation. We introduce waiting heuristics to limit misspeculation and a semi-static load balancing scheme to eliminate load imbalance as parts of the mesh require finer or coarser timesteps. Last, we outline an interface for separating the physics of the specific conservation law from the temporal integration allowing for productive adoption of our proposed algorithm. We present a misspeculation study for three conservation laws, demonstrating both the productivity of the local timestepping API, for which 74% of the lines of code are reused across different conservation laws, and the robustness of the waiting heuristics—at most 1.5% of element updates are rolled back. Our performance studies demonstrate up to a 2.8× speedup versus a baseline unoptimized local timestepping approach, a 4x improvement in per-node throughput compared to an MPI parallelization of synchronous timestepping, and scalability up to 3,072 cores on NERSC’s Cori Haswell partition.

97 MATHEMATICS AND COMPUTING↗

Reliability considerations for the total strain range version of strainrange partitioning

A proposed total strainrange version of strainrange partitioning (SRP) to enhance the manner in which SRP is applied to life prediction is considered with emphasis on how advanced reliability technology can be applied to perform risk analysis and to derive safety check expressions. Uncertainties existing in the design factors associated with life prediction of a component which experiences the combined effects of creep and fatigue can be identified. Examples illustrate how reliability analyses of such a component can be performed when all design factors in the SRP model are random variables reflecting these uncertainties. The Rackwitz-Fiessler and Wu algorithms are used and estimates of the safety index and the probablity of failure are demonstrated for a SRP problem. Methods of analysis of creep-fatigue data with emphasis on procedures for producing synoptic statistics are presented. An attempt to demonstrate the importance of the contribution of the uncertainties associated with small sample sizes (fatique data) to risk estimates is discussed. The procedure for deriving a safety check expression for possible use in a design criteria document is presented.

Wirsching, P. H.↗

Formal Verification of the Runway Safety Monitor

The Runway Safety Monitor (RSM) designed by Lockheed Martin is part of NASA's effort to reduce runway accidents. We developed a Petri net model of the RSM protocol and used the model checking functions of our tool SMART to investigate a number of safety properties in RSM. To mitigate the impact of state-space explosion, we built a highly discretized model of the system, obtained by partitioning the monitored runway zone into a grid of smaller volumes and by considering scenarios involving only two aircraft. The model also assumes that there are no communication failures, such as bad input from radar or lack of incoming data, thus it relies on a consistent view of reality by all participants. In spite of these simplifications, we were able to expose potential problems in the RSM conceptual design. Our findings were forwarded to the design engineers, who undertook corrective action. Additionally, the results stress the efficiency attained by the new model checking algorithms implemented in SMART, and demonstrate their applicability to real-world systems.

Siminiceanu, Radu↗

Improvement of Radiative Fluxes for the CERES FluxByCldTyp Data Product Based on Machine Learning Technique

The NASA Clouds and the Earth's Radiant Energy System (CERES) product provides over 20 years of accurately observed top-of-the-atmosphere and surface flux data for climate studies. The interaction between clouds and radiation interaction is a key factor that dominate climate feedbacks but is not well understood. To further advance our understanding of the cloud-radiation interaction, a new CERES FluxByCldTyp (FBCT) product has been developed that contains radiative fluxes by cloud-type, which can provide more stringent constraints when validating models. The FBCT product utilizes Moderate Resolution Imaging Spectroradiometer (MODIS) narrow-band (NB) imager channel radiances partitioned by cloud-type within a CERES footprint to estimate their broadband fluxes. The MODIS multi-channel derived broadband fluxes were compared with the CERES observed footprint fluxes and were found to be within 1% and 2.5% for LW and SW, respectively, as well as being mostly free of cloud property dependencies. The FBCT all-sky and clear-sky monthly averaged fluxes were found to be consistent with the CERES SSF1deg product. This study takes advantage of recent progress in machine learning (ML) field by applying deep neural network algorithm to improve fluxes based on MODIS NB radiances. The preliminary study shows ML produce are an improvement over the current FBCT Edition 4 NB2BB algorithm. Furthermore, unlike Ed4 NB2BB, the new ML method convert NB radiances directly to broadband fluxes. For future Ed5, new NB radiances are proposed and used by ML to improve fluxes calculation. Preliminary results show significant LW improvement.

Sun, Moguo↗

Productivity, Respiration, and Light-Response Parameters of World Grassland and Agroecosystems Derived From Flux-Tower Measurements

Grasslands and agroecosystems occupy one-third of the terrestrial area, but their contribution to the global carbon cycle remains uncertain. We used a set of 316 site-years of CO2 exchange measurements to quantify gross primary productivity, respiration, and light-response parameters of grasslands, shrublands/savanna, wetlands, and cropland ecosystems worldwide. We analyzed data from 72 global flux-tower sites partitioned into gross photosynthesis and ecosystem respiration with the use of the light- response method (Gilmanov, T. G., D. A. Johnson, and N. Z. Saliendra. 2003. Growing season CO2 fluxes in a sagebrush- steppe ecosystem in Idaho: Bowen ratio/energy balance measurements and modeling. Basic and Applied Ecology 4:167–183) from the RANGEFLUX and WORLDGRASSAGRIFLUX data sets supplemented by 46 sites from the FLUXNET La Thuile data set partitioned with the use of the temperature-response method (Reichstein, M., E. Falge, D. Baldocchi, D. Papale, R. Valentini, M. Aubinet, P. Berbigier, C. Bernhofer, N. Buchmann, M. Falk, T. Gilmanov, A. Granier, T. Grunwald, K. Havrankova, D. Janous, A. Knohl, T. Laurela, A. Lohila, D. Loustau, G. Matteucci, T. Meyers, F. Miglietta, J. M. Ourcival, D. Perrin, J. Pumpanen, S. Rambal, E. Rotenberg, M. Sanz, J. Tenhunen, G. Seufert, F. Vaccari, T. Vesala, and D. Yakir. 2005. On the separation of net ecosystem exchange into assimilation and ecosystem respiration: review and improved algorithm. Global Change Biology 11:1424–1439). Maximum values of the quantum yield (a 5 75 mmol ? mol21), photosynthetic capacity (Amax 5 3.4 mg CO2 ? m22 ? s21), gross photosynthesis (Pg,max 5 116 g CO2 ? m22 ? d21), and ecological light-use efficiency (eecol 5 59 mmol ? mol21) of managed grasslands and high-production croplands exceeded those of most forest ecosystems, indicating the potential of nonforest ecosystems for uptake of atmospheric CO2. Maximum values of gross primary production (8 600 g CO2 ? m22 ? yr21), total ecosystem respiration (7 900 g CO2 ? m22 ? yr21), and net CO2 exchange (2 400 g CO2 ? m22 ? yr21) were observed for intensively managed grasslands and high-yield crops, and are comparable to or higher than those for forest ecosystems, excluding some tropical forests. On average, 80% of the nonforest sites were apparent sinks for atmospheric CO2, with mean net uptake of 700 g CO2 ? m22 ? yr21 for intensive grasslands and 933 g CO2 ? m22 ? d21 for croplands. However, part of these apparent sinks is accumulated in crops and forage, which are carbon pools that are harvested, transported, and decomposed off site. Therefore, although agricultural fields may be predominantly sinks for atmospheric CO2, this does not imply that they are necessarily increasing their carbon stock.

54 ENVIRONMENTAL SCIENCES↗

Automatic off-body overset adaptive Cartesian mesh method based on an octree approach

This paper describes a method for generating adaptive structured Cartesian grids within a near-body/off-body mesh partitioning framework for the flow simulation around complex geometries. The off-body Cartesian mesh generation derives from an octree structure, assuming each octree leaf node defines a structured Cartesian block. This enables one to take into account the large scale discrepancies in terms of resolution between the different bodies involved in the simulation, with minimum memory requirements. Two different conversions from the octree to Cartesian grids are proposed: the first one generates Adaptive Mesh Refinement (AMR) type grid systems, and the second one generates abutting or minimally overlapping Cartesian grid set. We also introduce an algorithm to control the number of points at each adaptation, that automatically determines relevant values of the refinement indicator driving the grid refinement and coarsening. An application to a wing tip vortex computation assesses the capability of the method to capture accurately the flow features.

97 MATHEMATICS AND COMPUTING↗

Intelligent Experiments through Real-Time AI: Fast Data Processing and Autonomous Detector Control for High-Energy Nuclear Experiments

The aim of this project is to develop software and hardware for fast real-time data processing and autonomous detector control and calibration for the sPHENIX and the future EIC experiments. Below summarizes Georgia Tech team efforts in the past year: 1. We developed a real-time clustering algorithm and FPGA-based pipeline architecture for processing fired pixel data from ALPIDE sensors in sPHENIX experiments. Our Columnar Clustering Co-Design introduces a hardware-aware, stream-friendly approach that segments pixel data by column pairs using a Column Pair Clustering (CPC) strategy, followed by Cluster Stitching to merge adjacent subclusters. Implemented in Vitis HLS, the pipeline comprises five stages—read-in, subclustering, stitching, analysis, and write-out—connected by tagged HLS streams with custom end-of-event signaling for robust synchronization. We designed a pipelined dataflow model optimized for throughput, low latency, and minimal buffering, enabling scalable clustering across events of arbitrary size. Our system maintains spatial precision via center-of-mass and shape key extraction and efficiently handles edge cases such as fragmented or nested clusters. Compared against DBSCAN in both software and hardware, our approach demonstrates competitive performance under FPGA constraints. 2. We also conducted a comprehensive algorithm-to-hardware co-design of connected component analysis tailored for sPHENIX experiments, focusing on real-time, low-latency processing using FPGAs and High-Level Synthesis (HLS). Starting from a Python-based particle tracking pipeline, the team translated the core logic—graph traversal via DFS and Union-Find—into an HLS-compatible C++ model, replacing dynamic memory and recursion with static arrays and pipelined control flow. The final design includes a fully streamed and dataflow-compatible Union-Find kernel optimized across five iterations, incorporating loop pipelining, array partitioning, AXI/FIFO interface tuning, and function flattening. Experimental results show up to 14.8× speedup over the CPU baseline, reducing per-graph latency to 1.58 μs and demonstrating strong resource efficiency with only ~7k LUTs and zero BRAM usage. The design maintains functional correctness against the Python reference using a Python-based C-simulation framework and Mean Squared Error metrics. This work validates the potential of HLS-driven FPGA designs for edge-level HEP data acquisition, laying a scalable foundation for future integration with real-time detector pipelines and multi-graph processing systems.

73 NUCLEAR PHYSICS AND RADIATION PHYSICS↗

Validation of Satellite-Based Precipitation Products from TRMM to GPM

The global precipitation measurement mission (GPM) has been in operation for seven years and continues to provide a vast quantity of global precipitation data at finer temporospatial resolutions with improved accuracy and coverage. GPM’s signature algorithm, the integrated multisatellite retrievals for GPM (IMERG) is a next-generation of precipitation product expected for wide variety of research and operational applications. This study evaluates the latest version (V06B) of IMERG and its predecessor, the tropical rainfall measuring mission (TRMM) multisatellite precipitation (TMPA) 3B42 (V7) using ground-based and gauge-corrected multiradar multisensor system (MRMS) precipitation products over the conterminous United States (CONUS). The spatial distributions of all products are analyzed. The error characteristics are further examined for 3B42 and IMERG in winter and summer by an error decomposition approach, which partitions total bias into hit bias, biases due to missed precipitation and false precipitation. The volumetric and categorical statistical metrics are used to quantitatively evaluate the performance of the two satellite-based products. All products show a similar precipitation climatology with some regional differences. The two satellite-based products perform better in the eastern CONUS than in the mountainous Western CONUS. The evaluation demonstrates the clear improvement in IMERG precipitation product in comparison with its predecessor 3B42, especially in reducing missed precipitation in winter and summer, and hit bias in winter, resulting in better performance in capturing lighter and heavier precipitation.

MRMS↗

CERES FluxByCldTyp NB2BB Fluxes Improvement based on Deep Neural Network

The NASA Clouds and the Earth's Radiant Energy System (CERES) product provides over 20 years of accurately observed top-of-the-atmosphere (TOA) and surface flux data record for climate monitoring and diagnostic studies. The interaction between clouds and radiation interaction is a key factor that dominate climate feedbacks but is not well understood. To further advance our understanding of the cloud-radiation interaction, a new CERES FluxByCldTyp (FBCT) product has been developed that contains radiative fluxes by cloud-type, which can provide more stringent constraints when validating models and reveal more insight into the interactions between clouds and climate. For CERES partly cloudy and multiple cloud-type footprints, the FBCT product utilizes Moderate Resolution Imaging Spectroradiometer (MODIS) narrow-band (NB) imager channel radiances partitioned by cloud-type within a CERES footprint to estimate the cloud-type broadband fluxes. The MODIS multi-channel derived broadband fluxes were compared with the CERES observed footprint fluxes and were found to be within 1% and 2.5% for LW and SW, respectively, as well as being mostly free of cloud property dependencies. The FBCT all-sky and clear-sky monthly averaged fluxes were found to be consistent with the CERES SSF1deg product. This study takes advantage of recent progress in machine learning (ML) field by applying deep neural network algorithm to improve fluxes based on MODIS NB radiances. The preliminary study shows ML produce are an improvement over the current FBCT Edition 4 NB2BB algorithm. Furthermore, unlike Ed4 NB2BB, the new ML method convert NB radiances directly to broadband fluxes. For future Ed5, new NB radiances are proposed and used by ML to improve fluxes calculation. Prelimary results show significant LW improvement.

Moguo Sun↗

Flux Improvement based on Machine Learning for the CERES FluxByCldTyp Data Product

The NASA Clouds and the Earth's Radiant Energy System (CERES) product provides over 20 years of accurately observed top-of-the-atmosphere (TOA) and surface flux data record for climate monitoring and diagnostic studies. The interaction between clouds and radiation interaction is a key factor that dominate climate feedbacks but is not well understood. To further advance our understanding of the cloud-radiation interaction, a new CERES FluxByCldTyp (FBCT) product has been developed that contains radiative fluxes by cloud-type, which can provide more stringent constraints when validating models and reveal more insight into the interactions between clouds and climate. For CERES partly cloudy and multiple cloud-type footprints, the FBCT product utilizes Moderate Resolution Imaging Spectroradiometer (MODIS) narrow-band (NB) imager channel radiances partitioned by cloud-type within a CERES footprint to estimate the cloud-type broadband fluxes. The MODIS multi-channel derived broadband fluxes were compared with the CERES observed footprint fluxes and were found to be within 1% and 2.5% for LW and SW, respectively, as well as being mostly free of cloud property dependencies. The FBCT all-sky and clear-sky monthly averaged fluxes were found to be consistent with the CERES SSF1deg product. This study takes advantage of recent progress in machine learning (ML) field by applying deep neural network algorithm to improve fluxes based on MODIS NB radiances. The preliminary study shows ML produce are an improvement over the current FBCT Edition 4 NB2BB algorithm. Furthermore, unlike Ed4 NB2BB, the new ML method convert NB radiances directly to broadband fluxes. For future Ed5, new NB radiances are proposed and used by ML to improve fluxes calculation. Prelimary results show significant LW improvement.

Moguo Sun↗

Improvement of Radiative Fluxes for the CERES FluxByCldTyp Data Product Based on Machine Learning Technique

The NASA Clouds and the Earth's Radiant Energy System (CERES) product provides over 20 years of accurately observed top-of-the-atmosphere (TOA) and surface flux data record for climate monitoring and diagnostic studies. The interaction between clouds and radiation interaction is a key factor that dominate climate feedbacks but is not well understood. To further advance our understanding of the cloud-radiation interaction, a new CERES FluxByCldTyp (FBCT) product has been developed that contains radiative fluxes by cloud-type, which can provide more stringent constraints when validating models and reveal more insight into the interactions between clouds and climate. For CERES partly cloudy and multiple cloud-type footprints, the FBCT product utilizes Moderate Resolution Imaging Spectroradiometer (MODIS) narrow-band (NB) imager channel radiances partitioned by cloud-type within a CERES footprint to estimate the cloud-type broadband fluxes. The MODIS multi-channel derived broadband fluxes were compared with the CERES observed footprint fluxes and were found to be within 1% and 2.5% for LW and SW, respectively, as well as being mostly free of cloud property dependencies. The FBCT all-sky and clear-sky monthly averaged fluxes were found to be consistent with the CERES SSF1deg product. This study takes advantage of recent progress in machine learning (ML) field by applying deep neural network algorithm to improve fluxes based on MODIS NB radiances. The preliminary study shows ML produce are an improvement over the current FBCT Edition 4 NB2BB algorithm. Furthermore, unlike Ed4 NB2BB, the new ML method convert NB radiances directly to broadband fluxes. For future Ed5, new NB radiances are proposed and used by ML to improve fluxes calculation. Prelimary results show significant LW improvement.

Moguo Sun↗

Improving Radiative Fluxes for the CERES FluxByCldTyp Data Product Using Deep Neural Network

The NASA Clouds and the Earth's Radiant Energy System (CERES) product provides over 20 years of accurately observed top-of-the-atmosphere (TOA) and surface flux data record for climate monitoring and diagnostic studies. The interaction between clouds and radiation interaction is a key factor that dominate climate feedbacks but is not well understood. To further advance our understanding of the cloud-radiation interaction, a new CERES FluxByCldTyp (FBCT) product has been developed that contains radiative fluxes by cloud-type, which can provide more stringent constraints when validating models and reveal more insight into the interactions between clouds and climate. For CERES partly cloudy and multiple cloud-type footprints, the FBCT product utilizes Moderate Resolution Imaging Spectroradiometer (MODIS) narrow-band (NB) imager channel radiances partitioned by cloud-type within a CERES footprint to estimate the cloud-type broadband fluxes. The MODIS multi-channel derived broadband fluxes were compared with the CERES observed footprint fluxes and were found to be within 1% and 2.5% for LW and SW, respectively, as well as being mostly free of cloud property dependencies. The FBCT all-sky and clear-sky monthly averaged fluxes were found to be consistent with the CERES SSF1deg product. This study takes advantage of recent progress in machine learning (ML) field by applying deep neural network algorithm to improve fluxes based on MODIS NB radiances. The preliminary study shows ML produce are an improvement over the current FBCT Edition 4 NB2BB algorithm. Furthermore, unlike Ed4 NB2BB, the new ML method convert NB radiances directly to broadband fluxes. For future Ed5, new NB radiances are proposed and used by ML to improve fluxes calculation. Preliminary results show significant LW improvement.

Sun, Moguo↗

Decentralized modular hybrid supervisory control for the formation of unmanned helicopters

Abstract Formation control of Unmanned Aerial Vehicles (UAVs) requires them to tightly cooperate to reach and keep the formation, while avoiding collision. This paper proposes a novel decentralized hybrid supervisory control approach for the formation control of multiple UAVs. This is achieved by developing a symbolic motion planning technique to polarly partition the motion space resulting in a finite state discrete event model for the motion dynamics of each UAV. Then, a modular discrete supervisor is designed for different components of the formation mission including reaching the formation, keeping the formation, and collision avoidance. Further, for the collision avoidance mechanism, a novel top‐down decomposition‐based approach is developed to design local supervisors decentralizedly. It is formally proved that with the proposed top‐down decomposition‐based approach, the (locally) supervised UAVs, as a whole, can cooperatively satisfy the desired (global) collision avoidance specification. The proposed decentralized supervisory control algorithm is also verified through a hardware‐in‐the‐loop simulator for the formation control of unmanned helicopters.

Karimoddini, Ali↗

The impact of aerosol mixing state on immersion freezing: insights from classical nucleation theory and particle-resolved simulations

Immersion freezing, initiated by ice-nucleating particles (INPs) in supercooled aqueous droplets, plays an important role in the formation of ice crystals within clouds. The efficiency of immersion freezing depends strongly on INP composition and, crucially, on the mixing state – how chemical species are distributed across the particle population. Here, we quantify the impact of aerosol mixing state on immersion freezing using a combined theoretical and particle-resolved modeling approach. We derive analytical expressions for the frozen fraction of internally and externally mixed INP populations based on classical nucleation theory, showing that the frozen fraction is sensitive to whether ice-active species are present in all particles or only in a subset of the population. We introduce a multi-species immersion freezing scheme into the particle-resolved model PartMC, using the water activity-based immersion freezing model (ABIFM) to compute freezing probabilities for mixed-composition particles. To improve computational efficiency, we implement a Binned Tau-Leaping algorithm and demonstrate an order-of-magnitude speedup with minimal accuracy loss. Simulations reproduce the analytical trends in limiting cases and extend the analysis to more general aerosol populations, where mixing state continues to exert a substantial control on frozen fraction. Sensitivity analyses across particle size, species type, and cooling condition reveal that the mixing state effect is most pronounced when small amounts of highly efficient INPs are mixed with less efficient materials. These findings underscore the need to represent aerosol mixing state explicitly in models of heterogeneous ice nucleation to reduce uncertainty in cloud-phase partitioning.

54 ENVIRONMENTAL SCIENCES↗

A coupled discontinuous Galerkin-Finite Volume framework for solving gas dynamics over embedded geometries

Herein, we present a computational framework for solving the equations of inviscid gas dynamics using structured grids with embedded geometries. The novelty of the proposed approach is the use of high-order discontinuous Galerkin (dG) schemes and a shock-capturing Finite Volume (FV) scheme coupled via an hp adaptive mesh refinement (hp-AMR) strategy that offers high-order accurate resolution of the embedded geometries. The hp-AMR strategy is based on a multi-level block-structured domain partition in which each level is represented by block-structured Cartesian grids and the embedded geometry is represented implicitly by a level set function. The intersection of the embedded geometry with the grids produces the implicitly-defined mesh that consists of a collection of regular rectangular cells plus a relatively small number of irregular curved elements in the vicinity of the embedded boundaries. High-order quadrature rules for implicitly-defined domains enable high-order accuracy resolution of the curved elements with a cell-merging strategy to address the small-cell problem. The hp-AMR algorithm treats the system with a second-order finite volume scheme at the finest level to dynamically track the evolution of solution discontinuities while using dG schemes at coarser levels to provide high-order accuracy in smooth regions of the flow. On the dG levels, the methodology supports different orders of basis functions on different levels. The space-discretized governing equations are then advanced explicitly in time using high-order Runge-Kutta algorithms. Numerical tests are presented for two-dimensional and three-dimensional problems involving an ideal gas. The results are compared with both analytical solutions and experimental observations and demonstrate that the framework provides high-order accuracy for smooth flows and accurately captures solution discontinuities.

97 MATHEMATICS AND COMPUTING↗

PUMIPic: A mesh-based approach to unstructured mesh Particle-In-Cell on GPUs

Unstructured mesh particle-in-cell, PIC, simulations executing on the current and next generation of massively parallel systems require new methods for both the mesh and particles to achieve performance and scalability on GPUs. The traditional approach to implementing PIC simulations defines data structures and algorithms in terms of particles with a full copy of the unstructured mesh on every process. To effectively scale the unstructured mesh and particles, mesh-based PIC uses the unstructured mesh as the predominant data structure with the particles stored in terms of the mesh entities. Here, this paper details the PUMIPic library, a framework for developing efficient and performance-portable mesh-based PIC simulations on GPU systems. A pseudo physics simulation based on a five-dimensional gyro-kinetic code for modeling plasma physics is used to examine the performance of PUMIPic. Scaling studies of the unstructured mesh partition and number of particles are performed up to 4096 nodes of the Summit system at Oak Ridge National Laboratory. The studies show that mesh-based PIC can utilize a partitioned mesh and maintain scaling up to system limitations.

97 MATHEMATICS AND COMPUTING↗

Understanding the Scalability of Bayesian Network Inference using Clique Tree Growth Curves

Bayesian networks (BNs) are used to represent and efficiently compute with multi-variate probability distributions in a wide range of disciplines. One of the main approaches to perform computation in BNs is clique tree clustering and propagation. In this approach, BN computation consists of propagation in a clique tree compiled from a Bayesian network. There is a lack of understanding of how clique tree computation time, and BN computation time in more general, depends on variations in BN size and structure. On the one hand, complexity results tell us that many interesting BN queries are NP-hard or worse to answer, and it is not hard to find application BNs where the clique tree approach in practice cannot be used. On the other hand, it is well-known that tree-structured BNs can be used to answer probabilistic queries in polynomial time. In this article, we develop an approach to characterizing clique tree growth as a function of parameters that can be computed in polynomial time from BNs, specifically: (i) the ratio of the number of a BN's non-root nodes to the number of root nodes, or (ii) the expected number of moral edges in their moral graphs. Our approach is based on combining analytical and experimental results. Analytically, we partition the set of cliques in a clique tree into different sets, and introduce a growth curve for each set. For the special case of bipartite BNs, we consequently have two growth curves, a mixed clique growth curve and a root clique growth curve. In experiments, we systematically increase the degree of the root nodes in bipartite Bayesian networks, and find that root clique growth is well-approximated by Gompertz growth curves. It is believed that this research improves the understanding of the scaling behavior of clique tree clustering, provides a foundation for benchmarking and developing improved BN inference and machine learning algorithms, and presents an aid for analytical trade-off studies of clique tree clustering using growth curves.

Mengshoel, Ole Jakob↗

Digital halftoning methods for selectively partitioning error into achromatic and chromatic channels

A method is described for reducing the visibility of artifacts arising in the display of quantized color images on CRT displays. The method is based on the differential spatial sensitivity of the human visual system to chromatic and achromatic modulations. Because the visual system has the highest spatial and temporal acuity for the luminance component of an image, a technique which will reduce luminance artifacts at the expense of introducing high-frequency chromatic errors is sought. A method based on controlling the correlations between the quantization errors in the individual phosphor images is explored. The luminance component is greatest when the phosphor errors are positively correlated, and is minimized when the phosphor errors are negatively correlated. The greatest effect of the correlation is obtained when the intensity quantization step sizes of the individual phosphors have equal luminances. For the ordered dither algorithm, a version of the method can be implemented by simply inverting the matrix of thresholds for one of the color components.

Mulligan, Jeffrey B.↗