Computer Science: Reflections on the Field, Reflections from the Field (2004)

In Chapter 2, the essay by Kleinberg and Papadimitriou discusses the universality of computers. To exploit this universality, we must specialize the computing engine to a specific task. This specialization ultimately takes the form of a program, but the program does not appear by magic—its creator needs to understand the task deeply. Further, a program must handle all variants of the task, not just those that the programmer can imagine. Usually we address this challenge by creating a model of the task’s problem domain. The model may be expressed in many different ways, but it can be understood in isolation from any particular program that implements it. These models may be designed to match physical reality, or they may express alternative sets of laws. In this way, simulation allows computer scientists—and others—to explain phenomena that may be difficult, dangerous, or impossible to explore in reality.

The use of digital computer simulations for scientific research is half a century old. Strogatz reflects on the explanatory power of Fermi’s early simulations and their profound effects. These early models of nonlinear systems gave better insight into the underlying phenomena than either the physical experiments (which proceeded too fast) or the math (which was too hard for the times).

Fedkiw describes the modern analog of Fermi’s experiments—the use of simulation to visualize complex phenomena such as turbulent flow. He shows how this mode of research complements the use of experiments and closed-form mathematics.

Steven Strogatz, Cornell University

NOTE: Originally published in the New York Times, this op-ed appeared on March 4, 2003. Reprinted by permission of the author.

Last week newspapers and magazines devoted tens of thousands of words to the 50th anniversary of the discovery of the chemical structure of DNA. While James D. Watson and Francis Crick certainly deserved a good party, there was no mention of another scientific feat that also turned 50 this year—one whose ramifications may ultimately turn out to be as profound as those of the double helix.

In 1953, Enrico Fermi and two of his colleagues at Los Alamos Scientific Laboratory, John Pasta and Stanislaw Ulam, invented the concept of a “computer experiment.” Suddenly the computer became a telescope for the mind, a way of exploring inaccessible processes like the collision of black holes or the frenzied dance of subatomic particles—phenomena that are too large or too fast to be visualized by traditional experiments, and too complex to be handled by pencil-and-paper mathematics. The computer experiment offered a third way of doing science. Over the past 50 years, it has helped scientists to see the invisible and imagine the inconceivable.

Fermi and his colleagues introduced this revolutionary approach to better understand entropy, the tendency of all systems to decay to states of ever greater disorder. To observe the predicted descent into chaos in unprecedented detail, Fermi and his team created a virtual world, a simulation taking place inside the circuits of an electronic behemoth known as Maniac, the most powerful supercomputer of its era. Their test problem involved a deliberately simplified model of a vibrating atomic lattice, consisting of 64 identical particles (representing atoms) linked end to end by springs (representing the chemical bonds between them).

This structure was akin to a guitar string, but with an unfamiliar feature: normally, a guitar string behaves “linearly”—pull it to the side and it pulls back, pull it twice as far and it pulls back twice as hard. Force and response are proportional. In the 300 years since Isaac Newton invented calculus, mathematicians and physicists had mastered the analysis of systems like that, where causes are strictly proportional to effects, and the whole is exactly equal to the sum of the parts.

But that’s not how the bonds between real atoms behave. Twice the stretch does not produce exactly twice the force. Fermi suspected that this

nonlinear character of chemical bonds might be the key to the inevitable increase of entropy. Unfortunately, it also made the mathematics impenetrable. A nonlinear system like this couldn’t be analyzed by breaking it into pieces. Indeed, that’s the hallmark of a nonlinear system: the parts don’t add up to the whole. Understanding a system like this defied all known methods. It was a mathematical monster.

Undaunted, Fermi and his collaborators plucked their virtual string and let Maniac grind away, calculating hundreds of simultaneous interactions, updating all the forces and positions, marching the virtual string forward in time in a series of slow-motion snapshots. They expected to see its shape degenerate into a random vibration, the musical counterpart of which would be a meaningless hiss, like static on the radio.

What the computer revealed was astonishing. Instead of a hiss, the string played an eerie tune, almost like music from an alien civilization. Starting from a pure tone, it progressively added a series of overtones, replacing one with another, gradually changing the timbre. Then it suddenly reversed direction, deleting overtones in the opposite sequence, before finally returning almost precisely to the original tone. Even creepier, it repeated this strange melody again and again, indefinitely, but always with subtle variations on the theme.

Fermi loved this result—he referred to it affectionately as a “little discovery.” He had never guessed that nonlinear systems could harbor such a penchant for order.

In the 50 years since this pioneering study, scientists and engineers have learned to harness nonlinear systems, making use of their capacity for self-organization. Lasers, now used everywhere from eye surgery to checkout scanners, rely on trillions of atoms emitting light waves in unison. Superconductors transmit electrical current without resistance, the byproduct of billions of pairs of electrons marching in lockstep. The resulting technology has spawned the world’s most sensitive detectors, used by doctors to pinpoint diseased tissues in the brains of epileptics without the need for invasive surgery, and by geologists to locate oil buried deep underground.

But perhaps the most important lesson of Fermi’s study is how feeble even the best minds are at grasping the dynamics of large, nonlinear systems. Faced with a thicket of interlocking feedback loops, where everything affects everything else, our familiar ways of thinking fall apart. To solve the most important problems of our time, we’re going to have to change the way we do science.

For example, cancer will not be cured by biologists working alone. Its solution will require a melding of both great discoveries of 1953. Many cancers, perhaps most of them, involve the derangement of biochemical networks that choreograph the activity of thousands of genes and pro-

teins. As Fermi and his colleagues taught us, a complex system like this can’t be understood merely by cataloging its parts and the rules governing their interactions. The nonlinear logic of cancer will be fathomed only through the collaborative efforts of molecular biologists—the heirs to Dr. Watson and Dr. Crick—and mathematicians who specialize in complex systems, the heirs to Fermi, Pasta, and Ulam.

Can such an alliance take place? Well, it can if scientists embrace the example set by an unstoppable 86-year-old who, following his co-discovery of the double helix, became increasingly interested in computer simulations of complex systems in the brain.

Happy anniversary, Dr. Crick. And a toast to the memory of Enrico Fermi.

Ronald Fedkiw, Stanford University

Have you ever sat in a movie theater with a box of popcorn and a soft drink watching a movie like The Perfect Storm and wondered where Hollywood found a cameraman brave enough to operate a camera under such dangerous conditions? Well, that particular cameraman was sitting in a small office north of San Francisco at a company called Industrial Light and Magic, which was founded in 1975 by George Lucas of Star Wars fame. There, a computer graphics specialist, our “cameraman,” safely operated the camera with the mouse attached to his computer. In fact, the camera was little more than a computer program that calculated the relative positions of boats and waves in order to add captivating imagery to a tale about fishermen struggling with treacherous waves on rough seas. Hollywood films are created to captivate and entertain, and thus they frequently contain exciting scenes with natural phenomena such as water waves, smoke, tornados, or even lava erupting from volcanoes. Obviously, we’re not going to put George Clooney on a boat in the middle of the Atlantic Ocean and subsequently pulverize it with waves until it sinks. In fact, we’re not going to put anyone on a boat in such a treacherous storm, assuming we could even find such a storm in the first place. It turns out to be a lot easier to make waves out of math than out of water.

For centuries, applied mathematicians and physicists have derived mathematical equations describing the behavior of a variety of substances including water waves in the ocean and the metal hull of a ship (Box 3.1). These equations are quite complicated and can be solved only in special situations or with the aid of simplifying assumptions that usually rule out problems of practical interest. However, in the last half century, the advent of computer technology has led to a revolution in the study of these types of equations. Using approximation theory, numerical analysts have devised a number of algorithms that enable one to program computers to estimate solutions to many of the equations governing the physical world to any desired accuracy. Moreover, these numerical solutions provide useful information for practical problems of interest to both scientists and engineers.

Solving such problems falls into an area of research referred to as “scientific computing.” Scientific computing has become the third branch of research in many engineering departments, joining theory and experiment as classical approaches to obtaining information about the world around us. While scientific computing has classically been applied to physical problems such as those faced in mechanical, aerospace, and struc-

