在逆迭代中求解线性方程(Solving linear equations during inverse iteration)

在逆迭代中求解线性方程(Solving linear equations during inverse iteration)

我正在使用OpenCL来计算矩阵的特征向量。 AMD有一个特征值计算的例子 ，因此我决定使用逆迭代来获得特征向量。

我遵循这里描述的算法，我注意到为了解决步骤4，我需要求解一个线性方程组（或计算矩阵的逆矩阵）。

使用OpenCL在GPU上执行此操作的最佳方法是什么？ 有没有我应该研究的例子/参考？

---

编辑：对不起，我应该提到我的矩阵是对称的三对角线。 从我读过的内容来看，这可能很重要，也许可以简化整个过程

I am using OpenCL to calculate the eigenvectors of a matrix. AMD has an example of eigenvalue calculation so I decided to use inverse iteration to get the eigenvectors.

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

What is the best way to do this on a GPU using OpenCL? Are there any examples/references that I should look into?

---

EDIT: I'm sorry, I should have mentioned that my matrix is symmetric tridiagonal. From what I have been reading this could be important and maybe simplifies the whole process a lot

最满意答案

矩阵是三对角的这一事实非常重要 - 这将问题的复杂性从O（N ^ 3）降低到O（N）。 你也可以从它对称的事实中得到一些加速，但这不会那么戏剧化。

解决三对角系统的方法如下： http ： //en.wikipedia.org/wiki/Tridiagonal_matrix_algorithm 。

另请注意，您不需要存储矩阵的所有N ^ 2个元素，因为几乎所有元素都将为零。 你只需要一个长度为N的矢量（对角线）和两个长度为N-1的矢量用于子和超对角线。 由于您的矩阵是对称的，因此子和超对角线是相同的。

希望有帮助......

The fact that the matrix is tridiagonal is VERY important - that reduces the complexity of the problem from O(N^3) to O(N). You can probably get some speedup from the fact that it's symmetric too, but that won't be as dramatic.

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

Also note that you don't need to store all N^2 elements of the matrix, since almost all of them will be zeroes. You just need one vector of length N (for the diagonal) and two of length N-1 for the sub- and superdiagonals. And since your matrix is symmetric, the sub- and superdiagonals are the same.

Hope that's helpful...