The NATO Advanced Research Workshop (ARW) "Algorithms and Model Formulations in Mathematical Programming" was held at Chr. Michelsen Institute in Bergen, Norway, from June 15 to June 19, 1987. The ARW was organized on behalf of the Committee on Algorithms (COAL) of the Mathematical Programming Society (MPS). Co-directors were Jan Telgen (Van Dien+Co Organisatie, Utrecht, The Netherlands) and Roger J-B Wets (The University of California at Davis, USA). 43 participants from 11 countries attended the ARW. The workshop was organized such that each day started with a - minute keynote presentation, followed by a 45-minute plenary discussion. The first part of this book contains the contributions of the five keynote speakers. The plenary discussions were taped, and the transcripts given to the keynote speakers. They have treated the transcripts differently, some by working the discussions into their papers, others by adding a section which sums up the discussions. The plenary discussions were very interesting and stimulating due to active participation of the audience. The five keynote speakers were asked to view the topic of the workshop, the interaction between algorithms and model formulations, from different perspectives. On the first day of the workshop Professor Alexander H.G. Rinnooy Kan (Erasmus University, Rotterdam, The Netherlands) put the theme into a larger context by his talk "Mathematical programming as an intellectual activity." This is an article of importance to any mathematical programmer who is interested in his field's history and present state.

This book contains thirty-six papers from among the forty-five papers presented at the Third International Conference on Fibonacci Numbers and Their Applications which was held in Pisa, Italy from July 25 to July 29, 1988 in honor of Leonardo de Pisa. 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 are their unifying bond. It is anticipated that this book, like its two predecessors, will be useful to research workers and graduate students interested in the Fibonacci numbers and their applications. August 1989 The Editors Gerald E. Bergum South Dakota State University Brookings, South Dakota, U. S. A. Andreas N. Philippou Ministry of Education Nicosia, Cyprus Alwyn F. Horadam University of New England Armidale N. S. W. , Australia xv THE ORGANIZING COMMITTEES LOCAL COMMITTEE INTERNATIONAL COMMITTEE Dvornicich, Roberto, Chairman Horadam, A. F. (Australia), Co-chairman Filipponi, Piero Philippou, A. N. (Cyprus), Co-chairman Perelli, Alberto Ando, S. (Japan) Viola, Carlo Bergum, G. E. (U. S. A. ) Zannier, Umberto Johnson, M. B. (U. S. A. ) Kiss, P. (Hungary) Tijdeman, Robert (The Netherlands) Tognetti, K. (Australia) XVII LIST OF CONTRIBUTORS TO THE CONFERENCE' ADLER, I. , RR 1, Box 532, North Bennington, VT 05257-9748. "Separating the Biological from the Mathematical Aspects of Phyllotaxis. " *AKRITAS, A. G. , (coauthor P. G. Bradford). "The Role of the Fibonacci Sequence in the Isolation of the Real Roots of Polynomial Equations.

Thework described in this has somewhat erratically, over monograph grown, of than a more interest inthe was firstaroused period thirty My subject years. thebeautiful and inBroucke.'sthesis also by see computations drawings (1963; Broucke where familiesof orbits in the restricted three 1968), periodic body for the Earth Moon ratio = were mass problem investigated (/.I 0.012155). These that natural for the existence ofthe a explanation drawingssuggested observed familiesand for the found the of orbits could be shapes perhaps by to the limit ] 0. a recourse y As first it a to as as step, appeared catalog completely possible necessary the orbits obtained in this limit. orbits of the first generaiing Generating hadbeen studied andother authors. Poincar6 specZes by (1892) Surprisingly, the two other had been Orbits ofthe however, species apparently neglected. second orbits with or consecutive a species, collisions, present comparatively the ofthe simple problem, only two body problem; no using equations yet had been done.An ofthe systematic ever constituent arcs study inventory was inH6non presented (1968). Also little work had been done on farmlies of orbits of the third very to Hill's A numerical species, was corresponding problem. investigation pub lished inR6non (1969).