tural engineering, the fastest growing application areas may currently be in electrical and computer engineering and in biology and medicine. More broadly, scientific computing encompasses both computational science and computational mathematics. We emphasize that mathematics is the fundamental language for problem solving, and when confronted with a problem most scientific researchers attempt to formulate a mathematical description of that problem. Once the mathematical description exists, the problem is potentially solvable on a computer using either existing algorithmic techniques or newly devised methods. Thus, scientific computing has become a fundamental requirement for solving problems in signal processing, image analysis, robotics, computer vision, human computer interaction, and computer graphics.

Returning to our cameraman and his goal of captivating us with dramatic sequences of waves pounding on a small ship, we now see that there are a lot of potential resources for creating “special effects” waves on the computer. In the particular case of The Perfect Storm, Industrial Light and Magic (ILM) had recently hired a professor of atmospheric

science (who specializes in scientific computing) to use his knowledge of oceans and waves, especially his algorithmic knowledge, to construct numerical solutions of large crashing waves on the ILM computers.

The Perfect Storm was not the first instance of scientific computing algorithms being used to make movies of boats and waves. A few years earlier, a Department of Defense (DOD)-oriented company called Areté Associates started a small spin-off company called Areté Entertainment to create computer graphics software that constructs artificial, but surprisingly realistic, ocean wave models. One can imagine that it could be particularly useful to be able to reproduce ocean wave models based on, for example, current wind speeds. If one could measure the wind and estimate what the ocean wave pattern should look like, this could be compared to the actual wave patterns in order to ascertain if there have been any recent outside influences on the wave patterns. That is, one could subtract the estimated wave pattern from the current wave pattern, thus revealing the wake of a large ship that passed through the water even some time ago. This becomes a lot more interesting when one realizes that underwater ships (submarines) can create surface disturbances as well. The implications for to the surveillance community are obvious. Using its knowledge of scientific computing algorithms for studying waves, Areté Entertainment developed computer graphics software to create ocean waves based on wind speeds. This software has won numerous awards and was used to create ocean waves in many films such as Water World and James Cameron’s Titanic. Another recent film, Cast Away, used similar technology to simulate a plane crashing into the ocean, stranding Tom Hanks on a deserted island.

As mentioned earlier, scientific computing algorithms can be used to simulate a variety of natural phenomena, including the water shown in Plates 1 and 2, and the smoke and fire shown in Plate 3. While these everyday events (smoke, fire, and water) are easy to relate to, similar numerical techniques can also be applied to events that the human eye will miss completely. For example, Plate 4 shows a computer simulation of a high-speed shock wave interacting with a bubble of helium. Scientific computing is having a growing impact in the fields of imaging and data analysis as well. This is important, for example, in medicine, biology, and even surveillance. For example, Plate 5 shows several data points obtained from MRI imaging of a rat’s brain along with a three-dimensional geometric reconstruction of the rat brain obtained by using numerical methods on a computer.

Possibly the most exciting area for future applications of scientific computing is the computer simulation and study of humans themselves. Researchers in biomechanics and medicine are currently working to write down mathematical equations and numerical models that describe most

of the human body from the cardiovascular system to muscles, bones, and organs. As these equations and models are formulated, there is an ever-growing need for new computational algorithms that can be used for the computer simulation of biological structures. Plate 6 shows a sample computer simulation of a skeleton running. Geometric models were used for the bones, mathematical equations were used to describe the limited motion allowed for by the connective tissue in joints, and special models for soft tissue were used to simulate the muscles (the red regions in Plate 6 represent the biceps muscles). Plate 7 shows 30 muscles of the upper limb represented as a tetrahedral mesh ready for finite element simulation. Computer simulation of humans is of interest to a wide variety of commercial industries as well. The entertainment industry would like to simulate virtual actors, the textile industry would like to simulate both runway models and everyday customers trying on virtual clothing, and so on. See Plate 8 for a computer simulation of a piece of draped cloth.

As both everyday personal computers and national laboratory supercomputers continue to increase in speed and as better algorithms are developed, the size, complexity, and realism of the problems that can be simulated on these computers increase as well. In addition, as researchers branch out into new and exciting research areas, they will formulate mathematical descriptions of their problems that are subsequently amenable to computer simulation. The future is bright in a number of research areas, and where researchers go, math and computer algorithms are sure to follow.