Алгоритм Штрассена

Использование правил блочного произведения матриц позволяет уменьшить общее количество операций, а значит, и время выполнения работы программы. Допустим, требуется умножить квадратные матрицы A и B порядка . При перемножении матриц, по формулам, приведённым в определении произведения, потребуется умножений и сложений. Разобьём матрицы A и B на блоки порядка n. Вычисление произведения блочных матриц проведём по формулам Штрассена

1. потребуется умножений и сложений

2. потребуется умножений и сложений

3. потребуется умножений и сложений

4. потребуется умножений и сложений

5. потребуется умножений и сложений

6. потребуется умножений и сложений

7. потребуется умножений и сложений

8. потребуется сложений

9. потребуется сложений

10. потребуется сложений

11. потребуется сложений.

Всего, для вычисления произведения матриц по формулам Штрассена, потребуется операций сложения и умножения. При выполнении неравенства (n>7) формулы Штрассена приводят к меньшему объёму вычислений. Выигрыш в числе операций будет увеличиваться, если при вычислении произведения матриц (шаги1-7) использовать ту же схему.

Обозначим через число операций сложения и умножения, используемых при умножении матриц n-го порядка по формулам Штрассена. Справедлива рекуррентная формула . Положим . Тогда , далее, свернём сумму по формуле суммы членов геометрической прогрессии и заметим. В результате получим . Подставив вместо k его выражение через n () получим ( ).

2. Содержание

   • Натуральные числа
   • Метод математической индукции.
   • Бином Ньютона, треугольник Паскаля
   • Целые числа
   • Рациональные числа
   • Числовые кольца, поля
   • Вещественные числа
   • Поле комплексных чисел
   • Комплексная плоскость.
   • Извлечение корней, корни из единицы
   • Делимость многочленов. Наибольший общий делитель. Алгоритм Евклида. Расширенный алгоритм Евклида.
   • Разложение рациональных функций в сумму дробей.
   • Неприводимый многочлен, его свойства
   • Из вытекает, либо , либо .
   • Если неприводимый многочлен делится на неприводимый многочлен, то они отличаются числовым множителем.
   • Корень многочлена.
   • Интерполяционный многочлен
   • Интерполяционный многочлен в форме Лагранжа
   • Интерполяционный многочлен в форме Ньютона
   • Разложение многочлена над полем рациональных чисел
   • Примитивный многочлен, его свойства
   • Критерий Эйзенштейна
   • Все коэффициенты многочлена f(X), кроме старшего, делятся на p
   • Старший коэффициент не делится на p
   • Свободный член не делится на
   • Метод Кронекера разложения многочлена на неприводимые многочлены над кольцом целых чисел.
   • Рациональные корни.
   • Присоединение корня. Поле разложения многочлена.
   • Формальная производная, ее свойства
   • Производные высоких порядков
   • Интерполяционный многочлен Лагранжа-Сильвестра
   • Формулы Виета
   • Симметрические полиномы
   • Формулы Кардано
   • Способ Феррари
   • Дискриминант
   • Основная теорема Алгебры
   • Разложение многочлена на неприводимые множители над полем вещественных чисел
   • Теорема Штурма
   • Любые два соседних многочлена не имеют общих корней
   • Последний многочлен не имеет вещественных корней.
   • Если в окрестностях корня a многочлена сам многочлен возрастает, то , а если убывает, то
   • Метод Гаусса решения системы линейных уравнений
   • Равносильные преобразования
   • Умножение строки не ненулевое число.
   • Перестановка строк
   • Прибавление к некоторой строке другой строки, умноженной на число.
   • Метод Гаусса.
   • Перестановки
   • Четность перестановок
   • Определитель
   • Свойства определителя
   • Изменит знак при перестановке столбцов
   • Равен нулю, если имеется два одинаковых столбца
   • Не изменится при прибавлении к столбцу другого столбца, умноженного на число.
   • Вычисление определителей произвольных порядков
   • Определитель Вандермонда
   • Теорема Лапласа
   • Умножение матриц
   • Формула Бине-Кощи
   • Операции с матрицами
   • Обратная матрица
   • Правило Крамера
   • Матрица элементарных преобразований
   • Построение обратной матрицы
   • Блочные матрицы
   • Алгоритм Штрассена
   • Кронекерово произведение
   • Формула Фробениуса
   • Линейные пространства.
   • . Линейная зависимость. Теорема о замене. Ранг системы.
   • Конечномерные пространства. Базис. Размерность. Дополнение до базиса. Базис суммы, пересечения.
   • . Прямая сумма подпространств. Проекция.
   • Изменение координат вектора при изменении базиса.
   • Изоморфизм линейных пространств.
   • Задание прямой и плоскости в пространстве. Деление отрезка. Задачи.
   • Ранги матрицы.
   • Общее решение системы линейных уравнений.
   • Двойственное пространство
   • Взаимное расположение линейных многообразий в пространстве.
   • Геометрия на плоскости и в пространстве.
   • Скалярное произведение.
   • Симметричность .
   • Векторное и смешанное произведение.
   • Уравнение прямой и плоскости в пространстве
   • Евклидово пространство. Скалярное произведение.
   • Изменение матрицы Грама при изменении базиса.
   • Ортогональность.