Форум программистов, компьютерный форум, киберфорум
Наши страницы
C для начинающих
Войти
Регистрация
Восстановить пароль
 
 
Рейтинг 4.70/30: Рейтинг темы: голосов - 30, средняя оценка - 4.70
zmei89
32 / 7 / 1
Регистрация: 10.09.2010
Сообщений: 835
1

Умножение матриц по Винограду

19.09.2011, 08:29. Просмотров 5932. Ответов 38
Метки нет (Все метки)

Для вариантов, предусматривающих решение систем линейных уравнений, умножение матриц и вычисление их определителей, размерность матрицы коэффициентов и ее элементы вводятся пользователем.
Необходимо реализовать следующие положения:
для вариантов по темам «матрицы», «системы линейных уравнений»:
реализовать генерацию данных случайным образом;
включить в функциональность программы оценку времени выполнения алгоритма;
оценить время работы алгоритма для матриц размерностей от 5 до 100 (верхний предел может быть больше), результаты измерений записать в файл; при этом время теста должно быть соизмеримо со временем принятия лабораторной работы;
на основании данных теста из файла вывести график зависимости времени работы программы от размерности матрицы, сделать выводы.

Само задание

Решение систем линейных уравнений методом исключения Гаусса с выбором главного элемента по столбцу.

Умножение матриц с использованием алгоритма Винограда.

может кто знает хотя бы одно задание помогите пожалуйста разобраться

Добавлено через 15 минут
вот что то нашел ну скорее всего это не то

Умножение матриц по Винограду
Если посмотреть на результат умножения двух матриц, то видно, что каждый элемент в нем представляет собой скалярное произведение соответствующих строки и столбца исходных матриц. Можно заметить также, что такое умножение допускает предварительную обработку, позволяющую часть работы выполнить заранее.
Рассмотрим два вектора V = (v1, v2, v3, v4) и W = (w1, w2, w3, w4). Их скалярное произведение равно:
V • W = v1w1 + v2w2 + v3w3 + v4w4.
Это равенство можно переписать в виде:
V • W = (v1 + w2)(v2 + w1) + (v3 + w4)(v4 + w3) - v1v2 - v3v4 - w1w2 - w3w4.
Вы сами можете без труда проверить эквивалентность двух последних выражений. Кажется, что второе выражение задает больше работы, чем первое: вместо четырех умножений мы насчитываем их шесть, а вместо трех сложений - десять. Менее очевидно, что выражение в правой части последнего равенства допускает предварительную обработку: его части можно вычислить заранее и запомнить для каждой строки первой матрицы и для каждого столбца второй. На практике это означает, что над предварительно обработанными элементами нам придется выполнять лишь первые два умножения и последующие пять сложений, а также дополнительно два сложения.
Вот как выглядит полный алгоритм Винограда для умножения матрицы G размером a x b на матрицу H размером b x c. Результат записывается в матрицу R размером a x c.
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
  d = b/2
  // вычисление rowFactors для G
  for i = 1 to a do
    rowFactor[i] = G[i, 1] * G[i, 2]
    for j = 2 to d do
        rowFactor[i] = rowFactor[i] + G[i, 2j - 1] * G[i, 2j]
    end for j
end for i
 
 
// вычисление   columnFactors для H
for i = 1 to c do
    columnFactor[i] = H[1, i] * H[2, i]
    for j = 2 to d do
        columnFactor[i] = columnFactor[i] + H[2j - 1, i] * H[2j, i]
    end for j
end for i
 
 
// вычисление матрицы R
for i = 1 to a do
    for j = 1 to c do
        R[i, j] = -rowFactor[i] - columnFactor[j]
        for k = 1 to d do
            R[i, j]=R[i, j]+(G[i, 2k-1]+H[2k, j])*(G[i, 2k] + H[2k-1, j])
        end for k
    end for j
end for i
 
 
// прибавление членов в случае нечетной общей размерности
if (2 * (b/2)    /= b) then
    for i = 1 to a do
        for j = 1 to c do
            R[i, j] = R[i, j] + G[i, b] * H[b, j]
        end for j
    end for i
end if
0
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
19.09.2011, 08:29
Ответы с готовыми решениями:

Умножение матриц (не работает для неквадратных матриц)
Доброго времени суток. Написал код для перемножения двух матриц. При вводе квадратной матрицы всё...

Умножение матриц Си
моя програма считает умножение двух матриц. Вводим одно Число(оно же будет размером двух матриц),...

Умножение квадратных матриц
Доброго времени суток. Я опять прошу Вашей неоценимой помощи. Столкнулся с задачей, нужно...

Параллельное умножение матриц
Всем привет, помогите написать программу) нужно написать программу Параллельное умножение матриц,...

Умножение матриц работает некорректно
Что не так в этом коде? Вроде же все правильно. Суммируется нормально, а вот умножение...Бывает...

38
-=ЮрА=-
Заблокирован
Автор FAQ
19.09.2011, 09:39 2
Цитата Сообщение от zmei89 Посмотреть сообщение
Решение систем линейных уравнений методом исключения Гаусса
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
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
#include <windows.h>//malloc, system("pause")
#include <stdio.h>  //i/o
#include <conio.h>  //getch
#include <math.h>
 
void ShowVector(int n, double * vec);
void PryamoiHod(int n, double **a, double *b);
void ObratniHod(int n, double **a, double *b, double *x);
 
int main()
{
        int i,j,n;
        double **a, *b, *x;
        do
        {
                printf("Enter NUM of equations: ");
                scanf("%d",&n);
                //Выделяем память под матрицу А и векторы В и Х
                a = (double **)malloc(n*sizeof(double));
                b = (double *)malloc(n*sizeof(double));
                x = (double *)malloc(n*sizeof(double));
                for(i = 0; i < n; i++)
                {
                        a[i] = (double *)malloc(n*sizeof(double));
                        //Ввод a
                        for(j = 0; j < n; j++)
                        {
                                printf("a[%d][%d] = ",i + 1,j + 1);
                                scanf("%lf",&a[i][j]);
                        }
                }
                //Ввод b
                for(i = 0; i < n; i++)
                {
                        printf("b[%d] = ",i + 1);
                        scanf("%lf",&b[i]);
                }
                
                printf("\tSee input\r\n");
                printf("Matrix A:\r\n");
                for(i = 0; i < n; i++)
                        ShowVector(n, a[i]);
                printf("Vector B:\r\n");
                ShowVector(n, b);
                
                printf("\tSolving on Gauss method\r\n");
                PryamoiHod(n, a, b);
                printf("Forvard Gauss course\r\n");//Прямой ход
                printf("Matrix A:\r\n");
                for(i = 0; i < n; i++)
                        ShowVector(n, a[i]);
                printf("Vector B:\r\n");
                ShowVector(n, b);
 
                ObratniHod(n, a, b, x);
                printf("Back Gauss course\r\n");//Обратный ход
                printf("Matrix A:\r\n");
                for(i = 0; i < n; i++)
                        ShowVector(n, a[i]);
                printf("Vector B:\r\n");
                ShowVector(n, b);
 
                printf("Results :\r\n");
                ShowVector(n, x);
 
                printf("Press Y for new input\r\n");
                //Чистим память
                free((void *)a);
                free((void *)b);
                free((void *)x);
        }
        while(toupper(getch()) == 'Y');
        return 0;
}
 
void ShowVector(int n, double * vec)
{
        for(int i = 0; i < n; i++)
                printf("%.3f ",vec[i]);
        printf("\r\n");
}
 
