2001-gre-vs-practice.pdf/Q39

Ссылки сюда (1) →

Вопрос: Q39-e5724f

Для вычисления матричного произведения и ,

• где содержит p-строк и q столбцов,
•  — q строк и r столбцов,
• требуется время, пропорциональное p × q × r , и в результате получается матрица из p строк и r столбцов.
  • алгоритм Штрассена или алгоритм Копперсмита-Винограда не рассматриваем.

Рассмотрим произведение трех матриц

•  — w строк и x столбцов
•  — x строк и y столбцов
•  — y строк и z столбцов.

При каком условии потребуется меньше времени, чтобы вычислить произведение как ( × ) × , (то есть сначала умножить первые две матрицы), или быстрее вычислить его как × ( × )?

Ответы

• Нет такого условия, время всегда будет одним и тем же.
• Правильный ответ:

Объяснение

Исходники — вопрос 39 на 33 странице книги «2001-gre-vs-practice.pdf»

Оценим сколько времени нужно на умножение ( × ) × .

На всякий случай, повод вспомнить стандартный механизм умножения двух матриц (скажем × ).

• Для каждого элемента результирующей матрицы, которая будет иметь размер w × y необходимо вычислить скалярное произведение строки из первой и столбца из второй.
• Каждое скалярное произведение включает x умножений и x - 1 сложений.
• Общее количество операций равно:

Умножение ( × ) пропорционально wy, получается матрица размера w × y. Далее результат умножается на . Время умножения пропорционально wyz.

Таким образом, первое умножение пропорционально wxy + wyz.

Аналогичными рассуждениями получаем, что умножение вторым способом пропорционально xyz + wxz.

По условию, первый способ должен занимать меньше времени, составим неравенство:

wxy + wyz < xyz + wxz

Разделим обе части на wxyz.

Получим неравенство .

[ Хронологический вид ]Комментарии

(нет элементов)

Войдите, чтобы комментировать.