Direct Eigenvalue solver, which retains the the order of eigenvectors

In summary, the conversation is about finding a direct eigenvalue solver algorithm in Fortran to calculate a small matrix, and the issue of the ordering of eigenvalues and eigenvectors. Different resources and libraries are suggested, including LAPACK and EISPACK, and the use of MATLAB is questioned.
  • #1
alyflex
9
0
Hi guys
I have a problem that I need some help with, I am looking for a direct eigenvalue solver algorithm.

The problem is that all the eigenvalue solvers I can find seems to reorder the final matrix after the size of the eigenvalues.

The matrix it shall calculate is very small (5-10), so speed should not be an issue.

I am writing this in Fortran, and have the lapack library available, but thus far I have found no routine in it which can do what I need.
 
Physics news on Phys.org
  • #2
I don't think that there is a natural order to eigenvalues. As long as the eigenvalues and eigenvectors are provided in the same order, you can reconstruct the original matrix...

Can you give a simple example of what you want/expect to happen?
 
  • #3
What I'm actually doing:
I'm doing imaginary time propagation in density functional theory.
So after each iteration I have to othogonalize my orbitals, this is done by subspace othogonalization, in which I create the overlap matrix M_ij, to get the new orbitals I then solve the coresponding eigenvalue problem to this matrix.

A simple example of what I'm doing mathematically:
I get a matrix
A=[1 0 0;0 0.7 0.5; 0 0.5 0.8]
Now this tells me that the first orbital does not overlap with any of the two other orbitals.
However if I solve the eigenvalue problem, I get the following:
[V,D]=eig[A]
D=[0.065 0 0; 0 0.8; 0 0 1.545]
V=[0 1 0;0.7047 0 -0.7095;-0.7095 0 -0.7047]
Now when I look at it, it is clear that the one that does not mix is now the second orbital. But how do I in general make this relation? such that I can permute the columns back to their right place?

I hope that made it more clear
 
  • #4
Are you sure that example is correct?
The diagonal matrix of eigenvalues don't match what I calculate - see the Mathematica code below.
Maybe you just made a mistake copying the example?

In some matrix algorithms, you might also be returned information about pivoting. It could be that maybe the you are returned this data and didn't realize it. This could explain how rows (or columns) are changing places.

Note that pivoting won't affect the values of the eigenvalues - so does not account for for the difference in eigenvalues below...

Code:
[PLAIN]http://www.calerga.com/doc/LME_matr.htm#eig[/PLAIN] [Broken]
[PLAIN]http://www.calerga.com/doc/LME_lapk.htm#eig[/PLAIN] [Broken]

In[1]:= importMatrix[m_String] := ImportString[StringTrim[m, "["|"]"], 
          "Table", "FieldSeparators" -> {" "}, "LineSeparators" -> {";"}]

In[2]:= a = importMatrix["[1 0 0;0 0.7 0.5; 0 0.5 0.8]"]

Out[2]= {{1, 0, 0}, {0, 0.7, 0.5}, {0, 0.5, 0.8}}

In[3]:= d = importMatrix["[0.065 0 0; 0 0.8 0; 0 0 1.545]"]
        v = importMatrix["[0 1 0;0.7047 0 -0.7095;-0.7095 0 -0.7047]"]

Out[3]= {{0.065, 0, 0}, {0, 0.8, 0}, {0, 0, 1.545}}

Out[4]= {{0, 1, 0}, {0.7047, 0, -0.7095}, {-0.7095, 0, -0.7047}}

In[5]:= a.Transpose[v]
        Transpose[v].d

Out[5]= {{0., 0.7047, -0.7095}, {0.7, -0.35475, -0.35235}, {0.5, -0.5676, -0.56376}}

Out[6]= {{0., 0.56376, -1.09618}, {0.065, 0., 0.}, {0., -0.5676, -1.08876}}

In[7]:= {val, vec} = Eigensystem[a]

Out[7]= {{1.25249, 1., 0.247506}, 
 {{0., 0.671005, 0.741453}, {1., 0., 0.}, {0., 0.741453, -0.671005}}}

In[8]:= a.Transpose[vec] == Transpose[vec].DiagonalMatrix[val]

Out[8]= True

In[9]:= Table[a.vec[[i]] == val[[i]] vec[[i]], {i, 3}]

Out[9]= {True, True, True}
 
Last edited by a moderator:
  • #5
I don't quite understand what you are asking here, but any algorithm that finds eigenvalues and vectors will return the eigenvectors (i.e. the columns of the matrix) in the same order as the eigenvalues. Otherwise, you wouldn't know which vector corresponds to which value!

If you want to permute them into a different order, when you interchange eigenvalues [itex]e_i[/itex] and [itex]e_j[/itex], just interchange columns i and j of the eigenvector matrix.
 
  • #6
alyflex said:
. . .

However if I solve the eigenvalue problem, I get the following:
[V,D]=eig[A]
D=[0.065 0 0; 0 0.8; 0 0 1.545]
V=[0 1 0;0.7047 0 -0.7095;-0.7095 0 -0.7047]

. . .

You seem to have access to MATLAB; why do you have to write a program in FORTRAN?

Are you sure you cannot find anything in the LAPACK libraries? They have just about everything there. And the eigensolvers usually print out eigenvectors in the same order as the eigenvalues.

Alternately, there is the http://www.netlib.org/eispack/" [Broken] library, which is older. But it still works. And I know for sure there is a routine there that prints out eigenvector1 for eigenvalue1, eigenvector2 for eigenvalue2, etc.

In fact, there is also an online solver that is a Javascript translation of an EISPACK routine that you may find useful (perhaps to compare results):

http://www.akiti.ca/EigR12Solver.html" [Broken]

(Keep in mind that some routines might normalize the eigenvectors; others may not.)

Hope this helps.
 
Last edited by a moderator:

1. What is a direct eigenvalue solver?

A direct eigenvalue solver is a numerical method used to calculate the eigenvalues and eigenvectors of a matrix. It is a direct method, which means it does not involve iterative calculations and instead directly computes the eigenvalues and eigenvectors.

2. How does a direct eigenvalue solver retain the order of eigenvectors?

A direct eigenvalue solver uses a specific ordering algorithm that ensures the eigenvectors are arranged in a specific order, typically from largest to smallest eigenvalues. This allows for easy identification of the most significant eigenvectors.

3. What are the advantages of using a direct eigenvalue solver?

A direct eigenvalue solver is typically faster and more accurate compared to iterative methods. It also allows for the calculation of all eigenvalues and eigenvectors, not just the dominant ones, making it useful for a wide range of applications.

4. Is a direct eigenvalue solver suitable for all types of matrices?

No, a direct eigenvalue solver is most suitable for symmetric, positive definite matrices. It may also be used for other types of matrices, but the results may not be as accurate.

5. Can a direct eigenvalue solver handle large matrices?

Yes, a direct eigenvalue solver can handle large matrices, but it may require a significant amount of computational resources and time. In some cases, it may be more efficient to use an iterative method for large matrices.

Similar threads

Replies
2
Views
1K
  • Linear and Abstract Algebra
Replies
1
Views
977
Replies
3
Views
2K
  • Linear and Abstract Algebra
Replies
3
Views
2K
  • Linear and Abstract Algebra
Replies
5
Views
4K
  • Linear and Abstract Algebra
Replies
16
Views
2K
  • Linear and Abstract Algebra
Replies
6
Views
9K
  • Linear and Abstract Algebra
Replies
7
Views
7K
  • Introductory Physics Homework Help
Replies
1
Views
661
  • Engineering and Comp Sci Homework Help
Replies
18
Views
2K
Back
Top