[Математика, Научно-популярное] Матричное умножение. Медленное достижение мифической цели (перевод)
Автор
Сообщение
news_bot ®
Стаж: 6 лет 4 месяца
Сообщений: 27286
В недавней работе был установлен новый рекорд скорости по умножению двух матриц. Она также знаменует и конец эпохи для метода, который ученые применяли для исследований на протяжении десятилетий.
Математики стремятся к достижению мифической цели — второй степени (exponent two), то есть к умножению пары матриц n х n всего за n2 шагов. Исследователи подбираются все ближе к своей цели, но получится ли у них когда-нибудь достичь ее?
Для специалистов в области Computer Science и математиков сама идея о «второй степени» связана с представлениями о совершенном мире.
«Трудно разграничить научное мышление и беспочвенные мечтания», — признается Крис Уманс из Калифорнийского технологического института. «Я хочу, чтобы степень была равна двум, потому что это красиво».
С точки зрения необходимого количества шагов «вторая степень» — это идеальная скорость выполнения одной из самых фундаментальных математических операций — матричного умножения. Если вторая степень достижима, то матричное умножение получится выполнять максимально быстро, насколько это физически возможно. Если это не так, то мы застряли в мире, который не соответствует нашим мечтам.
Матрицы представляют собой массивы чисел. Когда две матрицы согласованы (число столбцов в первом сомножителе равно числу строк во втором), их можно перемножить, чтобы получить третью. Например, если вы начнете с пары матриц 2 х 2, их произведение также будет матрицей 2 х 2, содержащей четыре элемента. В более общем смысле, произведение пары матриц размером n х n представляет собой другую матрицу размером n х n с n2 элементами.
Поэтому наименьшее возможное количество шагов для умножения пар матриц это n2, то есть количество шагов, необходимое просто для записи ответа. Отсюда и название «вторая степень».
И хотя никто точно не знает, можно ли этого достичь, исследователи продолжают продвигаться в этом направлении.
Статья, опубликованная в октябре, подбирается к цели еще ближе и описывает самый быстрый на данный момент метод умножения двух матриц. Результат, который получили Джош Алман, докторант Гарвардского университета, и Вирджиния Василевска Уильямс из Массачусетского технологического института, уменьшает степень предыдущего лучшего показателя примерно на одну стотысячную. Это действительно большое достижение в данной области, добытое кропотливым трудом.
Чтобы получше разобраться в этом процессе и понять, как его можно усовершенствовать, давайте начнем с пары матриц 2 х 2, A и B. При вычислении каждого элемента их произведения вы используете соответствующую строку из A и соответствующий столбец из B. Чтобы получить верхний правый элемент, умножьте первое число в первой строке A на первое число во втором столбце B, затем умножьте второе число в первой строке A на второе число во втором столбце B и сложите эти два произведения.
Самуэль Веласко / Quanta Magazine
Эта операция известна как получение «скалярного произведения» строки со столбцом (иногда называется «внутренним произведением»). Чтобы вычислить другие элементы в произведении матриц, повторите процедуру с соответствующими строками и столбцами.
В целом, классический метод умножения матриц 2 х 2 состоит из восьми умножений и нескольких сложений. Как правило, этот способ умножения двух матриц размера n х n требует n3 умножений.
С увеличением размера матриц количество умножений, необходимых для нахождения их произведения, растет намного быстрее, чем количество сложений. Чтобы найти произведение матриц 2 х 2 требуется всего восемь промежуточных умножений, а чтобы найти произведение матриц 4 х 4 их требуется уже 64. Однако количество сложений, необходимых для получения суммы этих матриц, не так значительно отличается. Обычно количество сложений равно количеству элементов в матрице, то есть четыре для матриц 2 х 2 и 16 для матриц 4 х 4. Эта разница между сложением и умножением позволяет понять, почему исследователи измеряют скорость умножения матриц исключительно с точки зрения количества требуемых умножений.
«Умножения — это наше всё, — утверждает Уманс, — Показатель степени в итоге полностью зависит только от количества умножений. Сложения в некотором смысле исчезают».
На протяжении веков люди считали, что n3 — это самый быстрый способ умножения матриц. По имеющимся сведениям, в 1969 году Фолькер Штрассен намеревался доказать, что невозможно умножить матрицы 2 х 2, используя менее восьми умножений. Видимо, он все-таки не смог найти доказательства, а через некоторое время и понял почему: на самом деле, существует способ сделать это с помощью семи умножений!
Штрассен придумал сложный набор соотношений, которые позволили заменить одно из этих восьми умножений 14 дополнительными сложениями. Может показаться, что разница совершенно незначительна, но она оправдывает себя, так как умножение вносит больший вклад, чем сложение. Найдя способ избавиться от одного умножения для маленьких матриц 2 х 2, Штрассен открыл возможность, которую он мог использовать при умножении бOльших матриц.
«Это крошечное изменение приводит к огромным улучшениям в работе с большими матрицами», — говорит Уильямс.
Вирджиния Василевска Уильямс из Массачусетского технологического института и Джош Алман из Гарвардского университета открыли самый быстрый способ перемножения двух матриц за n2.3728596 шагов. Джаред Чарни; Ричард Т.К. Хоук
Предположим, вы хотите перемножить пару матриц 8 х 8. Один из способов сделать это — разбить каждую большую матрицу на четыре матрицы размером 4 х 4 так, чтобы каждая имела по четыре элемента. Поскольку элементы матрицы также могут являться матрицами, вы можете считать исходные матрицы парой матриц 2 х 2, каждый из четырех элементов которых сам по себе является матрицей 4 х 4. Посредством некоторых манипуляций каждая из этих матриц размером 4 х 4 может быть разбита на четыре матрицы размером 2 х 2.
Смысл этого многократного разбиения больших матриц на более мелкие заключается в том, что можно снова и снова применять алгоритм Штрассена к меньшим матрицам и с помощью его метода сокращать количество шагов на каждом этапе. В целом алгоритм Штрассена увеличил скорость умножения матриц с n3 до n2.81 мультипликативных шагов.
Следующий важный шаг в развитии идеи произошел в конце 1970-х, когда появился принципиально новый подход к решению этой задачи. Он подразумевает перевод матричного умножения в другую вычислительную задачу линейной алгебры с использованием объектов, называемых тензорами. Тензоры, используемые в этой задаче, представляют собой трехмерные массивы чисел, состоящие из множества различных частей, каждая из которых выглядит как небольшая задача на умножение матриц.
Умножение матриц и эта задача, связанная с тензорами, в определенном смысле эквивалентны друг другу, но для решения последней исследователи уже имели более быстрые процедуры. Таким образом, перед ними встала задача определить «обменный курс» между ними: Матрицы какого размера можно перемножить при тех же вычислительных затратах, которые требуются для решения тензорной задачи?
«Это очень распространенная в теоретической информатике концепция: преобразовывать задачи и проводить аналогию между ними, чтобы показать, что они одинаково простые или сложные», — сказал Алман.
В 1981 году Арнольд Шёнхаге использовал этот подход, чтобы доказать, что умножение матриц возможно выполнить за n2.522 шагов. Позднее Штрассен назвал этот подход «лазерным методом» (laser method).
За последние несколько десятилетий каждое улучшение в процессе умножения матриц происходило за счет усовершенствования лазерного метода, поскольку исследователи находили все более эффективные способы трансформации задачи. В своем новом доказательстве Алман и Уильямс стирают различие между 2 задачами и показывают, что уменьшить число умножений возможно. «В целом Джош и Вирджиния нашли способ применить машинные вычисления в рамках лазерного метода и получили лучшие на настоящий момент результаты», — сказал Генри Кон из Microsoft Research.
В их статье теоретическое ограничение скорости умножения матриц улучшено до n2.3728596.
Также благодаря этому исследованию Уильямс может вернуть себе корону в области матричного умножения, которую она по праву получила в 2012 году (n2.372873), а затем уступила в 2014 году Франсуа Ле Галлю (n2.3728639).
Но, несмотря на все эти гонки и победы, становится ясно, что в случае с этим подходом действует закон убывающей доходности, или убывающей отдачи. Скорее всего, усовершенствование Алмана и Уильямс почти полностью исчерпало возможности лазерного метода, но так и не позволило достичь конечной теоретической цели.
«Маловероятно, что получится приблизиться ко второй степени, используя это семейство методов», — отметил Уманс.
Для этого потребуется открытие новых методов и стойкая вера в то, что это вообще возможно.
Уильямс вспоминает один из разговоров со Штрассеном об этом: «Я спросила его, считает ли он, что возможно получить вторую степень для матричного умножения, и он ответил: «Нет, нет, нет, никогда!».
===========
Источник:
habr.com
===========
===========
Автор оригинала: Kevin Hartnett
===========Похожие новости:
- [Научно-популярное, Космонавтика] Спустя двадцать лет после сведения с орбиты наследие «Мира» живет в современных космических проектах (перевод)
- [Математика, Научно-популярное] Когда прокурор и адвокат в разных метрических пространствах. Случай в Манхэттене
- [Криптография, Математика] Решение 340-символьного шифра Зодиака с помощью Mathematica (перевод)
- [Научно-популярное, Мозг, Здоровье] Выгорание — норма? Часть 3. Моя история выгораний и обучения в процессе
- [Научно-популярное, Астрономия] Что прячет Энцелад в темных водах своего океана? (перевод)
- [Научно-популярное, Мозг] Как я людей на типы делил
- [Научно-популярное, Физика] Как в одном атоме умещается вся физика (перевод)
- [Гаджеты] Тизер от Xiaomi: в новом Mi Mix будет камера с жидкостной линзой (перевод)
- [Open source, Программирование, Геоинформационные сервисы, Визуализация данных, Научно-популярное] Google Earth Engine (GEE) как общедоступный каталог больших геоданных
- [Научно-популярное, Физика, Будущее здесь, Квантовые технологии] Квантовое туннелирование элементарных частиц и сверхсветовые перемещения (перевод)
Теги для поиска: #_matematika (Математика), #_nauchnopopuljarnoe (Научно-популярное), #_matritsy (матрицы), #_umnozhenija_matrits (умножения матриц), #_matematika (математика), #_timeweb, #_metod_shtrassena (метод штрассена), #_blog_kompanii_timeweb (
Блог компании Timeweb
), #_matematika (
Математика
), #_nauchnopopuljarnoe (
Научно-популярное
)
Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете голосовать в опросах
Вы не можете прикреплять файлы к сообщениям
Вы не можете скачивать файлы
Текущее время: 30-Июн 13:21
Часовой пояс: UTC + 5
Автор | Сообщение |
---|---|
news_bot ®
Стаж: 6 лет 4 месяца |
|
В недавней работе был установлен новый рекорд скорости по умножению двух матриц. Она также знаменует и конец эпохи для метода, который ученые применяли для исследований на протяжении десятилетий.
Математики стремятся к достижению мифической цели — второй степени (exponent two), то есть к умножению пары матриц n х n всего за n2 шагов. Исследователи подбираются все ближе к своей цели, но получится ли у них когда-нибудь достичь ее? Для специалистов в области Computer Science и математиков сама идея о «второй степени» связана с представлениями о совершенном мире. «Трудно разграничить научное мышление и беспочвенные мечтания», — признается Крис Уманс из Калифорнийского технологического института. «Я хочу, чтобы степень была равна двум, потому что это красиво». С точки зрения необходимого количества шагов «вторая степень» — это идеальная скорость выполнения одной из самых фундаментальных математических операций — матричного умножения. Если вторая степень достижима, то матричное умножение получится выполнять максимально быстро, насколько это физически возможно. Если это не так, то мы застряли в мире, который не соответствует нашим мечтам. Матрицы представляют собой массивы чисел. Когда две матрицы согласованы (число столбцов в первом сомножителе равно числу строк во втором), их можно перемножить, чтобы получить третью. Например, если вы начнете с пары матриц 2 х 2, их произведение также будет матрицей 2 х 2, содержащей четыре элемента. В более общем смысле, произведение пары матриц размером n х n представляет собой другую матрицу размером n х n с n2 элементами. Поэтому наименьшее возможное количество шагов для умножения пар матриц это n2, то есть количество шагов, необходимое просто для записи ответа. Отсюда и название «вторая степень». И хотя никто точно не знает, можно ли этого достичь, исследователи продолжают продвигаться в этом направлении. Статья, опубликованная в октябре, подбирается к цели еще ближе и описывает самый быстрый на данный момент метод умножения двух матриц. Результат, который получили Джош Алман, докторант Гарвардского университета, и Вирджиния Василевска Уильямс из Массачусетского технологического института, уменьшает степень предыдущего лучшего показателя примерно на одну стотысячную. Это действительно большое достижение в данной области, добытое кропотливым трудом. Чтобы получше разобраться в этом процессе и понять, как его можно усовершенствовать, давайте начнем с пары матриц 2 х 2, A и B. При вычислении каждого элемента их произведения вы используете соответствующую строку из A и соответствующий столбец из B. Чтобы получить верхний правый элемент, умножьте первое число в первой строке A на первое число во втором столбце B, затем умножьте второе число в первой строке A на второе число во втором столбце B и сложите эти два произведения. Самуэль Веласко / Quanta Magazine Эта операция известна как получение «скалярного произведения» строки со столбцом (иногда называется «внутренним произведением»). Чтобы вычислить другие элементы в произведении матриц, повторите процедуру с соответствующими строками и столбцами. В целом, классический метод умножения матриц 2 х 2 состоит из восьми умножений и нескольких сложений. Как правило, этот способ умножения двух матриц размера n х n требует n3 умножений. С увеличением размера матриц количество умножений, необходимых для нахождения их произведения, растет намного быстрее, чем количество сложений. Чтобы найти произведение матриц 2 х 2 требуется всего восемь промежуточных умножений, а чтобы найти произведение матриц 4 х 4 их требуется уже 64. Однако количество сложений, необходимых для получения суммы этих матриц, не так значительно отличается. Обычно количество сложений равно количеству элементов в матрице, то есть четыре для матриц 2 х 2 и 16 для матриц 4 х 4. Эта разница между сложением и умножением позволяет понять, почему исследователи измеряют скорость умножения матриц исключительно с точки зрения количества требуемых умножений. «Умножения — это наше всё, — утверждает Уманс, — Показатель степени в итоге полностью зависит только от количества умножений. Сложения в некотором смысле исчезают». На протяжении веков люди считали, что n3 — это самый быстрый способ умножения матриц. По имеющимся сведениям, в 1969 году Фолькер Штрассен намеревался доказать, что невозможно умножить матрицы 2 х 2, используя менее восьми умножений. Видимо, он все-таки не смог найти доказательства, а через некоторое время и понял почему: на самом деле, существует способ сделать это с помощью семи умножений! Штрассен придумал сложный набор соотношений, которые позволили заменить одно из этих восьми умножений 14 дополнительными сложениями. Может показаться, что разница совершенно незначительна, но она оправдывает себя, так как умножение вносит больший вклад, чем сложение. Найдя способ избавиться от одного умножения для маленьких матриц 2 х 2, Штрассен открыл возможность, которую он мог использовать при умножении бOльших матриц. «Это крошечное изменение приводит к огромным улучшениям в работе с большими матрицами», — говорит Уильямс. Вирджиния Василевска Уильямс из Массачусетского технологического института и Джош Алман из Гарвардского университета открыли самый быстрый способ перемножения двух матриц за n2.3728596 шагов. Джаред Чарни; Ричард Т.К. Хоук Предположим, вы хотите перемножить пару матриц 8 х 8. Один из способов сделать это — разбить каждую большую матрицу на четыре матрицы размером 4 х 4 так, чтобы каждая имела по четыре элемента. Поскольку элементы матрицы также могут являться матрицами, вы можете считать исходные матрицы парой матриц 2 х 2, каждый из четырех элементов которых сам по себе является матрицей 4 х 4. Посредством некоторых манипуляций каждая из этих матриц размером 4 х 4 может быть разбита на четыре матрицы размером 2 х 2. Смысл этого многократного разбиения больших матриц на более мелкие заключается в том, что можно снова и снова применять алгоритм Штрассена к меньшим матрицам и с помощью его метода сокращать количество шагов на каждом этапе. В целом алгоритм Штрассена увеличил скорость умножения матриц с n3 до n2.81 мультипликативных шагов. Следующий важный шаг в развитии идеи произошел в конце 1970-х, когда появился принципиально новый подход к решению этой задачи. Он подразумевает перевод матричного умножения в другую вычислительную задачу линейной алгебры с использованием объектов, называемых тензорами. Тензоры, используемые в этой задаче, представляют собой трехмерные массивы чисел, состоящие из множества различных частей, каждая из которых выглядит как небольшая задача на умножение матриц. Умножение матриц и эта задача, связанная с тензорами, в определенном смысле эквивалентны друг другу, но для решения последней исследователи уже имели более быстрые процедуры. Таким образом, перед ними встала задача определить «обменный курс» между ними: Матрицы какого размера можно перемножить при тех же вычислительных затратах, которые требуются для решения тензорной задачи? «Это очень распространенная в теоретической информатике концепция: преобразовывать задачи и проводить аналогию между ними, чтобы показать, что они одинаково простые или сложные», — сказал Алман.
В 1981 году Арнольд Шёнхаге использовал этот подход, чтобы доказать, что умножение матриц возможно выполнить за n2.522 шагов. Позднее Штрассен назвал этот подход «лазерным методом» (laser method). За последние несколько десятилетий каждое улучшение в процессе умножения матриц происходило за счет усовершенствования лазерного метода, поскольку исследователи находили все более эффективные способы трансформации задачи. В своем новом доказательстве Алман и Уильямс стирают различие между 2 задачами и показывают, что уменьшить число умножений возможно. «В целом Джош и Вирджиния нашли способ применить машинные вычисления в рамках лазерного метода и получили лучшие на настоящий момент результаты», — сказал Генри Кон из Microsoft Research. В их статье теоретическое ограничение скорости умножения матриц улучшено до n2.3728596. Также благодаря этому исследованию Уильямс может вернуть себе корону в области матричного умножения, которую она по праву получила в 2012 году (n2.372873), а затем уступила в 2014 году Франсуа Ле Галлю (n2.3728639). Но, несмотря на все эти гонки и победы, становится ясно, что в случае с этим подходом действует закон убывающей доходности, или убывающей отдачи. Скорее всего, усовершенствование Алмана и Уильямс почти полностью исчерпало возможности лазерного метода, но так и не позволило достичь конечной теоретической цели. «Маловероятно, что получится приблизиться ко второй степени, используя это семейство методов», — отметил Уманс. Для этого потребуется открытие новых методов и стойкая вера в то, что это вообще возможно. Уильямс вспоминает один из разговоров со Штрассеном об этом: «Я спросила его, считает ли он, что возможно получить вторую степень для матричного умножения, и он ответил: «Нет, нет, нет, никогда!». =========== Источник: habr.com =========== =========== Автор оригинала: Kevin Hartnett ===========Похожие новости:
Блог компании Timeweb ), #_matematika ( Математика ), #_nauchnopopuljarnoe ( Научно-популярное ) |
|
Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете голосовать в опросах
Вы не можете прикреплять файлы к сообщениям
Вы не можете скачивать файлы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете голосовать в опросах
Вы не можете прикреплять файлы к сообщениям
Вы не можете скачивать файлы
Текущее время: 30-Июн 13:21
Часовой пояс: UTC + 5