Applied Math Colloquium

A basic problem in computational algebra is to find all zeros of a sparse system of polynomial equations. The situation is fairly well understood for complex zeros: their expected number is the mixed volume of the given Newton polytopes. This result due to Bernstein can be proved by an elementary algorithm using toric deformations.

Things are more difficult (and interesting) over the real numbers: Khovanskii has shown that the number of real roots is bounded by a function which is independent of the degree of the given equations. More precise upper bounds are stated in conjectures of Kouchnirenko and Itenberg-Roy. We discuss these results and conjectures, and we illustrate them with many colorful pictures of planar polygons.

Many statistical computations arising in linear least squares require the estimation of a quadratic form. We consider the problem of determining upper and lower bounds of the quadratic form

u^{T} F(A) u

where u is a given vector, A is a symmetric positive definite matix and F(.), an analytic function. The estimate of the quadratic form is determined by using Gauss quadrature rules; a basic tool of our studies is the Lanczos algorithm.

The technique we describe is useful in estimating the Generalized Cross Validation (GCV) function and solving linear least squares with a quadratic constraint. Our procedure is particular useful for large data sets.

We discuss the complexity problem in artificial feedforward neural networks designed to approximate real valued functions of several variables and estimate the number of neurons in a network required to ensure a given accuracy.

We present two new domain decomposition solvers in the context of spectral element discretizations. The first is a domain decomposition solver for the discrete steady convection-diffusion equation, while the second is a domain decomposition solver for the discrete steady Stokes or Navier-Stokes equations. The solution algorithms are both based on the additive Schwarz method in the context of nonoverlapping subdomains. The key ingredients are: (i) a coarse global system; (ii) a set of local, independent subproblems associated with the subdomains (or spectral elements); (iii) a system associated with the unknowns on the subdomain interfaces; and (iv) a Krylov method such as the CG algorithm or the GMRES algorithm. We present numerical results that demonstrate the convergence properties of the new solvers, as well as the applicability of the methods to solve heat transfer and incompressible fluid flow problems.

It's typically about 1 in 10 million.

To answer this question, you need a probability model of election outcomes. We first discuss some obvious but wrong ideas and then present the right general framework for answering this sort of question.

Our models for elections are extensions of well known results in political science. The state-by-state outcome of the Presidential election can be predicted with fair accuracy using information available before Labor Day. We briefly discuss the political implication of this fact and then describe a forecasting method based on a random components linear regression model. As a side issue, we also address the question of whether the electoral college is biased in favor of the Democrats or Republicans.

We also discuss the statistical difficulties in creating the model and compare to models for Congressional elections. This work is joint with Gary King, Department of Government, Harvard University.

We shall describe the problems known as the "Existential Theory of the Reals", the "General Decision problem for the reals" which are both special cases of "Quantifier Elimination over real closed fields" and the construction of "Roadmaps" for semi-algebraic sets. There is a long history of algorithmic solutions to these problems going back sixty years to Tarski followed by work of Collins, Schwartz-Sharir, Grigor'ev-Vorobjov, Heintz- Roy-Solerno, Canny and Renegar among others. Then we shall indicate some of the new ideas developed by Basu-Pollack-Roy that permit further improvements in these algorithms.

Where are the zeros of a polynomial of degree n with real iid standard normal coeffs? Can one reconstruct a finite subset S of the integer lattice Z^2 given the number of points of S on any line in any one of k fixed directions? - a "real" problem. Suppose a company has to choose between corporate options, each returning a profit stream which is a Brownian motion process with known drift and volatility; which option to choose? If Sn is the sum of iid normals with 0 mean and unit variance, then E|Sn| == sqrt(2n/pi); is there any other law besides the standard normal that can make that statement?

Let $L$ be a unimodular integral lattice in $R^n$ (a.k.a. positive-definite quadratic form over $\Bbb Z$ with discriminant 1). The "shadow" of $L$ is $L + {w\over 2}$ for $w\in L$ such that $(v,w) \equiv (v,v) {\rm \ mod\,} 2$ for all $v \in L$. (Such $w$ always exist and constitute a coset of $2L$ in $L$.)

We show how the theory of theta series and modular forms yields both the classical fact that $(w,w) \equiv n {\rm \ mod\,} 8$ and the new result (suggested by recent work on 4-manifolds) that ${\Bbb Z}^n$ is the lattice with the longest shadow (i.e., the lattice for which $\displaystyle\min_w\,(w,w)$ attains its maximal value $n$).

Recently, Gordon, Webb, and Wolpert proved that one cannot "hear the shape of a drum"---they constructed a pair of nonisometric planar regions that have identical Laplace spectra. Their discovery has been documented by artices in Science, Science News, and the Math Monthly. The simplest form of their example is as a pair of eight-sided nonconvex polygons. Since Gordon et al.'s work, many other isospectral pairs have been found, all in the form of nonconvex polygons.

While several elegant mathematical techniques can be used to prove the isospectrality of the drums, none can produce the spectrum itself. Standard numerical methods for determining the eigenvalues are in general inefficient because of the reentrant corners. However, there is an algorithm, originally due to Descloux and Tolley, that blends domain decomposition with finite elements. With a modification that doubles its accuracy, this method can be used to compute the eigenvalues of polygons efficiently and accurately. The first twenty-five eigenvalues of the Gordon, Webb, and Wolpert drums have been found to twelve digits, and eigenfunctions can be computed to similar accuracy. The algorithm clearly performs better than finite elements and other methods applied to this problem.

Vortex methods for incompressible 2-D flow require an efficient and accurate numerical integration of the singular Biot-Savart kernel. This is traditionally done via smoothing and the flow map, a strategy which loses accuracy over long time spans. A different approach --- using fast summation globally but correcting it locally --- yields efficient high-order vortex methods with excellent long-time accuracy.

Geometrical shock dynamics is an approximate theory for the propagation of shock waves in gases. The theory is based on an approximation of the Euler equations in which the motion of the leading shock is determined explicitly. The equations of the geometrical shock dynamics are analogous to those for steady, supersonic, potential flow with a particular choice of the density-speed relation. Several numerical methods for the calculation of the shock waves within the approximate theory will be discussed. Numerical results will be presented for shock propagation in channels and for converging cylindrical and spherical shocks. The channel problem is used to compare the shockfronts calculated using the approximate theory with those obtained from a corresponding calculation of the full Euler equations. Converging cylindrical and spherical shocks are calculated to analyze their stability.