Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Множення матриць за алгоритмом Винограда
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
КН
Кафедра:
Кафедра ЕОМ
Інформація про роботу
Рік:
2016
Тип роботи:
Лабораторна робота
Предмет:
Алгоритми та методи обчислень
Частина тексту файла (без зображень, графіків і формул):
МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА”
Кафедра ЕОМ
/
ЗВІТ
з лабораторної роботи № 7
з дисципліни: “Алгоритми та методи обчислень”
на тему: “ Множення матриць за алгоритмом Винограда ”
Мета роботи: навчитися будувати складні алгоритми.
Теоретичні відомості:
Алгоритм Винограда призначений для швидкого множення матриць. Він був розроблений Фолькером Виноградом в 1969 році і є узагальненням методу множення Карацуби на матриці. Цей алгоритм дозволяє швидше за стандартний спосіб множити матриці. На практиці це відчутно на великих матрицях, але існує ще більш швидкий алгоритм Копперсміта-Винограда[en] для множення дуже великих матриць.
На відміну від традиційного алгоритму множення матриць (за формулою /), який виконується за час /, алгоритм Штрассена множить матриці за час /, що дає виграш на великих щільних матрицях починаючи, приблизно, з матриць розміру 64 × 64.
Існує модифікація алгоритму Штрассена, для якого вимагається 7 множень та 15 додавань (замість18для звичайного алгоритму Штрассена). Матриці A,B і C діляться на блокові підматриці.
Обчислюються проміжні матриціS1 —S8,P1 —P7,T1 —T2
/
/
/
/
/
/
/
/
/
/
/
/
/
/
/
/
/
Елементи матриці C обчислюються за формулами
/
/
/
/
Завдання:
Реалізувати множення матриць за алгоритмом Винограда.
Код програми
#include <iostream>
#include <ctime>
using namespace std;
int main()
{
setlocale(0, "UKR");
srand(time(NULL));
const int a = 2, b = 5, c = 3;
int d = b / 2;
int G[a][b];
int H[b][c];
int R[a][c];
int rowFactor[a];
int columnFactor[c];
//заповнення матриць
for (int i = 0; i < a; ++i) {
for (int j = 0; j < b; ++j) {
G[i][j] = rand() % 10;
}
}
for (int i = 0; i < b; ++i) {
for (int j = 0; j < c; ++j) {
H[i][j] = rand() % 10;
}
}
// вивід матриць
cout << "I матриця:\n";
for (int i = 0; i < a; ++i) {
for (int j = 0; j < b; ++j) {
cout << G[i][j] << " ";
}
cout << endl;
}
cout << "\nII матриця:\n";
for (int i = 0; i < b; ++i) {
for (int j = 0; j < c; ++j) {
cout << H[i][j] << " ";
}
cout << endl;
}
// обчислення rowFactors для G
for (int i = 0; i < a; ++i) {
rowFactor[i] = G[i][0] * G[i][1];
for (int j = 1; j < d; ++j) {
rowFactor[i] = rowFactor[i] + G[i][2 * j - 1] * G[i][2 * j];
}
}
cout << "\nФактори рядка для G:\n";
for (int i = 0; i < a; ++i) {
cout << rowFactor[i] << " ";
}
cout << endl;
// вобчислення columnFactors для H
for (int i = 0; i < c; ++i) {
columnFactor[i] = H[0][i] * H[1][i];
for (int j = 1; j < d; ++j) {
columnFactor[i] = columnFactor[i] + H[2 * j - 1][i] * H[2 * j][i];
}
}
cout << "\nФактори колонки для H:\n";
for (int i = 0; i < c; ++i) {
cout << columnFactor[i] << " ";
}
cout << endl;
// обрахунок матриці R
for (int i = 0; i < a; ++i) {
for (int j = 0; j < c; ++j) {
R[i][j] = -rowFactor[i] - columnFactor[j];
for (int k = 1; k < d; ++k) {
R[i][j] = R[i][j] + (G[i][2 * k - 1] + H[2 * k][j]) * (G[i][2 * k] + H[2 * k - 1][j]);
}
}
}
cout << "\nРезультат множення:\n";
for (int i = 0; i < a; ++i) {
for (int j = 0; j < c; ++j) {
cout << R[i][j] << "\t";
}
cout << endl;
}
system("pause");
return 0;
}
/
Рис.1 Результат виконання програми
Висновок: На даній лабораторній роботі я навчилася реалізовувати множення матриць методом Винограда.
10.10.2017 22:10-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора