The course of lectures on numerical methods (part I) given by the author to students in the numerical third of the course of the mathematics mechanics department of Leningrad State University is set down in this volume. Only the topics which, in the opinion of the author, are of the greatest value for numerical methods are considered in this book. This permits making the book comparatively small in size, and, the author hopes, accessible to a sufficiently wide circle of readers. The book may be used not only by students in daily classes, but also by students taking correspondence courses and persons connected with practical computa tion who desire to improve their theoretical background. The author is deeply grateful to V. I. Krylov, the organizer ofthe course on numerical methods (part I) at Leningrad State University, for his considerable assistance and constant interest in the work on this book, and also for his attentive review of the manuscript. The author is very grateful to G. P. Akilov and I. K. Daugavet for a series of valuable suggestions and observations. The Author Chapter I NUMERICAL SOLUTION OF EQUATIONS In this chapter, methods for the numerical solution of equations of the form P(x) = 0, will be considered, where P(x) is in general a complex-valued function.

The Third International Symposium on Hultivariate Approximation Theory was held at the Oberwolfach !1athematical Research Insti- tute, Black Forest, February 8-12, 1982. The preceding conferen- ces on this topic were held in 1976* and 1979**. The conference brought together 50 mathematicians from 14 coun- tries. These Proceedings form arecord of most of the papers pre- sented at the Symposium. The topics treated cover different problems on multivariate approximation theory such as new results concerning approxima- tion by polynomials in Sobolev spaces, biorthogonal systems and orthogonal series of functions in several variables, multivariate spline functions, group theoretic and functional analytic methods, positive linear operators, error estimates for approximation procedures and cubature formulae, Boolean methods in multivari- ate interpolation and the numerical application of summation procedures. Special emphasis was posed on the application of multivariate approximation in various fields of science. One mathematician was sorely missed at the Symposium. Professor Arthur Sard who had actively taken part in the earlier conferen- ces passed away in August of 1980. Since he was a friend of many of the participants, the editors wish to dedicate these Procee- dings to the memory of this distinguished mathematician. Abrief appreciation of his life and mathematical work appears as well *"Constructive Theory of Functions of Several Variables". Edited by w. Schempp and Karl Zeller. Lecture Notes in 1-1athematics, Vol.

Mathematical modelling of many physical processes involves rather complex dif- ferential, integral, and integro-differential equations which can be solved directly only in a number of cases. Therefore, as a first step, an original problem has to be considerably simplified in order to get a preliminary knowledge of the most important qualitative features of the process under investigation and to estimate the effect of various factors. Sometimes a solution of the simplified problem can be obtained in the analytical form convenient for further investigation. At this stage of the mathematical modelling it is useful to apply various special functions. Many model problems of atomic, molecular, and nuclear physics, electrody- namics, and acoustics may be reduced to equations of hypergeometric type, a(x)y" + r(x)y' + AY = 0 , (0.1) where a(x) and r(x) are polynomials of at most the second and first degree re- spectively and A is a constant [E7, AI, N18]. Some solutions of (0.1) are functions extensively used in mathematical physics such as classical orthogonal polyno- mials (the Jacobi, Laguerre, and Hermite polynomials) and hypergeometric and confluent hypergeometric functions.

The book is a revised and updated version of the lectures given by the author at the University of Timi oara during the academic year 1990-1991. Its goal is to present in detail someold and new aspects ofthe geometry ofsymplectic and Poisson manifolds and to point out some of their applications in Hamiltonian mechanics and geometric quantization. The material is organized as follows. In Chapter 1 we collect some general facts about symplectic vector spaces, symplectic manifolds and symplectic reduction. Chapter 2 deals with the study ofHamiltonian mechanics. We present here the gen- eral theory ofHamiltonian mechanicalsystems, the theory ofthe corresponding Pois- son bracket and also some examples ofinfinite-dimensional Hamiltonian mechanical systems. Chapter 3 starts with some standard facts concerning the theory of Lie groups and Lie algebras and then continues with the theory ofmomentum mappings and the Marsden-Weinstein reduction. The theory of Hamilton-Poisson mechan- ical systems makes the object of Chapter 4. Chapter 5 js dedicated to the study of the stability of the equilibrium solutions of the Hamiltonian and the Hamilton- Poisson mechanical systems. We present here some of the remarcable results due to Holm, Marsden, Ra~iu and Weinstein. Next, Chapter 6 and 7 are devoted to the theory of geometric quantization where we try to solve, in a geometrical way, the so called Dirac problem from quantum mechanics. We follow here the construc- tion given by Kostant and Souriau around 1964.

