Western University Computer ScienceWestern Science

    Computer Algebra

    Computer algebra solves mathematical problems by means of computer programs. Those programs answer the user's questions with formulas rather than numbers. This is generally preferred in quantitative domains, such as engineering, finance and physics, where it is desired to understand the nature of things, rather than simply compute values. Computer algebra techniques have been applied to problems as straightforward as high school math homework, as practical as optimizing automobile suspension assemblies, and as fundamental as modeling the large-scale structure of the universe. At the heart of computer algebra is the invention of mathematical algorithms and software systems that manipulate symbolic mathematical expressions.

    Our research group, which involves computer scientists and applied mathematicians, conducts research in several areas of computer algebra. Those areas which are primarily led by our Faculty members in the Computer Science Department (Marc Moreno Maza, Eric Schost and Stephen M. Watt) are listed below in alphabetic order. More details on each of these seven research directions are given at the end of this document.

    Many of the algorithms we develop are incorporated in Maple, the leading mathematical software package, and open source software such as Aldor.

    Our group has been recognized by several prestigious awards including an endowed chair from Canada Research Chairs, MITACS Awards for Excellence in Mentoring and Best Use of Mathematics in Technology Transfer, a CANARIE IWAY award for new technology development, an Ontario Premier's Research Excellence Award and multiple best-paper/poster awards. Our research has been supported by grants from federal and provincial agencies and networks such as CFI, MITACS, NSERC and ORDCF, and, industrial partners such as Maplesoft, Microsoft, and Sharcnet.

    We give an idea below of what some of the research topics involve. All members of our group are involved to some extent in each of the topics, but we list for each area those who are most heavily involved.

    Research Webpage


    Algorithms for computing with matrices and polynomials

    At the practical and theoretical heart of computing with mathematical expressions is the treatment of matrices and polynomials. These provide a magnificent array of deep and useful properties that admit a host of surprising and highly-effective algorithms. Matrices and polynomials are therefore used to represent many of the more general mathematical objects in computer algebra systems. From the perspective of a pure mathematician, matrices and polynomials are well-known objects. However, from their implementation on computers non-standard research topics have emerged (fast arithmetic over non-integral domains, polynomials with symbolic exponents) which are the core of the most efficient computer algebra software.

    Faculty: Marc Moreno Maza

    Efficient algorithms and their implementation

    Asymptotically fast methods for symbolic computations have been known for more than forty years. Unfortunately their impact on computer algebra systems has been reduced since it was believed that they were irrelevant in practice. Recent progress have shown that careful programing and accurate experimentation can lead to a successful implementation of these methods permitting to overcome the size of magnitude of effective computations. Our research group has produced both new complexity results for symbolic computations (ranging from fundamental operations to the solving of polynomial systems) and efficient software, such as the modpn library, which is shipped with Maple.

    Faculty: Marc Moreno Maza

    Parallel computing, hierarchical memories

    Parallel hardware architectures (multiprocessors, multicores, graphics processing units, etc.) and computer memory hierarchies (from processor registers to hard disks via successive cache memories) enforce a radical evolution of mathematical software tools. Indeed, most of these software tools, in particular today's computer algebra systems, are not able to exploit modern hardware acceleration technologies, although many of the algorithms implemented in these tools have a large potential to take advantage of these hardware resources.

    Combining different complexity measures (cache complexity, parallelism, etc.) that are of interest for the targeted hardware, our research group aims at delivering appropriate algorithmic solutions to the fundamental operations on which computer algebra relies (polynomial and matrix arithmetic, algebraic expression manipulation, etc.).

    Faculty: Marc Moreno Maza