New Parallel Divide-and-Conquer Algorithm for Computing Full Spectrum of Polyacetylene

The Su-Schrieffer-Heeger (SSH) model is a simple tight-binding model that includes nearest neighbors and is frequently used to study the fundamental properties of trans-polyacetylene (trans-PA), as well as many other materials. In these studies, the essential and most time consuming step is the computation of the eigen-decomposition of the Hamiltonian matrix. In this poster, we present a new scalable parallel algorithm that efficiently computes the full spectrum of Hamiltonian matrices to a prescribed accuracy. Given an accuracy tolerance $\tau$ and Hamiltonian matrix $A$, which is a real symmetric dense matrix, our parallel algorithm fully exploits the structure of the Hamiltonian matrix and computes eigen-solutions in two steps: (a) Construct a block-tridiagonal matrix that approximates the original dense matrix; (b) Use the highly efficient block-tridiagonal divide-and- conquer algorithm to compute approximate eigen-solutions. The computed approximate eigen-solutions satisfy the following conditions: 1) $ ||A-V\Lambda V^T|| \le O(\tau||A||) $; and 2) $ ||(VV^T - I)|| \le O(n\epsilon_{mach}) $, where $\epsilon_{mach}$ is the machine precision. Performance tests show that this algorithm is extremely efficient for the computation of electronic spectrum of trans-PA compared to traditional dense eigensolvers. In many tests, the savings is several orders of magnitude!