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

This book is motivated largely by a desire to solve shape optimization prob lems that arise in applications, particularly in structural mechanics and in the optimal control of distributed parameter systems. Many such problems can be formulated as the minimization of functionals defined over a class of admissible domains. Shape optimization is quite indispensable in the design and construction of industrial structures. For example, aircraft and spacecraft have to satisfy, at the same time, very strict criteria on mechanical performance while weighing as little as possible. The shape optimization problem for such a structure consists in finding a geometry of the structure which minimizes a given functional (e. g. such as the weight of the structure) and yet simultaneously satisfies specific constraints (like thickness, strain energy, or displacement bounds). The geometry of the structure can be considered as a given domain in the three-dimensional Euclidean space. The domain is an open, bounded set whose topology is given, e. g. it may be simply or doubly connected. The boundary is smooth or piecewise smooth, so boundary value problems that are defined in the domain and associated with the classical partial differential equations of mathematical physics are well posed. In general the cost functional takes the form of an integral over the domain or its boundary where the integrand depends smoothly on the solution of a boundary value problem."

This book constitutes the thoroughly refereed proceedings of the 38th International Workshop on Graph Theoretic Concepts in Computer Science (WG 2012) held in Jerusalem, Israel on June 26-28, 2012. The 29 revised full papers presented were carefully selected and reviewed from 78 submissions. The papers are solicited describing original results on all aspects of graph-theoretic concepts in Computer Science, e.g. structural graph theory, sequential, parallel, randomized, parameterized, and distributed graph and network algorithms and their complexity, graph grammars and graph rewriting systems, graph-based modeling, graph-drawing and layout, random graphs, diagram methods, and support of these concepts by suitable implementations. The scope of WG includes all applications of graph-theoretic concepts in Computer Science, including data structures, data bases, programming languages, computational geometry, tools for software construction, communications, computing on the web, models of the web and scale-free networks, mobile computing, concurrency, computer architectures, VLSI, artificial intelligence, graphics, CAD, operations research, and pattern recognition

This volume is a selection from the 281 published papers of Joseph Leonard Walsh, former US Naval Officer and professor at University of Maryland and Harvard University. The nine broad sections are ordered following the evolution of his work. Commentaries and discussions of subsequent development are appended to most of the sections. Also included is one of Walsh's most influential works, "A closed set of normal orthogonal function," which introduced what is now known as "Walsh Functions".

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.

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 reasonable competence in (at least) linear algebra and calculus has already been attained - but at this stage those not specializ ing 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 cal culus 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 circum stances. 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 con cepts. 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."

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.

Starting with Cook's pioneering work on NP-completeness in 1970, polynomial complexity theory, the study of polynomial-time com putability, has quickly emerged as the new foundation of algorithms. On the one hand, it bridges the gap between the abstract approach of recursive function theory and the concrete approach of analysis of algorithms. It extends the notions and tools of the theory of computability to provide a solid theoretical foundation for the study of computational complexity of practical problems. In addition, the theoretical studies of the notion of polynomial-time tractability some times also yield interesting new practical algorithms. A typical exam ple is the application of the ellipsoid algorithm to combinatorial op timization problems (see, for example, Lovasz 1986]). On the other hand, it has a strong influence on many different branches of mathe matics, including combinatorial optimization, graph theory, number theory and cryptography. As a consequence, many researchers have begun to re-examine various branches of classical mathematics from the complexity point of view. For a given nonconstructive existence theorem in classical mathematics, one would like to find a construc tive proof which admits a polynomial-time algorithm for the solution. One of the examples is the recent work on algorithmic theory of per mutation groups. In the area of numerical computation, there are also two tradi tionally independent approaches: recursive analysis and numerical analysis."

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.

This book constitutes the refereed proceedings of the 7th International Workshop on Algorithms and Computation, WALCOM 2013, held in Kharagpur, India, in February 2013. The 29 full papers presented were carefully reviewed and selected from 86 submissions. The papers are organized in topical sections on computational geometry, approximation and randomized algorithms, parallel and distributed computing, graph algorithms, complexity and bounds, and graph drawing.

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

Parallel computers have started to completely revolutionize scientific computation. Articles in this volume represent applied mathematics, computer science, and application aspects of parallel scientific computing. Major advances are discussed dealing with multiprocessor architectures, parallel algorithm development and analysis, parallel systems and programming languages. The optimization of the application of massively parallel architectures to real world problems will provide the impetus for the development of entirely new approaches to these technical situations.

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

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.

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.

This volume contains the contributions to the 10th DGLR I AG ST AB-Symposium held at the German Aerospace Research Establishment (DLR) -Braunschweig Research Centre - November, 11 to 13, 1996. AG STAB is the German Aerospace AerodynapIics Association, founded at the end of the 70', while DGLR is the German Society for Aeronautics and Astronautics (Deutsche Gesellschaft fur Luft- und Raumfahrt, LilienthaI Oberth Gesellschaft). In the AG STAB German scientists and engineers from universities, research-establishments and industries are involved, who are doing research and project work in numerical and experimental fluidmechanics and aerodynamics for aerospace and other applications. About 20 years ago it became obvious for this community that a joint effort of members of universities, the DLR and industry was necessary to counter-act declining budgets in the field. It was decided to approach high-level persons in industry, ministries and the parliament for help to shift the trend with its negative effects for research and industry. From the begin it was clear that an effort should be built around a central theme. ''Flow with Separation" became the topic of the AG STAB (Arbeitsgemeinschaft Stromung mit Ablosung), which developed fast into a lively association, with, however, a larger scope than just flow with separation."

The finite element method (FEM) has been understood, at least in principle, for more than 50 years. The integral formulation on which it is based has been known for a longer time (thanks to the work of Galerkin, Ritz, Courant and Hilbert,1,4 to mention the most important). However, the method could not be applied in a practical way since it involved the solution of a large number of linear or non-linear algebraic equations. Today it is quite common, with the aid of computers, to solve non-linear algebraic problems of several thousand equations. The necessary numerical methods and programming techniques are now an integral part of the teaching curriculum in most engineering schools. Mechanical engineers, confronted with very complicated structural problems, were the first to take advantage of advanced computational methods and high level languages (FORTRAN) to transform the mechanical models into algebraic equations (1956). In recent times (1960), the FEM has been studied by applied mathematicians and, having received rigorous treatment, has become a part of the more general study of partial differential equations, gradually replacing the finite difference method which had been considered the universal tool to solve these types of problems.

This volume contains the extended version of selected talks given at the international research workshop "Coping with Complexity: Model Reduction and Data Analysis," Ambleside, UK, August 31 - September 4, 2009. The book is deliberately broad in scope and aims at promoting new ideas and methodological perspectives. The topics of the chapters range from theoretical analysis of complex and multiscale mathematical models to applications in e.g., fluid dynamics and chemical kinetics.

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

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