Modular Algorithms in Symbolic Summation and Symbolic Integration [Gerhard 2005-01-12].pdf

(3578 KB) Pobierz
Lecture Notes in Computer Science
Commenced Publication in 1973
Founding and Former Series Editors:
Gerhard Goos, Juris Hartmanis, and Jan van Leeuwen
3218
Editorial Board
David Hutchison
Lancaster University, UK
Takeo Kanade
Carnegie Mellon University, Pittsburgh, PA, USA
Josef Kittler
University of Surrey, Guildford, UK
Jon M. Kleinberg
Cornell University, Ithaca, NY, USA
Friedemann Mattern
ETH Zurich, Switzerland
John C. Mitchell
Stanford University, CA, USA
Moni Naor
Weizmann Institute of Science, Rehovot, Israel
Oscar Nierstrasz
University of Bern, Switzerland
C. Pandu Rangan
Indian Institute of Technology, Madras, India
Bernhard Steffen
University of Dortmund, Germany
Madhu Sudan
Massachusetts Institute of Technology, MA, USA
Demetri Terzopoulos
New York University, NY, USA
Doug Tygar
University of California, Berkeley, CA, USA
Moshe Y. Vardi
Rice University, Houston, TX, USA
Gerhard Weikum
Max-Planck Institute of Computer Science, Saarbruecken, Germany
Jürgen Gerhard
Modular Algorithms
in Symbolic Summation
and Symbolic Integration
13
Author
Jürgen Gerhard
Maplesoft
615 Kumpf Drive, Waterloo, ON, N2V 1K8, Canada
E-mail: Gerhard.Juergen@web.de
This work was accepted as PhD thesis on July 13, 2001, at
Fachbereich Mathematik und Informatik
Universität Paderborn
33095 Paderborn, Germany
Library of Congress Control Number: 2004115730
CR Subject Classification (1998): F.2.1, G.1, I.1
ISSN 0302-9743
ISBN 3-540-24061-6 Springer Berlin Heidelberg New York
This work is subject to copyright. All rights are reserved, whether the whole or part of the material is
concerned, specifically the rights of translation, reprinting, re-use of illustrations, recitation, broadcasting,
reproduction on microfilms or in any other way, and storage in data banks. Duplication of this publication
or parts thereof is permitted only under the provisions of the German Copyright Law of September 9, 1965,
in its current version, and permission for use must always be obtained from Springer. Violations are liable
to prosecution under the German Copyright Law.
Springer is a part of Springer Science+Business Media
springeronline.com
© Springer-Verlag Berlin Heidelberg 2004
Printed in Germany
Typesetting: Camera-ready by author, data conversion by Boller Mediendesign
Printed on acid-free paper
SPIN: 11362159
06/3142
543210
Foreword
This work brings together two streams in computer algebra: symbolic integration
and summation on the one hand, and fast algorithmics on the other hand.
In many algorithmically oriented areas of computer science, the
analysis of al-
gorithms
– placed into the limelight by Don Knuth’s talk at the 1970 ICM – provides
a crystal-clear criterion for success. The researcher who designs an algorithm that is
faster (asymptotically, in the worst case) than any previous method receives instant
gratification: her result will be recognized as valuable. Alas, the downside is that
such results come along quite infrequently, despite our best efforts.
An alternative evaluation method is to run a new algorithm on examples; this
has its obvious problems, but is sometimes the best we can do. George Collins, one
of the fathers of computer algebra and a great experimenter, wrote in 1969: “I think
this demonstrates again that a simple analysis is often more revealing than a ream
of empirical data (although both are important).”
Within computer algebra, some areas have traditionally followed the former
methodology, notably some parts of polynomial algebra and linear algebra. Other
areas, such as polynomial system solving, have not yet been amenable to this ap-
proach. The usual “input size” parameters of computer science seem inadequate,
and although some natural “geometric” parameters have been identified (solution
dimension, regularity), not all (potential) major progress can be expressed in this
framework.
Symbolic integration and summation have been in a similar state. There are
some algorithms with analyzed run time, but basically the mathematically oriented
world of integration and summation and the computer science world of algorithm
analysis did not have much to say to each other.
Gerhard’s progress, presented in this work, is threefold:
•
a clear framework for algorithm analysis with the appropriate parameters,
•
the introduction of modular techniques into this area,
•
almost optimal algorithms for the basic problems.
One might say that the first two steps are not new. Indeed, the basic algorithms
and their parameters – in particular, the one called dispersion in Gerhard’s work
– have been around for a while, and modular algorithms are a staple of computer
algebra. But their combination is novel and leads to new perspectives, the almost
optimal methods among them.

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin