Questions tagged [eigenvalues]

Eigenvalues are a special set of scalars associated with a linear system of equations (i.e., a matrix equation) that are sometimes also known as characteristic roots, characteristic values (Hoffman and Kunze 1971), proper values, or latent roots (Marcus and Minc 1988, p. 144).

Filter by
Sorted by
Tagged with
19 votes
1 answer
696 views

Difficulty with Spectral Method using Chebyshev Polynomials

I am having a bit of difficulty in trying to understand a paper. The paper uses spectral method to solve for an eigenvalue that comes from a system of coupled ODEs. I will write out only one equation ...
user avatar
  • 451
17 votes
3 answers
2k views

Why do we usually not want the eigenvalues of non-symmetric matrices?

I came across this line in a class note I am reading where it discusses finding eigenvalues of matrices. In reality we don't go all the way with Arnoldi. We stop at a decent value of 𝑘. Then the 𝑘 ...
user avatar
16 votes
1 answer
3k views

Why does SciPy eigsh() produce erroneous eigenvalues in case of harmonic oscillator?

I'm developing some larger code to perform eigenvalue computations of huge sparse matrices, in the context of computational physics. I test my routines against the simple harmonic oscillator in one ...
user avatar
  • 964
13 votes
2 answers
4k views

Compute all eigenvalues of a very big and very sparse adjacency matrix

I have two graphs with nearly n~100000 nodes each. In both graphs, each node is connected to exactly 3 other nodes so the adjacency matrix is symmetric and very sparse. The hard part is I need all ...
user avatar
  • 233
13 votes
0 answers
623 views

Fast Eigenvalue and SVD Solver for Structured Matrices

I am looking for a fast Eigenvalue and SVD solver for small dense structured matrices (Hankel and Toeplitz). I have searched for efficient implementations in libraries like MKL but I am not able to ...
user avatar
12 votes
3 answers
7k views

Testing if a matrix is positive semi-definite

I have a list ${\cal L}$ of symmetric matrices that I need to check for positive semi-definiteness (i.e their eigenvalues are non-negative.) The comment above implies that one could do it by ...
user avatar
  • 458
12 votes
1 answer
1k 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 ...
user avatar
11 votes
2 answers
243 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 ...
user avatar
10 votes
2 answers
5k 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 ...
user avatar
10 votes
2 answers
559 views

Eigenvectors of a small norm adjustment

I have a dataset that is slowly changing, and I need to keep track of eigenvectors/eigenvalues of its covariance matrix. I've been using scipy.linalg.eigh, but it'...
user avatar
9 votes
3 answers
484 views

Accuracy issues with Arpack in Julia for eigenvalues of smallest magnitude

Following the documentation of Julia's Arpack package (Cf. https://julialinearalgebra.github.io/Arpack.jl/stable/eigs/) I have computed some largest and smallest magnitude eigenvalues of sparse ...
user avatar
9 votes
1 answer
686 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 ...
user avatar
  • 397
8 votes
3 answers
2k views

How does the QR algorithm applied to a real matrix returns complex eigenvalues?

I'm a noob into eigenvalues algorithms, but something call my attention. QR algorithm works with real/complex matrices producing real/complex eigenvalues. However, it can not produce complex ...
user avatar
8 votes
1 answer
4k views

Computational methods for finding the energy eigenvalues of the time-independent Schrodinger equation with arbitrary potential

