DescriptionComplex band structures (CBSs) are useful to characterize the static and dynamical electronic properties of materials. Despite the intensive developments, it is computationally demanding to calculate CBSs for systems consisting of over several hundred atoms. We propose an efficient and scalable first-principles calculation method to obtain CBSs. The basic idea is to express the Kohn-Sham equation of the real-space grid scheme as a quadratic eigenvalue problem and compute only the solutions which are necessary to construct the CBS by Sakurai-Sugiura method. The serial performance of the proposed method shows a significant advantage in both runtime and memory usage compared to the conventional method. Furthermore, owing to the hierarchical parallelism in Sakurai-Sugiura method, we can achieve an excellent scalability in the CBS calculation of a boron and nitrogen doped carbon nanotube consisting of more than 10,000 atoms using 2,048 nodes of Oakforest-PACS.