Does the Lanczos algorithm remain memory efficient even if the original Hermitian matrix is dense?
The memory, used in the Lanczos algorithm, stores the Krylov subspace. The structure of the matrix does not impact this amount of memory. The size of the Krylov subspace is however impacted by the number of the eigenvalues of interest and their distribution (i.e. how separated they are) .
3$\begingroup$ I think some more discussion is necessary. In some cases you do not want to save the entire Krylov subspace; for instance if you just want to compute eigenvalues but not eigenvectors you can discard it. $\endgroup$ Feb 6 at 12:17
$\begingroup$ @FedericoPoloni - Feel free to elaborate. The original question was about the impact of the matrix being dense. Not storing the entire Krylov subspace does not depend on whether the hermitian matrix is dense or sparse. $\endgroup$– user7440Feb 7 at 14:23
$\begingroup$ I suppose, the point is, to build the Krylov space we need the Hamiltonian. Then the issue would be to the storage of the Hamiltonian dense matrix in memory. If some algorithm is available for specific Hamiltonians where the elements can be generated on the fly (or at least for rows/columns of the Hamiltonian can be generated for matrix multiplications needed for generating the Krylov space vectors) then Lanczos will work in memory efficient way. Any comment will be appreciated. $\endgroup$ Feb 22 at 5:19