IMA Volumes in Mathematics and its Applications – serie

This volume comprises some of the key work presented at two IMA Workshops on Computer Vision during fall of 2000. Recent years have seen significant advances in the application of sophisticated mathematical theories to the problems arising in image processing. Basic issues include image smoothing and denoising, image enhancement, morphology, image compression, and segmentation (determining boundaries of objects-including problems of camera distortion and partial occlusion). Several mathematical approaches have emerged, including methods based on nonlinear partial differential equations, stochastic and statistical methods, and signal processing techniques, including wavelets and other transform theories. Shape theory is of fundamental importance since it is the bottleneck between high and low level vision, and formed the bridge between the two workshops on vision. The recent geometric partial differential equation methods have been essential in throwing new light on this very difficult problem area. Further, stochastic processes, including Markov random fields, have been used in a Bayesian framework to incorporate prior constraints on smoothness and the regularities of discontinuities into algorithms for image restoration and reconstruction. A number of applications are considered including optical character and handwriting recognizers, printed-circuit board inspection systems and quality control devices, motion detection, robotic control by visual feedback, reconstruction of objects from stereoscopic view and/or motion, autonomous road vehicles, and many others.

Recent advances in both the theory and implementation of computational algebraic geometry have led to new, striking applications to a variety of fields of research. The articles in this volume highlight a range of these applications and provide introductory material for topics covered in the IMA workshops on "Optimization and Control" and "Applications in Biology, Dynamics, and Statistics" held during the IMA year on Applications of Algebraic Geometry. The articles related to optimization and control focus on burgeoning use of semidefinite programming and moment matrix techniques in computational real algebraic geometry. The new direction towards a systematic study of non-commutative real algebraic geometry is well represented in the volume. Other articles provide an overview of the way computational algebra is useful for analysis of contingency tables, reconstruction of phylogenetic trees, and in systems biology. The contributions collected in this volume are accessible to non-experts, self-contained and informative; they quickly move towards cutting edge research in these areas, and provide a wealth of open problems for future research.

Speech and language technologies continue to grow in importance as they are used to create natural and efficient interfaces between people and machines, and to automatically transcribe, extract, analyze, and route information from high-volume streams of spoken and written information. The workshops on Mathematical Foundations of Speech Processing and Natural Language Modeling were held in the Fall of 2000 at the University of Minnesota's NSF-sponsored Institute for Mathematics and Its Applications, as part of a "Mathematics in Multimedia" year-long program. Each workshop brought together researchers in the respective technologies on the one hand, and mathematicians and statisticians on the other hand, for an intensive week of cross-fertilization. There is a long history of benefit from introducing mathematical techniques and ideas to speech and language technologies. Examples include the source-channel paradigm, hidden Markov models, decision trees, exponential models and formal languages theory. It is likely that new mathematical techniques, or novel applications of existing techniques, will once again prove pivotal for moving the field forward.This volume consists of original contributions presented by participants during the two workshops. Topics include language modeling, prosody, acoustic-phonetic modeling, and statistical methodology.

This IMA Volume in Mathematics and its Applications TIME SERIES ANALYSIS AND APPLICATIONS TO GEOPHYSICAL SYSTEMS contains papers presented at a very successful workshop on the same title. The event which was held on November 12-15, 2001 was an integral part of the IMA 2001-2002 annual program on " Mathematics in the Geosciences. " We would like to thank David R. Brillinger (Department of Statistics, Uni­ versity of California, Berkeley), Enders Anthony Robinson (Department of Earth and Environmental Engineering, Columbia University), and Fred­ eric Paik Schoenberg (Department of Statistics, University of California, Los Angeles) for their superb role as workshop organizers and editors of the proceedings. We are also grateful to Robert H. Shumway (Department of Statistics, University of California, Davis) for his help in organizing the four-day event. We take this opportunity to thank the National Science Foundation for its support of the IMA. Series Editors Douglas N. Arnold, Director of the IMA Fadil Santosa, Deputy Director of the IMA v PREFACE This volume contains a collection of papers that were presented dur­ ing the Workshop on Time Series Analysis and Applications to Geophysical Systems at the Institute for Mathematics and its Applications (IMA) at the University of Minnesota from November 12-15, 2001. This was part of the IMA Thematic Year on Mathematics in the Geosciences, and was the last in a series of four Workshops during the Fall Quarter dedicated to Dynamical Systems and Ergodic Theory.

"Probability and Partial Differential Equations in Modern Applied Mathematics" is devoted to the role of probabilistic methods in modern applied mathematics from the perspectives of both a tool for analysis and as a tool in modeling. There is a recognition in the applied mathematics research community that stochastic methods are playing an increasingly prominent role in the formulation and analysis of diverse problems of contemporary interest in the sciences and engineering. A probabilistic representation of solutions to partial differential equations that arise as deterministic models allows one to exploit the power of stochastic calculus and probabilistic limit theory in the analysis of deterministic problems, as well as to offer new perspectives on the phenomena for modeling purposes. There is also a growing appreciation of the role for the inclusion of stochastic effects in the modeling of complex systems. This has led to interesting new mathematical problems at the interface of probability, dynamical systems, numerical analysis, and partial differential equations.This volume will be useful to researchers and graduate students interested in probabilistic methods, dynamical systems approaches and numerical analysis for mathematical modeling in the sciences and engineering.

This IMA Volume in Mathematics and its Applications MODELING OF SOFT MATTER contains papers presented at a very successful workshop with the same ti­ tle. The event, which was held on September 27-October 1, 2004, was an integral part of the 2004-2005 IMA Thematic Year on "Mathematics of Ma­ terials and Macromolecules: Multiple Scales, Disorder, and Singularities. " We would like to thank Maria-Carme T. Calderer (School of Mathematics, University of Minnesota) and Eugene M. Terentjev (Cavendish Laboratory, University of Cambridge) for their superb role as workshop organizers and editors of the proceedings. We take this opportunity to thank the National Science Foundation for its support of the IMA. Series Editors Douglas N. Arnold, Director of the IMA Arnd Scheel, Deputy Director of the IMA PREFACE The physics of soft matter in particular, focusing on such materials as complex fluids, liquid crystals, elastomers, soft ferroelectrics, foams, gels and particulate systems is an area of intense interest and contemporary study. Soft matter plays a role in a wide variety of important processes and application, as well as in living systems. For example, gel swelling is an essential part of many biological processes such as motility mecha­ nisms in bacteria and the transport and absorption of drugs. Ferroelectrics, liquid crystals, and elastomers are being used to design ever faster switch­ ing devices. Experiments of the last decade have provided a great deal of detailed information on structures and properties of soft matter.

The IMA Hot Topics workshop on compatible spatialdiscretizations was held in 2004. This volume contains original contributions based on the material presented there. A unique feature is the inclusion of work that is representative of the recent developments in compatible discretizations across a wide spectrum of disciplines in computational science. Abstracts and presentation slides from the workshop can be accessed on the internet.

This IMA Volume in Mathematics and its Applications Wireless Communications contains papers based on invited lectures at the very successful IMA Sum­ mer Program on Wireless Communications, held on June 22 - July 1, 2005. We would like to thank Prathima Agrawal (Auburn University), Daniel Matthew Andrews (Lucent Technologies), Philip J. Fleming (Mo­ torola, Inc.), George Yin (Wayne State University), and Lisa Zhang (Lucent Technologies) for their superb role as workshop organizers and editors of the proceedings. We take this opportunity to thank the National Science Foundation for its support of the IMA. Series Editors Douglas N. Arnold, Director of the IMA Arnd Scheel, Deputy Director of the IMA v PREFACE This volume presents papers, based on invited talks given at the 2005 IMA Summer Workshop on Wireless Communications, held at the Institute for Mathematics and Its Applications, University of Minnesota, June 22 ­ July 1, 2005. The conference provided a well blended program to facilitate the com­ munications between academia and the industry, and to bridge the mathe­ matical sciences, engineering, information theory, and communication com­ munities. The emphases were on design and analysis of computationally efficient algorithms to better understand the behavior and to control the wireless telecommunication networks. As an achieve, this volume presents some of the highlights of the conference, and collects papers covering a broad spectrum of topics. All papers have been reviewed.

