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.

Scientific Computation with Result Verification has been a persevering research topic at the Institute for Applied Mathematics of Karlsruhe University for many years. A good number of meetings have been devoted to this area. The latest of these meetings was held from 30 September to 2 October, 1987, in Karlsruhe; it was co-sponsored by the GAMM Committee on "Computer Arithmetic and Scientific Computation". - - This volume combines edited versions of selected papers presented at this confer­ ence, including a few which were presented at a similar meeting one year earlier. The selection was made on the basis of relevance to the topic chosen for this volume. All papers are original contributions. In an appendix, we have supplied a short account of the Fortran-SC language which permits the programming of algorithms with result verification in a natural manner. The editors hope that the publication of this material as a Supplementum of Computing will further stimulate the interest of the scientific community in this important tool for Scientific Computation. In particular, we would like to make application scientists aware of its potential. The papers in the second chapter of this volume should convince them that automatic result verification may help them to design more reliable software for their particular tasks. We wish to thank all contributors for adapting their manuscripts to the goals of this volume. We are also grateful to the Publisher, Springer-Verlag of Vienna, for an efficient and quick production.

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.

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

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 to be 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 volume contains eighteen papers submitted in celebration of the sixty-fifth birthday of Professor Tetsuro Yamamoto of Ehime University. Professor Yamamoto was born in Tottori, Japan on January 4, 1937. He obtained his B. S. and M. S. in mathematics from Hiroshima University in 1959 and 1961, respec­ tively. In 1966, he took a lecturer position in the Department of Mathematics, Faculty of General Education, Hiroshima University and obtained his Ph. D. degree from Hiroshima University two years later. In 1969, he moved to the Department of Applied Mathematics, Faculty of Engineering, Ehime University as an associate professor and he has been a full professor of the Department of Mathematics (now Department of Mathematical Sciences), Faculty of Science, since 1975. At the early stage of his study, he was interested in algebraic eigen­ value problems and linear iterative methods. He published some papers on these topics in high level international journals. After moving to Ehime University, he started his research on Newton's method and Newton-like methods for nonlinear operator equations. He published many papers on error estimates of the methods. He established the remarkable result that all the known error bounds for Newton's method under the Kantorovich assumptions follow from the Newton-Kantorovich theorem, which put a period to the race of finding sharper error bounds for Newton's method.