Форум программистов, компьютерный форум CyberForum.ru

Использование памяти. Алгоритм Штрассена умножения матриц - C++

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ MPI C++. Построение топологии сети http://www.cyberforum.ru/cpp/thread1601729.html
Всем доброго времени суток. Задача следующая: каждый узел в сети знает только своих соседей(локальную топологию). Необходимо объединить эти данные для построения полной топологии на определенном узле. (в виде матрицы) Не первые сутки голову ломаю над этим делом(( Понимаю, что необходимо послать с узла сообщение своим соседям, чтобы те после получения его послали в свою очередь своим...
C++ Вектор функций? Добрый вечер. На просторах интернета наткнулся на следующее: std::vector<std::function<...>> (http://www.cyberforum.ru/cpp-beginners/thread341275.html) а внутри лямбда-функции. Вопрос такой: можно ли подобное провернуть не с лямбда-функциями, а с: void a(int); void b(int); http://www.cyberforum.ru/cpp/thread1600997.html
Подключение камеры через FireWire к opencv C++
Столкнулся с проблемой, работаю с VS12 Opencv 3.0.0 и программа не находит камеру с FireWire, обычную вебку без проблем. Старая версия OPENCV231 находила без проблем, новая же увы Код для пробы самый простой #include "opencv2/opencv.hpp" using namespace cv; int main() {
Построить хеш-таблицу списка слов из файла C++
Уважаемые, программисты, задание звучит так - "Входной файл содержит список не повторяющихся слов и разделенных переводами строки. Построить хеш-таблицу и вывести на экран."
C++ Передача данных приложению №1 запустившего приложение №2 http://www.cyberforum.ru/cpp/thread1600169.html
Приветствую. Запускаю приложением №1 через ShellExecuteEx приложение №2 Можно ли как-то через хендл приложения №2 передать данные приложению №1? Может через CreateProcess?
C++ Как измерить время работы потока? Openmp Как измерить время работы потоков в рекурсивной функции? например есть функция (примерный код) void function(int i, int j ) { #pragma omp task if (i>j) function(i, j ); #pragma omp task if (i<j) function(j, i ); подробнее

Показать сообщение отдельно
Wanno
0 / 0 / 0
Регистрация: 21.11.2015
Сообщений: 6

Использование памяти. Алгоритм Штрассена умножения матриц - C++

05.12.2015, 00:28. Просмотров 511. Ответов 0
Метки (Все метки)

Есть код (вроде рабочий) с реализацией алгоритма Штрассена умножения квадратных матриц, этот алгоритм основан на разбиении перемножаемых матриц на 4 блока и вычисления результата по специальным формулам (использует 7 умножений а не 8), но на каждом уровне рекурсии приходится выделять 19 матриц, из-за этого тратится огромное количество памяти, можно ли как-то уменьшить кол-во выделяемых матриц, ибо при таком кол-ве получается умножить матрицы максимально 2048 на 2048 на большего просто не хватает памяти? Думаю что можно не выделять матрицы под разбиение входящих матриц, а просто передавать в функции смещенные указатели, но мои попытки что-то сделать в этом направлении ни к чему не привели. Так можно ли ка-то уменьшить кол-во выделяемой памяти?
P.S. Я знаю, что этот алгоритм редко на практике применяется и есть другие более эффективные, но нужно именно этот доработать.
Вот код алгоритма Штрассена (коды функций CreateMatrix(N) - выделяет память под матрицу размера NxN, Trivial_alghorithm() - умножение матриц "в 3 цикла", AdditionMatrix(A,B) - прибавляет к матрице А матрицу В(их не изменяет) и SubstructionMatrix() - вычитает из матрицы А матрицу В(их не изменяет), если нужно выложу)
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
int** Shtrassen_alghorithm(int** matrix1, int** matrix2, int N, int threshold){
    int** Rez = CreateMatrix(N);
    if(N <= threshold){
        Rez = Trivial_alghorithm(matrix1,matrix2,N);
    }
    else{
        N = N/2;
        int** A[4];
        int** B[4];
        int** C[4];
        int** P[7];
 
        /*Выделяем память под вспомогательные матрицы*/
        for(int i = 0; i < 4; i++){
            A[i] = CreateMatrix(N);
            B[i] = CreateMatrix(N);
            C[i] = CreateMatrix(N);
        }
        for(int i = 0; i < 7; i++)
            P[i] = CreateMatrix(N);
 
        /*Разбиваем матриц на 4 блока*/
        for(int i = 0; i < N; i++)
            for(int j = 0; j < N; j++){
                A[0][i][j] = matrix1[i][j];
                A[1][i][j] = matrix1[i][j+N];
                A[2][i][j] = matrix1[i+N][j];
                A[3][i][j] = matrix1[i+N][j+N];
 
                B[0][i][j] = matrix2[i][j];
                B[1][i][j] = matrix2[i][j+N];
                B[2][i][j] = matrix2[i+N][j];
                B[3][i][j] = matrix2[i+N][j+N];
            }
 
        /*Выполняем умножения 7 шт.*/
        P[0] = Shtrassen_alghorithm(AdditionMatrix(A[0], A[3], N), AdditionMatrix(B[0], B[3], N), N,threshold);
        P[1] = Shtrassen_alghorithm(AdditionMatrix(A[2], A[3], N), B[0], N, threshold);
        P[2] = Shtrassen_alghorithm(A[0], SubstructionMatrix(B[1], B[3], N), N, threshold);
        P[3] = Shtrassen_alghorithm(A[3], SubstructionMatrix(B[2], B[0], N), N, threshold);
        P[4] = Shtrassen_alghorithm(AdditionMatrix(A[0], A[1], N), B[3], N, threshold);
        P[5] = Shtrassen_alghorithm(SubstructionMatrix(A[2], A[0], N),AdditionMatrix(B[0], B[1], N), N, threshold);
        P[6] = Shtrassen_alghorithm(SubstructionMatrix(A[1], A[3], N),AdditionMatrix(B[2], B[3], N), N, threshold);
 
        /*Находим результирующие значения(блоки)*/
        C[0] = SubstructionMatrix(AdditionMatrix(AdditionMatrix(P[0], P[3], N), P[6],N),P[4],N);
        C[1] = AdditionMatrix(P[2], P[4], N);
        C[2] = AdditionMatrix(P[1], P[3], N);
        C[3] = SubstructionMatrix(AdditionMatrix(AdditionMatrix(P[0], P[2], N), P[5],N),P[1],N);
 
        /*Формируем результирующую матрицу*/
        for(int i = 0; i < N; i++)
            for(int j = 0; j < N; j++){
                    Rez[i][j] = C[0][i][j];
                    Rez[i][j+N] = C[1][i][j];
                    Rez[i+N][j] = C[2][i][j];
                    Rez[i+N][j+N] = C[3][i][j];
            }
 
        /*Освобождаем выделенную память*/
        for(int i = 0; i < 4; i++){
            delete[] A[i];
            delete[] B[i];
            delete[] C[i];
        }
        for(int i = 0; i < 7; i++)
            delete[] P[i];
    }
 
    return Rez;
}
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru