Wayne Eberly’s Research

I hope that this page, and the ones to which it links, will be of interest to someone wishing to learn about the areas in which I do research. A list of my publications is also available, in case you are interested in this, and wish to skip all the surrounding text.

Research Areas

Most of my research concerns the design and analysis of algorithms for problems in computer algebra; all the rest falls into the somewhat broader area of algorithm design and analysis.

Computer algebra is, generally, concerned with problems that arise in mathematics, the physical sciences, and in engineering. These frequently involve the formation and solution of mathematical equations.

This subject area is closely related to a somewhat older one: Numerical computation is a well-established area concerned with the computation of approximate solutions for these equations. In contrast, computer algebra is a more recent area of computer science that is generally concerned with the computation of exact solutions, instead.

My research has included projects in the following areas.

  1. Black Box Linear Algebra and Matrix Normal Forms

    "Black box linear algebra" is a study of algorithms for matrix computations in which the input matrix is not assumed to be explicitly given, but instead may only be used to perform matrix-vector multiplications. Such algorithms may be attractive for sparse or structured matrix computations.

    A few new results concerning the computation of matrix normal forms assuming the more traditional model (that is, assuming as usual that the entries of the input matrix are given) have been discovered during this study of black box computation. A discussion of this work and a list of publications is also included.

  2. Decomposition of Matrix Algebras

    Representation Theory is an area of abstract algebra in which one studies concrete realizations of groups, rings, and similar structures. My research has included a study of computational aspects of problems in this area.

  3. Parallel Algorithms

    This is a study of algorithms that solve problems (much) more quickly using multiple processors than is possible when only a single processor is available. Over the years, I have studied parallel algorithms for various polynomial and matrix computations.

    I am not working in this area at the moment. Indeed, research in parallel algorithms (rather than parallel architectures) seems to be a considerably less active research area than it was a few years ago.

  4. Other Research

    From time to time, I have also studied a few problems that are not related to the above projects.


Here are a few references that include some of the background material needed to read about the above research.

  1. B. Buchberger, G. E. Collins, and R. Loos (Eds), in association with R. Albrecht
    Computer Algebra: Symbolic and Algebraic Computation
    Springer-Verlag, 1982

    This is a collection of survey articles covering a variety of areas in computer algebra. It is now a little dated - for example, quite a bit has happened concerning factorization of polynomials since the early nineteen-eighties - but this still contains quite a bit of useful material, including an extensive discussion of arithemtic computatons in various algebraic domains (the underpinnings of just about everything else).

  2. A. M. Cohen, H. Cuypers, and H. Sterk (Eds.)
    Some Tapas of Computer Algebra
    Springer, 1999

    These are notes based on two minicourses on computer algebra given at the Eindhoven University of Technology by various invited lectures. They serve as readable (and reasonably up-to-date) introductions to research in several areas in computer algebra.

  3. T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein
    Introduction to Algorithms
    Second Edition, Mc-Graw Hill, 2001

    There are certainly lots of very readable introductions to design and analysis of algorithms that are now available. This one covers all the basics, and also includes a few advanced topics that are relevant to my research: Note, in particular, the chapters on "Matrix Operations" and "Polynomials and the FFT." The second edition of this chapter also includes a short introduction to average-analysis of algorithms and the analysis of randomized algorithms - which is frequently useful in computer algebra.

  4. J. von zur Gathen and J. Gerhard
    Modern Computer Algebra
    Cambridge University Press, 1999

    This beautifully written text on computer algebra includes far more than one would need in order to understand my research. The material in sections I (Euclid) and II (Newton) are most relevant; chapter 12 includes a short introduction to Black Box Linear Algebra.

University of Calgary Extension of Logo
Department of Computer Science

wayne eberly research cpsc 518 cpsc 667 other resources links

Research Black Box Linear Algebra Matrix Algebras Parallel Algorithms Other Research Publications