Search NASA⌕ Search

SEARCH · Search NASA

Results for “AMG”

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 109 records · Page 6

Scaling Algebraic Multigrid Solvers: On the Road to Exascale

Algebraic Multigrid (AMG) solvers are an essential component of many large-scale scientific simulation codes. Their continued numerical scalability and efficient implementation is critical for preparing these codes for exascale. Our experiences on modern multi-core machines show that significant challenges must be addressed for AMG to perform well on such machines. We discuss our experiences and describe the techniques we have used to overcome scalability challenges for AMG on hybrid architectures in preparation for exascale.

97 MATHEMATICS AND COMPUTING↗

High resolution viscous fingering simulation in miscible displacement using a p-adaptive discontinuous Galerkin method with algebraic multigrid preconditioner

High resolution simulation of viscous fingering can offer an accurate and detailed prediction for subsurface engineering processes involving fingering phenomena. The fully implicit discontinuous Galerkin (DG) method has been shown to be an accurate and stable method to model viscous fingering with high Peclet number and mobility ratio. In this study, we present two techniques to speedup large scale simulations of this kind. The first technique relies on a simple p-adaptive scheme in which high order basis functions are employed only in elements near the finger fronts where the concentration has a sharp change. As a result, the number of degrees of freedom is significantly reduced and the simulation yields almost identical results to the more expensive simulation with uniform high order elements throughout the mesh. The second technique for speedup involves improving the solver efficiency. We present an algebraic multigrid (AMG) preconditioner which allows the DG matrix to leverage the robust AMG preconditioner designed for the continuous Galerkin (CG) finite element method. The resulting preconditioner works effectively for fixed order DG as well as p-adaptive DG problems. Finally, with the improvements provided by the p-adaptivity and AMG preconditioning, we can perform high resolution three-dimensional viscous fingering simulations required for miscible displacement with high Peclet number and mobility ratio in greater detail than before for well injection problems.

97 MATHEMATICS AND COMPUTING↗

Physical origins of the varying performance and unusual transport behaviors among thermoelectric A Mg 2 Sb 2 materials ( A = Ca, Sr, Sm, Yb, and Mg)

Contrary to the similar thermoelectric performance among both AZn 2 Sb 2 and AMg 2 Bi 2 compounds, their isostructural counterparts, AMg 2 Sb 2 , can exhibit thermoelectric figure of merit values that vary by orders of magnitude with different A elements. Here, we reveal physical origins accounting for the significantly differing performance among AMg 2 Sb 2 -based compounds (A = Ca, Sr, Sm, Yb, and Mg) through comprehensive analyses, where it is shown that the dispar- ities in performance at the macroscale essentially originate from the widely varying activation energies that equal amounts of dopant can induce. Meanwhile, a few unusual transport behaviors regarding electrical conductivity, carrier concentration, or lattice thermal con- ductivity among these compounds have been identified, and we also present their rationales in depth. Furthermore, this mechanism-focused study can not only promote further understanding of the complex transport behaviors in condensed matter but be instrumental in rationally tun- ing the physical properties of materials as well.

36 MATERIALS SCIENCE↗

A Comparison of Linear Solvers for Resolving Flow in Three-Dimensional Discrete Fracture Networks

We compare various methods for resolving steady flow within three-dimensional discrete fracture networks, including direct methods, Krylov subspace methods with and without preconditioning, and multi-grid methods. We compared the performance of the methods based on compute times and scaling of the solution as a function of the number of grid nodes and log-variance of the hydraulic aperture. The methods are applied to three test cases: (a) variable density of networks with a truncated power-law distribution of fracture lengths, (b) a fixed network composed of monodisperse fracture sizes but varied permeability/aperture heterogeneity, (c) and a network based on field site in Nevada, US. We chose these cases to allow us to study the impact of the mesh size and flow properties, as well as to demonstrate our conclusions on a large-scale, realistic problem (more than 40 million mesh nodes). A direct solution using Cholesky factorization outperformed other methods for every example but was closely followed in performance by some algebraic multigrid (AMG) preconditioned Krylov subspace methods. Among the Krylov methods, conjugate gradients (CG) with an AMG preconditioner performs the best. Generally, Cholesky factorization is recommended, but CG with an AMG preconditioner may be suitable for very large problems beyond 40 million nodes where the entire linear system cannot reside in memory.

58 GEOSCIENCES↗

