Параллельный алгоритм для собственной системы трехдиагональной матрицы

11

Я делаю диагонализацию Ланцоша большой разреженной матрицы (~ 2 миллиона элементов). Почти все шаги в алгоритме Ланцкоса выполняются параллельно на графическом процессоре, за исключением диагонализации матрицы Ланцоша для проверки сходимости. Для этого я использовал алгоритм TQLI из Numeric Recipes. Существуют ли методы нахождения собственной системы трехдиагональной матрицы, которые параллельны или легко распараллеливаемы? Существует ли параллельная версия TQLI?

linear-algebra algorithms eigensystem рампа
источник

Ответы:

4

Я предлагаю использовать такую ​​библиотеку, как SLEPc , которая включает в себя интерфейсы ко многим различным методам решения собственных систем последовательно или параллельно. Руководство пользователя содержит ссылки на несколько различных методов решения проблем с собственными значениями.

Джефф Оксберри
источник
Фактически, никакие существующие разреженные собственные решения не используют параллельную линейную алгебру для фактора Рэлея. Я написал такой eigensolver этим летом, но, к сожалению, это закрытый источник.
Джек Полсон
9

TQL не может быть распараллелен.

Стандартный параллельный алгоритм - это алгоритм Cuppen:

JJM Cuppen, метод «разделяй и властвуй» для симметричной трехдиагональной собственной проблемы, 1980 г.
http://www.springerlink.com/content/t21365q2gh702714/

смотрите также:

Ф. Тиссер, Параллельный алгоритм «разделяй и властвуй» для симметричной задачи на собственные значения на архитектурах распределенной памяти, 1999 г.
http://eprints.ma.man.ac.uk/981/01/covered/MIMS_ep2007_225.pdf

http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.75.4109&rep=rep1&type=pdf

http://www14.in.tum.de/konferenzen/Jass09/courses/2/Kleine_Albers_paper.pdf

Арнольд Ноймайер
источник
Ссылка на Арво очень печально сломана. :(
Джеффри Ирвинг
@ GeoffreyIrving: я заменил его рабочим, хотя он может быть не бесплатным для всех. И я добавил новую ссылку на статью Тиссера.
Арнольд Ноймайер,