Computing Supplementa – serie

This volume contains mainly a collection of the invited lectures which were given during a conference on "Fundamentals of Numerical Computation", held in June, 5 - 8, 1979, on the occasion of the centennial of the Technical University of Berlin. About hundred scientists from several countries attended this conference. A preceding meeting on "Fundamentals of Computer-Arithmetic" was held in August, 1975, at the "Mathematisches Forschungsinstitut Oberwolfach". The lectures of this conference have been published as Supplementum 1 of Computing (Editors R. Albrecht, U. Kulisch). After a period of four years of active research the purpose of the Berlin-Conference was to give a broad survey of the present status of the closely connected topics Interval Analysis, Mathematical Foundation of Computer Arithmetic, Rounding Error Analysis and Stability of Numerical Algorithms and to give prospects of future activities in these fields. Besides the invited lectures 35 short com- munications, each of 20 minutes length, were given. We gratefully acknowledge the support of the President of the Technical University and of his Aussenreferat as well as of the Department of Mathematics.Besides these institutions financial support was given by AEG-Telefunken, Berlin, Allianz Lebensversicherungs A.G., Stuttgart, CDC, Hamburg/Berlin, DAT A 100, Munchen, Gesellschaft von Freunden der TU Berlin e.V., Berlin and Siemens AG., Berlin. Finally we express our thanks to Mrs. G. Froehlich and Mrs. B. Trajanovic, who managed the paper work before, during and after the conference.

The third supplement volume of "Computing" deals with parallel processes and thus with a highly topical area of informatics. As both the first supplement volumes were concerned with numerical questions, the entire subject, the cultivation of which "Computing" purports, is now broadly outlined in the supplement volumes too. The reason for the simultaneous production of so many papers on the same subject was the 60th birthday of Prof. Dr. Wolfgang Handler, an eminent specialist in the field of parallel processing. It was the wish of his friends, colleagues and collaborators that Herr Handler be honoured by the gift of a volume which would have as its centre of interest the area of research that he represents. In this volume, parallelism is focused upon from various angles and an attempt has been made, through new results, to bring it a little further. It is obvious from a glance at the bibliographies of the papers contributed, in which many of Herr Handler's publications are referenced, that he was never far from the writer's minds.

this gap. In sixteen survey articles the most important theoretical results, algorithms and software methods of computer algebra are covered, together with systematic references to literature. In addition, some new results are presented. Thus the volume should be a valuable source for obtaining a first impression of computer algebra, as well as for preparing a computer algebra course or for complementary reading. The preparation of some papers contained in this volume has been supported by grants from the Austrian "Fonds zur Forderung der wissenschaftlichen For­ schung" (Project No. 3877), the Austrian Ministry of Science and Research (Department 12, Dr. S. Hollinger), the United States National Science Foundation (Grant MCS-8009357) and the Deutsche Forschungsgemeinschaft (Lo-23 1-2). The work on the volume was greatly facilitated by the opportunity for the editors to stay as visitors at the Department of Computer and Information Sciences, University of Delaware, at the General Electric Company Research and Development Center, Schenectady, N. Y. , and at the Mathematical Sciences Department, Rensselaer Polytechnic Institute, Troy, N. Y. , respectively. Our thanks go to all these institutions. The patient and experienced guidance and collaboration of the Springer-Verlag Wien during all the stages of production are warmly appreciated. The editors of the Cooperative editor of Supplementum Computing B. Buchberger R. Albrecht G. Collins R. Loos Contents Loos, R. : Introduction. . . . . . . . . . . . . . . . . . . . . . . . . . 1 Buchberger, B. , Loos, R. : Algebraic Simplification . . . . . . . . . . 11 Neubiiser, J. : Computing with Groups and Their Character Tables. 45 Norman, A. C. : Integration in Finite Terms. . . . . . . . . . . . . .