IMA Volumes 135: Transport in Transition Regimes and 136: Dispersive Transport Equations and Multiscale Models focus on the modeling of processes for which transport is one of the most complicated components. This includes processes that involve a wide range of length scales over different spatio-temporal regions of the problem, ranging from the order of mean-free paths to many times this scale. Consequently, effective modeling techniques require different transport models in each region. The first issue is that of finding efficient simulations techniques, since a fully resolved kinetic simulation is often impractical. One therefore develops homogenization, stochastic, or moment based subgrid models. Another issue is to quantify the discrepancy between macroscopic models and the underlying kinetic description, especially when dispersive effects become macroscopic, for example due to quantum effects in semiconductors and superfluids. These two volumes address these questions in relation to a wide variety of application areas, such as semiconductors, plasmas, fluids, chemically reactive gases, etc.

IMA Volumes 135: Transport in Transition Regimes and 136: Dispersive Transport Equations and Multiscale Models focus on the modeling of processes for which transport is one of the most complicated components. This includes processes that involve a wdie range of length scales over different spatio-temporal regions of the problem, ranging from the order of mean-free paths to many times this scale. Consequently, effective modeling techniques require different transport models in each region. The first issue is that of finding efficient simulations techniques, since a fully resolved kinetic simulation is often impractical. One therefore develops homogenization, stochastic, or moment based subgrid models. Another issue is to quantify the discrepancy between macroscopic models and the underlying kinetic description, especially when dispersive effects become macroscopic, for example due to quantum effects in semiconductors and superfluids. These two volumes address these questions in relation to a wide variety of application areas, such as semiconductors, plasmas, fluids, chemically reactive gases, etc.

This IMA Volume in Mathematics and its Applications GEOMETRIC METHODS IN INVERSE PROBLEMS AND PDE CONTROL contains a selection of articles presented at 2001 IMA Summer Program with the same title. We would like to thank Christopher B. Croke (University of Penn sylva­ nia), Irena Lasiecka (University of Virginia), Gunther Uhlmann (University of Washington), and Michael S. Vogelius (Rutgers University) for their ex­ cellent work as organizers of the two-week summer workshop and for editing the volume. We also take this opportunity to thank the National Science Founda­ tion for their support of the IMA. Series Editors Douglas N. Arnold, Director of the IMA Fadil Santosa, Deputy Director of the IMA v PREFACE This volume contains a selected number of articles based on lectures delivered at the IMA 2001 Summer Program on "Geometric Methods in Inverse Problems and PDE Control. " The focus of this program was some common techniques used in the study of inverse coefficient problems and control problems for partial differential equations, with particular emphasis on their strong relation to fundamental problems of geometry. Inverse coef­ ficient problems for partial differential equations arise in many application areas, for instance in medical imaging, nondestructive testing, and geophys­ ical prospecting. Control problems involving partial differential equations may arise from the need to optimize a given performance criterion, e. g. , to dampen out undesirable vibrations of a structure , or more generally, to obtain a prescribed behaviour of the dynamics.

Symmetries in various forms pervade mathematics and physics. Globally, there are the symmetries of a homogenous space induced by the action of a Lie group. Locally, there are the infinitesimal symmetries induced by differential operators, including not only those of first order but of higher order too. This three-week summer program considered the symmetries preserving various natural geometric structures. Often these structures are themselves derived from partial differential equations whilst their symmetries turn out to be contrained by overdetermined systems. This leads to further topics including separation of variables, conserved quantities, superintegrability, parabolic geometry, represantation theory, the Bernstein-Gelfand-Gelfand complex, finite element schemes, exterior differential systems and moving frames.There are two parts to the Proceedings. The articles in the first part are expository but all contain significant new material. The articles in the second part are concerned with original research. All articles were thoroughly refereed and the range of interrelated work ensures that this will be an extremely useful collection.

This IMA Volume in Mathematics and its Applications TOPICS IN STOCHASTIC ANALYSIS AND NONPARAMETRIC ESTIMATION contains papers that were presented at the IMA Participating Institution conference on "Asymptotic Analysis in Stochastic Processes, Nonparamet­ ric Estimation, and Related Problems" held on September 15-17, 2006 at Wayne State University. The conference, which was one of approximately ten selected each year for partial support by the IMA through its affiliates program, was dedicated to Professor Rafail Z. Khasminskii on the occasion th of his 75 birthday, in recognition of his profound contributions to the field of stochastic processes and nonparametric estimation theory. We are grateful to the participants and, especially, to the conference organizers, for making the event so successful. Pao-Liu Chow, Boris Mor­ dukhovich, and George Yin of the Department of Mathematics at Wayne State University did a superb job organizing this first-rate event and in editing these proceedings. We take this opportunity to thank the Nation al Science Foundation for its support of the IMA.

This IMA Volume in Mathematics and its Applications SYMMETRIC FUNCTIONALS ON RANDOM MATRICES AND RANDOM MATCHINGS PROBLEMS During the academic year 2003–2004, the Institute for Mathematics and its Applications (IMA) held a thematic program on Probability and Stat- tics in Complex Systems. The program focused on large complex systems in which stochasticity plays a signi?cant role. Such systems are very diverse, and the IMA program emphasized systems as varied as the human genome, the internet, and world ?nancial markets. Although quite di?erent, these s- tems have features in common, such as multitudes of interconnecting parts and the availability of large amounts of high-dimensional noisy data. The programemphasized the development and application of common mathem- ical and computational techniques to model and analyze such systems. About 1,000 mathematicians, statisticians, scientists, and engineers participated in the IMA thematic program, including about 50 who were in residence at the IMA during much or all of the year. The present volume was born during the 2003–2004 thematic program at the IMA. The two authors were visitors to the IMA during the program year, withthe?rstauthorresidentforthe entiretenmonths. Thisvolumeisaresult of the authors’ interactions at the IMA, and, especially their discussions with the many other program participants in the program and their involvement in the numerous tutorials, workshops,and seminars held during the year.

In the last decade, there has been a burgeoning of activity in the design and implementation of algorithms for algebraic geometric compuation. Some of these algorithms were originally designed for abstract algebraic geometry, but now are of interest for use in applications and some of these algorithms were originally designed for applications, but now are of interest for use in abstract algebraic geometry.The workshop on Algorithms in Algebraic Geometry that was held in the framework of the IMA Annual Program Year in Applications of Algebraic Geometry by the Institute for Mathematics and Its Applications on September 18-22, 2006 at the University of Minnesota is one tangible indication of the interest. One hundred ten participants from eleven countries and twenty states came to listen to the many talks; discuss mathematics; and pursue collaborative work on the many faceted problems and the algorithms, both symbolic and numberic, that illuminate them.This volume of articles captures some of the spirit of the IMA workshop.

Algorithms in algebraic geometry go hand in hand with software packages that implement them. Together they have established the modern field of computational algebraic geometry which has come to play a major role in both theoretical advances and applications. Over the past fifteen years, several excellent general purpose packages for computations in algebraic geometry have been developed, such as, CoCoA, Singular and Macaulay 2. While these packages evolve continuously, incorporating new mathematical advances, they both motivate and demand the creation of new mathematics and smarter algorithms.This volume reflects the workshop “Software for Algebraic Geometry” held in the week from 23 to 27 October 2006, as the second workshop in the thematic year on Applications of Algebraic Geometry at the IMA. The papers in this volume describe the software packages Bertini, PHClab, Gfan, DEMiCs, SYNAPS, TrIm, Gambit, ApaTools, and the application of Risa/Asir to a conjecture on multiple zeta values. They offer the reader a broad view of current trends in computational algebraic geometry through software development and applications.

This IMA Volume in Mathematics and its Applications DEGENERATE DIFFUSIONS is based on the proceedings of a workshop which was an integral part of the 1990- 91 IMA program on "Phase Transitions and Free Boundaries". The aim of this workshop was to provide some focus in the study of degenerate diffusion equations, and by involving scientists and engineers as well as mathematicians, to keep this focus firmly linked to concrete problems. We thank Wei-Ming Ni, L.A. Peletier and J.L. Vazquez for organizing the meet­ ing. We especially thank Wei-Ming Ni for editing the proceedings. We also take this opportunity to thank those agencies whose financial support made the workshop possible: the Army Research Office, the National Science Foun­ dation, and the Office of Naval Research. A vner Friedman Willard Miller, Jr. PREFACE This volume is the proceedings of the IMA workshop "Degenerate Diffusions" held at the University of Minnesota from May 13 to May 18, 1991.

