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)

Looking back at the years that have passed since the realization of the very first electronic, multi-purpose computers, one observes a tremendous growth in hardware and software performance. Today, researchers and engi neers have access to computing power and software that can solve numerical problems which are not fully understood in terms of existing mathemati cal theory. Thus, computational sciences must in many respects be viewed as experimental disciplines. As a consequence, there is a demand for high quality, flexible software that allows, and even encourages, experimentation with alternative numerical strategies and mathematical models. Extensibil ity is then a key issue; the software must provide an efficient environment for incorporation of new methods and models that will be required in fu ture problem scenarios. The development of such kind of flexible software is a challenging and expensive task. One way to achieve these goals is to in vest much work in the design and implementation of generic software tools which can be used in a wide range of application fields. In order to provide a forum where researchers could present and discuss their contributions to the described development, an International Work shop on Modern Software Tools for Scientific Computing was arranged in Oslo, Norway, September 16-18, 1996. This workshop, informally referred to as Sci Tools '96, was a collaboration between SINTEF Applied Mathe matics and the Departments of Informatics and Mathematics at the Uni versity of Oslo."

OO It is a matter of general consensus that in the last decade the H _ optimization for robust control has dominated the research effort in control systems theory. Much attention has been paid equally to the mathematical instrumentation and the computational aspects. There are several excellent monographs that cover the standard topics in the area. Among the recent issues we have to cite here Linear Robust Control authored by Green and Limebeer (Prentice Hall 1995), Robust Controller Design Using Normalized Coprime Factor Plant Descriptions - by McFarlane and Glover (Springer Verlag 1989), Robust and Optimal Control - by Zhou, Doyle and Glover (Prentice Hall 1996). Thus, when the authors of the present monograph decided to start the work they were confronted with a very rich literature on the subject. However two reasons motivated their initiative. The first concerns the theory in which the whole development of the book was embedded. As is well known, there are several ways of approach oo ing H and robust control theory. Here we mention three relevant direc tions chronologically ordered: a) the first makes use of a generalization of the Beurling-Lax theorem to Krein spaces; b) the second makes use of a generalization of Nevanlinna-Pick interpolation theory and commutant lifting theorem; c) the third, and probably the most attractive from an el evate engineering viewpoint, is the two Riccati equations based approach which offers a complete solution in state space form."

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.

Typing plays an important role in software development. Types can be consid ered as weak specifications of programs and checking that a program is of a certain type provides a verification that a program satisfies such a weak speci fication. By translating a problem specification into a proposition in constructive logic, one can go one step further: the effectiveness and unifonnity of a con structive proof allows us to extract a program from a proof of this proposition. Thus by the "proposition-as-types" paradigm one obtains types whose elements are considered as proofs. Each of these proofs contains a program correct w.r.t. the given problem specification. This opens the way for a coherent approach to the derivation of provably correct programs. These features have led to a "typeful" programming style where the classi cal typing concepts such as records or (static) arrays are enhanced by polymor phic and dependent types in such a way that the types themselves get a complex mathematical structure. Systems such as Coquand and Huet's Calculus of Con structions are calculi for computing within extended type systems and provide a basis for a deduction oriented mathematical foundation of programming. On the other hand, the computational power and the expressive (impred icativity !) of these systems makes it difficult to define appropriate semantics.

Given a function x(t) E c{n) [a, bj, points a = al < a2 < ...< ar = b and subsets aj of {0,1,"',n -1} with L:j=lcard(aj) = n, the classical interpolation problem is to find a polynomial P - (t) of degree at most (n - 1) n l such that P~~l(aj) = x{i)(aj) for i E aj, j = 1,2," r. In the first four chapters of this monograph we shall consider respectively the cases: the Lidstone interpolation (a = 0, b = 1, n = 2m, r = 2, al = a2 = {a, 2", 2m - 2}), the Hermite interpolation (aj = {a, 1,' ", kj - I}), the Abel - Gontscharoff interpolation (r = n, ai ~ ai+l, aj = {j - I}), and the several particular cases of the Birkhoff interpolation. For each of these problems we shall offer: (1) explicit representations of the interpolating polynomial; (2) explicit representations of the associated error function e(t) = x(t) - Pn-l(t); and (3) explicit optimal/sharp constants Cn,k so that the inequalities k I e{k)(t) I < C k(b -at- max I x{n)(t) I, 0 n - 1 n -, a$t$b - are satisfied. In addition, for the Hermite interpolation we shall provide explicit opti- mal/sharp constants C(n,p, v) so that the inequality II e(t) lip:::; C(n,p, v) II x{n)(t) 1111, p, v ~ 1 holds.

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 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.

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."

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.

Perturbation methods are widely used in the study of physically significant differential equations, which arise in Applied Mathematics, Physics and Engineering.; Background material is provided in each chapter along with illustrative examples, problems, and solutions.; A comprehensive bibliography and index complete the work.; Covers an important field of solutions for engineering and the physical sciences.; To allow an interdisciplinary readership, the book focuses almost exclusively on the procedures and the underlying ideas and soft pedal the proofs; Dr. Bhimsen K. Shivamoggi has authored seven successful books for various publishers like John Wiley & Sons and Kluwer Academic Publishers.

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.

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

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.

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

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.

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.

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.

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.

With contributions by specialists in optimization and practitioners in the fields of aerospace engineering, chemical engineering, and fluid and solid mechanics, the major themes include an assessment of the state of the art in optimization algorithms as well as challenging applications in design and control, in the areas of process engineering and systems with partial differential equation models.

These are the proceedings of the 19th international conference on domain decomposition methods in science and engineering. Domain decomposition methods are iterative methods for solving the often very large linear or nonlinear systems of algebraic equations that arise in various problems in mathematics, computational science, engineering and industry. They are designed for massively parallel computers and take the memory hierarchy of such systems into account. This is essential for approaching peak floating point performance. There is an increasingly well-developed theory which is having a direct impact on the development and improvement of these algorithms.