Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “Data reduction methods”

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 667 records · Page 37

Improvements of pre-emptive identification of particle accelerator failures using binary classifiers and dimensionality reduction

In this paper we look at the properties of the Spallation Neutron Source (SNS) Differential Beam Current Monitor (DCM) data and various methods of data transformation to improve pre-emptive detection of machine trips. In this study, the foundation of the approach is the analysis of new underlying data and understanding various properties with the goal of faster classification, higher precision and higher recall with the aim to reduce false positives as low as required. The result of the research presented in this paper are a binary classifier capable of predicting accelerator failures with millisecond classification time, 96% precision, 58% true positive and 0% false positive rate and optimization techniques enabling real-time implementations.

46 INSTRUMENTATION RELATED TO NUCLEAR SCIENCE AND ↗

PESSTO: survey description and products from the first data release by the Public ESO Spectroscopic Survey of Transient Objects

Context. The Public European Southern Observatory Spectroscopic Survey of Transient Objects (PESSTO) began as a public spectroscopic survey in April 2012. PESSTO classifies transients from publicly available sources and wide-field surveys, and selects science targets for detailed spectroscopic and photometric follow-up. PESSTO runs for nine months of the year, January - April and August - December inclusive, and typically has allocations of 10 nights per month. Aims. We describe the data reduction strategy and data products that are publicly available through the ESO archive as the Spectroscopic Survey data release 1 (SSDR1). Methods. PESSTO uses the New Technology Telescope with the instruments EFOSC2 and SOFI to provide optical and NIR spectroscopy and imaging. We target supernovae and optical transients brighter than 20.5m for classification. Science targets are selected for follow-up based on the PESSTO science goal of extending knowledge of the extremes of the supernova population. We use standard EFOSC2 set-ups providing spectra with resolutions of 13-18 Å between 3345-9995 Å. A subset of the brighter science targets are selected for SOFI spectroscopy with the blue and red grisms (0.935-2.53 μm and resolutions 23-33 Å) and imaging with broadband JHKs filters. Results. This first data release (SSDR1) contains flux calibrated spectra from the first year (April 2012-2013). A total of 221 confirmed supernovae were classified, and we released calibrated optical spectra and classifications publicly within 24 h of the data being taken (via WISeREP). The data in SSDR1 replace those released spectra. They have more reliable and quantifiable flux calibrations, correction for telluric absorption, and are made available in standard ESO Phase 3 formats. We estimate the absolute accuracy of the flux calibrations for EFOSC2 across the whole survey in SSDR1 to be typically ~15%, although a number of spectra will have less reliable absolute flux calibration because of weather and slit losses. Acquisition images for each spectrum are available which, in principle, can allow the user to refine the absolute flux calibration. The standard NIR reduction process does not produce high accuracy absolute spectrophotometry but synthetic photometry with accompanying JHKs imaging can improve this. Whenever possible, reduced SOFI images are provided to allow this. Conclusions. Future data releases will focus on improving the automated flux calibration of the data products. The rapid turnaround between discovery and classification and access to reliable pipeline processed data products has allowed early science papers in the first few months of the survey.

79 ASTRONOMY AND ASTROPHYSICS↗

Parallel performance optimizations on unstructured mesh-based simulations

This paper addresses two key parallelization challenges the unstructured mesh-based ocean modeling code, MPAS-Ocean, which uses a mesh based on Voronoi tessellations: (1) load imbalance across processes, and (2) unstructured data access patterns, that inhibit intra- and inter-node performance. Our work analyzes the load imbalance due to naive partitioning of the mesh, and develops methods to generate mesh partitioning with better load balance and reduced communication. Furthermore, we present methods that minimize both inter- and intranode data movement and maximize data reuse. Our techniques include predictive ordering of data elements for higher cache efficiency, as well as communication reduction approaches. We present detailed performance data when running on thousands of cores using the Cray XC30 supercomputer and show that our optimization strategies can exceed the original performance by over 2×. Additionally, many of these solutions can be broadly applied to a wide variety of unstructured grid-based computations.

97 MATHEMATICS AND COMPUTING↗

Advanced Dark Energy Physics Telescope (ADEPT)

In 2006, we proposed to NASA a detailed concept study of ADEPT (the Advanced Dark Energy Physics Telescope), a potential space mission to reliably measure the time-evolution of dark energy by conducting the largest effective volume survey of the universe ever done. A peer-review panel of scientific, management, and technical experts reported back the highest possible 'excellent' rating for ADEPT. We have since made substantial advances in the scientific and technical maturity of the mission design. With this Department of Energy (DOE) award we were granted supplemental funding to support specific extended research items that were not included in the NASA proposal, many of which were intended to broadly advance future dark energy research, as laid out by the Dark Energy Task Force (DETF). The proposed work had three targets: (1) the adaptation of large-format infrared arrays to a 2 micron cut-off; (2) analytical research to improve the understanding of the dark energy figure-of- merit; and (3) extended studies of baryon acoustic oscillation systematic uncertainties. Since the actual award was only for {approx}10% of the proposed amount item (1) was dropped and item (2) work was severely restricted, consistent with the referee reviews of the proposal, although there was considerable contradictions between reviewer comments and several comments that displayed a lack of familiarity with the research. None the less, item (3) was the focus of the work. To characterize the nature of the dark energy, ADEPT is designed to observe baryon acoustic oscillations (BAO) in a large galaxy redshift survey and to obtain substantial numbers of high-redshift Type Ia supernovae (SNe Ia). The 2003 Wilkinson Microwave Anisotropy Probe (WMAP) made a precise determination of the BAO 'standard ruler' scale, as it was imprinted on the cosmic microwave background (CMB) at z {approx} 1090. The standard ruler was also imprinted on the pattern of galaxies, and was first detected in 2005 in Sloan Digital Sky Survey (SDSS) data. A measurement of the BAO standard ruler as a function of time (or redshift) would provide powerful and reliable observational data to shed light on dark energy. In particular, the BAO data provide the angular diameter distance to each redshift, and directly give the expansion rate, H(z), at each redshift. The SNe measurements provide luminosity distances. A space mission is required to obtain the three-dimensional position of enormous numbers of galaxies at high redshift. As recognized by the Dark Energy Task Force, BAO systematic errors are naturally low. The following are the key findings: (1) The BAO method is robust. (2) Separation of the spectral and imaging detection focal planes vastly improves spectral identifications. (3) Prisms instead of grisms provide higher throughput and cleaner spectra. Prisms are clearly superior. (4) Lower prism dispersions improve signal-to-noise but high prism dispersions improve systematic. To ensure that the experiment is not systematic limited, a high dispersion should be used. (5) Counter-dispersion of the spectra reduces systematic errors on the redshift determination and assists in the reduction of confusion. (6) Small rolls are very effective for the reduction of confusion. (7) Interlopers can be recognized by a variety of methods, which combine to produce a sufficiently 'clean' survey data set so as not to limit the dark energy results. (8) A space mission can measure the BAO signature to the cosmic variance limit, limited only by statistics and not by systematic. (9) Density field reconstruction allows for significant BAO accuracy improvements, well beyond that assumed by the Dark Energy Task Force. (10) The BAO method is statistically powerful. It is more powerful than previously estimated, and far more powerful than high redshift Type 1a supernovae, for which the ultimate distance accuracy is limited by flux calibration accuracy. (11) The BAO technique is far simpler than the weak lensing technique and likely to produce more robust dark energy solutions.

72 PHYSICS OF ELEMENTARY PARTICLES AND FIELDS↗

MO-DE-207A-10: One-Step CT Reconstruction for Metal Artifact Reduction by a Modification of Penalized Weighted Least-Squares (PWLS)

Purpose: Metal objects create severe artifacts in kilo-voltage (kV) CT image reconstructions due to the high attenuation coefficients of high atomic number objects. Most of the techniques devised to reduce this artifact utilize a two-step approach, which do not reliably yield the qualified reconstructed images. Thus, for accuracy and simplicity, this work presents a one-step reconstruction method based on a modified penalized weighted least-squares (PWLS) technique. Methods: Existing techniques for metal artifact reduction mostly adopt a two-step approach, which conduct additional reconstruction with the modified projection data from the initial reconstruction. This procedure does not consistently perform well due to the uncertainties in manipulating the metal-contaminated projection data by thresholding and linear interpolation. This study proposes a one-step reconstruction process using a new PWLS operation with total-variation (TV) minimization, while not manipulating the projection. The PWLS for CT reconstruction has been investigated using a pre-defined weight, based on the variance of the projection datum at each detector bin. It works well when reconstructing CT images from metal-free projection data, which does not appropriately penalize metal-contaminated projection data. The proposed work defines the weight at each projection element under the assumption of a Poisson random variable. This small modification using element-wise penalization has a large impact in reducing metal artifacts. For evaluation, the proposed technique was assessed with two noisy, metal-contaminated digital phantoms, against the existing PWLS with TV minimization and the two-step approach. Result: The proposed PWLS with TV minimization greatly improved the metal artifact reduction, relative to the other techniques, by watching the results. Numerically, the new approach lowered the normalized root-mean-square error about 30 and 60% for the two cases, respectively, compared to the two-step method. Conclusion: A new PWLS operation shows promise for improving metal artifact reduction in CT imaging, as well as simplifying the reconstructing procedure.

60 APPLIED LIFE SCIENCES↗

The determination of third order linear models from a seventh order nonlinear jet engine model

Results are presented that demonstrate how good reduced-order models can be obtained directly by recursive parameter identification using input/output (I/O) data of high-order nonlinear systems. Three different methods of obtaining a third-order linear model from a seventh-order nonlinear turbojet engine model are compared. The first method is to obtain a linear model from the original model and then reduce the linear model by standard reduction techniques such as residualization and balancing. The second method is to identify directly a third-order linear model by recursive least-squares parameter estimation using I/O data of the original model. The third method is to obtain a reduced-order model from the original model and then linearize the reduced model. Frequency responses are used as the performance measure to evaluate the reduced models. The reduced-order models along with their Bode plots are presented for comparison purposes.

Lalonde, Rick J.↗

Electrode kinetics of oxygen reduction - A theoretical and experimental analysis of the rotating ring-disc electrode method

In order to calculate most of the rate constants for the intermediate formation of H2O2 in the electroreduction of O2 to H2O, the theoretical treatments of the rotating ring-disc electrode method by Damjanovic et al. (1966, 1967), Bagotskii et al. (1968, 1969), and Wroblowa et al. (1976) are modified. Rotating ring-disc electrode experimental data obtained for O2 reduction in Pt in 0.55 M H2SO4 are used to illustrate the calculations of rate constants according to the above theoretical treatments. A simple reaction model as proposed by the first author is consistent with the experimental data. The results indicate that O2 (97 percent) reduces to H2O in a direct four-electron transfer reaction. The adsorption of O2 is probably the rate-determining step in the potential region more negative than 0.5 V vs. reversible hydrogen electrode.

Hsueh, K.-L.↗

MRI-Based Computed Tomography Metal Artifact Correction Method for Improving Proton Range Calculation Accuracy

Purpose: Computed tomography (CT) artifacts can severely degrade dose calculation accuracy in proton therapy. Prompted by the recently increased popularity of magnetic resonance imaging (MRI) in the radiation therapy clinic, we developed an MRI-based CT artifact correction method for improving the accuracy of proton range calculations. Methods and Materials: The proposed method replaces corrupted CT data by mapping CT Hounsfield units (HU number) from a nearby artifact-free slice, using a coregistered MRI. MRI and CT volumetric images were registered with use of 3-dimensional (3D) deformable image registration (DIR). The registration was fine-tuned on a slice-by-slice basis by using 2D DIR. Based on the intensity of paired MRI pixel values and HU from an artifact-free slice, we performed a comprehensive analysis to predict the correct HU for the corrupted region. For a proof-of-concept validation, metal artifacts were simulated on a reference data set. Proton range was calculated using reference, artifactual, and corrected images to quantify the reduction in proton range error. The correction method was applied to 4 unique clinical cases. Results: The correction method resulted in substantial artifact reduction, both quantitatively and qualitatively. On respective simulated brain and head and neck CT images, the mean error was reduced from 495 and 370 HU to 108 and 92 HU after correction. Correspondingly, the absolute mean proton range errors of 2.4 cm and 1.7 cm were reduced to less than 2 mm in both cases. Conclusions: Our MRI-based CT artifact correction method can improve CT image quality and proton range calculation accuracy for patients with severe CT artifacts.