The articles in this volume are based on recent research on the phenomenon of turbulence in fluid flows collected by the Institute for Mathematics and its Applications. This volume looks into the dynamical properties of the solutions of the Navier-Stokes equations, the equations of motion of incompressible, viscous fluid flows, in order to better understand this phenomenon. Although it is a basic issue of science, it has implications over a wide spectrum of modern technological applications. The articles offer a variety of approaches to the Navier-Stokes problems and related issues. This book should be of interest to both applied mathematicians and engineers.

The articles in this volume cover power system model reduction, transient and voltage stability, nonlinear control, robust stability, computation and optimization and have been written by some of the leading researchers in these areas. This book should be of interest to power and control engineers, and applied mathematicians.

Recent revolutions in the world of finance have created a need for the expertise of research mathematicians in solving problems. The articles in this volume are based on recent research in methods in mathematical finance.

Signal processing applications have burgeoned in the past decade. During the same time, signal processing techniques have matured rapidly and now include tools from many areas of mathematics, computer science, physics, and engineering. This trend will continue as many new signal processing applications are opening up in consumer products and communications systems. In particular, signal processing has been making increasingly sophisticated use of linear algebra on both theoretical and algorithmic fronts. This volume gives particular emphasis to exposing broader contexts of the signal processing problems so that the impact of algorithms and hardware can be better understood; it brings together the writings of signal processing engineers, computer engineers, and applied linear algebraists in an exchange of problems, theories, and techniques. This volume will be of interest to both applied mathematicians and engineers.

Discrete probability theory and the theory of algorithms have become close partners over the last ten years, though the roots of this partnership go back much longer. The papers in this volume address the latest developments in this active field. They are from the IMA Workshops "Probability and Algorithms" and "The Finite Markov Chain Renaissance." They represent the current thinking of many of the world's leading experts in the field.Researchers and graduate students in probability, computer science, combinatorics, and optimization theory will all be interested in this collection of articles. The techniques developed and surveyed in this volume are still undergoing rapid development, and many of the articles of the collection offer an expositionally pleasant entree into a research area of growing importance.

This IMA Volume in Mathematics and its Applications MODELING, MESH GENERATION, AND ADAPTIVE NUMERICAL METHODS FOR PARTIAL DIFFERENTIAL EQUATIONS is based on the proceedings of the 1993 IMA Summer Program "Modeling, Mesh Generation, and Adaptive Numerical Methods for Partial Differential Equations." We thank Ivo Babuska, Joseph E. Flaherty, William D. Hen- shaw, John E. Hopcroft, Joseph E. Oliger, and Tayfun Tezduyar for orga- nizing the workshop and editing the proceedings. We also take this oppor- tunity to thank those agencies whose financial support made the summer program possible: the National Science Foundation (NSF), the Army Re- search Office (ARO) the Department of Energy (DOE), the Minnesota Su- percomputer Institute (MSI), and the Army High Performance Computing Research Center (AHPCRC). A vner Friedman Willard Miller, Jr. xiii PREFACE Mesh generation is one of the most time consuming aspects of com- putational solutions of problems involving partial differential equations. It is, furthermore, no longer acceptable to compute solutions without proper verification that specified accuracy criteria are being satisfied.Mesh gen- eration must be related to the solution through computable estimates of discretization errors. Thus, an iterative process of alternate mesh and so- lution generation evolves in an adaptive manner with the end result that the solution is computed to prescribed specifications in an optimal, or at least efficient, manner. While mesh generation and adaptive strategies are becoming available, major computational challenges remain. One, in particular, involves moving boundaries and interfaces, such as free-surface flows and fluid-structure interactions.

The articles in this volume present the state of the art in a variety of areas of discrete probability, including random walks on finite and infinite graphs, random trees, renewal sequences, Stein's method for normal approximation and Kohonen-type self-organizing maps. This volume also focuses on discrete probability and its connections with the theory of algorithms. Classical topics in discrete mathematics are represented as are expositions that condense and make readable some recent work on Markov chains, potential theory and the second moment method. This volume is suitable for mathematicians and students.

