"Classification problems in geometry and algebra"

Abstract In this talk I shall illustrate, by means of two examples, an on-going program at Utah State University to create Maple software and Java applets for implementing the solution to various classification problems in mathematics.

The first classification problem to be discussed is Petrov's remarkable classification of all 4 dimensional local group actions which admit an Lorentz invariant metric. (This is different from Petrov's classification of spacetimes according to the algebraic properties of the Weyl tensor.) Petrov's classification contains over 100 distinct local group ations and associated invariant metrics and thus it is a non-trivial task to identify a given local group action or a given invariant metric in Petrov's list. I shall demonstrate a web-based Java applet which allows one to identify any metric with symmetry in Petrov's list and also to search for group actions or invariant metrics in Petrov's list with prescribed properties. The results of some preliminary efforts to automate the verification of Petrov's classification will be shown.

The second classification problem will focus on the classification of low dimensional Lie algebras. There are many such tables of Lie algebras in the literature but once again the problem remains of explicitly identifying a given Lie algebra in these tables, a task which is further complicated by the existence of families of Lie algebras containing arbitrary parameters.

The programs which support the implementation of these classification problems are part of Vessiot, an integrated suite of Maple packages for computations in differential geometry, Lie algebras and the variational calculus on jet spaces. The talk will conclude with a quick overview and demonstration of these programs.

Click to return to timetable

Click to return to timetable

Albert COHEN
"Anisotropy and sparse image representations"

Abstract In image processing applications such as compression and denoising, one is often led to select a representation in which the images of interest are as sparse as possible. As we shall explain, wavelet bases provide an optimal anwser to this problem when the images are modeled as functions of bounded variation. The main limitation of this approach is that the geometric smoothness of edges is not taken into account in the BV model and exploited in the wavelet method. This state of fact has open new trends in terms of finding sparse image representations which have anisotropic features in order to capture the geometric simplicity of edges with less parameters. We shall present a multiresolution representation of this new type which is based on nonlinear data processing, using prediction operators which are inspired from ENO interpolation introduced by Harten and Osher in the context of shock computations. We shall discuss the new theoretical difficulties which occur when analyzing these methods and present their practical performances on real and synthetic images.

Click to return to timetable

"How computer graphics is changing Hollywood"

Abstract Film making is undergoing a digital revolution brought on by advances in areas such as computer technology, computational physics and computer graphics. This talk will provide a behind the scenes look at how fully digital films - such as Pixar's "Toy Story 2" and "Monster's Inc" - are made, with particular emphasis on the role that geometry plays in the revolution. I'll use our Academy Award winning short film "Geri's game" as a running example, and I'll highlight the two main technical innovations behind it: the use of subdivision surfaces for geometric modeling, and the use of simulated cloth dynamics.

"What does `foundations of computational mathematics' mean?"

Abstract I am frequently asked this question when talking about FoCM. While I cannot answer it precisely, I can give some examples of how mathematical reasoning can properly frame computational problems and lead to a new and better understanding of computational issues. I will give two examples of this; one in data processing and the other in PDE solvers.

Click to return to timetable

"Algorithms in combinatorial Morse theory"

Abstract We consider piecewise linear functions over triangulated manifolds and algorithms that use the theory of smooth Morse functions on such data. Specifically, we address the following questions:

  • how can we recognize critical points and split degenerate critical points into simple instances?
  • how can we define and compute Morse complexes in the absence of smoothness?
  • how can we asses the importance of critical points and generate a hiearchy of progressively coarser Morse complexes?
  • how do the above concepts generalize to time-varying and to vector-valued Morse functions?

All questions are motivated by concrete applications in scientific visualization and the reconstruction of structure from density data. The goal of this research is to develop the methods necessary to give mathematically well-founded solutions to the application problems.

Click to return to timetable

"Quantum computation using anyonic systems"

Abstract Anyons are particle like excitations of two dimensional quantum systems which may posses exotic "statistics" under the action of the braid group. It is known that universal quantum computation can be founded on such systems. It is not known if a suitable candidate can actually be manufactured in the real world although there is evidence (in both directions) on this question. I will dicuss a very simple family of anyonic models and their relation with ongoing experiments.

Click to return to timetable

"The technique of hierarchical matrices"

Abstract The hierarchical matrix technique applies to fully populated matrices as they arise from the discretisation of non-local operators like in the boundary element method or as the inverse of a sparse finite element matrix, provided that the underlying problems are elliptic. Using the format of the so-called \emph{hierarchical matrices} (or short H-matrices) we are able to approximate the dense matrix by a data-sparse one so that the required storage is almost linear in the dimension, i.e., linear up to logarithmic factors.

