Suppose I have a symmetric linear operator $A:\mathbb{R}^k \rightarrow \mathbb{R}^k$ where $k$ is small (eg., $k=100$), and I want to find it's first few eigenvectors, (eg., $10$ eigenvectors).If we had a matrix representation of $A$ this would be a standard problem in dense numerical linear algebra. However, the catch is that we don't have the entries of $A$, only a code that can evaluate the action of $A$ on a vector. Furthermore, evaluating $Av$ is moderately costly - it involves solving a PDE behind the scenes.What is the best way to find the first few eigenvectors of $A$ in this situation? My first thought was the Lanczos algorithm, but that's usually good for large sparse systems, whereas my system is small and dense.
Finding dominant eigenvectors of an operator that is small but costly to evaluate
eigensystem
Is the matrix also positive, such that eigenvalues are equal to singular values? You can estimate $k$ singular values of a general matrix (possibly nonsquare) with several digits of accuracy provided they are at least somewhat isolated in $8k$ matrix multiplies. The algorithm, as described in the excellent survey by Halko, Martinsson, and Tropp (2012) is:choose a random $n\times 2k$ matrix $X$compute $Y = (A^* A)^q A X$ where $q=1$ is typically sufficientorthogonalize $Y = QR$ with $Q$ orthogonalcompute $B = Q^* A$compute an SVD of the small matrix: $\tilde U \Sigma V^* = B$If you want the left singular vectors, let $U = Q \tilde U$The first $k$ singular values and singular vectors typically provide several digits of accuracy. This algorithm is often more accurate than Lanczos or Arnoldi iteration and has fewer synchronization points. The advantage is more significant for large problems and if applying the operator to several vectors at once is significantly cheaper than applying it to one at a time. This could be a good choice if you only want a couple values.