Напишите ответ, чтобы он не остался без ответа, хотя в комментариях упоминался HNF.
Нормальная форма Эрмита — это стандартный способ сведения генераторной установки к базису.
Это означает, что это стандартный способ вычисления нескольких операций над решетками (которые легко выражаются в терминах базисных векторов), например
$L+L'$ (частным случаем которого является ваш пример), или
$L\крышка L'$ (это менее очевидно и требует двойственности).
См. простые задачи на решетку эти заметки.
Вы прокомментировали
Похоже, эффективное вычисление нормальной формы Эрмита нетривиально...
Это (вроде) верно, но нетривиальность далеко не «сложна».
цитирую из заметок
Нетрудно придумать алгоритм, вычисляющий ГНФ матрицы, выполняющий только полиномиальное число операций. Однако наивное решение этой проблемы может привести к сверхполиномиальному времени выполнения, поскольку числа в промежуточных вычислениях могут легко стать очень большими.
Связанные примечания включают псевдокод для реализации HNF с полиномиальным временем выполнения (путем обеспечения ограниченности промежуточных значений).
Возможно, он немного сложнее, чем LLL, но на самом деле ненамного — оба алгоритма, как я ожидаю, смогут реализовать без особых усилий младший/старший студент.
Конечно, можно приложить больше усилий, чтобы получить более практически эффективные вещи.
См. этот документ Перне и Штейн. Поскольку Штейн является основателем Sage CAS, я полагаю, что это довольно близко к тому, что Sage реализовал, по крайней мере, примерно в 2011 году.
Этот алгоритм, возможно, является своего рода "нетривиальным" алгоритмом, который вы имели в виду. Но, с другой стороны, эффективные реализации LLL также становятся нетривиальными (несколько лет назад я слышал, что LLL требует одновременно полиномиального времени и, возможно, его трудно запустить на больших решетках, скажем, размерностью 1k+).
Стоит упомянуть, что, похоже, есть некоторая работа, которая вычисляет HNF с использованием LLL в качестве подпрограммы, см., Например, это.