The current form of modern approximation theory is shaped by many new de velopments which are the subject of this series of conferences. The International Meetings on Approximation Theory attempt to keep track in particular of fun damental advances in the theory of function approximation, for example by (or thogonal) polynomials, (weighted) interpolation, multivariate quasi-interpolation, splines, radial basis functions and several others. This includes both approxima tion order and error estimates, as well as constructions of function systems for approximation of functions on Euclidean spaces and spheres. It is a piece of very good fortune that at all of the IDoMAT meetings, col leagues and friends from all over Europe, and indeed some count ries outside Europe and as far away as China, New Zealand, South Africa and U.S.A. came and dis cussed mathematics at IDoMAT conference facility in Witten-Bommerholz. The conference was, as always, held in a friendly and congenial atmosphere. After each meeting, the delegat es were invited to contribute to the proceed ing's volume, the previous one being published in the same Birkhauser series as this one. The editors were pleased about the quality of the contributions which could be solicited for the book. They are refereed and we should mention our gratitude to the referees and their work."

For well over a decade, the numerical approach to field computation has been gaining progressively greater importance. Analytical methods of field compu tation are, at best, unable to accommodate the very wide variety of configura tions in which fields must be computed. On the other hand, numerical methods can accommodate many practical configurations that analytical methods cannot. With the advent of high-speed digital computers, numerical field computations have finally become practical. However, in order to implement numerical methods of field computation, we need algorithms, numerical methods, and mathematical tools that are largely quite different from those that have been traditionally used with analytical methods. Many of these algorithms have, in fact, been presented in the large number of papers that have been published on this subject in the last two decades. And to some of those who are already experienced in the art of numerical field computations, these papers, in addition to their own original work, are enough to give them the knowledge that they need to perform practical numerical field computations."

Since the appearance of computers, numerical methods for discontinuous solutions of quasi-linear hyperbolic systems of partial differential equations have been among the most important research subjects in numerical analysis. The authors have developed a new difference method (named the singularity-separating method) for quasi-linear hyperbolic systems of partial differential equations. Its most important feature is that it possesses a high accuracy even for problems with singularities such as schocks, contact discontinuities, rarefaction waves and detonations. Besides the thorough description of the method itself, its mathematical foundation (stability-convergence theory of difference schemes for initial-boundary-value hyperbolic problems) and its application to supersonic flow around bodies are discussed. Further, the method of lines and its application to blunt body problems and conical flow problems are described in detail. This book should soon be an important working basis for both graduate students and researchers in the field of partial differential equations as well as in mathematical physics.

Many practical applications require the reconstruction of a multivariate function from discrete, unstructured data. This book gives a self-contained, complete introduction into this subject. It concentrates on truly meshless methods such as radial basis functions, moving least squares, and partitions of unity. The book starts with an overview on typical applications of scattered data approximation, coming from surface reconstruction, fluid-structure interaction, and the numerical solution of partial differential equations. It then leads the reader from basic properties to the current state of research, addressing all important issues, such as existence, uniqueness, approximation properties, numerical stability, and efficient implementation. Each chapter ends with a section giving information on the historical background and hints for further reading. Complete proofs are included, making this perfectly suited for graduate courses on multivariate approximation and it can be used to support courses in computer aided geometric design, and meshless methods for partial differential equations.

This volume includes contributions from diverse disciplines including electrical engineering, biomedical engineering, industrial engineering, and medicine, bridging a vital gap between the mathematical sciences and neuroscience research. Covering a wide range of research topics, this volume demonstrates how various methods from data mining, signal processing, optimization and cutting-edge medical techniques can be used to tackle the most challenging problems in modern neuroscience.

