*
Please note that this listing is currently one or two years out
of date. I plan to update it real soon now. :-)
*

- Models of Parallel Computation
- Parallel Applications
- Computational Group Theory
- Computer Algebra
- Scientific Computing

I began my career by working on individual scientific applications, and at heart, I still feel that I am solving individual applications. However, at some point, I stopped my work in order to search for a bigger lever. Computer algebra was the first lever that I came to, and my first hope in was for a set of rewrite rules that would take a set of equations representing the scientific problem, and rewrite them into a solution, whether it was an entirely symbolic solution or perhaps a rewriting into a FORTRAN or C program that could be executed on a computer. This view has been popularized since then by Mathematica.

As I looked more closely at the issue of rewrite rules and equivalent expressions, I drew the same lesson as other researchers at that time: that rewrite rules worked well for certain applications, but a relatively small number of rewrite rules can lead to a combinatorial explosion of invocations of such rules. This led to my search for a second lever. I was led to issues of groups of transformations, groups of symmetries, and presentations (defining equations for a group). Since Larry Finkelstein at Northeastern University was kind enough to give me an introduction to the field of computational group theory, which was still at a relatively early stage when I entered it, and I found much to do in building up the appropriate computational tools. These tools were sharpened and tried on some large applications. There were some early successes. For example, a one Megabyte data structure was pre-computed by which any state in Rubik's 2 x 2 x 2 cube (Rubik's cube with corners only) can be solved, and the shortest sequence of moves can be written out in a few milliseconds. (I found that Rubik's cube can always be solved in at most 11 moves.) My work has also had an impact on wider issues of computational algebra, such as fast Gaussian elimination for low rank matrices and fast computation of the GCD of many integers.

However, even with those sharper tools, there were still some problems that were just a little out of reach. This led me to search for my third lever: field of parallel computing. In my view, the single biggest problem of parallel computing today is the lack of a good high level programming model. Our situation today is roughly analogous to the situation in the 50's, when we had many assembly languages and were still searching for the right high level language (COBOL, FORTRAN, CPL/BCPL, IPL, LISP 1.5, etc.). One wants a simple and expressive programmer's model that doesn't lose too much efficiency in translation to lower level primitives. CILK (at M.I.T.), with its concept of work-stealing, is such an example for SMP (shared memory).

In the area of distributed memory, I have incrementally develop the TOP-C (Task-Oriented Parallel C) model. My goal was to present the applications programmer with an abstraction that hides the message passing issues, while not impacting the overall efficiency too greatly. I present such a model with three abstractions: (1) the task, (2) the environment, and (3) the action. You can read more here.

There is still work to do in improving all of these levers. For
example, I view my in-depth knowledge of computational group theory as
a necessary testbed for parallelism, without which, I would not have
enough perspective to develop a truly simple and expressive model of
parallelism. However, the recent set of very large parallel
computations gives me hope that I am making progress in bringing these
levers back to some of the original applications. After all, what is
the use of a journey, if one can't return home to tell one's friends
what one has found?