11.21.06
Posted in Computational Fluid Dynamics, Dissertation Research, Tex, LaTeX, and ConTeXt at 2:04 pm by Brooks
The 2006 annual conference of the American Physical Society’s Division of Fluid Dynamics just ended a few hours ago, here in Tampa. As usual, I’ve put the slides from my talk up on dpdx.net/research/papers. Direct links: abstract, Slides in PDF form, and ConTeXt source for the slides. It’s a fun conference; unlike most, the talks are only ten minutes long, so it’s pretty easy to hit information overload by the end.
I’ll post some more about these results once I get home. I’ve been working pretty hard on this for the last few months, and haven’t had time to post much about it here, but things should be a bit less hectic soon. My code is finally producing results (luckily just in time for the conference!), and the results are considerably more dramatic than I was expecting — a pleasant surprise!
Permalink
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
05.23.06
Posted in Thermodynamics at 7:12 pm by Brooks
I recently came across a mention of yet another inventor who supposedly has built a car engine that runs on water. The claim is in a video which doesn’t play on my computer, so I don’t know much for details of what he’s actually claiming. But even without watching the video, I can say with almost absolute certainty that this inventor hasn’t built a car powered by water.
I’m sure of this, even though I have no idea how this engine is supposed to work. Why? It’s a matter of applied thermodynamics.
First, imagine that the engine is in a black box. We can’t see into the black box, so it could be any possible type of engine that has been or will be invented. All we can measure is what goes in and out.
What goes in is basically just the “fuel”: room-temperature water. There might be some air with it, too. There are a couple of things that come out: The exhaust from the engine, and the power from the engine — maybe in the form of a shaft coming out of the engine that it’s turning, or something.
According to the First and Second Laws of Thermodynamics, available energy cannot be created, though it can be destroyed by turning available energy into unavailable energy. If we apply that principle to the box with the engine in it, it’s pretty clear that the sum of the available energy that goes into the box and what is in it when we start running it has to be at least as much as the sum of what comes out and what is in it when we finish.
Now, this is an “engine”, not a storage system; it’s not allowed to be running off some sort of hidden internal energy supply that’s also contained in the box. So, if the engine isn’t cheating, the amount of available energy in the box when we start will be the same as the amount when we finish. Thus, we conclude: what goes in must be at least as much as what goes out.
So, look at the available energy that’s in that exhaust. Whatever the exhaust is, it has to contain the same hydrogen and oxygen atoms that came in with the water, along with the atoms that came in with the air. It could hot steam — which has higher available energy than the water that came in. It could be some other compounds of hydrogen and oxygen and stuff in the air — and all of those have higher available energy than water and air do. It could be a cool wet fog, which has slightly higher energy than the water. It could even be ice, but even that has higher available energy than room-temperature water. The best possible case is that it could be room temperature water and air just like what came in, and have the same available energy.
That means that the available energy that comes out in the exhaust is at least as much than the available energy that goes in with the fuel and air. And there’s supposedly even more energy coming out via the power from the engine — thus, the output is claimed to be higher than the input.
This is obviously a contradiction. We just found that, by the laws of thermodynamics, we can’t have more energy coming out in the exhaust and power shaft than what came in with the fuel.
Thus, the engine is impossible.
Permalink
Posted in Programming and People at 1:25 pm by Brooks
Jeff Atwood makes the point that although experts generally don’t follow recipes (such as “best practices”) literally, the recipes are still valuable:
The idea that a recipe (eg, a best practice, a methodology, or a maturity model) is completely worthless is just as wrongheaded as the idea that everything should be based on a strict recipe. In other words, even an expert chef may occasionally find it helpful to refer to a recipe card.
There’s no reason these two models can’t coexist. You should always start with the common denominator recipe, of course, but you may want to provide some alternative guidelines and ideas for those cooks who have outgrown traditional recipes, too.
I strongly agree with his general point, but I think that “guidelines and ideas” are the wrong sort of thing to include.
To take the metaphor literally, for some things, I’m a level 4 cook. (Not necessarily an especially good one — it’s worth noting that these levels are not always parallel to the quality of the output!) A particular example would be some coleslaw I made a couple of weeks ago, when I found myself in an ill-stocked kitchen with a cabbage, an empty stomach, and the Joy of Cooking.
The Joy of Cooking is a pretty good cookbook for this sort of thing, as it turns out. It has a half-page discussion of what coleslaw is, without any recipes at all. It turns out that pretty much the only common factor in slaw is that it has cabbage in it. Everything else is variable. (This was an important point; we had no mayonaisse, and the person I was cooking with insisted that coleslaw has to have mayo.) It went on to describe, in loose terms, some of the common varieties. I skimmed through those, and then went on to look at the actual recipes. The standard recipe format is well-optimized for this sort of thing; there’s a list of ingredients at the top, separate from the instructions, making it very easy to skim to pull out specific bits of data such as the ratio of sugar to vinegar in a sugar-vinegar slaw.
After looking through the cookbook, I’d gleaned the following information: sugar and vinegar are a perfectly sufficient base for a slaw dressing, and it’s common to have them in X ratio, Y is a typical amount of salt, and Z, W, Q, and a dozen other things are some ideas for spices to put it.
Those, you may object, look exactly like “guidelines and ideas”. So, why am I objecting to including guidelines and ideas for experts in the recipe? The same reason that specific instructions are wrong for experts: They are processed information, and the definition of “expert” in this context is someone who does their own information processing. In my case, when I read the recipes, I was mining them for bits of information. Any processing that complicates that information-mining is a detriment, not a benefit.
And so, when writing recipes to be useful beyond basic instructions, the thing to include is facts. Not a guideline of “this squash should be cooked for 20 minutes”, but the fact of “if you cook this squash for more than 25 minutes it will be mushy and begin to lose flavor.” Not the idea of, “You could use peaches in this,” but the fact of “Peaches are also common in this.” The guidelines and ideas are certainly useful because they contain facts, but the parts that make them “guidelines” and “ideas” rather than bare facts rarely are. Often the process of distilling the fact into a guideline or idea loses useful information, too; suppose I wanted mushy squash, or wanted an uncommon alteration?
Permalink
« Previous Page — « Previous entries « Previous Page · Next Page » Next entries » — Next Page »