Вопрос:
Существует ли установленная процедура или теория для генерации кода, который эффективно применяет умножение матрицы на вектор, когда матрица плотна и заполнена только нулями и единицами? В идеале оптимизированный код должен систематически использовать ранее вычисленную информацию для сокращения дублируемой работы.
Другими словами, у меня есть матрица и я хочу выполнить некоторые предварительные вычисления на основе , которые сделают вычисление максимально эффективным, когда я позже получу вектор .
является прямоугольной плотной двоичной матрицей, которая известна во время компиляции, тогда как является неизвестным вещественным вектором, который известен только во время выполнения.
Пример 1: (раздвижное окно)
Позвольте мне использовать простой небольшой пример, чтобы проиллюстрировать мою точку зрения. Рассмотрим матрицу
Выполнение стандартного умножения матрицы на вектор будет вычислено именно таким образом. Однако большая часть этой работы является излишней. Мы могли бы сделать то же матричное вычисление с меньшими затратами, отслеживая «промежуточный итог» и добавляя / вычитая, чтобы получить следующее число:
Пример 2: (иерархическая структура)
В предыдущем примере мы могли просто отслеживать итоговую сумму. Однако обычно нужно создать и сохранить дерево промежуточных результатов. Например, рассмотрим Можно эффективно вычислитьw=Mv,используя дерево промежуточных результатов:
- Вычислите и w 7 и сложите их, чтобы получить w 3 .
- Вычислите и w 6 и сложите их, чтобы получить w 2 .
- Добавьте и w 3, чтобы получить w 1
Структуру в приведенных выше примерах легко увидеть, но для интересующих меня матриц структура не так проста.
Пример 3: (низкий ранг)
Чтобы устранить некоторую путаницу, матрицы, как правило, не разрежены. В частности, метод, решающий эту проблему, должен быть в состоянии найти эффективные методы для применения матриц, где большие блоки заполнены единицами. Например, рассмотрим
Эта матрица может быть разложена как разность двух матриц ранга 1,
поэтому его действие на вектор может быть эффективно вычислено с помощью w 1
Мотивация:
Я работаю над численным методом для некоторой обработки изображений, и есть несколько больших плотных матриц с различными структурами, которые зафиксированы на все времена. Позже эти матрицы нужно будет применить ко многим неизвестным векторам v i, которые будут зависеть от ввода пользователя. Сейчас я использую карандаш и бумагу, чтобы придумать эффективный код для каждой матрицы, но мне интересно, можно ли автоматизировать этот процесс.
Изменить: (постскриптум)
Все ответы здесь (по состоянию на 05.09.15) интересны, но ни один из них не отвечает на вопрос так же удовлетворительно, как я надеялся. Вероятно, получается, что это сложный исследовательский вопрос, и никто не знает хорошего ответа.
Поскольку время истекло, я присуждаю награду за ответ EvilJS, поскольку он отвечает на правильный вопрос. Однако я хотел бы, чтобы ответ содержал более четкие и подробные объяснения.
Ответ tranisstor устанавливает связь между этим вопросом и проблемой онлайнового булево-матричного умножения (OMv), но эта связь не совсем то, что задает этот вопрос. В частности, следующее предположение не совсем подходит (жирный акцент мой),
Теперь предположим, что для всех и всех n × n матриц M мы знаем алгоритм , который для всех векторов v вычисляет M v за действительно субквадратичное время, т.е. за время O ( n 2 - ε ) для некоторого ε > 0 .
Существуют или нет субквадратичные алгоритмы для всех матриц, ортогонально вопросу о поиске алгоритма для конкретной матрицы, который будет максимально быстрым. Большинство матриц 0-1 выглядят как случайный шум и (если я угадал), вероятно, не имеют субквадратичных алгоритмов. Однако тот факт, что существуют действительно плохие матрицы, не мешает мне найти быстрый алгоритм на хорошей матрице, например, матрице «скользящего окна».
Ответы vzn, первый ответ , второй ответ интересны (и, по моему мнению, не заслуживают такого большого количества отрицательных голосов), но они не относятся к вопросу по причинам, обсуждаемым в комментариях.
источник
Ответы:
Если это возможно, попробуйте использовать полосатую трехдиагональную природу матрицы.
В противном случае, если матрица содержит только постоянное число различных значений (что, безусловно, является двоичным), вам следует попробовать алгоритм Mailman (Эдо Либерти, Стивен У. Цукер, в техническом отчете Йельского университета # 1402): оптимизирован для конечного словаря.
Распространенное устранение общего выражения известно в течение некоторого времени, как множественное умножение констант, но вариант перехода на уровень гейта является опцией - используемые здесь шаблоны могут использоваться отдельно в качестве решения или объединяться с другими методами, статья для этого «Улучшение устранения общего подвыражения» Алгоритм с новым методом вычисления задержки на уровне затвора »Нин Ву, Сяоцян Чжан, Юньфэй Е. и Лидонг Лан, опубликованные в« Трудах Всемирного конгресса по инженерным наукам и информатике 2013, том II WCECS 2013, 23-25 октября 2013 г., Сан-Франциско, США " CSE уровня ворот"
Существует также грубый, но работающий метод: генерировать символьную матрицу с константами, вектор с переменными и подключать ее к статическому одиночному назначению (SSA) из компиляторов, что автоматизирует процесс написания матриц вручную.
прототип нового алгоритма
Что вы сделали с суммой: Дает 10операций, и с моей первоначальной идеей использовать Томаса это эквивалентно. На данный момент я все еще пишу и тестирую новый алгоритм, также время выполнениянеприятно, но первый результат теста дал мне неожиданный ответ:
что дает 9операций, определяя их как + или - равно 1, а = равно 0.
Это дает 7 операций , мой алгоритм дал результат:
Что дает 6операций. Пока я могу сказать, что использую расстояние Хэмминга, и и | побитовые операции, подсчет использований и создание чего-то вроде Cocke – Younger – Kasami (CYK) - «алгоритм синтаксического анализа для контекстно-свободных грамматик, названный в честь его изобретателей, John Cocke, Daniel Younger и Tadao Kasami. Он использует анализ снизу вверх и динамический анализ программирование «. - из Википедии Это та же техника, которую я использую для создания блоков переменных.
источник
Это связано с открытым вопросом исследования, который известен как «проблема умножения матриц-векторов (OMv) онлайн». Эта проблема гласит следующее (см. [1]): Учитывая двоичную матрицу M и n двоичных векторов столбцов v 1 , … , v n , нам нужно вычислить M v i до того, как прибудет v i + 1 .n×n M n v1,…,vn Mvi vi+1
Обратите внимание, что проблема из вопроса несколько более общая: она учитывает матрицы и действительные векторы. Заметьте, что проблема с n × n матрицами и булевыми векторами «проще», поскольку она представляет собой особый случай.m×n n×n
Ясно, что наивный алгоритм для задачи онлайн-булевого умножения матрицы на вектор (в котором просто используется стандартное умножение матрицы на вектор) занимает время . Существует предположение (см., Например, [1]), что это не может быть сделано действительно быстрее, чем O ( n 3 ) . (Более подробно, эта гипотеза выглядит следующим образом: не существует по-настоящему субкубического алгоритма, который решает проблему умножения матрицы на вектор в режиме онлайн, т. Е. Не существует алгоритма со временем O ( n 3 - ε ) для ε > 0 ).O(n3) O(n3) O(n3−ε) ε>0
Известно, что алгоритм Уильямса решает эту проблему за время . Смотрите [2] для более подробной информации.O(n3/log2n)
Это был бы прорыв в области условных нижних границ, если бы можно было доказать или опровергнуть приведенную выше гипотезу.
[1] Унификация и усиление твердости для динамических задач с помощью онлайн-гипотезы умножения матрицы на вектор. Хензингер, Криннингер, Нанонгкай и Саранурак
[ http://eprints.cs.univie.ac.at/4351/1/OMv_conjecture.pdf ]
[2] Матрично-векторное умножение в субквадратичном времени: (требуется некоторая предварительная обработка). Уильямс
[ http://dl.acm.org/citation.cfm?id=1283383.1283490 ]
Обновить
Один из вопросов в комментариях был следующим: мы знаем во время компиляции. Разве мы не можем настроить наш алгоритм в соответствии с M , поэтому проблема OMv (гипотеза) не применима? Мы увидим, что это не так, если только гипотеза OMv не удастся.M M
Идея доказательства проста: предположим, мы могли бы дать быстрые алгоритмы для всех матриц до некоторого определенного размера (например, различая все возможные случаи). После этого определенного размера мы используем разделяй и властвуй.
Вывод: Если бы вы могли использовать различия в регистрах входных матриц для выведения быстрых алгоритмов, вы могли бы улучшить гипотезу OMv.
источник
По сути, это КС исследовательского уровня, проблема изучается, по крайней мере, в двух вариантах: в одном умножение разреженных матриц (только что приведенный пример), а также частный случай «двоичных разреженных матриц». 2 - й случай , как известно, связаны с оптимизацией программ прямолинейные. минимальные программы также могут быть похожи на DAG с двумя типами «ворот», сложением и умножением, поэтому с этим может быть связана некоторая литература по минимизации схем, и, возможно, «готовое» программное обеспечение может быть адаптировано для этой цели. здесь есть конкретная ссылка на 2- й случай, а также тот же вопрос о теории с некоторым базовым начальным эмпирическим исследованием.
Представление разреженных двоичных матриц как прямолинейных программ для быстрого умножения матриц-векторов / Neves, Araujo
Быстроразреженный логический матричный цепочечный продукт / cstheory
источник
Не уверен, что эта проблема была точно изучена, но это исследование связано и кажется разумным началом / началом. это смотрит на разложение гиперграфа для умножения разреженной матрицы. двоичные матрицы являются частным случаем этого подхода. этот подход найдет более оптимальные стратегии, чем «прямой» метод умножения. дальнейшая оптимизация (в рамках этой структуры) может быть возможной на основе свойства двоичной матрицы.
источник