Linear-scaling methods have paved the way for large-scale ab initio calculations of solid-state systems. Existing methods suffer from two well-known limitations. First, they are only applicable to sparse systems, i.e., when long-range orbital interactions exponentially decay and therefore the Hamiltonian matrices have a small number of non-zero elements. Second, their computational performance is negatively impacted when high accuracy is needed. In this work, by revisiting linear scaling kernels, we introduce a new approach with nearly-linear complexity, provable convergence properties, and global applicability even for dense systems. We demonstrate their advantages and limitations both in theory and in practice.