32
votes
Accepted
Why do we usually not want the eigenvalues of non-symmetric matrices?
Stability under perturbations
Let $E$ be a perturbation such that $\|E\| \leq \varepsilon$.
If $A$ is symmetric, then the eigenvalues of $A+E$ are at a distance $\varepsilon$ from those of $A$. (Bauer-...
- 12.6k
15
votes
Why are systems with clustered eigenvalues easy to solve?
A good explanation of this phenomena with many examples is given in Iterative Methods for Linear and Nonlinear Equations by Tim Kelley. The crux of it comes down to the fact that each step of a ...
- 3,101
14
votes
Accepted
Quality of eigenvalue approximation in Lanczos method
The convergence behavior you are seeing is actually expected. One of
things that makes the Lanczos method so interesting is that it does
a good job of simultaneously converging eigenvalues at both ...
- 6,339
14
votes
Accepted
How does the QR algorithm applied to a real matrix returns complex eigenvalues?
In a nutshell, the QR algorithm applied to a matrix $A$ is an iterative procedure that converges to the real Schur decomposition: a unitary matrix $Q$ and a matrix $R$ in block upper triangular form (...
- 12.4k
14
votes
Accepted
Real-world applications of eigendecomposition?
You can compute analytic functions of matrices using the eigendecomposition (or more generally by using the Jordan normal form in case the matrix is defective), you cannot do so with the singular ...
- 2,882
12
votes
Accepted
Eigenvalues of Small Matrices
The first thing to note is that the correspondence between finding
roots of a polynomial (any polynomial) and finding the eigenvalues
of an arbitrary matrix is really direct, and it's a rich subject, ...
- 11.5k
12
votes
Optimized Lanczos method for finding eigenvalues of $A \otimes B$
There isn't much complicated behind this idea; it's just that since Lanczos is a black-box method you can use any method of your choice to compute the products $v\mapsto (A\otimes B)v$ needed in the ...
- 12.6k
11
votes
Complex Eigenvalues using eig (Matlab)
You have an ill-conditioned eigenvalue problem. Consider a perturbation $\delta A$ in your matrix $A$—with double-precision floats this is $O(10^{-16})$. It turns the eigendecomposition from
$$ X^{-1}...
- 11.5k
11
votes
Cheap recalculation of eigenvalues and eigenvectors for a low-rank update of the matrix
Unfortunately, I don't think there is a good algorithm to do this efficiently.
Given the eigendecomposition $\mathbf A = \mathbf X \mathbf D \mathbf X^T$, one is tempted to project $\mathbf v$ onto ...
- 5,076
11
votes
Electromagnetic Eigenvalue problem in FEM yielding spurious solutions
You are correct, this formulation does introduce a spurious space. It's not actually due to any function space/discretization choice, but rather that change of variables step ($\mathbf e_t = k_z \...
- 5,076
10
votes
Accepted
Convexity of Sum of $k$-smallest Eigenvalue
Given $A \in {\bf S}^n$ (a positive definite matrix) with eigenvalues $\lambda_1 \leq \lambda_2 \leq \ldots \leq \lambda_n $, then:
$\displaystyle f_k(A)=\sum_{i=1}^{k} \lambda_i$ is concave. Why?
$$...
- 2,236
10
votes
Accepted
How does gmres method iteration behave for this non-diagonalizable matrix?
Unfortunately, convergence of GMRES does not have a clear dependence on the distribution of eigenvalues.
It was proved by Greenbaum, Ptak and Strakos in 1996 that you can construct examples with an ...
- 12.6k
10
votes
Accepted
Why are all eigen solvers iterative?
There is simply no closed-form expression in terms of the four operations and radicals for the eigenvalues of a matrix greater than $4\times 4$.
This follows from the facts that (1) there are ...
- 12.6k
10
votes
Real-world applications of eigendecomposition?
In Quantum theory the observables corresponding to an operator are the eigenvalues of that operator. So, as an example, should you want the energy levels available to electrons in a molecule you need ...
- 626
9
votes
Accepted
Correct eigenfunctions of Laplace operator by Finite Differences
You should specify the eigenvalues you want with which="SM", for example.
Check the following snippet. I also changed the solver, since your system is symmetric.
<...
- 8,622
9
votes
Nonlinear eigenvalue problem - MATLAB code
Given a nonlinear eigenvalue problem of the form $A(\lambda)x = 0$, reducing it to a real equation $\det(A(\lambda))=0$ is known to be a poor method for just the reason you've discovered yourself. The ...
- 11.5k
9
votes
Is LAPACK behind the cutting edge of dense linear algebra?
When one says an algorithm is of order $O(n)$, that may mean that the complexity is given by: $c + b*n$. With every new element you add you increase in runtime (effectively). What mathematically ...
- 3,065
8
votes
Accepted
Eigen - Max and minimum eigenvalues of a sparse matrix
There are two relatively convenient options for calculating
selected (e.g. a few largest or smallest) eigenvalues using Eigen.
The first is Spectra, a header-only C++ library based on Eigen
that uses ...
- 6,339
8
votes
Accepted
How to compute all the eigenvalues of a large sparse matrix using matlab?
"Get more RAM" may be one of your best options. :) Prices are reasonably low right now, and it's one of the best upgrades you can gift your computer anyway. 10k x 10k is borderline but still doable ...
- 12.6k
8
votes
Accepted
Implementation of a $O(n \log(n))$ method to compute eigenvalues of real symmetric tridiagonal matrices
I think the method has too much implementation complexity and too narrow applicability to be worth it.
Though the paper is correct to point out the importance of solving the tridiagonal-symmetric ...
- 5,076
8
votes
Is LAPACK behind the cutting edge of dense linear algebra?
LAPACK has been on the cutting edge for just about three decades, and probably still is for its niche. However, given given recent developments in libraries for the simpler BLAS-type matrix operations ...
- 181
8
votes
Accepted
Can this simple quadratic optimization problem be turned into a simple eigenvalue problem?
At least for the second question the answer is yes. See for example Mattheij, Robert MM, and Gustaf Söderlind. "On inhomogeneous eigenvalue problems. I." Linear Algebra and its Applications ...
- 188
8
votes
Accepted
Python scipy eigh(Arpack) giving wrong eigenvalues for generalized eigenvalue problem
The matrix B (M in the documentation) needs to positive definite according to the documentation: "If sigma is None, M is positive definite", this is in addition to the first requirement &...
- 407
8
votes
Why do we usually not want the eigenvalues of non-symmetric matrices?
Amazing question which has a long answer, but I will try to be concise. In the context of Krylov subspace methods for general matrices, the eigenvalues of a non-symmetric matrix mean very little. In “...
- 2,851
8
votes
Why are systems with clustered eigenvalues easy to solve?
At the $k$th iteration, typical Krylov methods for solving $Ax=b$ (such as CG, MINRES, and GMRES) implicitly construct a $k$th order polynomial $Q(x)$ such that:
$Q(0) = 1$.
$|Q(\lambda_i)|$ is as ...
- 3,225
8
votes
Real-world applications of eigendecomposition?
The SVD is a special case of the eigen-decomposition, or could be thought closely related to it.
For instance, the Kahan-Golub algorithm to compute the SVD is developed from the eigen-decomposition of ...
- 6,159
8
votes
Real-world applications of eigendecomposition?
The energy levels available to a system (e.g. an atom, molecule, material, etc.) are the eigenvalues of the system's Hamiltonian matrix.
The following diagram which is presented to grade 9 (typically ...
- 195
7
votes
Matlab, Mathematica & LAPACK returning 3 different eigenvectors
Seems that you have a duplicate eigenvalue. Thus, you have two eigenpairs $(\lambda_1, x_1)$ and $(\lambda_2, x_2)$ where $\lambda_1 = \lambda_2$. Denote $\lambda = \lambda_1 = \lambda_2$. Let $\alpha$...
- 2,104
7
votes
Eigenvectors of a small norm adjustment
There exist special techniques for updating the eigen-decomposition of time-dependent covariance matrices. Given a "prior" eigenvalue decomposition (say at some initial time $t^0$), these recursive ...
- 2,236
7
votes
Accepted
Eigenvector with maximum overlap
The following paper suggests that the Jacobi-Davidson method can be used to target eigenvectors based on "any property that can be computed from the eigenvector", which would seem to include overlap ...
- 303
Only top scored, non community-wiki answers of a minimum length are eligible