1
$\begingroup$

I have experience with LAPACK (direct solvers) and ARPACK (sparse iterative solvers), but are there any sparse direct solvers? I am concerned more with preserving space than with fast solutions. ARPACK is fast when it converges, but seems to struggle when many eigenvalues are degenerate.

$\endgroup$
5
  • $\begingroup$ I suggest you provide the details of how you are using arpack. Among other things, it is not clear to me what you mean by direct and iterative "solvers". $\endgroup$ Dec 2, 2023 at 10:47
  • 1
    $\begingroup$ There is a very fine line between direct and iterative in the end. Lapack's eigenvalue algorithms based on QR/Francis iteration are iterative, but so fast and effortless that they 'feel' direct. And even "direct" algorithms to solve linear systems like DGESVX include an iterative refinement step. $\endgroup$ Dec 2, 2023 at 15:37
  • 1
    $\begingroup$ ARPACK is implementing $iterative$ solvers. It does not require or assume any sparsity. IMHO, a better distinction is whether you need a subset of approximations to the eigenpairs (i.e. < n, the matrix dimension) or a complete set of approximations (i.e. = n, the matrix dimension). - How many modes do you need? - If you know the maximum size of degeneracy, then a block implementation of Arnoldi (or Lanczos) could handle the degeneracy. $\endgroup$
    – user7440
    Dec 4, 2023 at 3:15
  • $\begingroup$ @user7440 The number of modes is significantly less than n. Your comment on a block implementation is interesting. Could you expand on that? $\endgroup$
    – DJames
    Dec 5, 2023 at 0:58
  • 1
    $\begingroup$ @DJames A reference discussing these aspects is doi.org/10.1137/S0895479888151111 Section 4.5 discusses the block size: "[...] it is best to choose a blocksize as large as the largest expected multiplicity if eigenvalues of moderate multiplicities are expected. This is particularly important if many clusters of eigenvalues are expected (Table 12). A blocksize of 6 or 7 works well in problems with rigid body modes. We rarely find that p > 10 is cost-effective." $\endgroup$
    – user7440
    Dec 6, 2023 at 4:06

1 Answer 1

8
$\begingroup$

There cannot be. The problem of finding eigenvalues is nonlinear, and it can be shown that finding eigenvalues of a matrix is a problem that is equivalent to finding roots of polynomials. We know that the latter only has solutions that can be computed in a finite number of steps for polynomial degree $\le 4$ in general. If there was a direct solver for the eigenproblem, it would also provide a way to find the roots of arbitrary-order polynomials.

In other words, any algorithm to find the eigenvalues of a matrix beyond size 4 must necessarily be iterative.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.