Distributed Jacobi Joint Diagonalization on Clusters of Personal Computers

摘要

A new algorithm is described for distributed joint diagonalization of real symmetric or complex Hermitian matrices. The approach, which is based on the Jacobi diagonalization, utilizes distribution of the computational power and memory space, minimizes the communication costs, and runs on clusters of personal computers. It further combines two-step load balancing algorithm with a standard Kalman filter to enable quick but low-cost adaptation to resource varying conditions. Theoretical analysis of its performance shows that the communication costs (when normalized by computational costs) decline linearly with the number and size of the diagonalized matrices. This is also confirmed by experimental results: the measured speedup ratio yields 42.2 when jointly diagonalizing 800 matrices of size 400x400 on a cluster of 50 personal computers.