Computational aspects of geometry of numbers have been revolutionized by the Lenstra-Lenstra-Lovasz ' lattice reduction algorithm (LLL), which has led to bre- throughs in elds as diverse as computer algebra, cryptology, and algorithmic number theory. After its publication in 1982, LLL was immediately recognized as one of the most important algorithmic achievements of the twentieth century, because of its broad applicability and apparent simplicity. Its popularity has kept growing since, as testi ed by the hundreds of citations of the original article, and the ever more frequent use of LLL as a synonym to lattice reduction. As an unfortunate consequence of the pervasiveness of the LLL algorithm, researchers studying and applying it belong to diverse scienti c communities, and seldom meet. While discussing that particular issue with Damien Stehle ' at the 7th Algorithmic Number Theory Symposium (ANTS VII) held in Berlin in July 2006, John Cremona accuratelyremarkedthat 2007would be the 25th anniversaryof LLL and this deserveda meetingto celebrate that event. The year 2007was also involved in another arithmetical story. In 2003 and 2005, Ali Akhavi, Fabien Laguillaumie, and Brigitte Vallee ' with other colleagues organized two workshops on cryptology and algorithms with a strong emphasis on lattice reduction: CAEN '03 and CAEN '05, CAEN denoting both the location and the content (Cryptologie et Algori- miqueEn Normandie). Veryquicklyafterthe ANTSconference,AliAkhavi,Fabien Laguillaumie, and Brigitte Vallee ' were thus readily contacted and reacted very enthusiastically about organizing the LLL birthday conference. The organization committee was formed.

The requirement of causality in system theory is inevitably accompanied by the appearance of certain mathematical operations, namely the Riesz proj- tion,theHilberttransform,andthespectralfactorizationmapping.Aclassical exampleillustratingthisisthedeterminationoftheso-calledWiener?lter(the linear, minimum means square error estimation ?lter for stationary stochastic sequences [88]). If the ?lter is not required to be causal, the transfer function of the Wiener ?lter is simply given by H(?)=? (?)/? (?),where ? (?) xy xx xx and ? (?) are certain given functions. However, if one requires that the - xy timation ?lter is causal, the transfer function of the optimal ?lter is given by 1 ? (?) xy H(?)= P ,?? (??,?] . + [? ] (?) [? ] (?) xx + xx? Here [? ] and [? ] represent the so called spectral factors of ? ,and xx + xx? xx P is the so called Riesz projection. Thus, compared to the non-causal ?lter, + two additional operations are necessary for the determination of the causal ?lter, namely the spectral factorization mapping ? ? ([? ] ,[? ] ),and xx xx + xx? the Riesz projection P .

This text is an introduction to methods of grid generation technology in scientific computing. Special attention is given to methods developed by the author for the treatment of singularly-perturbed equations, e.g. in modeling high Reynolds number flows. Functionals of conformality, orthogonality, energy and alignment are discussed.

Many phenomena of interest for applications are represented by differential equations which are defined in a domain whose boundary is a priori unknown, and is accordingly named a "free boundary." A further quantitative condition is then provided in order to exclude indeterminacy. Free boundary problems thus encompass a broad spectrum which is represented in this state-of-the-art volume by a variety of contributions of researchers in mathematics and applied fields like physics, biology and material sciences. Special emphasis has been reserved for mathematical modelling and for the formulation of new problems.

The classical theories of Linear Elasticity and Newtonian Fluids, though trium phantly elegant as mathematical structures, do not adequately describe the defor mation and flow of most real materials. Attempts to characterize the behaviour of real materials under the action of external forces gave rise to the science of Rheology. Early rheological studies isolated the phenomena now labelled as viscoelastic. Weber (1835, 1841), researching the behaviour of silk threats under load, noted an instantaneous extension, followed by a further extension over a long period of time. On removal of the load, the original length was eventually recovered. He also deduced that the phenomena of stress relaxation and damping of vibrations should occur. Later investigators showed that similar effects may be observed in other materials. The German school referred to these as "Elastische Nachwirkung" or "the elastic aftereffect" while the British school, including Lord Kelvin, spoke ofthe "viscosityofsolids." The universal adoption of the term "Viscoelasticity," intended to convey behaviour combining proper ties both of a viscous liquid and an elastic solid, is of recent origin, not being used for example by Love (1934), though Alfrey (1948) uses it in the context of polymers. The earliest attempts at mathematically modelling viscoelastic behaviour were those of Maxwell (1867) (actually in the context of his work on gases; he used this model for calculating the viscosity of a gas) and Meyer (1874)."

One of the major concerns of theoretical computer science is the classifi cation of problems in terms of how hard they are. The natural measure of difficulty of a function is the amount of time needed to compute it (as a function of the length of the input). Other resources, such as space, have also been considered. In recursion theory, by contrast, a function is considered to be easy to compute if there exists some algorithm that computes it. We wish to classify functions that are hard, i.e., not computable, in a quantitative way. We cannot use time or space, since the functions are not even computable. We cannot use Turing degree, since this notion is not quantitative. Hence we need a new notion of complexity-much like time or spac that is quantitative and yet in some way captures the level of difficulty (such as the Turing degree) of a function."

The chapters in this volume, written by international experts from different fields of mathematics, are devoted to honoring George Isac, a renowned mathematician. These contributions focus on recent developments in complementarity theory, variational principles, stability theory of functional equations, nonsmooth optimization, and several other important topics at the forefront of nonlinear analysis and optimization.

This textbook is designed to give graduate students an understanding of integrable systems via the study of Riemann surfaces, loop groups, and twistors. The book has its origins in a series of lecture courses given by the authors, all of whom are internationally known mathematicians and renowned expositors. It is written in an accessible and informal style, and fills a gap in the existing literature. The introduction by Nigel Hitchin addresses the meaning of integrability: how do we recognize an integrable system? His own contribution then develops connections with algebraic geometry, and includes an introduction to Riemann surfaces, sheaves, and line bundles. Graeme Segal takes the Kortewegde Vries and nonlinear Schroedinger equations as central examples, and explores the mathematical structures underlying the inverse scattering transform. He explains the roles of loop groups, the Grassmannian, and algebraic curves. In the final part of the book, Richard Ward explores the connection between integrability and the self-dual Yang-Mills equations, and describes the correspondence between solutions to integrable equations and holomorphic vector bundles over twistor space.

A "Sonderforschungsbereich" (SFB) is a programme of the "Deutsche For schungsgemeinschaft" to financially support a concentrated research effort of a number of scientists located principally at one University, Research La boratory or a number of these situated in close proximity to one another so that active interaction among individual scientists is easily possible. Such SFB are devoted to a topic, in our case "Deformation and Failure in Metallic and Granular M aterialK', and financing is based on a peer reviewed proposal for three (now four) years with the intention of several prolongations after evaluation of intermediate progress and continuation reports. An SFB is terminated in general by a formal workshop, in which the state of the art of the achieved results is presented in oral or I and poster communications to which also guests are invited with whom the individual project investigators may have collaborated. Moreover, a research report in book form is produced in which a number of articles from these lectures are selected and collected, which present those research results that withstood a rigorous reviewing pro cess (with generally two or three referees). The theme deformation and failure of materials is presented here in two volumes of the Lecture Notes in Applied and Computational Mechanics by Springer Verlag, and the present volume is devoted to granular and porous continua. The complementary volume (Lecture Notes in Applied and Com putational Mechanics, vol. 10, Eds. K. HUTTER & H."

This book contains the main results of the German project POPINDA. It surveys the state of the art of industrial aerodynamic design simulations on parallel systems. POPINDA is an acronym for Portable Parallelization of Industrial Aerodynamic Applications. This project started in late 1993. The research and development work invested in POPINDA corresponds to about 12 scientists working full-time for the three and a half years of the project. POPINDA was funded by the German Federal Ministry for Education, Science, Research and Technology (BMBF). The central goals of POPINDA were to unify and parallelize the block-structured aerodynamic flow codes of the German aircraft industry and to develop new algorithmic approaches to improve the efficiency and robustness of these programs. The philosophy behind these goals is that challenging and important numerical appli cations such as the prediction of the 3D viscous flow around full aircraft in aerodynamic design can only be carried out successfully if the benefits of modern fast numerical solvers and parallel high performance computers are combined. This combination is a "conditio sine qua non" if more complex applications such as aerodynamic design optimization or fluid structure interaction problems have to be solved. When being solved in a standard industrial aerodynamic design process, such more complex applications even require a substantial further reduction of computing times. Parallel and vector computers on the one side and innovative numerical algorithms such as multigrid on the other have enabled impressive improvements in scientific computing in the last 15 years."

Computational simulation of scientific phenomena and engineering problems often depends on solving linear systems with a large number of unknowns. This book gives insight into the construction of iterative methods for the solution of such systems and helps the reader to select the best solver for a given class of problems. The emphasis is on the main ideas and how they have led to efficient solvers such as CG, GMRES, and BI-CGSTAB. The author also explains the main concepts behind the construction of preconditioners. The reader is encouraged to gain experience by analysing numerous examples that illustrate how best to exploit the methods. The book also hints at many open problems and as such it will appeal to established researchers. There are many exercises that motivate the material and help students to understand the essential steps in the analysis and construction of algorithms.

There is no doubt nowadays that numerical mathematics is an essential component of any educational program. It is probably more efficient to present such material after a strong grasp of (at least) linear algebra and calculus has already been attained -but at this stage those not specializing in numerical mathematics are often interested in getting more deeply into their chosen field than in developing skills for later use. An alternative approach is to incorporate the numerical aspects of linear algebra and calculus as these subjects are being developed. Long experience has persuaded us that a third attack on this problem is the best and this is developed in the present two volumes, which are, however, easily adaptable to other circumstances. The approach we prefer is to treat the numerical aspects separately, but after some theoretical background. This is often desirable because of the shortage of persons qualified to present the combined approach and also because the numerical approach provides an often welcome change which, however, in addition, can lead to better appreciation of the fundamental concepts. For instance, in a 6-quarter course in Calculus and Linear Algebra, the material in Volume 1 can be handled in the third quarter and that in Volume 2 in the fifth or sixth quarter.

Least squares is probably the best known method for fitting linear models and by far the most widely used. Surprisingly, the discrete L 1 analogue, least absolute deviations (LAD) seems to have been considered first. Possibly the LAD criterion was forced into the background because of the com putational difficulties associated with it. Recently there has been a resurgence of interest in LAD. It was spurred on by work that has resulted in efficient al gorithms for obtaining LAD fits. Another stimulus came from robust statistics. LAD estimates resist undue effects from a feyv, large errors. Therefore. in addition to being robust, they also make good starting points for other iterative, robust procedures. The LAD criterion has great utility. LAD fits are optimal for linear regressions where the errors are double exponential. However they also have excellent properties well outside this narrow context. In addition they are useful in other linear situations such as time series and multivariate data analysis. Finally, LAD fitting embodies a set of ideas that is important in linear optimization theory and numerical analysis. viii PREFACE In this monograph we will present a unified treatment of the role of LAD techniques in several domains. Some of the material has appeared in recent journal papers and some of it is new. This presentation is organized in the following way. There are three parts, one for Theory, one for Applicatior.s and one for Algorithms."

This edited survey book consists of 20 chapters showing application of Clifford algebra in quantum mechanics, field theory, spinor calculations, projective geometry, Hypercomplex algebra, function theory and crystallography. Many examples of computations performed with a variety of readily available software programs are presented in detail.

Recent years have witnessed a surge of activity in the field of dynamic both theory and applications. Theoretical as well as practical games, in problems in zero-sum and nonzero-sum games, continuous time differential and discrete time multistage games, and deterministic and stochastic games games are currently being investigated by researchers in diverse disciplines, such as engineering, mathematics, biology, economics, management science, and political science. This surge of interest has led to the formation of the International Society of Dynamic Games (ISDG) in 1990, whose primary goal is to foster the development of advanced research and applications in the field of game theory. One important activity of the Society is to organize biannually an international symposium which aims at bringing together all those who contribute to the development of this active field of applied science. In 1992 the symposium was organized in Grimentz, Switzerland, under the supervision of an international scientific committee and with the help of a local organizing committee based at University of Geneva. This book, which is the first volume in the new Series, Annals of the International Society of Dynamic Games (see the Preface to the Series), is based on presentations made at this symposium. It is however more than a book of proceedings for a conference. Every paper published in this volume has passed through a very selective refereeing process, as in an archival technical journal.

The development of high-order accurate numerical discretization techniques for irregular domains and meshes is often cited as one of the remaining chal lenges facing the field of computational fluid dynamics. In structural me chanics, the advantages of high-order finite element approximation are widely recognized. This is especially true when high-order element approximation is combined with element refinement (h-p refinement). In computational fluid dynamics, high-order discretization methods are infrequently used in the com putation of compressible fluid flow. The hyperbolic nature of the governing equations and the presence of solution discontinuities makes high-order ac curacy difficult to achieve. Consequently, second-order accurate methods are still predominately used in industrial applications even though evidence sug gests that high-order methods may offer a way to significantly improve the resolution and accuracy for these calculations. To address this important topic, a special course was jointly organized by the Applied Vehicle Technology Panel of NATO's Research and Technology Organization (RTO), the von Karman Institute for Fluid Dynamics, and the Numerical Aerospace Simulation Division at the NASA Ames Research Cen ter. The NATO RTO sponsored course entitled "Higher Order Discretization Methods in Computational Fluid Dynamics" was held September 14-18,1998 at the von Karman Institute for Fluid Dynamics in Belgium and September 21-25,1998 at the NASA Ames Research Center in the United States."

It was about 1985 when both of the authors started their work using multigrid methods for process simulation problems. This happened in dependent from each other, with a completely different background and different intentions in mind. At this time, some important monographs appeared or have been in preparation. There are the three "classical" ones, from our point of view: the so-called "1984 Guide" [12J by Brandt, the "Multi-Grid Methods and Applications" [49J by Hackbusch and the so-called "Fundamentals" [132J by Stiiben and Trottenberg. Stiiben and Trottenberg in [132J state a "delayed acceptance, resent ments" with respect to multigrid algorithms. They complain: "Nevertheless, even today's situation is still unsatisfactory in several respects. If this is true for the development of standard methods, it applies all the more to the area of really difficult, complex applications." In spite of all the above mentioned publications and without ignoring important theoretical and practical improvements of multigrid, this situa tion has not yet changed dramatically. This statement is made under the condition that a numerical principle like multigrid is "accepted", if there exist "professional" programs for research and production purposes. "Professional" in this context stands for "solving complex technical prob lems in an industrial environment by a large community of users". Such a use demands not only for fast solution methods but also requires a high robustness with respect to the physical parameters of the problem.

One of the most well-known of all network optimization problems is the shortest path problem, where a shortest connection between two locations in a road network is to be found. This problem is the basis of route planners in vehicles and on the Internet. Networks are very common structures; they consist primarily of a ?nite number of locations (points, nodes), together with a number of links (edges, arcs, connections) between the locations. Very often a certain number is attached to the links, expressing the distance or the cost between the end points of that connection. Networks occur in an extremely wide range of applications, among them are: road networks; cable networks; human relations networks; project scheduling networks; production networks; distribution networks; neural networks; networks of atoms in molecules. In all these cases there are "objects" and "relations" between the objects. A n- work optimization problem is actually nothing else than the problem of ?nding a subset of the objects and the relations, such that a certain optimization objective is satis?ed.

At first sight, finitely generated abelian groups and canonical forms of matrices appear to have little in common. However, reduction to Smith normal form, named after its originator H.J.S.Smith in 1861, is a matrix version of the Euclidean algorithm and is exactly what the theory requires in both cases. Starting with matrices over the integers, Part1 of this book provides a measured introduction to such groups: two finitely generated abelian groups are isomorphic if and only if their invariant factor sequences are identical. The analogous theory of matrix similarity over a field is then developed in Part2 starting with matrices having polynomial entries: two matrices over a field are similar if and only if their rational canonical forms are equal. Under certain conditions each matrix is similar to a diagonal or nearly diagonal matrix, namely its Jordan form.

The reader is assumed to be familiar with the elementary properties of rings and fields. Also a knowledge of abstract linear algebra including vector spaces, linear mappings, matrices, bases and dimension is essential, although much of the theory is covered in the text but from a more general standpoint: the role of vector spaces is widened to modules over commutative rings.

Based on a lecture course taught by the author for nearly thirty years, the book emphasises algorithmic techniques and features numerous worked examples and exercises with solutions. The early chapters form an ideal second course in algebra for second and third year undergraduates. The later chapters, which cover closely related topics, e.g. field extensions, endomorphism rings, automorphism groups, and variants of the canonical forms, will appeal to more advanced students. The book is a bridge between linear and abstract algebra."

This collection on "Mechanics of Generalized Continua - from Micromechanical Basics to Engineering Applications" brings together leading scientists in this field from France, Russian Federation, and Germany. The attention in this publication is be focussed on the most recent research items, i.e., - new models, - application of well-known models to new problems, - micro-macro aspects, - computational effort, - possibilities to identify the constitutive equations, and - old problems with incorrect or non-satisfying solutions based on the classical continua assumptions.

This book addresses the task of computation from the standpoint of asymptotic analysis and multiple scales that may be inherent in the system dynamics being studied. This is in contrast to the usual methods of numerical analysis and computation. The technical literature is replete with numerical methods such as Runge-Kutta approach and its variations, finite element methods, and so on. However, not much attention has been given to asymptotic methods for computation, although such approaches have been widely applied with great success in the analysis of dynamic systems. The presence of different scales in a dynamic phenomenon enable us to make judicious use of them in developing computational approaches which are highly efficient. Many such applications have been developed in such areas as astrodynamics, fluid mechanics and so on. This book presents a novel approach to make use of the different time constants inherent in the system to develop rapid computational methods. First, the fundamental notions of asymptotic analysis are presented with classical examples. Next, the novel systematic and rigorous approaches of system decomposition and reduced order models are presented. Next, the technique of multiple scales is discussed. Finally application to rapid computation of several aerospace systems is discussed, demonstrating the high efficiency of such methods.