Skip to the content of the web site.

 

Keith O Geddes

Key Research Contributions


Maple Software

I am co-founder of the Maple research project in the Symbolic Computation Group at the University of Waterloo and co-founder of the software company Maplesoft. Contributions of code which has been incorporated into the Maple computer algebra system represents my most significant contribution to research and to practical applications.

Documentation for this work is represented by the Maple reference books:

The Maple system has achieved an influential position worldwide as a research and teaching tool in engineering, mathematics, and science.

For some presentations on the history of the Maple project, see Maple Archives.

Back to top


Textbook on Algebraic Algorithms

  • K.O. Geddes, S.R. Czapor and G. Labahn, Algorithms for Computer Algebra. Kluwer Academic Publishers, Boston, 1992, 585 pages.
  • This book develops the mathematical foundations for the fundamental algorithms used by computer algebra systems.

    Back to top


    On the Design of Maple

    Two papers published in 1983 and 1984 set out the design criteria for Maple and present some performance measurements.

  • B.W. Char, K.O. Geddes, W.M. Gentleman and G.H. Gonnet, The design of Maple: A compact, portable and powerful computer algebra system. Appears in Computer Algebra (Proceedings of EUROCAL '83), J.A. van Hulzen (ed.), Lecture Notes in Computer Science, No. 162, Springer-Verlag, Berlin, 1983, pp. 101—115.

    See also: Technical Report CS-83-06, 1983 http://www.cs.uwaterloo.ca/research/tr/

  • B.W. Char, G.J. Fee, K.O. Geddes, G.H. Gonnet, M.B. Monagan and S.M. Watt, On the design and performance of the Maple system. Proceedings of the 1984 MACSYMA Users' Conference, V. Ellen Golden (ed.), General Electric, Schenectady, New York, 1984, pp. 199—219.

    Online paper: Design84

    Extended version: Technical Report CS-84-13, 1984 http://www.cs.uwaterloo.ca/research/tr/
  • Back to top


    Hybrid Symbolic-Numeric Computation

    This work exploits the increased problem-solving power which can be realized by a hybrid approach combining traditional numerical computation with automated symbolic analysis.

  • K.O. Geddes, Numerical integration in a symbolic context. Proceedings of SYMSAC'86, B.W. Char (ed.), ACM Press, New York, 1986, pp. 185—191.

  • K.O. Geddes and G.J. Fee, Hybrid symbolic-numeric integration in Maple. Proceedings of ISSAC'92, P.S. Wang (ed.), ACM Press, New York, 1992, pp. 36—41.

  • Tom Robinson and K.O. Geddes, Automated generation of numerical evaluation routines. Maple Conference 2005, Ilias S. Kotsireas (ed.), Maplesoft, Waterloo, Ontario, Canada, 2005, pp. 383—398.
  • The latter paper is derived from Tom Robinson's Masters thesis.

    The following paper, joint with Masters student Wei Wei Zheng, considers numerical computations where a very high precision result is desired. We show that, rather than performing the complete computation in high precision, it can be significantly more efficient to exploit the speed of hardware precision and to use an iterative refinement scheme to build up the desired high precision result.

    In the following paper, we develop a new hybrid symbolic-numeric method for the fast and accurate evaluation of multiple integrals. The new method is shown to be effective both in high dimensions and with high accuracy.

    This work exploits the theory of tensor product series developed by Frederick Chapman in his 2003 Ph.D thesis, and the paper is derived from Orlando Carvajal's Masters thesis.

    Back to top


    Symbolic Computation of Integrals

    Work on this topic aims to advance the algorithmic knowledge incorporated into computer algebra systems for computing closed-form solutions of indefinite and definite integrals.

    In the above-referenced textbook, I present a detailed development of the Risch integration algorithm for computing indefinite integrals (anti-derivatives) for elementary functions.

    The following paper, joint with Masters student L.Y. Stefanus, studies a variation of the Risch algorithm known as Risch-Norman (or the parallel Risch algorithm).

    Below are three selected papers dealing with various aspects of the integration problem. Note that for the case of a definite integral when the corresponding indefinite integral is not known in closed form, the technique of "differentiation under the integral sign" leads to a solution for some classes of integrands.

    Back to top


    Symbolic Computation of Summations and Identities

    In joint work with Ph.D student Ha Le, Sergei Abramov of Moscow State University, and Jacques Carette of Maplesoft (now at McMaster University), we develop some new algorithms and a comprehensive library of Maple routines for computing closed-form solutions of summation problems.

    The following paper, joint with former Ph.D student Frederick Chapman, presents an algorithm for generating and proving various mathematical function identities.

    Back to top


    Symbolic Computation of GCDs and Limits

    The following two papers present the design of some algorithms for polynomial GCD computation based on probabilistic approaches. The significance of these algorithms is that their practical implementations achieve a significant speedup compared with traditional algorithms for polynomial GCD computation.

  • B.W. Char, K.O. Geddes and G.H. Gonnet, GCDHEU: Heuristic polynomial GCD algorithm based on integer GCD computation. J. Symbolic Computation, 7, 1989, pp. 31—48.

  • K.O. Geddes, G.H. Gonnet and T.J. Smedley, Heuristic methods for operations with algebraic numbers. Appears in Symbolic and Algebraic Computation, P. Gianni (ed.), Lecture Notes in Computer Science, No. 358, Springer-Verlag, Berlin, 1989, pp. 475—480.
  • Ph.D student Trevor Smedley wrote a thesis on the latter topic.

    The problem of computing limits of mathematical functions is the topic of the following paper, which presents a new algorithm based on hierarchical series. (For more recent results on this topic, see the work of Bruno Salvy and his co-authors.)

    Back to top


    Approximation of Functions

    The following two journal papers deal with approximation by rational functions, specifically Padé and Chebyshev-Padé approximants.

    In the following two journal papers, the topic is near-minimax polynomial approximation in regions of the complex plane.

    Back to top