A Critical Study of Agglomerated Multigrid Methods for Diffusion
NASA Technical Reports Server (NTRS)
Nishikawa, Hiroaki; Diskin, Boris; Thomas, James L.
2011-01-01
Agglomerated multigrid techniques used in unstructured-grid methods are studied critically for a model problem representative of laminar diffusion in the incompressible limit. The studied target-grid discretizations and discretizations used on agglomerated grids are typical of current node-centered formulations. Agglomerated multigrid convergence rates are presented using a range of two- and three-dimensional randomly perturbed unstructured grids for simple geometries with isotropic and stretched grids. Two agglomeration techniques are used within an overall topology-preserving agglomeration framework. The results show that multigrid with an inconsistent coarse-grid scheme using only the edge terms (also referred to in the literature as a thin-layer formulation) provides considerable speedup over single-grid methods but its convergence deteriorates on finer grids. Multigrid with a Galerkin coarse-grid discretization using piecewise-constant prolongation and a heuristic correction factor is slower and also grid-dependent. In contrast, grid-independent convergence rates are demonstrated for multigrid with consistent coarse-grid discretizations. Convergence rates of multigrid cycles are verified with quantitative analysis methods in which parts of the two-grid cycle are replaced by their idealized counterparts.
A Critical Study of Agglomerated Multigrid Methods for Diffusion
NASA Technical Reports Server (NTRS)
Thomas, James L.; Nishikawa, Hiroaki; Diskin, Boris
2009-01-01
Agglomerated multigrid techniques used in unstructured-grid methods are studied critically for a model problem representative of laminar diffusion in the incompressible limit. The studied target-grid discretizations and discretizations used on agglomerated grids are typical of current node-centered formulations. Agglomerated multigrid convergence rates are presented using a range of two- and three-dimensional randomly perturbed unstructured grids for simple geometries with isotropic and highly stretched grids. Two agglomeration techniques are used within an overall topology-preserving agglomeration framework. The results show that multigrid with an inconsistent coarse-grid scheme using only the edge terms (also referred to in the literature as a thin-layer formulation) provides considerable speedup over single-grid methods but its convergence deteriorates on finer grids. Multigrid with a Galerkin coarse-grid discretization using piecewise-constant prolongation and a heuristic correction factor is slower and also grid-dependent. In contrast, grid-independent convergence rates are demonstrated for multigrid with consistent coarse-grid discretizations. Actual cycle results are verified using quantitative analysis methods in which parts of the cycle are replaced by their idealized counterparts.
Development and Application of Agglomerated Multigrid Methods for Complex Geometries
NASA Technical Reports Server (NTRS)
Nishikawa, Hiroaki; Diskin, Boris; Thomas, James L.
2010-01-01
We report progress in the development of agglomerated multigrid techniques for fully un- structured grids in three dimensions, building upon two previous studies focused on efficiently solving a model diffusion equation. We demonstrate a robust fully-coarsened agglomerated multigrid technique for 3D complex geometries, incorporating the following key developments: consistent and stable coarse-grid discretizations, a hierarchical agglomeration scheme, and line-agglomeration/relaxation using prismatic-cell discretizations in the highly-stretched grid regions. A signi cant speed-up in computer time is demonstrated for a model diffusion problem, the Euler equations, and the Reynolds-averaged Navier-Stokes equations for 3D realistic complex geometries.
Unstructured multigrid through agglomeration
NASA Technical Reports Server (NTRS)
Venkatakrishnan, V.; Mavriplis, D. J.; Berger, M. J.
1993-01-01
In this work the compressible Euler equations are solved using finite volume techniques on unstructured grids. The spatial discretization employs a central difference approximation augmented by dissipative terms. Temporal discretization is done using a multistage Runge-Kutta scheme. A multigrid technique is used to accelerate convergence to steady state. The coarse grids are derived directly from the given fine grid through agglomeration of the control volumes. This agglomeration is accomplished by using a greedy-type algorithm and is done in such a way that the load, which is proportional to the number of edges, goes down by nearly a factor of 4 when moving from a fine to a coarse grid. The agglomeration algorithm has been implemented and the grids have been tested in a multigrid code. An area-weighted restriction is applied when moving from fine to coarse grids while a trivial injection is used for prolongation. Across a range of geometries and flows, it is shown that the agglomeration multigrid scheme compares very favorably with an unstructured multigrid algorithm that makes use of independent coarse meshes, both in terms of convergence and elapsed times.
Recent Advances in Agglomerated Multigrid
NASA Technical Reports Server (NTRS)
Nishikawa, Hiroaki; Diskin, Boris; Thomas, James L.; Hammond, Dana P.
2013-01-01
We report recent advancements of the agglomerated multigrid methodology for complex flow simulations on fully unstructured grids. An agglomerated multigrid solver is applied to a wide range of test problems from simple two-dimensional geometries to realistic three- dimensional configurations. The solver is evaluated against a single-grid solver and, in some cases, against a structured-grid multigrid solver. Grid and solver issues are identified and overcome, leading to significant improvements over single-grid solvers.
NASA Astrophysics Data System (ADS)
Langer, Stefan
2014-11-01
For unstructured finite volume methods an agglomeration multigrid with an implicit multistage Runge-Kutta method as a smoother is developed for solving the compressible Reynolds averaged Navier-Stokes (RANS) equations. The implicit Runge-Kutta method is interpreted as a preconditioned explicit Runge-Kutta method. The construction of the preconditioner is based on an approximate derivative. The linear systems are solved approximately with a symmetric Gauss-Seidel method. To significantly improve this solution method grid anisotropy is treated within the Gauss-Seidel iteration in such a way that the strong couplings in the linear system are resolved by tridiagonal systems constructed along these directions of strong coupling. The agglomeration strategy is adapted to this procedure by taking into account exactly these anisotropies in such a way that a directional coarsening is applied along these directions of strong coupling. Turbulence effects are included by a Spalart-Allmaras model, and the additional transport-type equation is approximately solved in a loosely coupled manner with the same method. For two-dimensional and three-dimensional numerical examples and a variety of differently generated meshes we show the wide range of applicability of the solution method. Finally, we exploit the GMRES method to determine approximate spectral information of the linearized RANS equations. This approximate spectral information is used to discuss and compare characteristics of multistage Runge-Kutta methods.
Agglomeration multigrid for viscous turbulent flows
NASA Technical Reports Server (NTRS)
Mavriplis, D. J.; Venkatakrishnan, V.
1994-01-01
Agglomeration multigrid, which has been demonstrated as an efficient and automatic technique for the solution of the Euler equations on unstructured meshes, is extended to viscous turbulent flows. For diffusion terms, coarse grid discretizations are not possible, and more accurate grid transfer operators are required as well. A Galerkin coarse grid operator construction and an implicit prolongation operator are proposed. Their suitability is evaluated by examining their effect on the solution of Laplace's equation. The resulting strategy is employed to solve the Reynolds-averaged Navier-Stokes equations for aerodynamic flows. Convergence rates comparable to those obtained by a previously developed non-nested mesh multigrid approach are demonstrated, and suggestions for further improvements are given.
Agglomeration multigrid for the three-dimensional Euler equations
NASA Technical Reports Server (NTRS)
Venkatakrishnan, V.; Mavriplis, D. J.
1994-01-01
A multigrid procedure that makes use of coarse grids generated by the agglomeration of control volumes is advocated as a practical approach for solving the three dimensional Euler equations on unstructured grids about complex configurations. It is shown that the agglomeration procedure can be tailored to achieve certain coarse grid properties such as the sizes of the coarse grids and aspect ratios of the coarse grid cells. The agglomeration is done as a preprocessing step and runs in linear time. The implications for multigrid of using arbitrary polyhedral coarse grids are discussed. The agglomeration multigrid technique compares very favorably with existing multigrid procedures both in terms of convergence rates and elapsed times. The main advantage of the present approach is the ease with which coarse grids of any desired degree of coarseness may be generated in three dimensions, without being constrained by considerations of geometry. Inviscid flows over a variety of complex configurations are computed using the agglomeration multigrid strategy.
Introduction to multigrid methods
NASA Technical Reports Server (NTRS)
Wesseling, P.
1995-01-01
These notes were written for an introductory course on the application of multigrid methods to elliptic and hyperbolic partial differential equations for engineers, physicists and applied mathematicians. The use of more advanced mathematical tools, such as functional analysis, is avoided. The course is intended to be accessible to a wide audience of users of computational methods. We restrict ourselves to finite volume and finite difference discretization. The basic principles are given. Smoothing methods and Fourier smoothing analysis are reviewed. The fundamental multigrid algorithm is studied. The smoothing and coarse grid approximation properties are discussed. Multigrid schedules and structured programming of multigrid algorithms are treated. Robustness and efficiency are considered.
Adaptive Algebraic Multigrid Methods
Brezina, M; Falgout, R; MacLachlan, S; Manteuffel, T; McCormick, S; Ruge, J
2004-04-09
Our ability to simulate physical processes numerically is constrained by our ability to solve the resulting linear systems, prompting substantial research into the development of multiscale iterative methods capable of solving these linear systems with an optimal amount of effort. Overcoming the limitations of geometric multigrid methods to simple geometries and differential equations, algebraic multigrid methods construct the multigrid hierarchy based only on the given matrix. While this allows for efficient black-box solution of the linear systems associated with discretizations of many elliptic differential equations, it also results in a lack of robustness due to assumptions made on the near-null spaces of these matrices. This paper introduces an extension to algebraic multigrid methods that removes the need to make such assumptions by utilizing an adaptive process. The principles which guide the adaptivity are highlighted, as well as their application to algebraic multigrid solution of certain symmetric positive-definite linear systems.
Agglomeration Multigrid for an Unstructured-Grid Flow Solver
NASA Technical Reports Server (NTRS)
Frink, Neal; Pandya, Mohagna J.
2004-01-01
An agglomeration multigrid scheme has been implemented into the sequential version of the NASA code USM3Dns, tetrahedral cell-centered finite volume Euler/Navier-Stokes flow solver. Efficiency and robustness of the multigrid-enhanced flow solver have been assessed for three configurations assuming an inviscid flow and one configuration assuming a viscous fully turbulent flow. The inviscid studies include a transonic flow over the ONERA M6 wing and a generic business jet with flow-through nacelles and a low subsonic flow over a high-lift trapezoidal wing. The viscous case includes a fully turbulent flow over the RAE 2822 rectangular wing. The multigrid solutions converged with 12%-33% of the Central Processing Unit (CPU) time required by the solutions obtained without multigrid. For all of the inviscid cases, multigrid in conjunction with an explicit time-stepping scheme performed the best with regard to the run time memory and CPU time requirements. However, for the viscous case multigrid had to be used with an implicit backward Euler time-stepping scheme that increased the run time memory requirement by 22% as compared to the run made without multigrid.
NASA Technical Reports Server (NTRS)
Marvriplis, D. J.; Venkatakrishnan, V.
1995-01-01
An agglomeration multigrid strategy is developed and implemented for the solution of three-dimensional steady viscous flows. The method enables convergence acceleration with minimal additional memory overheads, and is completely automated, in that it can deal with grids of arbitrary construction. The multigrid technique is validated by comparing the delivered convergence rates with those obtained by a previously developed overset-mesh multigrid approach, and by demonstrating grid independent convergence rates for aerodynamic problems on very large grids. Prospects for further increases in multigrid efficiency for high-Reynolds number viscous flows on highly stretched meshes are discussed.
Multigrid contact detection method
NASA Astrophysics Data System (ADS)
He, Kejing; Dong, Shoubin; Zhou, Zhaoyao
2007-03-01
Contact detection is a general problem of many physical simulations. This work presents a O(N) multigrid method for general contact detection problems (MGCD). The multigrid idea is integrated with contact detection problems. Both the time complexity and memory consumption of the MGCD are O(N) . Unlike other methods, whose efficiencies are influenced strongly by the object size distribution, the performance of MGCD is insensitive to the object size distribution. We compare the MGCD with the no binary search (NBS) method and the multilevel boxing method in three dimensions for both time complexity and memory consumption. For objects with similar size, the MGCD is as good as the NBS method, both of which outperform the multilevel boxing method regarding memory consumption. For objects with diverse size, the MGCD outperform both the NBS method and the multilevel boxing method. We use the MGCD to solve the contact detection problem for a granular simulation system based on the discrete element method. From this granular simulation, we get the density property of monosize packing and binary packing with size ratio equal to 10. The packing density for monosize particles is 0.636. For binary packing with size ratio equal to 10, when the number of small particles is 300 times as the number of big particles, the maximal packing density 0.824 is achieved.
Directional Agglomeration Multigrid Techniques for High-Reynolds Number Viscous Flows
NASA Technical Reports Server (NTRS)
Mavriplis, Dimitri J.
1998-01-01
A preconditioned directional-implicit agglomeration algorithm is developed for solving two- and three-dimensional viscous flows on highly anisotropic unstructured meshes of mixed-element types. The multigrid smoother consists of a pre-conditioned point- or line-implicit solver which operates on lines constructed in the unstructured mesh using a weighted graph algorithm. Directional coarsening or agglomeration is achieved using a similar weighted graph algorithm. A tight coupling of the line construction and directional agglomeration algorithms enables the use of aggressive coarsening ratios in the multigrid algorithm, which in turn reduces the cost of a multigrid cycle. Convergence rates which are independent of the degree of grid stretching are demonstrated in both two and three dimensions. Further improvement of the three-dimensional convergence rates through a GMRES technique is also demonstrated.
Directional Agglomeration Multigrid Techniques for High Reynolds Number Viscous Flow Solvers
NASA Technical Reports Server (NTRS)
1998-01-01
A preconditioned directional-implicit agglomeration algorithm is developed for solving two- and three-dimensional viscous flows on highly anisotropic unstructured meshes of mixed-element types. The multigrid smoother consists of a pre-conditioned point- or line-implicit solver which operates on lines constructed in the unstructured mesh using a weighted graph algorithm. Directional coarsening or agglomeration is achieved using a similar weighted graph algorithm. A tight coupling of the line construction and directional agglomeration algorithms enables the use of aggressive coarsening ratios in the multigrid algorithm, which in turn reduces the cost of a multigrid cycle. Convergence rates which are independent of the degree of grid stretching are demonstrated in both two and three dimensions. Further improvement of the three-dimensional convergence rates through a GMRES technique is also demonstrated.
Multigrid methods for isogeometric discretization.
Gahalaut, K P S; Kraus, J K; Tomar, S K
2013-01-01
We present (geometric) multigrid methods for isogeometric discretization of scalar second order elliptic problems. The smoothing property of the relaxation method, and the approximation property of the intergrid transfer operators are analyzed. These properties, when used in the framework of classical multigrid theory, imply uniform convergence of two-grid and multigrid methods. Supporting numerical results are provided for the smoothing property, the approximation property, convergence factor and iterations count for V-, W- and F-cycles, and the linear dependence of V-cycle convergence on the smoothing steps. For two dimensions, numerical results include the problems with variable coefficients, simple multi-patch geometry, a quarter annulus, and the dependence of convergence behavior on refinement levels [Formula: see text], whereas for three dimensions, only the constant coefficient problem in a unit cube is considered. The numerical results are complete up to polynomial order [Formula: see text], and for [Formula: see text] and [Formula: see text] smoothness. PMID:24511168
Multigrid methods for isogeometric discretization
Gahalaut, K.P.S.; Kraus, J.K.; Tomar, S.K.
2013-01-01
We present (geometric) multigrid methods for isogeometric discretization of scalar second order elliptic problems. The smoothing property of the relaxation method, and the approximation property of the intergrid transfer operators are analyzed. These properties, when used in the framework of classical multigrid theory, imply uniform convergence of two-grid and multigrid methods. Supporting numerical results are provided for the smoothing property, the approximation property, convergence factor and iterations count for V-, W- and F-cycles, and the linear dependence of V-cycle convergence on the smoothing steps. For two dimensions, numerical results include the problems with variable coefficients, simple multi-patch geometry, a quarter annulus, and the dependence of convergence behavior on refinement levels ℓ, whereas for three dimensions, only the constant coefficient problem in a unit cube is considered. The numerical results are complete up to polynomial order p=4, and for C0 and Cp-1 smoothness. PMID:24511168
Some Aspects of Multigrid Methods on Non-Structured Meshes
NASA Technical Reports Server (NTRS)
Guillard, H.; Marco, N.
1996-01-01
To solve a given fine mesh problem, the design of a multigrid method requires the definition of coarse levels, associated coarse grid operators and inter-grid transfer operators. For non-structured simplified meshes, these definitions can rely on the use of non-nested triangulations. These definitions can also be founded on agglomeration/aggregation techniques in a purely algebraic manner. This paper analyzes these two options, shows the connections of the volume-agglomeration method with algebraic methods and proposes a new definition of prolongation operator suitable for the application of the volume-agglomeration method to elliptic problems.
Parallel Element Agglomeration Algebraic Multigrid and Upscaling Library
Energy Science and Technology Software Center (ESTSC)
2015-02-19
ParFELAG is a parallel distributed memory C++ library for numerical upscaling of finite element discretizations. It provides optimal complesity algorithms ro build multilevel hierarchies and solvers that can be used for solving a wide class of partial differential equations (elliptic, hyperbolic, saddle point problems) on general unstructured mesh (under the assumption that the topology of the agglomerated entities is correct). Additionally, a novel multilevel solver for saddle point problems with divergence constraint is implemented.
The multigrid preconditioned conjugate gradient method
NASA Technical Reports Server (NTRS)
Tatebe, Osamu
1993-01-01
A multigrid preconditioned conjugate gradient method (MGCG method), which uses the multigrid method as a preconditioner of the PCG method, is proposed. The multigrid method has inherent high parallelism and improves convergence of long wavelength components, which is important in iterative methods. By using this method as a preconditioner of the PCG method, an efficient method with high parallelism and fast convergence is obtained. First, it is considered a necessary condition of the multigrid preconditioner in order to satisfy requirements of a preconditioner of the PCG method. Next numerical experiments show a behavior of the MGCG method and that the MGCG method is superior to both the ICCG method and the multigrid method in point of fast convergence and high parallelism. This fast convergence is understood in terms of the eigenvalue analysis of the preconditioned matrix. From this observation of the multigrid preconditioner, it is realized that the MGCG method converges in very few iterations and the multigrid preconditioner is a desirable preconditioner of the conjugate gradient method.
Fuel agglomerates and method of agglomeration
Wen, Wu-Wey
1986-01-01
Solid fuel agglomerates are prepared of particulate coal or other carbonaceous material with a binder having a high humic acid or humate salt content. The humic acid is extracted from oxidized carbonaceous material with a mild aqueous alkali solution of, for instance, ammonia. The particulate material is blended with the extract which serves as the binder for the agglomerates. The water-resistant agglomerates are formed such as by pelletizing, followed by drying to remove moisture and solidify the humic acid binder throughout the agglomerate.
A Parallel Multigrid Method for Neutronics Applications
Alcouffe, Raymond E.
2001-01-01
The multigrid method has been shown to be the most effective general method for solving the multi-dimensional diffusion equation encountered in neutronics. This being the method of choice, we develop a strategy for implementing the multigrid method on computers of massively parallel architecture. This leads us to strategies for parallelizing the relaxation, contraction (interpolation), and prolongation operators involved in the method. We then compare the efficiency of our parallel multigrid with other parallel methods for solving the diffusion equation on selected problems encountered in reactor physics.
Report on the Copper Mountain Conference on Multigrid Methods
2001-04-06
OAK B188 Report on the Copper Mountain Conference on Multigrid Methods. The Copper Mountain Conference on Multigrid Methods was held on April 11-16, 1999. Over 100 mathematicians from all over the world attended the meeting. The conference had two major themes: algebraic multigrid and parallel multigrid. During the five day meeting 69 talks on current research topics were presented as well as 3 tutorials. Talks with similar content were organized into sessions. Session topics included: Fluids; Multigrid and Multilevel Methods; Applications; PDE Reformulation; Inverse Problems; Special Methods; Decomposition Methods; Student Paper Winners; Parallel Multigrid; Parallel Algebraic Multigrid; and FOSLS.
Extending the applicability of multigrid methods
Brannick, J; Brezina, M; Falgout, R; Manteuffel, T; McCormick, S; Ruge, J; Sheehan, B; Xu, J; Zikatanov, L
2006-09-25
Multigrid methods are ideal for solving the increasingly large-scale problems that arise in numerical simulations of physical phenomena because of their potential for computational costs and memory requirements that scale linearly with the degrees of freedom. Unfortunately, they have been historically limited by their applicability to elliptic-type problems and the need for special handling in their implementation. In this paper, we present an overview of several recent theoretical and algorithmic advances made by the TOPS multigrid partners and their collaborators in extending applicability of multigrid methods. Specific examples that are presented include quantum chromodynamics, radiation transport, and electromagnetics.
A multigrid method for the Euler equations
NASA Technical Reports Server (NTRS)
Jespersen, D. C.
1983-01-01
A multigrid algorithm has been developed for the numerical solution of the steady two-dimensional Euler equations. Flux vector splitting and one-sided differencing are employed to define the spatial discretization. Newton's method is used to solve the nonlinear equations, and a multigrid solver is used on each linear problem. The relaxation scheme for the linear problems is symmetric Gauss-Seidel. Standard restriction and interpolation operators are employed. Local mode analysis is used to predict the convergence rate of the multigrid process on the linear problems. Computed results for transonic flows over airfoils are presented.
A multigrid method for variational inequalities
Oliveira, S.; Stewart, D.E.; Wu, W.
1996-12-31
Multigrid methods have been used with great success for solving elliptic partial differential equations. Penalty methods have been successful in solving finite-dimensional quadratic programs. In this paper these two techniques are combined to give a fast method for solving obstacle problems. A nonlinear penalized problem is solved using Newton`s method for large values of a penalty parameter. Multigrid methods are used to solve the linear systems in Newton`s method. The overall numerical method developed is based on an exterior penalty function, and numerical results showing the performance of the method have been obtained.
Multigrid methods with applications to reservoir simulation
Xiao, Shengyou
1994-05-01
Multigrid methods are studied for solving elliptic partial differential equations. Focus is on parallel multigrid methods and their use for reservoir simulation. Multicolor Fourier analysis is used to analyze the behavior of standard multigrid methods for problems in one and two dimensions. Relation between multicolor and standard Fourier analysis is established. Multiple coarse grid methods for solving model problems in 1 and 2 dimensions are considered; at each coarse grid level we use more than one coarse grid to improve convergence. For a given Dirichlet problem, a related extended problem is first constructed; a purification procedure can be used to obtain Moore-Penrose solutions of the singular systems encountered. For solving anisotropic equations, semicoarsening and line smoothing techniques are used with multiple coarse grid methods to improve convergence. Two-level convergence factors are estimated using multicolor. In the case where each operator has the same stencil on each grid point on one level, exact multilevel convergence factors can be obtained. For solving partial differential equations with discontinuous coefficients, interpolation and restriction operators should include information about the equation coefficients. Matrix-dependent interpolation and restriction operators based on the Schur complement can be used in nonsymmetric cases. A semicoarsening multigrid solver with these operators is used in UTCOMP, a 3-D, multiphase, multicomponent, compositional reservoir simulator. The numerical experiments are carried out on different computing systems. Results indicate that the multigrid methods are promising.
Spectral multigrid methods for elliptic equations
NASA Technical Reports Server (NTRS)
Zang, T. A.; Wong, Y. S.; Hussaini, M. Y.
1981-01-01
An alternative approach which employs multigrid concepts in the iterative solution of spectral equations was examined. Spectral multigrid methods are described for self adjoint elliptic equations with either periodic or Dirichlet boundary conditions. For realistic fluid calculations the relevant boundary conditions are periodic in at least one (angular) coordinate and Dirichlet (or Neumann) in the remaining coordinates. Spectral methods are always effective for flows in strictly rectangular geometries since corners generally introduce singularities into the solution. If the boundary is smooth, then mapping techniques are used to transform the problem into one with a combination of periodic and Dirichlet boundary conditions. It is suggested that spectral multigrid methods in these geometries can be devised by combining the techniques.
Multigrid Methods for Nonlinear Problems: An Overview
Henson, V E
2002-12-23
Since their early application to elliptic partial differential equations, multigrid methods have been applied successfully to a large and growing class of problems, from elasticity and computational fluid dynamics to geodetics and molecular structures. Classical multigrid begins with a two-grid process. First, iterative relaxation is applied, whose effect is to smooth the error. Then a coarse-grid correction is applied, in which the smooth error is determined on a coarser grid. This error is interpolated to the fine grid and used to correct the fine-grid approximation. Applying this method recursively to solve the coarse-grid problem leads to multigrid. The coarse-grid correction works because the residual equation is linear. But this is not the case for nonlinear problems, and different strategies must be employed. In this presentation we describe how to apply multigrid to nonlinear problems. There are two basic approaches. The first is to apply a linearization scheme, such as the Newton's method, and to employ multigrid for the solution of the Jacobian system in each iteration. The second is to apply multigrid directly to the nonlinear problem by employing the so-called Full Approximation Scheme (FAS). In FAS a nonlinear iteration is applied to smooth the error. The full equation is solved on the coarse grid, after which the coarse-grid error is extracted from the solution. This correction is then interpolated and applied to the fine grid approximation. We describe these methods in detail, and present numerical experiments that indicate the efficacy of them.
Spectral multigrid methods for elliptic equations II
NASA Technical Reports Server (NTRS)
Zang, T. A.; Wong, Y. S.; Hussaini, M. Y.
1984-01-01
A detailed description of spectral multigrid methods is provided. This includes the interpolation and coarse-grid operators for both periodic and Dirichlet problems. The spectral methods for periodic problems use Fourier series and those for Dirichlet problems are based upon Chebyshev polynomials. An improved preconditioning for Dirichlet problems is given. Numerical examples and practical advice are included.
Spectral multigrid methods for elliptic equations 2
NASA Technical Reports Server (NTRS)
Zang, T. A.; Wong, Y. S.; Hussaini, M. Y.
1983-01-01
A detailed description of spectral multigrid methods is provided. This includes the interpolation and coarse-grid operators for both periodic and Dirichlet problems. The spectral methods for periodic problems use Fourier series and those for Dirichlet problems are based upon Chebyshev polynomials. An improved preconditioning for Dirichlet problems is given. Numerical examples and practical advice are included.
Relaxation schemes for Chebyshev spectral multigrid methods
NASA Technical Reports Server (NTRS)
Kang, Yimin; Fulton, Scott R.
1993-01-01
Two relaxation schemes for Chebyshev spectral multigrid methods are presented for elliptic equations with Dirichlet boundary conditions. The first scheme is a pointwise-preconditioned Richardson relaxation scheme and the second is a line relaxation scheme. The line relaxation scheme provides an efficient and relatively simple approach for solving two-dimensional spectral equations. Numerical examples and comparisons with other methods are given.
Acoustic agglomeration methods and apparatus
NASA Technical Reports Server (NTRS)
Barmatz, M. B. (Inventor)
1984-01-01
Methods are described for using acoustic energy to agglomerate fine particles on the order of one micron diameter that are suspended in gas, to provide agglomerates large enough for efficient removal by other techniques. The gas with suspended particles, is passed through the length of a chamber while acoustic energy at a resonant chamber mode is applied to set up one or more acoustic standing wave patterns that vibrate the suspended particles to bring them together so they agglomerate. Several widely different frequencies can be applied to efficiently vibrate particles of widely differing sizes. The standing wave pattern can be applied along directions transversed to the flow of the gas. The particles can be made to move in circles by applying acoustic energy in perpendicular directions with the energy in both directions being of the same wavelength but 90 deg out of phase.
Multigrid Methods for Mesh Relaxation
O'Brien, M J
2006-06-12
When generating a mesh for the initial conditions for a computer simulation, you want the mesh to be as smooth as possible. A common practice is to use equipotential mesh relaxation to smooth out a distorted computational mesh. Typically a Laplace-like equation is set up for the mesh coordinates and then one or more Jacobi iterations are performed to relax the mesh. As the zone count gets really large, the Jacobi iteration becomes less and less effective and we are stuck with our original unrelaxed mesh. This type of iteration can only damp high frequency errors and the smooth errors remain. When the zone count is large, almost everything looks smooth so relaxation cannot solve the problem. In this paper we examine a multigrid technique which effectively smooths out the mesh, independent of the number of zones.
Multigrid Methods in Electronic Structure Calculations
NASA Astrophysics Data System (ADS)
Briggs, Emil
1996-03-01
Multigrid techniques have become the method of choice for a broad range of computational problems. Their use in electronic structure calculations introduces a new set of issues when compared to traditional plane wave approaches. We have developed a set of techniques that address these issues and permit multigrid algorithms to be applied to the electronic structure problem in an efficient manner. In our approach the Kohn-Sham equations are discretized on a real-space mesh using a compact representation of the Hamiltonian. The resulting equations are solved directly on the mesh using multigrid iterations. This produces rapid convergence rates even for ill-conditioned systems with large length and/or energy scales. The method has been applied to both periodic and non-periodic systems containing over 400 atoms and the results are in very good agreement with both theory and experiment. Example applications include a vacancy in diamond, an isolated C60 molecule, and a 64-atom cell of GaN with the Ga d-electrons in valence which required a 250 Ry cutoff. A particular strength of a real-space multigrid approach is its ready adaptability to massively parallel computer architectures. The compact representation of the Hamiltonian is especially well suited to such machines. Tests on the Cray-T3D have shown nearly linear scaling of the execution time up to the maximum number of processors (512). The MPP implementation has been used for studies of a large Amyloid Beta Peptide (C_146O_45N_42H_210) found in the brains of Alzheimers disease patients. Further applications of the multigrid method will also be described. (in collaboration D. J. Sullivan and J. Bernholc)
Grandchild of the frequency: Decomposition multigrid method
Dendy, J.E. Jr.; Tazartes, C.C.
1994-12-31
Previously the authors considered the frequency decomposition multigrid method and rejected it because it was not robust for problems with discontinuous coefficients. In this paper they show how to modify the method so as to obtain such robustness while retaining robustness for problems with anisotropic coefficients. They also discuss application of this method to a problem arising in global ocean modeling on the CM-5.
On Some Versions of the Element Agglomeration AMGe Method
Lashuk, I; Vassilevski, P
2007-08-09
The present paper deals with element-based AMG methods that target linear systems of equations coming from finite element discretizations of elliptic PDEs. The individual element information (element matrices and element topology) is the main input to construct the AMG hierarchy. We study a number of variants of the spectral agglomerate element based AMG method. The core of the algorithms relies on element agglomeration utilizing the element topology (built recursively from fine to coarse levels). The actual selection of the coarse degrees of freedom (dofs) is based on solving large number of local eigenvalue problems. Additionally, we investigate strategies for adaptive AMG as well as multigrid cycles that are more expensive than the V-cycle utilizing simple interpolation matrices and nested conjugate gradient (CG) based recursive calls between the levels. The presented algorithms are illustrated with an extensive set of experiments based on a matlab implementation of the methods.
The multigrid method: Fast relaxation
NASA Technical Reports Server (NTRS)
South, J. C., Jr.; Brandt, A.
1976-01-01
A multi-level grid method was studied as a possible means of accelerating convergence in relaxation calculations for transonic flows. The method employs a hierarchy of grids, ranging from very coarse (e.g. 4 x 2 mesh cells) to fine (e.g. 64 x 32); the coarser grids are used to diminish the magnitude of the smooth part of the residuals, hopefully with far less total work than would be required with optimal iterations on the finest grid. To date the method was applied quite successfully to the solution of the transonic small-disturbance equation for the velocity potential in conservation form. Nonlifting transonic flow past a parabolic arc airfoil is the example studied, with meshes of both constant and variable step size.
Implementing abstract multigrid or multilevel methods
NASA Technical Reports Server (NTRS)
Douglas, Craig C.
1993-01-01
Multigrid methods can be formulated as an algorithm for an abstract problem that is independent of the partial differential equation, domain, and discretization method. In such an abstract setting, problems not arising from partial differential equations can be treated. A general theory exists for linear problems. The general theory was motivated by a series of abstract solvers (Madpack). The latest version was motivated by the theory. Madpack now allows for a wide variety of iterative and direct solvers, preconditioners, and interpolation and projection schemes, including user callback ones. It allows for sparse, dense, and stencil matrices. Mildly nonlinear problems can be handled. Also, there is a fast, multigrid Poisson solver (two and three dimensions). The type of solvers and design decisions (including language, data structures, external library support, and callbacks) are discussed. Based on the author's experiences with two versions of Madpack, a better approach is proposed. This is based on a mixed language formulation (C and FORTRAN + preprocessor). Reasons for not using FORTRAN, C, or C++ (individually) are given. Implementing the proposed strategy is not difficult.
Lecture Notes on Multigrid Methods
Vassilevski, P S
2010-06-28
The Lecture Notes are primarily based on a sequence of lectures given by the author while been a Fulbright scholar at 'St. Kliment Ohridski' University of Sofia, Sofia, Bulgaria during the winter semester of 2009-2010 academic year. The notes are somewhat expanded version of the actual one semester class he taught there. The material covered is slightly modified and adapted version of similar topics covered in the author's monograph 'Multilevel Block-Factorization Preconditioners' published in 2008 by Springer. The author tried to keep the notes as self-contained as possible. That is why the lecture notes begin with some basic introductory matrix-vector linear algebra, numerical PDEs (finite element) facts emphasizing the relations between functions in finite dimensional spaces and their coefficient vectors and respective norms. Then, some additional facts on the implementation of finite elements based on relation tables using the popular compressed sparse row (CSR) format are given. Also, typical condition number estimates of stiffness and mass matrices, the global matrix assembly from local element matrices are given as well. Finally, some basic introductory facts about stationary iterative methods, such as Gauss-Seidel and its symmetrized version are presented. The introductory material ends up with the smoothing property of the classical iterative methods and the main definition of two-grid iterative methods. From here on, the second part of the notes begins which deals with the various aspects of the principal TG and the numerous versions of the MG cycles. At the end, in part III, we briefly introduce algebraic versions of MG referred to as AMG, focusing on classes of AMG specialized for finite element matrices.
Vandewalle, S.
1994-12-31
Time-stepping methods for parabolic partial differential equations are essentially sequential. This prohibits the use of massively parallel computers unless the problem on each time-level is very large. This observation has led to the development of algorithms that operate on more than one time-level simultaneously; that is to say, on grids extending in space and in time. The so-called parabolic multigrid methods solve the time-dependent parabolic PDE as if it were a stationary PDE discretized on a space-time grid. The author has investigated the use of multigrid waveform relaxation, an algorithm developed by Lubich and Ostermann. The algorithm is based on a multigrid acceleration of waveform relaxation, a highly concurrent technique for solving large systems of ordinary differential equations. Another method of this class is the time-parallel multigrid method. This method was developed by Hackbusch and was recently subject of further study by Horton. It extends the elliptic multigrid idea to the set of equations that is derived by discretizing a parabolic problem in space and in time.
Semi-coarsening multigrid methods for parallel computing
Jones, J.E.
1996-12-31
Standard multigrid methods are not well suited for problems with anisotropic coefficients which can occur, for example, on grids that are stretched to resolve a boundary layer. There are several different modifications of the standard multigrid algorithm that yield efficient methods for anisotropic problems. In the paper, we investigate the parallel performance of these multigrid algorithms. Multigrid algorithms which work well for anisotropic problems are based on line relaxation and/or semi-coarsening. In semi-coarsening multigrid algorithms a grid is coarsened in only one of the coordinate directions unlike standard or full-coarsening multigrid algorithms where a grid is coarsened in each of the coordinate directions. When both semi-coarsening and line relaxation are used, the resulting multigrid algorithm is robust and automatic in that it requires no knowledge of the nature of the anisotropy. This is the basic multigrid algorithm whose parallel performance we investigate in the paper. The algorithm is currently being implemented on an IBM SP2 and its performance is being analyzed. In addition to looking at the parallel performance of the basic semi-coarsening algorithm, we present algorithmic modifications with potentially better parallel efficiency. One modification reduces the amount of computational work done in relaxation at the expense of using multiple coarse grids. This modification is also being implemented with the aim of comparing its performance to that of the basic semi-coarsening algorithm.
Preconditioners for the spectral multigrid method
NASA Technical Reports Server (NTRS)
Phillips, T. N.; Zang, T. A.; Hussaini, M. Y.
1983-01-01
The systems of algebraic equations which arise from spectral discretizations of elliptic equations are full and direct solutions of them are rarely feasible. Iterative methods are an attractive alternative because Fourier transform techniques enable the discrete matrix-vector products to be computed with nearly the same efficiency as is possible for corresponding but sparse finite difference discretizations. For realistic Dirichlet problems preconditioning is essential for acceptable convergence rates. A brief description of Chebyshev spectral approximations and spectral multigrid methods for elliptic problems is given. A survey of preconditioners for Dirichlet problems based on second-order finite difference methods is made. New preconditioning techniques based on higher order finite differences and on the spectral matrix itself are presented. The preconditioners are analyzed in terms of their spectra and numerical examples are presented.
Preconditioners for the spectral multigrid method
NASA Technical Reports Server (NTRS)
Phillips, T. N.; Hussaini, M. Y.; Zang, T. A.
1986-01-01
The systems of algebraic equations which arise from spectral discretizations of elliptic equations are full and direct solutions of them are rarely feasible. Iterative methods are an attractive alternative because Fourier transform techniques enable the discrete matrix-vector products to be computed with nearly the same efficiency as is possible for corresponding but sparse finite difference discretizations. For realistic Dirichlet problem preconditioning is essential for acceptable convergence rates. A brief description of Chebyshev spectral approximations and spectral multigrid methods for elliptic problems is given. A survey of preconditioners for Dirichlet problems based on second-order finite difference methods is made. New preconditioning techniques based on higher order finite differences and on the spectral matrix itself are presented. The preconditioners are analyzed in terms of their spectra and numerical examples are presented.
Layout optimization with algebraic multigrid methods
NASA Technical Reports Server (NTRS)
Regler, Hans; Ruede, Ulrich
1993-01-01
Finding the optimal position for the individual cells (also called functional modules) on the chip surface is an important and difficult step in the design of integrated circuits. This paper deals with the problem of relative placement, that is the minimization of a quadratic functional with a large, sparse, positive definite system matrix. The basic optimization problem must be augmented by constraints to inhibit solutions where cells overlap. Besides classical iterative methods, based on conjugate gradients (CG), we show that algebraic multigrid methods (AMG) provide an interesting alternative. For moderately sized examples with about 10000 cells, AMG is already competitive with CG and is expected to be superior for larger problems. Besides the classical 'multiplicative' AMG algorithm where the levels are visited sequentially, we propose an 'additive' variant of AMG where levels may be treated in parallel and that is suitable as a preconditioner in the CG algorithm.
Convergence acceleration of the Proteus computer code with multigrid methods
NASA Technical Reports Server (NTRS)
Demuren, A. O.; Ibraheem, S. O.
1995-01-01
This report presents the results of a study to implement convergence acceleration techniques based on the multigrid concept in the two-dimensional and three-dimensional versions of the Proteus computer code. The first section presents a review of the relevant literature on the implementation of the multigrid methods in computer codes for compressible flow analysis. The next two sections present detailed stability analysis of numerical schemes for solving the Euler and Navier-Stokes equations, based on conventional von Neumann analysis and the bi-grid analysis, respectively. The next section presents details of the computational method used in the Proteus computer code. Finally, the multigrid implementation and applications to several two-dimensional and three-dimensional test problems are presented. The results of the present study show that the multigrid method always leads to a reduction in the number of iterations (or time steps) required for convergence. However, there is an overhead associated with the use of multigrid acceleration. The overhead is higher in 2-D problems than in 3-D problems, thus overall multigrid savings in CPU time are in general better in the latter. Savings of about 40-50 percent are typical in 3-D problems, but they are about 20-30 percent in large 2-D problems. The present multigrid method is applicable to steady-state problems and is therefore ineffective in problems with inherently unstable solutions.
Convergence acceleration of the Proteus computer code with multigrid methods
NASA Technical Reports Server (NTRS)
Demuren, A. O.; Ibraheem, S. O.
1992-01-01
Presented here is the first part of a study to implement convergence acceleration techniques based on the multigrid concept in the Proteus computer code. A review is given of previous studies on the implementation of multigrid methods in computer codes for compressible flow analysis. Also presented is a detailed stability analysis of upwind and central-difference based numerical schemes for solving the Euler and Navier-Stokes equations. Results are given of a convergence study of the Proteus code on computational grids of different sizes. The results presented here form the foundation for the implementation of multigrid methods in the Proteus code.
Spectral multigrid methods with applications to transonic potential flow
NASA Technical Reports Server (NTRS)
Streett, C. L.; Zang, T. A.; Hussaini, M. Y.
1983-01-01
Spectral multigrid methods are demonstrated to be a competitive technique for solving the transonic potential flow equation. The spectral discretization, the relaxation scheme, and the multigrid techniques are described in detail. Significant departures from current approaches are first illustrated on several linear problems. The principal applications and examples, however, are for compressible potential flow. These examples include the relatively challenging case of supercritical flow over a lifting airfoil.
Spectral multigrid methods with applications to transonic potential flow
NASA Technical Reports Server (NTRS)
Streett, C. L.; Zang, T. A.; Hussaini, M. Y.
1985-01-01
Spectral multigrid methods are demonstrated to be a competitive technique for solving the transonic potential flow equation. The spectral discretization, the relaxation scheme, and the multigrid techniques are described in detail. Significant departures from current approaches are first illustrated on several linear problems. The principal applications and examples, however, are for compressible potential flow. These examples include the relatively challenging case of supercritical flow over a lifting airfoil.
The mixed finite element multigrid method for stokes equations.
Muzhinji, K; Shateyi, S; Motsa, S S
2015-01-01
The stable finite element discretization of the Stokes problem produces a symmetric indefinite system of linear algebraic equations. A variety of iterative solvers have been proposed for such systems in an attempt to construct efficient, fast, and robust solution techniques. This paper investigates one of such iterative solvers, the geometric multigrid solver, to find the approximate solution of the indefinite systems. The main ingredient of the multigrid method is the choice of an appropriate smoothing strategy. This study considers the application of different smoothers and compares their effects in the overall performance of the multigrid solver. We study the multigrid method with the following smoothers: distributed Gauss Seidel, inexact Uzawa, preconditioned MINRES, and Braess-Sarazin type smoothers. A comparative study of the smoothers shows that the Braess-Sarazin smoothers enhance good performance of the multigrid method. We study the problem in a two-dimensional domain using stable Hood-Taylor Q2-Q1 pair of finite rectangular elements. We also give the main theoretical convergence results. We present the numerical results to demonstrate the efficiency and robustness of the multigrid method and confirm the theoretical results. PMID:25945361
The Mixed Finite Element Multigrid Method for Stokes Equations
Muzhinji, K.; Shateyi, S.; Motsa, S. S.
2015-01-01
The stable finite element discretization of the Stokes problem produces a symmetric indefinite system of linear algebraic equations. A variety of iterative solvers have been proposed for such systems in an attempt to construct efficient, fast, and robust solution techniques. This paper investigates one of such iterative solvers, the geometric multigrid solver, to find the approximate solution of the indefinite systems. The main ingredient of the multigrid method is the choice of an appropriate smoothing strategy. This study considers the application of different smoothers and compares their effects in the overall performance of the multigrid solver. We study the multigrid method with the following smoothers: distributed Gauss Seidel, inexact Uzawa, preconditioned MINRES, and Braess-Sarazin type smoothers. A comparative study of the smoothers shows that the Braess-Sarazin smoothers enhance good performance of the multigrid method. We study the problem in a two-dimensional domain using stable Hood-Taylor Q2-Q1 pair of finite rectangular elements. We also give the main theoretical convergence results. We present the numerical results to demonstrate the efficiency and robustness of the multigrid method and confirm the theoretical results. PMID:25945361
Multigrid Methods for Fully Implicit Oil Reservoir Simulation
NASA Technical Reports Server (NTRS)
Molenaar, J.
1996-01-01
In this paper we consider the simultaneous flow of oil and water in reservoir rock. This displacement process is modeled by two basic equations: the material balance or continuity equations and the equation of motion (Darcy's law). For the numerical solution of this system of nonlinear partial differential equations there are two approaches: the fully implicit or simultaneous solution method and the sequential solution method. In the sequential solution method the system of partial differential equations is manipulated to give an elliptic pressure equation and a hyperbolic (or parabolic) saturation equation. In the IMPES approach the pressure equation is first solved, using values for the saturation from the previous time level. Next the saturations are updated by some explicit time stepping method; this implies that the method is only conditionally stable. For the numerical solution of the linear, elliptic pressure equation multigrid methods have become an accepted technique. On the other hand, the fully implicit method is unconditionally stable, but it has the disadvantage that in every time step a large system of nonlinear algebraic equations has to be solved. The most time-consuming part of any fully implicit reservoir simulator is the solution of this large system of equations. Usually this is done by Newton's method. The resulting systems of linear equations are then either solved by a direct method or by some conjugate gradient type method. In this paper we consider the possibility of applying multigrid methods for the iterative solution of the systems of nonlinear equations. There are two ways of using multigrid for this job: either we use a nonlinear multigrid method or we use a linear multigrid method to deal with the linear systems that arise in Newton's method. So far only a few authors have reported on the use of multigrid methods for fully implicit simulations. Two-level FAS algorithm is presented for the black-oil equations, and linear multigrid for
Multigrid Methods for Aerodynamic Problems in Complex Geometries
NASA Technical Reports Server (NTRS)
Caughey, David A.
1995-01-01
Work has been directed at the development of efficient multigrid methods for the solution of aerodynamic problems involving complex geometries, including the development of computational methods for the solution of both inviscid and viscous transonic flow problems. The emphasis is on problems of complex, three-dimensional geometry. The methods developed are based upon finite-volume approximations to both the Euler and the Reynolds-Averaged Navier-Stokes equations. The methods are developed for use on multi-block grids using diagonalized implicit multigrid methods to achieve computational efficiency. The work is focused upon aerodynamic problems involving complex geometries, including advanced engine inlets.
Final report on the Copper Mountain conference on multigrid methods
1997-10-01
The Copper Mountain Conference on Multigrid Methods was held on April 6-11, 1997. It took the same format used in the previous Copper Mountain Conferences on Multigrid Method conferences. Over 87 mathematicians from all over the world attended the meeting. 56 half-hour talks on current research topics were presented. Talks with similar content were organized into sessions. Session topics included: fluids; domain decomposition; iterative methods; basics; adaptive methods; non-linear filtering; CFD; applications; transport; algebraic solvers; supercomputing; and student paper winners.
Parallel Algebraic Multigrid Methods - High Performance Preconditioners
Yang, U M
2004-11-11
The development of high performance, massively parallel computers and the increasing demands of computationally challenging applications have necessitated the development of scalable solvers and preconditioners. One of the most effective ways to achieve scalability is the use of multigrid or multilevel techniques. Algebraic multigrid (AMG) is a very efficient algorithm for solving large problems on unstructured grids. While much of it can be parallelized in a straightforward way, some components of the classical algorithm, particularly the coarsening process and some of the most efficient smoothers, are highly sequential, and require new parallel approaches. This chapter presents the basic principles of AMG and gives an overview of various parallel implementations of AMG, including descriptions of parallel coarsening schemes and smoothers, some numerical results as well as references to existing software packages.
A multigrid solution method for mixed hybrid finite elements
Schmid, W.
1996-12-31
We consider the multigrid solution of linear equations arising within the discretization of elliptic second order boundary value problems of the form by mixed hybrid finite elements. Using the equivalence of mixed hybrid finite elements and non-conforming nodal finite elements, we construct a multigrid scheme for the corresponding non-conforming finite elements, and, by this equivalence, for the mixed hybrid finite elements, following guidelines from Arbogast/Chen. For a rectangular triangulation of the computational domain, this non-conforming schemes are the so-called nodal finite elements. We explicitly construct prolongation and restriction operators for this type of non-conforming finite elements. We discuss the use of plain multigrid and the multilevel-preconditioned cg-method and compare their efficiency in numerical tests.
Seventh Copper Mountain Conference on Multigrid Methods. Part 2
NASA Technical Reports Server (NTRS)
Melson, N. Duane (Editor); Manteuffel, Tom A. (Editor); McCormick, Steve F. (Editor); Douglas, Craig C. (Editor)
1996-01-01
The Seventh Copper Mountain Conference on Multigrid Methods was held on April 2-7, 1995 at Copper Mountain, Colorado. This book is a collection of many of the papers presented at the conference and so represents the conference proceedings. NASA Langley graciously provided printing of this document so that all of the papers could be presented in a single forum. Each paper was reviewed by a member of the conference organizing committee under the coordination of the editors. The vibrancy and diversity in this field are amply expressed in these important papers, and the collection clearly shows the continuing rapid growth of the use of multigrid acceleration techniques.
Geometric multigrid for an implicit-time immersed boundary method
Guy, Robert D.; Philip, Bobby; Griffith, Boyce E.
2014-10-12
The immersed boundary (IB) method is an approach to fluid-structure interaction that uses Lagrangian variables to describe the deformations and resulting forces of the structure and Eulerian variables to describe the motion and forces of the fluid. Explicit time stepping schemes for the IB method require solvers only for Eulerian equations, for which fast Cartesian grid solution methods are available. Such methods are relatively straightforward to develop and are widely used in practice but often require very small time steps to maintain stability. Implicit-time IB methods permit the stable use of large time steps, but efficient implementations of such methods require significantly more complex solvers that effectively treat both Lagrangian and Eulerian variables simultaneously. Moreover, several different approaches to solving the coupled Lagrangian-Eulerian equations have been proposed, but a complete understanding of this problem is still emerging. This paper presents a geometric multigrid method for an implicit-time discretization of the IB equations. This multigrid scheme uses a generalization of box relaxation that is shown to handle problems in which the physical stiffness of the structure is very large. Numerical examples are provided to illustrate the effectiveness and efficiency of the algorithms described herein. Finally, these tests show that using multigrid as a preconditioner for a Krylov method yields improvements in both robustness and efficiency as compared to using multigrid as a solver. They also demonstrate that with a time step 100–1000 times larger than that permitted by an explicit IB method, the multigrid-preconditioned implicit IB method is approximately 50–200 times more efficient than the explicit method.
Geometric multigrid for an implicit-time immersed boundary method
Guy, Robert D.; Philip, Bobby; Griffith, Boyce E.
2014-10-12
The immersed boundary (IB) method is an approach to fluid-structure interaction that uses Lagrangian variables to describe the deformations and resulting forces of the structure and Eulerian variables to describe the motion and forces of the fluid. Explicit time stepping schemes for the IB method require solvers only for Eulerian equations, for which fast Cartesian grid solution methods are available. Such methods are relatively straightforward to develop and are widely used in practice but often require very small time steps to maintain stability. Implicit-time IB methods permit the stable use of large time steps, but efficient implementations of such methodsmore » require significantly more complex solvers that effectively treat both Lagrangian and Eulerian variables simultaneously. Moreover, several different approaches to solving the coupled Lagrangian-Eulerian equations have been proposed, but a complete understanding of this problem is still emerging. This paper presents a geometric multigrid method for an implicit-time discretization of the IB equations. This multigrid scheme uses a generalization of box relaxation that is shown to handle problems in which the physical stiffness of the structure is very large. Numerical examples are provided to illustrate the effectiveness and efficiency of the algorithms described herein. Finally, these tests show that using multigrid as a preconditioner for a Krylov method yields improvements in both robustness and efficiency as compared to using multigrid as a solver. They also demonstrate that with a time step 100–1000 times larger than that permitted by an explicit IB method, the multigrid-preconditioned implicit IB method is approximately 50–200 times more efficient than the explicit method.« less
Multigrid methods for bifurcation problems: The self adjoint case
NASA Technical Reports Server (NTRS)
Taasan, Shlomo
1987-01-01
This paper deals with multigrid methods for computational problems that arise in the theory of bifurcation and is restricted to the self adjoint case. The basic problem is to solve for arcs of solutions, a task that is done successfully with an arc length continuation method. Other important issues are, for example, detecting and locating singular points as part of the continuation process, switching branches at bifurcation points, etc. Multigrid methods have been applied to continuation problems. These methods work well at regular points and at limit points, while they may encounter difficulties in the vicinity of bifurcation points. A new continuation method that is very efficient also near bifurcation points is presented here. The other issues mentioned above are also treated very efficiently with appropriate multigrid algorithms. For example, it is shown that limit points and bifurcation points can be solved for directly by a multigrid algorithm. Moreover, the algorithms presented here solve the corresponding problems in just a few work units (about 10 or less), where a work unit is the work involved in one local relaxation on the finest grid.
NASA Technical Reports Server (NTRS)
Dinar, N.
1978-01-01
Several aspects of multigrid methods are briefly described. The main subjects include the development of very efficient multigrid algorithms for systems of elliptic equations (Cauchy-Riemann, Stokes, Navier-Stokes), as well as the development of control and prediction tools (based on local mode Fourier analysis), used to analyze, check and improve these algorithms. Preliminary research on multigrid algorithms for time dependent parabolic equations is also described. Improvements in existing multigrid processes and algorithms for elliptic equations were studied.
A multigrid nonoscillatory method for computing high speed flows
NASA Technical Reports Server (NTRS)
Li, C. P.; Shieh, T. H.
1993-01-01
A multigrid method using different smoothers has been developed to solve the Euler equations discretized by a nonoscillatory scheme up to fourth order accuracy. The best smoothing property is provided by a five-stage Runge-Kutta technique with optimized coefficients, yet the most efficient smoother is a backward Euler technique in factored and diagonalized form. The singlegrid solution for a hypersonic, viscous conic flow is in excellent agreement with the solution obtained by the third order MUSCL and Roe's method. Mach 8 inviscid flow computations for a complete entry probe have shown that the accuracy is at least as good as the symmetric TVD scheme of Yee and Harten. The implicit multigrid method is four times more efficient than the explicit multigrid technique and 3.5 times faster than the single-grid implicit technique. For a Mach 8.7 inviscid flow over a blunt delta wing at 30 deg incidence, the CPU reduction factor from the three-level multigrid computation is 2.2 on a grid of 37 x 41 x 73 nodes.
A parallel multigrid method for data-driven multiprocessor systems
Lin, C.H.; Gaudiot, J.L.; Proskurowski, W.
1989-12-31
The multigrid algorithm (MG) is recognized as an efficient and rapidly converging method to solve a wide family of partial differential equations (PDE). When this method is implemented on a multiprocessor system, its major drawback is the low utilization of processors. Due to the sequentiality of the standard algorithm, the fine grid levels cannot start relaxation until the coarse grid levels complete their own relaxation. Indeed, of all processors active on the fine two dimensional grid level only one fourth will be active at the coarse grid level, leaving full 75% idle. In this paper, a novel parallel V-cycle multigrid (PVM) algorithm is proposed to cure the idle processors` problem. Highly programmable systems such as data-flow architectures are then applied to support this new algorithm. The experiments based on the proposed architecture show that the convergence rate of the new algorithm is about twice faster than that of the standard method and twice as efficient system utilization is achieved.
Monolithic multigrid methods for two-dimensional resistive magnetohydrodynamics
Adler, James H.; Benson, Thomas R.; Cyr, Eric C.; MacLachlan, Scott P.; Tuminaro, Raymond S.
2016-01-06
Magnetohydrodynamic (MHD) representations are used to model a wide range of plasma physics applications and are characterized by a nonlinear system of partial differential equations that strongly couples a charged fluid with the evolution of electromagnetic fields. The resulting linear systems that arise from discretization and linearization of the nonlinear problem are generally difficult to solve. In this paper, we investigate multigrid preconditioners for this system. We consider two well-known multigrid relaxation methods for incompressible fluid dynamics: Braess--Sarazin relaxation and Vanka relaxation. We first extend these to the context of steady-state one-fluid viscoresistive MHD. Then we compare the two relaxationmore » procedures within a multigrid-preconditioned GMRES method employed within Newton's method. To isolate the effects of the different relaxation methods, we use structured grids, inf-sup stable finite elements, and geometric interpolation. Furthermore, we present convergence and timing results for a two-dimensional, steady-state test problem.« less
The Sixth Copper Mountain Conference on Multigrid Methods, part 1
NASA Technical Reports Server (NTRS)
Melson, N. Duane (Editor); Manteuffel, T. A. (Editor); Mccormick, S. F. (Editor)
1993-01-01
The Sixth Copper Mountain Conference on Multigrid Methods was held on 4-9 Apr. 1993, at Copper Mountain, CO. This book is a collection of many of the papers presented at the conference and as such represents the conference proceedings. NASA LaRC graciously provided printing of this document so that all of the papers could be presented in a single forum. Each paper was reviewed by a member of the conference organizing committee under the coordination of the editors. The multigrid discipline continues to expand and mature, as is evident from these proceedings. The vibrancy in this field is amply expressed in these important papers, and the collection clearly shows its rapid trend to further diversity and depth.
The Sixth Copper Mountain Conference on Multigrid Methods, part 2
NASA Technical Reports Server (NTRS)
Melson, N. Duane (Editor); Mccormick, Steve F. (Editor); Manteuffel, Thomas A. (Editor)
1993-01-01
The Sixth Copper Mountain Conference on Multigrid Methods was held on April 4-9, 1993, at Copper Mountain, Colorado. This book is a collection of many of the papers presented at the conference and so represents the conference proceedings. NASA Langley graciously provided printing of this document so that all of the papers could be presented in a single forum. Each paper was reviewed by a member of the conference organizing committee under the coordination of the editors. The multigrid discipline continues to expand and mature, as is evident from these proceedings. The vibrancy in this field is amply expressed in these important papers, and the collection clearly shows its rapid trend to further diversity and depth.
Seventh Copper Mountain Conference on Multigrid Methods. Part 1
NASA Technical Reports Server (NTRS)
Melson, N. Duane; Manteuffel, Tom A.; McCormick, Steve F.; Douglas, Craig C.
1996-01-01
The Seventh Copper Mountain Conference on Multigrid Methods was held on 2-7 Apr. 1995 at Copper Mountain, Colorado. This book is a collection of many of the papers presented at the conference and so represents the conference proceedings. NASA Langley graciously provided printing of this document so that all of the papers could be presented in a single forum. Each paper was reviewed by a member of the conference organizing committee under the coordination of the editors. The multigrid discipline continues to expand and mature, as is evident from these proceedings. The vibrancy in this field is amply expressed in these important papers, and the collection shows its rapid trend to further diversity and depth.
Method for providing improved solid fuels from agglomerated subbituminous coal
Janiak, Jerzy S.; Turak, Ali A.; Pawlak, Wanda; Ignasiak, Boleslaw L.
1989-01-01
A method is provided for separating agglomerated subbituminous coal and the heavy bridging liquid used to form the agglomerates. The separation is performed by contacting the agglomerates with inert gas or steam at a temperature in the range of 250.degree. to 350.degree. C. at substantially atmospheric pressure.
Multigrid methods and the surface consistent equations of Geophysics
NASA Astrophysics Data System (ADS)
Millar, John
The surface consistent equations are a large linear system that is frequently used in signal enhancement for land seismic surveys. Different signatures may be consistent with a particular dynamite (or other) source. Each receiver and the conditions around the receiver will have different impact on the signal. Seismic deconvolution operators, amplitude corrections and static shifts of traces are calculated using the surface consistent equations, both in commercial and scientific seismic processing software. The system of equations is singular, making direct methods such as Gaussian elimination impossible to implement. Iterative methods such as Gauss-Seidel and conjugate gradient are frequently used. A limitation in the nature of the methods leave the long wavelengths of the solution poorly resolved. To reduce the limitations of traditional iterative methods, we employ a multigrid method. Multigrid methods re-sample the entire system of equations on a more coarse grid. An iterative method is employed on the coarse grid. The long wavelengths of the solutions that traditional iterative methods were unable to resolve are calculated on the reduced system of equations. The coarse estimate can be interpolated back up to the original sample rate, and refined using a standard iterative procedure. Multigrid methods provide more accurate solutions to the surface consistent equations, with the largest improvement concentrated in the long wavelengths. Synthetic models and tests on field data show that multigrid solutions to the system of equations can significantly increase the resolution of the seismic data, when used to correct both static time shifts and in calculating deconvolution operators. The first chapter of this thesis is a description of the physical model we are addressing. It reviews some of the literature concerning the surface consistent equations, and provides background on the nature of the problem. Chapter 2 contains a review of iterative and multigrid methods
Method for producing ceramic particles and agglomerates
Phillips, Jonathan; Gleiman, Seth S.; Chen, Chun-Ku
2001-01-01
A method for generating spherical and irregularly shaped dense particles of ceramic oxides having a controlled particle size and particle size distribution. An aerosol containing precursor particles of oxide ceramics is directed into a plasma. As the particles flow through the hot zone of the plasma, they melt, collide, and join to form larger particles. If these larger particles remain in the hot zone, they continue melting and acquire a spherical shape that is retained after they exit the hot zone, cool down, and solidify. If they exit the hot zone before melting completely, their irregular shape persists and agglomerates are produced. The size and size distribution of the dense product particles can be controlled by adjusting several parameters, the most important in the case of powder precursors appears to be the density of powder in the aerosol stream that enters the plasma hot zone. This suggests that particle collision rate is responsible for determining ultimate size of the resulting sphere or agglomerate. Other parameters, particularly the gas flow rates and the microwave power, are also adjusted to control the particle size distribution.
Algebraic multigrid methods applied to problems in computational structural mechanics
NASA Technical Reports Server (NTRS)
Mccormick, Steve; Ruge, John
1989-01-01
The development of algebraic multigrid (AMG) methods and their application to certain problems in structural mechanics are described with emphasis on two- and three-dimensional linear elasticity equations and the 'jacket problems' (three-dimensional beam structures). Various possible extensions of AMG are also described. The basic idea of AMG is to develop the discretization sequence based on the target matrix and not the differential equation. Therefore, the matrix is analyzed for certain dependencies that permit the proper construction of coarser matrices and attendant transfer operators. In this manner, AMG appears to be adaptable to structural analysis applications.
Multigrid method for the equilibrium equations of elasticity using a compact scheme
NASA Technical Reports Server (NTRS)
Taasan, S.
1986-01-01
A compact difference scheme is derived for treating the equilibrium equations of elasticity. The scheme is inconsistent and unstable. A multigrid method which takes into account these properties is described. The solution of the discrete equations, up to the level of discretization errors, is obtained by this method in just two multigrid cycles.
Application of multi-grid methods for solving the Navier-Stokes equations
NASA Technical Reports Server (NTRS)
Demuren, A. O.
1989-01-01
The application of a class of multi-grid methods to the solution of the Navier-Stokes equations for two-dimensional laminar flow problems is discussed. The methods consist of combining the full approximation scheme-full multi-grid technique (FAS-FMG) with point-, line-, or plane-relaxation routines for solving the Navier-Stokes equations in primitive variables. The performance of the multi-grid methods is compared to that of several single-grid methods. The results show that much faster convergence can be procured through the use of the multi-grid approach than through the various suggestions for improving single-grid methods. The importance of the choice of relaxation scheme for the multi-grid method is illustrated.
Application of multi-grid methods for solving the Navier-Stokes equations
NASA Technical Reports Server (NTRS)
Demuren, A. O.
1989-01-01
This paper presents the application of a class of multi-grid methods to the solution of the Navier-Stokes equations for two-dimensional laminar flow problems. The methods consists of combining the full approximation scheme-full multi-grid technique (FAS-FMG) with point-, line- or plane-relaxation routines for solving the Navier-Stokes equations in primitive variables. The performance of the multi-grid methods is compared to those of several single-grid methods. The results show that much faster convergence can be procured through the use of the multi-grid approach than through the various suggestions for improving single-grid methods. The importance of the choice of relaxation scheme for the multi-grid method is illustrated.
A generalized BPX multigrid framework covering nonnested V-cycle methods
NASA Astrophysics Data System (ADS)
Duan, Huo-Yuan; Gao, Shao-Qin; Tan, Roger C. E.; Zhang, Shangyou
2007-03-01
More than a decade ago, Bramble, Pasciak and Xu developed a framework in analyzing the multigrid methods with nonnested spaces or noninherited quadratic forms. It was subsequently known as the BPX multigrid framework, which was widely used in the analysis of multigrid and domain decomposition methods. However, the framework has an apparent limit in the analysis of nonnested V-cycle methods, and it produces a variable V-cycle, or nonuniform convergence rate V-cycle methods, or other nonoptimal results in analysis thus far. This paper completes a long-time effort in extending the BPX multigrid framework so that it truly covers the nonnested V-cycle. We will apply the extended BPX framework to the analysis of many V-cycle nonnested multigrid methods. Some of them were proven previously only for two-level and W-cycle iterations. Some numerical results are presented to support the theoretical analysis of this paper.
A multigrid method for variable coefficient Maxwell's equations
Jones, J E; Lee, B
2004-05-13
This paper presents a multigrid method for solving variable coefficient Maxwell's equations. The novelty in this method is the use of interpolation operators that do not produce multilevel commutativity complexes that lead to multilevel exactness. Rather, the effects of multilevel exactness are built into the level equations themselves--on the finest level using a discrete T-V formulation, and on the coarser grids through the Galerkin coarsening procedure of a T-V formulation. These built-in structures permit the levelwise use of an effective hybrid smoother on the curl-free near-nullspace components, and these structures permit the development of interpolation operators for handling the curl-free and divergence-free error components separately, with the resulting block diagonal interpolation operator not satisfying multilevel commutativity but having good approximation properties for both of these error components. Applying operator-dependent interpolation for each of these error components leads to an effective multigrid scheme for variable coefficient Maxwell's equations, where multilevel commutativity-based methods can degrade. Numerical results are presented to verify the effectiveness of this new scheme.
Constructive interference II: Semi-chaotic multigrid methods
Douglas, C.C.
1994-12-31
Parallel computer vendors have mostly decided to move towards multi-user, multi-tasking per node machines. A number of these machines already exist today. Self load balancing on these machines is not an option to the users except when the user can convince someone to boot the entire machine in single user mode, which may have to be done node by node. Chaotic relaxation schemes were considered for situations like this as far back as the middle 1960`s. However, very little convergence theory exists. Further, what exists indicates that this is not really a good method. Besides chaotic relaxation, chaotic conjugate direction and minimum residual methods are explored as smoothers for symmetric and nonsymmetric problems. While having each processor potentially going off in a different direction from the rest is not what one would strive for in a unigrid situation, the change of grid procedures in multigrid provide a natural way of aiming all of the processors in the right direction. The author presents some new results for multigrid methods in which synchronization of the calculations on one or more levels is not assumed. However, he assumes that he knows how far out of synch neighboring subdomains are with respect to each other. Thus the author can show that the combination of a limited chaotic smoother and coarse level corrections produces a better algorithm than would be expected.
Large-Eddy Simulation and Multigrid Methods
Falgout,R D; Naegle,S; Wittum,G
2001-06-18
A method to simulate turbulent flows with Large-Eddy Simulation on unstructured grids is presented. Two kinds of dynamic models are used to model the unresolved scales of motion and are compared with each other on different grids. Thereby the behavior of the models is shown and additionally the feature of adaptive grid refinement is investigated. Furthermore the parallelization aspect is addressed.
Apparatus and method for compacting, degassing and carbonizing carbonaceous agglomerates
Theodore, F.W.
1980-08-19
An apparatus for compacting, degassing and carbonizing carbonaceous agglomerates is described. The apparatus comprises a rotary kiln having an agglomerate inlet means for introducing green agglomerates into the kiln near the inlet of the kiln and a heating medium inlet for introducing a heating medium comprising a finely divided solid into the kiln at a preselected location intermediate the inlet end of the kiln and the outlet end of the kiln to produce a mixture at a temperature above the carbonizing temperature of the agglomerates and a sieve positioned to receive the products from the rotary kiln and separate the heating medium and the compacted, degassed, carbonized agglomerate product. A method for producing compacted, degassed, carbonized carbonaceous agglomerates by the use of the apparatus is also disclosed.
Method for recovering light hydrocarbons from coal agglomerates
Huettenhain, Horst; Benz, August D.; Getsoian, John
1991-01-01
A method and apparatus for removing light hydrocarbons, such as heptane, from coal agglomerates includes an enclosed chamber having a substantially horizontal perforate surface therein. The coal agglomerates are introduced into a water bath within the chamber. The agglomerates are advanced over the surface while steam is substantially continuously introduced through the surface into the water bath. Steam heats the water and causes volatilization of the light hydrocarbons, which may be collected from the overhead of the chamber. The resulting agglomerates may be collected at the opposite end from the surface and subjected to final draining processes prior to transportation or use.
Multigrid hierarchical simulated annealing method for reconstructing heterogeneous media.
Pant, Lalit M; Mitra, Sushanta K; Secanell, Marc
2015-12-01
A reconstruction methodology based on different-phase-neighbor (DPN) pixel swapping and multigrid hierarchical annealing is presented. The method performs reconstructions by starting at a coarse image and successively refining it. The DPN information is used at each refinement stage to freeze interior pixels of preformed structures. This preserves the large-scale structures in refined images and also reduces the number of pixels to be swapped, thereby resulting in a decrease in the necessary computational time to reach a solution. Compared to conventional single-grid simulated annealing, this method was found to reduce the required computation time to achieve a reconstruction by around a factor of 70-90, with the potential of even higher speedups for larger reconstructions. The method is able to perform medium sized (up to 300(3) voxels) three-dimensional reconstructions with multiple correlation functions in 36-47 h. PMID:26764849
Solving nonlinear heat conduction problems with multigrid preconditioned Newton-Krylov methods
Rider, W.J.; Knoll, D.A.
1997-09-01
Our objective is to investigate the utility of employing multigrid preconditioned Newton-Krylov methods for solving initial value problems. Multigrid based method promise better performance from the linear scaling associated with them. Our model problem is nonlinear heat conduction which can model idealized Marshak waves. Here we will investigate the efficiency of using a linear multigrid method to precondition a Krylov subspace method. In effect we will show that a fixed point nonlinear iterative method provides an effective preconditioner for the nonlinear problem.
NASA Technical Reports Server (NTRS)
Golik, W. L.
1996-01-01
A robust solver for the elliptic grid generation equations is sought via a numerical study. The system of PDEs is discretized with finite differences, and multigrid methods are applied to the resulting nonlinear algebraic equations. Multigrid iterations are compared with respect to the robustness and efficiency. Different smoothers are tried to improve the convergence of iterations. The methods are applied to four 2D grid generation problems over a wide range of grid distortions. The results of the study help to select smoothing schemes and the overall multigrid procedures for elliptic grid generation.
Novel Binders and Methods for Agglomeration of Ore
S. K. Kawatra; T. C. Eisele; K. A. Lewandowski; J. A. Gurtler
2006-09-30
Heap leaching is one of the methods being used to recover metal from low grade ore deposits. The main problem faced during heap leaching is the migration of fine grained particles through the heap, forming impermeable beds which result in poor solution flow. The poor solution flow leads to less contact between the leach solution and the ore, resulting in low recovery rates. Agglomeration of ore into coarse, porous masses prevents fine particles from migrating and clogging the spaces and channels between the larger ore particles. Currently, there is one facility in the United States which uses agglomeration. This operation agglomerates their ore using leach solution (raffinate), but is still experiencing undesirable metal recovery from the heaps due to agglomerate breakdown. The use of a binder, in addition to the leach solution, during agglomeration would help to produce stronger agglomerates that did not break down during processing. However, there are no known binders that will work satisfactorily in the acidic environment of a heap, at a reasonable cost. As a result, operators of many facilities see a large loss of process efficiency due to their inability to take advantage of agglomeration. Increasing copper recovery in heap leaching by the use of binders and agglomeration would result in a significant decrease in the amount of energy consumed. Assuming that 70% of all the leaching heaps would convert to using agglomeration technology, as much as 1.64*10{sup 12} BTU per year would be able to be saved if a 25% increase in copper recovery was experienced, which is equivalent to saving approximately 18% of the energy currently being used in leaching heaps. For every week a leach cycle was decreased, a savings of as much as 1.23*10{sup 11} BTU per week would result. This project has identified several acid-resistant binders and agglomeration procedures. These binders and experimental procedures will be able to be used for use in improving the energy efficiency of
A Conforming Multigrid Method for the Pure Traction Problem of Linear Elasticity: Mixed Formulation
NASA Technical Reports Server (NTRS)
Lee, Chang-Ock
1996-01-01
A multigrid method using conforming P-1 finite element is developed for the two-dimensional pure traction boundary value problem of linear elasticity. The convergence is uniform even as the material becomes nearly incompressible. A heuristic argument for acceleration of the multigrid method is discussed as well. Numerical results with and without this acceleration as well as performance estimates on a parallel computer are included.
NASA Technical Reports Server (NTRS)
Fay, John F.
1990-01-01
A calculation is made of the stability of various relaxation schemes for the numerical solution of partial differential equations. A multigrid acceleration method is introduced, and its effects on stability are explored. A detailed stability analysis of a simple case is carried out and verified by numerical experiment. It is shown that the use of multigrids can speed convergence by several orders of magnitude without adversely affecting stability.
Copper Mountain conference on multigrid methods. Preliminary proceedings -- List of abstracts
1995-12-31
This report contains abstracts of the papers presented at the conference. Papers cover multigrid algorithms and applications of multigrid methods. Applications include the following: solution of elliptical problems; electric power grids; fluid mechanics; atmospheric data assimilation; thermocapillary effects on weld pool shape; boundary-value problems; prediction of hurricane tracks; modeling multi-dimensional combustion and detailed chemistry; black-oil reservoir simulation; image processing; and others.
Application of the multigrid method to grid generation
NASA Technical Reports Server (NTRS)
Ohring, S.
1980-01-01
The multigrid method (MGM), used to numerically solve the pair of nonlinear elliptic equations commonly used to generate two dimensional boundary-fitted coordinate systems is discussed. Two different geometries are considered: one involving a coordinate system fitted about a circle and the other selected for an impinging jet flow problem. Two different relaxation schemes are tried: one is successive point overrelaxation and the other is a four-color scheme vectorizeable to take advantage of a parallel processor computer for greater computational speed. Results using MGM are compared with those using SOR (doing successive overrelaxations with the corresponding relaxation scheme on the fine grid only). It is found that MGM becomes significantly more effective than SOR as more accuracy is demanded and as more corrective grids, or more grid points, are used. For the accuracy required, it is found that MGM is two to three times faster than SOR in computing time. With the four-color relaxation scheme as applied to the impinging jet problem, the advantage of MGM over SOR is not as great. This may be due to the effect of a poor initial guess on MGM for this problem.
Novel Binders and Methods for Agglomeration of Ore
S. K. Kawatra; T. C. Eisele; K. A. Lewandowski; J. A. Gurtler
2006-12-31
Many metal extraction operations, such as leaching of copper, leaching of precious metals, and reduction of metal oxides to metal in high-temperature furnaces, require agglomeration of ore to ensure that reactive liquids or gases are evenly distributed throughout the ore being processed. Agglomeration of ore into coarse, porous masses achieves this even distribution of fluids by preventing fine particles from migrating and clogging the spaces and channels between the larger ore particles. Binders are critically necessary to produce agglomerates that will not break down during processing. However, for many important metal extraction processes there are no binders known that will work satisfactorily. Primary examples of this are copper heap leaching, where there are no binders that will work in the acidic environment encountered in this process, and advanced ironmaking processes, where binders must function satisfactorily over an extraordinarily large range of temperatures (from room temperature up to over 1200 C). As a result, operators of many facilities see a large loss of process efficiency due to their inability to take advantage of agglomeration. The large quantities of ore that must be handled in metal extraction processes also means that the binder must be inexpensive and useful at low dosages to be economical. The acid-resistant binders and agglomeration procedures developed in this project will also be adapted for use in improving the energy efficiency and performance of a broad range of mineral agglomeration applications, particularly heap leaching and advanced primary ironmaking. This project has identified several acid-resistant binders and agglomeration procedures that can be used for improving the energy efficiency of heap leaching, by preventing the ''ponding'' and ''channeling'' effects that currently cause reduced recovery and extended leaching cycle times. Methods have also been developed for iron ore processing which are intended to improve the
Recent developments in multigrid methods for the steady Euler equations
NASA Technical Reports Server (NTRS)
Jespersen, D. C.
1984-01-01
The solution by multigrid techniques of the steady inviscid compressible equations of gas dynamics, the Euler equations is investigated. Steady two dimensional transonic flow over an airfoil section is studied intensively. Most of the material is applicable to three dimensional flow problems of aerodynamic interest.
Continuous air agglomeration method for high carbon fly ash beneficiation
Gray, McMahon L.; Champagne, Kenneth J.; Finseth, Dennis H.
2000-01-01
The carbon and mineral components of fly ash are effectively separated by a continuous air agglomeration method, resulting in a substantially carboree mineral stream and a highly concentrated carbon product. The method involves mixing the fly ash comprised of carbon and inorganic mineral matter with a liquid hydrocarbon to form a slurry, contacting the slurry with an aqueous solution, dispersing the hydrocarbon slurry into small droplets within the aqueous solution by mechanical mixing and/or aeration, concentrating the inorganic mineral matter in the aqueous solution, agglomerating the carbon and hydrocarbon in the form of droplets, collecting the droplets, separating the hydrocarbon from the concentrated carbon product, and recycling the hydrocarbon.
Continuous air Agglomeration Method for high Carbon fly ash Beneficiation
Gray, McMahan L.; Champagne, Kenneth J.; Finseth, Dennis H.
1998-09-29
The carbon and mineral components of fly ash are effectively separated by a continuous air agglomeration method, resulting in a substantially carbon-free mineral stream and a highly concentrated carbon product. The method involves mixing the fly ash comprised of carbon and inorganic mineral matter with a liquid hydrocarbon to form a slurry, contacting the slurry with an aqueous solution, dispersing the hydrocarbon slurry into small droplets within the aqueous solution by mechanical mixing and/or aeration, concentrating the inorganic mineral matter in the aqueous solution, agglomerating the carbon and hydrocarbon in the form of droplets, collecting the droplets, separating the hydrocarbon from the concentrated carbon product, and recycling the hydrocarbon.
Multigrid lattice Boltzmann method for accelerated solution of elliptic equations
NASA Astrophysics Data System (ADS)
Patil, Dhiraj V.; Premnath, Kannan N.; Banerjee, Sanjoy
2014-05-01
A new solver for second-order elliptic partial differential equations (PDEs) based on the lattice Boltzmann method (LBM) and the multigrid (MG) technique is presented. Several benchmark elliptic equations are solved numerically with the inclusion of multiple grid-levels in two-dimensional domains at an optimal computational cost within the LB framework. The results are compared with the corresponding analytical solutions and numerical solutions obtained using the Stone's strongly implicit procedure. The classical PDEs considered in this article include the Laplace and Poisson equations with Dirichlet boundary conditions, with the latter involving both constant and variable coefficients. A detailed analysis of solution accuracy, convergence and computational efficiency of the proposed solver is given. It is observed that the use of a high-order stencil (for smoothing) improves convergence and accuracy for an equivalent number of smoothing sweeps. The effect of the type of scheduling cycle (V- or W-cycle) on the performance of the MG-LBM is analyzed. Next, a parallel algorithm for the MG-LBM solver is presented and then its parallel performance on a multi-core cluster is analyzed. Lastly, a practical example is provided wherein the proposed elliptic PDE solver is used to compute the electro-static potential encountered in an electro-chemical cell, which demonstrates the effectiveness of this new solver in complex coupled systems. Several orders of magnitude gains in convergence and parallel scaling for the canonical problems, and a factor of 5 reduction for the multiphysics problem are achieved using the MG-LBM.
Multiple Vector Preserving Interpolation Mappings in Algebraic Multigrid
Vassilevski, P S; Zikatanov, L T
2004-11-03
We propose algorithms for the construction of AMG (algebraic multigrid) interpolation mappings such that the resulting coarse space to span (locally and globally) any number of a priori given set of vectors. Specific constructions in the case of element agglomeration AMG methods are given. Some numerical illustration is also provided.
Inverse airfoil design procedure using a multigrid Navier-Stokes method
NASA Technical Reports Server (NTRS)
Malone, J. B.; Swanson, R. C.
1991-01-01
The Modified Garabedian McFadden (MGM) design procedure was incorporated into an existing 2-D multigrid Navier-Stokes airfoil analysis method. The resulting design method is an iterative procedure based on a residual correction algorithm and permits the automated design of airfoil sections with prescribed surface pressure distributions. The new design method, Multigrid Modified Garabedian McFadden (MG-MGM), is demonstrated for several different transonic pressure distributions obtained from both symmetric and cambered airfoil shapes. The airfoil profiles generated with the MG-MGM code are compared to the original configurations to assess the capabilities of the inverse design method.
Multigrid for the Galerkin least squares method in linear elasticity: The pure displacement problem
Yoo, Jaechil
1996-12-31
Franca and Stenberg developed several Galerkin least squares methods for the solution of the problem of linear elasticity. That work concerned itself only with the error estimates of the method. It did not address the related problem of finding effective methods for the solution of the associated linear systems. In this work, we prove the convergence of a multigrid (W-cycle) method. This multigrid is robust in that the convergence is uniform as the parameter, v, goes to 1/2 Computational experiments are included.
Advanced discretizations and multigrid methods for liquid crystal configurations
NASA Astrophysics Data System (ADS)
Emerson, David B.
addition, we present two novel, optimally scaling, multigrid approaches for these systems based on Vanka- and Braess-Sarazin-type relaxation. Both approaches outperform direct methods and represent highly efficient and scalable iterative solvers. Finally, a three-dimensional problem considering the effects of geometrically patterned surfaces is presented, which gives rise to a nonlinear anisotropic reaction-diffusion equation. Well-posedness is shown for the intermediate linearization systems of the proposed Newton linearization. The configurations under consideration are part of ongoing physics research seeking new bistable configurations induced by geometric nano-patterning.
On multigrid methods for the Navier-Stokes Computer
NASA Technical Reports Server (NTRS)
Nosenchuck, D. M.; Krist, S. E.; Zang, T. A.
1988-01-01
The overall architecture of the multipurpose parallel-processing Navier-Stokes Computer (NSC) being developed by Princeton and NASA Langley (Nosenchuck et al., 1986) is described and illustrated with extensive diagrams, and the NSC implementation of an elementary multigrid algorithm for simulating isotropic turbulence (based on solution of the incompressible time-dependent Navier-Stokes equations with constant viscosity) is characterized in detail. The present NSC design concept calls for 64 nodes, each with the performance of a class VI supercomputer, linked together by a fiber-optic hypercube network and joined to a front-end computer by a global bus. In this configuration, the NSC would have a storage capacity of over 32 Gword and a peak speed of over 40 Gflops. The multigrid Navier-Stokes code discussed would give sustained operation rates of about 25 Gflops.
A positivity-preserving, implicit defect-correction multigrid method for turbulent combustion
NASA Astrophysics Data System (ADS)
Wasserman, M.; Mor-Yossef, Y.; Greenberg, J. B.
2016-07-01
A novel, robust multigrid method for the simulation of turbulent and chemically reacting flows is developed. A survey of previous attempts at implementing multigrid for the problems at hand indicated extensive use of artificial stabilization to overcome numerical instability arising from non-linearity of turbulence and chemistry model source-terms, small-scale physics of combustion, and loss of positivity. These issues are addressed in the current work. The highly stiff Reynolds-averaged Navier-Stokes (RANS) equations, coupled with turbulence and finite-rate chemical kinetics models, are integrated in time using the unconditionally positive-convergent (UPC) implicit method. The scheme is successfully extended in this work for use with chemical kinetics models, in a fully-coupled multigrid (FC-MG) framework. To tackle the degraded performance of multigrid methods for chemically reacting flows, two major modifications are introduced with respect to the basic, Full Approximation Storage (FAS) approach. First, a novel prolongation operator that is based on logarithmic variables is proposed to prevent loss of positivity due to coarse-grid corrections. Together with the extended UPC implicit scheme, the positivity-preserving prolongation operator guarantees unconditional positivity of turbulence quantities and species mass fractions throughout the multigrid cycle. Second, to improve the coarse-grid-correction obtained in localized regions of high chemical activity, a modified defect correction procedure is devised, and successfully applied for the first time to simulate turbulent, combusting flows. The proposed modifications to the standard multigrid algorithm create a well-rounded and robust numerical method that provides accelerated convergence, while unconditionally preserving the positivity of model equation variables. Numerical simulations of various flows involving premixed combustion demonstrate that the proposed MG method increases the efficiency by a factor of
Simulation of viscous flows using a multigrid-control volume finite element method
Hookey, N.A.
1994-12-31
This paper discusses a multigrid control volume finite element method (MG CVFEM) for the simulation of viscous fluid flows. The CVFEM is an equal-order primitive variables formulation that avoids spurious solution fields by incorporating an appropriate pressure gradient in the velocity interpolation functions. The resulting set of discretized equations is solved using a coupled equation line solver (CELS) that solves the discretized momentum and continuity equations simultaneously along lines in the calculation domain. The CVFEM has been implemented in the context of both FMV- and V-cycle multigrid algorithms, and preliminary results indicate a five to ten fold reduction in execution times.
Method for agglomerating powdered coal by compaction
Byrne, L.D.; Byrne, B.J.
1987-07-21
A method is described for preparing a powdered carboniferous composition and forming this composition into solid product shapes suitable for handling, transporting and burning, comprising the steps of: (a) mixing (1) powdered carboniferous material with (2) an amount of surfactant effective for wetting the powdered carboniferous material with water but for which no appreciable binding occurs between the surfactant and carboniferous material upon compaction and (3) an amount of water effective to bring the moisture content of the resultant mixture within the range of about 32 to 35% by weight; (b) working the mixture to obtain a homogeneous composition comprising a uniform dispersion of the water, surfactant, and powdered carboniferous material; and (c) compacting the resultant homogeneous composition into the desired solid product shape by extruding the homogeneous composition through a ring pelletizing extruder.
Spectral multigrid methods for the solution of homogeneous turbulence problems
NASA Technical Reports Server (NTRS)
Erlebacher, G.; Zang, T. A.; Hussaini, M. Y.
1987-01-01
New three-dimensional spectral multigrid algorithms are analyzed and implemented to solve the variable coefficient Helmholtz equation. Periodicity is assumed in all three directions which leads to a Fourier collocation representation. Convergence rates are theoretically predicted and confirmed through numerical tests. Residual averaging results in a spectral radius of 0.2 for the variable coefficient Poisson equation. In general, non-stationary Richardson must be used for the Helmholtz equation. The algorithms developed are applied to the large-eddy simulation of incompressible isotropic turbulence.
A multigrid method for N-component nucleation.
van Putten, Dennis S; Glazenborg, Simon P; Hagmeijer, Rob; Venner, Cornelis H
2011-07-01
A multigrid algorithm has been developed enabling more efficient solution of the cluster size distribution for N-component nucleation from the Becker-Döring equations. The theoretical derivation is valid for an arbitrary number of condensing components, making the simulation of many-component nucleating systems feasible. A steady state ternary nucleation problem is defined to demonstrate its efficiency. The results are used as a validation for existing nucleation theories. The non-steady state ternary problem provides useful insight into the initial stages of the nucleation process. We observe that for the ideal mixture the main nucleation flux bypasses the saddle point. PMID:21744895
A multigrid method for steady Euler equations on unstructured adaptive grids
NASA Technical Reports Server (NTRS)
Riemslagh, Kris; Dick, Erik
1993-01-01
A flux-difference splitting type algorithm is formulated for the steady Euler equations on unstructured grids. The polynomial flux-difference splitting technique is used. A vertex-centered finite volume method is employed on a triangular mesh. The multigrid method is in defect-correction form. A relaxation procedure with a first order accurate inner iteration and a second-order correction performed only on the finest grid, is used. A multi-stage Jacobi relaxation method is employed as a smoother. Since the grid is unstructured a Jacobi type is chosen. The multi-staging is necessary to provide sufficient smoothing properties. The domain is discretized using a Delaunay triangular mesh generator. Three grids with more or less uniform distribution of nodes but with different resolution are generated by successive refinement of the coarsest grid. Nodes of coarser grids appear in the finer grids. The multigrid method is started on these grids. As soon as the residual drops below a threshold value, an adaptive refinement is started. The solution on the adaptively refined grid is accelerated by a multigrid procedure. The coarser multigrid grids are generated by successive coarsening through point removement. The adaption cycle is repeated a few times. Results are given for the transonic flow over a NACA-0012 airfoil.
A multigrid Newton-Krylov method for flux-limited radiation diffusion
Rider, W.J.; Knoll, D.A.; Olson, G.L.
1998-09-01
The authors focus on the integration of radiation diffusion including flux-limited diffusion coefficients. The nonlinear integration is accomplished with a Newton-Krylov method preconditioned with a multigrid Picard linearization of the governing equations. They investigate the efficiency of the linear and nonlinear iterative techniques.
NASA Technical Reports Server (NTRS)
Dendy, J. E., Jr.
1981-01-01
The black box multigrid (BOXMG) code, which only needs specification of the matrix problem for application in the multigrid method was investigated. It is contended that a major problem with the multigrid method is that each new grid configuration requires a major programming effort to develop a code that specifically handles that grid configuration. The SOR and ICCG methods only specify the matrix problem, no matter what the grid configuration. It is concluded that the BOXMG does everything else necessary to set up the auxiliary coarser problems to achieve a multigrid solution.
An overlapped grid method for multigrid, finite volume/difference flow solvers: MaGGiE
NASA Technical Reports Server (NTRS)
Baysal, Oktay; Lessard, Victor R.
1990-01-01
The objective is to develop a domain decomposition method via overlapping/embedding the component grids, which is to be used by upwind, multi-grid, finite volume solution algorithms. A computer code, given the name MaGGiE (Multi-Geometry Grid Embedder) is developed to meet this objective. MaGGiE takes independently generated component grids as input, and automatically constructs the composite mesh and interpolation data, which can be used by the finite volume solution methods with or without multigrid convergence acceleration. Six demonstrative examples showing various aspects of the overlap technique are presented and discussed. These cases are used for developing the procedure for overlapping grids of different topologies, and to evaluate the grid connection and interpolation data for finite volume calculations on a composite mesh. Time fluxes are transferred between mesh interfaces using a trilinear interpolation procedure. Conservation losses are minimal at the interfaces using this method. The multi-grid solution algorithm, using the coaser grid connections, improves the convergence time history as compared to the solution on composite mesh without multi-gridding.
Development of methods to predict agglomeration and disposition in FBCs
Mann, M.D.; Henderson, A.K.; Swanson, M.K.; Erickson, T.A.
1995-11-01
This 3-year, multiclient program is providing the information needed to determine the behavior of inorganic components in FBC units using advanced methods of analysis coupled with bench-scale combustion experiments. The major objectives of the program are as follows: (1) To develop further our advanced ash and deposit characterization techniques to quantify the effects of the liquid-phase components in terms of agglomerate formation and ash deposits, (2) To determine the mechanisms of inorganic transformations that lead to bed agglomeration and ash deposition in FBC systems, and (3) To develop a better means to predict the behavior of inorganic components as a function of coal composition, bed material characteristics, and combustion conditions.
New Nonlinear Multigrid Analysis
NASA Technical Reports Server (NTRS)
Xie, Dexuan
1996-01-01
The nonlinear multigrid is an efficient algorithm for solving the system of nonlinear equations arising from the numerical discretization of nonlinear elliptic boundary problems. In this paper, we present a new nonlinear multigrid analysis as an extension of the linear multigrid theory presented by Bramble. In particular, we prove the convergence of the nonlinear V-cycle method for a class of mildly nonlinear second order elliptic boundary value problems which do not have full elliptic regularity.
Multigrid methods for differential equations with highly oscillatory coefficients
NASA Technical Reports Server (NTRS)
Engquist, Bjorn; Luo, Erding
1993-01-01
New coarse grid multigrid operators for problems with highly oscillatory coefficients are developed. These types of operators are necessary when the characters of the differential equations on coarser grids or longer wavelengths are different from that on the fine grid. Elliptic problems for composite materials and different classes of hyperbolic problems are practical examples. The new coarse grid operators can be constructed directly based on the homogenized differential operators or hierarchically computed from the finest grid. Convergence analysis based on the homogenization theory is given for elliptic problems with periodic coefficients and some hyperbolic problems. These are classes of equations for which there exists a fairly complete theory for the interaction between shorter and longer wavelengths in the problems. Numerical examples are presented.
A multigrid method for a model of the implicit immersed boundary equations
Guy, Robert; Philip, Bobby
2012-01-01
Explicit time stepping schemes for the immersed boundary method require very small time steps in order to maintain stability. Solving the equations that arise from an implicit discretization is difficult. Recently, several different approaches have been proposed, but a complete understanding of this problem is still emerging. A multigrid method is developed and explored for solving the equations in an implicit time discretization of a model of the immersed boundary equations. The model problem consists of a scalar Poisson equation with conformation-dependent singular forces on an immersed boundary. This model does not include the inertial terms or the incompressibility constraint. The method is more efficient than an explicit method, but the efficiency gain is limited. The multigrid method alone may not be an effective solver, but when used as a preconditioner for Krylov methods, the speed-up over the explicit time method is substantial. For example, depending on the constitutive law for the boundary force, with a time step 100 times larger than the explicit method, the implicit method is about 15-100 times more efficient than the explicit method. A very attractive feature of this method is that the efficiency of the multigrid preconditioned Krylov solver is shown to be independent of the number of immersed boundary points.
An automatic multigrid method for the solution of sparse linear systems
NASA Technical Reports Server (NTRS)
Shapira, Yair; Israeli, Moshe; Sidi, Avram
1993-01-01
An automatic version of the multigrid method for the solution of linear systems arising from the discretization of elliptic PDE's is presented. This version is based on the structure of the algebraic system solely, and does not use the original partial differential operator. Numerical experiments show that for the Poisson equation the rate of convergence of our method is equal to that of classical multigrid methods. Moreover, the method is robust in the sense that its high rate of convergence is conserved for other classes of problems: non-symmetric, hyperbolic (even with closed characteristics) and problems on non-uniform grids. No double discretization or special treatment of sub-domains (e.g. boundaries) is needed. When supplemented with a vector extrapolation method, high rates of convergence are achieved also for anisotropic and discontinuous problems and also for indefinite Helmholtz equations. A new double discretization strategy is proposed for finite and spectral element schemes and is found better than known strategies.
NASA Astrophysics Data System (ADS)
Lavery, N.; Taylor, C.
1999-07-01
Multigrid and iterative methods are used to reduce the solution time of the matrix equations which arise from the finite element (FE) discretisation of the time-independent equations of motion of the incompressible fluid in turbulent motion. Incompressible flow is solved by using the method of reduce interpolation for the pressure to satisfy the Brezzi-Babuska condition. The k-l model is used to complete the turbulence closure problem. The non-symmetric iterative matrix methods examined are the methods of least squares conjugate gradient (LSCG), biconjugate gradient (BCG), conjugate gradient squared (CGS), and the biconjugate gradient squared stabilised (BCGSTAB). The multigrid algorithm applied is based on the FAS algorithm of Brandt, and uses two and three levels of grids with a V-cycling schedule. These methods are all compared to the non-symmetric frontal solver. Copyright
Multilevel local refinement and multigrid methods for 3-D turbulent flow
Liao, C.; Liu, C.; Sung, C.H.; Huang, T.T.
1996-12-31
A numerical approach based on multigrid, multilevel local refinement, and preconditioning methods for solving incompressible Reynolds-averaged Navier-Stokes equations is presented. 3-D turbulent flow around an underwater vehicle is computed. 3 multigrid levels and 2 local refinement grid levels are used. The global grid is 24 x 8 x 12. The first patch is 40 x 16 x 20 and the second patch is 72 x 32 x 36. 4th order artificial dissipation are used for numerical stability. The conservative artificial compressibility method are used for further improvement of convergence. To improve the accuracy of coarse/fine grid interface of local refinement, flux interpolation method for refined grid boundary is used. The numerical results are in good agreement with experimental data. The local refinement can improve the prediction accuracy significantly. The flux interpolation method for local refinement can keep conservation for a composite grid, therefore further modify the prediction accuracy.
General relaxation schemes in multigrid algorithms for higher order singularity methods
NASA Technical Reports Server (NTRS)
Oskam, B.; Fray, J. M. J.
1981-01-01
Relaxation schemes based on approximate and incomplete factorization technique (AF) are described. The AF schemes allow construction of a fast multigrid method for solving integral equations of the second and first kind. The smoothing factors for integral equations of the first kind, and comparison with similar results from the second kind of equations are a novel item. Application of the MD algorithm shows convergence to the level of truncation error of a second order accurate panel method.
Parallel Multigrid Equation Solver
Energy Science and Technology Software Center (ESTSC)
2001-09-07
Prometheus is a fully parallel multigrid equation solver for matrices that arise in unstructured grid finite element applications. It includes a geometric and an algebraic multigrid method and has solved problems of up to 76 mullion degrees of feedom, problems in linear elasticity on the ASCI blue pacific and ASCI red machines.
On Efficient Multigrid Methods for Materials Processing Flows with Small Particles
NASA Technical Reports Server (NTRS)
Thomas, James (Technical Monitor); Diskin, Boris; Harik, VasylMichael
2004-01-01
Multiscale modeling of materials requires simulations of multiple levels of structural hierarchy. The computational efficiency of numerical methods becomes a critical factor for simulating large physical systems with highly desperate length scales. Multigrid methods are known for their superior efficiency in representing/resolving different levels of physical details. The efficiency is achieved by employing interactively different discretizations on different scales (grids). To assist optimization of manufacturing conditions for materials processing with numerous particles (e.g., dispersion of particles, controlling flow viscosity and clusters), a new multigrid algorithm has been developed for a case of multiscale modeling of flows with small particles that have various length scales. The optimal efficiency of the algorithm is crucial for accurate predictions of the effect of processing conditions (e.g., pressure and velocity gradients) on the local flow fields that control the formation of various microstructures or clusters.
Numerical solution of flame sheet problems with and without multigrid methods
NASA Technical Reports Server (NTRS)
Douglas, Craig C.; Ern, Alexandre
1993-01-01
Flame sheet problems are on the natural route to the numerical solution of multidimensional flames, which, in turn, are important in many engineering applications. In order to model the structure of flames more accurately, we use the vorticity-velocity formulation of the fluid flow equations, as opposed to the streamfunction-vorticity approach. The numerical solution of the resulting nonlinear coupled elliptic partial differential equations involves a pseudo transient process and a steady state Newton iteration. Rather than working with dimensionless variables, we introduce scale factors that can yield significant savings in the execution time. In this context, we also investigate the applicability and performance of several multigrid methods, focusing on nonlinear damped Newton multigrid, using either one way or correction schemes.
A Parallel Multigrid Method for the Finite Element Analysis of Mechanical Contact
Hales, J D; Parsons, I D
2002-03-21
A geometrical multigrid method for solving the linearized matrix equations arising from node-on-face three-dimensional finite element contact is described. The development of an efficient implementation of this combination that minimizes both the memory requirements and the computational cost requires careful construction and storage of the portion of the coarse mesh stiffness matrices that are associated with the contact stiffness on the fine mesh. The multigrid contact algorithm is parallelized in a manner suitable for distributed memory architectures: results are presented that demonstrates the scheme's scalability. The solution of a large contact problem derived from an analysis of the factory joints present in the Space Shuttle reusable solid rocket motor demonstrates the usefulness of the general approach.
Rotor-stator interaction analysis using the Navier-Stokes equations and a multigrid method
Arnone, A.; Pacciani, R.
1996-10-01
A recently developed, time-accurate multigrid viscous solver has been extended to the analysis of unsteady rotor-stator interaction. In the proposed method, a fully implicit discretization is used to remove stability limitations. By means of a dual time-stepping approach, a four-stage Runge-Kutta scheme is used in conjunction with several accelerating techniques typical of steady-state solvers, instead of traditional time-expensive factorizations. The accelerating strategies include local time stepping, residual smoothing, and multigrid. Two-dimensional viscous calculations of unsteady rotor-stator interaction in the first stage of a modern gas turbine are presented. The stage analysis is based on the introduction of several blade passages to approximate the stator:rotor count ratio. Particular attention is dedicated to grid dependency in space and time as well as to the influence of the number of blades included in the calculations.
On the solution of evolution equations based on multigrid and explicit iterative methods
NASA Astrophysics Data System (ADS)
Zhukov, V. T.; Novikova, N. D.; Feodoritova, O. B.
2015-08-01
Two schemes for solving initial-boundary value problems for three-dimensional parabolic equations are studied. One is implicit and is solved using the multigrid method, while the other is explicit iterative and is based on optimal properties of the Chebyshev polynomials. In the explicit iterative scheme, the number of iteration steps and the iteration parameters are chosen as based on the approximation and stability conditions, rather than on the optimization of iteration convergence to the solution of the implicit scheme. The features of the multigrid scheme include the implementation of the intergrid transfer operators for the case of discontinuous coefficients in the equation and the adaptation of the smoothing procedure to the spectrum of the difference operators. The results produced by these schemes as applied to model problems with anisotropic discontinuous coefficients are compared.
Agglomerating combustor-gasifier method and apparatus for coal gasification
Chen, Joseph L. P.; Archer, David H.
1976-09-21
A method and apparatus for gasifying coal wherein the gasification takes place in a spout fluid bed at a pressure of about 10 to 30 atmospheres and a temperature of about 1800.degree. to 2200.degree.F and wherein the configuration of the apparatus and the manner of introduction of gases for combustion and fluidization is such that agglomerated ash can be withdrawn from the bottom of the apparatus and gas containing very low dust loading is produced. The gasification reaction is self-sustaining through the burning of a stoichiometric amount of coal with air in the lower part of the apparatus to form the spout within the fluid bed. The method and apparatus are particularly suitable for gasifying coarse coal particles.
Multigrid techniques for unstructured meshes
NASA Technical Reports Server (NTRS)
Mavriplis, D. J.
1995-01-01
An overview of current multigrid techniques for unstructured meshes is given. The basic principles of the multigrid approach are first outlined. Application of these principles to unstructured mesh problems is then described, illustrating various different approaches, and giving examples of practical applications. Advanced multigrid topics, such as the use of algebraic multigrid methods, and the combination of multigrid techniques with adaptive meshing strategies are dealt with in subsequent sections. These represent current areas of research, and the unresolved issues are discussed. The presentation is organized in an educational manner, for readers familiar with computational fluid dynamics, wishing to learn more about current unstructured mesh techniques.
AMG by element agglomeration and constrained energy minimization interpolation
Kolev, T V; Vassilevski, P S
2006-02-17
This paper studies AMG (algebraic multigrid) methods that utilize energy minimization construction of the interpolation matrices locally, in the setting of element agglomeration AMG. The coarsening in element agglomeration AMG is done by agglomerating fine-grid elements, with coarse element matrices defined by a local Galerkin procedure applied to the matrix assembled from the individual fine-grid element matrices. This local Galerkin procedure involves only the coarse basis restricted to the agglomerated element. To construct the coarse basis, one exploits previously proposed constraint energy minimization procedures now applied to the local matrix. The constraints are that a given set of vectors should be interpolated exactly, not only globally, but also locally on every agglomerated element. The paper provides algorithmic details, as well as a convergence result based on a ''local-to-global'' energy bound of the resulting multiple-vector fitting AMG interpolation mappings. A particular implementation of the method is illustrated with a set of numerical experiments.
Novel Binders and Methods for Agglomeration of Ore
S. K. Kawatra; T. C. Eisele; J. A. Gurtler; K. Lewandowski
2005-09-30
Many metal extraction operations, such as leaching of copper, leaching of precious metals, and reduction of metal oxides to metal in high-temperature furnaces, require agglomeration of ore to ensure that reactive liquids or gases are evenly distributed throughout the ore being processed. Agglomeration of ore into coarse, porous masses achieves this even distribution of fluids by preventing fine particles from migrating and clogging the spaces and channels between the larger ore particles. Binders are critically necessary to produce agglomerates that will not break down during processing. However, for many important metal extraction processes there are no binders known that will work satisfactorily at a reasonable cost. A primary example of this is copper heap leaching, where there are no binders currently encountered in this acidic environment process. As a result, operators of many facilities see a large loss of process efficiency due to their inability to take advantage of agglomeration. The large quantities of ore that must be handled in metal extraction processes also means that the binder must be inexpensive and useful at low dosages to be economical. The acid-resistant binders and agglomeration procedures developed in this project will also be adapted for use in improving the energy efficiency and performance of a broad range of mineral agglomeration applications, particularly heap leaching. The active involvement of our industrial partners will help to ensure rapid commercialization of any agglomeration technologies developed by this project.
Novel Binders and Methods for Agglomeration of Ore
S. K. Kawatra; T. C. Eisele; K. A. Lewandowski; J. A. Gurtler
2006-03-31
Many metal extraction operations, such as leaching of copper, leaching of precious metals, and reduction of metal oxides to metal in high-temperature furnaces, require agglomeration of ore to ensure that reactive liquids or gases are evenly distributed throughout the ore being processed. Agglomeration of ore into coarse, porous masses achieves this even distribution of fluids by preventing fine particles from migrating and clogging the spaces and channels between the larger ore particles. Binders are critically necessary to produce agglomerates that will not break down during processing. However, for many important metal extraction processes there are no binders known that will work satisfactorily at a reasonable cost. A primary example of this is copper heap leaching, where there are no binders currently encountered in this acidic environment process. As a result, operators of many facilities see a large loss of process efficiency due to their inability to take advantage of agglomeration. The large quantities of ore that must be handled in metal extraction processes also means that the binder must be inexpensive and useful at low dosages to be economical. The acid-resistant binders and agglomeration procedures developed in this project will also be adapted for use in improving the energy efficiency and performance of a broad range of mineral agglomeration applications, particularly heap leaching. The active involvement of our industrial partners will help to ensure rapid commercialization of any agglomeration technologies developed by this project.
Final Report on Subcontract B605152. Multigrid Methods for Systems of PDEs
Brannick, James; Xu, Jinchao
2015-07-07
The project team has continued with work on developing aggressive coarsening techniques for AMG methods. Of particular interest is the idea to use aggressive coarsening with polynomial smoothing. Using local Fourier analysis the optimal values for the parameters involved in defining the polynomial smoothers are determined automatically in a way to achieve fast convergence of cycles with aggressive coarsening. Numerical tests have the sharpness of the theoretical results. The methods are highly parallelizable and efficient multigrid algorithms on structured and semistructured grids in two and three spatial dimensions.
A comparison of locally adaptive multigrid methods: LDC, FAC and FIC
NASA Technical Reports Server (NTRS)
Khadra, Khodor; Angot, Philippe; Caltagirone, Jean-Paul
1993-01-01
This study is devoted to a comparative analysis of three 'Adaptive ZOOM' (ZOom Overlapping Multi-level) methods based on similar concepts of hierarchical multigrid local refinement: LDC (Local Defect Correction), FAC (Fast Adaptive Composite), and FIC (Flux Interface Correction)--which we proposed recently. These methods are tested on two examples of a bidimensional elliptic problem. We compare, for V-cycle procedures, the asymptotic evolution of the global error evaluated by discrete norms, the corresponding local errors, and the convergence rates of these algorithms.
NOVEL BINDERS AND METHODS FOR AGGLOMERATION OF ORE
S.K. Kawatra; T.C. Eisele; J.A. Gurtler; C.A. Hardison; K. Lewandowski
2004-04-01
Many metal extraction operations, such as leaching of copper, leaching of precious metals, and reduction of metal oxides to metal in high-temperature furnaces, require agglomeration of ore to ensure that reactive liquids or gases are evenly distributed throughout the ore being processed. Agglomeration of ore into coarse, porous masses achieves this even distribution of fluids by preventing fine particles from migrating and clogging the spaces and channels between the larger ore particles. Binders are critically necessary to produce agglomerates that will not break down during processing. However, for many important metal extraction processes there are no binders known that will work satisfactorily. Primary examples of this are copper heap leaching, where there are no binders that will work in the acidic environment encountered in this process, and advanced ironmaking processes, where binders must function satisfactorily over an extraordinarily large range of temperatures (from room temperature up to over 1200 C). As a result, operators of many facilities see a large loss of process efficiency due to their inability to take advantage of agglomeration. The large quantities of ore that must be handled in metal extraction processes also means that the binder must be inexpensive and useful at low dosages to be economical. The acid-resistant binders and agglomeration procedures developed in this project will also be adapted for use in improving the energy efficiency and performance of a broad range of mineral agglomeration applications, particularly heap leaching and advanced primary ironmaking.
Novel Binders and Methods for Agglomeration of Ore
S. K. Kawatra; T. C. Eisele; J. A. Gurtler
2004-03-31
Many metal extraction operations, such as leaching of copper, leaching of precious metals, and reduction of metal oxides to metal in high-temperature furnaces, require agglomeration of ore to ensure that reactive liquids or gases are evenly distributed throughout the ore being processed. Agglomeration of ore into coarse, porous masses achieves this even distribution of fluids by preventing fine particles from migrating and clogging the spaces and channels between the larger ore particles. Binders are critically necessary to produce agglomerates that will not break down during processing. However, for many important metal extraction processes there are no binders known that will work satisfactorily. A primary example of this is copper heap leaching, where there are no binders that will work in the acidic environment encountered in this process. As a result, operators of acidic heap-leach facilities see a large loss of process efficiency due to their inability to take advantage of agglomeration. The large quantities of ore that must be handled in metal extraction processes also means that the binder must be inexpensive and useful at low dosages to be economical. The acid-resistant binders and agglomeration procedures developed in this project will also be adapted for use in improving the energy efficiency and performance of other agglomeration applications, particularly advanced primary ironmaking.
NOVEL BINDERS AND METHODS FOR AGGLOMERATION OF ORE
S.K. Kawatra; T.C. Eisele; J.A. Gurtler; K. Lewandowski
2005-04-01
Many metal extraction operations, such as leaching of copper, leaching of precious metals, and reduction of metal oxides to metal in high-temperature furnaces, require agglomeration of ore to ensure that reactive liquids or gases are evenly distributed throughout the ore being processed. Agglomeration of ore into coarse, porous masses achieves this even distribution of fluids by preventing fine particles from migrating and clogging the spaces and channels between the larger ore particles. Binders are critically necessary to produce agglomerates that will not breakdown during processing. However, for many important metal extraction processes there are no binders known that will work satisfactorily. Primary examples of this are copper heap leaching, where there are no binders that will work in the acidic environment encountered in this process. As a result, operators of many facilities see large loss of process efficiency due to their inability to take advantage of agglomeration. The large quantities of ore that must be handled in metal extraction processes also means that the binder must be inexpensive and useful at low dosages to be economical. The acid-resistant binders and agglomeration procedures developed in this project will also be adapted for use in improving the energy efficiency and performance of a broad range of mineral agglomeration applications, particularly heap leaching.
Multigrid methods for a semilinear PDE in the theory of pseudoplastic fluids
NASA Technical Reports Server (NTRS)
Henson, Van Emden; Shaker, A. W.
1993-01-01
We show that by certain transformations the boundary layer equations for the class of non-Newtonian fluids named pseudoplastic can be generalized in the form the vector differential operator(u) + p(x)u(exp -lambda) = 0, where x is a member of the set Omega and Omega is a subset of R(exp n), n is greater than or equal to 1 under the classical conditions for steady flow over a semi-infinite flat plate. We provide a survey of the existence, uniqueness, and analyticity of the solutions for this problem. We also establish numerical solutions in one- and two-dimensional regions using multigrid methods.
NASA Technical Reports Server (NTRS)
Liu, C.; Liu, Z.
1993-01-01
The fourth-order finite-difference scheme with fully implicit time-marching presently used to computationally study the spatial instability of planar Poiseuille flow incorporates a novel treatment for outflow boundary conditions that renders the buffer area as short as one wavelength. A semicoarsening multigrid method accelerates convergence for the implicit scheme at each time step; a line-distributive relaxation is developed as a robust fast solver that is efficient for anisotropic grids. Computational cost is no greater than that of explicit schemes, and excellent agreement with linear theory is obtained.
A multigrid integral equation method for large-scale models with inhomogeneous backgrounds
NASA Astrophysics Data System (ADS)
Endo, Masashi; Čuma, Martin; Zhdanov, Michael S.
2008-12-01
We present a multigrid integral equation (IE) method for three-dimensional (3D) electromagnetic (EM) field computations in large-scale models with inhomogeneous background conductivity (IBC). This method combines the advantages of the iterative IBC IE method and the multigrid quasi-linear (MGQL) approximation. The new EM modelling method solves the corresponding systems of linear equations within the domains of anomalous conductivity, Da, and inhomogeneous background conductivity, Db, separately on coarse grids. The observed EM fields in the receivers are computed using grids with fine discretization. The developed MGQL IBC IE method can also be applied iteratively by taking into account the return effect of the anomalous field inside the domain of the background inhomogeneity Db, and vice versa. The iterative process described above is continued until we reach the required accuracy of the EM field calculations in both domains, Da and Db. The method was tested for modelling the marine controlled-source electromagnetic field for complex geoelectrical structures with hydrocarbon petroleum reservoirs and a rough sea-bottom bathymetry.
Quasi-Newton and multigrid methods for semiconductor device simulation
Slamet, S.
1983-12-01
A finite difference approximation to the semiconductor device equations using the Bernoulli function approximation to the exponential function is described, and the robustness of this approximation is demonstrated. Sheikh's convergence analysis of Gummel's method and quasi-Newton methods is extended to a nonuniform mesh and the Bernoulli function discretization. It is proved that Gummel's method and the quasi-Newton methods for the scaled carrier densities and carrier densities converge locally for sufficiently smooth problems.
Sixth Copper Mountain Conference on Multigrid Methods. Final report
Not Available
1994-07-01
During the 5-day meeting, 112 half-hour talks on current research topics were presented. Session topics included: fluids, domain decomposition, iterative methods, Basics I and II, adaptive methods, nonlinear filtering, CFD I, II, and III, applications, transport, algebraic solvers, supercomputing, and student paper winners.
Ku, Bon Ki; Kulkarni, Pramod
2015-01-01
We compare different approaches to measure surface area of aerosol agglomerates. The objective was to compare field methods, such as mobility and diffusion charging based approaches, with laboratory approach, such as Brunauer, Emmett, Teller (BET) method used for bulk powder samples. To allow intercomparison of various surface area measurements, we defined ‘geometric surface area’ of agglomerates (assuming agglomerates are made up of ideal spheres), and compared various surface area measurements to the geometric surface area. Four different approaches for measuring surface area of agglomerate particles in the size range of 60–350 nm were compared using (i) diffusion charging-based sensors from three different manufacturers, (ii) mobility diameter of an agglomerate, (iii) mobility diameter of an agglomerate assuming a linear chain morphology with uniform primary particle size, and (iv) surface area estimation based on tandem mobility–mass measurement and microscopy. Our results indicate that the tandem mobility–mass measurement, which can be applied directly to airborne particles unlike the BET method, agrees well with the BET method. It was also shown that the three diffusion charging-based surface area measurements of silver agglomerates were similar within a factor of 2 and were lower than those obtained from the tandem mobility–mass and microscopy method by a factor of 3–10 in the size range studied. Surface area estimated using the mobility diameter depended on the structure or morphology of the agglomerate with significant underestimation at high fractal dimensions approaching 3. PMID:26692585
An angular multigrid method for computing mono-energetic particle beams in Flatland
Boergers, Christoph MacLachlan, Scott
2010-04-20
Beams of microscopic particles penetrating scattering background matter play an important role in several applications. The parameter choices made here are motivated by the problem of electron-beam cancer therapy planning. Mathematically, a steady particle beam penetrating matter, or a configuration of several such beams, is modeled by a boundary value problem for a Boltzmann equation. Grid-based discretization of such a problem leads to a system of algebraic equations. This system is typically very large because of the large number of independent variables in the Boltzmann equation-six if no dimension-reducing assumptions other than time independence are made. If grid-based methods are to be practical for these problems, it is therefore necessary to develop very fast solvers for the discretized problems. For beams of mono-energetic particles interacting with a passive background, but not with each other, in two space dimensions, the first author proposed such a solver, based on angular domain decomposition, some time ago. Here, we propose and test an angular multigrid algorithm for the same model problem. Our numerical experiments show rapid, grid-independent convergence. For high-resolution calculations, our method is substantially more efficient than the angular domain decomposition method. In addition, unlike angular domain decomposition, the angular multigrid method works well even when the angular diffusion coefficient is fairly large.
Multigrid methods for flow transition in three-dimensional boundary layers with surface roughness
NASA Technical Reports Server (NTRS)
Liu, Chaoqun; Liu, Zhining; Mccormick, Steve
1993-01-01
The efficient multilevel adaptive method has been successfully applied to perform direct numerical simulations (DNS) of flow transition in 3-D channels and 3-D boundary layers with 2-D and 3-D isolated and distributed roughness in a curvilinear coordinate system. A fourth-order finite difference technique on stretched and staggered grids, a fully-implicit time marching scheme, a semi-coarsening multigrid method associated with line distributive relaxation scheme, and an improved outflow boundary-condition treatment, which needs only a very short buffer domain to damp all order-one wave reflections, are developed. These approaches make the multigrid DNS code very accurate and efficient. This allows us not only to be able to do spatial DNS for the 3-D channel and flat plate at low computational costs, but also to do spatial DNS for transition in the 3-D boundary layer with 3-D single and multiple roughness elements, which would have extremely high computational costs with conventional methods. Numerical results show good agreement with the linear stability theory, the secondary instability theory, and a number of laboratory experiments. The contribution of isolated and distributed roughness to transition is analyzed.
Adaptive multi-grid method for a periodic heterogeneous medium in 1-D
Fish, J.; Belsky, V.
1995-12-31
A multi-grid method for a periodic heterogeneous medium in 1-D is presented. Based on the homogenization theory special intergrid connection operators have been developed to imitate a low frequency response of the differential equations with oscillatory coefficients. The proposed multi-grid method has been proved to have a fast rate of convergence governed by the ratio q/(4-q), where o
Combustor flow computations in general coordinates with a multigrid method
NASA Astrophysics Data System (ADS)
Shyy, Wei; Braaten, Mark E.
The computational approach presented for single-phase combusting turbulent flowfields balances the requirements of complex physical and chemical flow interactions with those of resolving the three-dimensional geometrical constraints of the combustor contours, film cooling slots, and circular dilution holes. Attention is given to the three-dimensional grid-generation algorithm, the two-dimensional adaptive grid method applied to recirculating turbulent reacting flows, and theory/data assessments for three-dimensional combusting flows in an annular gas turbine combustor.
On multigrid methods for image reconstruction from projections
Henson, V.E.; Robinson, B.T.; Limber, M.
1994-12-31
The sampled Radon transform of a 2D function can be represented as a continuous linear map R : L{sup 1} {yields} R{sup N}. The image reconstruction problem is: given a vector b {element_of} R{sup N}, find an image (or density function) u(x, y) such that Ru = b. Since in general there are infinitely many solutions, the authors pick the solution with minimal 2-norm. Numerous proposals have been made regarding how best to discretize this problem. One can, for example, select a set of functions {phi}{sub j} that span a particular subspace {Omega} {contained_in} L{sup 1}, and model R : {Omega} {yields} R{sup N}. The subspace {Omega} may be chosen as a member of a sequence of subspaces whose limit is dense in L{sup 1}. One approach to the choice of {Omega} gives rise to a natural pixel discretization of the image space. Two possible choices of the set {phi}{sub j} are the set of characteristic functions of finite-width `strips` representing energy transmission paths and the set of intersections of such strips. The authors have studied the eigenstructure of the matrices B resulting from these choices and the effect of applying a Gauss-Seidel iteration to the problem Bw = b. There exists a near null space into which the error vectors migrate with iteration, after which Gauss-Seidel iteration stalls. The authors attempt to accelerate convergence via a multilevel scheme, based on the principles of McCormick`s Multilevel Projection Method (PML). Coarsening is achieved by thickening the rays which results in a much smaller discretization of an optimal grid, and a halving of the number of variables. This approach satisfies all the requirements of the PML scheme. They have observed that a multilevel approach based on this idea accelerates convergence at least to the point where noise in the data dominates.
NASA Technical Reports Server (NTRS)
1981-01-01
Developments in numerical solution of certain types of partial differential equations by rapidly converging sequences of operations on supporting grids that range from very fine to very coarse are presented.
Multigrid on massively parallel architectures
Falgout, R D; Jones, J E
1999-09-17
The scalable implementation of multigrid methods for machines with several thousands of processors is investigated. Parallel performance models are presented for three different structured-grid multigrid algorithms, and a description is given of how these models can be used to guide implementation. Potential pitfalls are illustrated when moving from moderate-sized parallelism to large-scale parallelism, and results are given from existing multigrid codes to support the discussion. Finally, the use of mixed programming models is investigated for multigrid codes on clusters of SMPs.
Multigrid one shot methods for optimal control problems: Infinite dimensional control
NASA Technical Reports Server (NTRS)
Arian, Eyal; Taasan, Shlomo
1994-01-01
The multigrid one shot method for optimal control problems, governed by elliptic systems, is introduced for the infinite dimensional control space. ln this case, the control variable is a function whose discrete representation involves_an increasing number of variables with grid refinement. The minimization algorithm uses Lagrange multipliers to calculate sensitivity gradients. A preconditioned gradient descent algorithm is accelerated by a set of coarse grids. It optimizes for different scales in the representation of the control variable on different discretization levels. An analysis which reduces the problem to the boundary is introduced. It is used to approximate the two level asymptotic convergence rate, to determine the amplitude of the minimization steps, and the choice of a high pass filter to be used when necessary. The effectiveness of the method is demonstrated on a series of test problems. The new method enables the solutions of optimal control problems at the same cost of solving the corresponding analysis problems just a few times.
NASA Technical Reports Server (NTRS)
Atkins, H. L.; Helenbrook, B. T.
2005-01-01
This paper describes numerical experiments with P-multigrid to corroborate analysis, validate the present implementation, and to examine issues that arise in the implementations of the various combinations of relaxation schemes, discretizations and P-multigrid methods. The two approaches to implement P-multigrid presented here are equivalent for most high-order discretization methods such as spectral element, SUPG, and discontinuous Galerkin applied to advection; however it is discovered that the approach that mimics the common geometric multigrid implementation is less robust, and frequently unstable when applied to discontinuous Galerkin discretizations of di usion. Gauss-Seidel relaxation converges 40% faster than block Jacobi, as predicted by analysis; however, the implementation of Gauss-Seidel is considerably more expensive that one would expect because gradients in most neighboring elements must be updated. A compromise quasi Gauss-Seidel relaxation method that evaluates the gradient in each element twice per iteration converges at rates similar to those predicted for true Gauss-Seidel.
Multigrid Method for Modeling Multi-Dimensional Combustion with Detailed Chemistry
NASA Technical Reports Server (NTRS)
Zheng, Xiaoqing; Liu, Chaoqun; Liao, Changming; Liu, Zhining; McCormick, Steve
1996-01-01
A highly accurate and efficient numerical method is developed for modeling 3-D reacting flows with detailed chemistry. A contravariant velocity-based governing system is developed for general curvilinear coordinates to maintain simplicity of the continuity equation and compactness of the discretization stencil. A fully-implicit backward Euler technique and a third-order monotone upwind-biased scheme on a staggered grid are used for the respective temporal and spatial terms. An efficient semi-coarsening multigrid method based on line-distributive relaxation is used as the flow solver. The species equations are solved in a fully coupled way and the chemical reaction source terms are treated implicitly. Example results are shown for a 3-D gas turbine combustor with strong swirling inflows.
A Full Multi-Grid Method for the Solution of the Cell Vertex Finite Volume Cauchy-Riemann Equations
NASA Technical Reports Server (NTRS)
Borzi, A.; Morton, K. W.; Sueli, E.; Vanmaele, M.
1996-01-01
The system of inhomogeneous Cauchy-Riemann equations defined on a square domain and subject to Dirichlet boundary conditions is considered. This problem is discretised by using the cell vertex finite volume method on quadrilateral meshes. The resulting algebraic problem is overdetermined and the solution is defined in a least squares sense. By this approach a consistent algebraic problem is obtained which differs from the original one by O(h(exp 2)) perturbations of the right-hand side. A suitable cell-based convergent smoothing iteration is presented which is naturally linked to the least squares formulation. Hence, a standard multi-grid algorithm is reported which combines the given smoother and cell-based transfer operators. Some remarkable reduction properties of these operators are shown. A full multi-grid method is discussed which solves the discrete problem to the level of truncation error by employing one multi-grid cycle at each current level of discretisation. Experiments and applications of the full multi-grid scheme are presented.
Magnetic agglomeration method for size control in the synthesis of magnetic nanoparticles
Huber, Dale L.
2011-07-05
A method for controlling the size of chemically synthesized magnetic nanoparticles that employs magnetic interaction between particles to control particle size and does not rely on conventional kinetic control of the reaction to control particle size. The particles are caused to reversibly agglomerate and precipitate from solution; the size at which this occurs can be well controlled to provide a very narrow particle size distribution. The size of particles is controllable by the size of the surfactant employed in the process; controlling the size of the surfactant allows magnetic control of the agglomeration and precipitation processes. Agglomeration is used to effectively stop particle growth to provide a very narrow range of particle sizes.
A cell-vertex multigrid method for the Navier-Stokes equations
NASA Technical Reports Server (NTRS)
Radespiel, R.
1989-01-01
A cell-vertex scheme for the Navier-Stokes equations, which is based on central difference approximations and Runge-Kutta time stepping, is described. Using local time stepping, implicit residual smoothing, a multigrid method, and carefully controlled artificial dissipative terms, very good convergence rates are obtained for a wide range of two- and three-dimensional flows over airfoils and wings. The accuracy of the code is examined by grid refinement studies and comparison with experimental data. For an accurate prediction of turbulent flows with strong separations, a modified version of the nonequilibrium turbulence model of Johnson and King is introduced, which is well suited for an implementation into three-dimensional Navier-Stokes codes. It is shown that the solutions for three-dimensional flows with strong separations can be dramatically improved, when a nonequilibrium model of turbulence is used.
Practical improvements of multi-grid iteration for adaptive mesh refinement method
NASA Astrophysics Data System (ADS)
Miyashita, Hisashi; Yamada, Yoshiyuki
2005-03-01
Adaptive mesh refinement(AMR) is a powerful tool to efficiently solve multi-scaled problems. However, the vanilla AMR method has a well-known critical demerit, i.e., it cannot be applied to non-local problems. Although multi-grid iteration (MGI) can be regarded as a good remedy for a non-local problem such as the Poisson equation, we observed fundamental difficulties in applying the MGI technique in AMR to realistic problems under complicated mesh layouts because it does not converge or it requires too many iterations even if it does converge. To cope with the problem, when updating the next approximation in the MGI process, we calculate the precise total corrections that are relatively accurate to the current residual by introducing a new iteration for such a total correction. This procedure greatly accelerates the MGI convergence speed especially under complicated mesh layouts.
NASA Technical Reports Server (NTRS)
Zeng, S.; Wesseling, P.
1993-01-01
The performance of a linear multigrid method using four smoothing methods, called SCGS (Symmetrical Coupled GauBeta-Seidel), CLGS (Collective Line GauBeta-Seidel), SILU (Scalar ILU), and CILU (Collective ILU), is investigated for the incompressible Navier-Stokes equations in general coordinates, in association with Galerkin coarse grid approximation. Robustness and efficiency are measured and compared by application to test problems. The numerical results show that CILU is the most robust, SILU the least, with CLGS and SCGS in between. CLGS is the best in efficiency, SCGS and CILU follow, and SILU is the worst.
An Introduction to Algebraic Multigrid
Falgout, R D
2006-04-25
Algebraic multigrid (AMG) solves linear systems based on multigrid principles, but in a way that only depends on the coefficients in the underlying matrix. The author begins with a basic introduction to AMG methods, and then describes some more recent advances and theoretical developments
A parallel geometric multigrid method for finite elements on octree meshes
Sampath, Rahul S; Biros, George
2010-01-01
In this article, we present a parallel geometric multigrid algorithm for solving variable-coefficient elliptic partial differential equations on the unit box (with Dirichlet or Neumann boundary conditions) using highly nonuniform, octree-based, conforming finite element discretizations. Our octrees are 2:1 balanced, that is, we allow no more than one octree-level difference between octants that share a face, edge, or vertex. We describe a parallel algorithm whose input is an arbitrary 2:1 balanced fine-grid octree and whose output is a set of coarser 2:1 balanced octrees that are used in the multigrid scheme. Also, we derive matrix-free schemes for the discretized finite element operators and the intergrid transfer operations. The overall scheme is second-order accurate for sufficiently smooth right-hand sides and material properties; its complexity for nearly uniform trees is {Omicron}(N/n{sub p} log N/n{sub p}) + {Omicron}(n{sub p} log n{sub p}), where N is the number of octree nodes and n{sub p} is the number of processors. Our implementation uses the Message Passing Interface standard. We present numerical experiments for the Laplace and Navier (linear elasticity) operators that demonstrate the scalability of our method. Our largest run was a highly nonuniform, 8-billion-unknown, elasticity calculation using 32,000 processors on the Teragrid system, 'Ranger,' at the Texas Advanced Computing Center. Our implementation is publically available in the Dendro library, which is built on top of the PETSc library from Argonne National Laboratory.
Toward robust scalable algebraic multigrid solvers.
Waisman, Haim; Schroder, Jacob; Olson, Luke; Hiriyur, Badri; Gaidamour, Jeremie; Siefert, Christopher; Hu, Jonathan Joseph; Tuminaro, Raymond Stephen
2010-10-01
This talk highlights some multigrid challenges that arise from several application areas including structural dynamics, fluid flow, and electromagnetics. A general framework is presented to help introduce and understand algebraic multigrid methods based on energy minimization concepts. Connections between algebraic multigrid prolongators and finite element basis functions are made to explored. It is shown how the general algebraic multigrid framework allows one to adapt multigrid ideas to a number of different situations. Examples are given corresponding to linear elasticity and specifically in the solution of linear systems associated with extended finite elements for fracture problems.
NASA Astrophysics Data System (ADS)
Jönsthövel, T. B.; van Gijzen, M. B.; MacLachlan, S.; Vuik, C.; Scarpas, A.
2012-09-01
Many applications in computational science and engineering concern composite materials, which are characterized by large discontinuities in the material properties. Such applications require fine-scale finite-element meshes, which lead to large linear systems that are challenging to solve with current direct and iterative solutions algorithms. In this paper, we consider the simulation of asphalt concrete, which is a mixture of components with large differences in material stiffness. The discontinuities in material stiffness give rise to many small eigenvalues that negatively affect the convergence of iterative solution algorithms such as the preconditioned conjugate gradient (PCG) method. This paper considers the deflated preconditioned conjugate gradient (DPCG) method in which the rigid body modes of sets of elements with homogeneous material properties are used as deflation vectors. As preconditioner we consider several variants of the algebraic multigrid smoothed aggregation method. We evaluate the performance of the DPCG method on a parallel computer using up to 64 processors. Our test problems are derived from real asphalt core samples, obtained using CT scans. We show that the DPCG method is an efficient and robust technique for solving these challenging linear systems.
NASA Technical Reports Server (NTRS)
Atkins, Harold
1991-01-01
A multiple block multigrid method for the solution of the three dimensional Euler and Navier-Stokes equations is presented. The basic flow solver is a cell vertex method which employs central difference spatial approximations and Runge-Kutta time stepping. The use of local time stepping, implicit residual smoothing, multigrid techniques and variable coefficient numerical dissipation results in an efficient and robust scheme is discussed. The multiblock strategy places the block loop within the Runge-Kutta Loop such that accuracy and convergence are not affected by block boundaries. This has been verified by comparing the results of one and two block calculations in which the two block grid is generated by splitting the one block grid. Results are presented for both Euler and Navier-Stokes computations of wing/fuselage combinations.
NASA Astrophysics Data System (ADS)
Zhu, Yu; Cangellaris, Andreas C.
2002-05-01
A new finite element methodology is presented for fast and robust numerical simulation of three-dimensional electromagnetic wave phenomena. The new methodology combines nested multigrid techniques with the ungauged vector and scalar potential formulation of the finite element method. The finite element modeling is performed on nested meshes over the computational domain of interest. The iterative solution of the finite element matrix on the finest mesh is performed using the conjugate gradient method, while the nested multigrid vector and scalar potential algorithm acts as the preconditioner for the iterative solver. Numerical experiments from the application of the new methodology to three-dimensional electromagnetic scattering are used to demonstrate its superior numerical convergence and efficient memory usage.
Development of a pressure based multigrid solution method for complex fluid flows
NASA Technical Reports Server (NTRS)
Shyy, Wei
1991-01-01
In order to reduce the computational difficulty associated with a single grid (SG) solution procedure, the multigrid (MG) technique was identified as a useful means for improving the convergence rate of iterative methods. A full MG full approximation storage (FMG/FAS) algorithm is used to solve the incompressible recirculating flow problems in complex geometries. The algorithm is implemented in conjunction with a pressure correction staggered grid type of technique using the curvilinear coordinates. In order to show the performance of the method, two flow configurations, one a square cavity and the other a channel, are used as test problems. Comparisons are made between the iterations, equivalent work units, and CPU time. Besides showing that the MG method can yield substantial speed-up with wide variations in Reynolds number, grid distributions, and geometry, issues such as the convergence characteristics of different grid levels, the choice of convection schemes, and the effectiveness of the basic iteration smoothers are studied. An adaptive grid scheme is also combined with the MG procedure to explore the effects of grid resolution on the MG convergence rate as well as the numerical accuracy.
Peláez, Daniel; Meyer, Hans-Dieter
2013-01-01
In this article, a new method, multigrid POTFIT (MGPF), is presented. MGPF is a grid-based algorithm which transforms a general potential energy surface into product form, that is, a sum of products of one-dimensional functions. This form is necessary to profit from the computationally advantageous multiconfiguration time-dependent Hartree method for quantum dynamics. MGPF circumvents the dimensionality related issues present in POTFIT [A. Jäckle and H.-D. Meyer, J. Chem. Phys. 104, 7974 (1996)], allowing quantum dynamical studies of systems up to about 12 dimensions. MGPF requires the definition of a fine grid and a coarse grid, the latter being a subset of the former. The MGPF approximation relies on a series of underlying POTFIT calculations on grids which are smaller than the fine one and larger than or equal to the coarse one. This aspect makes MGPF a bit less accurate than POTFIT but orders of magnitude faster and orders of magnitude less memory demanding than POTFIT. Moreover, like POTFIT, MGPF is variational and provides an efficient error control. PMID:23298029
NASA Technical Reports Server (NTRS)
Liu, C.; Liu, Z.
1993-01-01
The high order finite difference and multigrid methods have been successfully applied to direct numerical simulation (DNS) for flow transition in 3D channels and 3D boundary layers with 2D and 3D isolated and distributed roughness in a curvilinear coordinate system. A fourth-order finite difference technique on stretched and staggered grids, a fully-implicit time marching scheme, a semicoarsening multigrid method associated with line distributive relaxation scheme, and a new treatment of the outflow boundary condition, which needs only a very short buffer domain to damp all wave reflection, are developed. These approaches make the multigrid DNS code very accurate and efficient. This makes us not only able to do spatial DNS for the 3D channel and flat plate at low computational costs, but also able to do spatial DNS for transition in the 3D boundary layer with 3D single and multiple roughness elements. Numerical results show good agreement with the linear stability theory, the secondary instability theory, and a number of laboratory experiments.
Filtering Algebraic Multigrid and Adaptive Strategies
Nagel, A; Falgout, R D; Wittum, G
2006-01-31
Solving linear systems arising from systems of partial differential equations, multigrid and multilevel methods have proven optimal complexity and efficiency properties. Due to shortcomings of geometric approaches, algebraic multigrid methods have been developed. One example is the filtering algebraic multigrid method introduced by C. Wagner. This paper proposes a variant of Wagner's method with substantially improved robustness properties. The method is used in an adaptive, self-correcting framework and tested numerically.
Final Report on Subcontract B591217: Multigrid Methods for Systems of PDEs
Xu, J; Brannick, J J; Zikatanov, L
2011-10-25
Progress is summarized in the following areas of study: (1) Compatible relaxation; (2) Improving aggregation-based MG solver performance - variable cycle; (3) First Order System Least Squares (FOSLS) for LQCD; (4) Auxiliary space preconditioners; (5) Bootstrap algebraic multigrid; and (6) Practical applications of AMG and fast auxiliary space preconditioners.
Element Agglomeration Algebraic Multigrid and Upscaling Library
Energy Science and Technology Software Center (ESTSC)
2015-02-11
ELAG is a serial C++ library for numerical upscaling of finite element discretizations. It provides optimal complexity algorithms to build multilevel hierarchies and solvers that can be used for solving a wide class of partial differential equation (elliptic, hyperbolic, saddle point problems) on general unstructured mesh. Additionally, a novel multilevel solver for saddle point problems with divergence constraint is implemented.
Another look at neural multigrid
Baeker, M.
1997-04-01
We present a new multigrid method called neural multigrid which is based on joining multigrid ideas with concepts from neural nets. The main idea is to use the Greenbaum criterion as a cost functional for the neural net. The algorithm is able to learn efficient interpolation operators in the case of the ordered Laplace equation with only a very small critical slowing down and with a surprisingly small amount of work comparable to that of a Conjugate Gradient solver. In the case of the two-dimensional Laplace equation with SU(2) gauge fields at {beta}=0 the learning exhibits critical slowing down with an exponent of about z {approx} 0.4. The algorithm is able to find quite good interpolation operators in this case as well. Thereby it is proven that a practical true multigrid algorithm exists even for a gauge theory. An improved algorithm using dynamical blocks that will hopefully overcome the critical slowing down completely is sketched.
Lignite pellets and methods of agglomerating or pelletizing
Baker, Albert F.; Blaustein, Eric W.; Deurbrouck, Albert W.; Garvin, John P.; McKeever, Robert E.
1981-01-01
The specification discloses lignite pellets which are relatively hard, dust resistant, of generally uniform size and free from spontaneous ignition and general degradation. Also disclosed are methods for making such pellets which involve crushing as mined lignite, mixing said lignite with a binder such as asphalt, forming the lignite binder mixture into pellets, and drying the pellets.
New convergence estimates for multigrid algorithms
Bramble, J.H.; Pasciak, J.E.
1987-10-01
In this paper, new convergence estimates are proved for both symmetric and nonsymmetric multigrid algorithms applied to symmetric positive definite problems. Our theory relates the convergence of multigrid algorithms to a ''regularity and approximation'' parameter ..cap alpha.. epsilon (0, 1) and the number of relaxations m. We show that for the symmetric and nonsymmetric ..nu.. cycles, the multigrid iteration converges for any positive m at a rate which deteriorates no worse than 1-cj/sup -(1-//sup ..cap alpha..//sup )///sup ..cap alpha../, where j is the number of grid levels. We then define a generalized ..nu.. cycle algorithm which involves exponentially increasing (for example, doubling) the number of smoothings on successively coarser grids. We show that the resulting symmetric and nonsymmetric multigrid iterations converge for any ..cap alpha.. with rates that are independent of the mesh size. The theory is presented in an abstract setting which can be applied to finite element multigrid and finite difference multigrid methods.
NASA Technical Reports Server (NTRS)
Demuren, A. O.
1990-01-01
A multigrid method is presented for calculating turbulent jets in crossflow. Fairly rapid convergence is obtained with the k-epsilon turbulence model, but computations with a full Reynolds stress turbulence model (RSM) are not yet very efficient. Grid dependency tests show that there are slight differences between results obtained on the two finest grid levels. Computations using the RSM are significantly different from those with k-epsilon model and compare better to experimental data. Some work is still required to improve the efficiency of the computations with the RSM.
An Optimal Order Nonnested Mixed Multigrid Method for Generalized Stokes Problems
NASA Technical Reports Server (NTRS)
Deng, Qingping
1996-01-01
A multigrid algorithm is developed and analyzed for generalized Stokes problems discretized by various nonnested mixed finite elements within a unified framework. It is abstractly proved by an element-independent analysis that the multigrid algorithm converges with an optimal order if there exists a 'good' prolongation operator. A technique to construct a 'good' prolongation operator for nonnested multilevel finite element spaces is proposed. Its basic idea is to introduce a sequence of auxiliary nested multilevel finite element spaces and define a prolongation operator as a composite operator of two single grid level operators. This makes not only the construction of a prolongation operator much easier (the final explicit forms of such prolongation operators are fairly simple), but the verification of the approximate properties for prolongation operators is also simplified. Finally, as an application, the framework and technique is applied to seven typical nonnested mixed finite elements.
Lee, Barry
2010-05-01
This paper presents a new multigrid method applied to the most common Sn discretizations (Petrov-Galerkin, diamond-differenced, corner-balanced, and discontinuous Galerkin) of the mono-energetic Boltzmann transport equation in the optically thick and thin regimes, and with strong anisotropic scattering. Unlike methods that use scalar DSA diffusion preconditioners for the source iteration, this multigrid method is applied directly to an integral equation for the scalar flux. Thus, unlike the former methods that apply a multigrid strategy to the scalar DSA diffusion operator, this method applies a multigrid strategy to the integral source iteration operator, which is an operator for 5 independent variables in spatial 3-d (3 in space and 2 in angle) and 4 independent variables in spatial 2-d (2 in space and 2 in angle). The core smoother of this multigrid method involves applications of the integral operator. Since the kernel of this integral operator involves the transport sweeps, applying this integral operator requires a transport sweep (an inversion of an upper triagular matrix) for each of the angles used. As the equation is in 5-space or 4-space, the multigrid approach in this paper coarsens in both angle and space, effecting efficient applications of the coarse integral operators. Although each V-cycle of this method is more expensive than a V-cycle for the DSA preconditioner, since the DSA equation does not have angular dependence, the overall computational efficiency is about the same for problems where DSA preconditioning {\\it is} effective. This new method also appears to be more robust over all parameter regimes than DSA approaches. Moreover, this new method is applicable to a variety of Sn spatial discretizations, to problems involving a combination of optically thick and thin regimes, and more importantly, to problems with anisotropic scattering cross-sections, all of which DSA approaches perform poorly or not applicable at all. This multigrid approach
Multicloud: Multigrid convergence with a meshless operator
Katz, Aaron Jameson, Antony
2009-08-01
The primary objective of this work is to develop and test a new convergence acceleration technique we call multicloud. Multicloud is well-founded in the mathematical basis of multigrid, but relies on a meshless operator on coarse levels. The meshless operator enables extremely simple and automatic coarsening procedures for arbitrary meshes using arbitrary fine level discretization schemes. The performance of multicloud is compared with established multigrid techniques for structured and unstructured meshes for the Euler equations on two-dimensional test cases. Results indicate comparable convergence rates per unit work for multicloud and multigrid. However, because of its mesh and scheme transparency, multicloud may be applied to a wide array of problems with no modification of fine level schemes as is often required with agglomeration techniques. The implication is that multicloud can be implemented in a completely modular fashion, allowing researchers to develop fine level algorithms independent of the convergence accelerator for complex three-dimensional problems.
Self-correcting Multigrid Solver
Jerome L.V. Lewandowski
2004-06-29
A new multigrid algorithm based on the method of self-correction for the solution of elliptic problems is described. The method exploits information contained in the residual to dynamically modify the source term (right-hand side) of the elliptic problem. It is shown that the self-correcting solver is more efficient at damping the short wavelength modes of the algebraic error than its standard equivalent. When used in conjunction with a multigrid method, the resulting solver displays an improved convergence rate with no additional computational work.
NASA Astrophysics Data System (ADS)
Chern, R. L.; Chang, C. Chung; Chang, Chien C.; Hwang, R. R.
2003-08-01
In this study, two fast and accurate methods of inverse iteration with multigrid acceleration are developed to compute band structures of photonic crystals of general shape. In particular, we report two-dimensional photonic crystals of silicon air with an optimal full band gap of gap-midgap ratio Δω/ωmid=0.2421, which is 30% larger than ever reported in the literature. The crystals consist of a hexagonal array of circular columns, each connected to its nearest neighbors by slender rectangular rods. A systematic study with respect to the geometric parameters of the photonic crystals was made possible with the present method in drawing a three-dimensional band-gap diagram with reasonable computing time.
Chern, R L; Chang, C Chung; Chang, Chien C; Hwang, R R
2003-08-01
In this study, two fast and accurate methods of inverse iteration with multigrid acceleration are developed to compute band structures of photonic crystals of general shape. In particular, we report two-dimensional photonic crystals of silicon air with an optimal full band gap of gap-midgap ratio Deltaomega/omega(mid)=0.2421, which is 30% larger than ever reported in the literature. The crystals consist of a hexagonal array of circular columns, each connected to its nearest neighbors by slender rectangular rods. A systematic study with respect to the geometric parameters of the photonic crystals was made possible with the present method in drawing a three-dimensional band-gap diagram with reasonable computing time. PMID:14525145
Multigrid for locally refined meshes
Shapira, Y.
1999-12-01
A multilevel method for the solution of finite element schemes on locally refined meshes is introduced. For isotropic diffusion problems, the condition number of the two-level method is bounded independently of the mesh size and the discontinuities in the diffusion coefficient. The curves of discontinuity need not be aligned with the coarse mesh. Indeed, numerical applications with 10 levels of local refinement yield a rapid convergence of the corresponding 10-level, multigrid V-cycle and other multigrid cycles which are more suitable for parallelism even when the discontinuities are invisible on most of the coarse meshes.
Canonical-variables multigrid method for steady-state Euler equations
NASA Technical Reports Server (NTRS)
Taasan, Shlomo
1994-01-01
A novel approach for the solution of inviscid flow problems for subsonic compressible flows is described. The approach is based on canonical forms of the equations, in which subsystems governed by hyperbolic operators are separated from those governed by elliptic ones. The discretizations used as well as the iterative techniques for the different subsystems are inherently different. Hyperbolic parts, which describe, in general, propagation phenomena, are discretized using upwind schemes and are solved by marching techniques. Elliptic parts, which are directionally unbiased, are discretized using h-elliptic central discretizations, and are solved by pointwise relaxations together with coarse grid acceleration. The resulting discretization schemes introduce artificial viscosity only for the hyperbolic parts of the system; thus a smaller total artificial viscosity is used, while the multigrid solvers used are much more efficient. Solutions of the subsonic compressible Euler equations are achieved at the same efficiency as the full potential equation.
MGLab: An Interactive Multigrid Environment
NASA Technical Reports Server (NTRS)
Bordner, James; Saied, Faisal
1996-01-01
MGLab is a set of Matlab functions that defines an interactive environment for experimenting with multigrid algorithms. The package solves two-dimensional elliptic partial differential equations discretized using either finite differences or finite volumes, depending on the problem. Built-in problems include the Poisson equation, the Helmholtz equation, a convection-diffusion problem, and a discontinuous coefficient problem. A number of parameters controlling the multigrid V-cycle can be set using a point-and-click mechanism. The menu-based user interface also allows a choice of several Krylov subspace methods, including CG, GMRES(k), and Bi-CGSTAB, which can be used either as stand-alone solvers or as multigrid acceleration schemes. The package exploits Matlab's visualization and sparse matrix features and has been structured to be easily extensible.
NASA Technical Reports Server (NTRS)
Yang, Cheng I.; Guo, Yan-Hu; Liu, C.- H.
1996-01-01
The analysis and design of a submarine propulsor requires the ability to predict the characteristics of both laminar and turbulent flows to a higher degree of accuracy. This report presents results of certain benchmark computations based on an upwind, high-resolution, finite-differencing Navier-Stokes solver. The purpose of the computations is to evaluate the ability, the accuracy and the performance of the solver in the simulation of detailed features of viscous flows. Features of interest include flow separation and reattachment, surface pressure and skin friction distributions. Those features are particularly relevant to the propulsor analysis. Test cases with a wide range of Reynolds numbers are selected; therefore, the effects of the convective and the diffusive terms of the solver can be evaluated separately. Test cases include flows over bluff bodies, such as circular cylinders and spheres, at various low Reynolds numbers, flows over a flat plate with and without turbulence effects, and turbulent flows over axisymmetric bodies with and without propulsor effects. Finally, to enhance the iterative solution procedure, a full approximation scheme V-cycle multigrid method is implemented. Preliminary results indicate that the method significantly reduces the computational effort.
NASA Astrophysics Data System (ADS)
Debreu, Laurent; Neveu, Emilie; Simon, Ehouarn; Le Dimet, Francois Xavier; Vidard, Arthur
2014-05-01
In order to lower the computational cost of the variational data assimilation process, we investigate the use of multigrid methods to solve the associated optimal control system. On a linear advection equation, we study the impact of the regularization term on the optimal control and the impact of discretization errors on the efficiency of the coarse grid correction step. We show that even if the optimal control problem leads to the solution of an elliptic system, numerical errors introduced by the discretization can alter the success of the multigrid methods. The view of the multigrid iteration as a preconditioner for a Krylov optimization method leads to a more robust algorithm. A scale dependent weighting of the multigrid preconditioner and the usual background error covariance matrix based preconditioner is proposed and brings significant improvements. [1] Laurent Debreu, Emilie Neveu, Ehouarn Simon, François-Xavier Le Dimet and Arthur Vidard, 2014: Multigrid solvers and multigrid preconditioners for the solution of variational data assimilation problems, submitted to QJRMS, http://hal.inria.fr/hal-00874643 [2] Emilie Neveu, Laurent Debreu and François-Xavier Le Dimet, 2011: Multigrid methods and data assimilation - Convergence study and first experiments on non-linear equations, ARIMA, 14, 63-80, http://intranet.inria.fr/international/arima/014/014005.html
Large-Scale Parallel Viscous Flow Computations using an Unstructured Multigrid Algorithm
NASA Technical Reports Server (NTRS)
Mavriplis, Dimitri J.
1999-01-01
The development and testing of a parallel unstructured agglomeration multigrid algorithm for steady-state aerodynamic flows is discussed. The agglomeration multigrid strategy uses a graph algorithm to construct the coarse multigrid levels from the given fine grid, similar to an algebraic multigrid approach, but operates directly on the non-linear system using the FAS (Full Approximation Scheme) approach. The scalability and convergence rate of the multigrid algorithm are examined on the SGI Origin 2000 and the Cray T3E. An argument is given which indicates that the asymptotic scalability of the multigrid algorithm should be similar to that of its underlying single grid smoothing scheme. For medium size problems involving several million grid points, near perfect scalability is obtained for the single grid algorithm, while only a slight drop-off in parallel efficiency is observed for the multigrid V- and W-cycles, using up to 128 processors on the SGI Origin 2000, and up to 512 processors on the Cray T3E. For a large problem using 25 million grid points, good scalability is observed for the multigrid algorithm using up to 1450 processors on a Cray T3E, even when the coarsest grid level contains fewer points than the total number of processors.
Vectorized multigrid Poisson solver for the CDC CYBER 205
NASA Technical Reports Server (NTRS)
Barkai, D.; Brandt, M. A.
1984-01-01
The full multigrid (FMG) method is applied to the two dimensional Poisson equation with Dirichlet boundary conditions. This has been chosen as a relatively simple test case for examining the efficiency of fully vectorizing of the multigrid method. Data structure and programming considerations and techniques are discussed, accompanied by performance details.
Tsujita, K.; Endo, T.; Yamamoto, A.
2013-07-01
An efficient numerical method for time-dependent transport equation, the mutigrid amplitude function (MAF) method, is proposed. The method of characteristics (MOC) is being widely used for reactor analysis thanks to the advances of numerical algorithms and computer hardware. However, efficient kinetic calculation method for MOC is still desirable since it requires significant computation time. Various efficient numerical methods for solving the space-dependent kinetic equation, e.g., the improved quasi-static (IQS) and the frequency transform methods, have been developed so far mainly for diffusion calculation. These calculation methods are known as effective numerical methods and they offer a way for faster computation. However, they have not been applied to the kinetic calculation method using MOC as the authors' knowledge. Thus, the MAF method is applied to the kinetic calculation using MOC aiming to reduce computation time. The MAF method is a unified numerical framework of conventional kinetic calculation methods, e.g., the IQS, the frequency transform, and the theta methods. Although the MAF method is originally developed for the space-dependent kinetic calculation based on the diffusion theory, it is extended to transport theory in the present study. The accuracy and computational time are evaluated though the TWIGL benchmark problem. The calculation results show the effectiveness of the MAF method. (authors)
NASA Technical Reports Server (NTRS)
1982-01-01
Papers presented in this volume provide an overview of recent work on numerical boundary condition procedures and multigrid methods. The topics discussed include implicit boundary conditions for the solution of the parabolized Navier-Stokes equations for supersonic flows; far field boundary conditions for compressible flows; and influence of boundary approximations and conditions on finite-difference solutions. Papers are also presented on fully implicit shock tracking and on the stability of two-dimensional hyperbolic initial boundary value problems for explicit and implicit schemes.
Toward textbook multigrid efficiency for fully implicit resistive magnetohydrodynamics
Adams, Mark F.; Samtaney, Ravi; Brandt, Achi
2013-12-14
Multigrid methods can solve some classes of elliptic and parabolic equations to accuracy below the truncation error with a work-cost equivalent to a few residual calculations – so-called “textbook” multigrid efficiency. We investigate methods to solve the system of equations that arise in time dependent magnetohydrodynamics (MHD) simulations with textbook multigrid efficiency. We apply multigrid techniques such as geometric interpolation, full approximate storage, Gauss-Seidel smoothers, and defect correction for fully implicit, nonlinear, second-order finite volume discretizations of MHD. We apply these methods to a standard resistive MHD benchmark problem, the GEM reconnection problem, and add a strong magnetic guide field, which is a critical characteristic of magnetically confined fusion plasmas. We show that our multigrid methods can achieve near textbook efficiency on fully implicit resistive MHD simulations.
Toward textbook multigrid efficiency for fully implicit resistive magnetohydrodynamics
Adams, Mark F.; Samtaney, Ravi; Brandt, Achi
2010-09-01
Multigrid methods can solve some classes of elliptic and parabolic equations to accuracy below the truncation error with a work-cost equivalent to a few residual calculations – so-called ‘‘textbook” multigrid efficiency. We investigate methods to solve the system of equations that arise in time dependent magnetohydrodynamics (MHD) simulations with textbook multigrid efficiency. We apply multigrid techniques such as geometric interpolation, full approximate storage, Gauss–Seidel smoothers, and defect correction for fully implicit, nonlinear, second-order finite volume discretizations of MHD. We apply these methods to a standard resistive MHD benchmark problem, the GEM reconnection problem, and add a strong magnetic guide field,more » which is a critical characteristic of magnetically confined fusion plasmas. We show that our multigrid methods can achieve near textbook efficiency on fully implicit resistive MHD simulations.« less
Toward textbook multigrid efficiency for fully implicit resistive magnetohydrodynamics
Adams, Mark F.; Samtaney, Ravi; Brandt, Achi
2010-09-01
Multigrid methods can solve some classes of elliptic and parabolic equations to accuracy below the truncation error with a work-cost equivalent to a few residual calculations – so-called ‘‘textbook” multigrid efficiency. We investigate methods to solve the system of equations that arise in time dependent magnetohydrodynamics (MHD) simulations with textbook multigrid efficiency. We apply multigrid techniques such as geometric interpolation, full approximate storage, Gauss–Seidel smoothers, and defect correction for fully implicit, nonlinear, second-order finite volume discretizations of MHD. We apply these methods to a standard resistive MHD benchmark problem, the GEM reconnection problem, and add a strong magnetic guide field, which is a critical characteristic of magnetically confined fusion plasmas. We show that our multigrid methods can achieve near textbook efficiency on fully implicit resistive MHD simulations.
Toward textbook multigrid efficiency for fully implicit resistive magnetohydrodynamics
Adams, Mark F.; Samtaney, Ravi; Brandt, Achi
2010-09-01
Multigrid methods can solve some classes of elliptic and parabolic equations to accuracy below the truncation error with a work-cost equivalent to a few residual calculations - so-called 'textbook' multigrid efficiency. We investigate methods to solve the system of equations that arise in time dependent magnetohydrodynamics (MHD) simulations with textbook multigrid efficiency. We apply multigrid techniques such as geometric interpolation, full approximate storage, Gauss-Seidel smoothers, and defect correction for fully implicit, nonlinear, second-order finite volume discretizations of MHD. We apply these methods to a standard resistive MHD benchmark problem, the GEM reconnection problem, and add a strong magnetic guide field, which is a critical characteristic of magnetically confined fusion plasmas. We show that our multigrid methods can achieve near textbook efficiency on fully implicit resistive MHD simulations.
NASA Astrophysics Data System (ADS)
Li, Gang; Zhang, Lili; Hao, Tianyao
2016-02-01
An effective solver for the large complex system of linear equations is critical for improving the accuracy of numerical solutions in three-dimensional (3D) magnetotelluric (MT) modeling using the staggered finite-difference (SFD) method. In electromagnetic modeling, the formed system of linear equations is commonly solved using preconditioned iterative relaxation methods. We present 3D MT modeling using the SFD method, based on former work. The multigrid solver and three solvers preconditioned by incomplete Cholesky decomposition—the minimum residual method, the generalized product bi-conjugate gradient method and the bi-conjugate gradient stabilized method—are used to solve the formed system of linear equations. Divergence correction for the magnetic field is applied. We also present a comparison of the stability and convergence of these iterative solvers if divergence correction is used. Model tests show that divergence correction improves the convergence of iterative solvers and the accuracy of numerical results. Divergence correction can also decrease the number of iterations for fast convergence without changing the stability of linear solvers. For consideration of the computation time and memory requirements, the multigrid solver combined with divergence correction is preferred for 3D MT field simulation.
Multigrid method applied to the solution of an elliptic, generalized eigenvalue problem
Alchalabi, R.M.; Turinsky, P.J.
1996-12-31
The work presented in this paper is concerned with the development of an efficient MG algorithm for the solution of an elliptic, generalized eigenvalue problem. The application is specifically applied to the multigroup neutron diffusion equation which is discretized by utilizing the Nodal Expansion Method (NEM). The underlying relaxation method is the Power Method, also known as the (Outer-Inner Method). The inner iterations are completed using Multi-color Line SOR, and the outer iterations are accelerated using Chebyshev Semi-iterative Method. Furthermore, the MG algorithm utilizes the consistent homogenization concept to construct the restriction operator, and a form function as a prolongation operator. The MG algorithm was integrated into the reactor neutronic analysis code NESTLE, and numerical results were obtained from solving production type benchmark problems.
NASA Astrophysics Data System (ADS)
Cools, S.; Vanroose, W.
2016-03-01
This paper improves the convergence and robustness of a multigrid-based solver for the cross sections of the driven Schrödinger equation. Adding a Coupled Channel Correction Step (CCCS) after each multigrid (MG) V-cycle efficiently removes the errors that remain after the V-cycle sweep. The combined iterative solution scheme (MG-CCCS) is shown to feature significantly improved convergence rates over the classical MG method at energies where bound states dominate the solution, resulting in a fast and scalable solution method for the complex-valued Schrödinger break-up problem for any energy regime. The proposed solver displays optimal scaling; a solution is found in a time that is linear in the number of unknowns. The method is validated on a 2D Temkin-Poet model problem, and convergence results both as a solver and preconditioner are provided to support the O (N) scalability of the method. This paper extends the applicability of the complex contour approach for far field map computation (Cools et al. (2014) [10]).
MueLu Multigrid Preconditioning Package
2012-09-11
MueLu is intended for the research and development of multigrid algorithms used in the solution of sparse linear systems arising from systems of partial differential equations. The software provides multigrid source code, test programs, and short example programs to demonstrate the various interfaces for creating, accessing, and applying the solvers. MueLu currently provides an implementation of smoothed aggregation algebraic multigrid method and interfaces to many commonly used smoothers. However, the software is intended to be extensible, and new methods can be incorporated easily. MueLu also allows for advanced usage, such as combining multiple methods and segregated solves. The library supports point and block access to matrix data. All algorithms and methods in MueLu have been or will be published in the open scientific literature.
MueLu Multigrid Preconditioning Package
Energy Science and Technology Software Center (ESTSC)
2012-09-11
MueLu is intended for the research and development of multigrid algorithms used in the solution of sparse linear systems arising from systems of partial differential equations. The software provides multigrid source code, test programs, and short example programs to demonstrate the various interfaces for creating, accessing, and applying the solvers. MueLu currently provides an implementation of smoothed aggregation algebraic multigrid method and interfaces to many commonly used smoothers. However, the software is intended to bemore » extensible, and new methods can be incorporated easily. MueLu also allows for advanced usage, such as combining multiple methods and segregated solves. The library supports point and block access to matrix data. All algorithms and methods in MueLu have been or will be published in the open scientific literature.« less
Augustin, Christoph M.; Neic, Aurel; Liebmann, Manfred; Prassl, Anton J.; Niederer, Steven A.; Haase, Gundolf; Plank, Gernot
2016-01-01
Electromechanical (EM) models of the heart have been used successfully to study fundamental mechanisms underlying a heart beat in health and disease. However, in all modeling studies reported so far numerous simplifications were made in terms of representing biophysical details of cellular function and its heterogeneity, gross anatomy and tissue microstructure, as well as the bidirectional coupling between electrophysiology (EP) and tissue distension. One limiting factor is the employed spatial discretization methods which are not sufficiently flexible to accommodate complex geometries or resolve heterogeneities, but, even more importantly, the limited efficiency of the prevailing solver techniques which are not sufficiently scalable to deal with the incurring increase in degrees of freedom (DOF) when modeling cardiac electromechanics at high spatio-temporal resolution. This study reports on the development of a novel methodology for solving the nonlinear equation of finite elasticity using human whole organ models of cardiac electromechanics, discretized at a high para-cellular resolution. Three patient-specific, anatomically accurate, whole heart EM models were reconstructed from magnetic resonance (MR) scans at resolutions of 220 μm, 440 μm and 880 μm, yielding meshes of approximately 184.6, 24.4 and 3.7 million tetrahedral elements and 95.9, 13.2 and 2.1 million displacement DOF, respectively. The same mesh was used for discretizing the governing equations of both electrophysiology (EP) and nonlinear elasticity. A novel algebraic multigrid (AMG) preconditioner for an iterative Krylov solver was developed to deal with the resulting computational load. The AMG preconditioner was designed under the primary objective of achieving favorable strong scaling characteristics for both setup and solution runtimes, as this is key for exploiting current high performance computing hardware. Benchmark results using the 220 μm, 440 μm and 880 μm meshes demonstrate
NASA Astrophysics Data System (ADS)
Augustin, Christoph M.; Neic, Aurel; Liebmann, Manfred; Prassl, Anton J.; Niederer, Steven A.; Haase, Gundolf; Plank, Gernot
2016-01-01
Electromechanical (EM) models of the heart have been used successfully to study fundamental mechanisms underlying a heart beat in health and disease. However, in all modeling studies reported so far numerous simplifications were made in terms of representing biophysical details of cellular function and its heterogeneity, gross anatomy and tissue microstructure, as well as the bidirectional coupling between electrophysiology (EP) and tissue distension. One limiting factor is the employed spatial discretization methods which are not sufficiently flexible to accommodate complex geometries or resolve heterogeneities, but, even more importantly, the limited efficiency of the prevailing solver techniques which is not sufficiently scalable to deal with the incurring increase in degrees of freedom (DOF) when modeling cardiac electromechanics at high spatio-temporal resolution. This study reports on the development of a novel methodology for solving the nonlinear equation of finite elasticity using human whole organ models of cardiac electromechanics, discretized at a high para-cellular resolution. Three patient-specific, anatomically accurate, whole heart EM models were reconstructed from magnetic resonance (MR) scans at resolutions of 220 μm, 440 μm and 880 μm, yielding meshes of approximately 184.6, 24.4 and 3.7 million tetrahedral elements and 95.9, 13.2 and 2.1 million displacement DOF, respectively. The same mesh was used for discretizing the governing equations of both electrophysiology (EP) and nonlinear elasticity. A novel algebraic multigrid (AMG) preconditioner for an iterative Krylov solver was developed to deal with the resulting computational load. The AMG preconditioner was designed under the primary objective of achieving favorable strong scaling characteristics for both setup and solution runtimes, as this is key for exploiting current high performance computing hardware. Benchmark results using the 220 μm, 440 μm and 880 μm meshes demonstrate
Selective oil agglomeration of lignite
Halime Abakay Temel; Volkan Bozkurt; Arun Kumar Majumder
2009-01-15
In this study, desulfurization and deashing of Adiyaman-Glbai lignite by the agglomeration method were studied. For this purpose, three groups of agglomeration experiments were made. The effects of solid concentration, bridging liquid type and dosage, pH, and screen size on the agglomeration after desliming were investigated in the first group of experiments. The effects of lake water and sea water (the Mediterranean Sea water, the Aegean Sea water, and the Black Sea water) on the agglomeration were investigated in the second group of experiments. The effects of different salts (NaCl, MgCl{sub 2}, and FeCl{sub 3}) on the agglomeration were investigated in the third group of experiments. Agglomeration results showed that the usage of sea waters and soda lake water in the agglomeration medium had a positive effect on the reduction of total sulfur content of agglomerates. In addition, the usage of NaCl, MgCl{sub 2}, and FeCl{sub 3} in the agglomeration medium had a positive effect on the ash content reduction of the agglomerates. 27 refs., 10 figs., 6 tabs.
3D magnetospheric parallel hybrid multi-grid method applied to planet-plasma interactions
NASA Astrophysics Data System (ADS)
Leclercq, L.; Modolo, R.; Leblanc, F.; Hess, S.; Mancini, M.
2016-03-01
We present a new method to exploit multiple refinement levels within a 3D parallel hybrid model, developed to study planet-plasma interactions. This model is based on the hybrid formalism: ions are kinetically treated whereas electrons are considered as a inertia-less fluid. Generally, ions are represented by numerical particles whose size equals the volume of the cells. Particles that leave a coarse grid subsequently entering a refined region are split into particles whose volume corresponds to the volume of the refined cells. The number of refined particles created from a coarse particle depends on the grid refinement rate. In order to conserve velocity distribution functions and to avoid calculations of average velocities, particles are not coalesced. Moreover, to ensure the constancy of particles' shape function sizes, the hybrid method is adapted to allow refined particles to move within a coarse region. Another innovation of this approach is the method developed to compute grid moments at interfaces between two refinement levels. Indeed, the hybrid method is adapted to accurately account for the special grid structure at the interfaces, avoiding any overlapping grid considerations. Some fundamental test runs were performed to validate our approach (e.g. quiet plasma flow, Alfven wave propagation). Lastly, we also show a planetary application of the model, simulating the interaction between Jupiter's moon Ganymede and the Jovian plasma.
New Multigrid Solver Advances in TOPS
Falgout, R D; Brannick, J; Brezina, M; Manteuffel, T; McCormick, S
2005-06-27
In this paper, we highlight new multigrid solver advances in the Terascale Optimal PDE Simulations (TOPS) project in the Scientific Discovery Through Advanced Computing (SciDAC) program. We discuss two new algebraic multigrid (AMG) developments in TOPS: the adaptive smoothed aggregation method ({alpha}SA) and a coarse-grid selection algorithm based on compatible relaxation (CR). The {alpha}SA method is showing promising results in initial studies for Quantum Chromodynamics (QCD) applications. The CR method has the potential to greatly improve the applicability of AMG.
Some multigrid algorithms for SIMD machines
Dendy, J.E. Jr.
1996-12-31
Previously a semicoarsening multigrid algorithm suitable for use on SIMD architectures was investigated. Through the use of new software tools, the performance of this algorithm has been considerably improved. The method has also been extended to three space dimensions. The method performs well for strongly anisotropic problems and for problems with coefficients jumping by orders of magnitude across internal interfaces. The parallel efficiency of this method is analyzed, and its actual performance on the CM-5 is compared with its performance on the CRAY-YMP. A standard coarsening multigrid algorithm is also considered, and we compare its performance on these two platforms as well.
Application of multigrid methods to the solution of liquid crystal equations on a SIMD computer
NASA Technical Reports Server (NTRS)
Farrell, Paul A.; Ruttan, Arden; Zeller, Reinhardt R.
1993-01-01
We will describe a finite difference code for computing the equilibrium configurations of the order-parameter tensor field for nematic liquid crystals in rectangular regions by minimization of the Landau-de Gennes Free Energy functional. The implementation of the free energy functional described here includes magnetic fields, quadratic gradient terms, and scalar bulk terms through the fourth order. Boundary conditions include the effects of strong surface anchoring. The target architectures for our implementation are SIMD machines, with interconnection networks which can be configured as 2 or 3 dimensional grids, such as the Wavetracer DTC. We also discuss the relative efficiency of a number of iterative methods for the solution of the linear systems arising from this discretization on such architectures.
Multigrid calculation of three-dimensional turbomachinery flows
NASA Technical Reports Server (NTRS)
Caughey, David A.
1989-01-01
Research was performed in the general area of computational aerodynamics, with particular emphasis on the development of efficient techniques for the solution of the Euler and Navier-Stokes equations for transonic flows through the complex blade passages associated with turbomachines. In particular, multigrid methods were developed, using both explicit and implicit time-stepping schemes as smoothing algorithms. The specific accomplishments of the research have included: (1) the development of an explicit multigrid method to solve the Euler equations for three-dimensional turbomachinery flows based upon the multigrid implementation of Jameson's explicit Runge-Kutta scheme (Jameson 1983); (2) the development of an implicit multigrid scheme for the three-dimensional Euler equations based upon lower-upper factorization; (3) the development of a multigrid scheme using a diagonalized alternating direction implicit (ADI) algorithm; (4) the extension of the diagonalized ADI multigrid method to solve the Euler equations of inviscid flow for three-dimensional turbomachinery flows; and also (5) the extension of the diagonalized ADI multigrid scheme to solve the Reynolds-averaged Navier-Stokes equations for two-dimensional turbomachinery flows.
Spectral element multigrid. Part 2: Theoretical justification
NASA Technical Reports Server (NTRS)
Maday, Yvon; Munoz, Rafael
1988-01-01
A multigrid algorithm is analyzed which is used for solving iteratively the algebraic system resulting from tha approximation of a second order problem by spectral or spectral element methods. The analysis, performed here in the one dimensional case, justifies the good smoothing properties of the Jacobi preconditioner that was presented in Part 1 of this paper.
Unsteady Analysis of Separated Aerodynamic Flows Using an Unstructured Multigrid Algorithm
NASA Technical Reports Server (NTRS)
Pelaez, Juan; Mavriplis, Dimitri J.; Kandil, Osama
2001-01-01
An implicit method for the computation of unsteady flows on unstructured grids is presented. The resulting nonlinear system of equations is solved at each time step using an agglomeration multigrid procedure. The method allows for arbitrarily large time steps and is efficient in terms of computational effort and storage. Validation of the code using a one-equation turbulence model is performed for the well-known case of flow over a cylinder. A Detached Eddy Simulation model is also implemented and its performance compared to the one equation Spalart-Allmaras Reynolds Averaged Navier-Stokes (RANS) turbulence model. Validation cases using DES and RANS include flow over a sphere and flow over a NACA 0012 wing including massive stall regimes. The project was driven by the ultimate goal of computing separated flows of aerodynamic interest, such as massive stall or flows over complex non-streamlined geometries.
Conduct of the International Multigrid Conference
NASA Technical Reports Server (NTRS)
Mccormick, S.
1984-01-01
The 1983 International Multigrid Conference was held at Colorado's Copper Mountain Ski Resort, April 5-8. It was organized jointly by the Institute for Computational Studies at Colorado State University, U.S.A., and the Gasellschaft fur Mathematik und Datenverarbeitung Bonn, F.R. Germany, and was sponsored by the Air Force Office of Sponsored Research and National Aeronautics and Space Administration Headquarters. The conference was attended by 80 scientists, divided by institution almost equally into private industry, research laboratories, and academia. Fifteen attendees came from countries other than the U.S.A. In addition to the fruitful discussions, the most significant factor of the conference was of course the lectures. The lecturers include most of the leaders in the field of multigrid research. The program offered a nice integrated blend of theory, numerical studies, basic research, and applications. Some of the new areas of research that have surfaced since the Koln-Porz conference include: the algebraic multigrid approach; multigrid treatment of Euler equations for inviscid fluid flow problems; 3-D problems; and the application of MG methods on vector and parallel computers.
Matrix-dependent multigrid-homogenization for diffusion problems
Knapek, S.
1996-12-31
We present a method to approximately determine the effective diffusion coefficient on the coarse scale level of problems with strongly varying or discontinuous diffusion coefficients. It is based on techniques used also in multigrid, like Dendy`s matrix-dependent prolongations and the construction of coarse grid operators by means of the Galerkin approximation. In numerical experiments, we compare our multigrid-homogenization method with homogenization, renormalization and averaging approaches.
On the connection between multigrid and cyclic reduction
NASA Technical Reports Server (NTRS)
Merriam, M. L.
1984-01-01
A technique is shown whereby it is possible to relate a particular multigrid process to cyclic reduction using purely mathematical arguments. This technique suggest methods for solving Poisson's equation in 1-, 2-, or 3-dimensions with Dirichlet or Neumann boundary conditions. In one dimension the method is exact and, in fact, reduces to cyclic reduction. This provides a valuable reference point for understanding multigrid techniques. The particular multigrid process analyzed is referred to here as Approximate Cyclic Reduction (ACR) and is one of a class known as Multigrid Reduction methods in the literature. It involves one approximation with a known error term. It is possible to relate the error term in this approximation with certain eigenvector components of the error. These are sharply reduced in amplitude by classical relaxation techniques. The approximation can thus be made a very good one.
Multigrid techniques for the numerical solution of the diffusion equation
NASA Technical Reports Server (NTRS)
Phillips, R. E.; Schmidt, F. W.
1984-01-01
An accurate numerical solution of diffusion problems containing large local gradients can be obtained with a significant reduction in computational time by using a multigrid computational scheme. The spatial domain is covered with sets of uniform square grids of different sizes. The finer grid patterns overlap the coarse grid patterns. The finite-difference expressions for each grid pattern are solved independently by iterative techniques. Two interpolation methods were used to establish the values of the potential function on the fine grid boundaries with information obtained from the coarse grid solution. The accuracy and computational requirements for solving a test problem by a simple multigrid and a multilevel-multigrid method were compared. The multilevel-multigrid method combined with a Taylor series interpolation scheme was found to be best.
2013-05-06
AMG2013 is a parallel algebraic multigrid solver for linear systems arising from problems on unstructured grids. It has been derived directly from the Boomer AMG solver in the hypre library, a large linear solvers library that is being developed in the Center for Applied Scientific Computing (CASC) at LLNL. The driver provided in the benchmark can build various test problems. The default problem is a Laplace type problem on an unstructured domain with various jumps and an anisotropy in one part.
Applications of multigrid software in the atmospheric sciences
NASA Technical Reports Server (NTRS)
Adams, J.; Garcia, R.; Gross, B.; Hack, J.; Haidvogel, D.; Pizzo, V.
1992-01-01
Elliptic partial differential equations from different areas in the atmospheric sciences are efficiently and easily solved utilizing the multigrid software package named MUDPACK. It is demonstrated that the multigrid method is more efficient than other commonly employed techniques, such as Gaussian elimination and fixed-grid relaxation. The efficiency relative to other techniques, both in terms of storage requirement and computational time, increases quickly with grid size.
Element Agglomeration Algebraic Multilevel Monte-Carlo Library
2015-02-19
ElagMC is a parallel C++ library for Multilevel Monte Carlo simulations with algebraically constructed coarse spaces. ElagMC enables Multilevel variance reduction techniques in the context of general unstructured meshes by using the specialized element-based agglomeration techniques implemented in ELAG (the Element-Agglomeration Algebraic Multigrid and Upscaling Library developed by U. Villa and P. Vassilevski and currently under review for public release). The ElabMC library can support different type of deterministic problems, including mixed finite element discretizations of subsurface flow problems.
Element Agglomeration Algebraic Multilevel Monte-Carlo Library
Energy Science and Technology Software Center (ESTSC)
2015-02-19
ElagMC is a parallel C++ library for Multilevel Monte Carlo simulations with algebraically constructed coarse spaces. ElagMC enables Multilevel variance reduction techniques in the context of general unstructured meshes by using the specialized element-based agglomeration techniques implemented in ELAG (the Element-Agglomeration Algebraic Multigrid and Upscaling Library developed by U. Villa and P. Vassilevski and currently under review for public release). The ElabMC library can support different type of deterministic problems, including mixed finite element discretizationsmore » of subsurface flow problems.« less
Updated users' guide for TAWFIVE with multigrid
NASA Technical Reports Server (NTRS)
Melson, N. Duane; Streett, Craig L.
1989-01-01
A program for the Transonic Analysis of a Wing and Fuselage with Interacted Viscous Effects (TAWFIVE) was improved by the incorporation of multigrid and a method to specify lift coefficient rather than angle-of-attack. A finite volume full potential multigrid method is used to model the outer inviscid flow field. First order viscous effects are modeled by a 3-D integral boundary layer method. Both turbulent and laminar boundary layers are treated. Wake thickness effects are modeled using a 2-D strip method. A brief discussion of the engineering aspects of the program is given. The input, output, and use of the program are covered in detail. Sample results are given showing the effects of boundary layer corrections and the capability of the lift specification method.
Progress with multigrid schemes for hypersonic flow problems
NASA Technical Reports Server (NTRS)
Radespiel, R.; Swanson, R. C.
1991-01-01
Several multigrid schemes are considered for the numerical computation of viscous hypersonic flows. For each scheme, the basic solution algorithm uses upwind spatial discretization with explicit multistage time stepping. Two level versions of the various multigrid algorithms are applied to the two dimensional advection equation, and Fourier analysis is used to determine their damping properties. The capabilities of the multigrid methods are assessed by solving three different hypersonic flow problems. Some new multigrid schemes based on semicoarsening strategies are shown to be quite effective in relieving the stiffness caused by the high aspect ratio cells required to resolve high Reynolds number flows. These schemes exhibit good convergence rates for Reynolds numbers up to 200 x 10(exp 6) and Mach numbers up to 25.
Progress with multigrid schemes for hypersonic flow problems
Radespiel, R.; Swanson, R.C.
1995-01-01
Several multigrid schemes are considered for the numerical computation of viscous hypersonic flows. For each scheme, the basic solution algorithm employs upwind spatial discretization with explicit multistage time stepping. Two-level versions of the various multigrid algorithms are applied to the two-dimensional advection equation, and Fourier analysis is used to determine their damping properties. The capabilities of the multigrid methods are assessed by solving three different hypersonic flow problems. Some new multigrid schemes based on semicoarsening strategies are shown to be quite effective in relieving the stiffness caused by the high-aspect-ratio cells required to resolve high Reynolds number flows. These schemes exhibit good convergence rates for Reynolds numbers up to 200 X 10{sup 6} and Mach numbers up to 25. 32 refs., 31 figs., 1 tab.
Coal Cleaning by Gas Agglomeration
Meiyu Shen; Royce Abbott; T. D. Wheelock
1998-03-01
The gas agglomeration method of coal cleaning was demonstrated with laboratory scale mixing equipment which made it possible to generate microscopic gas bubbles in aqueous suspensions of coal particles. A small amount of i-octane was introduced to enhance the hydrophobicity of the coal. Between 1.0 and 2.5 v/w% i-octane was sufficient based on coal weight. Coal agglomerates or aggregates were produced which were bound together by small gas bubbles.
Energy Science and Technology Software Center (ESTSC)
2013-05-06
AMG2013 is a parallel algebraic multigrid solver for linear systems arising from problems on unstructured grids. It has been derived directly from the Boomer AMG solver in the hypre library, a large linear solvers library that is being developed in the Center for Applied Scientific Computing (CASC) at LLNL. The driver provided in the benchmark can build various test problems. The default problem is a Laplace type problem on an unstructured domain with various jumpsmore » and an anisotropy in one part.« less
NASA Technical Reports Server (NTRS)
Jentink, Thomas Neil; Usab, William J., Jr.
1990-01-01
An explicit, Multigrid algorithm was written to solve the Euler and Navier-Stokes equations with special consideration given to the coarse mesh boundary conditions. These are formulated in a manner consistent with the interior solution, utilizing forcing terms to prevent coarse-mesh truncation error from affecting the fine-mesh solution. A 4-Stage Hybrid Runge-Kutta Scheme is used to advance the solution in time, and Multigrid convergence is further enhanced by using local time-stepping and implicit residual smoothing. Details of the algorithm are presented along with a description of Jameson's standard Multigrid method and a new approach to formulating the Multigrid equations.
NASA Technical Reports Server (NTRS)
Mineck, Raymond E.; Thomas, James L.; Biedron, Robert T.; Diskin, Boris
2005-01-01
FMG3D (full multigrid 3 dimensions) is a pilot computer program that solves equations of fluid flow using a finite difference representation on a structured grid. Infrastructure exists for three dimensions but the current implementation treats only two dimensions. Written in Fortran 90, FMG3D takes advantage of the recursive subroutine feature, dynamic memory allocation, and structured-programming constructs of that language. FMG3D supports multi-block grids with three types of block-to-block interfaces: periodic, C-zero, and C-infinity. For all three types, grid points must match at interfaces. For periodic and C-infinity types, derivatives of grid metrics must be continuous at interfaces. The available equation sets are as follows: scalar elliptic equations, scalar convection equations, and the pressure-Poisson formulation of the Navier-Stokes equations for an incompressible fluid. All the equation sets are implemented with nonzero forcing functions to enable the use of user-specified solutions to assist in verification and validation. The equations are solved with a full multigrid scheme using a full approximation scheme to converge the solution on each succeeding grid level. Restriction to the next coarser mesh uses direct injection for variables and full weighting for residual quantities; prolongation of the coarse grid correction from the coarse mesh to the fine mesh uses bilinear interpolation; and prolongation of the coarse grid solution uses bicubic interpolation.
Choi, Young Joon; Jorshari, Razzi Movassaghi; Djilali, Ned
2015-03-10
Direct numerical simulations of the flow-nanoparticle interaction in a colloidal suspension are presented using an extended finite element method (XFEM) in which the dynamics of the nanoparticles is solved in a fully-coupled manner with the flow. The method is capable of accurately describing solid-fluid interfaces without the need of boundary-fitted meshes to investigate the dynamics of particles in complex flows. In order to accurately compute the high interparticle shear stresses and pressures while minimizing computing costs, an adaptive meshing technique is incorporated with the fluid-structure interaction algorithm. The particle-particle interaction at the microscopic level is modeled using the Lennard-Jones (LJ) potential and the corresponding potential parameters are determined by a scaling procedure. The study is relevant to the preparation of inks used in the fabrication of catalyst layers for fuel cells. In this paper, we are particularly interested in investigating agglomeration of the nanoparticles under external shear flow in a sliding bi-periodic Lees-Edwards frame. The results indicate that the external shear has a crucial impact on the structure formation of colloidal particles in a suspension.
Mechanisms for selective agglomeration of coals
Wheelock, T.D.; Drzymala, J.; Allen, R.W.; Hu, Y.-C.; Tyson, D.; Xiaoping, Qiu; Lessa, A.
1989-05-01
Work continued on the basic mechanisms which underlie various processes for beneficiating aqueous suspensions of coal by selective agglomeration with oil. A new method was demonstrated for characterizing the agglomerability of coal suspensions. This method utilizes a photometric dispersion analyzer to monitor changes in the turbidity of a particle suspension as increasing amounts of oil are added to the suspension in a batch agglomeration test. Agglomeration of the particles leads to a marked decrease in the turbidity of the suspension. Another experimental technique was also demonstrated for characterizing oil agglomeration. This technique involves measuring the rate of growth of agglomerates in a continuous flow system operating under stead-state conditions. The data are analyzed by means of a population balance. The results of a preliminary set of experiments in which Indiana V seam coal was agglomerated with tetralin seemed to fit a particular growth model very well. Equipment was also constructed for studying the kinetics of agglomeration in a batch process. While earlier work showed that quebracho (a commercially available dispersant) is a strong agglomeration depressant for pyrite, recent experiments with mixtures of Upper Freeport coal and mineral pyrite showed that quebracho does not appear to be sufficiently selective. Further consideration was given to the separation of mixtures of coal and pyrite agglomeration with heptane. 2 refs., 17 figs., 1 tab.
Multigrid approaches to non-linear diffusion problems on unstructured meshes
NASA Technical Reports Server (NTRS)
Mavriplis, Dimitri J.; Bushnell, Dennis M. (Technical Monitor)
2001-01-01
The efficiency of three multigrid methods for solving highly non-linear diffusion problems on two-dimensional unstructured meshes is examined. The three multigrid methods differ mainly in the manner in which the nonlinearities of the governing equations are handled. These comprise a non-linear full approximation storage (FAS) multigrid method which is used to solve the non-linear equations directly, a linear multigrid method which is used to solve the linear system arising from a Newton linearization of the non-linear system, and a hybrid scheme which is based on a non-linear FAS multigrid scheme, but employs a linear solver on each level as a smoother. Results indicate that all methods are equally effective at converging the non-linear residual in a given number of grid sweeps, but that the linear solver is more efficient in cpu time due to the lower cost of linear versus non-linear grid sweeps.
Spectral Element Agglomerate AMGe
Chartier, T; Falgout, R; Henson, V E; Jones, J E; Vassilevski, P S; Manteuffel, T A; McCormick, S F; Ruge, J W
2005-05-20
The purpose of this note is to describe an algorithm resulting from the uniting of two ideas introduced and applied elsewhere. For many problems, AMG has always been difficult due to complexities whose natures are difficult to discern from the entries of matrix A alone. Element-based interpolation has been shown to be an effective method for some of these problems, but it requires access to the element matrices on all levels. One way to obtain these has been to perform element agglomeration to form coarse elements, but in complicated situations defining the coarse degrees of freedom (dofs) is not easy. The spectral approach to coarse dof selection is very attractive due to its elegance and simplicity. The algorithm presented here combines the robustness of element interpolation, the ease of coarsening by element agglomeration, and the simplicity of defining coarse dofs through the spectral approach. As demonstrated in the numerical results, the method does yield a reasonable solver for the problems described. It can, however, be an expensive method due to the number and cost of the local, small dense linear algebra problems; making it a generally competitive method remains an area for further research.
NASA Astrophysics Data System (ADS)
Ai, Xiaolan
Surface topography has long been recognized to have a significant influence on lubricated contacts. This thesis deals with the subject of elastohydrodynamic lubricated line and point contacts with rough surfaces (rough EHL contacts). As an introduction to this subject, a brief historical review is provided, followed by the mathematical descriptions of the rough EHL contacts for both Newtonian and non-Newtonian lubricants. On the basis of the merits of presently used numerical algorithms, two numerical methods, the semi-system method and the multigrid method, were adopted for developing fast numerical solvers to simulate the rough EHL contact problems. For line contact geometry, numerical simulations were performed for both steady and transient conditions. The surface irregularities examined range from single transverse bump or groove to random surface roughness. Based on the simulation results, an empirical formula for pressure fluctuations was regressed, and a fast pressure calculation model for EHL contact with arbitrary surface profiles was developed. As an extension to the 2-D surface irregularities, the problems of 3-D surface irregularities in line contact geometry were also examined. Parallel simulations were performed for point contact geometry. The types of surface irregularities studied included single asperity, dent, bump, multiple asperities, waviness, and random surface roughness. The orientation of the surface irregularities varies from transverse to striated to longitudinal. The simulation results reveal the fundamental fact that under heavily loaded conditions the domination of pressure flow yields to the unidirectional shear flow in the EHL conjunction. Lubricant passes though the EHL conjunction at approximately the rolling speed. For sliding contact with moving surface roughness, the rolling speed transport behavior leads to an induced transient image. This transient phenomena will be fully developed under steady-state conditions; and, as a
Multigrid solution of the convection-diffusion equation with high-Reynolds number
Zhang, Jun
1996-12-31
A fourth-order compact finite difference scheme is employed with the multigrid technique to solve the variable coefficient convection-diffusion equation with high-Reynolds number. Scaled inter-grid transfer operators and potential on vectorization and parallelization are discussed. The high-order multigrid method is unconditionally stable and produces solution of 4th-order accuracy. Numerical experiments are included.
COAL CLEANING BY GAS AGGLOMERATION
T.D. Wheelock
1999-03-01
The technical feasibility of a gas agglomeration method for cleaning coal was demonstrated by means of bench-scale tests conducted with a mixing system which enabled the treatment of ultra-fine coal particles with a colloidal suspension of microscopic gas bubbles in water. A suitable suspension of microbubbles was prepared by first saturating water with air or carbon dioxide under pressure then reducing the pressure to release the dissolved gas. The formation of microbubbles was facilitated by agitation and a small amount of i-octane. When the suspension of microbubbles and coal particles was mixed, agglomeration was rapid and small spherical agglomerates were produced. Since the agglomerates floated, they were separated from the nonfloating tailings in a settling chamber. By employing this process in numerous agglomeration tests of moderately hydrophobic coals with 26 wt.% ash, it was shown that the ash content would be reduced to 6--7 wt.% while achieving a coal recovery of 75 to 85% on a dry, ash-free basis. This was accomplished by employing a solids concentration of 3 to 5 w/w%, an air saturation pressure of 136 to 205 kPa (5 to 15 psig), and an i-octane concentration of 1.0 v/w% based on the weight of coal.
Towards Optimal Multigrid Efficiency for the Navier-Stokes Equations
NASA Technical Reports Server (NTRS)
Swanson, R. C.
2001-01-01
A fast multigrid solver for the steady incompressible Navier-Stokes equations is presented. Unlike time-marching schemes, this approach uses relaxation of the steady equations. Application of this method results in a discretization that correctly distinguishes between the advection and elliptic parts of the operator, allowing efficient smoothers to be constructed. Numerical solutions are shown for flow over a flat plate and a Karman-Trefftz airfoil. Using collective Gauss-Seidel line relaxation in both the vertical and horizontal directions, multigrid convergence behavior approaching that of O(N) methods is achieved. The computational efficiency of the numerical scheme is compared with that of a Runge-Kutta based multigrid method.
A multigrid fluid pressure solver handling separating solid boundary conditions.
Chentanez, Nuttapong; Müller-Fischer, Matthias
2012-08-01
We present a multigrid method for solving the linear complementarity problem (LCP) resulting from discretizing the Poisson equation subject to separating solid boundary conditions in an Eulerian liquid simulation’s pressure projection step. The method requires only a few small changes to a multigrid solver for linear systems. Our generalized solver is fast enough to handle 3D liquid simulations with separating boundary conditions in practical domain sizes. Previous methods could only handle relatively small 2D domains in reasonable time, because they used expensive quadratic programming (QP) solvers. We demonstrate our technique in several practical scenarios, including nonaxis-aligned containers and moving solids in which the omission of separating boundary conditions results in disturbing artifacts of liquid sticking to solids. Our measurements show, that the convergence rate of our LCP solver is close to that of a standard multigrid solver. PMID:22411885
Evaluation of a Multigrid Scheme for the Incompressible Navier-Stokes Equations
NASA Technical Reports Server (NTRS)
Swanson, R. C.
2004-01-01
A fast multigrid solver for the steady, incompressible Navier-Stokes equations is presented. The multigrid solver is based upon a factorizable discrete scheme for the velocity-pressure form of the Navier-Stokes equations. This scheme correctly distinguishes between the advection-diffusion and elliptic parts of the operator, allowing efficient smoothers to be constructed. To evaluate the multigrid algorithm, solutions are computed for flow over a flat plate, parabola, and a Karman-Trefftz airfoil. Both nonlifting and lifting airfoil flows are considered, with a Reynolds number range of 200 to 800. Convergence and accuracy of the algorithm are discussed. Using Gauss-Seidel line relaxation in alternating directions, multigrid convergence behavior approaching that of O(N) methods is achieved. The computational efficiency of the numerical scheme is compared with that of Runge-Kutta and implicit upwind based multigrid methods.
Fast Multigrid Techniques in Total Variation-Based Image Reconstruction
NASA Technical Reports Server (NTRS)
Oman, Mary Ellen
1996-01-01
Existing multigrid techniques are used to effect an efficient method for reconstructing an image from noisy, blurred data. Total Variation minimization yields a nonlinear integro-differential equation which, when discretized using cell-centered finite differences, yields a full matrix equation. A fixed point iteration is applied with the intermediate matrix equations solved via a preconditioned conjugate gradient method which utilizes multi-level quadrature (due to Brandt and Lubrecht) to apply the integral operator and a multigrid scheme (due to Ewing and Shen) to invert the differential operator. With effective preconditioning, the method presented seems to require Omicron(n) operations. Numerical results are given for a two-dimensional example.
Some multigrid algorithms for elliptic problems on data parallel machines
Bandy, V.A.; Dendy, J.E. Jr.; Spangenberg, W.H.
1998-01-01
Previously a semicoarsening multigrid algorithm suitable for use on data parallel architectures was investigated. Through the use of new software tools, the performance of this algorithm has been considerably improved. The method has also been extended to three space dimensions. The method performs well for strongly anisotropic problems and for problems with coefficients jumping by orders of magnitude across internal interfaces. The parallel efficiency of this method is analyzed, and its actual performance on the CM-5 is compared with its performance on the CRAY Y-MP and the Sparc-5. A standard coarsening multigrid algorithm is also considered, and they compare its performance on these three platforms as well.
Black box multigrid solver for definite and indefinite problems
Shapira, Yair
1997-02-01
A two-level analysis method for certain separable problems is introduced. It motivates the definition of improved versions of Black Box Multigrid for diffusion problems with discontinuous coefficients and indefinite Helmholtz equations. For anisotropic problems, it helps in choosing suitable implementations for frequency decomposition multigrid methods. For highly indefinite problems, it provides a way to choose in advance a suitable mesh size for the coarsest grid used. Numerical experiments confirm the analysis and show the advantage of the present methods for several examples.
A diagonally inverted LU implicit multigrid scheme
NASA Technical Reports Server (NTRS)
Yokota, Jeffrey W.; Caughey, David A.; Chima, Rodrick V.
1988-01-01
A new Diagonally Inverted LU Implicit scheme is developed within the framework of the multigrid method for the 3-D unsteady Euler equations. The matrix systems that are to be inverted in the LU scheme are treated by local diagonalizing transformations that decouple them into systems of scalar equations. Unlike the Diagonalized ADI method, the time accuracy of the LU scheme is not reduced since the diagonalization procedure does not destroy time conservation. Even more importantly, this diagonalization significantly reduces the computational effort required to solve the LU approximation and therefore transforms it into a more efficient method of numerically solving the 3-D Euler equations.
Möller, T; Korsatko, W
2000-06-01
Due to its low melting range approx. 53 degrees C optically pure ibuprofen can be regarded as problematic in a pharmaceutic-technological sense. With regard to the non-solvent shock agglomeration method this means that the process and product temperatures must strictly be kept in the range of 10 K above the melting point of the substance. Higher temperatures can induce degradation of S(+)ibuprofen. During storage under stress conditions (31 degrees C for a period of 18 months) ibuprofen shows extreme stability independent of its optical activity. Racemic ibuprofen is inert to the influence of light; in individual cases optically pure substance containing an increased level of impurities can show slight degradation tendencies. The thermal and photo stability of ibuprofen is independent of the preparation technology. For comparison, conventional, fluid bed granulated, briquetted and from organic solvents especially recrystallised and optically active substances were investigated besides the shock agglomerated substances. PMID:10907254
Multigrid and cyclic reduction applied to the Helmholtz equation
NASA Technical Reports Server (NTRS)
Brackenridge, Kenneth
1993-01-01
We consider the Helmholtz equation with a discontinuous complex parameter and inhomogeneous Dirichlet boundary conditions in a rectangular domain. A variant of the direct method of cyclic reduction (CR) is employed to facilitate the design of improved multigrid (MG) components, resulting in the method of CR-MG. We demonstrate the improved convergence properties of this method.
NASA Technical Reports Server (NTRS)
Cannizzaro, Frank E.; Ash, Robert L.
1992-01-01
A state-of-the-art computer code has been developed that incorporates a modified Runge-Kutta time integration scheme, upwind numerical techniques, multigrid acceleration, and multi-block capabilities (RUMM). A three-dimensional thin-layer formulation of the Navier-Stokes equations is employed. For turbulent flow cases, the Baldwin-Lomax algebraic turbulence model is used. Two different upwind techniques are available: van Leer's flux-vector splitting and Roe's flux-difference splitting. Full approximation multi-grid plus implicit residual and corrector smoothing were implemented to enhance the rate of convergence. Multi-block capabilities were developed to provide geometric flexibility. This feature allows the developed computer code to accommodate any grid topology or grid configuration with multiple topologies. The results shown in this dissertation were chosen to validate the computer code and display its geometric flexibility, which is provided by the multi-block structure.
Textbook Multigrid Efficiency for the Steady Euler Equations
NASA Technical Reports Server (NTRS)
Roberts, Thomas W.; Sidilkover, David; Swanson, R. C.
2004-01-01
A fast multigrid solver for the steady incompressible Euler equations is presented. Unlike time-marching schemes, this approach uses relaxation of the steady equations. Application of this method results in a discretization that correctly distinguishes between the advection and elliptic parts of the operator, allowing efficient smoothers to be constructed. Solvers for both unstructured triangular grids and structured quadrilateral grids have been written. Computations for channel flow and flow over a nonlifting airfoil have computed. Using Gauss-Seidel relaxation ordered in the flow direction, textbook multigrid convergence rates of nearly one order-of-magnitude residual reduction per multigrid cycle are achieved, independent of the grid spacing. This approach also may be applied to the compressible Euler equations and the incompressible Navier-Stokes equations.
Multigrid and multilevel domain decomposition for unstructured grids
Chan, T.; Smith, B.
1994-12-31
Multigrid has proven itself to be a very versatile method for the iterative solution of linear and nonlinear systems of equations arising from the discretization of PDES. In some applications, however, no natural multilevel structure of grids is available, and these must be generated as part of the solution procedure. In this presentation the authors will consider the problem of generating a multigrid algorithm when only a fine, unstructured grid is given. Their techniques generate a sequence of coarser grids by first forming an approximate maximal independent set of the vertices and then applying a Cavendish type algorithm to form the coarser triangulation. Numerical tests indicate that convergence using this approach can be as fast as standard multigrid on a structured mesh, at least in two dimensions.
Reducing Communication in Algebraic Multigrid Using Additive Variants
Vassilevski, Panayot S.; Yang, Ulrike Meier
2014-02-12
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.
Multigrid solution strategies for adaptive meshing problems
NASA Technical Reports Server (NTRS)
Mavriplis, Dimitri J.
1995-01-01
This paper discusses the issues which arise when combining multigrid strategies with adaptive meshing techniques for solving steady-state problems on unstructured meshes. A basic strategy is described, and demonstrated by solving several inviscid and viscous flow cases. Potential inefficiencies in this basic strategy are exposed, and various alternate approaches are discussed, some of which are demonstrated with an example. Although each particular approach exhibits certain advantages, all methods have particular drawbacks, and the formulation of a completely optimal strategy is considered to be an open problem.
Compatible Relaxation and Coarsening in Algebraic Multigrid
Brannick, J J; Falgout, R D
2009-09-22
We introduce a coarsening algorithm for algebraic multigrid (AMG) based on the concept of compatible relaxation (CR). The algorithm is significantly different from standard methods, most notably because it does not rely on any notion of strength of connection. We study its behavior on a number of model problems, and evaluate the performance of an AMG algorithm that incorporates the coarsening approach. Lastly, we introduce a variant of CR that provides a sharper metric of coarse-grid quality and demonstrate its potential with two simple examples.
A multigrid preconditioner for the semiconductor equations
Meza, J.C.; Tuminaro, R.S.
1994-12-31
Currently, integrated circuits are primarily designed in a {open_quote}trial and error{close_quote} fashion. That is, prototypes are built and improved via experimentation and testing. In the near future, however, it may be possible to significantly reduce the time and cost of designing new devices by using computer simulations. To accurately perform these complex simulations in three dimensions, however, new algorithms and high performance computers are necessary. In this paper the authors discuss the use of multigrid preconditioning inside a semiconductor device modeling code, DANCIR. The DANCIR code is a full three-dimensional simulator capable of computing steady-state solutions of the drift-diffusion equations for a single semiconductor device and has been used to simulate a wide variety of different devices. At the inner core of DANCIR is a solver for the nonlinear equations that arise from the spatial discretization of the drift-diffusion equations on a rectangular grid. These nonlinear equations are resolved using Gummel`s method which requires three symmetric linear systems to be solved within each Gummel iteration. It is the resolution of these linear systems which comprises the dominant computational cost of this code. The original version of DANCIR uses a Cholesky preconditioned conjugate gradient algorithm to solve these linear systems. Unfortunately, this algorithm has a number of disadvantages: (1) it takes many iterations to converge (if it converges), (2) it can require a significant amount of computing time, and (3) it is not very parallelizable. To improve the situation, the authors consider a multigrid preconditioner. The multigrid method uses iterations on a hierarchy of grids to accelerate the convergence on the finest grid.
Crane, N K; Parsons, I D; Hjelmstad, K D
2002-03-21
Adaptive mesh refinement selectively subdivides the elements of a coarse user supplied mesh to produce a fine mesh with reduced discretization error. Effective use of adaptive mesh refinement coupled with an a posteriori error estimator can produce a mesh that solves a problem to a given discretization error using far fewer elements than uniform refinement. A geometric multigrid solver uses increasingly finer discretizations of the same geometry to produce a very fast and numerically scalable solution to a set of linear equations. Adaptive mesh refinement is a natural method for creating the different meshes required by the multigrid solver. This paper describes the implementation of a scalable adaptive multigrid method on a distributed memory parallel computer. Results are presented that demonstrate the parallel performance of the methodology by solving a linear elastic rocket fuel deformation problem on an SGI Origin 3000. Two challenges must be met when implementing adaptive multigrid algorithms on massively parallel computing platforms. First, although the fine mesh for which the solution is desired may be large and scaled to the number of processors, the multigrid algorithm must also operate on much smaller fixed-size data sets on the coarse levels. Second, the mesh must be repartitioned as it is adapted to maintain good load balancing. In an adaptive multigrid algorithm, separate mesh levels may require separate partitioning, further complicating the load balance problem. This paper shows that, when the proper optimizations are made, parallel adaptive multigrid algorithms perform well on machines with several hundreds of processors.
An evaluation of parallel multigrid as a solver and a preconditioner for singular perturbed problems
Oosterlee, C.W.; Washio, T.
1996-12-31
In this paper we try to achieve h-independent convergence with preconditioned GMRES and BiCGSTAB for 2D singular perturbed equations. Three recently developed multigrid methods are adopted as a preconditioner. They are also used as solution methods in order to compare the performance of the methods as solvers and as preconditioners. Two of the multigrid methods differ only in the transfer operators. One uses standard matrix- dependent prolongation operators from. The second uses {open_quotes}upwind{close_quotes} prolongation operators, developed. Both employ the Galerkin coarse grid approximation and an alternating zebra line Gauss-Seidel smoother. The third method is based on the block LU decomposition of a matrix and on an approximate Schur complement. This multigrid variant is presented in. All three multigrid algorithms are algebraic methods.
Annaratone, B. M.; Arnas, C.; Elskens, Y.
2008-09-07
The agglomeration of the matter in plasma, from the atomic level up to millimetre size particles, is here considered. In general we identify a continuous growth, due to deposition, and two agglomeration steps, the first at the level of tens of nanometres and the second above the micron. The agglomeration of nano-particles is attributed to electrostatic forces in presence of charge polarity fluctuations. Here we present a model based on discrete currents. With increasing grain size the positive charge permanence decreases, tending to zero. This effect is only important in the range of nanometre for dust of highly dispersed size. When the inter-particle distance is of the order of the screening length another agglomeration mechanism dominates. It is based on attractive forces, shadow forces or dipole-dipole interaction, overcoming the electrostatic repulsion. In bright plasma radiation pressure also plays a role.
On the parallel efficiency of the Frederickson-McBryan multigrid
NASA Technical Reports Server (NTRS)
Decker, Naomi H.
1990-01-01
To take full advantage of the parallelism in a standard multigrid algorithm requires as many processors as points. However, since coarse grids contain fewer points, most processors are idle during the coarse grid iterations. Frederickson and McBryan claim that retaining all points on all grid levels (using all processors) can lead to a superconvergent algorithm. The purpose of this work is to show that the parellel superconvergent multigrid (PSMG) algorithm of Frederickson and McBryan, though it achieves perfect processor utilization, is no more efficient than a parallel implementation of standard multigrid methods. PSMG is simply a new and perhaps simpler way of achieving the same results.
A Hexahedral Multigrid Approach for Simulating Cuts in Deformable Objects.
Dick, C; Georgii, J; Westermann, R
2011-11-01
We present a hexahedral finite element method for simulating cuts in deformable bodies using the corotational formulation of strain at high computational efficiency. Key to our approach is a novel embedding of adaptive element refinements and topological changes of the simulation grid into a geometric multigrid solver. Starting with a coarse hexahedral simulation grid, this grid is adaptively refined at the surface of a cutting tool until a finest resolution level, and the cut is modeled by separating elements along the cell faces at this level. To represent the induced discontinuities on successive multigrid levels, the affected coarse grid cells are duplicated and the resulting connectivity components are distributed to either side of the cut. Drawing upon recent work on octree and multigrid schemes for the numerical solution of partial differential equations, we develop efficient algorithms for updating the systems of equations of the adaptive finite element discretization and the multigrid hierarchy. To construct a surface that accurately aligns with the cuts, we adapt the splitting cubes algorithm to the specific linked voxel representation of the simulation domain we use. The paper is completed by a convergence analysis of the finite element solver and a performance comparison to alternative numerical solution methods. These investigations show that our approach offers high computational efficiency and physical accuracy, and that it enables cutting of deformable bodies at very high resolutions. PMID:21173453
Coarse Spaces by Algebraic Multigrid: Multigrid Convergence and Upscaled Error Estimates
Vassilevski, P S
2010-04-30
We give an overview of a number of algebraic multigrid methods targeting finite element discretization problems. The focus is on the properties of the constructed hierarchy of coarse spaces that guarantee (two-grid) convergence. In particular, a necessary condition known as 'weak approximation property', and a sufficient one, referred to as 'strong approximation property' are discussed. Their role in proving convergence of the TG method (as iterative method) and also on the approximation properties of the AMG coarse spaces if used as discretization tool is pointed out. Some preliminary numerical results illustrating the latter aspect are also reported.
Effect of temperature on wet agglomeration of crystals
Maghsoodi, Maryam; Yari, Zahra
2014-01-01
Objective(s): This study dealt with the wet agglomeration process in which a small quantity of binder liquid was added into a suspension of crystals, directly in the stirring vessel where the crystallization took place. The purpose of this investigation was evaluation of the effect of temperature on the agglomeration process in order to gain insight into the mechanism of the formation of the agglomerates. Materials and Methods: Carbamazepine was used as a model drug and water/ethanol and isopropyl acetate were used as crystallization system and binder liquid, respectively. The agglomeration of crystals was carried out at various temperatures and the agglomerates were characterized in terms of size, morphology, density and mechanical strength. Results: Evaluation of the agglomerates along the course of agglomeration shows that the properties of the particles change gradually but substantially. Higher temperature of the system during agglomeration process favors the formation of more regular agglomerates with mechanically stronger and denser structure; this can be explained by the promotion effect of temperature on the agglomeration process. Conclusion: With optimized wet agglomeration temperature, spherical, dense, and strong agglomerates can be obtained. PMID:24967063
Operator induced multigrid algorithms using semirefinement
NASA Technical Reports Server (NTRS)
Decker, Naomi; Vanrosendale, John
1989-01-01
A variant of multigrid, based on zebra relaxation, and a new family of restriction/prolongation operators is described. Using zebra relaxation in combination with an operator-induced prolongation leads to fast convergence, since the coarse grid can correct all error components. The resulting algorithms are not only fast, but are also robust, in the sense that the convergence rate is insensitive to the mesh aspect ratio. This is true even though line relaxation is performed in only one direction. Multigrid becomes a direct method if an operator-induced prolongation is used, together with the induced coarse grid operators. Unfortunately, this approach leads to stencils which double in size on each coarser grid. The use of an implicit three point restriction can be used to factor these large stencils, in order to retain the usual five or nine point stencils, while still achieving fast convergence. This algorithm achieves a V-cycle convergence rate of 0.03 on Poisson's equation, using 1.5 zebra sweeps per level, while the convergence rate improves to 0.003 if optimal nine point stencils are used. Numerical results for two and three dimensional model problems are presented, together with a two level analysis explaining these results.
Operator induced multigrid algorithms using semirefinement
NASA Technical Reports Server (NTRS)
Decker, Naomi Henderson; Van Rosendale, John
1989-01-01
A variant of multigrid, based on zebra relaxation, and a new family of restriction/prolongation operators is described. Using zebra relaxation in combination with an operator-induced prolongation leads to fast convergence, since the coarse grid can correct all error components. The resulting algorithms are not only fast, but are also robust, in the sense that the convergence rate is insensitive to the mesh aspect ratio. This is true even though line relaxation is performed in only one direction. Multigrid becomes a direct method if an operator-induced prolongation is used, together with the induced coarse grid operators. Unfortunately, this approach leads to stencils which double in size on each coarser grid. The use of an implicit three point restriction can be used to factor these large stencils, in order to retain the usual five or nine point stencils, while still achieving fast convergence. This algorithm achieves a V-cycle convergence rate of 0.03 on Poisson's equation, using 1.5 zebra sweeps per level, while the convergence rate improves to 0.003 if optimal nine point stencils are used. Numerical results for two- and three-dimensional model problems are presented, together with a two level analysis explaining these results.
Analysis Tools for CFD Multigrid Solvers
NASA Technical Reports Server (NTRS)
Mineck, Raymond E.; Thomas, James L.; Diskin, Boris
2004-01-01
Analysis tools are needed to guide the development and evaluate the performance of multigrid solvers for the fluid flow equations. Classical analysis tools, such as local mode analysis, often fail to accurately predict performance. Two-grid analysis tools, herein referred to as Idealized Coarse Grid and Idealized Relaxation iterations, have been developed and evaluated within a pilot multigrid solver. These new tools are applicable to general systems of equations and/or discretizations and point to problem areas within an existing multigrid solver. Idealized Relaxation and Idealized Coarse Grid are applied in developing textbook-efficient multigrid solvers for incompressible stagnation flow problems.