3
$\begingroup$

I have a saddle point of a function defined on a $64 \times 64 \times 64$ grid, i.e. a function of $64^3$ variables. I would like to compute the lowest-lying eigenvalues of the Hessian to see how they depend on the parameters of the function.

The function is analytically twice differentiable, but computation of the complete Hessian is impossible due to memory constraints (the full matrix would be around 8TB). The Hessian is sparse, but it is not a simple sparsity pattern such as a tridiagonal matrix. I also know that the Hessian has several zero eigenvalues.

Is it possible to calculate the $n$ smallest eigenvalues without computing the full Hessian? Either an analytical method or a numerical approximation would be fine.

$\endgroup$
6
  • $\begingroup$ Sylvester's law of inertia (en.wikipedia.org/wiki/Sylvester%27s_law_of_inertia) allows to analyse the Hessian (positive definite, $\ldots$) without calculating the eigenvalues. It's a matter of completing the square, or else of computing a sequence of determinants. $\endgroup$ Dec 16 '20 at 9:57
  • $\begingroup$ Thanks Christian Blatter, but despite my misleading wording in the question, I am specifically interested in the values of the eigenvalues. I've edited the question to make this clear. $\endgroup$
    – DavidH
    Dec 16 '20 at 10:07
  • $\begingroup$ The Lanczos method is a great way to get the extreme eigenvalues of a matrix without going through the full $O(N^3)$ process of diagonalization. But you have to actually know the matrix. Since you can’t even store it in memory, this is probably not helpful. $\endgroup$
    – sasquires
    Dec 16 '20 at 10:13
  • $\begingroup$ maybe you can compute a partial principal submatrix of the the Hessian and use it as an approximation/bound of the Hessian eigenvalues Eigenvalues of a principal sub-matrix of a symmetric matrix $\endgroup$
    – iarbel84
    Dec 16 '20 at 11:26
  • $\begingroup$ You should move this to scicomp.stackexchange.com . Or post threre, with links on both posts to the other. $\endgroup$ Dec 19 '20 at 14:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.