Умножение матриц – алгоритм Штрассена Решаемая задача – вычисление произведения матриц A B при больших A и B. Предполагаем, что обе матрицы – квадратные,

Презентация:

Advertisements

Похожие презентации

Р е ш е н и е к в а д р а т н ы х у р а в н е н и й п о о с н о в н о й ф о р м у л е.

Advertisements

Алгоритм решения квадратного уравнения Чтобы решить квадратное уравнение, достаточно: 1) вычислить дискриминант и сравнить его с нулем; 2) если дискриминант.

1. Найдите площадь треугольника ABC, считая стороны квадратных клеток равными 1. Ответ. 9. Решение 2. Проведем высоту AH. Тогда BC = 6, AH = 3 и, следовательно,.

Работа с матрицами Задача 1. Выполните действия с матрицами.

М о с к в а – Что обозначает 1 множитель?2. Что обозначает 2 множитель? 3. Записать в виде суммы и вычислить: 17 2 = 3 10 = 7 4 = 4. Представить.

Метод умножения (или деления) уравнения на функцию.

«Логарифмы и их свойства» Урок алгебры и начала анализа в 11 классе по теме: «Логарифмы и их свойства» Учитель математики МОУ Верхнетойденской СОШ Уварова.

Логарифм произведения Вычислить устно: Вычислить: 1) 3)

Линейная алгебра Матрицы. Основные понятия. Действия над матрицами Метод обратной матрицы решения систем линейных уравнений.

Однородные уравнения 10 класс.

Цель: знакомство с матричным способом кодирования и декодирования информации. Задачи: изучить понятия: матрица; кодирующая матрица; произведение матриц.

Степень с отрицательным целым показателем Вычислите 5 = 12 · 3 = (27 · 3 ) = = 16 · 2 = (64 · 4 ) =

1© Богомолова ОМ. 1. Найдите площадь ΔABC, считая стороны квадратных клеток равными 1 2 Ответ: 9 Решение Проведем высоту AH. Тогда BC = 6, AH = 3 и, следовательно,

Рациональные уравнения это уравнения, в которых правая и левая части являются рациональными выражениями. Рациональными выражениями называют.

Тема 1 «Элементы линейной и векторной алгебры» Кафедра математики и моделирования Старший преподаватель Г.В. Аверкова Курс «Высшая математика» Понятия.

Системы двух уравнений с двумя переменными Каждая пара значений переменных, образующая в верное равенство каждое уравнение системы, называется решением.

Системы уравнений Системы уравнений Метод сложения.

1 3. Системы линейных уравнений. Леопо́льд Кро́некер.

Презентация к уроку по алгебре (10 класс) по теме: Системы тригонометрических уравнений

2. Составьте алгоритм на алгоритмическом языке и программу на языке Паскаль вычисления У по формуле: Самостоятельная работа 1. Составьте алгоритм на алгоритмическом.

Транксрипт:

Умножение матриц – алгоритм Штрассена Решаемая задача – вычисление произведения матриц A B при больших A и B. Предполагаем, что обе матрицы – квадратные, размера n n. Предположим, что n – степень двойки. Тогда можно воспользоваться следующим рекурсивным алгоритмом: Эффективность (число умножений) T(n) этого алгоритма можно вычислить: T(1) = 1; T(n) = 8T(n/2), откуда получаем T(n) = n 3 = n log 8. Формулы для приведенного выше алгоритма: P 1 = A 1 B 1 ; P 2 = A 2 B 2 ; P 3 = A 3 B 3 ; P 4 = A 4 B 4 ; P 5 = A 5 B 5 ; P 6 = A 6 B 6 ; P 7 = A 7 B 7 ; P 8 = A 8 B 8 ; r = P 1 + P 2 ; s = P 3 + P 4 ; t = P 5 + P 6 ; u = P 7 + P 8 ; Всего 8 матричных умножений и 4 матричных сложения. Алгоритм Штрассена позволяет уменьшить асимптотическую оценку до T(n) = n log 7 С помощью уменьшения количества необходимых промежуточных матриц P i.

Умножение матриц – алгоритм Штрассена (продолжение) iAiAi BiBi P i = A i B i 1ag hag ah 2a + bhah + bh 3c + dece + de 4df edf de 5a + de + hae + ah + de + dh 6b df + hbf + bh df dh 7a ce + gae + ag ce cg r = P4 P2 + P5 + P6 = ae + bf s = P1 + P2 = ag + bh t = P3 + P4 = ce + df u = P1 + P5 P3 P7 = cg + dh В этом алгоритме потребовалось 7 матричных умножений и 18 сложений

Умножение матриц – алгоритм Штрассена (обсуждение) 1.Как модифицировать алгоритм для случая, когда n не является степенью двойки? Ответ: дополняем исходные матрицы до нужной размерности и обрезаем результат. 2.Что лучше: 8 умножений и 4 сложения или 7 умножений и 18 сложений? Ответ: асимптотически лучше алгоритм Штрассена, но для матриц небольшого размера лучше использовать традиционное умножение. 3.Когда следует на практике применять алгоритм Штрассена? Ответ: для перемножения больших плотных (не разреженных) матриц размерности не меньше 64.