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.

Filter by
Sorted by
Tagged with
6
votes
3answers
391 views

Preconditioner for finding the smallest eigenpairs of a large, but structured, matrix

I'm trying to find the eigenvector corresponding to the second smallest eigenvalue of a large $(4,000,000 \times 4,000,000)$ matrix $L$. $L$ is a graph Laplacian, with the following structure: $L = D -...
2
votes
0answers
98 views

Preconditioner for large size hermitian eigenvalue problems

Basically I try to compute several smallest eigenvalues of some sparse 50k*50k eigenvalue problems using matlab. $$Ax = \lambda Bx$$ With matlab eigs, it's not as fast as I expected. So I tried some ...
8
votes
2answers
512 views

Continuity of eigenvectors of parametric matrix

I have $n$-dimensional matrices $\mathrm{\hat{H}}(\vec{k})$ depending on vector parameter $\vec{k}$. Now, eigenvalue routines return eigenvalues in no particular order (they are usually sorted), but ...
1
vote
2answers
287 views

how can I numerically calculate all eigenvectors of a $n \times n$ complex tridiagonal matrix?

I have tried matlab eig command, it results true eigenvalues but wrong eigenvectors. I also tried direct iteration with rayleigh qotient which is better but doesn't give all eigenvectors also I have ...
8
votes
1answer
879 views

Solving a large non-hermitian generalised eigenvalue problem from a linear stability analysis using SLEPc

I have a generalised matrix problem: $A x = \lambda B x$ from a spectral method on a linear stability analysis problem. My matrix B is diagonal and positive semi-definite. A is non-hermitian and ...
5
votes
2answers
612 views

find a set of linearly independent columns in a $m\times n$ matrix

my question is between mathematics, physics and informatics. Suppose i have an Hamiltonian (hermitian matrix) that i can diagonalize. The matrix that allows this transformation is a unitary matrix ...
4
votes
3answers
5k views

Algorithm for Principal Eigenvector of a Real Symmetric 3x3 Matrix

I have a 3x3 covariance matrix (so, real, symmetric, dense, 3x3), I would like it's principal eigenvector, and speed is a concern. Is there a fast algorithm for this specific problem? I've seen ...
12
votes
2answers
6k views

What is the fastest way to compute all eigenvalues of a very big and sparse adjacency matrix in python?

I'm trying to figure out if there is a faster way to compute all the eigenvalues and eigenvectors of a very big and sparse adjacency matrix than using scipy.sparse.linalg.eigsh As far as I know, this ...
6
votes
1answer
1k views

generalized eigenvalue problem

I need to solve a real generalized eigenvalue problem $Ax= \lambda Bx(*)$ A and B are calculated from equations below: $$A=\sum_{i,j=1}^{N}W_{ij}(K_{i}-K_{j})\beta\beta^{T}(K_{i}-K_{j})^{T}$$ $$B=\...
1
vote
4answers
370 views

Ground state eigenvector different for different eigen solvers (differs by negative sign in the elements). Does it matter?

Here is some code that hopefully clearly illustrates what I'm doing: ...
6
votes
4answers
2k views

computing the determinant of a dense nonsymmetric 100x100 matrix having very big and very small eigenvalues

The motivation for my question is the following: in one of Project Euler questions there is a need to count the spanning trees of a rectangular grid graph of dimension 100x500. By the Matrix-Tree ...
13
votes
1answer
301 views

Specialized methods for complex symmetric tridiagonal generalized eigenvalue problems

I have to solve generalized eigenvalue problems $Ax = \lambda Bx$ where $A$ and $B$ are both tridiagonal, $B$ is symmetric positive definite and real, but $A$ is only complex symmetric (not definite ...
4
votes
1answer
453 views

Numerical Methods for minimizing a Non-Differentiable Convex Function of Several Variables

I have a multi-variable convex continuous function which is not differentiable. I am interested to know about different numerical techniques, possibly also references to them, used for this. Read ...
6
votes
1answer
2k views

Simple Lanczos algorithm code to obtain eigenvalues and eigenvectors of a symmetric matrix

I would like to write a simple program (in C) using Lanczos algorithm. I came across a Matlab example which helped me to understand a bit further the algorithm, however from this piece of code I can't ...
7
votes
2answers
894 views

Finding the distribution (histogram) of eigenvalues for large sparse matrices

Are there any existing programs that are able to compute the (approximate) distribution of eigenvalues for very large (symmetric) sparse matrices? Note that I do not need the eigenvalues themselves, ...
4
votes
1answer
649 views

On implementations of the complex QR decomposition

I have an mathematical theorem on the QR decomposition, which relies on the QR decomposition of an invertible square complex matrix always constructing a triangular matrix with real diagonal entries. ...
2
votes
2answers
2k views

Implementing PageRank using the Power Method

I am trying to implement the PageRank algorithm described in this paper (Fig. 1). Here is the breakdown of the steps: http://www.louismullie.com/algo.png where: ...
3
votes
2answers
3k 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
1answer
3k 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
1answer
226 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
3answers
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
2answers
362 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
1answer
181 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
1answer
258 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 ...
6
votes
1answer
165 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 ...
3
votes
2answers
240 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$ (...
4
votes
2answers
193 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 ...
1
vote
2answers
983 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
2answers
706 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 ...
13
votes
6answers
956 views

Approximate spectrum of a large matrix

I want to compute the spectrum (all the eigenvalues) of a large sparse matrix (hundreds of thousands of rows). This is hard. I am willing to settle for an approximation. Are there approximation ...
13
votes
3answers
1k 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
1answer
307 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
2answers
510 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
1answer
157 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
2answers
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
3answers
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
2answers
417 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 ...
11
votes
4answers
2k 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 ...
4
votes
0answers
599 views

Perron-Frobenius theorem on general real symmetric matrices

From the Perron-Frobenius theorem, it might be concluded that the spectral radius is the largest eigenvalue for positive matrices, ie, matrices with strictly positive entries. In other words, the ...
6
votes
2answers
240 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? ...
2
votes
1answer
221 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}$ ...
7
votes
3answers
718 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 ...
7
votes
3answers
8k views

Gershgorin Circle Theorem to estimate the eigenvalues

In order to estimate the eigenvalues of a real symmetric $n\times n$ matrix, I intend to use the Gershgorin Circle Theorem. Unfortunately, the examples one might find on the internet are a bit ...
6
votes
2answers
715 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 ...
11
votes
3answers
424 views

Parallel algorithm for eigensystem of a tridiagonal matrix

I'm doing a Lanczos diagonalization of a large sparse matrix (~2 million elements). Almost all of the steps in the Lanzcos algorithm are done in parallel on the GPU, except for diagonalizing the ...
3
votes
1answer
854 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)...
4
votes
0answers
99 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(...
27
votes
7answers
21k views

What is the fastest way to calculate the largest eigenvalue of a general matrix?

EDIT: I am testing if any eigenvalues have a magnitude of one or greater. I need to find the largest absolute eigenvalue of a large sparse, non-symmetric matrix. I have been using R's ...
5
votes
2answers
3k 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$, ...
4
votes
3answers
218 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 ...