Investigation of the process of mixing reagents in the laser chamber of active medium generators of continuous-wave chemical lasers with promising nozzle arrays

It is shown that the use of a toothed nozzle array in the active medium generator (AMG) of continuous-wave chemical lasers (CWCLs) allows more efficient mixing of reagents to be achieved in the laser chamber than in an AMG with a slit nozzle array. The results of calculations of parameters of the active medium of a DF CWCL operating in the gain regime for the AMG with traditional and promising nozzle array designs are presented. A kinetic model of processes in the DF CWCL active medium is proposed, which allows obtaining a good agreement with the results of measurements of the small-signal gain. (paper)

37 INORGANIC, ORGANIC, PHYSICAL, AND ANALYTICAL CH↗

DNA Viral Diversity, Abundance, and Functional Potential Vary across Grassland Soils with a Range of Historical Moisture Regimes

Soil viruses are abundant, but the influence of the environment and climate on soil viruses remains poorly understood. Here, we addressed this gap by comparing the diversity, abundance, lifestyle, and metabolic potential of DNA viruses in three grassland soils with historical differences in average annual precipitation, low in eastern Washington (WA), high in Iowa (IA), and intermediate in Kansas (KS). Bioinformatics analyses were applied to identify a total of 2,631 viral contigs, including 14 complete viral genomes from three deep metagenomes (1 terabase [Tb] each) that were sequenced from bulk soil DNA. An additional three replicate metagenomes (~0.5 Tb each) were obtained from each location for statistical comparisons. Identified viruses were primarily bacteriophages targeting dominant bacterial taxa. Both viral and host diversity were higher in soil with lower precipitation. Viral abundance was also significantly higher in the arid WA location than in IA and KS. More lysogenic markers and fewer clustered regularly interspaced short palindromic repeats (CRISPR) spacer hits were found in WA, reflecting more lysogeny in historically drier soil. More putative auxiliary metabolic genes (AMGs) were also detected in WA than in the historically wetter locations. The AMGs occurring in 18 pathways could potentially contribute to carbon metabolism and energy acquisition in their hosts. Structural equation modeling (SEM) suggested that historical precipitation influenced viral life cycle and selection of AMGs. The observed and predicted relationships between soil viruses and various biotic and abiotic variables have value for predicting viral responses to environmental change.

59 BASIC BIOLOGICAL SCIENCES↗

Algebraic Multigrid Preconditioners for Multiphase Flow in Porous Media

Multiphase flow is a critical process in a wide range of applications, including carbon sequestration, contaminant remediation, and groundwater management. Typically, this process is modeled by a nonlinear system of partial differential equations derived by considering the mass conservation of each phase (e.g., oil, water), along with constitutive laws for the relationship of phase velocity to phase pressure. In this study, we develop and study efficient solution algorithms for solving the algebraic systems of equations derived from a fully coupled and time-implicit treatment of models of multiphase flow. We explore the performance of several preconditioners based on algebraic multigrid (AMG) for solving the linearized problem, including “black-box” AMG applied directly to the system, a new version of constrained pressure residual multigrid (CPR-AMG) preconditioning, and a new preconditioner derived using an approximate Schur complement arising from the block factorization of the Jacobian. Finally, we show that the new methods are the most robust with respect to problem character, as determined by varying effects of capillary pressures, and we show that the block factorization preconditioner both is efficient and scales optimally with problem size.

97 MATHEMATICS AND COMPUTING↗

A Fast Algebraic Multigrid Solver and Accurate Discretization for Highly Anisotropic Heat Flux I: Open Field Lines

We present a novel solver technique for the anisotropic heat flux equation, aimed at the high level of anisotropy seen in magnetic confinement fusion plasmas. Such problems pose two major challenges: (i) discretization accuracy and (ii) efficient implicit linear solvers. We simultaneously address each of these challenges by constructing a new finite element discretization with excellent accuracy properties, tailored to a novel solver approach based on algebraic multigrid (AMG) methods designed for advective operators. We pose the problem in a mixed formulation, introducing the directional temperature gradient as an auxiliary variable. The temperature and auxiliary fields are discretized in a scalar discontinuous Galerkin space with upwinding principles used for discretizations of advection. We demonstrate the proposed discretization’s superior accuracy over other discretizations of anisotropic heat flux, achieving error 1000x smaller for anisotropy ratio of 10 9 , for closed field lines. The block matrix system is reordered and solved in an approach where the two advection operators are inverted using AMG solvers based on approximate ideal restriction, which is particularly efficient for upwind discontinuous Galerkin discretizations of advection. To ensure that the advection operators are nonsingular, in this paper we restrict ourselves to considering open (acyclic) magnetic field lines for the linear solvers. We demonstrate fast convergence of the proposed iterative solver in highly anisotropic regimes where other diffusion-based AMG methods fail.

