Proposal to the NCSA for Virtual Environment and Power Challenge Cluster Resources,

based on a funded Proposal to the UIUC Research Board:

George K. Francis , 10 May 1996

OBJECTIVES

The objectives of this project are to design and execute a series of mathematical experiments in parallel and distributed supercomputing and to exhibit the results as real-time interactive CAVE/console animations (RTICA). These will all work on the IWALL and the IDESK as well. Three prototypes for this new kind of mathematical software were built last year by my illiView team in the Virtual Environments Group of the NCSA and our extramural collaborators. These constituted our Laterna matheMagica exhibit at the 1995 joint IEEE-ACM Supercomputing Conference, SC95. Ours was one of only four mathematical entries among over 68 juried projects in science and technology on the Global Information Infrastructure (GII) Testbeds. Given that we have the unique opportunity at the NCSA to work with the most advanced and powerful new supercomputing architectures, there is an obligation to learn how to use such instruments in experimental mathematics, and make this knowledge available to the mathematical community as a whole.

Specifically, we intend complete and integrate the remaining, more difficult parts of the Minimax Sphere Eversion project begun last year. These parts were not needed for the ``proof of concept'' we demonstrated in the Laterna matheMagica at Supercomputing'95. However, they are needed to bring the study to a satisfactory scientific conclusion in the form of these five products: In the remainder of this narrative we shall describe the Minimax Sphere Eversion Project, indicating which parts are complete and which are proposed. In particular, we shall outline why and how we intend to use parallel, distributed supercomputing to achieve our ends, and what we mean by these terms in the present context. This discussion will reveal the need to acquire a much deeper and effective understanding of geometrical supercomputing. To acquire this knowledge we intend to address some related, but conceptually simpler problems in simulating certain non-linear systems of partial and ordinary differential equations.

For this purpose, the skill, patience and enthusiasm of graduate research assistants are needed. In particular, I am counting on the assistance of one senior and one junior member of my illiView team, both of whom have made essential contributions to my research program. Both are available this coming summer and one would be free to continue half-time through the academic year. Their first task will be to join me in an effort to gain some solid proficiency in parallel, distributed and scalable supercomputing.

DEFINITIONS

For our purposes, parallel shall mean that the main part of the program spawns a number of subsidiary processes all of which have access to the same shared memory. Thus when the CAVE Onyx animates three walls, monitors the tracking system, and initiates the communication processes with one or more remote supercomputers there is one shared memory, and at least 4 processors for all 6 processes. This is an instance of coarse grained parallelism. When a second Onyx is enlisted to manage the fourth wall, and two SGI Indys are contacted to run two soundservers (for stereo, localization and reverberating sound) then this is an example o f locally distributed computing. If the real-time data, generated by one or more supercomputers at a distant location, is conducted by the Internet or over an experimental asynchronous transmission mode (ATM), it is globally distributed computing. This is what we did for the Laterna matheMagica at SC95.

Fine grained parallelism for us shall mean that nearly identical subprocesses are parcelled out to as many processors as are available on the current shared memory Power Challenge. Such a program is scalable if it can run many processes on few processors efficiently, if much more slowly, than on many processors; and whose performance continues to improve as more processors become available.

For us the term distributed shall mean that several independent computers are working simultaneously with copies of the same code, and communicate the results by whatever networking is available ( e.g. common Ethernet for development and debugging.) Implicit here is that the mother program is capable of integrating the contributions in real-time and interactively.

Our performance criterion is to maintain, at all times, animation speed on the console and in the CAVE.

SPHERE EVERSIONS

To evert a sphere is to turn it inside out by means of a continuous deformation, a regular homotopy which allows the surface to pass through itself, but forbids more serious singularities where the curvature becomes locally infinite. There have been many eversions since S. Smale proved the possibility of this phenomenon forty years ago. The extraordinary difficulty in visualizing an explicit eversion has made it an effective challenge for a succession of both mathematical and graphical innovations.

Our sphere eversion differs from all previous ones in that it proceeds automatically through an optimization procedure. We use the Surface Evolver, a computer program by Ken Brakke for solving variational problems like finding the shape of soap films and exploring the behavior of elastic foams. We need only to specify the starting point and a general strategy of energy minimization to the program. The starting point is one of Bernard Morin's halfway models which is an immersed sphere with four-fold orientation reversing rotational symmetry. This is also an unstable critical point of the Willmore energy. This is the integral of the squared mean curvature of the surface, or, more precisely, a discrete approximation of it. The regular homotopy is automatically generated by flowing down the Willmore gradient from the halfway model to the round sphere. The latter is an absolute minimum of the Willmore energy. Actually, the strategy is considerably more sophisticated. Steps using a conjugate gradient method of descent are alternated with steps that compute the largest negative eigenvector of the (discrete approximation) of the Hessian to move along.

The resulting minimax eversion is optimal in that it requires the least bending at any stage and again, in that it has the least number of ``catastrophes'' in the regular homotopy. As in all good experiments, we did not know a priori that the Evolver would be successful in producing a sphere eversion. To our great pleasure, it not only succeeded, but also produced an eversion which turned out to be among those designed by Bernard Morin three decades earlier. That nature should choose, as an optimal geometry for the eversion, the artifice envisioned by a blind topologist is pure serendipity.

MORPHING

Successive stages in the evolution of a triangulated surface by the Evolver do not, in general, have the same number of vertices or facets. For the Minimax Sphere Eversion, the algorithm may subdivide triangles if they become too large, or retriangulate the four vertices of two adjacent triangles if that brings them closer to being equilateral. Facets that become sufficiently degenerate may be culled from the list.

