This monograph is a slightly revised version of my PhD thesis [86], com pleted in the Department of Computer Science at the University of Edin burgh in June 1988, with an additional chapter summarising more recent developments. Some of the material has appeared in the form of papers [50,88]. The underlying theme of the monograph is the study of two classical problems: counting the elements of a finite set of combinatorial structures, and generating them uniformly at random. In their exact form, these prob lems appear to be intractable for many important structures, so interest has focused on finding efficient randomised algorithms that solve them ap proxim~ly, with a small probability of error. For most natural structures the two problems are intimately connected at this level of approximation, so it is natural to study them together. At the heart of the monograph is a single algorithmic paradigm: sim ulate a Markov chain whose states are combinatorial structures and which converges to a known probability distribution over them. This technique has applications not only in combinatorial counting and generation, but also in several other areas such as statistical physics and combinatorial optimi sation. The efficiency of the technique in any application depends crucially on the rate of convergence of the Markov chain.

This book is devoted to the relation between two different concepts of integrability: the complete integrability of complex analytical Hamiltonian systems and the integrability of complex analytical linear differential equations. For linear differential equations, integrability is made precise within the framework of differential Galois theory. The connection of these two integrability notions is given by the variational equation (i.e. linearized equation) along a particular integral curve of the Hamiltonian system. The underlying heuristic idea, which motivated the main results presented in this monograph, is that a necessary condition for the integrability of a Hamiltonian system is the integrability of the variational equation along any of its particular integral curves. This idea led to the algebraic non-integrability criteria for Hamiltonian systems. These criteria can be considered as generalizations of classical non-integrability results by Poincare and Lyapunov, as well as more recent results by Ziglin and Yoshida. Thus, by means of the differential Galois theory it is not only possible to understand all these approaches in a unified way but also to improve them. Several important applications are also included: homogeneous potentials, Bianchi IX cosmological model, three-body problem, Henon-Heiles system, etc. The book is based on the original joint research of the author with J.M. Peris, J.P. Ramis and C. Simo, but an effort was made to present these achievements in their logical order rather than their historical one. The necessary background on differential Galois theory and Hamiltonian systems is included, and several new problems and conjectures which open new lines of research are proposed. - - - The book is an excellent introduction to non-integrability methods in Hamiltonian mechanics and brings the reader to the forefront of research in the area. The inclusion of a large number of worked-out examples, many of wide applied interest, is commendable. There are many historical references, and an extensive bibliography. (Mathematical Reviews) For readers already prepared in the two prerequisite subjects [differential Galois theory and Hamiltonian dynamical systems], the author has provided a logically accessible account of a remarkable interaction between differential algebra and dynamics. (Zentralblatt MATH)

With this proceedings volume a new series of publications is started which will present the results of interdisciplinary research activities in the fields of materials science, coupling of biological and electronic systems and commu nication ergonomy. It will contain the contributions of the participants of the caesarium, a conference caesar will organize annually. The 1 st caesarium was held in Bonn on November 17-19, 1999 concentrating on Smart Materials. With the caesarium the recently founded research center caesar (center of advanced european studies and research) creates a forum for discussion of new developments in its fields of activities. caesar is an international research center, focusing on applied, interdisciplinary research projects in the areas of science and engineering. It was established as an independent foundation under private law as part of the compensatory actions under the Berlin/Bonn law of April 26, 1994 to support the structural change in the region of Bonn, when the German Government moved from Bonn to Berlin. The main donors of caesar are the Federal Republic of Germany and the State of North Rhine-Westphalia. A Board consisting of state and federal leg islators, members from the research community and industry and a Scientific Advisory Council assist caesar in all decisions concerning administration and research.

This book gives a systematic account of the facts concerning complexes of differential operators on differentiable manifolds. The central place is occupied by the study of general complexes of differential operators between sections of vector bundles. Although the global situation often contains nothing new as compared with the local one (that is, complexes of partial differential operators on an open subset of ]Rn), the invariant language allows one to simplify the notation and to distinguish better the algebraic nature of some questions. In the last 2 decades within the general theory of complexes of differential operators, the following directions were delineated: 1) the formal theory; 2) the existence theory; 3) the problem of global solvability; 4) overdetermined boundary problems; 5) the generalized Lefschetz theory of fixed points, and 6) the qualitative theory of solutions of overdetermined systems. All of these problems are reflected in this book to some degree. It is superfluous to say that different directions sometimes whimsically intersect. Considerable attention is given to connections and parallels with the theory of functions of several complex variables. One of the reproaches avowed beforehand by the author consists of the shortage of examples. The framework of the book has not permitted their number to be increased significantly. Certain parts of the book consist of results obtained by the author in 1977-1986. They have been presented in seminars in Krasnoyarsk, Moscow, Ekaterinburg, and N ovosi birsk.

'Et moi, ..., si j'avait su comment en revenir, One service mathematics has rendered the je n'y se.rais point aile.' human race. It has put common sense back Jules Verne where it belongs, on be topmost shelf next to the dusty canister labelled 'disc: arded non sense'. The series is divergent; therefore we may be able to do something with it. Eric T. Bell O. Heaviside Mathematics is a tool for thought. A highly necessary tool in a world where both feedback and non linearities abound. Similarly, all kinds of parts of mathematics serve as tools for other parts and for other sciences. Applying a simple rewriting rule to the quote on the right above one finds such statements as: 'One service topology has rendered mathematical physics .. .'; 'One service logic has rendered com puter science .. .'; 'One service category theory has rendered mathematics .. .'. All arguably true. And all statements obtainable this way form part of the raison d'etre of this series."

The aim of this monograph is to introduce the reader to modern methods of projective geometry involving certain techniques of formal geometry. Some of these methods are illustrated in the first part through the proofs of a number of results of a rather classical flavor, involving in a crucial way the first infinitesimal neighbourhood of a given subvariety in an ambient variety. Motivated by the first part, in the second formal functions on the formal completion X/Y of X along a closed subvariety Y are studied, particularly the extension problem of formal functions to rational functions.
The formal scheme X/Y, introduced to algebraic geometry by Zariski and Grothendieck in the 1950s, is an analogue of the concept of a tubular neighbourhood of a submanifold of a complex manifold. It is very well suited to study the given embedding Y\subset X. The deep relationship of formal geometry with the most important connectivity theorems in algebraic geometry, or with complex geometry, is also studied. Some of the formal methods are illustrated and applied to homogeneous spaces.
The book contains a lot of results obtained over the last thirty years, many of which never appeared in a monograph or textbook. It addresses to algebraic geometers as well as to those interested in using methods of algebraic geometry.

This book is a comprehensive presentation of recent results and developments on several widely used transforms and their fast algorithms. In many cases, new options are provided for improved or new fast algorithms, some of which are not well known in the digital signal processing community. The book is suitable as a textbook for senior undergraduate and graduate courses in digital signal processing. It may also serve as an excellent self-study reference for electrical engineers and applied mathematicians whose work is related to the fields of electronics, signal processing, image and speech processing, or digital design and communication.

The conference Challenges In Scientific Computing (CISC 2002) took place from October, 2 to 5, 2002. The hosting institution was the Weierstrass Insti tute for Applied Analysis and Stochastics (WIAS) in Berlin, Germany. The main purpose of this meeting was to draw together researchers working in the fields of numerical analysis and scientific computing with a common interest in the numerical treatment and the computational solution of systems of nonlinear partial differential equations arising from applications of physical and engineering problems. The main focus of the conference was on the problem class of non linear transport/diffusion/reaction systems, chief amongst these being: the Navier-Stokes equations, semiconductor-device equations and porous media flow problems. The emphasis was on unsolved problems, challenging open questions from applications and assessing the various numerical methods used to handle them, rather than concentrate on accurate results from "solved" problems. Thanks to the participants it was an interesting meeting. The presentations stimulated exchanging ideas and lively discussions. This proceedings comprises 13 papers form the conference, ranging from numerical methods for flow problems, multigrid methods, semiconductor and microwave simulation, solution methods, finite element analysis to software aspects. This interesting conference would not have been possible without the help of the staff of the WIAS. I thank all participants, and all our supporters, especially those not onstage, for making the conference a success.

This volume represents the refereed proceedings of the Fifth International Conference on Finite Fields and Applications (F q5) held at the University of Augsburg (Germany) from August 2-6, 1999, and hosted by the Department of Mathematics. The conference continued a series of biennial international conferences on finite fields, following earlier conferences at the University of Nevada at Las Vegas (USA) in August 1991 and August 1993, the University ofGlasgow (Scotland) in July 1995, and the University ofWaterloo (Canada) in August 1997. The Organizing Committee of F q5 comprised Thomas Beth (University ofKarlsruhe), Stephen D. Cohen (University of Glasgow), Dieter Jungnickel (University of Augsburg, Chairman), Alfred Menezes (University of Waterloo), Gary L. Mullen (Pennsylvania State University), Ronald C. Mullin (University of Waterloo), Harald Niederreiter (Austrian Academy of Sciences), and Alexander Pott (University of Magdeburg). The program ofthe conference consisted offour full days and one halfday ofsessions, with 11 invited plenary talks andover80contributedtalks that re- quired three parallel sessions. This documents the steadily increasing interest in finite fields and their applications. Finite fields have an inherently fasci- nating structure and they are important tools in discrete mathematics. Their applications range from combinatorial design theory, finite geometries, and algebraic geometry to coding theory, cryptology, and scientific computing. A particularly fruitful aspect is the interplay between theory and applications which has led to many new perspectives in research on finite fields.

Inverse problems in wave propagation occur in geophysics, ocean acoustics, civil and environmental engineering, ultrasonic non-destructive testing, biomedical ultrasonics, radar, astrophysics, as well as other areas of science and technology. The papers in this volume cover these scientific and technical topics, together with fundamental mathematical investigations of the relation between waves and scatterers.

This book contains 58 papers from among the 68 papers presented at the Fifth International Conference on Fibonacci Numbers and Their Applications which was held at the University of St. Andrews, St. Andrews, Fife, Scotland from July 20 to July 24, 1992. These papers have been selected after a careful review by well known referees in the field, and they range from elementary number theory to probability and statistics. The Fibonacci numbers and recurrence relations are their unifying bond. It is anticipated that this book, like its four predecessors, will be useful to research workers and graduate students interested in the Fibonacci numbers and their applications. June 5, 1993 The Editors Gerald E. Bergum South Dakota State University Brookings, South Dakota, U.S.A. Alwyn F. Horadam University of New England Armidale, N.S.W., Australia Andreas N. Philippou Government House Z50 Nicosia, Cyprus xxv THE ORGANIZING COMMITTEES LOCAL COMMITTEE INTERNATIONAL COMMITTEE Campbell, Colin M., Co-Chair Horadam, A.F. (Australia), Co-Chair Phillips, George M., Co-Chair Philippou, A.N. (Cyprus), Co-Chair Foster, Dorothy M.E. Ando, S. (Japan) McCabe, John H. Bergum, G.E. (U.S.A.) Filipponi, P. (Italy) O'Connor, John J.

These are the proceedings of the international conference on "Nonlinear numerical methods and Rational approximation II" organised by Annie Cuyt at the University of Antwerp (Belgium), 05-11 September 1993. It was held for the third time in Antwerp at the conference center of UIA, after successful meetings in 1979 and 1987 and an almost yearly tradition since the early 70's. The following figures illustrate the growing number of participants and their geographical dissemination. In 1993 the Belgian scientific committee consisted of A. Bultheel (Leuven), A. Cuyt (Antwerp), J. Meinguet (Louvain-Ia-Neuve) and J.-P. Thiran (Namur). The conference focused on the use of rational functions in different fields of Numer ical Analysis. The invited speakers discussed "Orthogonal polynomials" (D. S. Lu binsky), "Rational interpolation" (M. Gutknecht), "Rational approximation" (E. B. Saff), "Pade approximation" (A. Gonchar) and "Continued fractions" (W. B. Jones). In contributed talks multivariate and multidimensional problems, applications and implementations of each main topic were considered. To each of the five main topics a separate conference day was devoted and a separate proceedings chapter compiled accordingly. In this way the proceedings reflect the organisation of the talks at the conference. Nonlinear numerical methods and rational approximation may be a nar row field for the outside world, but it provides a vast playground for the chosen ones. It can fascinate specialists from Moscow to South-Africa, from Boulder in Colorado and from sunny Florida to Zurich in Switzerland."

This volume is based on the outcome of a workshop held at the Institute for Mathematics and Its Applications. This institute was founded to promote the interchange of ideas between applied mathematics and the other sciences, and this volume fits into that framework by bringing together the ideas of mathematicians, physicists and chemists in the area of multiparticle scattering theory. The correct formulation of scattering theory for two-body collisions is now well worked out, but systems with three or more particles still present fundamental challenges, both in the formulations of the problem and in the interpretation of computational results. The book begins with two tutorials, one on mathematical issues, including cluster decompositions and asymptotic completeness in N-body quantum systems, and the other on computational approaches to quantum mechanics and time evolution operators, classical action, collisions in laser fields and in magnetic fields, laser-induced processes, barrier resonances, complex dilated expansions, effective potentials for nuclear collisions, long-range potentials, and the Pauli Principle.

The advent of fast and sophisticated computer graphics has brought dynamic and interactive images under the control of professional mathematicians and mathematics teachers. This volume in the NATO Special Programme on Advanced Educational Technology takes a comprehensive and critical look at how the computer can support the use of visual images in mathematical problem solving. The contributions are written by researchers and teachers from a variety of disciplines including computer science, mathematics, mathematics education, psychology, and design. Some focus on the use of external visual images and others on the development of individual mental imagery. The book is the first collected volume in a research area that is developing rapidly, and the authors pose some challenging new questions.

Polymers occur in many different states and their physical properties are strongly correlated with their conformations. The theoretical investigation of the conformational properties of polymers is a difficult task and numerical methods play an important role in this field. This book contains contributions from a workshop on numerical methods for polymeric systems, held at the IMA in May 1996, which brought together chemists, physicists, mathematicians, computer scientists and statisticians with a common interest in numerical methods. The two major approaches used in the field are molecular dynamics and Monte Carlo methods, and the book includes reviews of both approaches as well as applications to particular polymeric systems. The molecular dynamics approach solves the Newtonian equations of motion of the polymer, giving direct information about the polymer dynamics as well as about static properties. The Monte Carlo approaches discussed in this book all involve sampling along a Markov chain defined on the configuration space of the system. An important feature of the book is the treatment of Monte Carlo methods, including umbrella sampling and multiple Markov chain methods, which are useful for strongly interacting systems such as polymers at low temperatures and in compact phases. The book is of interest to workers in polymer statistical mechanics and also to a wider audience interested in numerical methods and their application in polymeric systems.

In recent years kinetic theory has developed in many areas of the physical sciences and engineering, and has extended the borders of its traditional fields of application. This monograph is a self-contained presentation of such recently developed aspects of kinetic theory, as well as a comprehensive account of the fundamentals of the theory. Emphasizing modeling techniques and numerical methods, the book provides a unified treatment of kinetic equations not found in more focused works. Specific applications presented include plasma kinetic models, traffic flow models, granular media models, and coagulation-fragmentation problems. The work may be used for self-study, as a reference text, or in graduate-level courses in kinetic theory and its applications.

My book "Asymptotic Expansions for Ordinary Differential Equations" published in 1965 is out of print. In the almost 20 years since then, the subject has grown so much in breadth and in depth that an account of the present state of knowledge of all the topics discussed there could not be fitted into one volume without resorting to an excessively terse style of writing. Instead of undertaking such a task, I have concentrated, in this exposi tion, on the aspects of the asymptotic theory with which I have been particularly concerned during those 20 years, which is the nature and structure of turning points. As in Chapter VIII of my previous book, only linear analytic differential equations are considered, but the inclusion of important new ideas and results, as well as the development of the neces sary background material have made this an exposition of book length. The formal theory of linear analytic differential equations without a parameter near singularities with respect to the independent variable has, in recent years, been greatly deepened by bringing to it methods of modern algebra and topology. It is very probable that many of these ideas could also be applied to the problems concerning singularities with respect to a parameter, and I hope that this will be done in the near future. It is less likely, however, that the analytic, as opposed to the formal, aspects of turning point theory will greatly benefit from such an algebraization."

This work is based on the lecture notes of the course M742: Topics in Partial Dif- ferential Equations, which I taught in the Spring semester of 1997 at Indiana Univer- sity. My main intention in this course was to give a concise introduction to solving two-dimensional compressibleEuler equations with Riemann data, which are special Cauchy data. This book covers new theoretical developments in the field over the past decade or so. Necessary knowledge of one-dimensional Riemann problems is reviewed and some popularnumerical schemes are presented. Multi-dimensional conservation laws are more physical and the time has come to study them. The theory onbasicone-dimensional conservation laws isfairly complete providing solid foundation for multi-dimensional problems. The rich theory on ellip- tic and parabolic partial differential equations has great potential in applications to multi-dimensional conservation laws. And faster computers make itpossible to reveal numerically more details for theoretical pursuitin multi-dimensional problems. Overview and highlights Chapter 1is an overview ofthe issues that concern us inthisbook. It lists theEulersystemandrelatedmodelssuch as theunsteady transonic small disturbance, pressure-gradient, and pressureless systems. Itdescribes Mach re- flection and the von Neumann paradox. In Chapters 2-4, which form Part I of the book, we briefly present the theory of one-dimensional conservation laws, which in- cludes solutions to the Riemann problems for the Euler system and general strictly hyperbolic and genuinely nonlinearsystems, Glimm's scheme, and large-time asymp- toties.

Boundary problems constitute an essential field of common mathematical interest. The intention of this volume is to highlight several analytic and geometric aspects of boundary problems with special emphasis on their interplay. It includes surveys on classical topics presented from a modern perspective as well as reports on current research.

The collection splits into two related groups:

- analysis and geometry of geometric operators and their index theory

- elliptic theory of boundary value problems and the Shapiro-Lopatinsky condition

From the reviews: "This is an excellent exposition about abelian Reidemeister torsions for three-manifolds." -Zentralblatt Math

"This monograph contains a wealth of information many topologists will find very handy. ...Many of the new points of view pioneered by Turaev are gradually becoming mainstream and are spreading beyond the pure topology world. This monograph is a timely and very useful addition to the scientific literature." -Mathematical Reviews

Hyperbolic partial differential equations describe phenomena of material or wave transport in physics, biology and engineering, especially in the field of fluid mechanics. The mathematical theory of hyperbolic equations has recently made considerable progress. Accurate and efficient numerical schemes for computation have been and are being further developed.
This two-volume set of conference proceedings contains about 100 refereed and carefully selected papers. The books are intended for researchers and graduate students in mathematics, science and engineering interested in the most recent results in theory and practice of hyperbolic problems.
Applications touched in these proceedings concern one-phase and multiphase fluid flow, phase transitions, shallow water dynamics, elasticity, extended thermodynamics, electromagnetism, classical and relativistic magnetohydrodynamics, cosmology. Contributions to the abstract theory of hyperbolic systems deal with viscous and relaxation approximations, front tracking and wellposedness, stability of shock profiles and multi-shock patterns, traveling fronts for transport equations. Numerically oriented articles study finite difference, finite volume, and finite element schemes, adaptive, multiresolution, and artificial dissipation methods.

This monograph is intended to provide a comprehensive description of the rela tion between kinetic theory and fluid dynamics for a time-independent behavior of a gas in a general domain. A gas in a steady (or time-independent) state in a general domain is considered, and its asymptotic behavior for small Knudsen numbers is studied on the basis of kinetic theory. Fluid-dynamic-type equations and their associated boundary conditions, together with their Knudsen-layer corrections, describing the asymptotic behavior of the gas for small Knudsen numbers are presented. In addition, various interesting physical phenomena derived from the asymptotic theory are explained. The background of the asymptotic studies is explained in Chapter 1, accord ing to which the fluid-dynamic-type equations that describe the behavior of a gas in the continuum limit are to be studied carefully. Their detailed studies depending on physical situations are treated in the following chapters. What is striking is that the classical gas dynamic system is incomplete to describe the behavior of a gas in the continuum limit (or in the limit that the mean free path of the gas molecules vanishes). Thanks to the asymptotic theory, problems for a slightly rarefied gas can be treated with the same ease as the corresponding classical fluid-dynamic problems. In a rarefied gas, a temperature field is di rectly related to a gas flow, and there are various interesting phenomena which cannot be found in a gas in the continuum limit.

This volume contains the proceedings of the Colloquium "Analysis, Manifolds and Physics" organized in honour of Yvonne Choquet-Bruhat by her friends, collaborators and former students, on June 3, 4 and 5, 1992 in Paris. Its title accurately reflects the domains to which Yvonne Choquet-Bruhat has made essential contributions. Since the rise of General Relativity, the geometry of Manifolds has become a non-trivial part of space-time physics. At the same time, Functional Analysis has been of enormous importance in Quantum Mechanics, and Quantum Field Theory. Its role becomes decisive when one considers the global behaviour of solutions of differential systems on manifolds. In this sense, General Relativity is an exceptional theory in which the solutions of a highly non-linear system of partial differential equations define by themselves the very manifold on which they are supposed to exist. This is why a solution of Einstein's equations cannot be physically interpreted before its global behaviour is known, taking into account the entire hypothetical underlying manifold. In her youth, Yvonne Choquet-Bruhat contributed in a spectacular way to this domain stretching between physics and mathematics, when she gave the proof of the existence of solutions to Einstein's equations on differential manifolds of a quite general type. The methods she created have been worked out by the French school of mathematics, principally by Jean Leray. Her first proof of the local existence and uniqueness of solutions of Einstein's equations inspired Jean Leray's theory of general hyperbolic systems.

These proceedings collect the papers accepted for presentation at the bien nial IMA Conference on the Mathematics of Surfaces, held in the University of Cambridge, 4-7 September 2000. While there are many international con ferences in this fruitful borderland of mathematics, computer graphics and engineering, this is the oldest, the most frequent and the only one to concen trate on surfaces. Contributors to this volume come from twelve different countries in Eu rope, North America and Asia. Their contributions reflect the wide diversity of present-day applications which include modelling parts of the human body for medical purposes as well as the production of cars, aircraft and engineer ing components. Some applications involve design or construction of surfaces by interpolating or approximating data given at points or on curves. Others consider the problem of 'reverse engineering'-giving a mathematical descrip tion of an already constructed object. We are particularly grateful to Pamela Bye (at the Institue of Mathemat ics and its Applications) for help in making arrangements; Stephanie Harding and Karen Barker (at Springer Verlag, London) for publishing this volume and to Kwan-Yee Kenneth Wong (Cambridge) for his heroic help with com piling the proceedings and for dealing with numerous technicalities arising from large and numerous computer files. Following this Preface is a listing of the programme committee who with the help of their colleagues did much work in refereeing the papers for these proceedings.

In this monograph the theory and methods of solving inverse Stefan problems for quasilinear parabolic equations in regions with free boundaries are developed. The study of this new class of ill-posed problems is motivated by the needs of the mod eling and control of nonlinear processes with phase transitions in thermophysics and mechanics of continuous media. Inverse Stefan problems are important for the perfection of technologies both in high temperature processes (e.g., metallurgy, the aircraft industry, astronautics and power engineering) and in hydrology, exploitation of oil-gas fields, etc. The proposed book will complete a gap in these subjects in the preceding re searches of ill-posed problems. It contains the new theoretical and applied studies of a wide class of inverse Stefan problems. The statements of such problems on the determination of boundary functions and coefficients of the equation are considered for different types of additional information about their solution. The variational method of obtaining stable approximate solutions is proposed and established. It is implemented by an efficient computational scheme of descriptive regularization. This algorithm utilizes a priori knowledge of the qualitative structure of the sought solution and ensures a substantial saving in computational costs. It is tested on model and applied problems in nonlinear thermophysics. In particular, the results of calculations for important applications in continuous casting of ingots and in the melting of a plate with the help of laser technology are presented."