Questions tagged [eigensystem]
An eigenvector of an operator is a vector such that the action of the operator is the same as multiplication by a constant, called the eigenvalue. The eigensystem of an operator is the set of all such eigenvectors and their associated eigenvalues.
184
questions
4
votes
1
answer
5k
views
Power Iteration on general matrices (with higher multiplicity of dominant eigenvalue)
To compute the eigenvector corresponding to a dominant eigenvalue of a matrix $A\in\mathbb{R}^{n\times n}$, one could apply the Power Iteration: $$v_1=\frac{Av_1}{\|Av_1\|}.$$
1) in case $A$ is ...
3
votes
2
answers
4k
views
An eigenvalue algorithm to solve constrained quadratic form minimization
I have a quadratic form $\mathbf{x}^T A \mathbf{x}$ (where $A\in \mathbb{R}^{n\times n}$ is symmetric matrix and $\mathbf{x}\in \mathbb{R}^n$) that I want to minimize given the normalization ...
3
votes
1
answer
242
views
Manipulating a generalized eigenvector problem to plain eigenvector problem
Let $X\in\mathbb{R}^{n\times p}$ denote a matrix with $p$ linearly-independent columns, and let $L\in\mathbb{R}^{n\times n}$ denote a symmetric matrix. Furthermore, let $D\in\mathbb{R}^{n\times n}$ ...
6
votes
3
answers
1k
views
Eigenvectors with the Power Iteration
To compute the eigenvector corresponding to dominant eigenvalue of a symmetric matrix $A\in\mathbb{R}^{n\times n}$, one used Power Iteration, i.e., given some random initialization, $u_1\in\mathbb{R}^...
9
votes
2
answers
398
views
Fastest way to find eigenpairs of a small nonsymmetric matrix on a GPU in shared memory
I have a problem where I need to find all positive (as in the eigenvalue is positive) eigenpairs of a small (usually smaller than 60x60) nonsymmetric matrix. I can stop calculating when the eigenvalue ...
2
votes
1
answer
218
views
Root Convergence rate of Iterative Scheme
I have an iterative sequence for optimizing an EM (Expectation Maximization) algorithm based loss function $L(X)$ with $t$ being the iteration number as:
$X_t=ABX_{t-1}+CX_{t-1}+X_{t-1}$ where $A$ is ...
6
votes
1
answer
186
views
Identifying the name/provenance of a technique to find the nullspace vectors of a matrix by random sampling and the conjugate residual method
I have got a large sparse matrix $A \in \mathbb R^{n \times n}$ and I want to find non-trivial elements in the kernel/nullspace of this matrix. How can this be done? I would like to learn more about a ...
6
votes
1
answer
319
views
Dense generalized hermitian indefinite eigenvalue problem
Lapack contains a driver routine to solve dense generalized Hermitian positive definite eigenvalue problems of the form $Ax=\lambda Bx$, where $A$ and $B$ are both Hermitian, and $B$ is positive ...
3
votes
2
answers
314
views
Positive semi-definiteness of a (symmetric) matrix
Suppose a matrix $A\in\mathbb{R}^{n\times n}$ is given. Faced with a proof for $$x^TAx>0,$$
for a non-zero vector $x\in\mathbb{R}^{n}$, I was thinking to use the information of the spectrum of $A$ (...
7
votes
3
answers
885
views
Largest eigenvalue of FD discrete Laplacian
Is there good approximation for largest (in magnitude) eigenvalue for discrete Laplacian ($\nabla^2$) obtained from nonuniform structured grid (like that)?
Of course, one can always use general ...
4
votes
2
answers
211
views
Finding dominant eigenvectors of an operator that is small but costly to evaluate
Suppose I have a symmetric linear operator $A:\mathbb{R}^k \rightarrow \mathbb{R}^k$ where $k$ is "small" (eg., $k=100$), and I want to find it's first few eigenvectors, (eg., $10$ eigenvectors).
If ...
2
votes
2
answers
2k
views
What does "Counting algebraic multiplicity" mean?
As stated in the title, I encountered a proof with the final statement of the form
"the eigenvalues of A are then $\{\lambda_1+c, \lambda_2, \dots, \lambda_n \},$ counting algebraic multiplicity.
...
10
votes
2
answers
852
views
Diagonalization of Dense Ill Conditioned Matrices
I am trying to diagonalize some dense, ill-conditioned matrices. In machine precision, results are inaccurate (returning negative eigenvalues, eigenvectors do not have the expected symmetries). I ...
8
votes
3
answers
1k
views
Laplacian eigenmodes on a semi-circular region with finite-difference method
The computation of eigenmodes of a semi-circular membrane reduces to the following eigenvalue problem
$$\nabla^2u=k^2u\;,$$
where the region of interest is a semi-circle defined by $r\in[0,1]$ and $\...
14
votes
3
answers
2k
views
SVD for finding the largest eigenvalue of a 50x50 matrix -- am I wasting significant amounts of time?
I've got a program that computes the largest eigenvalue of many real symmetric 50x50 matrices by performing singular-value decompositions on all of them. The SVD is a bottleneck in the program.
Are ...
5
votes
1
answer
506
views
solving generalized eigenvalue problems with the same precondition
suppose solving sequential generalized eigenvalue problems
$$A_i x= \lambda Bx, i=1,2,3,\ldots $$
In general setting, we always need to perform LU for matrix B
(preconditioned) before to apply the ...
6
votes
2
answers
576
views
Large-scale generalized eigenvalue problem with low rank LHS matrix
Assume that we have generalized eigenvalue problem:
$B^HB\textbf{x} = \lambda A\textbf{x}$
where $A$ is an nxn Hermitian sparse matrix (n is very large, so we do not have $A^{-1}$ but can solve ...
8
votes
1
answer
179
views
Eigenspace basis continuously depending on parameters
I have a Hermitian matrix $\mathbf{H}$ which depends on two parameters say $x$ and $y$.
When I diagonalize it at two close points $(x_1,y_1)$ and $(x_2,y_2)$ I get two close eigenvalues ($\...
4
votes
2
answers
3k
views
How to parallelize the computation of eigenvalues of a sparse symmetric matrix in MATLAB?
I have a similarity matrix which is symmetric and sparse. How can I parallelize the computation of the eigenvalues of this matrix in MATLAB?
8
votes
3
answers
2k
views
Compute smallest eigenvectors of a matrix
It appears that matlab's eigs is giving me bad approximations of the smallest eigenvectors of a matrix.
I assume I can use some slower methods which would also be ...
9
votes
2
answers
554
views
Is there a generalization of the Sylvester Inertia Law for the symmetric generalized eigenvalue problem?
I know that in order to solve symmetric eigenvalue problem $Ax = \lambda x$, we can use the Sylvester Inertia Law, that is the number of eigenvalues of $A$ less than $a$ equals the number of negative ...
6
votes
2
answers
341
views
Is it possible to ignore/discard part of a matrix when finding eigenvalues?
I have have multiple large matrices for which I need to find the largest absolute eigenvalue. I know that there is a large submatrix that does not vary. Is it possible to ignore/discard the submatrix?
...
12
votes
4
answers
3k
views
Finding the square root of a Laplacian matrix
Suppose the following matrix $A$ is given
$$ \left[\begin{array}{ccc}
0.500 & -0.333 & -0.167\\
-0.500 & 0.667 & -0.167\\
-0.500 & -0.333 & 0.833\end{array}\right]$$
with ...
2
votes
1
answer
265
views
Proof continuation for rigid transformation on PCA solution
Suppose a matrix $X\in\mathbb{R}^{n\times 3}$ is given as a Principal Component Analysis (PCA) projection from some high dimensional space. The 2D PCA solution on X, say $Y\in\mathbb{R}^{n\times 2}$ ...
6
votes
2
answers
1k
views
Using algebraically smallest eigenvalues to find smallest in magnitude eigenvalues
I have a symmetric indefinite matrix, $H$. I also have a routine that can compute the algebraically smallest eigenvalues of a symmetric indefinite matrix. I would like to compute the eigenvalues with ...
4
votes
3
answers
240
views
Efficiently computing a few localized eigenvectors
Let $H = \triangle + V(x) : \mathbb{R}^2 \rightarrow \mathbb{R}^2$. I am interested in domain decomposition for an eigenproblem involving $H$.
The lowest 1000 eigenfunctions of $H$, $ \psi_i $, can ...
4
votes
1
answer
1k
views
Spectral decomposition with eigenvalue shift
Suppose a square, real and symmetric matrix $G\in\mathbb{R}^{n\times n}$ is given, and it is known to have one zero eigenvalue associated with all ones eigenvector, $1_n$. I'm aware that the (possibly)...
5
votes
0
answers
103
views
Time-stable spectral decomposition algorithm
Consider an $n \times n$ real, time-dependent matrix $A(t)$ such that $A(t) = A(t)^{T} > 0$ and $A(t)$ is continuous on $[a,b]$. Then it is posible to specify a matrix $S(t) \in SO(n)$ such that $S(...
6
votes
2
answers
4k
views
Fast algorithms to find the eigenvalues of some matrix on intervals of interest
I am curious how to quickly compute the eigenvalues for arbitrary matrices, sparse or dense, restricted on some given interval of interest.
Suppose we have an arbitrary $n\times n$ matrix $A$, ...
7
votes
1
answer
1k
views
Sparse hermitian eigensystems: are there better techniques than Arpack or TRLan?
As a part of other work I need to solve relatively large (~1E5x1E5) and sparse (~100 non-zero elements in each raw in few blocks) hermitian eigensystems. Usually only few eigenvalues+vectors are ...
11
votes
2
answers
3k
views
What's the most efficient way to compute the eigenvector of a dense matrix corresponding to the eigenvalue of largest magnitude?
I have a dense real symmetric square matrix. The dimension is about 1000x1000.
I need to compute the first principal component and wonder what the best algorithm to do this might be.
It seems that ...
2
votes
2
answers
1k
views
Lanczos solver implementations in MATLAB/C++ give different results
I have transferred my MATLAB Lanczos solver for symmetric eigenvalue solvers to C++ with the help of Intel MKL and MTL4 libraries. I have some wrapper templates for MKL routines. However during the ...
10
votes
1
answer
4k
views
What is a good stop criterion when using an iterative method to find eigenvalues?
I read this answer, and realized I have been using the difference between sucessive iterates to define a stop criterion for an iterative method of finding eigenvalues/vectors.
What are good stop ...
8
votes
1
answer
280
views
Is multigrid useful for finding all eigenvalues and eigenvectors of a differential equation, or only the lowest eigenvalues?
I've been considering using a multigrid method to calculate the eigenvalues of a particular PDE. I know that multigrid is extremely good at finding the least eigenvalues and their associated ...