Thus, the customary way of improving the smoothness of an animation of the evolution is to calculate additional evolutionary steps based on smaller variations. This may, however, prove too `costly', and spoil the goal of real-time animation. An alternative is to devise spatial interpolations which may be considered a type of 3-D morphing. The general 3-D morphing problem between two arbitrary, triangulated surfaces is not tractable in real-time. However, the evolver does keep track of its modifications of the triangulations, and it may prove that incorporating this information into a morphing algorithm is sufficiently efficient to maintain animation speed. Or, for the purposes of a very smooth animation for a video, this method may consume fewer resources than the Evolver slowed down by a tiny stepsize. The solution of this problem would be generally useful for all similar surface deformation processes which do not use a global parametrization of the vertices of triangulated surfaces.

SYMMETRY

Symmetry is frequently an essential part in the solution of a geometrical problem. Even when it is not, symmetric solutions to differential equations and to optimizing evolutions of structures not only reduce computation but improve the visual perception of the represention. Both aspects occurs in the Minimax Sphere Eversion. But for the Evolver, enforcing symmetries increases the load imposed by the constraints. The discrete, rotational symmetries have largely been solved for the Evolver. There is however a second, continuous group of conformal transformations, the 3-dimensional Moebius transforms, which preserve the Willmore energy. Finally, there is the infinite dimensional group of reparametrizations (the gauge transformations for this problem) which account for much of the useless thrashing and drifting of the surface as it moves down the Willmore energy gradient.

All these improvements must not, however, slow down the evolution below animation speed because the experimentor has to interact with the evolution at times. It is necessary to find an appropriate mixture of first-order and second-order energy minimization by hand, at least until the optimal strategy has been identified and encoded.

Underlying all of these technical problems is a more serious one which surfaced during the initial experiments. The author of the Evolver, Ken Brakke, is an extramural collaborator of this project. He has done the best he can to parallelize the Evolver, but there remain a number of steps which are serial by their very nature, such as the calculation of the largest negative eigenvalue of the Hessian of the Willmore energy. Even the parallel portions of the evolution appear to reach scalability limits around 7-8 processors\footnote{That is on a Power Challenge. On the Convex Exemplar or on the non-shared memory IBM SSPs the situation was much worse.} due to dataflow problems. There are alternative algorithms which are not used by the Evolver and which could be amenable to fine-grained parallelisation. These have been dormant since their initial development and serial implementation on an Iris 4D/25GT by my PhD student Byoung Kim a decade ago.

In order to develop the intuition and experience for the parallelizing problem we intend to subject two somewhat simpler problems to the same design. Each of these have considerable independent interest for experimental mathematics. We will report our results this summer at the International Summer School on Scientific and Mathematical Visualization, Freiburg, September 1996.

NONLINEAR WAVE MECHANICS

Early on in my learning how to use graphics computers to simulate dynamical systems a colleague, the late Lee Rubel, stopped by the Apple Lab and elaborated on a curious situation in experimental mathematics. Whereas the linearized, 1-dimensional wave equation,
utt= k uxx
is solved exactly in every college differential equations course, the non-linear equation,
utt=k uxx/(1+ux2)3/2
is suffiently intractable in the abstract to have cost him an erroneous paper. Yet this equation expresses the natural condition that the restoring force on a violin string is proportional to its curvature. Now, we may finally have the computing power to attack this problem in a succession of dimensional generalizations and conduct the experiments Rubel envisioned. The 1 and 2 dimensional cases are straight forward and will enable us to develop the expertise at fine-grained parallel programming. The 3 dimensional case may already present unforseen difficulties, at least for real-time interactive purposes.

We are, however, interested in the 4 dimensional case for the following reason. It is a classical result that the solutions to the even-dimensional linear wave equation behave very differently from those we are familiar with in 3 dimensions. For the example, the speed of propagation is dependent on the pitch in even dimensions. It would be interesting to see experimentally what the situation is when the force of displacement is proportional to a suitable interpretation of curvature.

Thus, a subsidiary project which initially serves as a foil for learning geometrical parallel supercomputing, leads to a good research project. We hope to interest Prof. Robert Jerrard in a collaboration.

SYMPLECTIC GEOMETRY

Another colleague, Prof. Eugene Lerman, suggests the following problem in mechanics. Consider two spinning tops, linked together by an idealization of the universal joint\footnote{As in the automotive powertrain of yesteryear.}. It is not known, for example, whether the dynamical system associated with this physical problem is integrable, or whether it is chaotic. Considerable theoretical progress could be made if one had a real-time interactive simulation of this system. With Prof. Lerman's collaboration, we could build an RTICA. Since it is a ``fresh problem'' we will code a fine-grained parallelisation into the powerShell prototype right from the start. This will require good collaboration between the graduate student programmer and the specialist in symplectic geometry. %I expect to serve as facilitator here.

ADDITIONAL BACKGROUND

From the beginning of the NCSA, I have been working on the realization of an idea of using computer graphics not just to create mathematically significant illustrations, but to simulate processes such as populate the phase space of dynamical systems, cellular automata, and homotopies of curves and surfaces in 3 and 4 spatial dimensions.

For the Etruscan Venus Project, which was a multiyear collaboration with computer artists Donna Cox and Ellen Sandor and graphics programmer Ray Idaszak, I taught myself C, Unix and the SGI graphics library. This permitted us to translate complex geometrical abstractions into vivid light sculptures (Phscolograms) and visually stunning videotapes.

The SGI donation of Iris graphics computers (REL) to the NCSA, and the regular opportunity to teach both graduate and undergraduate courses in the REL, led to the illiView collection of real-time interactive computer animations (RTICA). The `C' in the acronym acquired new interpretations with the NCSA installation of the CAVE, which is the virtual reality theater invented by the faculty and students at the Electronic Visualization Laboratory (EVL) at our sister campus in Chicago.

In preparation for a major exhibit at SIGGRAPH'94 using 3 CAVEs, the illiView team created a style of programming, the illiShell which permits very rapid development at the console of an Iris of programs that recompile efficiently for the CAVE. The year I used the illiShell in my REL courses, most of the projects in my graduate course and half of the projects in my undergraduate course were presented in the CAVE at the end of the semester.

