Форум программистов, компьютерный форум, киберфорум
C для начинающих
Войти
Регистрация
Восстановить пароль
Карта форума Темы раздела Блоги Сообщество Поиск Заказать работу  
 
 
Рейтинг 5.00/65: Рейтинг темы: голосов - 65, средняя оценка - 5.00
32 / 7 / 1
Регистрация: 10.09.2010
Сообщений: 837
1

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

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

Author24 — интернет-сервис помощи студентам
Для вариантов, предусматривающих решение систем линейных уравнений, умножение матриц и вычисление их определителей, размерность матрицы коэффициентов и ее элементы вводятся пользователем.
Необходимо реализовать следующие положения:
для вариантов по темам «матрицы», «системы линейных уравнений»:
реализовать генерацию данных случайным образом;
включить в функциональность программы оценку времени выполнения алгоритма;
оценить время работы алгоритма для матриц размерностей от 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)
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
19.09.2011, 08:29
Ответы с готовыми решениями:

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

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

Умножение двух матриц
Здравствуйте, завтра нужно сдать лабу по сишке, но функция Multiplication отказывается работать,...

Умножение неквадратных матриц
Здравствуйте. Столкнулась с segmentation fault (core dumped) при умножении матриц. Сами они...

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
Higher
1953 / 1219 / 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
программист С++
860 / 600 / 147
Регистрация: 19.12.2010
Сообщений: 2,014
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
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
32 / 7 / 1
Регистрация: 10.09.2010
Сообщений: 837
19.09.2011, 13:47  [ТС] 13
Цитата Сообщение от -=ЮрА=- Посмотреть сообщение
- у ТС были особые требования к ОС, ммм???
Работаю в форточках, на счёт сего скажу что ели есть желание разводить офтоп у меня его нет!На сим перехожу в другой топик до того как не последуют посты ТС...
PS:Вам сюдаhttp://en.wikipedia.org/wiki/Windows.h
Спасибо за код!а можешь по подробней рассказать что как получаеться
0
3564 / 2711 / 347
Регистрация: 11.03.2009
Сообщений: 6,240
19.09.2011, 13:53 14
Цитата Сообщение от -=ЮрА=- Посмотреть сообщение
sandye51, подключив в программу windows.h избавляем себя от кучи гемора,
кроме вышеназванных, есть еще один недостаток. Компилятор не умеет отделять код какой-либо функции из либы, поэтому при статической линковке, в программу будет добавляться код всей либы, соответсвующей хидеру.
0
794 / 546 / 61
Регистрация: 11.05.2010
Сообщений: 1,298
Записей в блоге: 1
19.09.2011, 13:56 15
kazak, а разве можно статически прилинковаться к kernel32.dll, user32.dll и другим?.. И разве заголовочник определяет, с какими библиотеками линковаться? Мне казалось, что это делается через параметры сборщика.
0
3564 / 2711 / 347
Регистрация: 11.03.2009
Сообщений: 6,240
19.09.2011, 14:34 16
Цитата Сообщение от talis Посмотреть сообщение
kazak, а разве можно статически прилинковаться к kernel32.dll, user32.dll и другим?..
Вообще возможно, но поскольку внутренне содержание виндовых либ известно лишь компании Майкрософт (причем оно может менятся от версии к версии), то для других компаний это будет труднореализуемым и с технической точки зрения и с юридической.
Я имел в виду стандартные библиотеки языка.
Цитата Сообщение от talis Посмотреть сообщение
И разве заголовочник определяет, с какими библиотеками линковаться?
Нет. Тут я наверное загнул. Немного перефразирую, при статической линковке в программу будет добавляться код всех объявленных функций. Думаю так будет правильнее.
Цитата Сообщение от talis Посмотреть сообщение
Мне казалось, что это делается через параметры сборщика.
Для нестандартных библиотек.
0
Эксперт С++
4267 / 2241 / 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
Эксперт С++
4267 / 2241 / 203
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
20.09.2011, 12:32 19
Цитата Сообщение от silent_1991 Посмотреть сообщение

Не по теме:


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

Не по теме:

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

0
32 / 7 / 1
Регистрация: 10.09.2010
Сообщений: 837
02.10.2011, 21:25  [ТС] 20
не запускаеться данный проект,вот такая ошибка
Миниатюры
Умножение матриц по Винограду  
0
02.10.2011, 21:25
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
02.10.2011, 21:25
Помогаю со студенческими работами здесь

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

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

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

Не правильно происходит умножение матриц
#include &lt;stdio.h&gt; #include &lt;stdlib.h&gt; #include &lt;locale.h&gt; int main() { int...


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

Или воспользуйтесь поиском по форуму:
20
Ответ Создать тему
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru