Parallel Absorbing Diagonal Algorithm: A Scalable Iterative Parallel Fast Eigen-Solver for Symmetric Matrices

In this paper, a scalable parallel eigen-solver called parallel absorbing diagonal algorithm (parallel ADA) is proposed. This algorithm is of significantly improved parallel complexity when compared to traditional parallel symmetric eigen-solver algorithms. The scalability-bottleneck of the traditional eigen-solvers is the tri-diagonalization of a matrix via Householder/Givens transforms. The basic idea of ADA is to avoid the tri-diagonalization completely by iteratively and alternatingly applying two kind of operations in multi-scales: diagonal attaction operations and diagonal absorption operations. In a diagonal attraction operation, it attracts the off-diagonal entries to make the entries near to the diagonal larger in magnitude than the entries far away from the diagonal. In a diagonal absoprtion operation, it absorbs the nearer nonzero entries into the diagonal. Theories of ADA has been established in another paper of ours that for any \(\epsilon >0\), there exists a constant \(C=C\left( \epsilon \right) \), such that within C rounds of iterations, the relative error of the algorithm will be reduced to below \(\epsilon \). Parallel complexity of ADA is analyzed in this paper to reveal its qualitative improvement of scalability.