Решение линейных уравнений во время обратной итерации

Question

Я использую OpenCL для вычисления собственных векторов матрицы. У AMD есть пример вычисления собственных значений, поэтому я решил использовать обратную итерацию для получения собственных векторов.

Я следовал описанному алгоритму здесь и заметил, что для решения шага 4 мне нужно решить систему линейных уравнений (или вычислить обратную матрицу).

Каков наилучший способ сделать это на графическом процессоре с использованием OpenCL? Есть ли примеры / ссылки, на которые я должен обратить внимание?

---

РЕДАКТИРОВАТЬ: Извините, я должен был упомянуть, что моя матрица является симметричной трехугольной. Из того, что я читал, это может быть важно и, возможно, значительно упростит весь процесс

Answer 1

ОЧЕНЬ важен тот факт, что матрица является трехдиагональной - это снижает сложность задачи с O (N ^ 3) до O (N). Вероятно, вы можете получить некоторое ускорение от того факта, что он тоже симметричен, но это будет не так драматично.

Метод решения трехдиагональной системы здесь: http://en.wikipedia.org/wiki/Tridiagonal_matrix_algorithm.

Также обратите внимание, что вам не нужно хранить все N ^ 2 элементов матрицы, так как почти все они будут равны нулю. Вам просто нужен один вектор длины N (для диагонали) и два вектора длины N-1 для суб- и супердиагоналей. А поскольку ваша матрица симметрична, суб- и супердиагонали одинаковы.

Надеюсь, это полезно ...

Answer 2

Я предлагаю использовать LU-разложение . Вот пример .

Он написан на CUDA, но, думаю, его не так сложно переписать в OpenCL.