2
votes
1answer
25 views

Parallelism in Golub & van Loan's Jacobi algorithm for symmetric eigenvalue problems

In Matrix Computations by Golub and Van Loan (3rd edition, page 433) an algorithm is given for a parallel version of the classical Jacobi algorithm for solving a real symmetric eigenvalue problem. The ...
0
votes
1answer
27 views

Numerically find all zeros of multivariate function

How do I find all zeros of a multivariate function , i.e. f(x1,x2,x2,...xn)=0 numerically? I don't know exact analytic form of f , but can numerically compute f at every point on its domain. ...
2
votes
1answer
55 views

Derivation of power method

POWER METHOD Let $x_0$ be an initial approximation to the eigenvector. For $k=1,2,3,\ldots$ do Compute $x_k=Ax_{k-1}$, Normalize $x_k=x_k/\|x_k\|_\infty$. Then $\|x_k\|_\infty$ approaches the ...
0
votes
2answers
63 views

Determinant Formula for Tri-Diagonal Matrix

for an assignment in numerical analysis, I need to find the eigenvalues of a matrix with values only in the diagonal, upper diagonal and lower diagonal. I guess there is an easy formula for this sort ...
0
votes
0answers
41 views

Complexity of the power method

I'd like to find out what the complexity of the power method is depending on the size of the matrix $A \in \mathbb{R}^{n\times n}$ given that the algorithm runs until a certain stop criterion. I.e. ...
1
vote
0answers
31 views

Numerical Computation for K smallest eigenvalues of a large Real Symmetric Matrix with restricted methods

I'm writing some code on a distributed platform, using some programming language like Hadoop, and now I need to calculate the K smallest eigenvalues for a Large Matrix. K is a small constant at most ...
3
votes
2answers
67 views

Power iteration

If $A$ is a matrix you can calculate its largest eigenvalue $\lambda_1$. What are the exact conditions under which the power iteration converges? Power iteration Especially, I often see that we ...
1
vote
0answers
31 views

Influence of preconditioning on degenerate eigenvectors

I'm using a hierarchical decomposition of a sparse matrix $A$ as suggested here. I find that the method essentially finds eigenvectors using the QR algorithm. $A$ has some eigenvalues with ...
0
votes
1answer
78 views

How to compute the eigenvalue condition number of a matrix

How to compute the eigenvalue condition number, $\kappa(4,A)$, of a matrix $A$ $$A = \begin{bmatrix} 4 & 0 \\ 1000 & 2\end{bmatrix}$$ I am a bit stuck on how to proceed solving this problem ...
1
vote
0answers
54 views

Numerical algorithm to solve quadratic eigenvalue problem.

