REDUCING THE SYMMETRICAL MATRIX EIGENVALUE PROBLEM TO MATRIX MULTIPLICATIONS

A numerical method for the symmetric matrix eigenvalue problem is developed by reducing it to a number of matrix-matrix multiplications. For matrices of size n, the number of such multiplications is on the order of log2 n. On high performance parallel computers, it is important to minimize memory reference, since the movement of data between memory and registers can be a dominant factor for the overall performance. The matrix-matrix multiplication is more efficient than matrix-vector or vector-vector operations, since it involves O(n3) floating point operations while creating only O(n2) data movements. The number of data movements of the traditional methods based on reduction to the tridiagonal form is O(n3), while that of our method is O(n2 log2 n). Asymptotically, there are fast numerical algorithms for matrix multiplications that require less than O(n3) floating point operations. One example is the O(n2.376) method of Coppersmith and Winograd [Proc. 19th Ann. ACM Symp. Theory Comput., 1987, pp. 1-6]. Therefore, in principle, our method for the symmetric matrix eigenvalue problem requires only O(n2.376 log2 n) operations.