Springer Series in Computational Physics Editors w. Beiglbock H. Cabannes H. B. Keller 1. Killeen S. A. Orszag F ini te-Difference Techniques for Vectorized Fluid Dynamics Calculations Edited by David L. Book With Contributions by Jay P. Boris Martin J. Fritts Rangaro V. Madala B. Edward McDonald Niels K. Winsor Steven T. Zalesak With 60 Illustrations Springer-Verlag New Yark Heidelberg Berlin David L. Book Naval Research Laboratory Washington, DC 20375 USA Editors w. Beiglbock H. Cabannes Institut fiir Angewandte Mathematik Mecanique Theoretique Universitat Heidelberg Universite Pierre et Marie Curie D-6900 Heidelberg I F-75005 Paris Federal Republic of Germany France H. B. Keller J. Killeen California Institute of Technology Lawrence Livermore Laboratory Pasadena, CA 91125 Livermore, CA 94551 USA USA S. A. Orszag Massachusetts Institute of Technology Cambridge, MA 02139 USA Library of Congress Cataloging in Publication Data Main entry under title: Finite-difference techniques for vectorized fluid dynamics calculations. (Springer series in computational physics) Bibliography: p. Includes index. I. Fluid dynamics. 2. Finite differences. I. Book, D. L. (David Lincoln), 1939- II. Series. TA357.F49 532'.05'0151562 81-5282 AACR2 All rights reserved. No part of this book may be translated or reproduced in any form without written permission form Springer-Verlag, 175 Fifth Avenue, New York, New York 10010, U.SA. © 1981 by Springer-Verlag New York Inc. Softcover reprint of the hardcover 1st edition 1981 ISBN-13: 978-3-642-86717-0 e-ISBN-13: 978-3-642-86715-6 DOl: 10.1007/978-3-642-86715-6 Summary This book describes several finite-difference techniques developed recently for the numerical solution of fluid equations. Both convective (hyperbolic) equations and elliptic equations (of Poisson's type) are discussed. The em phasis is on methods developed and in use at the Naval Research Laboratory, although brief descriptions of competitive and kindred techniques are included as background material. This book is intended for specialists in computational fluid dynamics and related subjects. It includes examples, applications and source listings of program modules in Fortran embodying the methods. Contents Introduction 1 (D. L. Book) 2 Computational Techniques for Solution of Convective Equations 5 (D. L. Book and J. P. Boris) 2.1 Importance of Convective Equations 5 2.2 Requirements for Convective Equation Algorithms 7 2.3 Quasiparticle Methods 10 2.4 Characteristic Methods 13 2.5 Finite-Difference Methods 15 2.6 Finite-Element Methods 20 2.7 Spectral Methods 23 3 Flux-Corrected Transport 29 (D. L. Book, J. P. Boris, and S. T. Zalesak) 3.1 Improvements in Eulerian Finite-Difference Algorithms 29 3.2 ETBFCT: A Fully Vectorized FCT Module 33 3.3 Multidimensional FCT 41 4 Efficient Time Integration Schemes for Atmosphere and Ocean Models 56 (R. V. Madala) 4.1 Introduction 56 4.2 Time Integration Schemes for Barotropic Models 58 4.3 Time Integration Schemes for Baroclinic Models 63 4.4 Extension to Ocean Models 70 David L. Book, Jay P. Boris, and Martin J. Fritts are from the Laboratory for Computational Physics, Naval Research Laboratory, Washington, D.C. B. Edward McDonald, Rangaro V. Madala, Niels K. Winsor, and Steven T. Zalesak are from the Plasma Physics Division, Naval Research Laboratory, Washington, D.C. viii Contents 5 A One-Dimensional Lagrangian Code for Nearly Incompressible Flow 75 (J. P. Boris) 5.1 Difficulties Encountered in Lagrangian Methods 75 5.2 Adaptive Gridding in a Lagrangian Calculation 78 5.3 The Algorithm and Structure of ADINC 82 5.4 Examples 91 6 Two-Dimensional Lagrangian Fluid Dynamics Using Triangular Grids 98 (M. J. Fritts) 6.1 Grid Distortion in Two Dimensions 98 6.2 Use of Reconnection to Eliminate Grid Distortion 100 6.3 Numerical Algorithms 105 6.4 Examples 112 7 Solution of Elliptic Equations 117 (R. V. Madala and B. E. McDonald) 7.1 Survey of Standard Techniques 117 7.2 A New Direct Solver: The Stabilized Error Vector Propagation Technique (SEVP) 123 7.3 Application of Chebychev Iteration to Non-Self-Adjoint Equations 135 8 Vectorization of Fluid Codes 152 (N. K. Winsor) 8.1 Speed in Hardware 153 8.2 Speed in Fortran 154 8.3 Problems with Causality 157 8.4 Examples 159 8.5 Summary of Parallelism Principles 162 Appendix A 164 Appendix B 171 Appendix C 177 Appendix D 191 Appendix E 200 References 209 Index 215 CHAPTER 1 Introduction In this book we describe a series of vectorizable computational techniques for solving hydrodynamics problems which have been developed at the Naval Research Laboratory in the past few years. We also relate them to older tech niques, discuss the applications for which they were developed, and describe their implementation on a particular vector machine, the NRL Texas Instru ments Advanced Scientific Computer (ASC). A tremendous range of physical phenomena are described by fluid equa tions. All four of the classical "elements"-earth, water, air, and fire behave, at least on some scales, as fluids. For this to be true, the features they share in common must be very simple, in spite of the variegation and superficial complexity we are accustomed to dealing with. This is indeed the case, and the present book deals chiefly with those central aspects. The mathematical description of fluid motion makes use of partial differen tial equations which propagate the fluid variables (density, velocity, pressure, etc.) in time. Most systems of such equations closely resemble one another in containing convective derivatives, expressing causality, conservation laws, and other properties, and in emphasizing the connectedness of the physical system. This latter property is often manifested in the appearance of a Poisson equation, which relates the pressure or velocity potential at a given point to the properties of the physical system as a whole. It is also displayed in the smooth (rather than discontinuous) variation through most of the system which we expect in fluids. However, many of the most important computa tional methods are intended to describe discontinuous behavior as well, such as that occurring in shocks, at combustion fronts, and on free surfaces and boundaries. Because we have emphasized the common features and generality of fluid behavior, most of the discussion in this book is theoretical, and the applica tions given are fairly simple. To apply the techniques to specific problems of interest, one or more of the following must be added to the basic (Navier Stokes) fluid equations: (i) more dimensions; (ii) more complicated geometry or boundary conditions; (iii) additional source, sink, or transport terms; (iv) more dependent variables; (v) an equation of state. For example, ideal mag netohydrodynamics requires the introduction of the magnetic field strength B and the Lorentz force; nonideal magneto hydrodynamics requires thermal 2 1 Introduction conduction, resistivity, and viscosity terms. Ocean internal waves require a buoyancy term and an eddy viscosity derived from a turbulence closure model. Chemically reactive flow requires the introduction of chemical vari ables, together with reaction rates, thermal conduction, and a turbulence model. Although most of the physics in any given problem is comprised in these added terms and conditions, computational practice shows that most of the difficult numerics problems are associated with the universal fluid features. If adequate care is devoted to developing accurate general numerical techniques for treating these, the resulting code invariably turns out to be robust, adaptable, and efficient. Hence the techniques described here encom pass a substantial portion of the effort needed to construct even the most elaborate numerical hydoodynamic model. We discuss techniques for both "incompressible" and "compressible" hydrodynamics, distinguished according to whether V· v = 0 or V· v ¥- o. In general we will be treating systems in which the fundamental variables are the mass density p, flow velocity v, and pressure p, and the equations are, respectively, those of continuity or advection; momentum transfer (Euler's equation); and an energy transport equation, equation of state, or the incom pressibility condition (see Section 2.1). It is assumed that the reader is familiar with the basic concepts of fluid dynamics, as expounded, for example, in Landau and Lifshitz (1959). No attempt will be made in this book to study in any detail the physics of fluids, or to explore the physical significance of the specialized problems which have been solved using the computational methods we present. Instead the em phasis is on the methods themselves. The reader is expected to be conversant in the standard numerical tech niques used for machine computation, as given in, e.g., Hamming (1962), and to have had experience in programming physics problems in Fortran or some other high-level language. Moreover, he should have some acquaintance with standard methods for computer solution of fluid problems, such as would result from having been involved in research in which fluid computations were carried out or from having read the descriptions given by, e.g., Richtmyer and Morton (1967) or Roache (1975). This book is intended, in other words, for the specialist in computational fluid dynamics or in one of the fields which makes use of fluid computational techniques: plasma, space, solar or astro physics, oceanology, meteorology, combustion, etc. As used in this book, "computational techniques" relate to the solution of equations derived from theoretical models, specifically models of hydro dynamic phenomena, and are to be distinguished from the use of computers in data reduction and analysis. Almost all of the techniques are aimed at solving nonlinear problems, which are inherently intractable by classical analytic techniques. Indeed, it is to their nonlinearity that fluid dynamic sys tems owe both their richness and their relative inaccessibility to computational treatment. 1 Introduction 3 Every theoretical model yields its predictions as solutions of the model equations. These may be as general as the three-dimensional Navier-Stokes equations, or as specific as an equation for the evolution of a particular type of wave (e.g., solitons) or a steady-state turbulent spectrum. Broadly speaking, there is a correlation between generality and the following difficulties: 1. Heavy machine requirements (storage and CP time); 2. need for highly sophisticated numerical methods; 3. limitations in precision and validity of long-term predictions; while specificity is associated with 1. theoretical problems in deriving and justifying the model; 2. stringent requirements on plausibility and agreement of predictions with experiment. In addition to determining the concrete predictions inherent in a particular set of assumptions, computer modeling can be used in an exploratory role, through "computer experiments." Where the precise set of assumptions or the values of the physical parameters are not clear, it is possible to generate a family of solutions to study trends and systematic properties. This form of computation is often referred to as "numerical simulation" and is contrasted with "numerical solution" of equations. This computer-experimentation point of view is the one adopted in the present work. We will be concerned principally with addressing the three kinds of difficulty listed above in connection with general models. The techniques we describe are designed to work in a production mode which emphasizes convenient data structures, high resolution (large computational meshes), detailed diagnostics, ruggedness, and, so far as is compatible with these, high execution rates. Most techniques which are inherently efficient show to good advantage on any machine and can be coded in nearly machine-independent form. In order to shave the last few percent (sometimes more than a few) from execution times, it is essential to make optimum use of the characteristics ofthe individual machine. The methods described in the text and the corresponding modules listed in the Appendices were developed for the NRL ASC. While some have been run on other machines with only small changes, optimization would entail a certain amount of recoding. The effort required varies, depending on both the machine and the routine involved. This book is organized as follows. In Chapter 2 six different classes of methods are compared and categorized in a framework provided by a set of six requirements which ought to be satisfied by an ideal continuity equation algorithm. The strengths and weaknesses of the different approaches are analyzed. Within this framework finite-difference techniques have particularly attractive properties. Hence most of the book is devoted to describing tech niques which correct, at least partially, the difficulties from which finite- 4 1 Introduction difference techniques suffer. Chapter 3 is devoted to flux-corrected transport (FCT) and related Eulerian solutions of the nonlinear continuity equation, which preserve the positivity property of the real equations and yet have relatively low numerical diffusion. Chapter 4 describes another kind of Eulerian code, designed to solve evolution equations describing the upper ocean and the atmosphere without the stringent time-step limitation imposed by an explicit treatment of surface waves and fast-moving internal gravity waves. Chapter 5 describes ADINC, a Lagrangian algorithm appropriate for describing nearly incompressible flow. In Chapter 6 we consider the Lagrangian techniques incorporated in the SPLISH code, which uses a recon nectable grid of triangles to allow accurate numerical solution of complicated flows with breaking waves and other severe nonlinearities. In Chapter 7 we briefly survey elliptic equation solvers, then describe two new techniques-one direct and one iterative-which have proven useful in fluid computations. Chapter 8 describes the rationale behind vectorization and summarizes techniques used to vectorize codes we have written incorporating the tech niques described in this book. From several of these codes we have extracted the core modules, Fortran listings of which are collected in the Appendices, along with directions for utilization. While this book is in no sense a treatise on the whole subject of computa tional fluid dynamics, it spans a wide range of topics. These were selected because each represents a definite advance in the state of the computational art. Although they have been described in specialist journals, each of the techniques is useful in a wide variety of applications. By collecting them in this fashion, relating them to each other and to previously existing techniques, and describing both theory and applications, we hope to bring about their exposure to a much wider audience than would otherwise be possible.