Our research in high performance matrix computations continues through collaboration with two Ph.D students. With ACRI-supported Greg Henry we have have developed new ways to improve data reuse issue for a range of algorithms that are associated with the Hessenberg canonical form and the unsymmetric eigenvalue problem. WithNikos Pitsianis our search for new "high-performance" applications of the Kronecker product is branching out in several interesting directions.
The unsymmetric eigenvalue problem is a major challenge when it comes to extracting high performance. To begin with, any eigenvalue problem that requires row and column transformations of the matrix poses difficulties because no one has shown how to reorganize effectively the calculations so that matrix-matrix multiplicaion dominates. Our ultimate goal in this direction is to obtain a block eigensolver that performs at the same level as block QR, block LU, or block Cholesky. Matrix-multiply rich methods have been found for these factorizations that require one-sided acess to the matrix.
Nevertheless, we have shown how to introduce significantly better memory traffic patterns in various eigenvalue calculations by being careful with level-2 operations. For example, the QR iteration with shift has been implemented in a way that reduces execution time between 20 and 50 percent in both the RS 6000 and ES 900 environments. The idea is to ascertain the shifts without updating the matrix fully every step.
Another aspect of our research is concerned with finding new applications for the Kronecker product. Our current focus is on the use of Kronecker product preconditioners. For the discrete Laplacian, the the Kronecker product preconditioner is comparable in iterations to the incomplete Cholesky preconditioner, whch is the preferred choice in many applications. However, the Kronecker product has the advantage of being highly parallelizable and we have demonstrated its advantage on the CM-5.
Finally, we have begun to develop a "template library" to go along with my recently published book Computational Frameworks for the Fast Fourier Transform. The template idea has been implemented by Dongarra and others in the area of iterative methods. he idea is not to produce a library of optimized codes but a sufficiently detailed script (say in high performance Fortran) that can be easily adapted to various environments. The goal is to simplify the production of optimized FFTs that have been parameerized through the Kronecker product methodology.