Lecture Notes ni Computer Science Edited by .G Goos dna .J sinamtraH 441 retupmoC arbeglA Algebra Computer Conference '82, EUROCAM European ,elliesraM ,ecnarF 5-7 April 1982 Calmet Jacques Edited by galreV-regnirpS Berlin Heidelberg NewYork 1982 Editorial Board .R.D Barstow, .W Brauer R Brinch Hansen .D Gries D.C. Luckham C. Moler A. Pnueli G. SeegmLiller .J Stoer .N Wirth Editor Jacques Calmet IMAG Laboratoire d'lnformatique etd e Mathematiques Appliquees de Grenoble BP 53, 38041 Grenoble Cedex, France CR Subject Classifications (t980): 5.7, 5.25 ISBN Springer-Verlag 3-540-11607-9 Berlin Heidelberg New York ISBN Springer-Verlag 0-387-11607-9 New York Heidelberg Berlin This work is subject to copyright. All rights are whether reserved, the whole or ~rap of the material is concerned, specifically those of translation, reprinting, re-use of illustrations, broadcasting, reproduction by photocopying machine or similar means, and storage in data banks. Under § 54 of the German Copyright Law where copies are made for other than private a use, fee is payable to "Verwertungsgesellschaft Wort", Munich. © by Springer-Verlag Berlin Heidelberg 1982 Printed in Germany Printing and binding: Bettz Offsetdruck, HemebachtBergstr. 012345-041315412 PREFACE EUROCAM '82 is the first major conference to be organized by the European computer algebra community. The symposia in the field previously held in Europe (Stockholm, 1974 and Marseilles, 1979) had for main sponsor and organizer the SIGSAM group of the ACM. In January of 1981 it was decided that the time for a purely Euro- pean conference had come. Indeed the number of researchers active in the field of computer algebra and the quality of their work had steadely increased over the recent years in our part of the world. This meeting has been held in Marseilles which has a long experien- ce in organizing similar colloquia. In fact EUROCAM '82 can as well be considered as being the sixth in the "International Colloquium on Advanced Computing Methods" series initialized in 1970 with A. Visconti. It was hosted by the newly operating "Centre Internatio- nal de Rencontres Mathematiques" in the Luminy campus of the Uni- versity of Aix-Marseille II which turned out to be a very pleasant meeting place. Invited, selected (referred), informal talks and demonstrations of systems were presented during the conference. Only the invited and selected ones appear in these proceedings. The selection of papers has been the responsability of the program committe with the help of outside referees when appropriate. When the decision to held EUROCAM '82 was taken it was assumed that both the number of papers submitted for selection and the number of attendees would be large enough to insure its success. This has indeed be true and one can predict that this is only the first one in a series of European conferences on Computer Algebra. As the main organizer of EUROCAM '82 I want to express my gratitude to Marc Bergman who was in charge of the local arrangements. This was not an easy job because the number of attendees was almost twice as large as expected. The program committee members spent much time and efforts in setting up the final program. Special thanks are deserved to the sessions chairmen who have been successful in keeping a strict schedule for the 55 communications presented during the three days of the conference. They are: G.E. Collins, .I Frick, J.P. Fitch, M. Mignotte, R. Loos, .J Davenport, A.C. Norman, J. Smit, P.S. Wang, J. van Hulzen, A.C. Hearn, J. Aman, D.R. Musser and M. Bergman. ACM and its specialzed group SIGSAM have given to EUROCAM '82 their official approval for cooperation. This was showing their confidence in the scientific quality of this first European conference. Besides this motivation when applying for it I was driven by a very personal will of keeping closed links with this world-wide professional organization. I am grateful to the SIGSAM chairman, Tony Hearn, for helping me with this application. Jacques Calmet IMAG, Grenoble REMERCIEMENTS Organiser une conf6rence internationale requiert certainement de nombreux efforts de la part de nombreuses personnes. Toutefois ces efforts seraient vains si de g~n~reuses institutions ne mettaient pas ~ la disposition des organisateurs les moyens financiers n~ces- saires. EUROCAM '82 a eu la chance d'etre jug~ digne d'int~r~t scientifique par la DRET (Direction des Recherches, Etudes et Techniques du Minist~re de la D~fense), l'Universit~ d'Aix-Marseille II, la SMF(Soci~t~ Math~matique de France) et le CNRS (Centre National de la Recherche Scientifique) par l'interm~diaire de la RCP (Recherche Cooperative sur Programme) g~r~e par la SMF. Nous remercions ces organismes pour leurs aides financi~res importantes qui ont grandement contributes au succ~s de cette conference. M. Bergman et J. Calmet ORGANIZING COMMITTEE PROGRAM CHAIRMAN: J. Calmet, Grenoble, France PROGRAM COMMITTEE: B. Buchberger, Linz, Austria J.H. Davenport, Cambridge, Great Britain J.P. Fitch, Bath, Great Britain I.B. Frick, Stockholm, Sweden R.G. Loos, Karlsruhe, West Germany LOCAL ARRANGEMENTS: M. Bergman, Marseille, France PROCEEDINGS EDITOR: J. Calmet, Grenoble, France AUTHORS INDEX Alagar ............... 16 Laue ................. 65 Angerer .............. 57 Lazard ............... 40, 126 Arnon ................ 215 Lenstra .............. 32 Avenhaus ............. 49 Lomecky .... .......... 223 Bergman .............. 91 Loos ................. 117 Bordoni .............. 231 Madlener ............. 49 Buchberger ........... 24 Malm ................. 289 Bundy ................ 109 Marti ................ 249 Byrd ................. 109 McCallum ............. 215 Calmet ............... 117 Miola ................ 231 Campbell ............. 196 Moller ............... 24 Claude ............... 294 Mora ................. 158 Colagrossi ........... 231 Musser ............... 77 Collins .............. 212 Norman ............... 237 Davenport ............ 144 O'Keefe .............. 109 Della Dora ........... 273 Padget ............... 256 Di Crescenzo ......... 273 Pilz ................. 57 Dufresne ............. 294 Pohst ................ 71 Fitch ................ 249 Probst ............... 16 Gardin ............... 196 Raulefs .............. 302 Gragert .............. 181 Schonhage ............ 3 Hearn ................ 263 Silver ............... 109 Hornfeldt ............ 188 Smit ................. 281 Kapur ................ 77 Sterling ............. 109 Kersten .............. 181 Tournier ............. 273 Kuchlin .............. 101 Van Hulzen ........... 166, 281 Lamnabhi ............. 204 Wang ................. 135 Lamnabhi-Lagarrigue .. 204 TABLE OF CONTENTS 0. INTRODUCTION ............................................... 1 i. ALGORITHMS I "Asymptotically fast algorithms for the numerical multiplication and division of polynomials with complex coefficients.~ (Invited) .......................... 3 A. Scbonhage, Univ. Tvb~ngen "An adaptive hybrid algorithm for multiplying dense polynomials.". ............................................. 16 D. Probst and V.S. Alagar, Concordia Univ., Montreal "The construction of multivariate polynomials with preassigned zeros." ........................................ 24 H.M. M611er and B. Buchberger, Fernuniversitat, Hagen and J. kepler Univ., Linz "Lattices and factorization of polynomials over algebraic number fields." .................................. 32 A.K. Lenstra, Math. Centrum, Amsterdam 2. ALGEBRAIC STRUCTURES "Commutative Algebra and Computer Algebra." (Invited) ....... 40 D. Lazard, Univ. Poitiers "The Nielsen reduction as key problem to polynomial algorithms in free groups." ................................ 49 J. Avenhaus and K. Madlener, Univ. Kaiserslautern "The structure of near-rings of small Order." ............... 57 J. Angerer and G. Pilz, J. Kepler Univ., Linz "Computing double coset representatives for the generation of solvable groups." ............................ 65 R. Laue, RWTH, Aachen "On the determination of algebraic number fields of given discriminant.". ...................................... 71 M. Pohst, Univ. D~eldorf 3. ABSTRACT DATA TYPES AND REWRITE RULES "Rewrite rule theory and abstract data type analysis." (Invited) ....................................... 77 D.R. Musser and Deepak Kapur, General Electric Co. Schenectady XII "Algebraic specifications:a constructive methodology in logic programming.". .................................... 91 M. Bergman, Univ. Aix-Marseille II "A theorem-proving approach to the Knuth-Bendix completion algorithm.". .................................... i01 W. KUchlin, Univ. of Karlsruhe "Solving symbolic equations with PRESS." .................... 109 L. Sterling, A. Bundy, L. Byrd, R. O'Keefe and B. Silver, Univ. of Edinburgh 4. ALGORITHMS II "Deterministic versus probabilistic factorization of integral polynomials..". ................................ 117 J. Calmet and R. Loos, IMAG, Grenoble and Univ. Karlsruhe "On polynomial factorization." .............................. 126 D. Lazard, Univ. Poitiers "H~cijan's algorithm in VAXIMA: improvements and difficulties.". ............................................ 135 P.S. Wang, Kent State Univ. "The parallel Risch algorithm (I)." ......................... 144 J.H. Davenport, Univ. of Cambridge "An algorithm to compute the equations of tangent cones." .................................................... 158 F. Mora, Univ. Genova 5. APPLICATIONS I "Computer algebra systems viewed by a notorious user." (Invited) .................................................. 166 J.A. van Hulzen, Twente Univ. Tech. "Implementation of differential geometric objects and functions with an application to extended Maxwell equations.". ............................................... 181 P.K.H. Gragert and P.H.M. Kersten, Twente Univ. Technology "A sum-substitutor used as trigonometric simplifier." ............................................... 188 L. Hornfeldt, Univ. of Stockholm "Transformation of an intractable problem into a tractable problem: evaluation of a determinant in several variables." ......................... 196 J.A. Campbell and F. Gardin, Univ. of Exeter IIIX "Algebraic computation of the solution of some non linear differential equations.". ....................... 204 F. Lamnabhi-Lagarrigue and M. Lamnabhi, LSE Gif sur Yvette 6. ALGORITHMS III "Factorization in cylindrical algebraic decomposition." (Invited) .................................. 212 G.E. Collins, Univ. of Wisconsin-Madison "Cylindrical algebraic decomposition by quantifier elimination..". ............................................ 215 D.S. Arnon and S. McCallum, Purdue Univ and Univ. of Wisconsin-Madison "Algorithms for the computation of free lattices." .......... 223 .Z Lomecky, ETH Zurich "Linear algebraic approach for computing polynomial resultant." ................................................ 231 L. Bordoni, A. Colagrossi and A. Miola, IASI, Roma 7. SYSTEMS "The development of a vector-based algebra system." (Invited).. ....................................... 237 A.C. Norman, Univ. of Cambridge "NLARGEing a Z80 microprocessor." ........................... 249 J.P. Fitch and J. Marti, Univ. of Bath and Univ. of Oregon "Escaping from intermediate expression swell: a continuing saga." ........................................ 256 J.A. Padget, Univ. of Bath "REDUCE A case study in algebra system development."(Invited) - ..................................... 263 A.C. Hearn, The Rand Corp., Santa Monica 8. APPLICATIONS II "An algorithm to obtain formal solutions Of a linear homogeneous differential equation at an irregular singular point.". .......................................... 273 J. Della Dora, C. Di Crescenzo and E. Tournier, IMAG, Grenoble "Symbolic-numeric methods in microwave technology.". ........ 281 J. Smit and J.A. van Hulzen, Twente Univ. Tech. XIV "A program in REDUCE for finding explicit solutions to certain ordinary differential equations." ............... 289 B. Malm, Univ. of Stockholm "An application of MACSYMA to nonlinear systems decoupling." ............................................... 294 D. Claude and P. Dufresne, LSE, Gif sur Yvette and Ecole Polytechnique, Palaiseau