Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben

1983 | Buch | 2. Auflage

Introduction Kapitel lesen Erstes Kapitel lesen

Computer Algebra

Symbolic and Algebraic Computation

herausgegeben von: Prof. Dr. Bruno Buchberger, Prof. Dr. George Edwin Collins, Prof. Dr. Rüdiger Loos, Prof. Dr. Rudolf Albrecht

Verlag: Springer Vienna

Buchreihe : Computing Supplementum

Enthalten in: Professional Book Archive

Einloggen, um Zugang zu erhalten
insite
SUCHEN

Über dieses Buch

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

Inhaltsverzeichnis

Frontmatter
Introduction
Abstract
In this introduction we first give a working defmition of Computer algebra. We then describe the Organization of research activities in this field. Finally the overall structure and the intention of the present volume on Computer algebra is explained. Some technical information (basic references, notation etc.) about the volume is given.
R. Loos
Algebraic Simplification
Abstract
Some basic techniques for the simplification of terms are surveyed. In two introductory sections the problem of canonical algebraic simplification is formally stated and some elementary facts are derived that explain the fundamental role of simplification in Computer algebra. In the subsequent sections two major groups of simplification techniques are presented: special techniques for simplifying terms over numerical domains and completion algorithms for simplification with respect to sets of equations. Within the first group canonical simplification algorithms for polynomials, rational expressions, radical expressions and transcendental expressions are treated (Sections 3–7). As examples for completion algorithms the Knuth-Bendix algorithm for rewrite rules and an algorithm for completing bases of polynomial ideals are described (Sections 8–11).
B. Buchberger, R. Loos
Computing with Groups and Their Character Tables
Abstract
In this survey an attempt is made to give some impression of the eapabilities of currently available programs for computations with finitely generated groups and their representations.
J. Neubüser
Integration in Finite Terms
Abstract
A survey on algorithms for integration in finite terms is given. The emphasis is on indefinite integration. Systematic methods for rational, algebraic and elementary transcendental integrands are reviewed. Heuristic techniques for indefinite integration, and techniques for definite integration and ordinary differential equations are touched on only briefly.
A. C. Norman
Summation in Finite Terms
Abstract
A survey on algorithms for summation in finite terms is given. After a precise defmition of the problem the cases of polynomial and rational summands are treated. The main concern of this paper is a description of Gosper’s algorithm, which is applicable for a wide class of summands. Karr’s theory of extension difference fields and some heuristic techniques are touched on briefly.
J. C. Lafon
Quantifier Elimination for Real Closed Fields: A Guide to the Literature
Abstract
This article provides a brief summary of the most important publications relating to quantifier elimination algorithms for the elementary theory of real closed fields. Especially mentioned is the cylindrical algebraic decomposition method and its relation to the facilities of Computer algebra facilities.
G. E. Collins
Real Zeros of Polynomials
Abstract
Let A be a polynomial over Z, Q or Q(α) where α is a real algebraic number. The problem is to compute a sequence of disjoint intervals with rational endpoints, each containing exactly one real zero of A and together containing all real zeros of A. We describe an algorithm due to Kronecker based on the minimum root Separation, Sturm’s algorithm, an algorithm based on Rolle’s theorem due to Collins and Loos and the modified Uspensky algorithm due to Collins and Aritas. For the last algorithm a recursive version with correctness proof is given which appears in print for the first time.
G. E. Collins, R. Loos
Factorization of Polynomials
Abstract
Algorithms for factoring polynomials in one or more variables over various coefficient domains are discussed. Special emphasis is given to finite fields, the integers, or algebraic extensions of the rationals, and to multivariate polynomials with integral coefficients. In particular, various squarefree decomposition algorithms and Hensel lifting techniques are analyzed. An attempt is made to establish a complete historic trace for today’s methods. The exponential worst case complexity nature of these algorithms receives attention.
E. Kaltofen
Generalized Polynomial Remainder Sequences
Abstract
Given two polynomials over an integral domain, the problem is to compute their polynomial remainder sequence (p.r.s.) over the same domain. Following Habicht, we show how certain powers of leading coefficients enter systematically all following remainders. The key tool is the subresultant chain of two polynomials. We study the primitive, the reduced and the improved subresultant p.r.s. algorithm of Brown and Collins as basis for Computing polynomial greatest common divisors, resultants or Sturm sequences. Habicht’s subresultant theorem allows new and simple proofs of many results and algorithms found in different ways in Computer algebra.
R. Loos
Computing by Homomorphic Images
Abstract
After explaining the general technique of Computing by homomorphic images, the Chinese remainder algorithm and the Hensel lifting construction are treated extensively. Chinese remaindering is first presented in an abstract setting. Then the specialization to Euclidean domains, in particular Z, K[y] and Z[y 1,…,y r ] is treated. The lifting construction is first also presented in an abstract form from which Henss Lemma derives by specialization. After introducing Zassenhaus’ quadratic lifting construction, again, the case of Z and Z[y 1,…,y r ]is considered. For both techniques, Chinese remaindering as well as the lifting algorithms, a complete computational example is presented and the most frequent applications are discussed.
M. Lauer
Computing in Transcendental Extensions
Abstract
Performing the rational Operations in a field extended by a transcendental element is equivalent to performing arithmetic in the field of rational functions over the field. The computational difficulty associated with such extensions is in verifying that proposed extensions are transcendental. When the extensions being considered are functions, and where a differentiation operator can be defined for them, strueture theorems can be used to determine the character of the extension and to exhibit a relationship between the adjoined element and existing quantities in case the adjoined element is not transcendental.
A. C. Norman
Computing in Algebraic Extensions
Abstract
The aim of this chapter is an introduction to elementary algorithms in algebraic extensions, mainly over Q and, to some extent, over GF(p). We will talk about arithmetic in Q(α) and GF(p n ) in Section 1 and some polynomial algorithms with coefficients from these domains in Section 2. Then, we will consider the field K of all algebraic numbers over Q and show constructively that K indeed is a field, that multiple extensions can be replaced by single ones and that K is algebraically closed, i.e. that zeros of algebraic number polynomials will be elements of K (Section 4 — 6). For this purpose we develop a simple resultant calculus which reduces all Operations on algebraic numbers to polynomial arithmetic on long integers together with some auxiliary arithmetic on rational intervals (Section 3). Finally, we present some auxiliary algebraic number algorithms used in other chapters of this volume (Section 7). This chapter does not include any special algorithms of algebraic number theory. For an introduction and survey with an extensive bibliography the reader is referred to Zimmer [15].
R. Loos
Arithmetic in Basic Algebraic Domains
Abstract
This chapter is devoted to the arithmetic Operations, essentially addition, multiplication, exponentiation, division, gcd calculation and evaluation, on the basic algebraic domains. The algorithms for these basic domains are those most frequently used in any Computer algebra system. Therefore the best known algorithms, from a computational point of view, are presented. The basic domains considered here are the rational integers, the rational numbers, integers modulo m, Gaussian integers, polynomials, rational functions, power series, finite fields and P-adic numbers. Bounds on the maximum, minimum and average Computing time (t +, t -, t*) for the various algorithms are given.
G. E. Collins, M. Mignotte, F. Winkler
Computer Algebra Systems
Abstract
A survey is given of Computer algebra systems, with emphasis on design and implementation aspects, by presenting a review of the development of ideas and methods in a historical perspective, by us considered as instrumental for a better understanding of the rich diversity of now available facilities. We first indicate which classes of mathematical expressions can be stated and manipulated in different systems before we touch on different general aspects of usage, design and implementation, such as language design, encoding, dynamic storage allocation and a symbolic-numeric interface. Then we discuss polynomial and rational function systems, by describing ALTRAN and SAC-2. This is followed by a comparison of some of the features of MATHLAB-68, SYMBAL and FORMAC, which are pretended general purpose systems. Before considering giants (MACSYMA and SCRATCHPAD) and gnomes (muMATH-79), we give the main characteristics of TRIGMAN, CAMAL and REDUCE, systems we tend to consider as grown out special purpose facilities. Finally we mention some modern algebra systems (CAYLEY and CAMAC-79) in relation to recent proposals for a language for computational algebra. We conclude by stipulating the importance of documentation. Throughout this discussion related systems and facilities will be mentioned. Noticeable are ALKAHEST II, ALP AK, ANALITIK, ASHMEDAI, NETFORM, PM, SAC-1, SCHOONSCHIP, SHEEP, SMP, SYCOPHANTE and TAYLOR.
J. A. van Hulzen, J. Calmet
Computer Algebra Applications
Abstract
A survey of applications based either on fundamental algorithms in Computer algebra or on the use of a Computer algebra system is presented. Since many survey articles are previously published, we did not attempt to be exhaustive. We discuss mainly recent work in biology, chemistry, physics, mathematics and Computer science, thus again confirming that applications have both engineering and scientific aspects, i.e. apart from delivering results they assist in gaining insight as well.
J. Calmet, J. A. van Hulzen
Some Useful Bounds
Abstract
Some fundamental inequalities for the following values are listed: the determinant of a matrix, the absolute value of the roots of a polynomial, the coefficients of divisors of polynomials, and the minimal distance between the roots of a polynomial. These inequalities are useful for the analysis of algorithms in various areas of Computer algebra.
M. Mignotte
Backmatter
Metadaten
Titel
Computer Algebra
herausgegeben von
Prof. Dr. Bruno Buchberger
Prof. Dr. George Edwin Collins
Prof. Dr. Rüdiger Loos
Prof. Dr. Rudolf Albrecht
Copyright-Jahr
1983
Verlag
Springer Vienna
Electronic ISBN
978-3-7091-7551-4
Print ISBN
978-3-211-81776-6
DOI
https://doi.org/10.1007/978-3-7091-7551-4