Moreover, the essential operations for these matrices (matrix-vector and matrix-matrix multiplication, addition and inversion) can approximately be performed again in almost linear time. This fact offers new application, e.g., the computation of matrix functions like the exponential or the solution of matrix equations like the Riccati equation can be performed with almost optimal complexity.

Click to return to timetable

"Quantum complexity of numerical problems"

Abstract A challenging question in the overlap of computer science, mathematics, and physics, is the exploration of potential capabilities of quantum computers. Milestones were the algorithm of Shor (1994), who showed that quantum computers could factor large integers efficiently (which is widely believed to be infeasible on classical computers) and the quantum search algorithm of Grover (1996), which provides a quadratic speedup over deterministic and randomized classical algorithms of searching a database.

So far, major research was concentrated on discrete problems like the above and many others one encounters in computer science. Much less was known about computational problems of analysis, including such a prominent example as high dimensional numerical integration, which is well-studied in the classical setting. We seek to understand how efficiently this and related problems can be solved in the quantum model of computation (that is, on a quantum computer) and how the outcome compares to the efficiency of deterministic or randomized algorithms on a classical (i.e. non-quantum) computer.

Complexity of numerical problems is studied in the general framework of information-based complexity theory. By now for many important problems of numerical analysis, including high dimensional integration in various function spaces, matching upper and lower complexity bounds are known for both the classical deterministic and randomized setting. It is a challenging task to study these problems in the setting of quantum computation. Once such results are obtained, one can compare them to the deterministic and randomized classical ones to understand the possible speedups by quantum algorithms.

In the talk we first give a short introduction to the basic ideas of quantum computation and present the quantum setting of information-based complexity theory, a framework suitable to handle the complexity of numerical problems in the quantum model of computation. Then we discuss recent results on quantum algorithms, lower bounds, and complexity for various integration problems, like approximating the mean of p-summable sequences and the integral of functions from Lp and Sobolev spaces. It turns out that in many cases there is an exponential speed-up of quantum algorithms over classical deterministic ones, and a quadratic speed-up of quantum algorithms over classical randomized ones.

Click to return to timetable

"Generic curves, generic polynomials and Liouville functions"

Abstract This talk will be devoted to definability problems in first-order logic. For instance, is there a first-order sentence F in the language of fields expanded by a unary symbol function f which satisfies the two following properties:

  1. F is true in the field of complex numbers whenever f is interpreted by a polynomial of even degree;
  2. F is false in the field of complex numbers whenever f is interpreted by a polynomial of odd degree.

Note that the same problem for the field of real numbers has an obvious solution. We shall see that questions of this kind have intringuing connections with the model theory of complex analytic functions.

Click to return to timetable

Teresa KRICK
"Straight-line programs in polynomial equation solving"

Abstract Solving symbolically polynomial equation systems when polynomials are represented in the usual dense codification turns out to be very inefficient: the sizes of the systems one can deal with do not answer to realistic needs. The straight-line program encoding appeared a decade ago in this frame as an alternative to classify families of problems which behave better with respect to complexity.

The talk will present an overview of the most recent complexity results for different polynomial problems when the input is encoded by straight-line programs. It will also try to show how surprising mathematical by-products, such as new mathematical invariants and results, can appear as a consequence of the search of good algorithms.

Click to return to timetable

"Development of a new handbook of properties of special functions"

Abstract Abramowitz and Stegun's Handbook of Mathematical Functions, published in 1964 by the National Bureau of Standards, is familiar to most mathematicians. It is even more familiar to scientists who use special functions in their daily work. But developments in mathematics and computing since 1964 make the old handbook less and less useful. To meet the need for a modern reference, NIST is developing a new handbook that will be published in 2003. A Web site covering much the same territory will be released also. This work is supported by the National Science Foundation. Details of the project and its current status will be described.

Click to return to timetable

"Numerical solution of large scale structured polynomial eigenvalue problems"

Abstract Large scale polynomial eigenvalue problems arise in many different applications. We are concerned with special classes of polynomials, where the coefficients essentially (except for small perturbations) alternate between symmetric and skew symmetric matrices. These problems arise in several classes of applications, e.g. the computation of 3D vertex singularities of anisotropic elastic fields, the solution of optimal control problems for second or higher order ordinary differential equations, problems from damped gyroscopic systems as well as Maxwell eigenvalue problems for Optical Waveguide Design.

We discuss a shift-and-invert, Lanczos as well as implicitely restarted Arnoldi methods that are specifically adapted to the symmetry structure of the polynomials. The new approaches extend recent work of Mehrmann and Watkins for quadratic eigenvalue with Hamiltonian eigensymmetry.

