10.15.06
Posted in Computer Languages at 10:37 am by Brooks
IBM’s very first Fortran manual, Programmer’s Reference Manual: Fortran Automatic Coding System for the IBM 704, was dated October 15, 1956 — 50 years ago today. There are a couple of different scanned copies of it available online; bitsavers.org has one, and fortran.com has an autographed one.
There’s an old joke that, in a hundred years, programmers will be using a language that’s completely unrecognizable to modern users — and it will be called “Fortran”. There’s a lot of truth to that; in the first 50 years since this manual, Fortran has changed a lot. Among the signficant changes: subroutines, functions, explicit variable typing, character strings, block IF and DO loops, whole-array expressions, array segments, pointers, dynamic arrays, user-defined data types, pure functions, polymorphic data types, function pointers, generic functions, object-oriented capabilites, and (in the upcoming 2008 standard) arrays shared across multiple threads. Oh, and for those of you who remember the old version: lower-case letters and removal of the “statements must be in columns 7-72 of the line” restriction!
Permalink
10.06.06
Posted in Computational Fluid Dynamics at 9:45 pm by Brooks
This week’s big news in fluid flow simulation is Penny Smith’s existence proof for smooth solutions of the Navier-Stokes equations. (See also this in-depth explanation of the proof, and various other mentions of it here, here, and here.)
(Update: Regrettably, the article has been withdrawn due to a “serious flaw”. The piece described below is still interesting, however.)
The question that she’s solving is this: Given an infinite three-dimensional domain with arbitrary initial conditions, does a smooth solution to the Navier-Stokes equations (which are the equations describing the flow of water, air, or other fluids) exist on that domain for all future time? This problem was considered one of the most important open questions in mathematics by the Clay Institute, who are offering a one million dollar prize for a solution. It’s of some physical relevance directly, since if it’s not true then either there are cases where the Navier-Stokes equations don’t describe physical reality or else physical reality can behave in surprising ways. The greater significance, though, is that it and the methods that are used to prove it will be useful in further mathematical understanding of this particularly difficult problem.
Even though this is an existence proof and not a constructive one — which means that it proves that a solution exists, but does not provide an analytical method for finding one — there are some interesting construtive portions to the proof. Specifically, she shows that the solutions to the Navier-Stokes equations can be expressed as the limit of a set of hyperbolic equations. There is some interesting physical and computational relevance to how that works, which I thought would be interesting to more mathematically-inclined readers.
To start with, the Navier-Stokes equations are differential equations in four variables — pressure (p) and three directional components of velocity (ui, for i=1, 2, or 3). They look like this:
(Note that, in this notation, each term has an implicit sum over indices that appear twice in the term; thus, the second term in the first equation and the first term in the second equation are implicitly summed over
k. As
i appears only once in each term of the first equation, there isn’t an implicit summation over it, and thus that represents a set of three equations, one for each coordinate direction.)
There are some interesting features of this set of equations. First, there are four equations and four unknown variables, so it’s a closed set. However, if we start matching up variables with equations on a one-to-one basis, we find that the first three equations match up neatly with the three components of velocity, leaving the last for the pressure — even though it doesn’t actually have pressure in it (much less a time-derivative of pressure)!
What happens, then, is that at any point in time, the first three equations describe the time derivative of the velocity, as a function only of the local field at the current time (that is, they’re hyperbolic). This means that in these equations information travels across the domain at a finite rate, which is a very nice feature computationally; one can compute a solution at each grid point without needing to know the solution everywhere else. It’s also handy mathematically.
The fourth equation, though, messes all of this up. What it says is that the pressure needs to be chosen such that this velocity condition is satisfied everywhere. Physically speaking, if the velocities would be trying to compress a certain spot, the pressure there gets increased to counteract that, so it doesn’t compress. This isn’t a local constraint, because it’s the derivative of the pressure that affects the velocities, and so a change in pressure in one place causes immediate changes throughout the whole domain — essentially, the speed of information transfer is infinite. In a computational simulation, the vast bulk of the time is usually spent taking care of the pressure.
So, how does Penny Smith’s analysis approximate this by a set of hyperbolic equations? There are two parts to that. The first part is that she needs a set of first-order equations for her analysis, and this contains a second order term. Fixing that is straightforward, we simply introduce more variables, and a mathematical identity. The (nine) new variables are the components of a “viscous stress tensor”, defined as:
(That’s nine equations, one for each combination of
i and
k). (Also, for the fluid mechanicians: it’s not quite the viscous stress tensor, I know; there are terms left out that sum to zero.) Then, the first three equations can be rewritten as
This gives a set of thirteen first-order differential equations and thirteen unknowns.Now, for the hyperbolic part. I’ll start with the pressure equation, since that’s the one that has historically been a problem, but in this first-order formulation the stress-tensor equations also are not hyperbolic. To be a hyperbolic equation, this needs to have a time derivative of pressure in it. So, suppose we just add one, multiplied by an arbitrary constant (denoted ?):
If ? is zero, this is the same as the initial equation, but if ? is greater than zero, this and the other three initial equations form a hyperbolic set. Thus, if we take a set of ? values that converge to a limit of zero, we get a set of solutions of hyperbolic equations which converge to a solution of the initial non-hyperbolic equations.It turns out that this has physical significance — what happens is that, if the velocities are trying to compress a certain spot, the pressure there still goes up, but not immediately, and so things do get compressed but only a limited amount. This is exactly what happens in “compressible” flows, such as air flows at high speed, so it’s a phsyically meaningful problem. In effect, there’s a “relaxation time” — a finite amount of time that it takes for the pressure to respond to a given input; this relaxation time is proportional to ?, and so what we’ve done is taken an equation with a zero relaxation time and given it a finite nonzero one.
This suggests a rather simple computational method: solve the problem with a small but non-zero value of ?, and thereby obtain a solution that’s close to the desired one. This used to be a fairly common method, because hyperbolic problems are relatively easy to solve, and it’s called “artificial compressiblity”. It works reasonably well in some cases, although as ? gets closer to zero, the rates of information transfer around the domain get faster, and so the equations take more work to solve computationally. And, of course, if you use a larger ?, the rates of information transfer get slower, and so the solutions aren’t as close to the real solution. But it’s reasonably good for some problems.
Now, in Penny Smith’s case with everything in first-order equations, there are some additional equations that aren’t in hyperbolic form, so she does exactly the same thing to those equations, adding a time-derivative term to those as well:
In the computational situation, this isn’t necessary; the stress tensor can be calculatated from local data and doesn’t have problems of global dependencies, so there’s no need to add the nonzero relaxation time to these equations. However, it’s important for simplifying the mathematical analysis. (And it’s an interesting question whether it might be useful in computations as well; there are some advantages to working with things that are mathematically simpler.)So, that’s pretty much what’s going on with that part of the analysis. From there, the proof then goes off into two additional — and far more complicated — parts. First, there’s a proof that smooth solutions to these sets of first-order hyperbolic equations exist for all time, given a sufficiently smooth set of starting conditions. Then, there’s a reference to a proof from 25 years ago by John Heywood, which showed that smooth solutions to the Navier-Stokes equations exist at least for a finite time, and some analysis that shows that his solutions can be used to provide appropriate starting conditions for the first half of the proof. And, finally, there’s a small bit to tie everything together and show that the fact that the hyperbolic equations have smooth solutions means that their limit is also smooth. QED.
(Note: Equations in this article were typeset with MimeTeX.)
Permalink