Engineering PapersSearch

SEARCH · Engineering Papers

Results for “Preconditioning”

Search indexed NASA NTRS and DOE OSTI research on propulsion, heat transfer, battery materials and energy systems. Follow report and document links to the original sources.

Quote a phrase for an exact phrase match. Source license links do not imply unrestricted reuse.

At least 163 records · Page 9

Experiments with conjugate gradient algorithms for homotopy curve tracking

There are algorithms for finding zeros or fixed points of nonlinear systems of equations that are globally convergent for almost all starting points, i.e., with probability one. The essence of all such algorithms is the construction of an appropriate homotopy map and then tracking some smooth curve in the zero set of this homotopy map. HOMPACK is a mathematical software package implementing globally convergent homotopy algorithms with three different techniques for tracking a homotopy zero curve, and has separate routines for dense and sparse Jacobian matrices. The HOMPACK algorithms for sparse Jacobian matrices use a preconditioned conjugate gradient algorithm for the computation of the kernel of the homotopy Jacobian matrix, a required linear algebra step for homotopy curve tracking. Here, variants of the conjugate gradient algorithm are implemented in the context of homotopy curve tracking and compared with Craig's preconditioned conjugate gradient method used in HOMPACK. The test problems used include actual large scale, sparse structural mechanics problems.

Irani, Kashmira M.

An accelerated lambda iteration method for multilevel radiative transfer. I - Non-overlapping lines with background continuum

A method is presented for solving multilevel transfer problems when nonoverlapping lines and background continuum are present and active continuum transfer is absent. An approximate lambda operator is employed to derive linear, 'preconditioned', statistical-equilibrium equations. A method is described for finding the diagonal elements of the 'true' numerical lambda operator, and therefore for obtaining the coefficients of the equations. Iterations of the preconditioned equations, in conjunction with the transfer equation's formal solution, are used to solve linear equations. Some multilevel problems are considered, including an eleven-level neutral helium atom. Diagonal and tridiagonal approximate lambda operators are utilized in the problems to examine the convergence properties of the method, and it is found to be effective for the line transfer problems.

Rybicki, G. B.

Iterative solution techniques in boundary element analysis

Iterative techniques for the solution of the algebraic equations associated with the direct boundary element analysis (BEA) method are discussed. Continuum structural response analysis problems are considered, employing single- and multizone boundary element models with and without zone condensation. The impact on convergence rate and computer resource requirements associated with the sparse and blocked matrices, resulting in multizone BEA, is studied. Both conjugate gradient and generalized minimum residual preconditioned iterative solvers are applied for these problems and the performance of these algorithms is reported. Included is a quantification of the impact of the preconditioning utilized to render the boundary element matrices solvable by the respective iterative methods in a time competitive with direct methods.

Kane, J. H.

Modeling deep convection in the Greenland Sea

The development of deep convective events in the high-latitude ocean is studied using a three-dimensional, coupled ice-ocean model. Oceanic mixing is described according to the level 2.5 turbulence closure scheme in which convection occurs in a continuous way, i.e., convective adjustment is not invoked. The model is forced by strong winds and surface cooling. Strong upwelling at the multilyear ice edge and consequent entrainment of warm Atlantic waters into the mixed layer is produced by winds parallel to the ice edge. Concomitant cooling drives deep convection and produces chimneylike structures. Inclusion of a barotropic mean flow over topography to the model provides important preconditioning and selects the location of deep convection. The most efficient preconditioning occurs at locations where the flow ascends a slope. In a stratified environment similar to the Greenland Sea with a 12 m/s wind the model simulations show that localized deep convection takes place after about 10 days to depths of 1000 m.

Hakkinen, S.

The effect of grid aspect ratio on convergence

