Матрица           

            Впервые за последние 24 года некий прогресс в перемножении матриц. «Все это чрезвычайно увлекательно, и является одним из лучших результатов в теории за многие годы», — пишет в своем блоге Ричард Липтон, специалист по вычислительной технике из Технологического института Джоржии в Атланте. Его коллега, еще один блоггер и ученый в области вычислительной техники, Скотт Ааронсон из Массачусетского Технологического признается: «Вообще-то, я знал об этом еще месяц назад – и мне немалых трудов стоило сохранить все в секрете».

            Перемножение матриц – одна из основных математических операций для решения задач в физике (см. например), экономике, да и вообще в большей части естественных наук. Это конечно, не бытовая арифметика вроде перемножения чисел, но лишь слегка менее фундаментальный процесс в математике. И хотя новый метод и нельзя применить в современных компьютерах, но это неожиданное достижение в области теории может однажды найти себе массу применений, — и некоторая часть математического сообщества всерьез возбуждена сюрпризом.  

            Матрица – это таблица из чисел, а перемножение матриц – это определенный способ, с помощью которого из двух матриц можно получить третью. Источником проблем здесь выступает необходимость проделывать множество обычных перемножений чисел. Простейший способ перемножения двух матриц размером NхN (с N строк и N столбцов) включает в себя N3 таких шагов. Таким образом, перемножение двух сравнительно небольших матриц 100х100 требует миллиона перемножений чисел. Конечно, математики не могли с этим смириться, и вот, в 1969 году Волкер Штрассен открыл алгоритм, который позволяет обойтись N2.807-ю шагами.

            Итак, обычно перемножение матриц выполняется либо простым N3-способом, либо с использованием алгоритма Штрассена, который более сложен, но и более эффективен для больших матриц. Но, вполне естественно, что теоретики перепробовали множество других путей сокращения числа вычислительных шагов, результат которого в конечном итоге выражается в снижении показателя степени у N. Наконец, в 1987 году поиски завершились алгоритмом, который оставался наибыстрейшим 24 года. Его предложили Дон Копперсмит и Шмуэль Виноград, и показатель степени, называемый также «омегой», оказался равен 2.376.

            Вообще говоря, этот результат вызывает законное удивление. Трудно представить себе что-то более простое, чем простой способ перемножения матриц с омегой, равной 3.00. И как-то сократить здесь путь кажется настолько же невероятным, как построить кривую, вдоль которой движение происходит быстрее, чем по прямой. В физике это возможно, но и математикам, выходит, это удалось. Как говорится, ловкость рук и никакого мошенничества. Предполагалось, что улучшить этот результат дальше не удастся.

            И вот теперь, Вирджиния Василевска-Уильямс, занятая одновременно на двух работах – в  в Калифорнийском Университете в Беркли и в Стэнфордском Университете, показала, что это предположение неверно. Ей удалось подстроить алгоритм так, что омега упала до 2.373.

            С одной стороны, три тысячных – не так уж много. Но, как нетрудно убедиться, для двух десяти- или стотысячных матриц это даст снижение числа перемножений примерно на 3 процента, что уже вполне ощутимо. Однако, интересен и сам способ улучшения алгоритма.

            Идея, на самом деле, уже была использована в изначальном методе Копперсмита-Винограда, который включает в себя применение начального алгоритма два раза подряд. Проблема состояла в том, что применение алгоритма трижды, казалось, не давало никакого выигрыша. «Это привело к уверенности, что более высокие степени рекурсии также не дадут улучшения», — объясняет Василевска-Вильямс, — так что теоретики сдались. Каждое приложение алгоритма требует решения возрастающего числа сложных уравнений, и без какой-либо компенсации на выходе, эта тяжелая работа казалась нестоящей труда.

            Затем, в 2010, Андрю Стотерз из Эдинбургского Университета, попробовал использовать алгоритм четырежды, — в качестве части своей диссертации, — но не упомянул о результатах в описании своей работы.  Естественно, что широкая математическая общественность ничего не заметила; он же оставил исследовательскую работу и перешел в финансовую службу. Сейчас он говорит, что не разгласил о своих результатах ненамеренно.

            Когда Василевска-Уильямс, работавшая независимо, наткнулась на диссертацию Стотерза, она поняла, что может использовать часть его работы. Она применила начальный алгоритм восемь раз, и получила конечное омега равным 2.373.

            Встает вопрос: стоит ли приходить в восторг от столь малого улучшения? «Да, потому что этот рекорд держался так долго, и многие работали над этим», — заявляет Уильям Гасарч, специалист по вычислительной технике из Мэрилэндского Университета. «Частенько теоретики работают над проблемами, которые на самом деле никого не волнуют. Но это не тот случай».

            Хотя современные компьютеры не могут воспользоваться этим специфическим способом ускорения расчетов, Василевска-Уильямс также создала особую математическую схему, которая могла бы в дальнейшем помочь в достижении теоретических решений, полезных и на практике. «Вы можете представить себе это, как если бы еще один инструмент добавился на рабочем месте», — считает женщина-математик.

            Итак, упорное применение одного и того же алгоритма восемь (!) раз принесло свои плоды. Произошел своего рода переход количества в … количество. Больше оборотов рекурсии – меньше перемножений.

            Чем-то этот способ решения проблем напоминает открытие В. В. Петровым электрической дуги, которое случилось вот уже двести десят лет назад. Он просто соединил вместе много гальванических элементов, — так много, как никто другой до него. Правда у него все-таки количество перешло в качество, и высокое напряжение вкупе с большим запасом заряда дало нам в руки новое явление – электрический разряд, отличный от искры. Кто знает, если в методе Василевски-Уильямс применить алгоритм не восемь, а восемьдесят раз, не получится ли чего-нибудь этакого?

GD Star Rating
loading...
Переход количества в количество, 10.0 out of 10 based on 1 rating

Добавить комментарий