Geek Answers Handbook

Solving linear equations during reverse iteration

I use OpenCL to calculate eigenvectors of a matrix. AMD has an example of calculating eigenvalues, so I decided to use reverse iteration to get eigenvectors.

I followed the algorithm described above and I noticed that in order to solve step 4, I need to solve a system of linear equations (or calculate the inverse matrix).

Inverse iteration

What is the best way to do this on a GPU using OpenCL? Are there any examples / links I should study?

EDIT: Sorry, I should have mentioned that my matrix is ​​symmetric tridiagonal. From what I read, this can be important and possibly simplify the whole process.

+4
source share
2 answers

The fact that the matrix is ​​tridiagonal is VERY important - this reduces the complexity of the problem from O (N ^ 3) to O (N). You can probably get some acceleration due to the fact that it is also symmetrical, but it will not be so dramatic.

A method for solving a tridiagonal system is here: http://en.wikipedia.org/wiki/Tridiagonal_matrix_algorithm .

Also note that you do not need to store all elements of the N ^ 2 matrix, since almost all of them will be zeros. You just need one vector of length N (for the diagonal) and two lengths of N-1 for sub- and super-diagonals. And since your matrix is ​​symmetrical, the sub- and super-diagonals are the same.

Hope this is helpful ...

+3
source

I suggest using LU decomposition . Here is an example .

It is written in CUDA, but I think it is not so difficult to rewrite it in OpenCL.

+2
source

More articles:


All Articles