Vector stability theory and computational experiments are used to examine the effects of high aspect ratio grids on algorithm convergence. Emphasis is placed on identifying the degree of convergence deterioration that ADI schemes experience as grid aspect ratio increases and on deriving methods for circumventing this problem. Approximately factored implicit schemes are found to experience convergence deterioration because of nonoptimum local time stepping procedures and the increased need for viscous preconditioning. An enhanced algorithm is devised on the basis of improved selection of the local time step, appropriate definition of viscous preconditioning matrix, and proper implementation of boundary conditions. The novel algorithm provides uniformly efficient convergence at all aspect ratios for both Euler and Navier-Stokes computations for a variety of test problems.

Buelow, P. E. O.

Flow Coefficient Behavior for Boundary Layer Bleed Holes and Slots

An experimental investigation into the flow coefficient behavior for nine boundary layer bleed orifice configurations is reported. This test was conducted for the purposes of exploring boundary layer control through mass flow removal and does not address issues of stability bleed. Parametric data consist of bleed region flow coefficient as a function of Mach number, bleed plenum pressure, and bleed orifice geometry. Seven multiple hole configurations and two single slot configurations were tested over a supersonic Mach number range of 1.3 to 2.5 (nominal). Advantages gained by using multiple holes in a bleed region instead of a single spanwise slot are discussed and the issue of modeling an entire array of bleed orifices based on the performance of a single orifice is addressed. Preconditioning the flow approaching a 90 degree inclined (normal) hole configuration resulted in a significant improvement in the performance of the configuration. The same preconditioning caused only subtle changes in performance for a 20 degree inclined (slanted) configuration.

Willis, B. P.

Towards a generalized computational fluid dynamics technique for all Mach numbers

Currently there exists no single unified approach for efficiently and accurately solving computational fluid dynamics (CFD) problems across the Mach number regime, from truly low speed incompressible flows to hypersonic speeds. There are several CFD codes that have evolved into sophisticated prediction tools with a wide variety of features including multiblock capabilities, generalized chemistry and thermodynamics models among other features. However, as these codes evolve, the demand placed on the end user also increases simply because of the myriad of features that are incorporated into these codes. In order for a user to be able to solve a wide range of problems, several codes may be needed requiring the user to be familiar with the intricacies of each code and their rather complicated input files. Moreover, the cost of training users and maintaining several codes becomes prohibitive. The objective of the current work is to extend the compressible, characteristic-based, thermochemical nonequilibrium Navier-Stokes code GASP to very low speed flows and simultaneously improve convergence at all speeds. Before this work began, the practical speed range of GASP was Mach numbers on the order of 0.1 and higher. In addition, a number of new techniques have been developed for more accurate physical and numerical modeling. The primary focus has been on the development of optimal preconditioning techniques for the Euler and the Navier-Stokes equations with general finite-rate chemistry models and both equilibrium and nonequilibrium thermodynamics models. We began with the work of Van Leer, Lee, and Roe for inviscid, one-dimensional perfect gases and extended their approach to include three-dimensional reacting flows. The basic steps required to accomplish this task were a transformation to stream-aligned coordinates, the formulation of the preconditioning matrix, incorporation into both explicit and implicit temporal integration schemes, and modification of the numerical flux formulae. In addition, we improved the convergence rate of the implicit time integration schemes in GASP through the use of inner iteration strategies and the use of the GMRES (General Minimized Resisual) which belongs to the class of algorithms referred to as Krylov subspace iteration. Finally, we significantly improved the practical utility of GASP through the addition of mesh sequencing, a technique in which computations begin on a coarse grid and get interpolated onto successively finer grids. The fluid dynamic problems of interest to the propulsion community involve complex flow physics spanning different velocity regimes and possibly involving chemical reactions. This class of problems results in widely disparate time scales causing numerical stiffness. Even in the absence of chemical reactions, eigenvalue stiffness manifests itself at transonic and very low speed flows which can be quantified by the large condition number of the system and evidenced by slow convergence rates. This results in the need for thorough numerical analysis and subsequent implementation of sophisticated numerical techniques for these difficult yet practical problems. As a result of this work, we have been able to extend the range of applicability of compressible codes to very low speed inviscid flows (M = .001) and reacting flows.

Walters, R. W.

Convergence acceleration of implicit schemes in the presence of high aspect ratio grid cells

The performance of Navier-Stokes codes are influenced by several phenomena. For example, the robustness of the code may be compromised by the lack of grid resolution, by a need for more precise initial conditions or because all or part of the flowfield lies outside the flow regime in which the algorithm converges efficiently. A primary example of the latter effect is the presence of extended low Mach number and/or low Reynolds number regions which cause convergence deterioration of time marching algorithms. Recent research into this problem by several workers including the present authors has largely negated this difficulty through the introduction of time-derivative preconditioning. In the present paper, we employ the preconditioned algorithm to address convergence difficulties arising from sensitivity to grid stretching and high aspect ratio grid cells. Strong grid stretching is particularly characteristic of turbulent flow calculations where the grid must be refined very tightly in the dimension normal to the wall, without a similar refinement in the tangential direction. High aspect ratio grid cells also arise in problems that involve high aspect ratio domains such as combustor coolant channels. In both situations, the high aspect ratio cells can lead to extreme deterioration in convergence. It is the purpose of the present paper to address the reasons for this adverse response to grid stretching and to suggest methods for enhancing convergence under such circumstances. Numerical algorithms typically possess a maximum allowable or optimum value for the time step size, expressed in non-dimensional terms as a CFL number or vonNeumann number (VNN). In the presence of high aspect ratio cells, the smallest dimension of the grid cell controls the time step size causing it to be extremely small, which in turn results in the deterioration of convergence behavior. For explicit schemes, this time step limitation cannot be exceeded without violating stability restrictions of the scheme. On the other hand, for implicit schemes, which are typically unconditionally stable, there appears to be room for improvement through careful tailoring of the time step definition based on results of linear stability analyses. In the present paper, we focus on the central-differenced alternating direction implicit (ADI) scheme. The understanding garnered from this analyses can then be applied to other implicit schemes. In order to systematically study the effects of aspect ratio and the methods of mitigating the associated problems, we use a two pronged approach. We use stability analyses as a tool for predicting numerical convergence behavior and numerical experiments on simple model problems to verify predicted trends. Based on these analyses, we determine that efficient convergence may be obtained at all aspect ratios by getting a combination of things right. Primary among these are the proper definition of the time step size, proper selection of viscous preconditioner and the precise treatment of boundary conditions. These algorithmic improvements are then applied to a variety of test cases to demonstrate uniform convergence at all aspect ratios.

Buelow, B. E. O.

Reliability enhancement of Navier-Stokes codes through convergence acceleration

Methods for enhancing the reliability of Navier-Stokes computer codes through improving convergence characteristics are presented. The improving of these characteristics decreases the likelihood of code unreliability and user interventions in a design environment. The problem referred to as a 'stiffness' in the governing equations for propulsion-related flowfields is investigated, particularly in regard to common sources of equation stiffness that lead to convergence degradation of CFD algorithms. Von Neumann stability theory is employed as a tool to study the convergence difficulties involved. Based on the stability results, improved algorithms are devised to ensure efficient convergence in different situations. A number of test cases are considered to confirm a correlation between stability theory and numerical convergence. The examples of turbulent and reacting flow are presented, and a generalized form of the preconditioning matrix is derived to handle these problems, i.e., the problems involving additional differential equations for describing the transport of turbulent kinetic energy, dissipation rate and chemical species. Algorithms for unsteady computations are considered. The extension of the preconditioning techniques and algorithms derived for Navier-Stokes computations to three-dimensional flow problems is discussed. New methods to accelerate the convergence of iterative schemes for the numerical integration of systems of partial differential equtions are developed, with a special emphasis on the acceleration of convergence on highly clustered grids.

Merkle, Charles L.

Effect of grid aspect ratio on convergence

The effects of high-aspect-ratio grids on algorithm convergence are considered by means of vector stability theory and computational experiments. The results indicate that approximately factored implicit schemes experience convergence deterioration because of nonoptimum local time-stepping procedures and increased need for viscous preconditioning. Based on this insight, an enhanced algorithm is devised using improved selection of the local time step, appropriate definition of the viscous preconditioning matrix, and proper implementation of the boundary conditions. The new algorithm provides uniformly efficient convergence at all aspect ratios for both Euler and Navier-Stokes computations for a variety of test problems.

Buelow, P. E. O.

Time integration algorithms for the two-dimensional Euler equations on unstructured meshes

Explicit and implicit time integration algorithms for the two-dimensional Euler equations on unstructured grids are presented. Both cell-centered and cell-vertex finite volume upwind schemes utilizing Roe's approximate Riemann solver are developed. For the cell-vertex scheme, a four-stage Runge-Kutta time integration, a fourstage Runge-Kutta time integration with implicit residual averaging, a point Jacobi method, a symmetric point Gauss-Seidel method and two methods utilizing preconditioned sparse matrix solvers are presented. For the cell-centered scheme, a Runge-Kutta scheme, an implicit tridiagonal relaxation scheme modeled after line Gauss-Seidel, a fully implicit lower-upper (LU) decomposition, and a hybrid scheme utilizing both Runge-Kutta and LU methods are presented. A reverse Cuthill-McKee renumbering scheme is employed for the direct solver to decrease CPU time by reducing the fill of the Jacobian matrix. A comparison of the various time integration schemes is made for both first-order and higher order accurate solutions using several mesh sizes, higher order accuracy is achieved by using multidimensional monotone linear reconstruction procedures. The results obtained for a transonic flow over a circular arc suggest that the preconditioned sparse matrix solvers perform better than the other methods as the number of elements in the mesh increases.

Slack, David C.

Fast Multigrid Techniques in Total Variation-Based Image Reconstruction

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.

Oman, Mary Ellen

Quasi-Optimal Schwarz Methods for the Conforming Spectral Element Discretization

Fast methods are proposed for solving the system K(sub N)x = b resulting from the discretization of self-adjoint elliptic equations in three dimensional domains by the spectral element method. The domain is decomposed into hexahedral elements, and in each of these elements the discretization space is formed by polynomials of degree N in each variable. Gauss-Lobatto-Legendre (GLL) quadrature rules replace the integrals in the Galerkin formulation. This system is solved by the preconditioned conjugate gradients method. The conforming finite element space on the GLL mesh consisting of piecewise Q(sub 1) elements produces a stiffness matrix K(sub h) that is spectrally equivalent to the spectral element stiffness matrix K(sub N). The action of the inverse of K(sub h) is expensive for large problems, and is therefore replaced by a Schwarz preconditioner B(sub h) of this finite element stiffness matrix. The preconditioned operator then becomes B(sub h)(exp -l)K(sub N). The technical difficulties stem from the nonregularity of the mesh. Tools to estimate the convergence of a large class of new iterative substructuring and overlapping Schwarz preconditioners are developed. This technique also provides a new analysis for an iterative substructuring method proposed by Pavarino and Widlund for the spectral element discretization.

Casarin, Mario

Multigrid and Krylov Subspace Methods for the Discrete Stokes Equations

Discretization of the Stokes equations produces a symmetric indefinite system of linear equations. For stable discretizations, a variety of numerical methods have been proposed that have rates of convergence independent of the mesh size used in the discretization. In this paper, we compare the performance of four such methods: variants of the Uzawa, preconditioned conjugate gradient, preconditioned conjugate residual, and multigrid methods, for solving several two-dimensional model problems. The results indicate that where it is applicable, multigrid with smoothing based on incomplete factorization is more efficient than the other methods, but typically by no more than a factor of two. The conjugate residual method has the advantage of being both independent of iteration parameters and widely applicable.

Elman, Howard C.

Comparison of Implicit Schemes for the Incompressible Navier-Stokes Equations

For a computational flow simulation tool to be useful in a design environment, it must be very robust and efficient. To develop such a tool for incompressible flow applications, a number of different implicit schemes are compared for several two-dimensional flow problems in the current study. The schemes include Point-Jacobi relaxation, Gauss-Seidel line relaxation, incomplete lower-upper decomposition, and the generalized minimum residual method preconditioned with each of the three other schemes. The efficiency of the schemes is measured in terms of the computing time required to obtain a steady-state solution for the laminar flow over a backward-facing step, the flow over a NACA 4412 airfoil, and the flow over a three-element airfoil using overset grids. The flow solver used in the study is the INS2D code that solves the incompressible Navier-Stokes equations using the method of artificial compressibility and upwind differencing of the convective terms. The results show that the generalized minimum residual method preconditioned with the incomplete lower-upper factorization outperforms all other methods by at least a factor of 2.

Rogers, Stuart E.

A Parallel Non-Overlapping Domain-Decomposition Algorithm for Compressible Fluid Flow Problems on Triangulated Domains

This paper considers an algebraic preconditioning algorithm for hyperbolic-elliptic fluid flow problems. The algorithm is based on a parallel non-overlapping Schur complement domain-decomposition technique for triangulated domains. In the Schur complement technique, the triangulation is first partitioned into a number of non-overlapping subdomains and interfaces. This suggests a reordering of triangulation vertices which separates subdomain and interface solution unknowns. The reordering induces a natural 2 x 2 block partitioning of the discretization matrix. Exact LU factorization of this block system yields a Schur complement matrix which couples subdomains and the interface together. The remaining sections of this paper present a family of approximate techniques for both constructing and applying the Schur complement as a domain-decomposition preconditioner. The approximate Schur complement serves as an algebraic coarse space operator, thus avoiding the known difficulties associated with the direct formation of a coarse space discretization. In developing Schur complement approximations, particular attention has been given to improving sequential and parallel efficiency of implementations without significantly degrading the quality of the preconditioner. A computer code based on these developments has been tested on the IBM SP2 using MPI message passing protocol. A number of 2-D calculations are presented for both scalar advection-diffusion equations as well as the Euler equations governing compressible fluid flow to demonstrate performance of the preconditioning algorithm.

Barth, Timothy J.

Algebraic Nonoverlapping Domain Decomposition Methods for Stabilized FEM and FV Discretizations

We consider preconditioning methods for convection dominated fluid flow problems based on a nonoverlapping Schur complement domain decomposition procedure for arbitrary triangulated domains. The triangulation is first partitioned into a number of subdomains and interfaces which induce a natural 2 x 2 partitioning of the p.d.e. discretization matrix. We view the Schur complement induced by this partitioning as an algebraically derived coarse space approximation. This avoids the known difficulties associated with the direct formation of an effective coarse discretization for advection dominated equations. By considering various approximations of the block factorization of the 2 x 2 system, we have developed a family of robust preconditioning techniques. A computer code based on these ideas has been developed and tested on the IBM SP2 using MPI message passing protocol. A number of 2-D CFD calculations will be presented for both scalar advection-diffusion equations and the Euler equations discretized using stabilized finite element and finite volume methods. These results show very good scalability of the preconditioner for various discretizations as the number of processors is increased while the number of degrees of freedom per processor is fixed.

Barth, Timothy J.

Effects of Ordering Strategies and Programming Paradigms on Sparse Matrix Computations

The Conjugate Gradient (CG) algorithm is perhaps the best-known iterative technique to solve sparse linear systems that are symmetric and positive definite. For systems that are ill-conditioned, it is often necessary to use a preconditioning technique. In this paper, we investigate the effects of various ordering and partitioning strategies on the performance of parallel CG and ILU(O) preconditioned CG (PCG) using different programming paradigms and architectures. Results show that for this class of applications: ordering significantly improves overall performance on both distributed and distributed shared-memory systems, that cache reuse may be more important than reducing communication, that it is possible to achieve message-passing performance using shared-memory constructs through careful data ordering and distribution, and that a hybrid MPI+OpenMP paradigm increases programming complexity with little performance gains. A implementation of CG on the Cray MTA does not require special ordering or partitioning to obtain high efficiency and scalability, giving it a distinct advantage for adaptive applications; however, it shows limited scalability for PCG due to a lack of thread level parallelism.

Oliker, Leonid