Форум программистов, компьютерный форум, киберфорум
Наши страницы

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

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ MPI C++. Построение топологии сети http://www.cyberforum.ru/cpp/thread1601729.html
Всем доброго времени суток. Задача следующая: каждый узел в сети знает только своих соседей(локальную топологию). Необходимо объединить эти данные для построения полной топологии на определенном...
C++ Вектор функций? Добрый вечер. На просторах интернета наткнулся на следующее: std::vector<std::function<...>> (http://www.cyberforum.ru/cpp-beginners/thread341275.html) а внутри лямбда-функции. Вопрос такой:... http://www.cyberforum.ru/cpp/thread1600997.html
Подключение камеры через FireWire к opencv C++
Столкнулся с проблемой, работаю с VS12 Opencv 3.0.0 и программа не находит камеру с FireWire, обычную вебку без проблем. Старая версия OPENCV231 находила без проблем, новая же увы Код для пробы...
Построить хеш-таблицу списка слов из файла 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... подробнее

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

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

05.12.2015, 00:28. Просмотров 548. Ответов 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;
}
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru