+ Reply to Thread
Results 1 to 12 of 12

Thread: Eigenvector for large matrices

  1. #1
    Points: 3,104, Level: 34
    Level completed: 36%, Points required for next Level: 96

    Posts
    10
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Eigenvector for large matrices




    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

  2. #2
    R purist
    Points: 35,103, Level: 100
    Level completed: 0%, Points required for next Level: 0
    TheEcologist's Avatar
    Location
    United States
    Posts
    1,921
    Thanks
    303
    Thanked 607 Times in 341 Posts
    Quote Originally Posted by senorbum View Post
    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
    The true ideals of great philosophies always seem to get lost somewhere along the road..

  3. #3
    Points: 3,104, Level: 34
    Level completed: 36%, Points required for next Level: 96

    Posts
    10
    Thanks
    0
    Thanked 0 Times in 0 Posts
    Quote Originally Posted by TheEcologist View Post
    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.

  4. #4
    Points: 3,104, Level: 34
    Level completed: 36%, Points required for next Level: 96

    Posts
    10
    Thanks
    0
    Thanked 0 Times in 0 Posts
    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.

  5. #5
    R purist
    Points: 35,103, Level: 100
    Level completed: 0%, Points required for next Level: 0
    TheEcologist's Avatar
    Location
    United States
    Posts
    1,921
    Thanks
    303
    Thanked 607 Times in 341 Posts
    Quote Originally Posted by senorbum View Post
    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
    The true ideals of great philosophies always seem to get lost somewhere along the road..

  6. #6
    Points: 3,104, Level: 34
    Level completed: 36%, Points required for next Level: 96

    Posts
    10
    Thanks
    0
    Thanked 0 Times in 0 Posts
    Quote Originally Posted by TheEcologist View Post
    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

  7. #7
    R purist
    Points: 35,103, Level: 100
    Level completed: 0%, Points required for next Level: 0
    TheEcologist's Avatar
    Location
    United States
    Posts
    1,921
    Thanks
    303
    Thanked 607 Times in 341 Posts
    Quote Originally Posted by senorbum View Post
    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!
    The true ideals of great philosophies always seem to get lost somewhere along the road..

  8. #8
    Points: 3,104, Level: 34
    Level completed: 36%, Points required for next Level: 96

    Posts
    10
    Thanks
    0
    Thanked 0 Times in 0 Posts
    Quote Originally Posted by TheEcologist View Post
    Anytime and Goodluck!
    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.

  9. #9
    R purist
    Points: 35,103, Level: 100
    Level completed: 0%, Points required for next Level: 0
    TheEcologist's Avatar
    Location
    United States
    Posts
    1,921
    Thanks
    303
    Thanked 607 Times in 341 Posts
    Quote Originally Posted by senorbum View Post
    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.
    The true ideals of great philosophies always seem to get lost somewhere along the road..

  10. #10
    Points: 3,104, Level: 34
    Level completed: 36%, Points required for next Level: 96

    Posts
    10
    Thanks
    0
    Thanked 0 Times in 0 Posts
    Quote Originally Posted by TheEcologist View Post
    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)?

  11. #11
    R purist
    Points: 35,103, Level: 100
    Level completed: 0%, Points required for next Level: 0
    TheEcologist's Avatar
    Location
    United States
    Posts
    1,921
    Thanks
    303
    Thanked 607 Times in 341 Posts
    Quote Originally Posted by senorbum View Post
    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.
    The true ideals of great philosophies always seem to get lost somewhere along the road..

  12. #12
    Points: 3,104, Level: 34
    Level completed: 36%, Points required for next Level: 96

    Posts
    10
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Quote Originally Posted by TheEcologist View Post
    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.
    Last edited by senorbum; 07-01-2008 at 02:32 PM. Reason: Discovery

+ Reply to Thread

           




Similar Threads

  1. Log transforming distance matrices
    By alfredman in forum R
    Replies: 3
    Last Post: 03-14-2011, 10:47 AM
  2. eigenvector function
    By xixihaha in forum R
    Replies: 6
    Last Post: 02-26-2010, 05:37 AM
  3. T-Test: How large is large?
    By drekhan in forum Statistical Research
    Replies: 1
    Last Post: 12-18-2009, 03:14 AM
  4. Ill conditioned rectangular matrices
    By freebird2008 in forum General Discussion
    Replies: 0
    Last Post: 04-09-2009, 07:49 PM
  5. Categorical Variables in Correlation Matrices
    By KrystalLarson in forum Statistics
    Replies: 0
    Last Post: 05-22-2008, 04:41 PM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts






Advertise on Talk Stats