Since its very existence as a separate field within computer science, computer graphics had to make extensive use of non-trivial mathematics, for example, projective geometry, solid modelling, and approximation theory. This interplay of mathematics and computer science is exciting, but also makes it difficult for students and researchers to assimilate or maintain a view of the necessary mathematics. The possibilities offered by an interdisciplinary approach are still not fully utilized. This book gives a selection of contributions to a workshop held near Genoa, Italy, in October 1991, where a group of mathematicians and computer scientists gathered to explore ways of extending the cooperation between mathematics and computer graphics.

The NATO Advanced Study Institute on "Computer algorithms for solving linear algebraic equations: the state of the art" was held September 9-21, 1990, at II Ciocco, Barga, Italy. It was attended by 68 students (among them many well known specialists in related fields!) from the following countries: Belgium, Brazil, Canada, Czechoslovakia, Denmark, France, Germany, Greece, Holland, Hungary, Italy, Portugal, Spain, Turkey, UK, USA, USSR, Yugoslavia. Solving linear equations is a fundamental task in most of computational mathematics. Linear systems which are now encountered in practice may be of very large dimension and their solution can still be a challenge in terms of the requirements of accuracy or reasonable computational time. With the advent of supercomputers with vector and parallel features, algorithms which were previously formulated in a framework of sequential operations often need a completely new formulation, and algorithms that were not recommended in a sequential framework may become the best choice. The aim of the ASI was to present the state of the art in this field. While not all important aspects could be covered (for instance there is no presentation of methods using interval arithmetic or symbolic computation), we believe that most important topics were considered, many of them by leading specialists who have contributed substantially to the developments in these fields.

This book is of interest to mathematicians, geologists, engineers and, in general, researchers and post graduate students involved in spline function theory, surface fitting problems or variational methods. From reviews: The book is well organized, and the English is very good. I recommend the book to researchers in approximation theory, and to anyone interested in bivariate data fitting." (L.L. Schumaker, Mathematical Reviews, 2005).

Geometric dynamics is a tool for developing a mathematical representation of real world phenomena, based on the notion of a field line described in two ways: -as the solution of any Cauchy problem associated to a first-order autonomous differential system; -as the solution of a certain Cauchy problem associated to a second-order conservative prolongation of the initial system. The basic novelty of our book is the discovery that a field line is a geodesic of a suitable geometrical structure on a given space (Lorentz-Udri~te world-force law). In other words, we create a wider class of Riemann-Jacobi, Riemann-Jacobi-Lagrange, or Finsler-Jacobi manifolds, ensuring that all trajectories of a given vector field are geodesics. This is our contribution to an old open problem studied by H. Poincare, S. Sasaki and others. From the kinematic viewpoint of corpuscular intuition, a field line shows the trajectory followed by a particle at a point of the definition domain of a vector field, if the particle is sensitive to the related type of field. Therefore, field lines appear in a natural way in problems of theoretical mechanics, fluid mechanics, physics, thermodynamics, biology, chemistry, etc.

In November 2001 the Mathematical Research Center at Oberwolfach, Germany, hosted the third Conference on Mathematical Models and Numerical Simulation in Electronic Industry. It brought together researchers in mathematics, electrical engineering and scientists working in industry.

The contributions to this volume try to bridge the gap between basic and applied mathematics, research in electrical engineering and the needs of industry.

This book is devoted to fully developing and comparing the two main approaches to the numerical approximation of controls for wave propagation phenomena: the continuous and the discrete. This is accomplished in the abstract functional setting of conservative semigroups.The main results of the work unify, to a large extent, these two approaches, which yield similaralgorithms and convergence rates. The discrete approach, however, gives not only efficient numerical approximations of the continuous controls, but also ensures some partial controllability properties of the finite-dimensional approximated dynamics. Moreover, it has the advantage of leading to iterative approximation processes that converge without a limiting threshold in the number of iterations. Such a threshold, which is hard to compute and estimate in practice, is a drawback of the methods emanating from the continuous approach. To complement this theory, the book provides convergence results for the discrete wave equation when discretized using finite differences and proves the convergence of the discrete wave equation with non-homogeneous Dirichlet conditions. The first book to explore these topics in depth, "On the Numerical Approximations of Controls for Waves" has rich applications to data assimilation problems and will be of interest to researchers who deal with wave approximations.

