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.
1
vote
0answers
26 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 ...
4
votes
1answer
99 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}$$
...
1
vote
1answer
60 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:
...
5
votes
3answers
137 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 ...
8
votes
0answers
71 views
Specialized methods for 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 ...
3
votes
1answer
82 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 ...
4
votes
1answer
116 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
178 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
124 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.
...
1
vote
2answers
201 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:
where:
pT is a probability distribution ...
2
votes
2answers
146 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
265 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
146 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}$ ...
5
votes
3answers
300 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, ...
8
votes
2answers
215 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
103 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 ...
5
votes
1answer
105 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
126 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
157 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
131 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
116 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.
...
8
votes
2answers
201 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
4answers
251 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 ...
12
votes
3answers
482 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 ...
4
votes
1answer
149 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 ...
5
votes
2answers
161 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 ...
7
votes
1answer
85 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
648 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?
6
votes
3answers
314 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
2answers
195 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 ...
7
votes
4answers
428 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 ...
1
vote
0answers
146 views
Perron-Frobenius theorem on general real symmetric matrices
From the Perron-Frobenius theorem,
http://en.wikipedia.org/wiki/Perron%E2%80%93Frobenius_theorem#Perron_root_is_strictly_maximal_eigenvalue_for_positive_.28and_primitive.29_matrices
it might be ...
5
votes
2answers
146 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
152 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
3answers
260 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
3answers
1k 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 ...
5
votes
2answers
197 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 ...
7
votes
3answers
234 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 ...
2
votes
1answer
157 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 ...
3
votes
0answers
65 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 ...
13
votes
5answers
2k 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 eigen() ...
4
votes
2answers
473 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
177 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 ...
6
votes
1answer
213 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 ...
9
votes
2answers
295 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 ...
6
votes
3answers
419 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 ...
2
votes
2answers
619 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 ...
5
votes
1answer
332 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 ...
5
votes
1answer
121 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 ...
