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
33
votes
6answers
28k 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 ...
14
votes
6answers
1k 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 ...
14
votes
2answers
12k 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 ...
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 ...
13
votes
2answers
576 views

Verification in Eigenvalue problems

Let us start with a problem of the form $$(\mathcal{L} + k^2) u=0$$ with a set of given boundary conditions (Dirichlet, Neumann, Robin, Periodic, Bloch-Periodic). This corresponds with finding the ...
13
votes
1answer
324 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 ...
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 ...
11
votes
3answers
478 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 ...
11
votes
1answer
976 views

Smallest eigenvalue without inverse

Suppose $A\in\mathbb{R}^{n\times n}$ is a symmetric, positive definite matrix. $A$ is big enough that it's expensive to solve $Ax=b$ directly. Is there an iterative algorithm for finding the ...
11
votes
2answers
232 views

Benchmark problems for eigenvalue reordering algorithms sought

Every real matrix $A$ can be reduce to real Schur form $T = U^T A U$ using an orthogonal similiary transform $U$. Here the matrix $T$ is quasi-triangular form with 1 by 1 or 2 by 2 blocks on the main ...
10
votes
2answers
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 ...
10
votes
2answers
780 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 ...
9
votes
2answers
4k views

Quality of eigenvalue approximation in Lanczos method

I try to familiarize myself with iterative eigenvalue solvers such as Lanczos. So I tried rewrite it to python directly according to wiki. But it doesn't seem to work. The problem: it approximates ...
9
votes
2answers
940 views

Sparse smallest eigenvalue problem on a linear subspace?

I am interested in methods for solving the optimization problem $$ \begin{array}{rl} \arg\min_x & x^T A x \\ \mathrm{s.t.} & x^T x = 1 \\ & Bx = 0 \end{array} $$ where $A$ is symmetric ...
9
votes
2answers
510 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 ...
9
votes
1answer
673 views

Implementation of Jacobi-Davidson method for cubic eigenvalue problem

I have a large cubic eigenvalue problem: $$\left(\mathbf{A}_0 + \lambda\mathbf{A}_1 + \lambda^2\mathbf{A}_2 + \lambda^3\mathbf{A}_3\right)\mathbf{x} = 0.$$ I could solve this by converting to a ...
9
votes
2answers
391 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 ...
8
votes
2answers
201 views

diagonalization of matrix - omitting small matrix elements

I was wondering whether there is some theorem that allows me to put an upper bound on the error introduced by omitting small matrix elements from a matrix before diagonalization. Let's assume we ...
8
votes
1answer
6k views

How to use Lanczos method to compute eigenvalues and eigenvectors

I have a sparse and symmetric matrix A(n x n). The method Lanczos tranforms matrix A into tridiagonal and symmetric matrix T and the Lanczos vectors in matrix V. From there how do I compute k ...
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 ...
8
votes
1answer
170 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 ($\...
8
votes
1answer
3k 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
2answers
698 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 ...
8
votes
1answer
145 views

Eigenvalue-like problem with coupled ODEs

I am looking at the following system of ODEs: \begin{array}{r}{\left[c_{2}(k)-\partial_{\tau}^{2}\right] \varphi_{2}\left(\tau \right)=f_{21}(\tau) \varphi_{1}\left(\tau \right)} \\ {\left[c_{1}(k)-...
8
votes
2answers
276 views

calculating eigenvector components of a given vector

I have some vector $V$ which can be decomposed into the eigenspace of the hermitian sparse operator $M$: $V = \sum_i v_i \hat{m}_i$ Is there a way to find the $\hat{m}_i$ (the eigenvector itself) ...
8
votes
1answer
992 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 ...
8
votes
0answers
359 views

Eigenvalue with largest imaginary part

Iterative eigensolvers such as ARPACK, give the option to find a subset of the eigenvalues which have the largest imaginary part. My question is how do these algorithms work. As I understand it, ...
8
votes
3answers
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 $\...
7
votes
3answers
9k 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 ...
7
votes
4answers
3k 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 ...
7
votes
1answer
631 views

Correct eigenfunctions of Laplace operator by Finite Differences

I am trying to compute the eigenfunctions of the Laplace operator, i.e. finding $u$ in $$ -\nabla^2 u = \lambda u .$$ For now I am trying to do this in 1D, so $$ \nabla^2 = \partial_{xx} .$$ I am ...
7
votes
3answers
832 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
1answer
151 views

What are some ideas to preprocess / precondition the following linear system?

Let $A\in \mathbb{R}^{n\times n}$ symmetric and positive semidefinite, and $\omega\in \mathbb{R}\setminus\{0\}$. I am interested in solving the following linear system for a range of values of $\...
7
votes
2answers
1k 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, ...
7
votes
1answer
252 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 ...
7
votes
1answer
952 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 ...
7
votes
0answers
201 views

Implementation of Lanczos method that returns tridiagonal matrix

The Lanczos method can be used to obtain extremal eigenpairs of sparse symmetric or hermitian matrices. I know there are several implementations of the Lanczos method (as well as Arnoldi, Davidson, ...
7
votes
0answers
158 views

Solving a coupled eigen value problem

I have the following problem: $$\begin{bmatrix}A &B \\C& D\end{bmatrix}\begin{bmatrix}x\\y\end{bmatrix} = \begin{bmatrix}\lambda I_m & 0 \\ 0& \mu I_n\end{bmatrix}\begin{bmatrix}x \\y\...
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}^...
6
votes
3answers
507 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 -...
6
votes
1answer
3k 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 ...
6
votes
2answers
293 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? ...
6
votes
1answer
434 views

Eigenvector with maximum overlap

Given a matrix $M$ and a vector $v$, is there an efficient method to find the normalized eigenvector of $M$ that is closest to $v$, in that it has maximal overlap. More explicitly, a vector $v$ can be ...
6
votes
2answers
544 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 ...
6
votes
2answers
911 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 ...
6
votes
1answer
175 views

Roots of a function for eigensystem

I want to find the roots for $\kappa$ for the equation $$\sqrt{\alpha - 1} \cos{\left (\frac{\sqrt{2} \sqrt{\alpha - 1}}{2 \sqrt{\epsilon}} \right )} \cosh{\left (\frac{\sqrt{2} \sqrt{\alpha + 1}}{2 \...
6
votes
1answer
1k views

Numerical computation of Perron-Frobenius eigenvector

I would like to efficiently and (to the extent possible) reliably find the Perron-Frobenius eigenvector of non-negative matrices. These are not stochastic matrices, they are typically dense, and their ...
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=\...
6
votes
1answer
299 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
2answers
2k views

Numerical Solution to Schrödinger Equation--Multiple Wells

I am trying to solve for the allowed wavefunctions and energies for a 1D quartic potential well. To do this I am using the patching method (https://engineering.dartmouth.edu/microeng/otherweb/...