Оригинал статьи. Работы, выполненные с Эльке Рунденштайнер (Elke Rundensteiner). Эта работа стала возможной благодаря поддержке Air Force Office of Scientific Research.

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

Во вводных числовых классах часто упоминаемый пример, в котором используется правило Крамера для решения 25 неизвестных чисел. Многие студенты узнали в своих математических классах, как решить 3 или 4 неизвестных, используя правило Крамера, но никто не рассказал им, как использовать другой метод для большего количества неизвестных. Решение для 25 неизвестных не имеет большого значения, есть много простых методов, которые могут сделать это очень быстро, но правило Крамера не является одним из них! Он примерно в 100,000,000,000,000,000,000,000 раз медленнее, чем стандартный метод сделать расчет. Лучшие суперкомпьютеры стали бы пылью, прежде чем они бы закончили вычисление.

Как вы могли догадаться, подобная разница является исключительной. Это связано с выбором особенно слабого вычислительного метода, правила Крамера. Та проблема, с которой столкнулись Эльке и я, похоже совсем не открывала улучшений. Мы хотели вычислить потоки воздуха или воды вокруг препятствий, таких как провода или крылья. Числительный метод был «вихревым методом», в котором тысячи вызванных небольших торнадо, названные вихрями, использовались для того чтобы представить движение воздуха или воды. Сложность заключалась в том, что нам нужно было найти скорость каждого вихря, чтобы следить за их движением, а скорость каждого зависит от всех остальных вихрей.

Чтобы увидеть трудности, представьте, что мы имеем кричащих людей вместо вихрей. Например, предположим, что есть 10 000 кричащих людей, разбросанных по очень большому полю. Вопрос в том, сколько шума слышит каждый человек. Чтобы ответить на вопрос, вы должны определить для каждого человека, сколько шума он получает от каждого другого человека, находя расстояние от этого человека и вычисляя уровень шума на этом расстоянии. Суммируйте шумы от всех 9999 других людей, чтобы получить общий шум.

Это работает, но поскольку мы должны вычислить 9999 расстояний для каждого человека, объем вычислительной работы пропорционален 10000 раз на 9999. Она пропорциональна квадрату количества людей. Если бы было 20 000 человек вместо 10 000, нам пришлось бы преодолевать в четыре раза больше расстояний, а не в два раза. Для большого количества людей, работы над одним человеком просто становится слишком много, для того чтобы это разбирать.

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

Таким образом, используя ребенка, мы можем исключить некоторые расстояния, которые нам придется вычислить. Мы можем повторить это для других групп людей, которые находятся поблизости. И есть еще Другие игры, в которые мы можем играть. Предположим, что есть два близлежащих ребенка, заменяющих разные группы людей. На действительно больших расстояниях, мы могли бы заменить двух детей на Суперребенка, который снова в два раза громче. (Возможно, ему понадобится шпинат).

Как вы уже могли догадаться, основная идея оказалась не особенно оригинальный; реальный тест был в эффективном распределении людей (вихрей) в неправильном паттерне. Вот картина, как Элке и я сгруппировали вихри вместе:

Изображение для потока вокруг провода, увиденного на левой стороне. Вихри можно рассматривать как темные или светлые точки в основном в маленьких площадях.

Это сработало? Ну, вот некоторые вычислительные промежутки, в секундах, сначала, если мы вычисляем все расстояния, а затем с помощью нового метода, который мы разработали:

Вихри: 400 800 1600 3200 6400 12800 25600

Старое время: 9.1 36.3 151.9 586.8 2354.1 9404.8 37556.0

Новое время: 4.7 10.6 25.1 55.4 128.5 286.3 597.8

Соотношение: 2 3 6 11 18 33 63

Таким образом, новый метод уже в 63 раза быстрее для 25 000 вихрей, и это даст еще больше для большего количества вихрей.

Чтобы представить это в перспективе, это разница между получением результатов вычислений на следующий день или через два месяца. Возможно, вы сможете жить с первым, но, вероятно, не со вторым. Я все еще использую эту схему для своих вычислений, хотя другие исследователи, такие как Карриер, Грингард и Рохлин (Carrier, Greengard и Rokhlin), сформулировали аналогичные схемы, которые все еще быстрее. Они также более сложные: люди носят наушники и получают шум младенцев по радио. Когда-нибудь я напишу или получу одну из этих процедур.

Некоторые ссылки:

Van Dommelen, L. L. (1985) Adaptive-panel vortex summation for the CYBER 205. 38th Annual Meeting Div. Fluid Dynamics, Bulletin of the American Physical Society, 30.

Van Dommelen, L. L. & Rundensteiner, E. A. (1989) Fast solution of the two-dimensional Poisson equation with point-wise forcing. Journal of Computational Physics 83, 126-147.

Carrier, J., Greengard, L. \& Rokhlin, V. (1986) A fast adaptive multipole algorithm for particle simulations. Yale University Research Report YALEU/DCS/RR-496.

Greengard, L. \& Rokhlin, V. (1988) On the efficient implementation of the fast multipole algorithm. Yale University Research Report YALEU/DCS/RR-602.