Stephen M. Watt: Research Summary

My research is focused on computer algebra, the study of algorithms and software to allow computers to do mathematics, producing equations and expressions rather than just numbers. My goal has been to identify and solve the principal scientific questions necessary to allow symbolic mathematical computation to be as effective and pervasive as numerical and text-based computation. This has involved developing new areas of investigation and bringing them into the core of what we now view as computer algebra today.

My work has centered on the following key questions:

  1. What new programming language and compiler technology is needed to allow more efficient, general and expressive mathematical libraries?
  2. How do we meaningfully handle approximate numerical quantities in the context of symbolic mathematical computation?
  3. How should computer algebra systems interact with each other and the World Wide Web?, and most recently
  4. How can the problem of mathematical handwriting recognition be decomposed into tractable components?
Together these questions provide the elements of a natural, powerful environment for symbolic mathematical computation.

The highlights of this work are summarized below. A technical overview of some aspects is provided by chapters in the Computer Algebra Handbook (Springer Verlag 2003): Aldor, Hybrid Methods, and MathML.

Computer Algebra Systems

I have been one of the principal creators of two major computer algebra systems: Maple and Axiom. Both of these systems were highly novel when introduced.

In 1981, I was one of the original authors of Maple, together with Keith Geddes and Gaston Gonnet. Because the prevailing standard for interactive computer algebra system architecture was too resource intensive, Maple was conceived on a then-novel kernel/library structure. Maple has continued to set new directions in computer algebra system design, and is today one of the most used packages for mathematical software with some three million users world-wide.

Later in the 1980s, in collaboration with Jenks, Sutor and Trager at IBM Research, I was one of the principal authors of the Axiom computer algebra system. This system followed an approach fundamentally different than that of other systems, such as Maple and Mathematica, in that its libraries used the mathematical structures from modern abstract algebra to define interfaces and specifications. This was a highly innovative approach to system design, using parametric polymorphism and type categories well before they were used in mainstream applications, and stimulated similar projects at Berkeley and Tektronix. For this work, I received the Outstanding Innovation Award from IBM Research in 1992. My recent work in this area examines the fundamental questions in memory management and object semantics to allow multiple computer algebra systems to be tightly integrated. This was the subject of my invited address at the 2002 International Congress of Mathematical Software. Most recently, the collaboration between Maplesoft and the Ontario Research Centre for Computer Algebra was recognized by the NSERC 2004 Synergy Award.

Mathematical Data Communications and Knowledge Management

I have been one of the creators of two related standards for the exchange of mathematical data in distributed or web-based applications: OpenMath and MathML.

OpenMath is a standard supported by the European Union for the semantic markup of mathematical expressions in a naturally extensible fashion. OpenMath has been used as the basis of OmDoc and as an extension mechanism for MathML. MathML is a World Wide Web Consortium standard for the markup of mathematical expressions. Unlike earlier attempts at representing math such as TeX or images, MathML embodies expression tree structure so that applications can make meaningful transformations on mathematical content. My most significant contribution in this effort was to unify two opposing viewpoints by moving to an XML base with support for both notation and semantic markup. This was before XML was completed, and MathML thus became the first XML application. Since its first definition in 1999, MathML has been widely adopted by software vendors (Maple, Mathematica, NAG, IBM), has been supported by web browsers (Netscape, Internet Explorer with MathPlayer, Firefox, Mozilla, Amaya), and is now the representation of mathematics in all new United States patent documents. For this work, I received the IWAY Award for New Technology Development in 2002.

Most recently, I have directed my research group in developing techniques to use the OpenMath and MathML technologies to provide mathematical web services, accessible both to individuals and client programs. The ideas in mathematical service description and discovery might play an important role in the future for self-organizing behaviour in large mathematical software systems.

Symbolic-Numeric Algorithms for Polynomials

The algorithms of symbolic computation which assume exact, non-approximate, data break down when applied to polynomials with approximate floating point coefficients. This makes much of computer algebra inapplicable in practical applications where the mathematical objects arise from measured data. To work with these approximate algebraic objects, new ideas are needed.

I have been one of the founding contributors developing this new area. My 1995 paper with Corless, Gianni and Trager imported the ideas of backward error analysis to computer algebra to give a well defined meaning to the approximate greatest common divisor of polynomials and solution of polynomial systems. It applied the singular value decomposition and other techniques from numerical linear algebra to resultant-based methods known in computer algebra. This work had a major impact in the computer algebra community, and the following year saw an explosion of papers by many authors in the area of algorithms for approximate polynomials. Together with members of my lab at INRIA, I organized the SNAP '96 conference to explore the developing field, resulting in a special issue of the Journal of Symbolic Computation.

Numerous symposia have been held in this area since, and it is now normal for conferences in computer algebra to have special sessions on symbolic-numeric algorithms for polynomials. I continue to be an active contributor, with recent results in the most important basic polynomial operations, including absolute irreducibility testing (1997), functional decomposition (1999), implicitization (2000), factorization (2001, 2002), greatest common divisors (2004), and initial value problems (2005).

Automatic Differentiation

Automatic differentiation is the study of techniques to augment computer programs so they compute not only their original numerical values, but also the function's analytic derivatives. This is lies in the area between computer algebra and compilers. My work, together with colleagues at IBM, led to monthly savings of $1 Million in circuit simulation, an IBM Research Division Award in 1994, and two US Patents in 2001 and 2002.

Programming Languages and Compilers

Mathematical problems have a richer, more well-defined structure than other computational problems so it is not surprising that a number of programming language issues are first seen in the area of symbolic mathematical computation. Starting in 1990, I led an effort to create Aldor, a new programming language ideally adapted to the creation of natural and efficient programs for symbolic and numeric mathematical computation.

The formulation of the Aldor language balances the mathematical desire for generality and uniformity, on one hand, with the practical requirements of demanding symbolic and numeric computation, on the other. New techniques for higher-order type systems and optimization have led to a theoretically elegant language with an effective optimizing compiler. Aldor is in use in a number of research projects world-wide, including work at IBM, Seagate and J Lab (US); U. Edinburgh, U. Canterbury, U. Cambridge, and the Numerical Algorithms Group (UK); INRIA (FR); and RISC-Linz (AT).

For this work, I received the Ontario Premier's Research Excellence Award in 1999. I have also been awarded a NSERC Strategic Project grant in 2002 for my on-going work in this area.

Pen-Based Mathematical Computing

Most recently, I have begun investigating the problem of how to effectively structure an environment for pen-based mathematical computing. Current pen-based computing devices use sophisticated methods to achieve reasonable handwriting recognition rates. These methods are inapplicable, however, to mathematics, primarily for three reasons: (1) mathematical notation is two dimensional, with elements of both handwriting and drawing, (2) mathematical notation uses a vocabulary of thousands of symbols, with no well-defined stroke order, unlike e.g. English or Chinese, (3) there is not a fixed set of mathematical ``words'' that would allow the usual use of dictionary-based methods.

The many earlier attempts at dealing with pen-based mathematics have failed to define sufficiently delineated sub-problems and recognize their complexity. I currently lead a research group, significantly supported by Microsoft and Maplesoft, investigating these questions. This has led to my participation in the creation of InkML, the upcoming W3C draft standard for digital ink.