Testing a Lanczos (tridiagonalization) algorithm

[senorbum]

So I implemented a tridiagonalization algorithm, however I don't know if the result that I am receiving is accurate. Does anyone know of an easy way of testing this? I suppose it is possible to scour around for code, but it would be difficult to find matching code. So if anyone knows anything that could help me, that would be much appreciated!

Edit: One other question. If you tridiagonalize a matrix, then compute the Singular Value Decomposition, then re-compute the matrix with say 'k' singular values, isn't the resulting matrix going to also be tridiagonalized? In which case, how can you apply the SVD of a tridiagonal matrix back to the original matrix?

 

[vkroom]

what u can do is test the code for a smaller matrix of the same type. and if u r trying to find the extremal eigenvalue then u can do the following :

check for convergence of the extremal eigenvalue of ur tridiagonal matrix after it has grown by 10 dimensions, i.e. find the lowest/heighest eig val when ur tridiagonal matrix is 10 dim, then chk again when its 20 dim, then 30 dim, and so forth. once the value has reached a fixed point (it generally does so by 70-80 dim) u have ur extremal eigen value.
this saves a lot of resource, especially when u r generating the matrix with a lanczos.

 

[senorbum]

what u can do is test the code for a smaller matrix of the same type. and if u r trying to find the extremal eigenvalue then u can do the following :

check for convergence of the extremal eigenvalue of ur tridiagonal matrix after it has grown by 10 dimensions, i.e. find the lowest/heighest eig val when ur tridiagonal matrix is 10 dim, then chk again when its 20 dim, then 30 dim, and so forth. once the value has reached a fixed point (it generally does so by 70-80 dim) u have ur extremal eigen value.
this saves a lot of resource, especially when u r generating the matrix with a lanczos.

Thanks. I have been doing that recently. Is simple lanczos even good for more than the extremal eigenvalue? It seems that I'd have to reorthogonalize if I wanted more than one, but I'm not 100% sure. Basically I am wondering if it will preserve say the top x eigenvalues where x << matrix dimension (say like 20 in a 200x200 matrix). It seems like it may generate some spurious values, but I was wondering if you could confirm this.

 

[vkroom]

the lanczos vectors lose their orthonormality rapidly. so some kind of re-orthonormalization scheme is required. but thus far i didn't have any problem with the naive lanczos iterations.
You might want to consult the book "Matrix Computations" by Golub. Its pretty good.

the bottomline is that for practical and reliable calculations its better to use some ready made routine, rather than code one for urself. there are a few fine tuning required to produce a robust lanczos routine, and u mite want to use some readymade ones for the purpose.

one such is ARPACK. this one is coded in fortran. there's a c++ inrterface : ARPACK++


good luck

 

[senorbum]

the lanczos vectors lose their orthonormality rapidly. so some kind of re-orthonormalization scheme is required. but thus far i didn't have any problem with the naive lanczos iterations.
You might want to consult the book "Matrix Computations" by Golub. Its pretty good.

the bottomline is that for practical and reliable calculations its better to use some ready made routine, rather than code one for urself. there are a few fine tuning required to produce a robust lanczos routine, and u mite want to use some readymade ones for the purpose.

one such is ARPACK. this one is coded in fortran. there's a c++ inrterface : ARPACK++


good luck

Well, my portion of this project is done, but thanks for the response. I used a naive version of Lanczos, but will need somebody who has a better understanding of linear algebra to implement a reorthogonalization technique. The reason I couldn't use a pre-written routine is because I was coding it using CUDA, which is NVidia's GPU programming language. If I had more time I might have been able to figure out how ARPACK has theirs coded and replicate it, but my time is up within a week and a half, so I have more pressing issues to attend to (The project is for a summer internship, hence the random cutoff time).

Anyways, thanks again for the response.

 

[mfarooq52003]

I will be grateful if some one can help me in explaining the idea of breakdown in Lanczos algorithm and what is the difference between the breakdown and stoping criteria of lanczos algorithms. I will appreciate if some one can send me the codes of lanczos algorithm which they have tested on some problems of linear system of equation. Any one who knows the linear systems where this lanczos algorithm fails. Sorry to ask so many questions but I am really in hot water and I need the answeres of all these questions. I hope you people will help me out of this situations.

 

[Cantab Morgan]

Test it against LINPACK, or LAPACK, or some similar package. I bet they have an implementation in there. I haven't heard of ARPACK before, but I suspect it's similar.

 

[mfarooq52003]

Thank you very much for your response. Can you explain the following, I mean the theoretical aspects only please,,"The idea of breakdown in Lanczos algorithm and what is the difference between the breakdown and stoping criteria of lanczos algorithms".

Any one who can explain it please?

With Best Regards

Farooq

 

[mfarooq52003]

Any one who has implemented Lanczos algorithms for solving linear system of equation. I will appreciate if anyone has done it in Matlab and can send it to me please.

Regards