Ten years ago, the term "defect correction" was introduced to characterize a class of methods for the improvement of an approximate solution of an operator equation. This class includes many well-known techniques (e.g. Newton's method) but also some novel approaches which have turned out to be quite efficient. Meanwhile a large number of papers and reports, scattered over many journals and institutions, have appeared in this area. Therefore, a working conference on "Error Asymptotics and Defect Corrections" was organized by K. Bohmer, V. Pereyra and H. J. Stetter at the Mathematisches Forschungsinstitut Oberwolfach in July 1983, a meeting which aimed at bringing together a good number of the scientists who are active in this field. Altogether 26 persons attended, whose interests covered a wide spectrum from theoretical analyses to applications where defect corrections may be utilized; a list of the participants may be found in the Appendix. Most of the colleagues who presented formal lectures at the meeting agreed to publish their reports in this volume. It would be presumptuous to call this book a state-of-the-art report in defect corrections. It is rather a collection of snapshots of activities which have been going on in a number of segments on the frontiers of this area. No systematic coverage has been attempted. Some articles focus strongly on the basic concepts of defect correction; but in the majority of the contributions the defect correction ideas appear rather as instruments for the attainment of some specified goal.

This computing supplementum collects a number of original contributions which all aim to compute rigorous and reliable error bounds for the solution of numerical problems. An introductory article by the editors about the meaning and diverse methods of automatic result verification is followed by 16 original contributions. The first chapter deals with automatic result verification for standard mathematical problems, such as enclosing the solution of ordinary boundary value problems, linear programming problems, linear systems of equations and eigenvalue problems. The second chapter deals with applications of result verification methods to problems of the technical sciences. The contributions consider critical bending vibrations stability tests for periodic differential equations, geometric algorithms in the plane, and the periodic solution of the oregonator, a mathematical model in chemical kinetics. The contributions of the third chapter are concerned with extending and developing the tools required in scientific computation with automatic result verification.

One ofthe most important aspects in research fields where mathematics is "applied is the construction of a formal model of a real system. As for structural relations, graphs have turned out to provide the most appropriate tool for setting up the mathematical model. This is certainly one of the reasons for the rapid expansion in graph theory during the last decades. Furthermore, in recent years it also became clear that the two disciplines of graph theory and computer science have very much in common, and that each one has been capable of assisting significantly in the development of the other. On one hand, graph theorists have found that many of their problems can be solved by the use of com­ puting techniques, and on the other hand, computer scientists have realized that many of their concepts, with which they have to deal, may be conveniently expressed in the lan­ guage of graph theory, and that standard results in graph theory are often very relevant to the solution of problems concerning them. As a consequence, a tremendous number of publications has appeared, dealing with graphtheoretical problems from a computational point of view or treating computational problems using graph theoretical concepts.

In this volume experts from university and industry are presenting new technologies for solving industrial problems as well as important and practicable impulses for new research.The following topics are treated:- solid modelling- geometry processing- feature modelling- product modelling- surfaces over arbitrary topologies- blending methods- scattered data algorithms- smooting and fairing algorithms- NURBS 21 articles are giving a state-of-the-art survey of the relevant problems and issues in the rapidly growing area of geometric modelling.

The articles in this book give a comprehensive overview on the whole field of validated numerics. The problems covered include simultaneous systems of linear and nonlinear equations, differential and integral equations and certain applications from technical sciences. Furthermore some papers which improve the tools are included. The book is a must for scientists working in numerical analysis, computer science and in technical fields.

This collection of 24 articles gives a state-of-the-art survey of the relevant problems and issues in geometric modelling. Experts from university and industry are presenting new technologies for solving industrial problems and giving many important and practical impulses for new research. Topics explored include NURBS, product engineering, object-oriented modelling, surface interrogation, feature modelling, variational design, scattered data algorithms, geometry processing, blending methods, smoothing and fairing algorithms, spline conversion.

Computer Vision is a rapidly growing field of research investigating computational and algorithmic issues associated with image acquisition, processing, and understanding. It serves tasks like manipulation, recognition, mobility, and communication in diverse application areas such as manufacturing, robotics, medicine, security and virtual reality. This volume contains a selection of papers devoted to theoretical foundations of computer vision covering a broad range of fields; e.g. motion analysis, discrete geometry, computational aspects of vision processes, models, morphology, invariance, image compression, 3D reconstruction of shape. Several issues have been identified that are of essential interest to the community: non-linear operators; the transition between continuous to discrete representations; a new calculus of non-orthogonal partially dependent systems.

Graph-based representation of images is becoming a popular tool since it represents in a compact way the structure of a scene to be analyzed and allows for an easy manipulation of sub-parts or of relationships between parts. Therefore, it is widely used to control the different levels from segmentation to interpretation.The 14 papers in this volume are grouped in the following subject areas: hypergraphs, recognition and detection, matching, segmentation, implementation problems, representation.

19 papers presented by international experts give a state-of-the-art survey of the relevant problems and issues in modeling, CAD/CAM, scientific visualization, and computational geometry. The following topics are treated: - surface design and fairing - subdivision schemes - variational design - NURBS - reverse engineering - physically-based modelling - medical imaging.

Geometric Modelling is concerned with the computer aided design, manipulation, storage and transmission of geometric shape. It provides fundamental techniques to different areas of application as CAD/CAM, computer graphics, scientific visualization, and virtual Reality. 20 papers presented by leading experts give a state-of-the-art survey of the following topics: surface design and fairing; multiresolution models; reverse engineering; solid modelling; constrained based modelling.

This collection of papers on numerical analysis with special emphasis on nonlinear problems covers a broad spectrum of fields. Several papers are involved in applying numerical methods for proving the existence of solutions of nonlinear problems, e.g. of boundary problems or of obstacle problems. Naturally the solution of linear and nonlinear problems by iterative methods is the subject of a couple of papers. Here such topics as the fast verification of solutions of monotone matrix equations, the convergence of linear asynchronous iteration with spectral radius of modulus one or aggregation and disaggregation methods for p-cyclic Markov chains are treated. On the other hand, papers involved in optimization problems can also be found. Nearly all fields of modern numerical analysis are touched by at least one paper.