Титульный лист

Титульный лист
Содержание
Введение

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

Примерами более эффективных алгоритмов умножения матриц являются:
- алгоритм Штрассена;
- алгоритм Пана;
- алгоритм Бини;
- алгоритмы Шёнхаге;
- алгоритм Копперсмита – Винограда.
В рамках курсовой работы необходимо разработать программу реализующую модифицированный алгоритм Штрассена для перемножения матриц.
Для достижения поставленной цели необходимо:
-изучить алгоритм Штрассена и его модифицированную версию;
-разработать структуры данных для хранения матриц;
-разработать функции для решения поставленной задачи и реализовать их на языке С++;
-выполнить сравнение быстродействия разработанного алгоритма с алгоритмом классического перемножения матриц.
1. Описание используемого алгоритма

Алгоритм Штрассена предназначен для быстрого умножения матриц. Он был разработан Фолькером Штрассеном в 1969 году и является обобщением метода умножения Карацубы на матрицы.

В отличие от традиционного алгоритма умножения матриц (по формуле , работающего за время , алгоритм Штрассена умножает матрицы за время , что даёт выигрыш на больших плотных матрицах.
Несмотря на то, что алгоритм Штрассена является асимптотически не самым быстрым из существующих алгоритмов быстрого умножения матриц, он проще программируется и эффективнее при умножении матриц относительно малого размера, поэтому именно он чаще используется на практике.
Пусть A, B - две квадратные матрицы над кольцом R. Матрица C получается по формуле:
, где .
Если размер умножаемых матриц n не является натуральной степенью двойки, исходные матрицы необходимо дополнить дополнительными нулевыми строками и столбцами. При этом нужно получить удобные для рекурсивного умножения размеры, но теряем в эффективности за счёт дополнительных ненужных умножений.