'Et moi, ... si favait III mmment en revenir, One service mathematics has rendered the je n'y serais point aile: ' human race. It has put CXlUImon sense back Iules Verne where it belongs. on the topmost shelf next to the dUlty canister lahelled 'discarded non- The series i. divergent; therefore we may be able to do something with it. Eric T. Bell O. Hesvi.ide 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't tre of this series."

22 papers on control of nonlinear partial differential equations highlight the area from a broad variety of viewpoints. They comprise theoretical considerations such as optimality conditions, relaxation, or stabilizability theorems, as well as the development and evaluation of new algorithms. A significant part of the volume is devoted to applications in engineering, continuum mechanics and population biology.

Our aim in writing this book was to provide an extensive set of C++ programs for solving basic numerical problems with verification of the results. This C++ Toolbox for Verified Computing I is the C++ edition of the Numerical Toolbox for Verified Computing l. The programs of the original edition were written in PASCAL-XSC, a PASCAL eXtension for Scientific Computation. Since we published the first edition we have received many requests from readers and users of our tools for a version in C++. We take the view that C++ is growing in importance in the field of numeri cal computing. C++ includes C, but as a typed language and due to its modern concepts, it is superior to C. To obtain the degree of efficiency that PASCAL-XSC provides, we used the C-XSC library. C-XSC is a C++ class library for eXtended Scientific Computing. C++ and the C-XSC library are an adequate alternative to special XSC-Ianguages such as PASCAL-XSC or ACRITH-XSC. A shareware version of the C-XSC library and the sources of the toolbox programs are freely available via anonymous ftp or can be ordered against reimbursement of expenses. The programs of this book do not require a great deal of insight into the features of C++. Particularly, object oriented programming techniques are not required."

During the past two decades representations of noncompact Lie groups and Lie algebras have been studied extensively, and their application to other branches of mathematics and to physical sciences has increased enormously. Several theorems which were proved in the abstract now carry definite mathematical and physical sig nificance. Several physical observations which were not understood before are now explained in terms of models based on new group-theoretical structures such as dy namical groups and Lie supergroups. The workshop was designed to bring together those mathematicians and mathematical physicists who are actively working in this broad spectrum of research and to provide them with the opportunity to present their recent results and to discuss the challenges facing them in the many problems that remain. The objective of the workshop was indeed well achieved. This book contains 31 lectures presented by invited participants attending the NATO Advanced Research Workshop held in San Antonio, Texas, during the week of January 3-8, 1993. The introductory article by the editors provides a brief review of the concepts underlying these lectures (cited by author *]) and mentions some of their applications. The articles in the book are grouped under the following general headings: Lie groups and Lie algebras, Lie superalgebras and Lie supergroups, and Quantum groups, and are arranged in the order in which they are cited in the introductory article. We are very thankful to Dr."

In the six years since the first edition of this book was published, the field of Structural Complexity has grown quite a bit. However, we are keeping this volume at the same basic level that it had in the first edition, and the only new result incorporated as an appendix is the closure under complementation of nondeterministic space classes, which in the previous edition was posed as an open problem. This result was already included in our Volume II, but we feel that due to the basic nature of the result, it belongs to this volume. There are of course other important results obtained during these last six years. However, as they belong to new areas opened in the field they are outside the scope of this fundamental volume. Other changes in this second edition are the update of some Bibliograph ical Remarks and references, correction of many mistakes and typos, and a renumbering of the definitions and results. Experience has shown us that this new numbering is a lot more friendly, and several readers have confirmed this opinion. For the sake of the reader of Volume II, where all references to Volume I follow the old numbering, we have included here a table indicating the new number corresponding to each of the old ones."

One of the most challenging problems of modern engineering is undoubtedly the prediction of hypersonic flows around space vehicles in reentry conditions. Indeed, the difficulties are numerous: first of all, these flows are very difficult to model, since very complex physical and chemical phenomena take place during the reentry phase; secondly, temperature, velocity and enthalpy are very high and densities are very low, making the reentry process very difficult to reproduce in ground-based experiments. The past three decades have seen important efforts in computational fluid dynam ics relying on the use of supercomputers to simulate these very complicated flows. The numerical simulation based on imperfect models and methods which were es sentially designed for transonic and supersonic flows has still a long way to go in order to be able to predict these hypersonic reentry flows very accurately. This situation has motivated very strong international cooperative efforts with, as the most visible consequences, the EuropelUnited States Short Courses on Hy personics, which were held in Paris, in 1987 [1,2], Colorado Springs in 1989 [3], and Aachen in 1990 [3]. The workshop on Hypersonics whose results are presented and analysed in these volumes is also a direct consequence of this international cooperation. This scien tific event was an initiative of P. Perrier, Head of the Theoretical Aerodynamics Department of DASSAULT AVIATION, who played a key role in the identification of the critical problems and the realisation of experiments, within the Hermes R&D program framework.

This book contains the written versions of main lectures presented at the Advanced Study Institute (ASI) on Computational Mathematical Programming, which was held in Bad Windsheim, Germany F. R., from July 23 to August 2, 1984, under the sponsorship of NATO. The ASI was organized by the Committee on Algorithms (COAL) of the Mathematical Programming Society. Co-directors were Karla Hoffmann (National Bureau of Standards, Washington, U.S.A.) and Jan Teigen (Rabobank Nederland, Zeist, The Netherlands). Ninety participants coming from about 20 different countries attended the ASI and contributed their efforts to achieve a highly interesting and stimulating meeting. Since 1947 when the first linear programming technique was developed, the importance of optimization models and their mathematical solution methods has steadily increased, and now plays a leading role in applied research areas. The basic idea of optimization theory is to minimize (or maximize) a function of several variables subject to certain restrictions. This general mathematical concept covers a broad class of possible practical applications arising in mechanical, electrical, or chemical engineering, physics, economics, medicine, biology, etc. There are both industrial applications (e.g. design of mechanical structures, production plans) and applications in the natural, engineering, and social sciences (e.g. chemical equilibrium problems, christollography problems).

Computations with Markov Chains presents the edited and reviewed proceedings of the Second International Workshop on the Numerical Solution of Markov Chains, held January 16--18, 1995, in Raleigh, North Carolina. New developments of particular interest include recent work on stability and conditioning, Krylov subspace-based methods for transient solutions, quadratic convergent procedures for matrix geometric problems, further analysis of the GTH algorithm, the arrival of stochastic automata networks at the forefront of modelling stratagems, and more. An authoritative overview of the field for applied probabilists, numerical analysts and systems modelers, including computer scientists and engineers.

A spline is a thin flexible strip composed of a material such as bamboo or steel that can be bent to pass through or near given points in the plane, or in 3-space in a smooth manner. Mechanical engineers and drafting specialists find such (physical) splines useful in designing and in drawing plans for a wide variety of objects, such as for hulls of boats or for the bodies of automobiles where smooth curves need to be specified. These days, physi cal splines are largely replaced by computer software that can compute the desired curves (with appropriate encouragment). The same mathematical ideas used for computing "spline" curves can be extended to allow us to compute "spline" surfaces. The application ofthese mathematical ideas is rather widespread. Spline functions are central to computer graphics disciplines. Spline curves and surfaces are used in computer graphics renderings for both real and imagi nary objects. Computer-aided-design (CAD) systems depend on algorithms for computing spline functions, and splines are used in numerical analysis and statistics. Thus the construction of movies and computer games trav els side-by-side with the art of automobile design, sail construction, and architecture; and statisticians and applied mathematicians use splines as everyday computational tools, often divorced from graphic images."

This volume contains refereed papers and extended abstracts of papers presented at the NATO Advanced Research Workshop entitled 'Numerical Integration: Recent Develop ments, Software and Applications', held at the University of Bergen, Bergen, Norway, June 17-21,1991. The Workshop was attended by thirty-eight scientists. A total of eight NATO countries were represented. Eleven invited lectures and twenty-three contributed lectures were presented, of which twenty-five appear in full in this volume, together with three extended abstracts and one note. The main focus of the workshop was to survey recent progress in the theory of methods for the calculation of integrals and show how the theoretical results have been used in software development and in practical applications. The papers in this volume fall into four broad categories: numerical integration rules, numerical integration error analysis, numerical integration applications and numerical integration algorithms and software. It is five years since the last workshop of this nature was held, at Dalhousie University in Halifax, Canada, in 1986. Recent theoretical developments have mostly occurred in the area of integration rule construction. For polynomial integrating rules, invariant theory and ideal theory have been used to provide lower bounds on the numbers of points for different types of multidimensional rules, and to help in structuring the nonlinear systems which must be solved to determine the points and weights for the rules. Many new optimal or near optimal rules have been found for a variety of integration regions using these techniques."

In the modern age of almost universal computer usage, practically every individual in a technologically developed society has routine access to the most up-to-date cryptographic technology that exists, the so-called RSA public-key cryptosystem. A major component of this system is the factorization of large numbers into their primes. Thus an ancient number-theory concept now plays a crucial role in communication among millions of people who may have little or no knowledge of even elementary mathematics. The independent structure of each chapter of the book makes it highly readable for a wide variety of mathematicians, students of applied number theory, and others interested in both study and research in number theory and cryptography.

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

Visualization in scientific computing is getting more and more attention from many people. Especially in relation with the fast increase of com puting power, graphic tools are required in many cases for interpreting and presenting the results of various simulations, or for analyzing physical phenomena. The Eurographics Working Group on Visualization in Scientific Com puting has therefore organized a first workshop at Electricite de France (Clamart) in cooperation with ONERA (Chatillon). A wide range of pa pers were selected in order to cover most of the topics of interest for the members of the group, for this first edition, and 26 of them were presented in two days. Subsequently 18 papers were selected for this volume. 1'he presentations were organized in eight small sessions, in addition to discussions in small subgroups. The first two sessions were dedicated to the specific needs for visualization in computational sciences: the need for graphics support in large computing centres and high performance net works, needs of research and education in universities and academic cen tres, and the need for effective and efficient ways of integrating numerical computations or experimental data and graphics. Three of those papers are in Part I of this book. The third session discussed the importance and difficulties of using stan dards in visualization software, and was related to the fourth session where some reference models and distributed graphics systems were discussed. Part II has five papers from these sessions.

This book addresses the mathematical aspects of semiconductor modeling, with particular attention focused on the drift-diffusion model. The aim is to provide a rigorous basis for those models which are actually employed in practice, and to analyze the approximation properties of discretization procedures. The book is intended for applied and computational mathematicians, and for mathematically literate engineers, who wish to gain an understanding of the mathematical framework that is pertinent to device modeling. The latter audience will welcome the introduction of hydrodynamic and energy transport models in Chap. 3. Solutions of the nonlinear steady-state systems are analyzed as the fixed points of a mapping T, or better, a family of such mappings, distinguished by system decoupling. Significant attention is paid to questions related to the mathematical properties of this mapping, termed the Gummel map. Compu tational aspects of this fixed point mapping for analysis of discretizations are discussed as well. We present a novel nonlinear approximation theory, termed the Kras nosel'skii operator calculus, which we develop in Chap. 6 as an appropriate extension of the Babuska-Aziz inf-sup linear saddle point theory. It is shown in Chap. 5 how this applies to the semiconductor model. We also present in Chap. 4 a thorough study of various realizations of the Gummel map, which includes non-uniformly elliptic systems and variational inequalities. In Chap."

