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

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

Войти
Регистрация
Восстановить пароль
Другие темы раздела
Visual C++ Работа с FontDialog http://www.cyberforum.ru/cpp/thread1602242.html
Как привязать стиль шрифта с fontDialog к richTextBox, если есть Button, richTextBox, FontDialog и ShowDialog?
C++ Напечатать в алфавитном порядке все глухие согласные буквы, которые не входят только в одно слово Дан текст на русском языке. Напечатать в алфавитном порядке все глухие согласные буквы, которые не входят только в одно слово. Пытаюсь реализовать с помощью класса Set из библиотеки sysset. Создаю вектор,элементы которого множества,содержащие согласные буквы каждого слова. vector < Set <char,'A','z' > > v; Но проблема именно с алгоритмом поиска букв,которые входят во все кроме одного... http://www.cyberforum.ru/cpp/thread1602188.html
Массив: найти сумму отрицательных элементов и записать в одномерный массив C++
Люди добрые, подскажите пожалуйста как это сделать. 1)Задан двумерный массив, 2)найти сумму отрицательных элементов и записать в одномерный массив. 3) Динамически выделить память и обработку через указатели. 4) Результат вывести в файл.
MPI C++. Построение топологии сети C++
Всем доброго времени суток. Задача следующая: каждый узел в сети знает только своих соседей(локальную топологию). Необходимо объединить эти данные для построения полной топологии на определенном узле. (в виде матрицы) Не первые сутки голову ломаю над этим делом(( Понимаю, что необходимо послать с узла сообщение своим соседям, чтобы те после получения его послали в свою очередь своим...
C++ Блок схемы http://www.cyberforum.ru/cpp/thread1601715.html
Составить блок-схему алгоритма и программу для решения индивидуального задания. Задан массив целых чисел d1,...,d25. Вставить в него элемент, равный максимальному, справа от последнего отрицательного элемента. Дана матрица действительных чисел Eразмером 7х10. Получить новую матрицуA путем деления элементовматрицы E на наименьший по модулю элемент. Дан массив целых чисел D1,...,D30....
Delphi Решение СЛАУ с комплексными матрицами и столбцами методом исключения Гаусса Нужна программа для решения СЛАУ с комплексными матрицами и столбцами методом исключения Гаусса с выбором ведущего элемента по столбцу подробнее

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

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

05.12.2015, 00:28. Просмотров 481. Ответов 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