This volume contains the description of an EC-sponsered program to study all relevant aspects of shock/ boundary-layer interaction control, the latter designed to improve aircraft performance at design (cruise) and off-design conditions. The work being presented includes a discussion of basic control experiments and the corresponding physical modeling, to account for shock control and a discussion of the airfoil experiments conducted for code validation and control assessment, in conjunction with the basic experiments and computations. The contents is comprised of a section giving a broad overview of the research carried out here and more detailed individual contributions by the participants in the research.
Der Band enthalt den Abschlussbericht eines von EU geforderten Projekts EUROSHOCK, das alle relevanten Aspekte der Kontrolle von Stossfronten und Grenzschichten (wichtig z.B. fur die Verbesserung der Flugeigenschaften von Fluzeugen) untersuchte. Neben einer ausfuhrlichen Diskussion der grundlegenden Kontrollexperimente und der zugrundeliegenden Modellierung werden auch die Versuche an Tragflachen beschrieben, die zur Validierung von Modellrechnungen durchgefuhrt werden. Daruber hinaus enthalt der Band auch die detaillierten Ergebnisse der Teilnehmer an dem Forschungsprogramm."

Most real-world spectrum analysis problems involve the computation of the real-data discrete Fourier transform (DFT), a unitary transform that maps elements N of the linear space of real-valued N-tuples, R , to elements of its complex-valued N counterpart, C , and when carried out in hardware it is conventionally achieved via a real-from-complex strategy using a complex-data version of the fast Fourier transform (FFT), the generic name given to the class of fast algorithms used for the ef?cient computation of the DFT. Such algorithms are typically derived by explo- ing the property of symmetry, whether it exists just in the transform kernel or, in certain circumstances, in the input data and/or output data as well. In order to make effective use of a complex-data FFT, however, via the chosen real-from-complex N strategy, the input data to the DFT must ?rst be converted from elements of R to N elements of C . The reason for choosing the computational domain of real-data problems such N N as this to be C , rather than R , is due in part to the fact that computing equ- ment manufacturers have invested so heavily in producing digital signal processing (DSP) devices built around the design of the complex-data fast multiplier and accumulator (MAC), an arithmetic unit ideally suited to the implementation of the complex-data radix-2 butter?y, the computational unit used by the familiar class of recursive radix-2 FFT algorithms.

A new translation makes this classic and important text more generally accessible. The text is placed in its contemporary context, but also related to the interests of practising mathematicians today. This book will be of interest to mathematical historians, researchers, and numerical analysts.

An original motivation for algebraic geometry was to understand curves and surfaces in three dimensions. Recent theoretical and technological advances in areas such as robotics, computer vision, computer-aided geometric design and molecular biology, together with the increased availability of computational resources, have brought these original questions once more into the forefront of research. One particular challenge is to combine applicable methods from algebraic geometry with proven techniques from piecewise-linear computational geometry (such as Voronoi diagrams and hyperplane arrangements) to develop tools for treating curved objects. These research efforts may be summarized under the term nonlinear computational geometry. This volume grew out of an IMA workshop on Nonlinear Computational Geometry in May/June 2007 (organized by I.Z. Emiris, R. Goldman, F. Sottile, T. Theobald) which gathered leading experts in this emerging field. The research and expository articles in the volume are intended to provide an overview of nonlinear computational geometry. Since the topic involves computational geometry, algebraic geometry, and geometric modeling, the volume has contributions from all of these areas. By addressing a broad range of issues from purely theoretical and algorithmic problems, to implementation and practical applications this volume conveys the spirit of the IMA workshop.

Probably the first book to describe computational methods for numerically computing steady state and Hopf bifurcations. Requiring only a basic knowledge of calculus, and using detailed examples, problems, and figures, this is an ideal textbook for graduate students.

This book constitutes the refereed proceedings of the 11th International Symposium on Experimental Algorithms, SEA 2012, held Bordeaux, France, in June 2012. The 31 revised full papers presented together with 3 invited papers were carefully reviewed and selected from 64 submissions and present current research in the area of design, analysis, and experimental evaluation and engineering of algorithms, as well as in various aspects of computational optimization and its applications.

The papers presented here describe research to improve the general understanding of the application of SAMR to practical problems, to identify issues critical to efficient and effective implementation on high performance computers and to stimulate the development of a community code repository for software including benchmarks to assist in the evaluation of software and compiler technologies. The ten chapters have been divided into two parts reflecting two major issues in the topic: programming complexity of SAMR algorithms and the applicability and numerical challenges of SAMR methods.

This is a self-contained introduction to algebraic curves over finite fields and geometric Goppa codes. There are four main divisions in the book. The first is a brief exposition of basic concepts and facts of the theory of error-correcting codes (Part I). The second is a complete presentation of the theory of algebraic curves, especially the curves defined over finite fields (Part II). The third is a detailed description of the theory of classical modular curves and their reduction modulo a prime number (Part III). The fourth (and basic) is the construction of geometric Goppa codes and the production of asymptotically good linear codes coming from algebraic curves over finite fields (Part IV). The theory of geometric Goppa codes is a fascinating topic where two extremes meet: the highly abstract and deep theory of algebraic (specifically modular) curves over finite fields and the very concrete problems in the engineering of information transmission. At the present time there are two essentially different ways to produce asymptotically good codes coming from algebraic curves over a finite field with an extremely large number of rational points. The first way, developed by M. A. Tsfasman, S. G. Vladut and Th. Zink [210], is rather difficult and assumes a serious acquaintance with the theory of modular curves and their reduction modulo a prime number. The second way, proposed recently by A.

The study of optimal shape design can be arrived at by asking the following question: "What is the best shape for a physical system?" This book is an applications-oriented study of such physical systems; in particular, those which can be described by an elliptic partial differential equation and where the shape is found by the minimum of a single criterion function. There are many problems of this type in high-technology industries. In fact, most numerical simulations of physical systems are solved not to gain better understanding of the phenomena but to obtain better control and design. Problems of this type are described in Chapter 2. Traditionally, optimal shape design has been treated as a branch of the calculus of variations and more specifically of optimal control. This subject interfaces with no less than four fields: optimization, optimal control, partial differential equations (PDEs), and their numerical solutions-this is the most difficult aspect of the subject. Each of these fields is reviewed briefly: PDEs (Chapter 1), optimization (Chapter 4), optimal control (Chapter 5), and numerical methods (Chapters 1 and 4).

Energy levels, resonanees, vibrations, feature extraetion, faetor analysis - the names vary from discipline to diseipline; however, all involve eigenvalue/eigenveetor eomputations. An engineer or physicist who is modeling a physieal proeess, strueture, or deviee is eonstrained to seleet a model for whieh the subsequently-required eomputations ean be performed. This eonstraint often leads to redueed order or redueed size models whieh may or may not preserve all of the important eharaeteristies of the system being modeled. Ideally, the modeler should not be foreed to make such apriori reduetions. It is our intention to provide here proeedures wh ich will allow the direct and suceessful solution of many large 'symmetrie' eigenvalue problems, so that at least in problems where the computations are of this type there will be no need for model reduetion. Matrix eigenelement eomputations can be c1assified as smalI, medium, or large seale, in terms of their relative degrees of difficulty as measured by the amount of computer storage and time required to eomplete the desired eomputations. A matrix eigenvalue problem is said to be sm all scale if the given matrix has order smaller than 100. Well-documented and reliable FORTRAN pro grams exist for small scale eigenelement computations, see in particular ElS- PACK [1976,1977]. Typically those programs explicitly trans form the given matrix into a simpler canonieal form. The eigenelement eomputations are then performed on the canonical form.

Most of the papers in this volume were presented at the NATO Advanced Research Workshop High Performance Computing: Technology and Application, held in Cetraro, Italy from 24 to 26 of June, 1996. The main purpose of the Workshop was to discuss some key scientific and technological developments in high performance computing, identify significant trends and defme desirable research objectives. The volume structure corresponds, in general, to the outline of the workshop technical agenda: general concepts and emerging systems, software technology, algorithms and applications. One of the Workshop innovations was an effort to extend slightly the scope of the meeting from scientific/engineering computing to enterprise-wide computing. The papers on performance and scalability of database servers, and Oracle DBMS reflect this attempt We hope that after reading this collection of papers the readers will have a good idea about some important research and technological issues in high performance computing. We wish to give our thanks to the NATO Scientific and Environmental Affairs Division for being the principal sponsor for the Workshop. Also we are pleased to acknowledge other institutions and companies that supported the Workshop: European Union: European Commission DGIII-Industry, CNR: National Research Council of Italy, University of Calabria, Alenia Spazio, Centro Italiano Ricerche Aerospaziali, ENEA: Italian National Agency for New Technology, Energy and the Environment, Fujitsu, Hewlett Packard-Convex, Hitachi, NEC, Oracle, and Silicon Graphics-Cray Research. Editors January 1997 vii LIST OF CONTRIBUTORS Ecole Nonnale Sucentsrieure de Lyon, 69364 Abarbanel. Robert

The study of scan statistics and their applications to many different scientific and engineering problems have received considerable attention in the literature recently. In addition to challenging theoretical problems, the area of scan statis tics has also found exciting applications in diverse disciplines such as archaeol ogy, astronomy, epidemiology, geography, material science, molecular biology, reconnaissance, reliability and quality control, sociology, and telecommunica tion. This will be clearly evident when one goes through this volume. In this volume, we have brought together a collection of experts working in this area of research in order to review some of the developments that have taken place over the years and also to present their new works and point out some open problems. With this in mind, we selected authors for this volume with some having theoretical interests and others being primarily concerned with applications of scan statistics. Our sincere hope is that this volume will thus provide a comprehensive survey of all the developments in this area of research and hence will serve as a valuable source as well as reference for theoreticians and applied researchers. Graduate students interested in this area will find this volume to be particularly useful as it points out many open challenging problems that they could pursue. This volume will also be appropriate for teaching a graduate-level special course on this topic.

The history of continued fractions is certainly one of the longest among those of mathematical concepts, since it begins with Euclid's algorithm for the great est common divisor at least three centuries B.C. As it is often the case and like Monsieur Jourdain in Moliere's "Ie bourgeois gentilhomme" (who was speak ing in prose though he did not know he was doing so), continued fractions were used for many centuries before their real discovery. The history of continued fractions and Pade approximants is also quite im portant, since they played a leading role in the development of some branches of mathematics. For example, they were the basis for the proof of the tran scendence of 11' in 1882, an open problem for more than two thousand years, and also for our modern spectral theory of operators. Actually they still are of great interest in many fields of pure and applied mathematics and in numerical analysis, where they provide computer approximations to special functions and are connected to some convergence acceleration methods. Con tinued fractions are also used in number theory, computer science, automata, electronics, etc ..."

At the beginning we would like to introduce a refinement. The term 'VLSI planarization' means planarization of a circuit of VLSI, Le. the embedding of a VLSI circuit in the plane by different criteria such as the minimum number of connectors, the minimum total length of connectors, the minimum number of over-the-element routes, etc. A connector is designed to connect the broken sections of a net. It can be implemented in different ways depending on the technology. Connectors for a bipolar VLSI are implemented by diffused tun nels, for instance. By over-the-element route we shall mean a connection which intersects the enclosing rectangle of an element (or a cell). The possibility of the construction such connections during circuit planarization is reflected in element models and can be ensured, for example, by the availability of areas within the rectangles where connections may be routed. VLSI planarization is one of the basic stages (others will be discussed below) of the so called topological (in the mathematical sense) approach to VLSI design. This approach does not lie in the direction of the classical approach to automation of VLSI layout design. In the classical approach to computer aided design the placement and routing problems are solved successively. The topological approach, in contrast, allows one to solve both problems at the same time. This is achieved by constructing a planar embedding of a circuit and obtaining the proper VLSI layout on the basis of it."

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.