In delivering lectures and writing books, we were most often forced to pay absolutely no attention to a great body of interesting results and useful algorithms appearing in numerous sources and occasionally encountered. It was absolutely that most of these re sults would finally be forgotten because it is impossible to run through the entire variety of sources where these materials could be published. Therefore, we decided to do what we can to correct this situation. We discussed this problem with Ershov and came to an idea to write an encyclopedia of algorithms on graphs focusing our main attention on the algorithms already used in programming and their generalizations or modifications. We thought that it is reasonable to group all graphs into certain classes and place the algo rithms developed for each class into a separate book. The existence of trees, i. e., a class of graphs especially important for programming, also supported this decision. This monograph is the first but, as we hope, not the last book written as part of our project. It was preceded by two books "Algorithms on Trees" (1984) and "Algorithms of Processing of Trees" (1990) small editions of which were published at the Computer Center of the Siberian Division of the Russian Academy of Sciences. The books were distributed immediately and this made out our decision to prepare a combined mono graph on the basis of these books even stronger."

With applications in mind, this self-contained monograph provides a coherent and thorough treatment of the configuration spaces of Euclidean spaces and spheres, making the subject accessible to researchers and graduates with a minimal background in classical homotopy theory and algebraic topology.

The book Partial Differential Equations through Examples and Exercises has evolved from the lectures and exercises that the authors have given for more than fifteen years, mostly for mathematics, computer science, physics and chemistry students. By our best knowledge, the book is a first attempt to present the rather complex subject of partial differential equations (PDEs for short) through active reader-participation. Thus this book is a combination of theory and examples. In the theory of PDEs, on one hand, one has an interplay of several mathematical disciplines, including the theories of analytical functions, harmonic analysis, ODEs, topology and last, but not least, functional analysis, while on the other hand there are various methods, tools and approaches. In view of that, the exposition of new notions and methods in our book is "step by step." A minimal amount of expository theory is included at the beginning of each section Preliminaries with maximum emphasis placed on well selected examples and exercises capturing the essence of the material. Actually, we have divided the problems into two classes termed Examples and Exercises (often containing proofs of the statements from Preliminaries). The examples contain complete solutions, and also serve as a model for solving similar problems, given in the exercises. The readers are left to find the solution in the exercises; the answers, and occasionally, some hints, are still given. The book is implicitly divided in two parts, classical and abstract.

This book, dedicated to the memory of Gian-Carlo Rota, is the result of a collaborative effort by his friends, students and admirers. Rota was one of the great thinkers of our times, innovator in both mathematics and phenomenology. I feel moved, yet touched by a sense of sadness, in presenting this volume of work, despite the fear that I may be unworthy of the task that befalls me. Rota, both the scientist and the man, was marked by a generosity that knew no bounds. His ideas opened wide the horizons of fields of research, permitting an astonishing number of students from all over the globe to become enthusiastically involved. The contagious energy with which he demonstrated his tremendous mental capacity always proved fresh and inspiring. Beyond his renown as gifted scientist, what was particularly striking in Gian-Carlo Rota was his ability to appreciate the diverse intellectual capacities of those before him and to adapt his communications accordingly. This human sense, complemented by his acute appreciation of the importance of the individual, acted as a catalyst in bringing forth the very best in each one of his students. Whosoever was fortunate enough to enjoy Gian-Carlo Rota's longstanding friendship was most enriched by the experience, both mathematically and philosophically, and had occasion to appreciate son cote de bon vivant. The book opens with a heartfelt piece by Henry Crapo in which he meticulously pieces together what Gian-Carlo Rota's untimely demise has bequeathed to science.

This book describes the rapidly developing field of interior point methods (IPMs). An extensive analysis is given of path-following methods for linear programming, quadratic programming and convex programming. These methods, which form a subclass of interior point methods, follow the central path, which is an analytic curve defined by the problem. Relatively simple and elegant proofs for polynomiality are given. The theory is illustrated using several explicit examples. Moreover, an overview of other classes of IPMs is given. It is shown that all these methods rely on the same notion as the path-following methods: all these methods use the central path implicitly or explicitly as a reference path to go to the optimum. For specialists in IPMs as well as those seeking an introduction to IPMs. The book is accessible to any mathematician with basic mathematical programming knowledge.