Блог

Главная - Вопросы по программированию - Ускорение возведения матрицы в степень с помощью openmp

Ускорение возведения матрицы в степень с помощью openmp

#c #multithreading #matrix #optimization #openmp

#c #многопоточность #матрица #оптимизация #openmp

Вопрос:

У меня есть функция, которая вычисляет n-ю степень матрицы, используя мощность. Код написан на языке Си:

 void matrix_power(matrix *result, matrix *mat, int pow) {
    if (pow == 0) {
        for (int r = 0; r < mat->rows; r  ) {
            for (int c = 0; c < mat->cols; c  ) {
                result->content[r][c] = r == c;
            }
        }
    } else if (pow == 1) {
        for (int r = 0; r < mat->rows; r  ) {
            for (int c = 0; c < mat->cols; c  ) {
                result->content[r][c] = mat->content[r][c];
            }
        }
    } else {
        matrix *temp;
        copy_matrix(temp, mat); //now temp becomes mat
        matrix_power(temp, mat, pow /= 2);
        matrix_multiply(result, temp, temp);
        if (pow % 2 == 1) {
            copy_matrix(temp, result);
            matrix_multiply(result, temp, mat);
        }
        deallocate_matrix(temp);
    }
}

Я хочу оптимизировать свой код, чтобы он работал в 1000 раз быстрее, чем наивная реализация матричного питания. В настоящее время моя реализация работает только в 300 раз быстрее. Моя функция matrix_multiply была прилично оптимизирована с использованием SIMD и OpenMP. Я хочу использовать OpenMP для достижения лучшей параллельной производительности. Как я могу это сделать? Или есть какие-то другие методы, которые я должен рассмотреть, чтобы получить значительное увеличение скорости?

Комментарии:

1. Диагонализуема ли матрица?

2. Извините! Я забыл упомянуть, что записи матрицы являются двойными. Так что я предполагаю, что диагонализация будет затруднена.

3. Должно pow /= 2 быть pow / 2 ?

4. matrix *temp; за ним следует, copy_matrix(temp, mat); похоже, что он использует недопустимое (неинициализированное) значение указателя from temp . Если copy_matrix только это не макрос, который делает что-то нефункциональное.

5. @V.Reeve Я не знаю, почему вы предполагаете, что это сложно из-за удвоений. Гарольд имеет в виду, что в действительно интересных случаях (большие матрицы / большие мощности) лучше диагностировать матрицу (что означает преобразование матрицы в ее собственное представление), выполнить вычисление и преобразовать обратно. Возможно, он также прочитал только заголовок вашего вопроса и подумал, что вы имели в виду exp(matrix) вместо matrix ^ number . Для фактического возведения матрицы в степень exp (матрица) диагонализация в основном неизбежна.

Метки: