Рейтинг:1

Сокращение базиса решетки со слишком большим количеством базисных векторов

флаг us

Предположим, у меня есть база $В$ из $n$-мерная решетка $L\subseteq\mathbb{Z}^n$ и $В$ имеет $n$ векторы. теперь беру другой $v\in\mathbb{Z}^n\setminus L$ и я определяю новую решетку $L'=L+\mathbb{Z}v$. Набор векторов $B':=B\чашка\{v\}$ генерирует $L'$, но с тех пор $L'$ является $n$-размерный, его ранг не более $n$, так $В'$ слишком большой. Значит, должна быть какая-то другая основа, которая порождает $L'$. Как мы производим это из $В'$?

Я смутно припоминаю, что читал, что LLL может это сделать, но понятия не имею, как. Может ли кто-нибудь указать ссылку или дать быстрый аргумент/доказательство?

Daniel S avatar
флаг ru
Вместо того, чтобы разбивать LLL, вычислите [нормальную форму Эрмита] (https://en.wikipedia.org/wiki/Hermite_normal_form#Lattice_calculations) для $B'$ и отбросьте нулевые векторы.
Sam Jaques avatar
флаг us
Спасибо! Похоже, что эффективное вычисление нормальной формы Эрмита нетривиально, поэтому я просмотрю ссылки в Википедии. Очевидно, LLL может вычислить нормальную форму Эрмита, так что, вероятно, это то, что я видел.
Fractalice avatar
флаг in
LLL на B' уменьшит базу. т.е. некоторые выходные векторы будут нулевыми векторами и могут быть отброшены
kelalaka avatar
флаг in
Не могли бы вы опубликовать пример в качестве ответа?
Рейтинг:1
флаг ng

Напишите ответ, чтобы он не остался без ответа, хотя в комментариях упоминался HNF.

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

  • $L+L'$ (частным случаем которого является ваш пример), или

  • $L\крышка L'$ (это менее очевидно и требует двойственности).

См. простые задачи на решетку эти заметки.

Вы прокомментировали

Похоже, эффективное вычисление нормальной формы Эрмита нетривиально...

Это (вроде) верно, но нетривиальность далеко не «сложна». цитирую из заметок

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

Связанные примечания включают псевдокод для реализации HNF с полиномиальным временем выполнения (путем обеспечения ограниченности промежуточных значений). Возможно, он немного сложнее, чем LLL, но на самом деле ненамного — оба алгоритма, как я ожидаю, смогут реализовать без особых усилий младший/старший студент.

Конечно, можно приложить больше усилий, чтобы получить более практически эффективные вещи. См. этот документ Перне и Штейн. Поскольку Штейн является основателем Sage CAS, я полагаю, что это довольно близко к тому, что Sage реализовал, по крайней мере, примерно в 2011 году. Этот алгоритм, возможно, является своего рода "нетривиальным" алгоритмом, который вы имели в виду. Но, с другой стороны, эффективные реализации LLL также становятся нетривиальными (несколько лет назад я слышал, что LLL требует одновременно полиномиального времени и, возможно, его трудно запустить на больших решетках, скажем, размерностью 1k+).

Стоит упомянуть, что, похоже, есть некоторая работа, которая вычисляет HNF с использованием LLL в качестве подпрограммы, см., Например, это.

Sam Jaques avatar
флаг us
Спасибо, уникальность HNF, безусловно, объясняет, как он может уменьшить избыточный базис решетки. Я застрял на статье Гаваса-Маевского-Мэттьюса, где доказательство правильности является «простым продолжением аргумента в разделе 1», которое я не смог понять.

Ответить или комментировать

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