62 RADIOLOGY AND NUCLEAR MEDICINE↗

Satellite Detection of Smoke Aerosols Over a Snow/Ice Surface by TOMS

The use of TOMS (Total Ozone Mapping Spectrometer) satellite data demonstrates the recently developed technique of using satellite UV radiance measurements to detect absorbing tropospheric aerosols is effective over snow/ice surfaces. Instead of the traditional single wavelength (visible or infrared) method of measuring tropospheric aerosols, this method takes advantage of the wavelength dependent reduction in the backscattered radiance due to the presence of absorbing aerosols over snow/ice surfaces. An example of the resulting aerosol distribution derived from TOMS data is shown for an August 1998 event in which smoke generated by Canadian forest fires drifts over and across Greenland. As the smoke plume moved over Greenland, the TOMS observed 380 nm reflectivity over the snow/ice surface dropped drastically from 90-100% down to 30-40%. To study the effects of this smoke plume in both the UV and visible regions of the spectrum, we compared a smoke-laden spectrum taken over Greenland by the high spectral resolution (300 to 800 nm) GOME instrument with one that is aerosol-free. We also discuss the results of modeling the darkening effects of various types of absorbing aerosols over snow/ice surfaces using a radiative transfer code. Finally, we investigated the history of such events by looking at the nearly twenty year record of TOMS aerosol index measurements and found that there is a large interannual variability in the amount of smoke aerosols observed over Greenland. This information will be available for studies of radiation and transport properties in the Arctic.

Hsu, N. Christina↗

Quantitative Phenotypic Analysis of Arabidopsis Thaliana Grown in Microgravity Using Soap, an Applied Artificial Intelligence

Phenotypic analysis is an essential step in studying the gravitropic responses and gravitational stress experienced by plants grown in microgravity. Many of the phenotypic traits analyzed in gravitropism studies, such as root length, leaf area, secondary root count, and number of root hairs, currently rely upon manual measurement methods for quantification. However, new advances in data analysis technology using artificial intelligence offer an opportunity for more efficient phenotypic analysis and a reduction of time spent in the data collection phase. In this project, the ability of a new artificially intelligent data collection software, SOAP (Simple Object Access Protocol), to collect and quantify phenotypic traits of Arabidopsis thaliana will be assessed. This project will test the measurements taken by an initial draft of the software. SOAP will take measurements of shoot length, a key phenotype used to assess A. thaliana stress response when grown in microgravity conditions. Shoot length measurements made by SOAP will be compared against a series of manual shoot length measurements. The comparison between the two methods of data measurement will provide valuable insight into the relative accuracy of SOAP and the margin of human error when conducting lab measurements.

Arabidopsis↗

Employing Sensitivity Derivatives to Estimate Uncertainty Propagation in CFD

Two methods that exploit the availability of sensitivity derivatives are successfully employed to predict uncertainty propagation through Computational Fluid Dynamics (CFD) code for an inviscid airfoil problem. An approximate statistical second-moment method and a Sensitivity Derivative Enhanced Monte Carlo (SDEMC) method are successfully demonstrated on a two-dimensional problem. First- and second-order sensitivity derivatives of code output with respect to code input are obtained through an efficient incremental iterative approach. Given uncertainties in statistically independent, random, normally distributed flow parameters (input variables); these sensitivity derivatives enable one to formulate first- and second-order Taylor Series approximations for the mean and variance of CFD output quantities. Additionally, incorporation of the first-order sensitivity derivatives into the data reduction phase of a conventional Monte Carlo (MC) simulation allows for improved accuracy in determining the first moment of the CFD output. Both methods are compared to results generated using a conventional MC method. The methods that exploit the availability of sensitivity derivatives are found to be valid when considering small deviations from input mean values.

Putko, Michele M.↗

Free-Space Optical Communication for CubeSats in Low Lunar Orbit (LLO)

The NASA ARTEMIS Program will include LunaNet, a highly extensible, open architecture, lunar communications and navigation network. A constellation of CubeSats in Low Lunar Orbit (LLO), 100 km, could form an optical communications and navigation network as part of LunaNet, with terminals on the lunar surface, including mobile ones such as with astronauts and rovers. The proposed CubeSat nodes should provide data relay and navigational aid services. The proposed effort herein is to develop a fine pointing capability for laser beam pointing to augment body pointing by CubeSats. Body pointing was used by Aerospace Corporation for the CubeSats in LEO in NASA’s Optical Communications and Sensors Demonstration (OCSD) program [1]. Previously, this fine pointing capability was computer simulated for the OCSD program [2,3]. With fine pointing, the spot size on the Earth was reduced by a factor of eight with a reduction in laser output power by a factor of sixty-four, thereby mitigating the thermal load challenge on the CubeSats. The same reductions in spot size and laser output power can be achieved for CubeSats in LLO. A new method is described for optical data transmissions from satellites, which uses laser arrays for laser beam pointing. It combines a lens system and an array of vertical-cavity, surface-emitting lasers and photodetectors, an VCSEL/Photodetector Array, (both mature technologies), in a novel way. This system is applied to CubeSats in low lunar orbit, (LLO), which use body pointing. Also, It may be able to replace current architectures which use dynamical systems, (i.e., moving parts) to point the laser, and which may also use vibration isolation platforms. The computer simulations used the optics code, OpticStudio, from Zemax, LLC, which has the capabilities to model the laser source and diffraction effects from wave optics. These capabilities make it possible to model laser beam propagation over long space communication distances.

Goorjian, P. M.↗

Brillouin Sensing with PCA, and PCA-Based Neural Networks for Efficient Temperature Monitoring

This work explores peak estimation techniques in Brillouin Optical Time Domain Analysis (BOTDA), emphasizing both accuracy and efficiency. Euclidean distance measurement method is applied to principal components derived from Brillouin Gain Spectrum data. It offers a major speed advantage being 180 170 times faster than traditional curve fitting methods such as Lorentzian curve fitting, while maintaining similar accuracy. Additionally, a PCA- based neural network model shows significant reduction of peak estimation time compared to Lorentzian fitting. Results show Brillouin frequency shift errors lie under 0.75 MHz in both Euclidean distance-based and neural network-based methods, both of which utilize PCA components. For large data sets and long length fibers, PCA- assisted neural network for peak estimation would be an efficient solution.

Distributed optical fiber sensing↗

Thermodynamics of Aqueous Organic Sulfur Compounds: A Key to the Organic Geochemistry of Hydrothermal Systems?

Hydrothermal environments are locations of varied geochemistry due to the disequilibrium between vent fluids and seawater. The disequilibrium geochemistry has been hypothesized to include reactions to synthesize organic compounds. Observations of the organic geochemistry of hydrothermal vent sites has received little attention. Experimental simulations of these environments, however, indicate that organic compounds may have difficulty forming in a purely aqueous environment. On the other hand, thiols. thioesters and disulfides have been implicated as reaction intermediates between CO or CO2 in experiments of carbon reduction in hydrothermal environments as well as in a variety of biological processes and other abiotic reactions (Wachtershauser, 1990, OLEB 20, 173; Heinen and Lauwers, 1996, OLEB 26, 13 1, Huber and Wachtershauser, 1997, Science 276, 245; Russell et al., 1998, in Thermophiles: The keys to molecular evolution and the origin of life?). The reduction of CO2 to thiols, for example, is observed using the FeS-H2S/FeS2 couple to provide the reducing power (see Schoonen et al., 1999, OLEB 29, 5). In addition, the enzyme involved in final stage of methanogenesis, coenzyme-M, is itself a thiol. Thus, organic sulfur compounds may hold the key to the organic chemistry leading to the origin of life at high temperatures. Understanding the biochemical processes of microorganisms that can live to temperatures at least as high as 113 C (Blochl et al., 1996, Extremophiles 1, 14) requires knowledge of the properties of the chemical reactions involved. In order to assess the role of aqueous organic sulfur compounds in hydrothermal organic geochemistry, we have been attempting to determine their thermodynamic properties. We have culled the literature to obtain the properties of organic sulfur compounds. We are able to calculate a number of essential properties, such as free energies of formation, from solubility data available in the literature together with standard properties of organic sulfur gases. However, a number of the properties for aqueous organic sulfur compounds have not been experimentally determined. Furthermore, most of thermodynamic data that are available are for 25 C and 1 bar. In order to determine reaction properties to temperatures and pressures appropriate to the hydrothermal conditions in which thermophilic organisms actually live, we use equations of state developed by Helgeson and co-workers (Helgeson et al., 1981, AJS 281, 1249). A key piece of information needed to go up in temperature is the partial molal heat capacity, which is one of the properties for which experimental data are unavailable for nearly all organic sulfur compounds. We have used correlation methods to determine the partial molal heat capacities and volumes of many organic solutes. These estimates allow us to asses the role of organic sulfur compounds during the reduction of carbon in hydrothermal settings. We will present these data, along with examples of the thermodynamic properties of reactions involving aqueous organic sulfur compounds.

