Standard algorithm for symmetric tridiagonal matrix eigendecomposition?
up vote
3
down vote
favorite
Hi I am trying to generate an arbitrary Gauss quadrature rule by using the Golub-Welsh algorithm.
I need to code this on C++ for my personal project. This algorithm involves the eigendecomposition of a matrix in which the only non-zero elements are the subdiagonal and superdiagonal. Here, $n$ could go up to $512$.
To illustrate in Matlab code:
n = 16;
beta = .5./sqrt(1-(2*(1:n-1)).-2);
T = diag(beta,1) + diag(beta,-1);
[V,D] = eig(T);
I want to implement the eigenvalue decomposition in C++ and not use Matlab routines for this since I want to parallelize it. What is the best way to find the eigendecomposition of this type of matrix?
Is bisection method acceptable for my use case? How about divide and conquer or QR method or Lanczos?
(I was more inclined towards Lanczos since it seems that it is sparse friendly.)
linear-algebra numerical-methods eigenvalues-eigenvectors numerical-linear-algebra programming
edited Nov 24 at 5:46
Rócherz
2,6612721
asked Apr 4 '14 at 19:13
aatish
1162
add a comment |
up vote
3
down vote
favorite
Hi I am trying to generate an arbitrary Gauss quadrature rule by using the Golub-Welsh algorithm.
I need to code this on C++ for my personal project. This algorithm involves the eigendecomposition of a matrix in which the only non-zero elements are the subdiagonal and superdiagonal. Here, $n$ could go up to $512$.
To illustrate in Matlab code:
n = 16;
beta = .5./sqrt(1-(2*(1:n-1)).-2);
T = diag(beta,1) + diag(beta,-1);
[V,D] = eig(T);
I want to implement the eigenvalue decomposition in C++ and not use Matlab routines for this since I want to parallelize it. What is the best way to find the eigendecomposition of this type of matrix?
Is bisection method acceptable for my use case? How about divide and conquer or QR method or Lanczos?
(I was more inclined towards Lanczos since it seems that it is sparse friendly.)
linear-algebra numerical-methods eigenvalues-eigenvectors numerical-linear-algebra programming
edited Nov 24 at 5:46
Rócherz
2,6612721
asked Apr 4 '14 at 19:13
aatish
1162
1
1) Using Lanczos does not make sense since your matrix is already tridiagonal. 2) You can use a convenient routine from LAPACK, there are a few for eigenvalues of tridiagonal matrices.
– Algebraic Pavel
Apr 5 '14 at 3:02
I came across MRRR technique which is a recently developed algorithm meant for tridiagonal matrices. Apparently, it has the best time complexity for eigenvalue calculation. I am trying to grasp the material by reading Dhillon's paper.
– aatish
Apr 5 '14 at 22:35
add a comment |
up vote
3
down vote
favorite
up vote
3
down vote
favorite
Hi I am trying to generate an arbitrary Gauss quadrature rule by using the Golub-Welsh algorithm.
I need to code this on C++ for my personal project. This algorithm involves the eigendecomposition of a matrix in which the only non-zero elements are the subdiagonal and superdiagonal. Here, $n$ could go up to $512$.
To illustrate in Matlab code:
n = 16;
beta = .5./sqrt(1-(2*(1:n-1)).-2);
T = diag(beta,1) + diag(beta,-1);
[V,D] = eig(T);
I want to implement the eigenvalue decomposition in C++ and not use Matlab routines for this since I want to parallelize it. What is the best way to find the eigendecomposition of this type of matrix?
Is bisection method acceptable for my use case? How about divide and conquer or QR method or Lanczos?
(I was more inclined towards Lanczos since it seems that it is sparse friendly.)
linear-algebra numerical-methods eigenvalues-eigenvectors numerical-linear-algebra programming
edited Nov 24 at 5:46
Rócherz
2,6612721
asked Apr 4 '14 at 19:13
aatish
1162
Hi I am trying to generate an arbitrary Gauss quadrature rule by using the Golub-Welsh algorithm.
I need to code this on C++ for my personal project. This algorithm involves the eigendecomposition of a matrix in which the only non-zero elements are the subdiagonal and superdiagonal. Here, $n$ could go up to $512$.
To illustrate in Matlab code:
n = 16;
beta = .5./sqrt(1-(2*(1:n-1)).-2);
T = diag(beta,1) + diag(beta,-1);
[V,D] = eig(T);
I want to implement the eigenvalue decomposition in C++ and not use Matlab routines for this since I want to parallelize it. What is the best way to find the eigendecomposition of this type of matrix?
Is bisection method acceptable for my use case? How about divide and conquer or QR method or Lanczos?
(I was more inclined towards Lanczos since it seems that it is sparse friendly.)
linear-algebra numerical-methods eigenvalues-eigenvectors numerical-linear-algebra programming
linear-algebra numerical-methods eigenvalues-eigenvectors numerical-linear-algebra programming
edited Nov 24 at 5:46
Rócherz
2,6612721
asked Apr 4 '14 at 19:13
aatish
1162
edited Nov 24 at 5:46
Rócherz
2,6612721
asked Apr 4 '14 at 19:13
aatish
1162
edited Nov 24 at 5:46
Rócherz
2,6612721
edited Nov 24 at 5:46
Rócherz
2,6612721
edited Nov 24 at 5:46
Rócherz
2,6612721
2,6612721
asked Apr 4 '14 at 19:13
aatish
1162
asked Apr 4 '14 at 19:13
aatish
1162
asked Apr 4 '14 at 19:13
aatish
1162
1162
1
1) Using Lanczos does not make sense since your matrix is already tridiagonal. 2) You can use a convenient routine from LAPACK, there are a few for eigenvalues of tridiagonal matrices.
– Algebraic Pavel
Apr 5 '14 at 3:02
I came across MRRR technique which is a recently developed algorithm meant for tridiagonal matrices. Apparently, it has the best time complexity for eigenvalue calculation. I am trying to grasp the material by reading Dhillon's paper.
– aatish
Apr 5 '14 at 22:35
add a comment |
1
1) Using Lanczos does not make sense since your matrix is already tridiagonal. 2) You can use a convenient routine from LAPACK, there are a few for eigenvalues of tridiagonal matrices.
– Algebraic Pavel
Apr 5 '14 at 3:02
I came across MRRR technique which is a recently developed algorithm meant for tridiagonal matrices. Apparently, it has the best time complexity for eigenvalue calculation. I am trying to grasp the material by reading Dhillon's paper.
– aatish
Apr 5 '14 at 22:35
1
1
1) Using Lanczos does not make sense since your matrix is already tridiagonal. 2) You can use a convenient routine from LAPACK, there are a few for eigenvalues of tridiagonal matrices.
– Algebraic Pavel
Apr 5 '14 at 3:02
1) Using Lanczos does not make sense since your matrix is already tridiagonal. 2) You can use a convenient routine from LAPACK, there are a few for eigenvalues of tridiagonal matrices.
– Algebraic Pavel
Apr 5 '14 at 3:02
I came across MRRR technique which is a recently developed algorithm meant for tridiagonal matrices. Apparently, it has the best time complexity for eigenvalue calculation. I am trying to grasp the material by reading Dhillon's paper.
– aatish
Apr 5 '14 at 22:35
I came across MRRR technique which is a recently developed algorithm meant for tridiagonal matrices. Apparently, it has the best time complexity for eigenvalue calculation. I am trying to grasp the material by reading Dhillon's paper.
– aatish
Apr 5 '14 at 22:35
add a comment |
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f739917%2fstandard-algorithm-for-symmetric-tridiagonal-matrix-eigendecomposition%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
1
1) Using Lanczos does not make sense since your matrix is already tridiagonal. 2) You can use a convenient routine from LAPACK, there are a few for eigenvalues of tridiagonal matrices.
– Algebraic Pavel
Apr 5 '14 at 3:02
I came across MRRR technique which is a recently developed algorithm meant for tridiagonal matrices. Apparently, it has the best time complexity for eigenvalue calculation. I am trying to grasp the material by reading Dhillon's paper.
– aatish
Apr 5 '14 at 22:35