Tagged Questions

4
votes
1answer
94 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
136 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
70 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
81 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
111 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
176 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, ...
1
vote
2answers
200 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 ...
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
145 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
299 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, ...
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$ ...
1
vote
2answers
115 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 ...
11
votes
3answers
479 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
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 ...
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}$ ...
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 ...
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
156 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 ...
12
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$, ...
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
294 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
2answers
617 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 ...