97 MATHEMATICS AND COMPUTING↗

On Compatible Transfer Operators in Nonsymmetric Algebraic Multigrid

The standard goal for an effective algebraic multigrid (AMG) algorithm is to develop relaxation and coarse-grid correction schemes that attenuate complementary error modes. In the nonsymmetric setting, coarse-grid correction Π will almost certainly be nonorthogonal (and divergent) in any known standard product, meaning ∥Π∥ > 1. This introduces a new consideration, that one wants coarse-grid correction to be as close to orthogonal as possible, in an appropriate norm. In addition, due to nonorthogonality, Π may actually amplify certain error modes that are in the range of interpolation. Relaxation must then not only be complementary to interpolation, but also rapidly eliminate any error amplified by the nonorthogonal correction, or the algorithm may diverge. Here this paper develops analytic formulae on how to construct “compatible” transfer operators in nonsymmetric AMG such that ∥Π∥ = 1 in some standard matrix-induced norm. Discussion is provided on different options for the norm in the nonsymmetric setting, the relation between “ideal” transfer operators in different norms, and insight into the convergence of nonsymmetric reduction-based AMG.

97 MATHEMATICS AND COMPUTING↗

Statistical and machine learning models for optimizing energy in parallel applications

Rising power costs and constraints are driving a growing focus on the energy efficiency of high performance computing systems. The unique characteristics of a particular system and workload and their effect on performance and energy efficiency are typically difficult for application users to assess and to control. Settings for optimum performance and energy efficiency can also diverge, so we need to identify trade-off options that guide a suitable balance between energy use and performance. We present statistical and machine learning models that only require a small number of runs to make accurate Pareto-optimal trade-off predictions using parameters that users can control. We study model training and validation using several parallel kernels and more complex workloads, including Algebraic Multigrid (AMG), Large-scale Atomic Molecular Massively Parallel Simulator, and Livermore Unstructured Lagrangian Explicit Shock Hydrodynamics. Here, we demonstrate that we can train the models using as few as 12 runs, with prediction error of less than 10%. Our AMG results identify trade-off options that provide up to 45% improvement in energy efficiency for around 10% performance loss. We reduce the sample measurement time required for AMG by 90%, from 13 h to 74 min.

97 MATHEMATICS AND COMPUTING↗

Preparing Algebraic Multigrid for Exascale

Algebraic Multigrid (AMG) solvers are an essential component of many large-scale scientific simulation codes. Their continued numerical scalability and efficient implementation is critical for preparing these codes for exascale. Our experiences on modern multi-core machines show that significant challenges must be addressed for AMG to perform well on such machines. We discuss our experiences and describe the techniques we have used to overcome scalability challenges for AMG on hybrid architectures in preparation for exascale.

97 MATHEMATICS AND COMPUTING↗

Petascale Computing Enabling Technologies Project Final Report

The Petascale Computing Enabling Technologies (PCET) project addressed challenges arising from current trends in computer architecture that will lead to large-scale systems with many more nodes, each of which uses multicore chips. These factors will soon lead to systems that have over one million processors. Also, the use of multicore chips will lead to less memory and less memory bandwidth per core. We need fundamentally new algorithmic approaches to cope with these memory constraints and the huge number of processors. Further, correct, efficient code development is difficult even with the number of processors in current systems; more processors will only make it harder. The goal of PCET was to overcome these challenges by developing the computer science and mathematical underpinnings needed to realize the full potential of our future large-scale systems. Our research results will significantly increase the scientific output obtained from LLNL large-scale computing resources by improving application scientist productivity and system utilization. Our successes include scalable mathematical algorithms that adapt to these emerging architecture trends and through code correctness and performance methodologies that automate critical aspects of application development as well as the foundations for application-level fault tolerance techniques. PCET's scope encompassed several research thrusts in computer science and mathematics: code correctness and performance methodologies, scalable mathematics algorithms appropriate for multicore systems, and application-level fault tolerance techniques. Due to funding limitations, we focused primarily on the first three thrusts although our work also lays the foundation for the needed advances in fault tolerance. In the area of scalable mathematics algorithms, our preliminary work established that OpenMP performance of the AMG linear solver benchmark and important individual kernels on Atlas did not match the predictions of our simple initial model. Our investigations demonstrated that a poor default memory allocation mechanism degraded performance. We developed a prototype NUMA library to provide generic mechanisms to overcome these issues, resulting in significantly improved OpenMP performance. After additional testing, we will make this library available to all users, providing a simple means to improve threading on LLNL's production Linux platforms. We also made progress on developing new scalable algorithms that target multicore nodes. We designed and implemented a new AMG interpolation operator with improved convergence properties for very low complexity coarsening schemes. This implementation will also soon be available to LLNL's application teams as part of the hypre library. We presented results for both topics in an invited plenary talk entitled 'Efficient Sparse Linear Solvers for Multi-Core Architectures' at the 2009 HPCMP Institutes Annual Meeting/CREATE Annual All-Hands Meeting. The interpolation work was summarized in a talk entitled 'Improving Interpolation for Aggressive Coarsening' at the 14th Copper Mountain Conference on Multigrid Methods and in a research paper that will appear in Numerical Linear Algebra with Applications. In the area of code correctness, we significantly extended our behavior equivalence class identification mechanism. Specifically, we not only demonstrated it works well at very large scales but we also added the ability to classify MPI tasks not only by function call traces, but also by specific call sites (source code line numbers) being executed by tasks. More importantly, we developed a new technique to determine relative logical execution progress of tasks in the equivalence classes by combining static analysis with our original dynamic approach. We applied this technique to a correctness issue that arose at 4096 tasks during the development of the new AMG interpolation operator discussed above. This scale isat the limit of effectiveness of production tools, but our technique quickly located the erroneous source code, demonstrating the power of understanding relationships between behavioral equivalence classes. This work is the subject of a paper recently accepted to SC09, as well as a presentation entitled 'Providing Order to Extreme Scale Debugging Chaos' given at the ParaDyn Week annual conference in College Park, MD. In addition to this theoretical extension, we have made significant progress in developing a front end for this tool set, and the front-end is now available on several of LLNL's largescale computing resources. In addition, we explored mechanisms to identify exact locations of erroneous MPI usage in application source code. In this work, we developed a new model that led to a highly efficient algorithm for detecting deadlock during dynamic software testing. This work was the subject of a well-received paper at ICS 2009 [4].

99 GENERAL AND MISCELLANEOUS↗

Expanding standards in viromics: in silico evaluation of dsDNA viral genome identification, classification, and auxiliary metabolic gene curation

Viruses influence global patterns of microbial diversity and nutrient cycles. Though viral metagenomics (viromics), specifically targeting dsDNA viruses, has been critical for revealing viral roles across diverse ecosystems, its analyses differ in many ways from those used for microbes. To date, viromics benchmarking has covered read pre-processing, assembly, relative abundance, read mapping thresholds and diversity estimation, but other steps would benefit from benchmarking and standardization. Here we use in silico-generated datasets and an extensive literature survey to evaluate and highlight how dataset composition (i.e., viromes vs bulk metagenomes) and assembly fragmentation impact (i) viral contig identification tool, (ii) virus taxonomic classification, and (iii) identification and curation of auxiliary metabolic genes (AMGs). The in silico benchmarking of five commonly used virus identification tools show that gene-content-based tools consistently performed well for long (≥3 kbp) contigs, while k -mer- and blast-based tools were uniquely able to detect viruses from short (≤3 kbp) contigs. Notably, however, the performance increase of k -mer- and blast-based tools for short contigs was obtained at the cost of increased false positives (sometimes up to ~5% for virome and ~75% bulk samples), particularly when eukaryotic or mobile genetic element sequences were included in the test datasets. Furthermore, for viral classification, variously sized genome fragments were assessed using gene-sharing network analytics to quantify drop-offs in taxonomic assignments, which revealed correct assignations ranging from ~95% (whole genomes) down to ~80% (3 kbp sized genome fragments). A similar trend was also observed for other viral classification tools such as VPF-class, ViPTree and VIRIDIC, suggesting that caution is warranted when classifying short genome fragments and not full genomes. Finally, we highlight how fragmented assemblies can lead to erroneous identification of AMGs and outline a best-practices workflow to curate candidate AMGs in viral genomes assembled from metagenomes. Together, these benchmarking experiments and annotation guidelines should aid researchers seeking to best detect, classify, and characterize the myriad viruses ‘hidden’ in diverse sequence datasets.