Schulte, Mitchell↗

A complex approach to assessing porous structure of structured ceramics obtained by SPS technique

Highlights: • A complex approach to microstructural analysis of nanostructured SPS ceramics was presented. • A bunch of gas, intrusion and microscopic methods were applied for open/closed porosity determination in nanoceramics. • Kinetic TPR analysis for structural changes in nanoceramic was carried out. • 3D pore visualization for nanoceramics was provided via SEM/FIB tomography • Porosity calculations were performed via BET, BJH, t-plot, Washburn equation, FEI Avizo 9.1 software results. - Abstract: Spark plasma sintering (SPS) is a highly prospective technology providing rapid consolidation of nano-disperse compositions into structured ceramics with complex structural organization. Characterizing pore structure of such systems remains a challenge due to different types, size and shape of the pores as well as structural defects occurring in the material, thus requiring special methods to quantify certain porosity type. The paper presents a complex approach to studying structure of SPS hematite-based structured ceramics. The method involves a number of gas, intrusion and electron microscopy probing techniques to characterize open and closed pores in the ceramics bulk. Low temperature nitrogen sorption has been implemented to estimate open micro- and mesoporosity in the size range 0.7–50 nm using BET, BJH and t-plot methods to process experimental data. Additionally, structural peculiarities of consolidated structured ceramics have been studied using temperature-programmed reduction (TPR) with the kinetic analysis of the results being carried out. Volume of macropores sized above 50 nm has been measured with mercury intrusion. Closed pores and structural defects have been quantified with SEM and FIB/SEM tomography. By comparing experimental and estimated results we have shown that addressing all porosity types provides a highly precise structural characterization of the material.

77 NANOSCIENCE AND NANOTECHNOLOGY↗

Multi-GPU Implementation of a 3D Finite Difference Time Domain Earthquake Code on Heterogeneous Supercomputers

We have developed a highly scalable 3D Finite Difference GPU code for use in earthquake engineering and disaster management through regional petascale earthquake simulations. This MPI-CUDA code is based on a widely-used wave propagation code called AWP-ODC and restructured for high throughput and efficiency on a heterogeneous computing architecture. We present an effective communication reduction technique for leveraging GPUs with minimal PCI-e overhead, and a novel overlapping method to fully hide data communication latency between GPUs. The optimization concept used in this work can be extended to general stencil computing on a structured grid. The benchmarks demonstrated sustained 100 TFlops in single precision for 49 billion mesh points using 952 GPUs on the NCCS Titan Phase 5 system, which is a 77-fold speedup compared to the CPU version of the code. This multi-GPU implementation has been validated and used for a large-scale verification wave propagation simulation of Mw5.4 Chino Hills earthquake using 128 GPUs.

58 GEOSCIENCES↗

A Novel Coarsening Method for Scalable and Efficient Mesh Generation

In this paper, we propose a novel mesh coarsening method called brick coarsening method. The proposed method can be used in conjunction with any graph partitioners and scales to very large meshes. This method reduces problem space by decomposing the original mesh into fixed-size blocks of nodes called bricks, layered in a similar way to conventional brick laying, and then assigning each node of the original mesh to appropriate brick. Our experiments indicate that the proposed method scales to very large meshes while allowing simple RCB partitioner to produce higher-quality partitions with significantly less edge cuts. Our results further indicate that the proposed brick-coarsening method allows more complicated partitioners like PT-Scotch to scale to very large problem size while still maintaining good partitioning performance with relatively good edge-cut metric. Graph partitioning is an important problem that has many scientific and engineering applications in such areas as VLSI design, scientific computing, and resource management. Given a graph G = (V,E), where V is the set of vertices and E is the set of edges, (k-way) graph partitioning problem is to partition the vertices of the graph (V) into k disjoint groups such that each group contains roughly equal number of vertices and the number of edges connecting vertices in different groups is minimized. Graph partitioning plays a key role in large scientific computing, especially in mesh-based computations, as it is used as a tool to minimize the volume of communication and to ensure well-balanced load across computing nodes. The impact of graph partitioning on the reduction of communication can be easily seen, for example, in different iterative methods to solve a sparse system of linear equation. Here, a graph partitioning technique is applied to the matrix, which is basically a graph in which each edge is a non-zero entry in the matrix, to allocate groups of vertices to processors in such a way that many of matrix-vector multiplication can be performed locally on each processor and hence to minimize communication. Furthermore, a good graph partitioning scheme ensures the equal amount of computation performed on each processor. Graph partitioning is a well known NP-complete problem, and thus the most commonly used graph partitioning algorithms employ some forms of heuristics. These algorithms vary in terms of their complexity, partition generation time, and the quality of partitions, and they tend to trade off these factors. A significant challenge we are currently facing at the Lawrence Livermore National Laboratory is how to partition very large meshes on massive-size distributed memory machines like IBM BlueGene/P, where scalability becomes a big issue. For example, we have found that the ParMetis, a very popular graph partitioning tool, can only scale to 16K processors. An ideal graph partitioning method on such an environment should be fast and scale to very large meshes, while producing high quality partitions. This is an extremely challenging task, as to scale to that level, the partitioning algorithm should be simple and be able to produce partitions that minimize inter-processor communications and balance the load imposed on the processors. Our goals in this work are two-fold: (1) To develop a new scalable graph partitioning method with good load balancing and communication reduction capability. (2) To study the performance of the proposed partitioning method on very large parallel machines using actual data sets and compare the performance to that of existing methods. The proposed method achieves the desired scalability by reducing the mesh size. For this, it coarsens an input mesh into a smaller size mesh by coalescing the vertices and edges of the original mesh into a set of mega-vertices and mega-edges. A new coarsening method called brick algorithm is developed in this research. In the brick algorithm, the zones in a given mesh are first grouped into fixed size blocks called bricks. These brick are then laid in a way similar to conventional brick laying technique, which reduces the number of neighboring blocks each block needs to communicate. Contributions of this research are as follows: (1) We have developed a novel method that scales to a really large problem size while producing high quality mesh partitions; (2) We measured the performance and scalability of the proposed method on a machine of massive size using a set of actual large complex data sets, where we have scaled to a mesh with 110 million zones using our method. To the best of our knowledge, this is the largest complex mesh that a partitioning method is successfully applied to; and (3) We have shown that proposed method can reduce the number of edge cuts by as much as 65%.

97 MATHEMATICS AND COMPUTING↗

Transport Test Problems for Hybrid Methods Development

This report presents 9 test problems to guide testing and development of hybrid calculations for the ADVANTG code at ORNL. These test cases can be used for comparing different types of radiation transport calculations, as well as for guiding the development of variance reduction methods. Cases are drawn primarily from existing or previous calculations with a preference for cases which include experimental data, or otherwise have results with a high level of confidence, are non-sensitive, and represent problem sets of interest to NA-22.

99 GENERAL AND MISCELLANEOUS↗