In preparation for Supercomputing'95 the following year the SGI Power Challenge parallel supercomputers became available for use with the CAVE. Once again, the illiView team moved quickly and was able to demonstrate the usefulness of remote supercomputing in descriptive topology. The generally useful byproduct of this effort was the powerShell This is a tightly articulated pair of model programs designed to be easily customized for any particular application. One part of the pShell is a scalable, distributed `calculator' on a parallel computer such as the Power Challenge. The other is the `viewer' powering the CAVE from an Onyx.

OTHER PROJECTS

There are a number of smaller projects, most of which we should be able to complete during the summer.

1. Adaptation of the illiConic tutorial to run in the CAVE, IWALL and IDESK. This was our very successful instrument for a teachers-workshop at the NCSA in 1993.

2. The CAVE/Console template RTICA, illiShell, has successfully been implemented in C++. This will be polished and documented for general distribution. An OpenGL version is planned, if we can get the CAVE libraries to cooperate.

3. The class notes and tutorials for my annual fall graduate course in Geometrical Computer Graphics in REL will be revised to reflect the current interest in the OpenGL graphics library, and the C++ structural paradigm.

4. In addition, I have also committed myself to develop a new course UIMATH.grafiXlab This course will be offered for the first time fall 1996, and it will be taught by visiting Prof. J. Sullivan, who is my chief collaborator on the illiVert project. The course is an introduction to the use of advanced computer graphics packages\footnote{Geomview from the Geometry Center (University of Minnesota), Meshview (Indiana University), Oorange (Technical University of Berlin) and our own illiView (UIUC) developed at the NCSA.} in mathematics. The course has been proposed for inclusion as a Computational Science and Engineering (CSE) option in Mathematics. It is also part of a proposal for an NSF Mathematical Sciences/Group Infrastructure Grant (GIG) titled ``Mathematical Computation Program'', by John W. Gray, PI, submitted 16 January 1996. It is important that the RA who helps set up this software also be available for consulting in the fall when I teach the course.

PUBLICATION LIST 7/94 to 3/96.

Andrew Hanson, Tamara Munzner, and George Francis. Interactive methods for visualizable geometry. Computer, IEEE Computer Society, V.27, N.7 (1994), 73-83.

George Francis and Louis Kauffman. Air on the Dirac Strings. In W. Abikoff, J. Birman, and K. Kuiken, eds. The Mathematical Legacy of Wilhelm Magnus. Contemporary Mathematics, V.169, Amer. Math. Soc., Providence, RI. 1994.

John Hart, George Francis, Louis Kauffman. Visualizing quaternion rotation. Assoc. Comp. Mach., Transactions on Graphics, V.13, N.3, (1994), 256-276.

George Francis. The Hypergraphics Honors Seminar at Illinois. In D. Thomas, ed.. Scientific Visualization in Mathematics and Science Teaching. Assoc. Adv. Comp. in Educ., Charlottville, VA, 1995.

Randy Hudson, Charlie Gunn, George Francis, Daniel Sandin, Thomas DeFanti. Mathenautics: Using VR to visit 3-D manifolds. Symposium on Interactive 3D Graphics, April 1995.

George Francis, John M. Sullivan, Robert B. Kusner, Kenneth A. Brakke, Chris Hartman and Glenn Chappell. The Minimax Sphere Eversion. In Konrad Polthier and Hans-Christian Hege, eds., Mathematics and Visualization. Springer Verlag, Berlin, 1996.

Juried presentations at conferences:

Dan Sandin, Lou Kauffman, George Francis, Joanna Mason, Milana Huang. Getting Physical in 4-Dimensions. Virtual Reality Room, SIGGRAPH'94.

George Francis, Chris Hartman, Glenn Chappell, Ulrike Axen, Paul McCreary, Alma Arias. Post-Euclidean Walkabout. Virtual Reality Room, SIGGRAPH'94.

Marcus Wagner, Alex Bourd, Shankar Subramanian, George Francis. Cellular Semiotics. GII Testbed, Supercomputing'95.

George Francis, John Sullivan, Ken Brakke, Rob Kusner, Dennis Roseman, Alex Bourd, Chris Hartman, Glenn Chappell, Jason Rubenstein. Laterna matheMagica: a 4-D Stereopticon. GII Testbed, Supercomputing'95.