59 BASIC BIOLOGICAL SCIENCES↗

Challenges of Algebraic Multigrid across Multicore Architectures

Algebraic multigrid (AMG) is a popular solver for large-scale scientific computing and an essential component of many simulation codes. AMG has shown to be extremely efficient on distributed-memory architectures. However, when executed on modern multicore architectures, we face new challenges that can significantly deteriorate AMG's performance. We examine its performance and scalability on three disparate multicore architectures: a cluster with four AMD Opteron Quad-core processors per node (Hera), a Cray XT5 with two AMD Opteron Hex-core processors per node (Jaguar), and an IBM BlueGene/P system with a single Quad-core processor (Intrepid). We discuss our experiences on these platforms and present results using both an MPI-only and a hybrid MPI/OpenMP model. We also discuss a set of techniques that helped to overcome the associated problems, including thread and process pinning and correct memory associations.

97 MATHEMATICS AND COMPUTING↗

Scaled ILU Smoothers for Navier-Stokes Pressure Projection

Incomplete LU (ILU) smoothers are effective in the algebraic multigrid (AMG) V-cycle for reducing high-frequency components of the error. However, the requisite direct triangular solves are comparatively slow on GPUs. Previous work has demonstrated the advantages of Jacobi iteration as an alternative to direct solution of these systems. Depending on the threshold and fill-level parameters chosen, the factors can be highly nonnormal and Jacobi is unlikely to converge in a low number of iterations. We demonstrate that row scaling can reduce the departure from normality, allowing us to replace the inherently sequential solve with a rapidly converging Richardson iteration. There are several advantages beyond the lower compute time. Scaling is performed locally for a diagonal block of the global matrix because it is applied directly to the factor. Further, an ILUT Schur complement smoother maintains a constant GMRES iteration count as the number of MPI ranks increases, and thus parallel strong-scaling is improved. Our algorithms have been incorporated into hypre, and we demonstrate improved time to solution for linear systems arising in the Nalu-Wind and PeleLM pressure solvers. For large problem sizes, GMRES+AMG executes at least five times faster when using iterative triangular solves compared with direct solves on massively parallel GPUs.

algebraic multigrid↗

Reducing Communication in Algebraic Multigrid Using Additive Variants

Algebraic multigrid (AMG) has proven to be an effective scalable solver on many high performance computers. However, its increasing communication complexity on coarser levels has shown to seriously impact its performance on computers with high communication cost. Moreover, additive AMG variants provide not only increased parallelism as well as decreased numbers of messages per cycle but also generally exhibit slower convergence. Here we present various new additive variants with convergence rates that are significantly improved compared to the classical additive algebraic multigrid method and investigate their potential for decreased communication, and improved communication-computation overlap, features that are essential for good performance on future exascale architectures.

97 MATHEMATICS AND COMPUTING↗

Estimating posterior quantity of interest expectations in a multilevel scalable framework

Scalable approaches for uncertainty quantification are necessary for characterizing prediction confidence in large-scale subsurface flow simulations with uncertain permeability. To this end we explore a multilevel Monte Carlo approach for estimating posterior moments of a particular quantity of interest, where we employ an element-agglomerated algebraic multigrid (AMG) technique to generate the hierarchy of coarse spaces with guaranteed approximation properties for both the generation of spatially correlated random fields and the forward simulation of Darcy's law to model subsurface flow. In both these components (sampling and forward solves), we exploit solvers that rely on state-of-the-art scalable AMG. To illustrate the applicability of this approach, numerical tests are performed on two 3D examples-a unit cube and an egg-shaped domain with an irregular boundary-where the scalability of each simulation as well as the scalability of the overall algorithm are demonstrated.

97 MATHEMATICS AND COMPUTING↗

On the Performance of an Algebraic Multigrid Solver on Multicore Clusters

Algebraic multigrid (AMG) solvers have proven to be extremely efficient on distributed-memory architectures. However, when executed on modern multicore cluster architectures, we face new challenges that can significantly harm AMG's performance. We discuss our experiences on such an architecture and present a set of techniques that help users to overcome the associated problems, including thread and process pinning and correct memory associations. We have implemented most of the techniques in a MultiCore SUPport library (MCSup), which helps to map OpenMP applications to multicore machines. We present results using both an MPI-only and a hybrid MPI/OpenMP model.

99 GENERAL AND MISCELLANEOUS↗