Бинарное расщепление

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

Метод

Учитывая серию

S(a,b)=\sum _{n=a}^{b}{\frac {p_{n}}{q_{n}}}

где p _n и q _n — целые числа, цель двоичного разделения — вычислить целые числа P ( a , b ) и Q ( a , b ) такие, что

S(a,b)={\frac {P(a,b)}{Q(a,b)}}.

Разделение состоит из установки m = [( a + b )/2] и рекурсивного вычисления P ( a , b ) и Q ( a , b ) из P ( a , m ), P ( m , b ), Q ( a , м ) и Q ( м , б ). Когда a и b достаточно близки, P ( a , b ) и Q ( a , b ) могут быть вычислены непосредственно из p _a ...p _b и q _a ...q _b .

Сравнение с другими методами

Двоичное разбиение требует больше памяти, чем прямое почленное суммирование, но выполняется асимптотически быстрее, поскольку размеры всех возникающих подпродуктов уменьшаются. Кроме того, в то время как самая наивная схема оценки рационального ряда использует деление полной точности для каждого члена ряда, двоичное разбиение требует только одного окончательного деления с целевой точностью; это не только быстрее, но и удобно устраняет ошибки округления. Чтобы в полной мере воспользоваться преимуществами схемы, методы быстрого умножения, такие как умножение Тума – Кука и алгоритм Шенхаге – Штрассена необходимо использовать ; с обычным O ( n ²) умножение, двоичное разбиение могут вообще не ускоряться или работать медленнее.

Поскольку все подразделения ряда могут быть вычислены независимо друг от друга, двоичное разбиение хорошо подходит для распараллеливания и создания контрольных точек .

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

Ссылки

Ксавье Гурдон и Паскаль Себа. Бинарный метод разделения
Дэвид В. Чудновский и Грегори В. Чудновский. Компьютерная алгебра на службе математической физики и теории чисел . В книге «Компьютеры и математика» (Стэнфорд, Калифорния, 1986) , стр. 09–232, Деккер, Нью-Йорк, 1990.
Бруно Хайбле, Томас Папаниколау. Быстрое вычисление рядов рациональных чисел с высокой точностью . Статья распространяется с исходным кодом библиотеки CLN .
Лозье, Д.В. и Олвер, Ф.В.Дж. Численная оценка специальных функций. Математика вычислений 1943–1993: полвека вычислительной математики, ред. В. Гаучи, Proc. Симпозиумы. Прикладная математика, AMS, т. 48, стр. 79–125 (1994).
Бах, Э. Сложность теоретико-числовых констант. Информация. Учеб. Письма, № 62, стр. 145–152 (1997).
Борвейн Дж. М., Брэдли Д. М. и Крэндалл Р. Э. Вычислительные стратегии для дзета-функции Римана. Дж. из Comput. Прил. Матем., т.121, № 1-2, стр. 247–296 (2000).
Карацуба Е.А. Быстрое вычисление трансцендентных функций. (англ. русский оригинал) Пробл. Инф. Трансм. 27, №4, 339-360 (1991); перевод с Пробл. Передачи Инф. 27, № 4, 76–99 (1991).
Екатерина Карацуба. Быстрые алгоритмы и метод FEE