Поиск целочисленных соотношений является одной из важных задач вычислительной математики. Пусть заданы вещественные числа $x_1,\ldots,x_n$. Требуется определить, существуют ли небольшие целые коэффициенты $c_1,\ldots,c_n$, для которых выполняется
$$ c_1x_1+c_2x_2+\ldots+c_nx_n=0. $$Классическим решением этой задачи является алгоритм PSLQ. В настоящей работе представлен APS - Adaptive Precision Search, алгоритм, использующий целочисленное вложение решётки и LLL-редукцию для построения кандидатов целочисленных соотношений.
В отличие от непосредственного однократного применения LLL, APS использует несколько уровней вычислительной точности. На каждом уровне строится целочисленная решётка, выполняется LLL-редукция с получением трансформационной матрицы, из которой извлекаются кандидаты. Для каждого кандидата вычисляется исходная вещественная невязка. Кандидаты, сохраняющие устойчивость при повышении точности, получают преимущество перед случайными приближёнными отношениями.
В проведённых тестах APS успешно находил заданные отношения в размерностях от 4 до 30. На высоких размерностях наблюдалось существенное преимущество по времени относительно PSLQ. В тесте размерности 30 при ограничении коэффициентов 10 APS выполнялся примерно за 0.027 секунды, тогда как использованный PSLQ занимал примерно 6.41 секунды.
Рассмотрим набор вещественных чисел
$$ X=(x_1,x_2,\ldots,x_n). $$Целочисленным соотношением называется ненулевой вектор
$$ C=(c_1,c_2,\ldots,c_n), \qquad c_i\in\mathbb Z, $$для которого выполняется
$$ \sum_{i=1}^{n}c_ix_i=0. $$В вычислительной практике входные значения обычно представлены с конечной точностью. Поэтому вместо точного равенства используется невязка
$$ R(C)= \left| \sum_{i=1}^{n}c_ix_i \right|. $$Задача APS состоит в нахождении ненулевого $C$ с небольшими коэффициентами и достаточно малой невязкой.
Хороший алгоритм целочисленного соотношения должен удовлетворять нескольким требованиям.
Последний пункт особенно важен. Прямой перебор коэффициентов имеет экспоненциальный рост числа комбинаций. Если каждый коэффициент может принимать $2B+1$ значений, то полный перебор имеет порядок
$$ (2B+1)^n. $$Поэтому APS переводит задачу в задачу редукции решётки.
LLL (Lenstra-Lenstra-Lovász) является классическим алгоритмом редукции базиса целочисленной решётки. Сам LLL не является частью нового теоретического результата данной работы: алгоритм LLL и его применение к задачам диофантовых приближений известны давно.
APS использует LLL как внутренний механизм сокращения пространства кандидатов, то есть принципиальное отличие APS от утверждения "запустить LLL" заключается в полном процессе поиска:
$$ \boxed{ \text{вложение} \rightarrow \text{LLL} \rightarrow T \rightarrow \text{кандидаты} \rightarrow \text{проверка} \rightarrow \text{повышение точности} \rightarrow \text{стабильность} } $$Пусть используется $p$ десятичных знаков рабочей точности. APS выбирает масштаб
$$ Q=10^{\max(10,p-4)}. $$Для каждого входного значения вычисляется
$$ q_i=\operatorname{round}(Qx_i). $$То есть вещественные числа преобразуются в целые.
Строится матрица размера $n\times(n+1)$:
$$ B= \begin{pmatrix} 1&0&0&\ldots&0&q_1\\ 0&1&0&\ldots&0&q_2\\ 0&0&1&\ldots&0&q_3\\ \vdots&\vdots&\vdots&\ddots&\vdots&\vdots\\ 0&0&0&\ldots&1&q_n \end{pmatrix}. $$Для произвольного целочисленного вектора $C$ произведение $CB$ равно
$$ CB= \left( c_1,c_2,\ldots,c_n, \sum_{i=1}^{n}c_iq_i \right). $$Если $C$ является искомым отношением, последняя координата может оказаться малой относительно масштаба $Q$.
Следовательно, задача поиска отношения превращается в задачу поиска коротких векторов в специально построенной целочисленной решётке.
5. LLL-редукция и трансформационная матрицаПусть после LLL-редукции получена матрица $R$. Одновременно APS получает целочисленную трансформационную матрицу $T$, такую что
$$ R=TB. $$Строка $T_i$ определяет, какая целочисленная комбинация исходных строк $B$ использовалась для получения соответствующей строки $R$.
Поэтому первые $n$ координат строки $T_i$ можно рассматривать как кандидата:
$$ C_i= (T_{i1},T_{i2},\ldots,T_{in}). $$Это важная часть реализации APS. Алгоритм не ограничивается анализом непосредственно строк редуцированного базиса, а использует информацию о том, какими целочисленными комбинациями исходных векторов был получен редуцированный базис.
Два отношения
$$ (2,-4,6) $$и
$$ (1,-2,3) $$математически эквивалентны. Поэтому перед сравнением кандидатов APS делит все коэффициенты на их общий наибольший делитель.
Затем выбирается общий знак так, чтобы первый ненулевой коэффициент был положительным. Это позволяет хранить каждое отношение в канонической форме.
Пусть пользователь задаёт максимальный допустимый коэффициент $M$. Кандидат принимается в дальнейшее рассмотрение только если
$$ \max_i |c_i|\le M. $$Это значительно сокращает число кандидатов и одновременно позволяет избегать отношений, которые формально являются короткими в решётке, но имеют слишком большие коэффициенты для поставленной задачи.
Вместо немедленного запуска всей процедуры на максимальной точности APS использует последовательность уровней.
В текущей реализации начальный уровень равен 24 знакам. Следующий уровень получается умножением предыдущего примерно на 1.7:
$$ 24\rightarrow40\rightarrow68\rightarrow80. $$Последний уровень ограничивается заданной максимальной точностью.
На каждом уровне решётка строится заново. Это необходимо, поскольку округлённые значения $q_i$ меняются при изменении $Q$.
При конечной точности практически всегда можно найти случайные комбинации, дающие небольшую невязку. Особенно это заметно при увеличении размерности.
Например, некоторый случайный вектор $C$ может давать:
$$ R(C)\approx10^{-24} $$при одной конкретной точности. Само по себе это ещё не доказывает наличие математического отношения.
Если же тот же вектор продолжает давать существенно меньшую невязку при переходе, например,
$$ 24\rightarrow40\rightarrow68\rightarrow80, $$то вероятность того, что он является случайным приближением, существенно уменьшается.
Для каждого кандидата вычисляется
$$ R(C)= \left| c_1x_1+c_2x_2+\ldots+c_nx_n \right|. $$Это вычисление производится на исходных вещественных значениях, а не по последней координате вложения в решётку. Это принципиально важно, поскольку
$$ q_i=\operatorname{round}(Qx_i) $$содержит ошибку округления.
Для каждого нормализованного кандидата APS может сохранять последовательность
$$ (p_1,R_1),(p_2,R_2),\ldots,(p_k,R_k), $$где $p_i$ - уровень точности, а $R_i$ - соответствующая невязка.
Кандидат, появляющийся только один раз, считается менее надёжным, чем кандидат, который воспроизводится на нескольких уровнях.
Условно можно оценить улучшение невязки между двумя уровнями как
$$ S= \log_{10}(R_{\mathrm{old}}) - \log_{10}(R_{\mathrm{new}}). $$Большое положительное значение $S$ означает существенное уменьшение невязки.
При этом устойчивость не используется как самостоятельное доказательство отношения. Она используется для ранжирования кандидатов.
Окончательное решение принимается после повторного вычисления невязки на повышенной точности.
Помимо строк $T$, APS рассматривает ограниченное количество коротких строк $R$.
Если строка $R_i$ имеет первые $n$ координат
$$ (r_{i1},r_{i2},\ldots,r_{in}), $$они также могут быть нормализованы и проверены как потенциальный вектор отношения.
Это создаёт дополнительный источник кандидатов практически без существенного увеличения времени работы.
14. Полный алгоритм APSПеред сохранением кандидат нормализуется: все коэффициенты делятся на их общий наибольший делитель, после чего знак выбирается так, чтобы первый ненулевой коэффициент был положительным. Это позволяет считать векторы, отличающиеся общим множителем или знаком, одним и тем же целочисленным соотношением.
Текущая реализация использует Python, mpmath и python-flint. Критическая операция LLL выполняется библиотекой FLINT, реализованной на низкоуровневом языке, что существенно снижает накладные расходы по сравнению с реализацией LLL на чистом Python.
Основные компоненты реализации:
mpmath - высокоточная арифметика;python-flint - целочисленные матрицы и LLL;normalize() - нормализация коэффициентов;residual() - вычисление невязки;build_lattice() - построение вложения;extract_candidates() - получение кандидатов из T;aps() - основной алгоритм.Для объективной проверки использовались синтетические задачи, в которых истинное отношение известно заранее.
Пусть заранее задан
$$ C^*=(c_1^*,c_2^*,\ldots,c_n^*). $$Генерируются независимые значения $x_1,\ldots,x_{n-1}$, после чего последнее значение строится как
$$ x_n= -\frac{ c_1^*x_1+\ldots+c_{n-1}^*x_{n-1} }{ c_n^* }. $$Тогда гарантированно выполняется:
$$ c_1^*x_1+\ldots+c_n^*x_n=0. $$После этого APS должен восстановить $C^*$ с точностью до общего множителя и знака.
Для сравнения использовался PSLQ с сопоставимой требуемой точностью. Измерялось время непосредственно выполнения решателя.
Для каждой задачи проверялась не только скорость, но и правильность найденного отношения.
Для сравнения APS и PSLQ использовались одинаковые входные данные и одинаковая целевая точность 80 десятичных знаков. Каждая тестовая конфигурация запускалась семь раз после предварительного прогрева. В качестве итогового времени использовалась медиана измерений. Порядок запуска APS и PSLQ чередовался.
Коэффициенты до 10:| Размерность | APS, с | PSLQ, с | PSLQ/APS | Правильно |
|---|---|---|---|---|
| 4 | 0.000831 | 0.000267 | 0.32x | Да |
| 6 | 0.000998 | 0.002238 | 2.24x | Да |
| 8 | 0.001246 | 0.006363 | 5.11x | Да |
| 10 | 0.001910 | 0.025024 | 13.10x | Да |
| 12 | 0.003577 | 0.053132 | 14.86x | Да |
| 15 | 0.005052 | 0.191840 | 37.97x | Да |
| 20 | 0.010024 | 0.929670 | 92.75x | Да |
| 25 | 0.015479 | 3.380119 | 218.37x | Да |
| 30 | 0.023770 | 6.131508 | 257.96x | Да |
| Размерность | APS, с | PSLQ, с | PSLQ/APS | Правильно |
|---|---|---|---|---|
| 6 | 0.000917 | 0.003424 | 3.73x | Да |
| 10 | 0.002570 | 0.045728 | 17.79x | Да |
| 15 | 0.005802 | 0.351198 | 60.53x | Да |
| 20 | 0.009979 | 1.415949 | 141.89x | Да |
| Размерность | APS, с | PSLQ, с | PSLQ/APS | Правильно |
|---|---|---|---|---|
| 6 | 0.000865 | 0.005272 | 6.10x | Да |
| 10 | 0.002928 | 0.074524 | 25.45x | Да |
| 15 | 0.005868 | 0.554795 | 94.54x | Да |
Во всех 16 протестированных конфигурациях оба алгоритма восстановили заранее известное целочисленное отношение.
Максимальное измеренное ускорение APS получено на размерности 30 при ограничении коэффициентов 10:
$$ t_{\mathrm{APS}}=0.023770\ {\rm s}, $$ $$ t_{\mathrm{PSLQ}}=6.131508\ {\rm s}. $$Отношение времени составило
$$ \frac{t_{\mathrm{PSLQ}}}{t_{\mathrm{APS}}} \approx257.96. $$Таким образом, в данном эксперименте реализация APS завершала поиск примерно в 258 раз быстрее реализации PSLQ.
При размерности 4 PSLQ оставался быстрее APS. Начиная с 6 измерений APS оказался быстрее во всех протестированных конфигурациях.
Скорость не считалась достаточным критерием. Для каждого теста найденный вектор сравнивался с заранее известным истинным отношением.
В частности, если истинный вектор имеет вид
$$ C^*=(c_1,\ldots,c_n), $$а алгоритм возвращает
$$ C=(d_1,\ldots,d_n), $$то результаты считаются эквивалентными, если существует ненулевое целое $k$, такое что
$$ C=kC^*. $$После нормализации это означает полное совпадение векторов. Во всех 16 тестовых конфигурациях такое совпадение было получено для обоих алгоритмов.
В процессе разработки было обнаружено, что простое требование минимальной невязки недостаточно. При увеличении размерности существует большое количество целочисленных векторов. Среди них находятся векторы, которые случайно дают малую конечную невязку. Именно поэтому ранние варианты алгоритма могли возвращать неправильные коэффициенты в задачах 20-30 измерений.
Решение состоит не в простом увеличении допустимого размера коэффициентов, а в проверке поведения кандидата при повышении точности.
При $n=30$ и диапазоне коэффициентов $[-10,10]$ количество возможных векторов равно
$$ 21^{30}, $$что составляет примерно
$$ 2.6\times10^{39}. $$Полный перебор такого пространства невозможен.
APS вместо этого использует LLL для быстрого сокращения пространства поиска.
Теоретическая сложность полного APS определяется не только размерностью, но и стоимостью LLL, величиной целых чисел после масштабирования и числом уровней точности.
Поэтому из приведённых экспериментов нельзя вывести универсальную асимптотическую формулу времени APS.
Однако на протестированном наборе задач время APS росло значительно медленнее времени использованной реализации PSLQ. При увеличении размерности это преимущество становилось более выраженным.
Представленные результаты нельзя интерпретировать как доказательство того, что APS быстрее PSLQ на любых входных данных.
В частности, на размерности 4 PSLQ оказался быстрее:
$$ 0.000267\ {\rm s} < 0.000831\ {\rm s}. $$Это связано с тем, что при малой размерности накладные расходы построения вложения решётки и выполнения LLL могут превышать преимущество адаптивного поиска.
В данном исследовании область практического преимущества APS начинается примерно с 6 измерений.
Для воспроизведения экспериментов необходимы:
search.py;benchmark.py.Пример запуска:
python search.py
Для сравнения:
python benchmark.py
mpmath используется для произвольной точности вещественных вычислений.
python-flint предоставляет Python-интерфейс к FLINT, включая эффективные операции над целыми числами и матрицами.
PSLQ в эксперименте используется как контрольный алгоритм integer relation.
В отличие от непосредственного применения LLL или однократного поиска отношения, APS выполняет последовательный процесс:
Ключевой результат APS состоит в использовании изменения вычислительной точности не только для повышения точности вычислений, но и как дополнительного критерия выбора между конкурирующими целочисленными соотношениями. Это позволяет отбрасывать случайные приближённые отношения, которые могут иметь малую невязку на отдельном уровне точности.
APS представляет собой законченный адаптивный алгоритм поиска целочисленных соотношений, а LLL выступает в нём как механизм сокращения пространства поиска.
Экспериментально показано, что предложенная схема позволяет сохранять корректность поиска при увеличении размерности и одновременно существенно сокращать время вычислений по сравнению с PSLQ на исследованных тестовых задачах. В частности, в тесте размерности 30 APS выполнил поиск примерно в 258 раз быстрее использованной реализации PSLQ (см. выше).
APS может использоваться для автоматического поиска математических тождеств и формул, в которых заранее неизвестны целочисленные коэффициенты.
Возможные задачи включают:
Рассмотрим пять чисел:
$$ x_1=\pi, $$ $$ x_2=e, $$ $$ x_3=\sqrt{2}, $$ $$ x_4=\ln 2, $$а $x_5$ зададим таким образом, чтобы выполнялось отношение
$$ 4x_1-7x_2+2x_3-9x_4+x_5=0. $$Следовательно,
$$ x_5= -4\pi+7e-2\sqrt2+9\ln2. $$APS должен восстановить
$$ (4,-7,2,-9,1). $$В эксперименте этот вектор был найден на раннем уровне точности, после чего повторная проверка на значительно большей точности подтвердила отношение.
В работе представлен APS - Adaptive Precision Search, практический алгоритм поиска целочисленных соотношений.
Алгоритм основан на известном математическом аппарате LLL, но объединяет его с адаптивным изменением точности, извлечением кандидатов через трансформационную матрицу, анализом невязки и проверкой устойчивости.
Экспериментальные результаты показывают существенное преимущество APS над использованным PSLQ на высоких размерностях. При размерности 30 и коэффициентах до 10 получено:
$$ 0.027231\ {\rm s} $$для APS против
$$ 6.407890\ {\rm s} $$для PSLQ, то есть примерно 258-кратное преимущество.
При этом на всех представленных тестах APS восстановил заранее известное отношение.
Результаты показывают, что APS особенно интересен не для малых размерностей, где накладные расходы LLL могут быть заметны, а для высокоразмерных задач целочисленного соотношения, где стоимость традиционного решателя быстро возрастает.
Работа описывает экспериментальную реализацию APS и результаты предварительного сравнительного тестирования. Фундаментальные методы LLL и PSLQ являются ранее опубликованными математическими методами.