1
$\begingroup$

When using the eigs function in MATLAB, which is based off of ARPACK, one can manually modify the maximal dimension of the constructed Krylov subspaces, the maximum iteration counts, and the error tolerance. The defaults are min$(2k, 20)$ (where $k$ is the number of requested eigenvalues), $300$, and $10^{-12}$. Depending on the problem at hand, the first two parameters may need to be adjusted to hit the prescribed error tolerance (at least within an acceptable amount of time). Is there existing theory to aid in the choices of the subspace dimensions and the iteration counts in order to hit the error tolerance in a reasonable amount of time? For large problems (with sparse matrices which may have poor conditioning), I have found that this can be pretty difficult to deduce. The runtime/convergence appears highly sensitive to the values of these parameters. Ideally, I wouldn’t need to modify my parameter choices every time that I want to run a problem.

For example, if I am working with a $4000\times4000$ matrix and only want the eigenvalue with largest imaginary part, then the subspace dimension will be capped at $20$ by default, which is rather small relative to the matrix dimensions. Generally, I may want the first $k$, where $2k$ is small relative to the matrix dimensions. I have found that one needs the subspace dimension and iteration count to be sufficiently high to hit the tolerance, but if it is too high, then the runtime is very large. I have been setting the maximal subspace dimension around $3/4$ of the number of rows in the matrix and the iteration count to $1000$, but that isn’t chosen rigorously. Perturbing these numbers (e.g. down to $1/2$ the number of rows or or up to $7/8$) leads to extreme runtimes/convergence problems. Is there a more rigorous way to choose this, especially if one takes into account matrix sparsity (/number of non-zero entries) or conditioning?

For added context, I am interested in problems as outlined in this previous question.

$\endgroup$
4
  • 1
    $\begingroup$ Since you just want the largest eigenvalue wouldn't a power iteration be enough? $\endgroup$
    – lightxbulb
    Jul 10, 2023 at 23:43
  • 5
    $\begingroup$ @lightxbulb Not always: it depends on the gap between the first and second largest eigenvalue; the power iteration can be very slow to converge. $\endgroup$ Jul 11, 2023 at 7:21
  • $\begingroup$ @lightxbulb - To accelerate with the power iteration, one can use a block version, i.e. start with $X_0$ a rectangular matrix of dimension $4000 \times k$ where $k > 1$ and apply the power iteration algorithm with $X$ of dimension $4000 \times k$. In that case, the convergence rate becomes $| \lambda_{n - k} / \lambda_{n} | $ where $|\lambda_{n}|$ is the largest modulus among all the eigenvalues. $\endgroup$
    – user7440
    Oct 23, 2023 at 1:58
  • $\begingroup$ @user45844 - One remark about ARPACK -- the algorithm checks for convergence only when the whole Krylov subspace is filled. So for your problem of dimension $4000 \times 4000$, a Krylov subspace of dimension $2000$ is big and no convergence check will be made until 2000 Lanczos (or Arnoldi) vectors are generated. The approximation to the largest eigenvalue may have "converged" a long time ago before 2000 basis vectors are created. For your problems, I would suggest to increase the dimension 20 more slowly and until the number of iterations becomes 1. $\endgroup$
    – user7440
    Oct 23, 2023 at 2:07

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.