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

C++

Войти
Регистрация
Восстановить пароль
 
Wanno
0 / 0 / 0
Регистрация: 21.11.2015
Сообщений: 6
#1

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

05.12.2015, 00:28. Просмотров 559. Ответов 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
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
05.12.2015, 00:28
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Использование памяти. Алгоритм Штрассена умножения матриц (C++):

Как на с++ организовать БЫСТРЫЙ алгоритм умножения матриц? - C++
Как на с++ организовать БЫСТРЫЙ алгоритм умножения матриц? Нужна именно быстрая сортировка а не обычный алгоритм умножения

Предложить эффективный алгоритм умножения числа на дробь в длинной арифметике - C++
Нам дано длинное натуральное число, представленное в виде динамического массива: 1) разряды числа записываются от старшего к младшему;...

Использование памяти при выполнении программы - C++
Здравствуйте, товарищи. Столкнулись с такой загвоздкой. Есть некая, совершенно небольшая программа, после компиляции которой и запуски...

Умножения матриц, цикл - C++ Builder
Всем привет, помогите пожалуйста, у меня есть 4 х CSpinEdit'a и 3 х StringGrid'a, с помощью CSpinEdita можно настроить размерность матрицы...

Разработать способ экономного хранения в памяти разреженных матриц - C++ Builder
Помогите плз зделать Задание 1 Разработать способ экономного хранения в памяти разреженных матриц (таблиц). Разработать процедуры и...

Алгоритм умножения матриц Винограда-Штрассена - C++
Имеется реализованный алгоритм умножения матриц по Штрассену. Проблема следующая: Штрассена надо переделать в Штрассена-Винограда, но это...

0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
05.12.2015, 00:28
Привет! Вот еще темы с ответами:

Прокомментировать код - алгоритм Штрассена для умножения матриц - C++
Народ Здравствуйте , есть такая задача ( Курсовая работа, алгоритм Штрассена для умножения матриц ) Пожалуйста сделайте в коде...

Перемножение матриц (алгоритм Штрассена) - C#
День добрый! Необходимо перемножить две квадратные матрицы размера 15000х15000. Нужно написать алгоритм Штрассена (или может предложите...

Алгоритм Штрассена для быстрого перемножения матриц - C++
Помогите реализовать алгоритм Штрассена! Может у кого нибудь есть исходник на С++? Если не программой то помогите с идеями, как это все...

Алгоритм умножения прямоугольных матриц - C++
написать алгоритм умножения прямоугольных матриц, известна только размерность


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
1
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru