The SPAMS Schedule - Spring 2000

Bill: Dude, being stuck on this desert island sure is bogus. I wish we had some rad math textbooks to pass the time.

Ted: Totally... but hey, why don't we reconstruct the real numbers using a recursive definition involving pairs of sets?

Bill: Gnarly! And check out what happens at infinity... yo, I think I just found a number that lies between two real numbers...

Ted: And I can extend it to ordinal numbers...

Bill: And we can generalize the definition to represent positions in two- player games...

Ted: ...Whoa...

Bill & Ted: EXCELLENT!!

Abstract: For a long time after the foundational work of Noether, Hilbert and Artin, commutative algebra has suffered from the nasty condition that affects many branches of pure mathematics: pathological non-constructiveness. Then in 1965, Bruno Buchberger's PhD thesis introduced an algorithm that marked the beginning of computational commutative algebra, and with it a wealth of applications.

The purpose of this talk is to give an overview of Grobner bases, of Buchberger's algorithm and of their application to geometric theorem proving. No commutative algebra background is required; of course, fond memories of some previous exposure to abstract algebra can only make these 50 minutes before food more enjoyable.

Abstract: Linear systems characterized by a very large number of state-space variables occur in many engineering applications. It is desirable and often necessary to approximate this high order model with a model of much lower order, which has similar properties as the original.

The two traditional and competing approaches to computing these reduced models have been moment-matching via Lanczos and Truncated Balanced Realization(TBR). TBR produces a nearly optimal reduced model with a known frequency domain error bound, but requires the solution of two Lyapunov equations, which, when solved exactly, is expensive. Moment-matching via Lanczos is inexpensive but has no known error bound and often requires much higher order models to achieve a given error tolerance.

I will present a new iterative method, Cholesky Factor ADI(CF-ADI), which solves Lyapunov equations efficiently. It requires only linear solves with the system matrix, and hence is extremely well-suited to sparse or structured problems. I will show how Cholesky Factor ADI can be made even more efficient by reusing Krylov subspace vectors in the linear solves.

The CF-ADI method is then applied to the model reduction problem. The new model reduction method uses CF-ADI to obtain approximate solutions to two Lyapunov equations, and then projects the original system by the union of the two solutions' dominant eigenspaces. This new model reduction method is inexpensive, requiring only linear matrix-vector solves, and it frequently gives a good approximation to TBR.

Abstract: A martenistic phase transformation is one where a given material changes its phase very quickly. This type of phase transformation has been seen in graphite / diamond and alpha iron / epsilon iron transformations. In both materials this type of phase transformations can occur due to the passage of a shock wave. The shock waves strength determines how this phase transformation will proceed. Currently the results predicted for the free surface velocity computed by an analysis with only shocks still do not explain one part of the experimental results. We hope that a computation with rarefaction fans will explain this missing piece.

Abstract: In this talk I will review the basic theory of baroclinic instability, which is the underlying phenomenon behind our everyday weather. There are two classical linear models: the Eady and the Charney problem, and an important difference between them is that only the former has a spatial threshold for instability. As Bretherton (1966) showed, this is related to the non-zero gradient of potential vorticity at the steering level (the level where the phase speed equals the mean flow) in the Charney problem. I will demonstrate that Charney waves of small scale can equilibrate by mixing potential vorticity at that level, thus violating Bretherton's condition.

Abstract: The statistics and structure of river networks are commonly described by power laws. In practice, deviations from and fluctuations about scaling are present making exact measurements difficult. The choice of parameter ranges used for regression analysis can markedly affect estimates of exponents. We show for the relationship between stream length and basin area the existence of several distinct scaling regimes linked by crossover regions. These scaling regimes, which may be present to varying degrees, pertain to the small scale of linear, pre-network basins; intermediate length scales where scaling approximately holds; and outer length scales where scaling breaks down. For the intermediate regime, we postulate a functional form for the underlying probability distribution for a number of network quantities and find reasonable agreement with data. The data we examine comes from large-scale networks such as the Mississippi, Amazon, Nile, Congo and Kansas river basins.

