Арифметика шаров и интервальная арифметика - PullRequest
0 голосов
/ 02 ноября 2018

Каковы преимущества арифметики шаров (Arb) над интервальной арифметики (MPFI) ?

Другими словами, каковы преимущества представления интервала как [центр, радиус] по сравнению с [влево, вправо]?

Речь идет не о конкретной библиотеке (Arb vs MPFI), а о преимуществах конкретного представления.

Меня особенно интересует, допускает ли одно представление более быструю арифметику (меньше примитивных операций), меньшую переоценку ошибок и более экономное использование памяти.

1 Ответ

0 голосов
/ 03 ноября 2018

В арифметике произвольной точности шариковая арифметика примерно в два раза быстрее, чем интервальная арифметика, и использует вдвое меньше места. Причина в том, что только центр шара нуждается в высокой точности, тогда как в интервальной арифметике обе конечные точки нуждаются в высокой точности. Конечно, детали зависят от реализации. (На практике Arb работает быстрее, чем MPFI, в два с лишним раза, но это во многом связано с усилиями по реализации.)

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

Статья Йориса ван дер Хувена об арифметике шаров хорошо отражает различия между арифметикой шаров и интервалов: http://www.texmacs.org/joris/ball/ball.html

Важная цитата: «Грубо говоря, шары должны использоваться для надежного приближения чисел, тогда как интервалы в основном полезны для сертифицированных алгоритмов, которые полагаются на деление пространства».

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

Лично я часто воспринимаю арифметику шаров как арифметику с плавающей точкой + анализ ошибок, но с распространением границ ошибок, которое выполняется компьютером, а не вручную. В этом смысле это лучший способ (для некоторых приложений!) Выполнять арифметику с плавающей точкой, а не просто лучший способ делать интервальную арифметику.

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

Истинные комплексные шары (комплексный центр + один радиус) иногда лучше, чем прямоугольные комплексные интервалы для представления комплексных чисел, поскольку эффект обертывания для умножений меньше. (Однако Arb использует прямоугольные «шарики» для комплексных чисел, поэтому у него нет этого особого преимущества.)

...