Genetics mapping, physical mapping and DNA sequencing are the three key components of the human and other genome projects. Statistics, mathematics and computing play important roles in all three, as well as in the uses to which the mapping and sequencing data are put. This volume edited by key researchers Mike Waterman and Terry Speed reviews recent progress in the area, with an emphasis on the theory and application of genetic mapping.

This volume explores the interface between two diverse areas of applied mathematics which are both 'customers' of the maximum likelihood methodology; emission tomography and hidden Markov models as an approach to speech understanding. Other areas where maximum likelihood is used in this volume include parsing of text (Jelinek), microstructure of materials (Ji), DNA sequencing (Nelson). Most of the participants were in the main areas of speech or emission density reconstruction.

This IMA Volume in Mathematics and its Applications MATHEMATICAL APPROACHES TO BIOMOLECULAR STRUCTURE AND DYNAMICS is one of the two volumes based on the proceedings of the 1994 IMA Sum­ mer Program on "Molecular Biology" and comprises Weeks 3 and 4 of the four-week program. Weeks 1 and 2 appeared as Volume 81: Genetic Mapping and DNA Sequencing. We thank Jill P. Mesirov, Klaus Schulten, and De Witt Sumners for organizing Weeks 3 and 4 of the workshop and for editing the proceedings. We also take this opportunity to thank the National Institutes of Health (NIH) (National Center for Human Genome Research), the National Science Foundation (NSF) (Biological Instrumen­ tation and Resources), and the Department of Energy (DOE), whose fi­ nancial support made the summer program possible. A vner Friedman Robert Gulliver v PREFACE The revolutionary progress in molecular biology within the last 30 years opens the way to full understanding of the molecular structures and mech­ anisms of living organisms. Interdisciplinary research in mathematics and molecular biology is driven by ever growing experimental, theoretical and computational power. The mathematical sciences accompany and support much of the progress achieved by experiment and computation as well as provide insight into geometric and topological properties of biomolecular structure and processes. This volume consists of a representative sample of the papers presented during the last two weeks of the month-long Institute for Mathematics and Its Applications Summer 1994 Program in Molecular Biology.

This is the eighth volume in the series "Mathematics in Industrial Prob­ lems." The motivation for these volumes is to foster interaction between Industry and Mathematics at the "grass roots level"; that is, at the level of specific problems. These problems come from Industry: they arise from models developed by the industrial scientists in ventures directed at the manufacture of new or improved products. At the same time, these prob­ lems have the potential for mathematical challenge and novelty. To identify such problems, I have visited industries and had discussions with their scientists. Some of the scientists have subsequently presented their problems in the IMA Seminar on Industrial Problems. The book is based on the seminar presentations and on questions raised in subsequent discussions. Each chapter is devoted to one of the talks and is self-contained. The chapters usually provide references to the mathematical literature and a list of open problems that are of interest to industrial scientists. For some problems, a partial solution is indicated briefly. The last chapter of the book contains a short description of solutions to some of the problems raised in the previous volume, as well as references to papers in which such solutions have been published.

This IMA Volume in Mathematics and its Applications CLASSICAL AND MODERN BRANCHING PROCESSES is based on the proceedings with the same title and was an integral part of the 1993-94 IMA program on "Emerging Applications of Probability." We would like to thank Krishna B. Athreya and Peter J agers for their hard work in organizing this meeting and in editing the proceedings. We also take this opportunity to thank the National Science Foundation, the Army Research Office, and the National Security Agency, whose financial support made this workshop possible. A vner Friedman Robert Gulliver v PREFACE The IMA workshop on Classical and Modern Branching Processes was held during June 13-171994 as part of the IMA year on Emerging Appli­ cations of Probability. The organizers of the year long program identified branching processes as one of the active areas in which a workshop should be held. Krish­ na B. Athreya and Peter Jagers were asked to organize this. The topics covered by the workshop could broadly be divided into the following areas: 1. Tree structures and branching processes; 2. Branching random walks; 3. Measure valued branching processes; 4. Branching with dependence; 5. Large deviations in branching processes; 6. Classical branching processes.