void PryamoiHod(int n, double **a, double *b)
{
        double v;
        for(int k = 0,i,j,im; k < n - 1; k++)
        {
                im = k;
                for(i = k + 1; i < n; i++)
                {
                        if(fabs(a[im][k]) < fabs(a[i][k]))
                        {
                                im = i;
                        }
                }
                if(im != k)
                {
                        for(j = 0; j < n; j++)
                        {
                                v                = a[im][j];
                                a[im][j] = a[k][j];
                                a[k][j]  = v;
                        }
                        v     = b[im];
                        b[im] = b[k];
                        b[k]  = v;
                }
                for(i = k + 1; i < n; i++)
                {
                        v               = 1.0*a[i][k]/a[k][k];
                        a[i][k] = 0;
                        b[i]    = b[i] - v*b[k];
                                                if(v != 0)
                        for(j = k + 1; j < n; j++)
                        {
                                a[i][j] = a[i][j] - v*a[k][j];
                        }
                }
        }
}
 
void ObratniHod(int n, double **a, double *b, double *x)
{
        double s = 0;
        x[n - 1] = 1.0*b[n - 1]/a[n - 1][n - 1];
        for(int i = n - 2, j; 0 <= i; i--)
        {
                s = 0;
                for(j = i + 1; j < n; j++)
                {
                        s = s+a[i][j]*x[j];
                }
                x[i] = 1.0*(b[i] - s)/a[i][i];
        }
}
результат работы
Enter NUM of equations: 5
a[1][1] = 2
a[1][2] = 0
a[1][3] = 0
a[1][4] = -12
a[1][5] = 3
a[2][1] = 0
a[2][2] = 2
a[2][3] = 0
a[2][4] = 3
a[2][5] = 2
a[3][1] = 0
a[3][2] = 0
a[3][3] = 38
a[3][4] = 5
a[3][5] = 7
a[4][1] = -12
a[4][2] = 13
a[4][3] = 5
a[4][4] = 0
a[4][5] = 0
a[5][1] = 3
a[5][2] = 2
a[5][3] = 7
a[5][4] = 0
a[5][5] = 0
b[1] = 22
b[2] = 14
b[3] = 456
b[4] = 0
b[5] = 5
See input
Matrix A:
2.000 0.000 0.000 -12.000 3.000
0.000 2.000 0.000 3.000 2.000
0.000 0.000 38.000 5.000 7.000
-12.000 13.000 5.000 0.000 0.000
3.000 2.000 7.000 0.000 0.000
Vector B:
22.000 14.000 456.000 0.000 5.000
Solving on Gauss method
Forvard Gauss course
Matrix A:
-12.000 13.000 5.000 0.000 0.000
0.000 5.250 8.250 0.000 0.000
0.000 0.000 38.000 5.000 7.000
0.000 0.000 0.000 -11.662 3.474
0.000 0.000 0.000 0.000 3.596
Vector B:
0.000 5.000 456.000 50.794 64.678
Back Gauss course
Matrix A:
-12.000 13.000 5.000 0.000 0.000
0.000 5.250 8.250 0.000 0.000
0.000 0.000 38.000 5.000 7.000
0.000 0.000 0.000 -11.662 3.474
0.000 0.000 0.000 0.000 3.596
Vector B:
0.000 5.000 456.000 50.794 64.678
Results : <- Это ответы
-9.967 -12.491 8.555 1.002 17.987
Press Y for new input
0
sandye51
19.09.2011, 12:36
  #3

Не по теме:

Цитата Сообщение от -=ЮрА=- Посмотреть сообщение
#include <windows.h>//malloc, system("pause")
сие находится в <cstdlib> :-)

0
-=ЮрА=-
Заблокирован
Автор FAQ
19.09.2011, 12:42 4
Цитата Сообщение от sandye51 Посмотреть сообщение
сие находится в <cstdlib>
и достаточно подключить windows.h чтобы не ломать голову где malloc где system где toupper лежит...Если же есть желание посмотреть где объявлен заголовок то нажимаем в студии Go To Declaration
0
sandye51
19.09.2011, 12:43
  #5

Не по теме:

использовать операционно-зависимые ашники, где это на самом деле не требуется - правило плохо тона

0
-=ЮрА=-
Заблокирован
Автор FAQ
19.09.2011, 13:07 6
sandye51, подключив в программу windows.h избавляем себя от кучи гемора, на старіх компиляторах malloc дан в malloc.h а уже в поновей cstdlib. Зачем кому-то этот гемор с хедерами если windows.h своими дефайнами позволяет точно всё подключить???И подключать всё по отдельности это дополнительные строки кода...
0
diagon
Higher
1938 / 1204 / 120
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
19.09.2011, 13:09 7
Цитата Сообщение от -=ЮрА=- Посмотреть сообщение
одключив в программу windows.h избавляем себя от кучи гемора
И добавляем гемора тем, кто будет этим кодом пользоваться.
У меня вообще windows.h нету, т.к. это нестандартный хедер, и ваш код просто не компилируется.
2
-=ЮрА=-
Заблокирован
Автор FAQ
19.09.2011, 13:13 8
Цитата Сообщение от diagon Посмотреть сообщение
У меня вообще windows.h нету, т.к. она не входит в стандарт, и ваш код просто не компилируется.
- выделяем память new и компилируем получившуюся смесь Си с С++. Если есть претензии к алгоритму сразу скажу он проверен многолетним стажем работы, есть желание поковырять код выдираем из проги
C++
1
void PryamoiHod(int n, double **a, double *b)
,
C++
1
void ObratniHod(int n, double **a, double *b, double *x);
PS:diagon, предлагаю поставить VisualStudio а не CodeBlocks или что там стоит юзать
0
sandye51
программист С++
837 / 596 / 147
Регистрация: 19.12.2010
Сообщений: 2,016
19.09.2011, 13:16 9
Цитата Сообщение от -=ЮрА=- Посмотреть сообщение
предлагаю поставить VisualStudio
ага, под линуксом

где ж ты работаешь? опытный прям такой)
2
-=ЮрА=-
Заблокирован
Автор FAQ
19.09.2011, 13:21 10
Цитата Сообщение от sandye51 Посмотреть сообщение
под линуксом
- у ТС были особые требования к ОС, ммм???
Работаю в форточках, на счёт сего
Цитата Сообщение от sandye51 Посмотреть сообщение
опытный прям такой)
скажу что ели есть желание разводить офтоп у меня его нет!На сим перехожу в другой топик до того как не последуют посты ТС...
PS:Вам сюдаhttp://en.wikipedia.org/wiki/Windows.h
0
sandye51
19.09.2011, 13:24
  #11

Не по теме:

Цитата Сообщение от -=ЮрА=- Посмотреть сообщение
скажу что ели есть желание разводить офтоп у меня его нет
это уже оправдание)

есть у нас тоже препод в универе. На первом занятии начал - если что обращайтесь, у меня большой опыт) а сам вместо табов несколько пробелов ставит и идентификаторы на транслите называет :rofl:

2
talis
794 / 546 / 61
Регистрация: 11.05.2010
Сообщений: 1,298
Записей в блоге: 1
19.09.2011, 13:32 12
Цитата Сообщение от sandye51 Посмотреть сообщение
вместо табов несколько пробелов ставит

Не по теме:

Ну это не показатель, я так же делаю. Из тех соображений, что в каждой IDE расстояние табуляции разное, и, если пользоваться табами, снижается комфортность. А так - четыре пробела и везде одно и то же.



А вообще, windows.h is a Windows-specific header, как говорит википедия. Так что лучше его не использовать, если можно обойтись без него.
1
zmei89
32 / 7 / 1
Регистрация: 10.09.2010
Сообщений: 835
19.09.2011, 13:47  [ТС] 13
Цитата Сообщение от -=ЮрА=- Посмотреть сообщение
- у ТС были особые требования к ОС, ммм???
Работаю в форточках, на счёт сего скажу что ели есть желание разводить офтоп у меня его нет!На сим перехожу в другой топик до того как не последуют посты ТС...
PS:Вам сюдаhttp://en.wikipedia.org/wiki/Windows.h
Спасибо за код!а можешь по подробней рассказать что как получаеться
0
kazak
3061 / 2382 / 255
Регистрация: 11.03.2009
Сообщений: 5,438
Завершенные тесты: 1
19.09.2011, 13:53 14
Цитата Сообщение от -=ЮрА=- Посмотреть сообщение
sandye51, подключив в программу windows.h избавляем себя от кучи гемора,
кроме вышеназванных, есть еще один недостаток. Компилятор не умеет отделять код какой-либо функции из либы, поэтому при статической линковке, в программу будет добавляться код всей либы, соответсвующей хидеру.
0
talis
794 / 546 / 61
Регистрация: 11.05.2010
Сообщений: 1,298
Записей в блоге: 1
19.09.2011, 13:56 15
kazak, а разве можно статически прилинковаться к kernel32.dll, user32.dll и другим?.. И разве заголовочник определяет, с какими библиотеками линковаться? Мне казалось, что это делается через параметры сборщика.
0
kazak
3061 / 2382 / 255
Регистрация: 11.03.2009
Сообщений: 5,438
Завершенные тесты: 1
19.09.2011, 14:34 16
Цитата Сообщение от talis Посмотреть сообщение
kazak, а разве можно статически прилинковаться к kernel32.dll, user32.dll и другим?..
Вообще возможно, но поскольку внутренне содержание виндовых либ известно лишь компании Майкрософт (причем оно может менятся от версии к версии), то для других компаний это будет труднореализуемым и с технической точки зрения и с юридической.
Я имел в виду стандартные библиотеки языка.
Цитата Сообщение от talis Посмотреть сообщение
И разве заголовочник определяет, с какими библиотеками линковаться?
Нет. Тут я наверное загнул. Немного перефразирую, при статической линковке в программу будет добавляться код всех объявленных функций. Думаю так будет правильнее.
Цитата Сообщение от talis Посмотреть сообщение
Мне казалось, что это делается через параметры сборщика.
Для нестандартных библиотек.
0
Thinker
Эксперт С++
4236 / 2210 / 203
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
19.09.2011, 22:59 17
Цитата Сообщение от sandye51 Посмотреть сообщение

Не по теме:


есть у нас тоже препод в универе. На первом занятии начал - если что обращайтесь, у меня большой опыт) а сам вместо табов несколько пробелов ставит и идентификаторы на транслите называет

Цитата Сообщение от talis Посмотреть сообщение

Не по теме:

Ну это не показатель, я так же делаю

Не по теме:

оформление java-программ вообще гласит никаких табуляций, именно пробелы. Не понятно вообще к чему эта шутка поднималась. Сам tab избегаю как только можно. 3-4 пробела самое то:)

0
silent_1991
20.09.2011, 12:05
  #18

Не по теме:

Цитата Сообщение от Thinker Посмотреть сообщение
3-4 пробела самое то
С другой стороны, любой внятный редактор имеет опцию "Заменять табуляции пробелами", и связанную с ней опцию "размер табуляции". Согласитесь, лучше один раз нажать таб, чем 4 раза пробел))

1
Thinker
Эксперт С++
4236 / 2210 / 203
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
20.09.2011, 12:32 19
Цитата Сообщение от silent_1991 Посмотреть сообщение

Не по теме:


Согласитесь, лучше один раз нажать таб, чем 4 раза пробел))

Не по теме:

Скорее это дело привычки. Когда пишется красивый код, на эти мелочи уже внимание не обращается:)

0
zmei89
32 / 7 / 1
Регистрация: 10.09.2010
Сообщений: 835
02.10.2011, 21:25  [ТС] 20
не запускаеться данный проект,вот такая ошибка
0
Миниатюры
Умножение матриц по Винограду  
02.10.2011, 21:25
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
02.10.2011, 21:25

Умножение матриц произвольного размера
Доброго времени суток.Нужно написать вот это Написать функцию для умножения матриц произвольного...

Умножение матриц - коррекция кода
Помогите пожалуйста вроде прогу пральную написал но ответы не совпадают даны две прямоугольные...

Умножение матриц большого размера
Как объявить матрицу из целых чисел размера NxN если это N &lt;=1024? Нужно написать умножение матриц...


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

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

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