DRUM :: Browsing by Author "Elman, Howard C."

Browsing by Author "Elman, Howard C."

Now showing 1 - 20 of 26

A Block Preconditioner for an Exact Penalty Formulation for Stationary MHD
(2014-02-04) Phillips, Edward G.; Elman, Howard C.; Cyr, Eric C.; Shadid, John N.; Pawlowski, Roger P.
The magnetohydrodynamics (MHD) equations are used to model the flow of electrically conducting fluids in such applications as liquid metals and plasmas. This system of non-self adjoint, nonlinear PDEs couples the Navier-Stokes equations for fluids and Maxwell's equations for electromagnetics. There has been recent interest in fully coupled solvers for the MHD system because they allow for fast steady-state solutions that do not require pseudo-time stepping. When the fully coupled system is discretized, the strong coupling can make the resulting algebraic systems difficult to solve, requiring effective preconditioning of iterative methods for efficiency. In this work, we consider a finite element discretization of an exact penalty formulation for the stationary MHD equations. This formulation has the benefit of implicitly enforcing the divergence free condition on the magnetic field without requiring a Lagrange multiplier. We consider extending block preconditioning techniques developed for the Navier-Stokes equations to the full MHD system. We analyze operators arising in block decompositions from a continuous perspective and apply arguments based on the existence of approximate commutators to develop new preconditioners that account for the physical coupling. This results in a family of parameterized block preconditioners for both Picard and Newton linearizations. We develop an automated method for choosing the relevant parameters and demonstrate the robustness of these preconditioners for a range of the physical non-dimensional parameters and with respect to mesh refinement.
Block-Diagonal Preconditioning for Spectral Stochastic Finite Element Systems
(2007-06) Powell, Catherine E.; Elman, Howard C.
Deterministic models of fluid flow and the transport of chemicals in flows in heterogeneous porous media incorporate PDEs whose material parameters are assumed to be known exactly. To tackle more realistic stochastic flow problems, it is fitting to represent the permeability coefficients as random fields with prescribed statistics. Traditionally, large numbers of deterministic problems are solved in a Monte Carlo framework and the solutions averaged to obtain statistical properties of the solution variables. Alternatively, so-called stochastic finite element methods (SFEMs) discretise the probabilistic dimension of the PDE directly leading to a single structured linear system. The latter approach is becoming extremely popular but its computational cost is still perceived to be problematic as this system is orders of magnitude larger than for the corresponding deterministic problem. A simple block-diagonal preconditioning strategy, incorporating only the mean component of the random field coefficient and based on incomplete factorisations has been employed in the literature, and observed to be robust, for problems of moderate variance, but without theoretical analysis. We solve the stochastic Darcy flow problem in primal formulation via the spectral SFEM and focus on its efficient iterative solution. To achieve optimal computational complexity, we base our block-diagonal preconditioner on algebraic multigrid. In addition, we provide new theoretical eigenvalue bounds for the preconditioned system matrix and highlight the dependence of the iteration counts on all the SFEM parameters.
Boundary Conditions in Approximate Commutator Preconditioners for the Navier-Stokes Equations
(2009-02) Elman, Howard C.; Tuminaro, Ray S.
Boundary conditions are analyzed for a class of preconditioners used for the incompressible Navier-Stokes equations. We consider pressure convection-diffusion preconditioners [8,12] as well as least-square commutator methods [2,3], both of which rely on commutators of certain differential operators. The effectiveness of these methods has been demonstrated in various studies, but both methods also have some deficiencies. For example, the pressure convection-diffusion preconditioner requires the construction of a Laplace and a convection--diffusion operator, together with some choices of boundary conditions. These boundary conditions are not well understood, and a poor choice can critically affect performance. This paper looks closely at properties of commutators near domain boundaries. We show that it is sometimes possible to choose boundary conditions to force the commutators of interest to be zero at boundaries, and this leads to a new strategy for choosing boundary conditions for the purpose of specifying preconditioning operators. With the new preconditioners, Krylov subspace methods display noticeably improved performance for solving the Navier-Stokes equations; in particular, mesh-independent convergence rates are observed for some problems for which previous versions of the methods did not exhibit this behavior.
A Characterisation of Oscillations in the Discrete Two-Dimensional Convection-Diffusion Equation
(2000-03-23) Elman, Howard C.; Ramage, Alison
It is well known that discrete solutions to the convection-diffusion equation contain nonphysical oscillations when boundary layers are present but not resolved by the discretisation. However, except for one-dimensional problems, there is little analysis of this phenomenon. In this paper, we present an analysis of the two-dimensional problem with constant flow aligned with the grid, based on a Fourier decomposition of the discrete solution. For Galerkin bilinear finite element discretisations, we derive closed form expressions for the Fourier coefficients, showing them to be weighted sums of certain functions which are oscillatory when the mesh P\'{e}clet number is large. The oscillatory functions are determined as solutions to a set of three-term recurrences, are then used to characterise the oscillations of the discrete solution in terms of the mesh P\'{e}clet number and boundary conditions of the problem. (Also cross-referenced UMIACS-TR-2000-15)
Convergence Analysis of Iterative Solvers in Inexact Rayleigh Quotient Iteration
(2008-01) Xue, Fei; Elman, Howard C.
We present a detailed convergence analysis of preconditioned MINRES for approximately solving the linear systems that arise when Rayleigh Quotient Iteration is used to compute the lowest eigenpair of a symmetric positive definite matrix. We provide insight into the ``slow start'' of MINRES iteration in both a qualitative and quantitative way, and show that the convergence of MINRES mainly depends on how quickly the unique negative eigenvalue of the preconditioned shifted coefficient matrix is approximated by its corresponding harmonic Ritz value. By exploring when the negative Ritz value appears in MINRES iteration, we obtain a better understanding of the limitation of preconditioned MINRES in this context and the virtue of a new type of preconditioner with ``tuning''. Comparison of MINRES with SYMMLQ in this context is also given. Finally we show that tuning based on a rank-2 modification can be applied with little additional cost to guarantee positive definiteness of the tuned preconditioner.
Efficient Iterative Algorithms for Linear Stability Analysis of Incompressible Flows
(2013-11-07) Elman, Howard C.; Rostami, Minghao W.
Linear stability analysis of a dynamical system entails finding the rightmost eigenvalue for a series of eigenvalue problems. For large-scale systems, it is known that conventional iterative eigenvalue solvers are not reliable for computing this eigenvalue. A more robust method recently developed in Elman & Wu (2012) and Meerbergen & Spence (2010), Lyapunov inverse iteration, involves solving large-scale Lyapunov equations, which in turn requires the solution of large, sparse linear systems analogous to those arising from solving the underlying partial differential equations. This study explores the efficient implementation of Lyapunov inverse iteration when it is used for linear stability analysis of incompressible flows. Efficiencies are obtained from effective solution strategies for the Lyapunov equations and for the underlying partial differential equations. Existing solution strategies are tested and compared, and a modified version of a Lyapunov solver is proposed that achieves significant savings in computational cost.
Efficient Iterative Solution of the Three-Dimensional Helmholtz Equation
(1998-10-15) Elman, Howard C.; O'Leary, Dianne P.
We examine preconditioners for the discrete indefinite Helmholtz equation on a three-dimensional box-shaped domain with Sommerfeld-like boundary conditions. The preconditioners are of two types. The first is derived by discretization of a related continuous operator that differs from the original only in its boundary conditions. The second is derived by a block Toeplitz approximation to the discretized problem. The resulting preconditioning matrices allow the use of fast transform methods and differ from the discrete Helmholtz operator by an operator of low rank. We present experimental results demonstrating that when these methods are combined with Krylov subspace iteration, convergence rates depend only mildly on both the wave number and discretization mesh size. In addition, the methods display high efficiencies in an implementation on an IBM SP-2 parallel computer. (Also cross-referenced as UMIACS-TR-97-63)
Efficient Iterative Solvers for Stochastic Galerkin Discretizations of Log-Transformed Random Diffusion Problems
(2011-06-22) Ullmann, Elisabeth; Elman, Howard C.; Ernst, Oliver G.
We consider the numerical solution of a steady-state diffusion problem where the diffusion coefficient is the exponent of a random field. The standard stochastic Galerkin formulation of this problem is computationally demanding because of the nonlinear structure of the uncertain component of it. We consider a reformulated version of this problem as a stochastic convection-diffusion problem with random convective velocity that depends linearly on a fixed number of independent truncated Gaussian random variables. The associated Galerkin matrix is nonsymmetric but sparse and allows for fast matrix-vector multiplications with optimal complexity. We construct and analyze two block-diagonal preconditioners for this Galerkin matrix for use with Krylov subspace methods such as the generalized minimal residual method. We test the efficiency of the proposed preconditioning approaches and compare the iterative solver performance for a model problem posed in both diffusion and convection-diffusion formulations.
Eigenanalysis of Some Preconditioned Helmholtz Problems
(1998-10-15) Elman, Howard C.; O'Leary, Dianne P.
In this work we calculate the eigenvalues obtained by preconditioning the discrete Helmholtz operator with Sommerfeld-like boundary conditions on a rectilinear domain, by a related operator with boundary conditions that permit the use of fast solvers. The main innovation is that the eigenvalues for two and three-dimensional domains can be calculated exactly by solving a set of one-dimensional eigenvalue problems. This permits analysis of quite large problems. For grids fine enough to resolve the solution for a given wave number, preconditioning using Neumann boundary conditions yields eigenvalues that are uniformly bounded, located in the first quadrant, and outside the unit circle. In contrast, Dirichlet boundary conditions yield eigenvalues that approach zero as the product of wave number with the mesh size is decreased. These eigenvalue properties yield the first insight into the behavior of iterative methods such as GMRES applied to these preconditioned problems. (Also cross-referenced as UMIACS-TR-98-22)
Fast Nonsymmetric Iterations and Preconditioning for Navier-Stokes Equations
(1998-10-15) Elman, Howard C.; Silvester, David J.
Discretization and linearization of the steady-state Navier-Stokes equations gives rise to a nonsymmetric indefinite linear system of equations. In this paper, we introduce preconditioning techniques for such systems with the property that the eigenvalues of the preconditioned matrices are bounded independently of the mesh size used in the discretization. We confirm and supplement these analytic results with a series of numerical experiments indicating that Krylov subspace iterative methods for nonsymmetric systems display rates of convergence that are independent of the mesh parameter. In addition, we show that preconditioning costs can be kept small by using iterative methods for some intermediate steps performed by the preconditioner. (Also cross-referenced as UMIACS-TR-94-66)
Fast Solvers for Models of ICEO Microfluidic Flows
(2008-01) Shuttleworth, Robert R.; Elman, Howard C.; Long, Kevin R.; Templeton, Jeremy A.
We demonstrate the performance of a fast computational algorithm for modeling the design of a microfluidic mixing device. The device uses an electrokinetic process, induced charge electroosmosis, by which a flow through the device is driven by a set of charged obstacles in it. Its design is realized by manipulating the shape and orientation of the obstacles in order to maximize the amount of fluid mixing within the device. The computation entails the solution of a constrained optimization problem in which function evaluations require the numerical solution of a set of partial differential equations: a potential equation, the incompressible Navier-Stokes equations, and a mass transport equation. The most expensive component of the function evaluation (which must be performed at every step of an iteration for the optimization) is the solution of the Navier-Stokes equations. We show that by using some new robust algorithms for this task, based on certain preconditioners that take advantage of the structure of the linearized problem, this computation can be done efficiently. Using this computational strategy, in conjunction with a derivative-free pattern search algorithm for the optimization, applied to a finite element discretization of the problem, we are able to determine optimal configurations of microfluidic devices.
Iterative Methods for Problems in Computational Fluid Dynamics
(1998-10-15) Elman, Howard C.; Silvester, David J.; Wathen, Andrew J.
We discuss iterative methods for solving the algebraic systems of equations arising from linearization and discretization of primitive variable formulations of the incompressible Navier-Stokes equations. Implicit discretization in time leads to a coupled but linear system of partial differential equations at each time step, and discretization in space then produces a series of linear algebraic systems. We give an overview of commonly used time and space discretization techniques,and we discuss a variety of algorithmic strategies for solving the resulting systems of equations.The emphasis is on preconditioning techniques, which can be combined with Krylov subspace iterative methods.In many cases the solution of subsidiary problems such as the discrete convection-diffusion equation and the discrete Stokes equations plays a crucial role. We examine iterative techniques for these problems and show how they can be integrated into effective solution algorithms for the Navier-Stokes equations. (Also cross-referenced as UMIACS-TR-96-58)
Iterative Methods for Stabilized DiscreteConvection--Diffusion Problems
(1998-10-28) Shih, Yin-Tzer; Elman, Howard C.
In this paper, we study the computational cost of solving the convection-diffusion equation using various discretization strategies and iteration solution algorithms. The choice of discretization influences the properties of the discrete solution and also the choice of solution algorithm. The discretizations considered here are stabilized low order finite element schemes using streamline diffusion, crosswind diffusion and shock--capturing. The latter, shock--capturing discretizations lead to nonlinear algebraic systems and require nonlinear algorithms. We compare various preconditioned Krylov subspace methods including Newton--Krylov methods for nonlinear problems, as well as several preconditioners based on relaxation and incomplete factorization. We find that although enhanced stabilization based on shock--capturing requires fewer degrees of freedom than linear stabilizations to achieve comparable accuracy, the nonlinear algebraic systems are more costly to solve than those derived from a judicious combination of streamline diffusion and crosswind diffusion. Solution algorithms based on GMRES with incomplete block--matrix factorization preconditioning are robust and efficient. (Also cross-referenced as UMIACS-TR-98-58)
Lyapunov Inverse Iteration for Computing a few Rightmost Eigenvalues of Large Generalized Eigenvalue Problems
(2012-04-20) Elman, Howard C.; Wu, Minghao
In linear stability analysis of a large-scale dynamical system, we need to compute the rightmost eigenvalue(s) for a series of large generalized eigenvalue problems. Existing iterative eigenvalue solvers are not robust when no estimate of the rightmost eigenvalue(s) is available. In this study, we show that such an estimate can be obtained from Lyapunov inverse iteration applied to a special eigenvalue problem of Lyapunov structure. We also show that Lyapunov inverse iteration will always converge in only two steps if the Lyapunov equation in the first step is solved accurately enough. Furthermore, we generalize the analysis to a deflated version of this Lyapunov eigenvalue problem and propose an algorithm that computes a few rightmost eigenvalues for the eigenvalue problems arising from linear stability analysis. Numerical experiments demonstrate the robustness of the algorithm.
Lyapunov Inverse Iteration for Identifying Hopf Bifurcations in Models of Incompressible Flow
(2011-03-07) Elman, Howard C.; Meerbergen, Karl; Spence, Alastair; Wu, Minghao
The identification of instability in large-scale dynamical systems caused by Hopf bifurcation is difficult because of the problem of identifying the rightmost pair of complex eigenvalues of large sparse generalized eigenvalue problems. A new method developed in [Meerbergen and Spence, SIAM J. Matrix Anal. Appl., 31 (2010), pp. 1982- 1999] avoids this computation, instead performing an inverse iteration for a certain set of real eigenvalues and that requires the solution of a large-scale Lyapunov equation at each iteration. In this study, we refine the Lyapunov inverse iteration method to make it more robust and efficient, and we examine its performance on challenging test problems arising from fluid dynamics. Various implementation issues are discussed, including the use of inexact inner iterations and the impact of the choice of iterative solution for the Lyapunov equations, and the effect of eigenvalue distribution on performance. Numerical experiments demonstrate the robustness of the algorithm.
Multigrid and Krylov Subspace Methods for the Discrete Stokes Equations}
(1998-10-15) Elman, Howard C.
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 factorizaton is more efficient than the other methods, but typically by no more than a factor of two. The conjugate residual method has the advantages of being both independent of iteration parameters and widely applicable. (Also cross-referenced as UMIACS-TR-94-76)
A Multigrid Method Enhanced by Krylov Subspace Iteration for Discrete Helmholtz Equations
(1999-08-27) Elman, Howard C.; Ernst, Oliver G.; O'Leary, Dianne P.
Standard multigrid algorithms have proven ineffective for the solution of discretizations of Helmholtz equations. In this work we modify the standard algorithm by adding GMRES iterations at coarse levels and as an outer iteration. We demonstrate the algorithm's effectiveness through theoretical analysis of a model problem and experimental results. In particular, we show that the combined use of GMRES as a smoother and outer iteration produces an algorithm whose performance depends relatively mildly on wave number and is robust for normalized wave numbers as large as two hundred. For fixed wave numbers, it displays grid-independent convergence rates and has costs proportional to number of unknowns. Also cross-referenced as UMIACS-TR-99-36
A Note on Conjugate Gradient Convergence
(1998-10-15) Naiman, Aaron E.; Babuska, Ivo M.; Elman, Howard C.
The one-dimensional discrete Poisson equation on a uniform grid with $n$ points produces a linear system of equations with a symmetric positive-definite coefficient matrix. Hence, the conjugate gradient method can be used, and standard analysis gives an upper bound of $O(n)$ on the number of iterations required for convergence. This paper introduces a systematically defined set of solutions dependent on a parameter $\beta$, and for several values of $\beta$, presents exact analytic expressions for the number of steps $k(\beta,\tau,n)$ needed to achieve accuracy $\tau$. The asymptotic behavior of these expressions has the form $O(n^{\alpha})$ as $n \to \infty$ and $O(\tau^{\gamma})$ as $\tau \to \infty$. In particular, two choices of $\beta$ corresponding to nonsmooth solutions give $\alpha=0$, i.e., iteration counts independent of $n$; this is in contrast to the standard bounds. The standard asymptotic convergence behavior, $\alpha=1$, is seen for a relatively smooth solution. Numerical examples illustrate and supplement the analysis. (Also cross-referenced as UMIACS-TR-95-86)
Perturbation of Eigenvalues of Preconditioned Navier-Stokes Operators
(1998-10-15) Elman, Howard C.
We study the sensitivity of algebraic eigenvalue problems associated with matrices arising from linearization and discretization of the steady-state Navier-Stokes equations. In particular, for several choices of Reconditioners applied to the system of discrete equations, we derive upper bounds on perturbations of eigenvalues as functions of the viscosity and discretization mesh size. The bounds suggest that the sensitivity of the eigenvalues is at worst linear in the inverse of the viscosity and quadratic in the inverse of the mesh size, and that scaling can be used to decrease the sensitivity in some cases. Experimental results supplement these results and confirm the relatively mild dependence on viscosity. They also indicate a dependence on the mesh size of magnitude smaller than the analysis suggests. (Also cross-referenced as UMIACS-TR-95-110)
Preconditioners for Saddle Point Problems Arising in Computational Fluid Dynamics
(2001-12-03) Elman, Howard C.
Discretization and linearization of the incompressible Navier-Stokes equations leads to linear algebraic systems in which the coefficient matrix has the form of a saddle point problem ( F B^T ) (u) = (f) (1) ( B 0 ) (p) (g) In this paper, we describe the development of efficient and general iterative solution algorithms for this class of problems. We review the case where (1) arises from the steady-state Stokes equations and show that solution methods such as the Uzawa algorithm lead naturally to a focus on the Schur complement operator BF^{-1}B^T together with efficient strategies of applying the action of F^{-1} to a vector. We then discuss the advantages of explicitly working with the coupled form of the block system (1). Using this point of view, we describe some new algorithms derived by developing efficient methods for the Schur complement systems arising from the Navier-Stokes equations, and we demonstrate their effectiveness for solving both steady-state and evolutionary problems. (Also referenced as UMIACS-TR-2001-88)

Browsing by Author "Elman, Howard C."

Results Per Page

Sort Options