Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Алгоритмы > Параллельное нахождение обратной матрицы с MPI

Автор: Тофана 29.5.2014, 22:40

Добрый вечер, помогите пожалуйста распараллелить алгоритм нахождения обратной матрицы с помощью 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

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

Автор: Тофана 30.5.2014, 08:15

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

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

Автор: Тофана 30.5.2014, 15:03

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

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