Year 2

1. Extend our work on geometric objects to arbitrary dimension. (There are immediate scientific applications for three-dimensional representations, but we would prefer to solve the general problem during Year 2.) High dimensional geometric objects require careful thinking about representation formats, because converting from one format to another often requires resources superexponential in the dimension.

2. Generation of parallel code for sparse matrix applications. We will generate parallel implementations of sparse iterative solvers (such as conjugate gradient method), starting from dense, sequential solvers. This will use restructuring compiler technology we have developed at Cornell, as well as program transformation technology which will be developed under the aegis of this grant.

3. Extend the MathBus specifications to deal with directed and undirected graphs. The basis for much of sparse matrix computation is graph theory. For instance, a preprocessing step of many sparse matrix algorithms is called ``symbolic factorization'' and involves some elegant graph algorithms [42]. A key to high performance sparse matrix algorithms is identifying certain cliques in the elimination order [72]. We will define a specification for directed and undirected graphs in the mathematical bus.

4. Extend the scope of the mathematical bus to include other software packages such as LAPACK, visualization tools, Matlab, and Maple.