I have seen in some papers that the energy levels in some arbitrary potential are specified. How can one find the energy levels in such arbitrary potentials. For example, $V(x)=\sin^2(x/2)$ with $x\in[...
user avatar
  • 153
8 votes
2 answers
487 views

Eigenvalues of Small Matrices

I'm writing a small numerical library for 2x2, 3x3, and 4x4 matrices (real, unsymmetric). A lot of numerical analysis texts highly recommend against computing the roots of the characteristic ...
user avatar
  • 373
8 votes
1 answer
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 ...
user avatar
  • 121
8 votes
1 answer
726 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 ...
user avatar
  • 135
8 votes
2 answers
196 views

A misunderstanding or a bug in LAPACK's solver for generalized eigenvalue problems?

In my application, I have two general real matrices $A$,$B$ defined as follows, $$ A=\begin{bmatrix} -s I_3 & A_0 & 0 & 0 \\ A_0^T & -s I_3 & 0 & 0 \\ 0 &...
user avatar
8 votes
1 answer
293 views

Can this simple quadratic optimization problem be turned into a simple eigenvalue problem?

I'm interested in a type of problem on this form $$\min_{x} x^{T}Ax+x^{T}b \quad \text{s.t} \quad x^{T}x=1 $$ where $A$ is positive definite. As you can see, if it weren't for the $x^{T}b$ term in the ...
user avatar
8 votes
1 answer
183 views

Finding the $i$-th largest eigenvalue of a matrix

Given a large matrix $A$ with eigenvalues $\sigma_1\ge \sigma_2 \ge \dotsc $, I want to determine only a subset of these values, say $\sigma_5,\sigma_8$ and $\sigma_{19}$. Is there an algorithm that ...
user avatar
  • 183
8 votes
2 answers
4k views

Solving a generalised eigenvalue problem

I have a generalized eigenvalue problem in the standard form $\lambda \mathbf{B} \mathbf{x} = \mathbf{A} \mathbf{x} $, resulting from a finite difference discretization of a coupled system of two ...
user avatar
  • 241
8 votes
1 answer
279 views

Compute eigenvectors of a matrix with known eigenvalue spectrum

If I have already accurately known the eigenvalue spectrum (i.e. all eigenvalues) of a matrix, is there any efficient numerical algorithm to compute all the eigenvectors corresponding to these ...
user avatar
8 votes
0 answers
385 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, ...
user avatar
  • 243
7 votes
3 answers
406 views

Is LAPACK behind the cutting edge of dense linear algebra?

I have been digging into some numerical linear algebra lately, and reading in particular about how LAPACK solves symmetric eigenvalue problems. I noticed that the ...
user avatar
  • 191
7 votes
3 answers
519 views

Does the Lanczos starting vector have to be random?

In all descriptions of the Lanczos vector, it's said that the starting vector is random. But let's say I'm only interested in the eigenvector associated with the lowest eigenvalue (as is the case ...
user avatar
  • 487
7 votes
3 answers
2k views

Largest negative eigenvalue

Is there an efficient way to find the largest negative eigenvalue of a matrix? The matrix in question is a Markov matrix. Computing the full spectrum of the matrix by decomposing it is not an ...
user avatar
7 votes
1 answer
854 views

Solving Coupled ODE eigenvalue problem

I've been trying to find some resources that would help me figure out how to numerically solve a coupled system of ODEs which is also an eigenvalue problem. The system is something like: $ \tag{1} \...
user avatar
  • 451
7 votes
2 answers
961 views

Can all eigenvalues of a Hermitian Toeplitz matrix be computed in $\tilde{O}(n)$ time?

I know there are "superfast" $O(n \log^p n)$ algorithms for solving Toeplitz linear systems. Is it possible to compute all eigenvalues of such a matrix with the same complexity?
user avatar
7 votes
1 answer
366 views

Eigenvalues of $ab^T$

In deriving a Newton scheme, I end up with a Jacobian matrix of the form $J=I+ab^T$ where $a,b$ are vectors. For practical reasons, I want to approximate it by a symmetric positive definite matrix. ...
user avatar
7 votes
1 answer
2k views

What is the state of the art algorithm for diagonalizing real symmetric matrices?

There are many methods for diagonalizing matrices, probably the most widely used is the combination of Householder transformations and the QR algorithm. Is there any superior method for diagonalizing ...
user avatar
  • 173
7 votes
2 answers
198 views

Left and right eigenspaces of the product of Gramians

I solve the Lyapunov equations : $$ A W_C E^T + E W_C A^T + B B^T = 0 $$ $$ A^T W_O E^T + E W_O A + C^T C = 0 $$ to obtain $ W_C $ and $W_O$. My aim is to get the left and right eigenspaces of $W_C ...
user avatar
  • 607
7 votes
0 answers
98 views

Can we sparse solve a few eigenvalues specified by index range?

I need to solve a few eigenvalues of a large sparse matrix specified by their index range. These indices are according to the whole eigenspectrum sorted in algebraic (not absolute value) ascending ...
user avatar
7 votes
0 answers
187 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\...
user avatar
  • 71
6 votes
2 answers
888 views

Complex Eigenvalues using eig (Matlab)

I wanted to find and plot the eigenvalues of large (around $1000\times1000$) matrices. But discovered when using the eig function in matlab, it gives complex ...
user avatar
  • 61
6 votes
3 answers
835 views

Nonlinear eigenvalue problem - MATLAB code

I'm trying to solve a nonlinear eigenvalue problem in MATLAB, still without success. It's a problem about graphene plasmonics. The nonlinear eigenvalue problem is given below: \begin{equation} \frac{...
user avatar
  • 161
6 votes
1 answer
840 views

Cheap recalculation of eigenvalues and eigenvectors for a low-rank update of the matrix

Suppose I have a correlation matrix, $A$, and I already have the eigenvalues and eigenvectors of this matrix. For a given vector, $\mathbf{\mathit{v}}$, I want to calculate the eigenvalues and ...
user avatar
6 votes
2 answers
1k views

matlab eigs: wrong eigenvalues for tridiagonal matrix

I try to compute eigenvalues of the tridiagonal matrix coming from finite difference scheme. For small mesh size, eigs works well. But for large size it fails. Here is an example where eigs fails. Is ...
user avatar
  • 2,983
6 votes
1 answer
4k 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 ...
user avatar
  • 163
6 votes
2 answers
277 views

inertia count sparse matrix with dense low-rank perturbation

I would like to determine the number of negative eigenvalues (inertia count) of the $(N \times N)$ symmetric real matrix $K - \sigma M$, with $K$ a positive-definite sparse matrix and $M$ a positive-...
user avatar
  • 81
6 votes
1 answer
506 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 ...
user avatar
  • 243
6 votes
1 answer
438 views

roots of polynomials with small coefficients

I would like to compute the roots of a polynomial with exponentially small coefficients. $$ \sum_{n=0}^N a_n \frac{z^n}{\sqrt{n!}} \tag{$\ast$}$$ where $a_n$ are Normal random variables with mean $0$...
user avatar
6 votes
2 answers
424 views

What algorithms are known for computing exact eigenvalues for rational matrices?

Let $M$ be a matrix which has the following properties: 1) $M$ is Hermitian 2) $M$ has only rational entries 3) $M$ is known to have rational eigenvalues What algorithms are there for exactly ...
user avatar
  • 161
6 votes
2 answers
931 views

Computing smallest eigenvectors of a sparse matrix, having its inverse

I'm a bit confused by the vast amount of literature on solving eigenvalue problems. I have a sparse (large) matrix which I have already factored (by Cholesky or LDU). I would like to compute few ...
user avatar
  • 435
6 votes
1 answer
304 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 ...
user avatar
  • 4,400
6 votes
4 answers
2k views

Efficient eigen-decomposition of covariance matrix

I am looking for an C/C++/Python algorithm implementation that calculates eigenvalues and eigenvectors of a symmetric, positive semidefinite covariance matrix. A general-purpose eigen-decomposition ...
user avatar
  • 91
6 votes
2 answers
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/...
user avatar
6 votes
1 answer
850 views

Inverse iteration to find the null singular vector of a rank-deficient matrix

I have an $n \times n$ unsymmetric matrix $A$ that results from the discretization of an ill-posed Poisson problem, and thus is rank-deficient with null space of dimension one. I want to compute just ...
user avatar
6 votes
1 answer
505 views

Dirichlet boundary conditions in generalized eigenvalue problem

Let us consider a problem of the form $$(\mathcal{L} + k^2) u(\mathbf{x})=0\, ,\quad \forall \mathbf{x} \in \Omega$$ with Dirichlet boundary conditions $$u(\mathbf{x}) = 0, \quad \forall \mathbf{x} ...
user avatar
  • 7,902
6 votes
1 answer
703 views

Estimate extreme eigenvalues with CG

CG may be used to estimate the extremal eigenvalues of a SPD matrix (by computing eigenvalues of tridiagonal matrix associated with the Lanczos algorithm). After a few iterations the largest ...
user avatar
  • 435
6 votes
0 answers
386 views

Will penalty-augmented stiffness matrix cause numerical issues in eigenvalue analysis?

In the finite element method, we often construct the constraints of the system by adding penalty-function terms ( which often are many many magnitudes, up to $10^6$ order bigger than the largest ...
user avatar
  • 468

1
2 3 4 5 6