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

kataich

Собственно требуется решить систему линейный уравнений
с трехдиагональной матрицей. Матрица хранится не равномерно,
то есть, если например, диагональ матрицы представить как массив,
то каждый процесс хранит кусок этого массива, но априори, длины этих
кусков не известны (память распределенная). Прошу просветить по поводу
следующих двух вопросов:
- какое ускорение ожидать от существующих алгоритмов?
- можете ли привести ссылку на статью, где алгоритм описывается?

Helga87

Каков порядок размера матрицы?

kataich

300-3000

Helga87

эээммм
так если меньше миллиарда, то зачем распределенный алгоритм?
я ведь правильно помню, что трехдиагональная матрица обращается за линейное время?

kataich

я ведь правильно помню, что трехдиагональная матрица обращается за линейное время?

Точно.

эээммм
так если меньше миллиарда, то зачем распределенный алгоритм?

1. Хотелось посмотреть на асимптотику, если это где-то есть.
2. Лучше я по-другому сформулирую задачу, которую хочется решить
Есть примерно следующий код



FOR (i = 0; i < N; i++)

   FOR (j = 0; j < N; j++)

     FOR (k = 0; k < N; k ++)

       /*

        * Matrix NxN is constructed here

        */

        MATRIX[k] = FUNCTION(i,j,k);

        SOLVE_SYSTEM(MATRIX, RIGHT_HAND(i,j,k;

     ENDFOR

   ENDFOR

ENDFOR

где MATRIX[k] - условно обозначает три элемента (под/над диагональю и саму диагональ)
* На данном этапе я не могу распараллелить цикл по i - будем считать это как данность.
* Я могу распараллелить цикл по j.
* Теперь думаю, что сделать с циклом по K + SOLVE_MATRIX
Если ничего не делать, то O(N^3) получается.

kataich

Самый банальный способ, который мне приходит на ум - это разбивая область (j=1,N,k=1,N) на прямоугольнички, считать матрицы параллельно (N матриц по количеству j а потом передавать их тем процессам, которые хранят k=1 к примеру, они и будут решать системы.
Но я не очень хорошо ориентируюсь в алгоритмах, поэтому буду рад, если кто-нибудь подкинет идейку

Оставить комментарий