13
$\begingroup$

Given a real $n\times n$ matrix $A$, one can find the eigenvalues in $O\left(n^3\right)$ by using say, the $QR$ algorithm.

Now, what if we guess an eigenvalue $\lambda_0$, and we want to know if it's actually an eigenvalue of the matrix $A$? Intuitively, this should be significantly faster than actually finding all of the eigenvalues. We can of course check if $\lambda_0$ is actually an eigenvalue by calculating $\det(A-\lambda_0 I)$, but calculating the determinant is also $O\left(n^3\right)$.

So:

  • Is there a faster than $O\left(n^3\right)$ method for testing the "eigenvaluedness" of a specific number $\lambda_0$, without solving for the rest of the $\lambda_i$'s? Can one prove there isn't?

  • Does it help if $A$ is orthogonal, symmetric or has other special (non triangular) form?

Bounty update:

Bounty goes to whoever shows either of the following:

  1. A method of checking a possible eigenvalue in less than $O(n^3)$.
  2. A proof or sufficiently convincing heuristic argument that no such method exists.
$\endgroup$
  • 2
    $\begingroup$ To my understanding pretty much anything you might do would require generating a candidate for the corresponding eigenvector. Simple things like Gerschgorin can rule out completely nonsensical eigenvalues, of course, but doing much better than that you tend to need an eigenvector guess. Given an eigenvector guess, in the symmetric case we can easily compute the Rayleigh quotient and compare it to $\lambda_0$. In the nonsymmetric case we have options. A simple one is to compute the mean and variance of $\{ (Ax)_i/x_i, \, i=1,\dots,n \}$ where we adopt the convention $0/0 = \lambda_0$. $\endgroup$ – Ian Aug 17 '14 at 19:24
  • 2
    $\begingroup$ Continued: one can often get an eigenvector candidate in faster than $O(n^3)$ time by using an iterative linear system method. Incidentally, QR fails in a lot of important cases, including the orthogonal case. $\endgroup$ – Ian Aug 17 '14 at 19:25
  • 2
    $\begingroup$ @Ian - Wouldn't that still be $O(n^3)$? $\endgroup$ – nbubis Aug 17 '14 at 19:54
  • 2
    $\begingroup$ If I'm not completely mistaken, this is equivalent to deciding whether a matrix $B$ is singular in $O(n^3)$ (to show equivalence, we can take $B = A-\lambda_0 I$ to show one direction and $B=A$, $\lambda_0=0$ for the other). That might be a more common problem and easier to search for? $\endgroup$ – JiK Aug 19 '14 at 22:01
  • 2
    $\begingroup$ According to Wikipedia, there are algorithms with a better complexity (but not necessarily faster for currently used matrices): en.wikipedia.org/wiki/Determinant#Calculation $\endgroup$ – xavierm02 Aug 19 '14 at 22:14
7
+50
$\begingroup$

The first algorithm computing the determinant faster than in $O(n^{3})$ time (his algorithm worked in $O(n^{\ln 7/\ln 2})$ time) was given by Volker Strassen in this classical paper. Therefore, $O(n^{\ln 7/\ln 2})$ time suffices to check whether a given number is an eigenvalue or not. In fact, the problem of computing the determinant has asymptotically the same complexity as the problem of multiplying two $n\times n$ matrices, for which $O(n^{2+\varepsilon})$ compleixty is conjectured. Some information and references on this are contained in the link provided by xavierm02 in his comment.

$\endgroup$
4
$\begingroup$

Of course, the Strassen algorithm computes the determinant in $O(n^{2.807})$ ; moreover it is the sole algorithm that, in practice, does the job faster than in $O(n^3)$ - when $n\geq 2048$ - (to fix ideas) (then, let $\omega=2.807$ if $n\geq 2048$, otherwise $\omega=3$.). Yet, that is not really the question here. Indeed the calculation of $spectrum(A)$ and the calculation of $\det(A)$ (or of the square $A^2$) are all in $O(n^{\omega})$, under the condition that we seek some approximation of the true values. So the good question would be:

We consider the following problem : Let $A\in M_n(\mathbb{C}),\lambda_0\in \mathbb{C},r\in \mathbb{N}$ ; does there exist an eigenvalue $\lambda$ of $A$ s.t. $|\lambda-\lambda_0|<10^{-r}$ ? Its complexity is $\sim kn^{\omega}$. What is the value of $k$ ?

We consider the following experiment (with Maple): $A\in M_{10}(\mathbb{Z})$ is randomly chosen ($a_{i,j}\in[-99,99])$. $A$ admits an eigenvalue $\lambda\approx -166-15i$ and $\lambda_0$ is constructed with the first $15$ significant digits of $Re(\lambda)$ and $Im(\lambda)$. If $r=12$, then the answer to our problem is YES. Unfortunately $\det(A-\lambda_0 I))\approx 1.7\times 10^7-3.7\times10^7i$. Finally, it does not suffice to calculate the previous determinant. We must also consider the derivative in $\lambda_0$ of the function $\phi:t\rightarrow \det(A-tI)$.

EDIT: More precisely, $\phi(\lambda_0)\approx(\lambda_0-\lambda)\phi'(\lambda_0)$ and, consequently, $|\lambda-\lambda_0|\approx\rho=\dfrac{|\det(A-\lambda_0I)|}{|trace(adj(A-\lambda_0I))|}=\dfrac{1}{|trace((A-\lambda_0I)^{-1})|}$ (if $\lambda_0\not=\lambda$). For the previous instance, we find $|\lambda-\lambda_0|\approx 6\times 10^{-13}$. The complexity of the calculation of $\rho$ , by $LU$ method, is $\sim n^3$ (that is $k=1$). Note that the complexity of one decomposition QR is $\sim\dfrac{4}{3}n^3$.

$\endgroup$
3
$\begingroup$

It is not necessary to actually calculate the determinant, only to confirm whether it's zero.

As such, it suffices to attempt a matrix inversion for $\mathbf{A}-\lambda\mathbf{I}$... if it fails, then the determinant is zero, and therefore we have confirmed $\lambda$ to be an eigenvalue.

It can be shown that, through a divide-and-conquer approach, matrix inversion has the same complexity as matrix multiplication. And because Williams algorithm exists with $O(n^{2.3727})$, this is also an achievable complexity for confirmation of an eigenvalue (up to a certain numerical accuracy, of course).

$\endgroup$
  • $\begingroup$ @ Glen O , 1. Generically $\lambda$ is a simple eigenvalue ; then the algorithm given $(A-\lambda I)^{-1}$ fails during the last step. Thus generically the complexity of your calculation is $\sim n^3$ , that is greater than complexity of the calculation of the det. 2. In practice, the Coppersmith- Winograd algorithm is not efficient (as one of Williams) ; the exponent $2.3...$ has purely mathematical interest and no impact for the computation of a determinant on a computer. $\endgroup$ – loup blanc Aug 25 '14 at 23:47
  • $\begingroup$ 3. Either you consider an approximation, and $\det(A-\lambda_0I)$ is not small in general (read my post) or you perform an exact calculation and the computation of the det is no more in $n^3$ ; if the $(a_{i,j})$ are integers, then it is in $O(n^{4/3}||A||)^{1+\epsilon}$ where $||A||$ measures the maximal length of the entries of $A$. $\endgroup$ – loup blanc Aug 25 '14 at 23:52
  • $\begingroup$ Read the formula in my last post: $O(n^{3+1/3}||A||)^{1+\epsilon}$. cf. www4.ncsu.edu/~kaltofen/bibliography/01/KaVi01.pdf $\endgroup$ – loup blanc Aug 26 '14 at 0:02
  • $\begingroup$ @loupblanc - The fact that in practice the Coppersmith-Winograd algorithm is only faster for very large matrices is beside the point. The question we are answering is asking about complexity, not raw speed, as demonstrated by the $O(n^3)$ in the title. And the failure of the algorithm to produce an inverse is precisely what we're looking for, and so the complexity is equal to the complexity of calculating the inverse, which is itself equal to the complexity of multiplying matrices. Remember, we need not determine $\lambda$, only test it. $\endgroup$ – Glen O Aug 26 '14 at 1:08

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.