I have a numerical problem in which I need to find the values $\lambda$ for which the determinant of a matrix $A_\lambda$ is zero. (The solutions $\lambda$ will give the eigenvalues of an operator...)

For that I learnt that it is better to look for the singularities of the function $\lambda \mapsto \log(|det(A_\lambda)|)$. An example of the plot of this kind of function on $[0,10]$ is given in the following figure:

enter image description here

I have two questions:

1) What algorithm is best for finding such a singularity if it is unique in a certain interval $[a,b]$?

2) How should I approach the problem of finding all singularities in an interval $[a,b]$?

[I'm not sure how to choose the right tags for this question, so please feel free to add the right ones.]

Perhaps an answer for 1) could be the golden ratio search: http://en.wikipedia.org/wiki/Golden_section_search , for the case when there is a single minimum in the interval.

Still, I have no idea how to generalize this to the case where there are multiple intervals to be chosen.

  • $\begingroup$ What form does $A_{\lambda}$ have? Chances are that we can suggest a much better way of approaching this problem, but you haven't provided sufficient information about how the problem arose. $\endgroup$ – Brian Borchers Feb 8 '13 at 5:05
  • $\begingroup$ @BrianBorchers The form of $A$ is $\phi_{\omega}(\|x_i-y_j\|)$ where $\phi_\omega$ is a bessel function, so $A_\lambda$ it is not sparse. $\endgroup$ – Beni Bogosel Feb 8 '13 at 6:58

This is an exceptionally bad algorithm to find eigenvalues, at the very least if you're just looking for the eigenvalues of a linear operator or matrix. There are many better algorithms to do what you are trying to do.

While it is true that the mathematical definition of an eigenvalue is that $A_\lambda$ is singular, i.e. that $\det A_\lambda=0$ in the finite dimensional case, this is not a practical definition to find eigenvalues in actual applications.

| cite | improve this answer | |
  • $\begingroup$ Do you have any suggestions of better algorithms? $\endgroup$ – Victor Liu Feb 8 '13 at 1:35
  • $\begingroup$ Are you simply trying to find the eigenvalues of a matrix? $\endgroup$ – Wolfgang Bangerth Feb 8 '13 at 3:05
  • $\begingroup$ I'm not looking for the eigenvalues of a matrix, but of the Laplace operator on a set. You may say that it is a bad algorithm, but there are articles on the subject which say otherwise. $\endgroup$ – Beni Bogosel Feb 8 '13 at 6:59
  • $\begingroup$ To find eigenvalues of operators I would look at the Lanczos and Arnoldi algorithms. $\endgroup$ – Wolfgang Bangerth Feb 8 '13 at 13:10
  • $\begingroup$ It would seem like he is solving a nonlinear matrix eigenvalue problem. How does one apply Lanczos or Arnoldi to such problems? $\endgroup$ – Victor Liu Feb 9 '13 at 4:10

Here is what I did: the idea is to find the eigenvalues in a certain interval $[a,b]$

  • choose a discretization step and a corresponding discretization of the interval and then calculate the values of the function on that discretization. This discretization must be done such that there is a reasonable equilibrium between the computation time and the precision I want. Each function computation calculates the determinant of a $100\times 100$ matrix which is obtained by evaluating a Bessel function over the entries of a distance matrix.

  • find the peaks among the calculated values

  • around each peak make a golden search in order to find one precise value close to the peak

(the method is inspired from the work of Alves and Antunes: http://msvlab.hre.ntou.edu.tw/cite/CMC-Alves-2005.pdf)

This is very accurate (errors of the order $10^{-6}$) and reasonably fast (for this precision) when all the eigenvalues are simple. Things get a bit messy when eigenvalues are double and worse if they are almost double. If an eigenvalue is double then looking at the kernel of $A_\lambda$ can give the multiplicity of $\lambda$.

If the eigenvalues are almost double, the kernel of $A_\lambda$ does not see the eigenvalue $\lambda\pm \varepsilon$, so the only way I managed to solve this is by choosing an interval $(\lambda-\delta,\lambda+\delta)$ and make an even smaller discretization in which the almost double eigenvalues will be visible.

Unfortunately, in my work (of optimizing eigenvalues), eigenvalues almost always tend to get double at the optimum.

If you have any suggestions on how could I improve the presented algorithm, they are more than welcome.

| cite | improve this answer | |

Your Answer

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

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