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

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

19.09.2011, 08:29. Просмотров 6030. Ответов 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
fasked
02.10.2011, 21:28     Умножение матриц по Винограду
  #21

Не по теме:

Цитата Сообщение от Thinker Посмотреть сообщение
Скорее это дело привычки. Когда пишется красивый код, на эти мелочи уже внимание не обращается
Не соглашусь, на красивость кода количество нажатий на кнопку не влияет, а нажать один раз Tab или один раз Shift+Tab, куда проще, чем раза Space или Backspace.

0
-=ЮрА=-
Заблокирован
Автор FAQ
02.10.2011, 21:31 22
zmei89, очистите папку проекта, оставьте только лишь срр файл программы и перекомпилируйте
0
alex_x_x
бжни
2456 / 1663 / 134
Регистрация: 14.05.2009
Сообщений: 7,162
02.10.2011, 21:47 23
программа не собралась - запускать нечего
0
zmei89
32 / 7 / 1
Регистрация: 10.09.2010
Сообщений: 835
02.10.2011, 22:20  [ТС] 24
все удалил из папки все равно такая же ошибка

Добавлено через 8 минут
так что еще добавить

Добавлено через 21 минуту
такую же ошибку выдает
0
Thinker
Эксперт С++
4236 / 2210 / 203
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
02.10.2011, 22:30 25
Цитата Сообщение от fasked Посмотреть сообщение

Не по теме:


Не соглашусь, на красивость кода количество нажатий на кнопку не влияет, а нажать один раз Tab или один раз Shift+Tab, куда проще, чем раза Space или Backspace.

Не по теме:

Кому как, а я лично настолько к пробелам привык, что tab не применяю, да и отучили, когда на java писал, официальное правило оформления кода не разрешало

0
kazak
3061 / 2382 / 255
Регистрация: 11.03.2009
Сообщений: 5,440
Завершенные тесты: 1
02.10.2011, 23:51 26
zmei89, в нижнем окошке выводится отчет о построении, в конце явственно читается, что есть ошибки. Поподробнее, что за ошибки?
0
zmei89
32 / 7 / 1
Регистрация: 10.09.2010
Сообщений: 835
03.10.2011, 09:17  [ТС] 27
вот и ошибки
0
Миниатюры
Умножение матриц по Винограду  
-=ЮрА=-
Заблокирован
Автор FAQ
03.10.2011, 09:18 28
zmei89, кроме замечания от kazak, укажите среду в которой вы работаете, в кодблокс приведенный мной алгоритм выдаст ошибки компиляции т.к. там заголовочные файлы имеют другие названия...
0
zmei89
32 / 7 / 1
Регистрация: 10.09.2010
Сообщений: 835
03.10.2011, 09:26  [ТС] 29
Visual Studio 2010
0
-=ЮрА=-
Заблокирован
Автор FAQ
03.10.2011, 09:46 30
Цитата Сообщение от zmei89 Посмотреть сообщение
Visual Studio 2010
- с этого надо было начинать построение задания.
1 - е код приведенный мной написан на Си и имеет старый стиль заголовков (include <stdlib.h> а не include <cstdlib>)
2 - е даже здесь по форуму встречал кучу топиков о неправильном или кривом инсталлировании 10-ки, а также её неправильной настройке. Единсвенное что могу сделать перправить код под С++, думаю тогда 10-ка его откомпилирует без проблем, поождите перу минут...
0
zmei89
32 / 7 / 1
Регистрация: 10.09.2010
Сообщений: 835
03.10.2011, 09:47  [ТС] 31
Переправте пожалуйста!
0
-=ЮрА=-
Заблокирован
Автор FAQ
03.10.2011, 09:53 32
Вот подогнал под С++
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 <iostream>//i/o
#include <conio.h> //getch
#include <cmath>   //fabs, abs
using namespace std;
 
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
        {
                cout<<"Enter NUM of equations: ";
                cin>>n;
                //Выделяем память под матрицу А и векторы В и Х
                a = new double *[n];
                b = new double  [n];
                x = new double  [n];
                for(i = 0; i < n; i++)
                {
                        a[i] = new double[n];
                        //Ввод a
                        for(j = 0; j < n; j++)
                        {
                                cout<<"a["<<i + 1<<"]["<<j + 1<<"] = ";
                                cin>>a[i][j];
                        }
                }
                //Ввод b
                for(i = 0; i < n; i++)
                {
                        cout<<"b["<<i + 1<<"] = ";
                        cin>>b[i];
                }
                
                cout<<"\tSee input\r\n";
                cout<<"Matrix A:\r\n";
                for(i = 0; i < n; i++)
                        ShowVector(n, a[i]);
                cout<<"Vector B:\r\n";
                ShowVector(n, b);
                
                cout<<"\tSolving on Gauss method\r\n";
                PryamoiHod(n, a, b);
                cout<<"Forvard Gauss course\r\n";//Прямой ход
                cout<<"Matrix A:\r\n";
                for(i = 0; i < n; i++)
                        ShowVector(n, a[i]);
                cout<<"Vector B:\r\n";
                ShowVector(n, b);
 
                ObratniHod(n, a, b, x);
                cout<<"Back Gauss course\r\n";//Обратный ход
                cout<<"Matrix A:\r\n";
                for(i = 0; i < n; i++)
                        ShowVector(n, a[i]);
                cout<<"Vector B:\r\n";
                ShowVector(n, b);
 
                cout<<"Results :\r\n";
                ShowVector(n, x);
 
                cout<<"Press Y for new input\r\n";
                //Чистим память
                delete [] a;
                delete [] b;
                delete [] x;
        }
        while(toupper(getch()) == 'Y');
        return 0;
}
 
void ShowVector(int n, double * vec)
{
        for(int i = 0; i < n; i++)
                cout<<vec[i]<<" ";
        cout<<endl;
}
 
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];
        }
}
0
zmei89
32 / 7 / 1
Регистрация: 10.09.2010
Сообщений: 835
03.10.2011, 13:59  [ТС] 33
так же ошибки
0
Миниатюры
Умножение матриц по Винограду  
-=ЮрА=-
Заблокирован
Автор FAQ
03.10.2011, 14:10 34
zmei89, прокрути ползунок ошибок(см миниатюру), я не увидел последней, в проекте есть фатал ерор, каков он, с ворнингами проекты компилятся
0
Миниатюры
Умножение матриц по Винограду  
kazak
3061 / 2382 / 255
Регистрация: 11.03.2009
Сообщений: 5,440
Завершенные тесты: 1
03.10.2011, 14:15 35
Неустранимая ошибка C1010
Сообщение об ошибке:
непредвиденный конец файла во время поиска предкомпилированного заголовка. Возможно, вы забыли добавить директиву "'#include name'" в источник.
Скорее всего на "stdafx.h" ругается, точнее на его отсутствие.

Для разрешения этой ошибки в среде Visual Studio используйте один из следующих методов:

1)Если вы не используете предварительно скомпилированные заголовки, установите для параметра Создавать или использовать предкомпилированный заголовок значение Не использовать предкомпилированный заголовок. Для этого выполните следующее:

В обозревателе решений окна проекта щелкните правой кнопкой мыши имя проекта и выберите Свойства.

В левом окне выберите папку C/C++.

Выберите узел Предкомпилированные заголовки.

В правом окне выберите Создать или использовать предкомпилированный заголовок и щелкните Не использовать предкомпилированный заголовок.

2)Убедитесь, что не был случайно удален, переименован или перемещен файл заголовка (по умолчанию — stdafx.h) из текущего проекта. Этот файл должен быть включен до какого-либо кода в исходном файле с помощью #include "stdafx.h". (Этот файл заголовка указан как свойство проекта Создать или использовать PCH во всем файле.)
0
zmei89
32 / 7 / 1
Регистрация: 10.09.2010
Сообщений: 835
03.10.2011, 14:22  [ТС] 36
fatal error C1010: непредвиденный конец файла во время поиска предкомпилированного заголовка. Возможно, вы забыли добавить директиву "#include "StdAfx.h"" в источник.
1>
0
-=ЮрА=-
Заблокирован
Автор FAQ
03.10.2011, 15:04 37
zmei89, пробуйте с std::
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
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
136
#include "stdafx.h"
#include <iostream>//i/o
#include <conio.h> //getch
#include <cmath>   //fabs, abs
using namespace std;
 
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
        {
                std::cout<<"Enter NUM of equations: ";
                std::cin>>n;
                //Выделяем память под матрицу А и векторы В и Х
                a = new double *[n];
                b = new double  [n];
                x = new double  [n];
                for(i = 0; i < n; i++)
                {
                        a[i] = new double[n];
                        //Ввод a
                        for(j = 0; j < n; j++)
                        {
                                std::cout<<"a["<<i + 1<<"]["<<j + 1<<"] = ";
                                std::cin>>a[i][j];
                        }
                }
                //Ввод b
                for(i = 0; i < n; i++)
                {
                        std::cout<<"b["<<i + 1<<"] = ";
                        std::cin>>b[i];
                }
                
                std::cout<<"\tSee input\r\n";
                std::cout<<"Matrix A:\r\n";
                for(i = 0; i < n; i++)
                        ShowVector(n, a[i]);
                std::cout<<"Vector B:\r\n";
                ShowVector(n, b);
                
                std::cout<<"\tSolving on Gauss method\r\n";
                PryamoiHod(n, a, b);
                std::cout<<"Forvard Gauss course\r\n";//Прямой ход
                std::cout<<"Matrix A:\r\n";
                for(i = 0; i < n; i++)
                        ShowVector(n, a[i]);
                std::cout<<"Vector B:\r\n";
                ShowVector(n, b);
 
                ObratniHod(n, a, b, x);
                std::cout<<"Back Gauss course\r\n";//Обратный ход
                std::cout<<"Matrix A:\r\n";
                for(i = 0; i < n; i++)
                        ShowVector(n, a[i]);
                std::cout<<"Vector B:\r\n";
                ShowVector(n, b);
 
                std::cout<<"Results :\r\n";
                ShowVector(n, x);
 
                std::cout<<"Press Y for new input\r\n";
                //Чистим память
                delete [] a;
                delete [] b;
                delete [] x;
        }
        while(toupper(getch()) == 'Y');
        return 0;
}
 
void ShowVector(int n, double * vec)
{
        for(int i = 0; i < n; i++)
                std::cout<<vec[i]<<" ";
        std::cout<<endl;
}
 
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(abs(a[im][k]) < abs(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];
        }
}
1
zmei89
32 / 7 / 1
Регистрация: 10.09.2010
Сообщений: 835
05.10.2011, 16:51  [ТС] 38
а можете не много пояснить код просто не все понятно
0
zmei89
32 / 7 / 1
Регистрация: 10.09.2010
Сообщений: 835
28.11.2011, 16:40  [ТС] 39
а как применить для кода программы
включить в функциональность программы оценку времени выполнения алгоритма;
оценить время работы алгоритма для матриц размерностей от 5 на 5 (верхний предел может быть больше), результаты измерений записать в файл; при этом время теста должно быть соизмеримо со временем принятия лабораторной работы;
на основании данных теста из файла вывести график зависимости времени работы программы от размерности матрицы, сделать выводы все файле Excele должно быть
0
28.11.2011, 16:40
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
28.11.2011, 16:40

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

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

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


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

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

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