VPF::Параллельное нахождение обратной матрицы с MPI

Тофана

Дата 29.5.2014, 22:40 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 3
Регистрация: 29.5.2014

Репутация: нет
Всего: нет

Добрый вечер, помогите пожалуйста распараллелить алгоритм нахождения обратной матрицы с помощью MPI. К сожалению, в данной теме я плохо разбираюсь, поэтому распараллеливание не получается.

Код


int k = 0;

    double temp, temp1;
    double **E = new double *[N];
 
    for (int i = 0; i < N; i++)
        E[i] = new double [N];
 
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++){
            E[i][j] = 0.0;
            if (i == j)
                E[i][j] = 1.0;
        }
    
    for ( k = 0; k < N; k++){
        temp1 = A[k][k];
        
        for (int j = 0; j < N; j++){
            A[k][j] /= temp1;
            E[k][j] /= temp1;    
        }

        for (int i = k + 1; i < N; i++){
            temp = A[i][k];
            for (int j = 0; j < N; j++){
                A[i][j] -= A[k][j] * temp;
                E[i][j] -= E[k][j] * temp;
            }
        }
    }

    for (int k = N - 1; k > 0; k--){
        for (int i = k - 1; i >= 0; i--){
            temp = A[i][k];

            for (int j = 0; j < N; j++){
                A[i][j] -= A[k][j] * temp;
                E[i][j] -= E[k][j] * temp;
            }
        }
    }
 
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            A[i][j] = E[i][j];
 
    for (int i = 0; i < N; i++)
        delete [] E[i];
 
    delete [] E;

maxim1000

Дата 30.5.2014, 08:09 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Участник
Сообщений: 3334
Регистрация: 11.1.2003
Где: Киев

Репутация: 33
Всего: 110

а вопрос о том какие части и на какие кусочки распараллелить или о конкретной технологии?

--------------------

qqq

Тофана

Дата 30.5.2014, 08:15 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 3
Регистрация: 29.5.2014

Репутация: нет
Всего: нет

maxim1000, скорее, как именно распараллеливать данный алгоритм. По идее, тут можно распараллелить разве что вот это:

Код


for (int i = k + 1; i < N; i++){
            temp = A[i][k];
            for (int j = 0; j < N; j++){
                A[i][j] -= A[k][j] * temp;
                E[i][j] -= E[k][j] * temp;
            }
        }
    }
    for (int k = N - 1; k > 0; k--){
        for (int i = k - 1; i >= 0; i--){
            temp = A[i][k];
            for (int j = 0; j < N; j++){
                A[i][j] -= A[k][j] * temp;
                E[i][j] -= E[k][j] * temp;
            }
        }
    }

Но вот как это описывается с помощью MPI, я, к сожалению, не знаю.

Mirkes

Дата 30.5.2014, 10:58 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 586
Регистрация: 18.8.2011
Где: Красноярск

Репутация: 4
Всего: 17

Дело сильно зависит от того, каким методом ищется обратная матрица и какова ее размерность. Если употребляются методы типа Гаусса, то распараллелить почти ничего невозможно, кроме вычитания приведенной строки из всех остальных строк. Это даст положительный эффект только для достаточно больших матриц. Впрочем для очень больших и не разреженных матриц можно поступить просто - на каждом процессоре держать определенный кусок всех строк. Тогда распараллеливание может получиться эффективным.

--------------------

Mirkes

Тофана

Дата 30.5.2014, 15:03 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 3
Регистрация: 29.5.2014

Репутация: нет
Всего: нет

Mirkes, то есть поделить исходную и единичную матрицу на куски для каждого процессора и там выполнять преобразования?

Да, минус алгоритма Гаусса как раз таки в слабой распараллеливаемости, но что велено сделать, то и делаю...

1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Алгоритмы \| Следующая тема »