Statement of Research Goals [2001]
Andrew A. Anda, Ph.D.

    Plane rotations have proven to be more robust and accurate than the
currently more popular Householder and modified-Gram-Schmidt based one and
two sided orthogonal transformation algorithms. I would like to facilitate
the utilization of rotations by providing a viable alternative to the other
orthogonalization algorithms through enhanced ease of use and augmented
efficiency.

    I propose to develop the self-scaling fast plane rotation algorithms
I introduced in my Ph.D. dissertation and preceding publications towards the
establishment of a set of related subroutines.  The ACM TOMS journal would
be an appropriate target for publication.  A primary target towards this
end will be development of a test suite to insure correctness and
portability.  The subroutines should parallel as closely as possible the
calling sequences, documentation standards and style of established
standard related subroutines, e.g., those in the BLAS.  The integration of
the new subroutines into the BLAS based LAPACK and its derived variants
such as the PBLAS and SCALAPACK would be a further extension of this
software engineering effort.  Related research topics would be the
extension of the rotation technology into the complex range and domain
(functions omitted from the BLAS), coping with and without IEEE754 floating
point standard conformant architectures, using the same subroutines for both
circular and hyperbolic plane rotations, and efficiency issues on superscalar,
vector, and parallel architectures.   The extension of these algorithms into
the area of sparse matrix computations is also possible.  Noteworthy
efficiency goals include the reduction of bandwidth and of floating point
pipeline bubbles (often due to such relatively high latency operations as
division on some architectures), and the enhancement of data locality and
of resource reuse.

    I propose to develop algorithms for the fast performance of Boolean
matrix-real vector products. These products arise in numerous contexts.
In many of these contexts, the Boolean matrix is invariant or changed only
slightly for a sequence of products. In this case, reordering should prove
beneficial. These Boolean matrix-real vector products can be exploited in
performing both dense and sparse matrix-vector products where the matrix is
over a relatively small set [O(n)] of integer or real values.  In this case
the more general matrix-vector product can be decomposed into a linear
combination of Boolean matrix-real vector products. Because the optimal
ordering problem is essentially a TSP problem, finding efficient nearly
optimal approximations will be challenging.

    Another topic I propose is to generalize the dynamic programming solution
of the matrix-chain ordering problem to admit and exploit specific matrix
and algorithm attributes. E.g., if a matrix is Toeplitz, or triangular,
more efficient algorithms can be exploited, thereby potentially influencing
the optimal associativity graph.

[end of Statement of Research Goals]