Выбор ответа Senior Векторы и матрицы обновлено
Стоимость умножения матриц
Вопрос
Сколько умножений чисел делает обычный алгоритм произведения матрицы n×m на матрицу m×k, и что из этого следует для цепочки A·B·x, где A и B размером 1000×1000, а x вектор длины 1000?
Попробуйте сами
Выберите вариант, и откроется разбор.
Показать ответ и разбор
Коротко
Правильный ответ: n·m·k; выгоднее считать A·(B·x): около 2 млн умножений против миллиарда. Каждый из n·k элементов результата это скалярное произведение длины m: итого n·m·k умножений.
Варианты ответа
- n·m·k; выгоднее считать A·(B·x): около 2 млн умножений против миллиардаправильный ответ
- n·k; порядок скобок не важен, ответ и стоимость одинаковы
- n·m + m·k; выгоднее (A·B)·x, потому что AB можно закешировать
- n·m·k; выгоднее (A·B)·x, потому что умножение матриц хорошо параллелится
Разбор
Каждый из n·k элементов результата это скалярное произведение длины m: итого n·m·k умножений. (A·B)·x стоит 10⁹ + 10⁶, а A·(B·x) два умножения матрицы на вектор по 10⁶. Ответ одинаков (ассоциативность), а цена различается в 500 раз. Тот же приём в LoRA: (B·A)·x не собирают, считают B·(A·x).
- n·k это число элементов результата, а не число умножений.
- n·m + m·k занижает стоимость, и кешировать AB имеет смысл, только если x много и A, B не меняются.
- Параллелизм не отменяет того, что работы в 500 раз больше.
Ответьте сами, а не прочитайте
В тренажёре вопрос попадёт в повторения и вернётся, когда начнёт забываться. Плюс билеты с зачётом: 20 вопросов, не больше 2 ошибок.
Термины по теме
Ещё по теме «Векторы и матрицы»
- Косинусная близость
- Решить систему методом Гаусса
- Умножение матриц на списках
- Косинусная близость против евклидова расстояния
- Скалярное произведение равно нулю
- Определитель и произведение 2×2
- Посчитайте скалярное произведение и норму
- Мультиколлинеарность глазами линала