Какова фактическая временная сложность исключения Гаусса?

В ответе на предыдущий вопрос я упомянул распространенное, но ошибочное мнение, что «гауссовское» исключение происходит за времени. Хотя очевидно, что алгоритм использует арифметических операций, небрежная реализация может создавать числа с экспоненциально большим количеством битов. В качестве простого примера, предположим, что мы хотим диагонализировать следующую матрицу: $O(n^3)$ $O(n^3)$

[\begin{matrix} 2 & 0 & 0 & \dots & 0 \\ 1 & 2 & 0 & \dots & 0 \\ 1 & 1 & 2 & \dots & 0 \\ ⋮ & ⋮ & ⋮ & ⋱ & ⋮ \\ 1 & 1 & 1 & \dots & 2 \end{matrix}]

$\begin{bmatrix} 2 & 0 & 0 & \cdots & 0 \\ 1 & 2 & 0 & \cdots & 0 \\ 1 & 1 & 2 & \cdots & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots\\ 1 & 1 & 1 & \cdots & 2 \\ \end{bmatrix}$

Если мы используем версию алгоритма исключения без деления, которая добавляет только целочисленные кратные одной строки к другой, и мы всегда поворачиваемся на диагональном элементе матрицы, выходная матрица имеет вектор по диагонали. $(2, 4, 16, 256, \dots, 2^{2^{n-1}})$

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

$n\times n$ $m$ $O(n(m+\log n))$ $m=O(\log n)$ $O(n^5)$ $\tilde{O}(n^4)$ $O(\log n)$

Это все еще лучший анализ, известный? Существует ли стандартная ссылка, которая дает более четкую временную границу или, по крайней мере, лучшую оценку требуемой точности?

В более общем смысле: каково время работы (в целочисленном ОЗУ) самого быстрого алгоритма, известного для решения произвольных систем линейных уравнений?

ds.algorithms reference-request linear-algebra Jeffε
источник

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

Суреш Венкат

O (n^{3} M_{B} [n (\log n + L)])

$O(n^3 M_B[n (\log n + L)])$

Стандартный алгоритм исключения Гаусса делит строку сводки на элемент сводки перед уменьшением более поздних строк. Открытый вопрос относится к этой стандартной версии. В примере, который я привел в начале моего вопроса, используется другой вариант, который НЕ разделяется на элемент pivot.

Джефф

Любопытно. Граница времени Yap для алгоритма Bereiss идентична границе времени, подразумеваемой анализом Эдмондса исключения Гаусса.

Джефф

Rjlipton недавно провел обзор местности и цитирует кандидатскую диссертацию Каннана на эту тему. ключевой частью анализа является WRT Смит нормальная форма

ВЗН

Ответы:

$\widetilde O(n^3 \log( \|A\| + \|b\|))$

Элиас
источник

Спасибо за ссылку! Это отвечает на мой второй вопрос, но не на мой первый.

Джефф

Если вы используете поворот, то размер битов промежуточных результатов в исключении Гаусса (GE) является полиномиальным, экспоненциальный взрыв отсутствует. Я думаю, что это результат Bareiss. Что касается сложности GE, в книге Гатена и Герхарда «Современная компьютерная алгебра» есть алгоритм для вычисления определителя матрицы , основанный на GE, модульной арифметике и теореме об остатках в Китае (раздел 5.5, С. 101-105). Сложность . Я думаю, что фактор может быть сохранен с помощью быстрой арифметики. Если я не ошибаюсь, это ограничение, которое упомянул user834.

A

$A$

O (n^{4} \log^{2} ‖ A ‖)

$O(n^4 \log^2\|A\|)$

n

$n$

Элиас

@ Элиас, каково определение нормы в этом выражении? Это самый большой коэффициент в абсолютном размере? Это размер в битах? Кроме того, этот результат для произвольных рациональных матриц?

Хуан Бермехо Вега

Я думаю, что ответом на ваш первый вопрос также является из-за следующих аргументов: статья Эдмондса не описывает вариант исключения Гаусса но это доказывает, что любое число, вычисленное в шаге алгоритма, является детерминантом некоторой подматрицы A. По книге Шрайвера «Теория линейного и целочисленного программирования» мы знаем, что если для кодирования A требуется b бит (b должно быть в $\widetilde O(n^3 \log( \|A\| + \|b\|))$ $\widetilde O(\log( \|A\|)$ ) тогда любому из его подопределителей требуется не более 2b битов (теорема 3.2). Чтобы сделать гауссовское исключение алгоритмом полиномиального времени, мы должны позаботиться о вычисленных коэффициентах: мы должны исключить общие факторы из каждой дроби, которую мы вычисляем на любом промежуточном шаге, и тогда все числа имеют длину кодирования, линейную по длине кодирования A.

Матиас Вальтер
источник