Given the equation $$-4 \left(a^2+a (n-1) (2 t^2-1)\right) \left(\sum _{i=0}^n \alpha_i t^{2 i}\right)^2 \\ +\frac12 \left(\sum _{i=0}^n \alpha_i t^{2 i}\right) \left(t \left(8 a (t^2-1)+1\right) \sum ...
1
vote
2answers
54 views

Euler method application: step size

Suppose we have a system of ODE's: $a' = -a - 2b$ and $b' = 2a-b$ with initial conditions $a(0)=1$ and $b(0)=-1$. How can we find the maximum value of the step size such that the norm a solution of ...
7
votes
1answer
187 views

Fast algorithm for approximating Eigenvalue distribution of large sparse matrix

I am interested in the eigenvalue distribution of a huge $2^{16}$x$2^{16}$ Hermitian sparse matrix with spectrum contained in $[-1,1]$. That is I don't need to know all eigenvalues exactly, but rather ...
0
votes
0answers
51 views

Francis Algorithm (Implicit QR Algorithm)

In Numerical Analysis, we are touching upon QR and Francis Algorithm. I understand that for Francis's Algorithm, we reduce the matrix to its upper Hessenberg form using Householder transform. What I ...
2
votes
1answer
48 views

how to find the distinct eigenvectors from a repeated eigenvalue

As the title, how to find the distinct eigenvectors of an certain eigenvalue if the algebraic multiplicity of that eigenvalue is not 1? The target matrix is real and symmetric. I know these ...
0
votes
1answer
97 views

Power method for finding all eigenvectors

This is my homework. I was asked to find all eigenvectors of a symmetric and positive definite matrix by inverse power method with shifted. I encountered three problems: The eigenvalues to the ...
0
votes
0answers
18 views

Stieltjes transformation of e.d.f. sample eigenvalues

If the eigen-decomposition of sample covariance matrix is $S=PDP'$ where $D$ is a diagonal matrix with eigen value of $S$ and $P$ are eigenvectors. If we define the empirical distribution function of ...
0
votes
1answer
53 views

Finding Eigenvalues with Gershgorin-Discs

$A=\begin{pmatrix}-5 & 0 & 0 \\ 2 & 2 & 1 \\ 3 & -5 & 4\end{pmatrix}$ Find the Gerschgorin-discs, where the eigenvalues of $A$ lie. According to the formula if we ...
2
votes
0answers
128 views

Standard symmetric tridiagonal matrix Eigenvalue decomposition algorithm?

Hi I am trying to generate an arbitrary Gauss quadrature rule by using the Golub-Welsh algorithm (here). I need to code this on C++ for my personal project. This algorithm involves the eigenvalue ...
2
votes
1answer
212 views

Quick way of finding the eigenvalues and eigenvectors of the matrix $A=\operatorname{tridiag}_n(-1,\alpha,-1)$

Matrix $A=\operatorname{tridiag}_n(-1,\alpha,-1)$ has the eigenvalue: $\lambda_i=\alpha-2\cos(i\theta),$ $i=1,\dots,n$ and the corresponding eigenvectors are: ...
2
votes
2answers
212 views

Power iteration sign of eigenvalue?

I need to write a program which computes all eigenvalues and corresponding eigenvectors. I'd like to use power iterations method (I know that it's not good but it's really necessary). my algorithm ...
2
votes
0answers
24 views

Does eigenvalue theory remain in numerical applications?

If I have a symmetric matrix $A \in \mathbb{Q}^{n \times n}$ in matlab, then in theory it is guaranteed that $A$ has a orthogonal basis of eigenvectors and real eigenvalues. Does this remain in ...
4
votes
4answers
339 views

How to find 2x2 matrix with non zero elements and repeated eigenvalues?

I need to find a 2x2 matrix with non zero elements that has eigenvalue = 1 repeated (double). How can i do that? Thanks!
0
votes
0answers
51 views

is 'chasing the bulge' in the implicit QR algorithm exactly the same as reducing a general matrix to hessenberg form?

When performing the implicit QR algorithm, there's a part where you 'chase the bulge' down the diagonal. While it may not necessarily be numerically or computation-time equivalent, is that ...
0
votes
1answer
113 views

How to show all eigenvalues are positive?

Could you help me to show that the following matrix has all its eigenvalues positive? $$H= \begin{bmatrix} \sum_{k=1}^ng_1(x_k)^2 & \sum_{k=1}^ng_1(x_k)g_2(x_k) & \cdots & ...
0
votes
1answer
134 views

Two Lagrange multipliers with one equation

I have an equation as below, $$Rw = \lambda_1R_aw + \lambda_2R_bw $$ where, $R$, $R_a$, and $R_b$ are positive definite at least semi-positive definite and Hermitian matrix. $\lambda_1$ and ...
4
votes
2answers
201 views

Math hack for solving system of equations

Is it a "standard" Math/Numerical-Analysis hack to add a relatively small number e.g. 1*10E-5 to the diagonal of a squared matrix to ensure LU Decomposition (or whichever decomposition algorithm is ...
4
votes
2answers
3k views

Power iteration smallest eigenvalue?

I need to write a program which computes the largest and the smallest (in terms of absolute value) eigenvalues using both Power Iteration and Inverse Iteration. I can find them using the Inverse ...
0
votes
1answer
358 views

Sturm-Liouville problem: eigenvalues

I have a Sturm-Liouville problem $$ y'' + \lambda^2 y = 0, \\ y'(0) + \alpha_1 y(0) = 0, \\ y'(L) + \alpha_2 y(L) = 0, $$ where $\alpha_1 \alpha_2 \neq 0$. I found that eigenvalues are ...
3
votes
1answer
104 views

Numerical Computation of Eigenvalues

I am trying to find the first few eigenvalues of an operator defined by the following PDE: $$ \begin{cases} -\Delta u +(1-\varphi)u=\lambda u, & \text{ on }\Omega = [0,1]^2 \\ u=0 & \text{ ...
2
votes
2answers
506 views

How to determine the N-smallest eigenvalues of a symmetric matrix using the Power Method?

I was assigned to make a program that finds the largest, the N-largest, the smallest and the N-smallest eigenvalues of a symmetric matrix, using the Power Method. So far, I've been able to succesfully ...
0
votes
1answer
65 views

variant eigenvector problem

I have the following problems when solving a linear equation. Let $A=(a_{i,j})_{n \times n}$ be a non-negative matrix with $a_{i,j} \in (0,1)$, and let $0<r<1$ be a scalar. Now we define a ...
5
votes
2answers
345 views

Is there a version of the Gershgorin circle theorem that is suitable for nearly triangular matricies?

The Gershgorin circle theorem, http://en.wikipedia.org/wiki/Gershgorin_circle_theorem, gives bounds on the eigenvalues of a square matrix, and works well for nearly diagonal matrices. For a ...
0
votes
3answers
400 views

program for eigenvalue calculation

I have a n x n matrix. I would like to (a) take successively higher powers of the matrix and then multiply by projection vectors until the resulting vectors differ by only a scalar factor. (b) ...
0
votes
3answers
606 views

Two linearly independent eigenvectors with eigenvalue zero

What is the only $2\times 2$ matrix that only has eigenvalue zero but does have two linearly independent eigenvectors? I know there is only one such matrix, but I'm not sure how to find it.
4
votes
1answer
130 views

Show the space spanned is an invariant subspace

Let $A$ be real and let $\lambda = \alpha + i \beta$ be a complex eigenvalue of $A$ with eigenvector $x + iy$, show that the space spanned by $x$ and $y$ is an invariant subspace of $A$. What I ...
8
votes
1answer
1k views

Using the Arnoldi Iteration to find the k largest eigenvalues of a matrix

I'm trying to obtain a general understanding of this algorithm which determines the k-largest eigenvalues of a matrix $A\in \mathbb{R}^{n\times n}$. How I see it: power iteration: take random ...
-1
votes
2answers
876 views

Library for Jacobi eigenvalue algorithm [closed]

I am looking for a C or C++ or fortran library that implements the Jacobi eigenvalue algorithm: http://en.wikipedia.org/wiki/Jacobi_eigenvalue_algorithm do you know if it is available?
1
vote
0answers
603 views

Shifted Power Method

Using the shifted power method I find the eigenvalue (of the matrix A) farthest from a number $\mu$ and the corresponding eigenvector . In the method I follow the below steps: I first compute the ...
2
votes
3answers
406 views

What is a robust and reliable way/library for eigenvalues of 3x3 matrices?

I use Eigen to compute the eigenvalues of symmetric matrices. The problem is, that sometimes the matrices not nice at all numerically. Because of this, I get NaN among the eigenvalues. I have tested ...
3
votes
1answer
358 views

Eigenvectors of a matrix reduced to tridiagonal

I am implementing an algorithm to calculate eigenvalues and eigenvectors of a symmetric matrix in a GPU. In order to calculate the eigenvalues I first reduced the matrix to the tridiagonal form using ...
3
votes
1answer
346 views

How do iterative methods applied to the companion matrix of a polynomial $p(\lambda)$ relate to $p$ itself?

A few days ago, I had a vague question in my mind about "matrix methods" for finding roots of a polynomial. Now I can ask at least a semi-precise question, thanks to the post How to calculate complex ...