| Institute for Mathematics and its Applications University of Minnesota 400 Lind Hall 207 Church Street SE Minneapolis, MN 55455 |
Web: http://www.ima.umn.edu |
Email: ima-staff@ima.umn.edu |
Telephone: (612) 624-6066 |
Fax: (612) 626-7370
Additional newsletters available at http://www.ima.umn.edu/newsletters
Additional newsletters available at http://www.ima.umn.edu/newsletters
IMA Newsletter #364
February 2007
2006-2007 Program
Applications of Algebraic Geometry
See http://www.ima.umn.edu/2006-2007 for a full description of the 2006-2007 program on Applications of Algebraic Geometry.
IMA in the news - Check-out the article IMA Hosts 2006 Blackwell-Tapia Conference by Barry Cipra in the January/February 2007 issue of SIAM News.
Opportunities at the IMA - If you are interested in applying for a General Membership for a period of one month to one year in residence at the IMA during the 2007-2008 thematic program: Mathematics of Molecular and Cellular Biology, please find the application for this membership at our Applications site.
New Directions Short Course: The IMA is currently accepting applications for the 2007 New Directions Short Course - Compressive Sampling and Frontiers in Signal Processing June 4 - 15, 2007, taught by Emmanuel Candes, Ron DeVore and Rich Barniuk. This exploding area of research has connections to many areas of mathematics and presents many research opportunities. No prior background in signal processing is expected. Participants will receive full travel and lodging support during the workshop. Participation is by application only. Application deadline: April 1, 2007.
IMA is seeking a new director: The IMA is looking for a new director to begin in summer 2008.
Schedule
Thursday, February 1
| 11:15a-12:15p | Real algebraic geometry tutorial: Quotients of polynomial rings, Hermite's quadratic form and root counting | Kenneth R. Driessel (Iowa State University) | Lind Hall 409 | RAG |
Friday, February 2
| 1:25p-2:25p | IMA/MCIM Industrial problems seminar: Data fusion in a UAV surveillance system | Janet Pavelich Keel (Lockheed Martin Missiles and Space Company, Inc.) | Vincent Hall 1 | IPS |
Tuesday, February 6
| 11:15a-12:15p | IMA postdoc seminar: Characterization and computation of real-radical ideals using semidefinite programming techniques | Philipp Rostalski (Eidgenössische TH Zürich-Hönggerberg) | Lind 215 | PS |
Wednesday, February 7
| 11:15a-12:15p | Algebraic geometry and applications seminar: An introduction to algebraic statistics | Serkan Hosten (San Francisco State University) | EE/CS 3-180 | AGS |
Thursday, February 8
| 11:15a-12:15p | Real algebraic geometry tutorial: Quotients of polynomial rings, Hermite's quadratic form and root counting (continued) | Kenneth R. Driessel (Iowa State University) | Lind Hall 409 | RAG |
Tuesday, February 13
| 11:15a-12:15p | IMA postdoc seminar: The small Chvátal rank of an integer matrix | Tristram Bogart (University of Washington) | Lind 215 | PS |
Wednesday, February 14
| 11:15a-12:15p | Algebraic geometry and applications seminar: Statistical formulation of issues associated with multi-way contingency tables and the links to algebraic geometry | Stephen E. Fienberg (Carnegie-Mellon University) | Lind Hall 229 | AGS |
Thursday, February 15
| 11:15a-12:15p | Real algebraic geometry tutorial: Quotients of polynomial rings, Hermite's quadratic form and root counting (continued) | Kenneth R. Driessel (Iowa State University) | Lind Hall 409 | RAG |
Monday, February 19
| All Day | Presidents' Day. The IMA is open. |
Tuesday, February 20
| 11:15a-12:15p | IMA postdoc seminar: Counting rational curves in P2 using Kontsevich's formula | Hannah Markwig (University of Minnesota Twin Cities) | Lind 215 | PS |
| 2:30p-3:30p | IMA postdoc seminar: Variational partial differential equation(PDE) models with an application to medical imaging | Jungha An (University of Minnesota Twin Cities) | Lind Hall 409 | PS |
Wednesday, February 21
| 11:15a-12:15p | Algebraic geometry and applications seminar: Rational and algebraic invariants of a group action | Evelyne Hubert (Institut National de Recherche en Informatique Automatique (INRIA)) | EE/CS 3-180 | AGS |
Thursday, February 22
| 11:15a-12:15p | Real algebraic geometry tutorial: Quotients of polynomial rings, Hermite's quadratic form and root counting (continued) | Kenneth R. Driessel (Iowa State University) | Lind Hall 409 | RAG |
Tuesday, February 27
| 11:15a-12:15p | IMA postdoc seminar: Counting rational curves in P2 using tropical geometry | Michael Kerber (Universität Kaiserslautern) | Lind 215 | PS |
Wednesday, February 28
| 11:15a-12:15p | Algebraic geometry and applications seminar: Moving frames in classical invariant theory and computer vision | Peter J. Olver (University of Minnesota Twin Cities) | EE/CS 3-180 | AGS |
Abstracts
| Tristram Bogart (University of Washington) | IMA postdoc seminar: The small Chvátal rank of an integer matrix |
| Abstract: Given an integer matrix A and an integer vector b, we define the small Chvatal rank (SCR) of the system Ax <= b to be the least number of
iterations of an iterated Hilbert basis construction to obtain all facet normals of the integer hull (that is, the convex hull of the set of integer solutions. Our procedure is a variation of the
Chvatal-Gomory procedure to compute integer hulls of polyhedra. The key difference is that our procedure ignores the right-hand side vector b and uses only the matrix A.
We prove that the SCR of Ax <= b is bounded above by the Chvatal rank of Ax <= b and is hence finite. To justify the adjective "small", we show that when n=2, SCR is at most one while Chvatal rank can be arbitrarily high. For a family of examples from combinatorial optimization, we prove that the SCR is one or two while the Chvatal rank is known to be roughly log(n). We next relate SCR to the notion of supernormality of a vector configuration (specifically, the rows of A.) Supernormality is a generalization of unimodularity and we exhibit an infinite family of vector configurations arising from odd cycles that are supernormal but not unimodular. This answers a question of Hosten, Maclagan and Sturmfels. Lastly, we provide lower bounds on SCR. We prove that when n >= 3, SCR can be arbitrarily high and exponentially large in the input size. We also prove that for polytopes contained in the d-dimensional unit cube, the SCR can be at least d/2 - o(d) which is of the same order as the known lower bounds on Chvatal rank for such systems. Our methods thus provide an alternate way to compute lower bounds on Chvatal rank. This project is joint work with Rekha Thomas. |
|
| Kenneth R. Driessel (Iowa State University) | Real algebraic geometry tutorial: Quotients of polynomial rings, Hermite's quadratic form and root counting (continued) |
| Abstract: I shall mainly follow the material in the section "Zero-dimensional systems" in the book by Basu, Pollack and Roy. | |
| Stephen E. Fienberg (Carnegie-Mellon University) | Algebraic geometry and applications seminar: Statistical formulation of issues associated with multi-way contingency tables and the links to algebraic geometry |
| Abstract: Many statistical problems arising in the context of multi-dimensional tables of non-negative counts (known as contingency tables) have natural representations in algebraic and polyhedral geometry. I will introduce some of these problems in the context of actual examples of large sparse tables and talk about how we have treated them and why. For example, our work on bounds for contingency table entries has been motivated by problems arising in the context of the protection of confidential statistical data results on decompositions related to graphical model representations have explicit algebraic geometry formulations. Similarly, results on the existence of maximum likelihood estimates for log-linear models are tied to polyhedral representations. It turns out that there are close linkages that I will describe. | |
| Serkan Hosten (San Francisco State University) | Algebraic geometry and applications seminar: An introduction to algebraic statistics |
| Abstract: This will be a gentle introduction to the applications of algebraic geometry to statistics. The main goal of the talk is to present statistical models, i.e. sets of probability distributions (defined parametrically most of the time), as algebraic varieties. I will give examples where defining equations of such statistical model varieties have been successfully computed: various graphical models and models for DNA sequence evolution. I will also talk about the algebraic degree of maximum likelihood estimation with old and new examples. | |
| Evelyne Hubert (Institut National de Recherche en Informatique Automatique (INRIA)) | Algebraic geometry and applications seminar: Rational and algebraic invariants of a group action |
| Abstract: We consider a rational group action on the affine space and propose a construction of a finite set of rational invariants and a simple algorithm to rewrite any rational invariant in terms of those generators. The construction can be extended to provide algebraic foundations to Cartan's moving frame method, as revised in [Fels & Olver 1999]. This is joint work with Irina Kogan, North Carolina State University. | |
| Janet Pavelich Keel (Lockheed Martin Missiles and Space Company, Inc.) | IMA/MCIM Industrial problems seminar: Data fusion in a UAV surveillance system |
| Abstract: This talk will be about a recent Lockheed Martin project, the implementation of a data fusion method in the surveillance system of an Unmanned Aerial Vehicle (UAV). In this context data fusion is the problem of sequentially estimating the state of a dynamic system - ships at sea - given a sequence of noisy and incomplete measurements from the sensor suite on the UAV: radar, an Electro-Optical/Infrared (EO/IR) camera, and an Automatic Identification System (AIS) receiver. We will present the basic algorithms used in this project, and will then discuss their limitations and possible improvements. | |
| Michael Kerber (Universität Kaiserslautern) | IMA postdoc seminar: Counting rational curves in P2 using tropical geometry |
| Abstract: Tropical geometry is a rapidly developing field of algebraic geometry with important applications in quite distinct areas of pure and applied mathematics. In this talk, we give a short introduction to the theory of tropical curves and discuss its applications to the enumerative geometry of plane curves, with a focus on computing the Kontsevich number Nd of rational plane curves of fixed degree d interpolating an appropriate number of given points in general position. | |
| Hannah Markwig (University of Minnesota Twin Cities) | IMA postdoc seminar: Counting rational curves in P2 using Kontsevich's formula |
| Abstract: The numbers Nd of rational plane curves has for a long time only been known for small d. In 1990, Kontsevich came up with a recursive formula. In this talk, we will give some basic ideas and an example how Kontsevich's formula can be derived. | |
| Peter J. Olver (University of Minnesota Twin Cities) | Algebraic geometry and applications seminar: Moving frames in classical invariant theory and computer vision |
| Abstract: Classical invariant theory was inspired by the basic problems of equivalence and symmetry of polynomials (or forms) under the projective group. In this talk, I will explain how a powerful new approach to the Cartan method of moving frames can be applied to classify algebraic and differential invariants for very general group actions, leading, among many other applications, to new solutions to the equivalence and symmetry problems arising in both invariant theory, differential geometry, and object recognition in computer vision. | |
| Philipp Rostalski (Eidgenössische TH Zürich-Hönggerberg) | IMA postdoc seminar: Characterization and computation of real-radical ideals using semidefinite programming techniques |
| Abstract: In this talk I will discuss a method (joined work with M. Laurent and J.-B. Lasserre) for computing all real points on a zero-dimensional semi-algebraic set described by polynomial equalities and inequalities as well as some "nice" polynomial generators for the corresponding vanishing ideal, namely border resp. Gröbner basis for the real radical ideal. In contrast to exact computational algebraic methods, the method we propose uses numerical linear algebra and semidefinite optimization techniques to compute approximate solutions and generator polynomials. The method is real-algebraic in nature and prevents the computation of any complex solution. The proposed methods fits well into a relatively new branch of mathematics called "Numerical Polynomial Algebra." | |
Visitors in Residence
| Elizabeth Allman | University of Alaska | 1/7/2007 - 4/7/2007 |
| Jungha An | University of Minnesota Twin Cities | 9/1/2005 - 8/31/2007 |
| Douglas N. Arnold | University of Minnesota Twin Cities | 7/15/2001 - 8/31/2007 |
| Donald G. Aronson | University of Minnesota Twin Cities | 9/1/2002 - 8/31/2007 |
| Hélène Barcelo | Arizona State University | 2/3/2007 - 3/31/2007 |
| Daniel J. Bates | University of Minnesota Twin Cities | 9/1/2006 - 8/31/2007 |
| Arend Bayer | University of Utah | 2/19/2007 - 2/19/2007 |
| Yermal Sujeet Bhat | University of Minnesota Twin Cities | 9/1/2006 - 8/31/2007 |
| Víctor Blanco Izquierdo | University of Sevilla | 1/11/2007 - 4/21/2007 |
| Cristiano Bocci | Università di Milano | 1/10/2007 - 3/10/2007 |
| Tristram Bogart | University of Washington | 1/8/2007 - 3/25/2007 |
| Enrico Carlini | Politecnico di Torino | 1/10/2007 - 2/16/2007 |
| Ionut Ciocan-Fontanine | University of Minnesota Twin Cities | 9/1/2006 - 6/30/2007 |
| Alicia Dickenstein | University of Buenos Aires | 2/15/2007 - 3/14/2007 |
| Kenneth R. Driessel | Iowa State University | 9/1/2006 - 6/29/2007 |
| Mathias Drton | University of Chicago | 1/8/2007 - 3/30/2007 |
| Nicholas Eriksson | Stanford University | 2/14/2007 - 3/16/2007 |
| Makan Fardad | University of Minnesota Twin Cities | 8/26/2006 - 8/13/2007 |
| Stephen E. Fienberg | Carnegie-Mellon University | 1/1/2007 - 3/31/2007 |
| Ioannis Fotiou | Eidgenössische TH Zürich-Hönggerberg | 1/10/2007 - 2/16/2007 |
| Jason E. Gower | University of Minnesota Twin Cities | 9/1/2006 - 8/31/2007 |
| Gloria Haro Ortega | University of Minnesota Twin Cities | 9/1/2005 - 8/31/2007 |
| Milena Hering | University of Minnesota Twin Cities | 9/1/2006 - 8/31/2007 |
| Patricia Hersh | Indiana University | 2/15/2007 - 5/15/2007 |
| Sung-Pil Hong | Seoul National University | 1/16/2007 - 2/1/2007 |
| Serkan Hosten | San Francisco State University | 1/2/2007 - 2/16/2007 |
| Benjamin J. Howard | University of Minnesota Twin Cities | 9/1/2006 - 8/31/2007 |
| Evelyne Hubert | Institut National de Recherche en Informatique Automatique (INRIA) | 9/1/2006 - 6/30/2007 |
| Farhad Jafari | University of Wyoming | 9/1/2006 - 6/30/2007 |
| Anders Nedergaard Jensen | Aarhus University | 9/6/2006 - 6/30/2007 |
| Steve Kaliszewski | Arizona State University | 1/7/2007 - 6/30/2007 |
| Mordechai Katzman | University of Sheffield | 1/10/2007 - 5/15/2007 |
| Janet Pavelich Keel | Lockheed Martin Missiles and Space Company, Inc. | 2/2/2007 - 2/2/2007 |
| Michael Kerber | Universität Kaiserslautern | 2/19/2007 - 5/11/2007 |
| Song-Hwa Kwon | University of Minnesota Twin Cities | 8/30/2005 - 8/31/2007 |
| Jean Bernard Lasserre | Centre National de la Recherche Scientifique (CNRS) | 1/7/2007 - 2/3/2007 |
| Niels Lauritzen | Aarhus University | 8/28/2006 - 7/10/2007 |
| Anton Leykin | University of Minnesota Twin Cities | 8/16/2006 - 8/15/2007 |
| Hstau Liao | University of Minnesota Twin Cities | 9/2/2005 - 8/31/2007 |
| Laura Lurati | University of Minnesota Twin Cities | 9/1/2006 - 8/31/2007 |
| Gennady Lyubeznik | University of Minnesota Twin Cities | 9/1/2006 - 6/30/2007 |
| Hannah Markwig | University of Minnesota Twin Cities | 9/1/2006 - 8/31/2007 |
| Thomas Markwig | Universität Kaiserslautern | 9/1/2006 - 6/30/2007 |
| Richard Moeckel | University of Minnesota Twin Cities | 9/1/2006 - 6/30/2007 |
| Uwe Nagel | University of Kentucky | 9/1/2006 - 6/1/2007 |
| Jiawang Nie | University of Minnesota Twin Cities | 9/1/2006 - 8/31/2007 |
| Peter J. Olver | University of Minnesota Twin Cities | 2/28/2007 - 2/28/2007 |
| Michael E. O'Sullivan | San Diego State University | 2/21/2007 - 3/24/2007 |
| Lior Pachter | University of California | 2/28/2007 - 3/10/2007 |
| Helfried Peyrl | Automatic Control Laboratory | 1/15/2007 - 2/3/2007 |
| Mihai Putinar | University of California | 1/7/2007 - 3/24/2007 |
| Victor Reiner | University of Minnesota Twin Cities | 9/1/2006 - 6/30/2007 |
| John A. Rhodes | University of Alaska | 1/7/2007 - 4/7/2007 |
| Joel Roberts | University of Minnesota Twin Cities | 9/1/2006 - 6/30/2007 |
| Daniel Robertz | RWTH Aachen | 2/18/2007 - 4/1/2007 |
| Marie Rognes | University of Oslo | 1/10/2007 - 6/30/2007 |
| Amos Ron | University of Wisconsin | 2/14/2007 - 2/14/2007 |
| Philipp Rostalski | Eidgenössische TH Zürich-Hönggerberg | 1/2/2007 - 2/19/2007 |
| Bjarke Hammersholt Roune | Aarhus University | 9/12/2006 - 6/30/2007 |
| Arnd Scheel | University of Minnesota Twin Cities | 7/15/2004 - 8/31/2007 |
| Chehrzad Shakiban | University of Minnesota Twin Cities | 9/1/2006 - 8/31/2007 |
| Aleksandra Slavkovic | Pennsylvania State University | 1/31/2007 - 3/31/2007 |
| Frank Sottile | Texas A & M University | 2/26/2007 - 6/30/2007 |
| Steven Sperber | University of Minnesota Twin Cities | 9/1/2006 - 6/30/2007 |
| Andrew Stein | University of Michigan | 2/6/2007 - 2/8/2007 |
| Seth Sullivant | Harvard University | 2/19/2007 - 3/30/2007 |
| Rebecca Swanson | Indiana University | 2/22/2007 - 3/31/2007 |
| Rekha R. Thomas | University of Washington | 1/1/2007 - 3/31/2007 |
| Carl Toews | University of Minnesota Twin Cities | 9/1/2005 - 8/31/2007 |
| John Voight | University of Minnesota Twin Cities | 8/15/2006 - 8/31/2007 |
| Josephine Yu | University of California | 1/9/2007 - 6/30/2007 |
| Hongchao Zhang | University of Minnesota Twin Cities | 9/1/2006 - 8/31/2007 |
| Lihong Zhi | Chinese Academy of Sciences | 1/11/2007 - 3/4/2007 |
| Yi Zhou | Carnegie-Mellon University | 2/28/2007 - 3/16/2007 |
Legend:
Postdoc or Industrial Postdoc
Long-term Visitor
IMA Affiliates:
3M, Boeing, Carnegie-Mellon University, Corning, ExxonMobil, Ford, General Electric, General Motors, Georgia Institute of Technology, Honeywell, IBM, Indiana University, Iowa State University, Johnson & Johnson, Kent State University, Lawrence Livermore National Laboratory, Lockheed Martin, Los Alamos National Laboratory, Medtronic, Michigan State University, Michigan Technological University, Mississippi State University, Motorola, Northern Illinois University, Ohio State University, Pennsylvania State University, Purdue University, Rice University, Rutgers University, Sandia National Laboratories, Schlumberger-Doll, Schlumberger-Doll Research, Seoul National University, Siemens, Telcordia, Texas A & M University, University of Chicago, University of Cincinnati, University of Delaware, University of Houston, University of Illinois at Urbana-Champaign, University of Iowa, University of Kentucky, University of Maryland, University of Michigan, University of Minnesota, University of Notre Dame, University of Pittsburgh, University of Texas, University of Wisconsin, University of Wyoming, US Air Force Research Laboratory, Wayne State University, Worcester Polytechnic Institute