Eigenvector for large matrices

[senorbum]

Well, this is kind of a linear algebra question, but is used very often in statistics, so it seems applicable for this forum.

My question is, does anyone have any resources for computing the eigenvectors of large matrices given the eigenvalues? It seems pretty straightforward for small (2x2, 3x3) matrices, but I need to be able to compute it for very large matrices. I'm just looking for somewhere to get started. Most sites that I have seen just discuss how to calculate the small matrix version and then say it is possible to do for large matrices, but you have to resort to a numerical approach(which is fine, but I can't find a lot of information on numerical approaches, other than the power method which only yields the dominant vector).

Thanks in advance

Joe

 

[TheEcologist]

Well, this is kind of a linear algebra question, but is used very often in statistics, so it seems applicable for this forum.

My question is, does anyone have any resources for computing the eigenvectors of large matrices given the eigenvalues? It seems pretty straightforward for small (2x2, 3x3) matrices, but I need to be able to compute it for very large matrices. I'm just looking for somewhere to get started. Most sites that I have seen just discuss how to calculate the small matrix version and then say it is possible to do for large matrices, but you have to resort to a numerical approach(which is fine, but I can't find a lot of information on numerical approaches, other than the power method which only yields the dominant vector).

Thanks in advance

Joe

Computation by "hand" gets exaustive quickly and I mean very quickly(unless your matrix contains mostly zero's), so if we're talking large matrices I'm assuming you want a computer program to do this?

Use Matlab,

Or even better Octave (the free Matlab). R (also free) can compute these too.

Otherwise a free online book:

http://ceee.rice.edu/Books/LA/index.html

 

[senorbum]

Computation by "hand" gets exaustive quickly and I mean very quickly(unless your matrix contains mostly zero's), so if we're talking large matrices I'm assuming you want a computer program to do this?

Use Matlab,

Or even better Octave (the free Matlab). R (also free) can compute these too.

Otherwise a free online book:

http://ceee.rice.edu/Books/LA/index.html

I'm developing a computer program to do this, so I effectively need to know how to do it. Actually, I just need the ability to calculate the determinant of a tridiagonal symmetric matrix, which should be significantly easier, I just can't find too much on it.

 

[senorbum]

Ok, so for a tridiagonal matrix, I have found a recursive algorithm from wikipedia.org as seen here http://en.wikipedia.org/wiki/Tridiagonal_matrix

Can anyone explain what ann represents? Does that represent A at position n,n? Also, one quick question about determinants. Is the determinant of a 1x1 matrix the same as the value of that one term? This is important because that is what the stop case for this algorithm would be.

 

[TheEcologist]

Ok, so for a tridiagonal matrix, I have found a recursive algorithm from wikipedia.org as seen here http://en.wikipedia.org/wiki/Tridiagonal_matrix

Can anyone explain what ann represents? Does that represent A at position n,n? Also, one quick question about determinants. Is the determinant of a 1x1 matrix the same as the value of that one term? This is important because that is what the stop case for this algorithm would be.

If you want efficient algorithms to do this look in the source code of a open-source program like R (or one you are familiar with).

A n,n would mean position n,n of matrix A

And the det of a 1x1 matrix would be the single matrix element. It helps to think of determents in the geometric sense:

http://en.wikipedia.org/wiki/Determinant

 

[senorbum]

If you want efficient algorithms to do this look in the source code of a open-source program like R (or one you are familiar with).

A n,n would mean position n,n of matrix A

And the det of a 1x1 matrix would be the single matrix element. It helps to think of determents in the geometric sense:

http://en.wikipedia.org/wiki/Determinant

Thank you for the response. I was thinking of looking for source code of MATLAB then realized it wasn't open source. I have used R before, it's just been a while so hopefully I can understand it enough .

I kinda thought that ann was A at n,n but wasn't entirely sure and didn't want to develop a program based on faulty math and then have to go back and change it.

Your response has been very helpful.

Joe

 

[TheEcologist]

Thank you for the response. I was thinking of looking for source code of MATLAB then realized it wasn't open source. I have used R before, it's just been a while so hopefully I can understand it enough .

I kinda thought that ann was A at n,n but wasn't entirely sure and didn't want to develop a program based on faulty math and then have to go back and change it.

Your response has been very helpful.

Joe

Anytime and Goodluck! :tup:

 

[senorbum]

Anytime and Goodluck! :tup:

So the real question is, what is the most efficient/effective way to calculate eigenvectors given the eigenvalues? Is the Jacobi algorithm plausable for 1000x1000 to 10000x10000+ matrices? I haven't seen direct calculation times for comparisons in any of the papers I've read.

 

[TheEcologist]

So the real question is, what is the most efficient/effective way to calculate eigenvectors given the eigenvalues? Is the Jacobi algorithm plausable for 1000x1000 to 10000x10000+ matrices? I haven't seen direct calculation times for comparisons in any of the papers I've read.

That probably because calculation times vary from system to system, so it's difficult to compare calculation times.

I usually build a code that requests and saves the system-time at start and end of a calculation. You can then check which function/algoritm is more efficient for your system.

 

[senorbum]

That probably because calculation times vary from system to system, so it's difficult to compare calculation times.

I usually build a code that requests and saves the system-time at start and end of a calculation. You can then check which function/algoritm is more efficient for your system.

Well, I don't want to implement a naturally poor algorithm. Generally there is a computational intensity level for these (i.e. O(n), O(n * log n) etc.). Is the QR algorithm the most widely used for eigenvector calculation (or EVD)?

 

[TheEcologist]

Well, I don't want to implement a naturally poor algorithm. Generally there is a computational intensity level for these (i.e. O(n), O(n * log n) etc.). Is the QR algorithm the most widely used for eigenvector calculation (or EVD)?

Not quite sure, never worked on it myself.

Why dont you try (it might be useful):

Smith, B. T, Boyle, J. M., Dongarra, J. J., Garbow, B. S., Ikebe,Y., Klema, V., and Moler, C. B. (1976). Matrix Eigensystems Routines – EISPACK Guide. Springer-Verlag Lecture Notes in Computer Science.

and maybe:

Wilkinson, J. H. (1965) The Algebraic Eigenvalue Problem. Clarendon Press, Oxford.

 

[senorbum]

Not quite sure, never worked on it myself.

Why dont you try (it might be useful):

Smith, B. T, Boyle, J. M., Dongarra, J. J., Garbow, B. S., Ikebe,Y., Klema, V., and Moler, C. B. (1976). Matrix Eigensystems Routines – EISPACK Guide. Springer-Verlag Lecture Notes in Computer Science.

and maybe:

Wilkinson, J. H. (1965) The Algebraic Eigenvalue Problem. Clarendon Press, Oxford.

Am I overcomplicating this? If I already have the eigenvalues and (A-lamba*I)*v = 0 where A is the matrix, I is identity matrix, v = vector to solve for, is there a BLAS function that is equipped to solve this kind of problem? I feel like there might be, but haven't used to blas libraries enough to know. I'll research in the meantime to see if I can find one, but if anyone knows off the top of their head I'd much appreciate it.

Edit: Is the STBSV what I'm looking for here? "stbsv solves one of the systems of equations A*x = b, or A'*x = b, where b and x are n element vectors and A is an n by n unit, or non-unit, upper or lower triangular band matrix, with ( k + 1 ) diagonals.
No test for singularity or near-singularity is included in this routine. Such tests must be performed before calling this routine. "

So if b = 0 at all points in the vector, wouldn't that technically work? The question becomes, is it just going to set each element in the result vector to 0. If not, it appears to be what I'm looking for.