This is partly joint work with Thomas Apel, Tsung-Min Hwang, Wen-Wei Lin, and David Watkins.

Click to return to timetable

"Zeros of the Riemann zeta function: Conjectures and computations"

Abstract The Riemann Hypothesis is now the most famous unsolved problem in mathematics. It has stimulated extensive computations, including development of novel algorithms that are similar to those used in astrophysical simulations and in signal processing. These computations have so far confirmed the predictions of the Riemann Hypothesis, as well as of other, even more speculative conjectures. However, there is still a serious question of what these results mean.

Click to return to timetable

"What is learning theory? How does it relate to approximation theory, and to probability?"

Abstract The idea is to discuss some joint work with Felipe Cucker, emphasizing mathematical foundations of learning, with motivation from centuries of work on laws of physics to present day problems of recognition of words and meanings. This a learning by induction and a learning from examples.

Click to return to timetable

Edriss TITI
"Postprocessing Galerkin methods and approximating dynamics"

Abstract In this talk we will survey old results about Approximate Inertial Manifolds and their implementation in nonlinear Galerkin (NLG) methods. We will stress the benefits and shortcomings of the NLG methods and present an alternative postprocessing procedure for the Galerkin method. This postprocessing Galerkin method, which is much cheaper to implement computationally than the NLG method, possess the same rate of convergence (accuracy) as the simplest version of the NLG method, which is more accurate than the standard Galerkin method. Our results valid in the context of spectral and finite element Galerkin methods and for many nonlinear parabolic equations including the Navier-Stokes equations. We justify the derivation of the postprocessing algorithm from a classical truncation analysis point of view. More specifically, we will show that, to leading order, the correct approximative scheme is actually the postprocessed Galerkin method, and not the standard Galerkin method as is commonly believed.

We will also present some computational study to support our analytical results. Furthermore, we will present numerical criteria for detecting the right dynamics for systems like the Navier-Stokes equations.

This talk is based on joint works with Bosco Garcia-Archilla, Len Margolin, Julia Novo and Shannon Wynne.

Click to return to timetable

Michael TODD
"Detecting infeasibility in interior-point methods for optimization"

Abstract Interior-point methods are both theoretically and practically efficient algorithms for solving linear programming problems and certain convex extensions. However, they seem to be less flexible than the well-known simplex method: in particular, they do not deal as gracefully with infeasible or unbounded (dual infeasible) problems. One elegant way to produce either an optimal solution or a certificate of infeasibility is to embed the original problem in a larger homogeneous self-dual problem, but this seems less efficient computationally. Most implementations use so-called infeasible-interior-point methods, which focus exclusively on attaining feasibility and optimality. However, such methods are surprisingly successful in detecting infeasibility. We show that, on infeasible problems, they can be viewed as implicitly searching for an infeasibility certificate.

Click to return to timetable

Vladimir VAPNIK
"Problems of induction, empirical inference, and computer learning"

Abstract In the talk I would like to show that:

  1. Classical (Fisher's) approach to the applied statistics based on idea of functions estimation. It lead to the "curse of dimensionality".
  2. Alternative approach (the VC theory) based on idea of functionals estimation. It overcome the "curse of dimensionality".
  3. Methods of VC theory provide algorithms (e.g. Support Vector Machines) that generalize well in high dimensional spaces.
  4. New real world problems (e.g. image understanding, information retrieval, micriarray analysis) requer generalization in high dimensional (10,000-1,000,000) spaces. New method can be succesfully used for solving such problems.

Click to return to timetable

"Statistical model building and classification as optimization problems in RKHS - Polychotomous penalized likelihood and multicategory support vector machines"

Abstract We describe two modern methods for classification, penalized likelihood methods for `soft' classification, and support vector machines (SVM's) for `hard' classification. A training set is given, and a classification algorithm for future observations is built from it. The k-category penalized likelihood method returns a vector of probabilities (p1(x), ... , pk(x)) for each category, where x is the attribute vector that will be observed. The multicategory support vector machine (MSVM) returns a classifier vector (f1(x), ... , fk(x)) satisfying suml fl(x) = 0, where maxl fl(x) identifies the category. The two category SVM is very well known, while the multi-category SVM described here is new. These procedures can be found as the solution to optimization problems in a reproducing kernel Hilbert space (RKHS). Numerical methods for large data sets and methods for choosing the tuning parameter(s) will be noted. An example estimating the probabilities of mortality from several causes or survival, from a demographic study, will be given, along with an example estimating the classification of gene expression data according to one of several types of disease or `none of the above'.

Click to return to timetable