We observe that improvements in topographic resolution would be unlikely to result in cleaner statistics; variations in measurements for small-scale basins are real and unavoidable; deviations from scaling can be subtle and are correlated with fluctuations in basin shape; universality classes cannot be unequivocally identified for real river networks; and that strong deviations are indicative of geology being at work.

Abstract: For examples from the theory of partitions, equations in the symmetric group, and symmetric functions, we try to interpret combinatorially the cancellation of factors $(1-x^i)$ in the numerator and the denominator of a generating function expression. The generating function arguments are relatively simple, while in the first case, a bijective proof is due to Erdos, in the second case, it is due to the combinatorics problem-solving seminar, and in the last, there is no known bijective proof.

Abstract: To begin, some classwork which will be easy even for non combinatorialists: examples of the results of Ehrhart on counting lattice points in scaled polytopes. In particular, we will compute examples of the Ehrhart polynomial and his Law of Reciprocity.

Moving swiftly onwards, there will be a hand waving discussion of the resolution of the upper bound conjecture, involving the face ring of a polytope, avoiding all Cohen-Macaulay / shellability "technicalities". If there is any time left, some easy to state open problems will be introduced, and the audience invited to test their wits.

Abstract: The phenomenon of skipping stones is well known to any child who has ever been to a lake or a beach. But not everybody agrees on the best stone and the method of throwing in order to have the most spectacular jumps. To answer this, one has to understand the relevant physics. What makes this problem so great is that it touches on a lot of smaller problems in fluid mechanics, which will allow me to introduce you to a great variety of results. What makes this problem so awful is that it is impossible to solve exactly (or even close), which will allow me to introduce you to educated approximations, known as scaling.

Abstract: The word tensegrity is meant to capture the idea of tension with integrity. The term was first used to describe works of the sculptor Kenneth Snelson. The sculptures were sticks suspended in mid-air by cables. Mathematicially, a tensegrity framework is a configuration of points with certain pairs constrained not to get closer and certain pairs constrained not to get further apart. First I will talk about some more classical geometric rigidity questions such as Cauchy's Rigidity Theorem. Later I will move into the topic of tensegrities, including the concepts of super stability and global rigidity. Also, there will be fun examples to play with!

Abstract: In order to study the properties of a quantum field theory or statistical field theory, such as phases and phase transitions, one needs to evaluate a path integral. This is a daunting task, which for all but the most trivial theories can only be tackled either perturbatively, or using numerical approximations. Focusing on the latter method, we will give an introduction to Monte Carlo integration in this context. We will then discuss the Metropolis algorithms and a variety of other algorithms that have been developed for particular models. If time permits, we will report on current research, exploring the phase space of an SO(6)*SO(4) model with applications to colour superconductivity and chiral symmetry breaking.

Rotaries (also known as "traffic circles" or "roundabouts") are a common feature of many Massachusetts roads. If too many cars want to use the same rotary, a traffic jam may develop. (This, too, is a common feature of many Massachusetts roads.)

If you were a traffic engineer, you'd love to be able to prove that there wouldn't be any traffic jams on the rotaries you design. Unfortunately, between road rage and the various other pathologies of Massachusetts residents, it's hard to know how drivers will behave (and hence hard to model the traffic jams). I'll show how to use a technique from queueing theory called "fluid limits" to overcome this difficulty. No knowledge of queueing theory or packet routing is assumed. Some prior experience driving on rotaries is helpful, but not necessary.

Find out when and how the edges of a simple graph can be oriented to obtain a transitive relation. Discover Galai's beautiful decomposition theory and list of forbidden induced subgraphs. Guess how to generalize the results to graphs with more colors on the edges. In three words: enjoy comparability graphs!

In 1980, Don Rawlings made up an interesting permutation statistic which generalizes MAJ and INV. To fully appreciate it, we will review the definitions of these and other permutation statistics, including one which I made up. We will use recursive formulas and bijections to demonstrate the equidistributions of various permutation statstics.

This talk will not involve any probability or statistics. Anyone who asks a question about either of these two topics will be escorted from the room by my bodyguards Peter and Francis.