Нижние оценки гауссовой сложности

18

Определим Gaussian сложность в качестве матрицы , чтобы минимальное число элементарных операций строк и столбцов , необходимых для приведения матрицы в верхней треугольной форме. Это величина от до (через гауссовское исключение). Понятие имеет смысл в любой области.n×nn 20n2

Эта проблема, безусловно, кажется очень простой, и она должна быть изучена. Удивительно, но я не знаю ни одной ссылки. Итак, я буду счастлив с любой ссылкой есть. Но, конечно же, главный вопрос:

Известны ли какие-либо нетривиальные явные нижние оценки?

Под нетривиальным я подразумеваю суперлинейный. Просто для ясности: для конечных полей счетный аргумент показывает, что случайная матрица имеет порядок сложности n ^ 2 (аналогичное утверждение должно быть верно для бесконечных полей). Следовательно, мы ищем явное семейство матриц, например, матрицы Хадмара. Это то же самое, что и со сложностью булевой схемы, когда мы знаем, что случайная функция имеет высокую сложность, но мы ищем явные функции с этим свойством.

Moritz
источник
Я не совсем уверен, что вопрос здесь. Вы спрашиваете о конкретных формах матриц или общем случае (в этом случае простой аргумент подсчета работает?)
Джо Фицсимонс
@ Джо, как уже упоминалось, я прошу явное семейство матриц, например, матрицы Адамара. Как обычно, случайные матрицы обманывают. Это во многом аналогично тому, как нас не устраивает тот факт, что случайная функция требует больших цепей. Я добавил параграф, чтобы подчеркнуть этот момент.
Мориц
может быть, это следует сделать как ответ :)
Суреш Венкат
Хорошо, сделаем так.
Джо Фицсимонс
На самом деле, я считаю, что мой метод мог быть ошибочным.
Джо Фитцзимонс

Ответы:

17

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

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

Теперь операции со строками обратимы . Отсюда следует, что c (A) может быть эквивалентно определено как минимальное количество операций строки, необходимых для получения A, начиная с единичной матрицы.

Обратите внимание, что создание A таким способом приводит к арифметической схеме для вычисления карты, переводящей x в Ax. Fanin каждого вентиля равен 2, а количество невходных вентилей соответствует количеству операций со строками.

Нет очевидного сокращения в обратном направлении (от цепей до последовательностей строк). Тем не менее, мы можем охарактеризовать c (A) с точки зрения сложности арифметической схемы Ax в модели ограниченного контура: я утверждаю, что c (A) равна половине минимального числа ребер в арифметической схеме для A, из fanin самое большее 2 и ширина n, где мы не взимаем плату за ребра, ведущие к воротам fanin 1. (Я использую обычное понятие ширины цепи здесь.) Это можно показать с помощью простой идеи, набросанной ранее.

Теперь вот связь с хорошо изученными проблемами: более 30 лет было известной открытой проблемой, чтобы показать явное линейное отображение Ax (над любым конечным полем), для которого требуется суперлинейное число вентилей в схеме fanin-2. Классическим справочником является Valiant, «Теоретические графы аргументы в низкоуровневой сложности», а также недавний опрос FTTCS Lokam также полезен.

Изучая c (A), мы накладываем дополнительное ограничение ширины, но, поскольку наше ограничение очень слабое (ширина n), я не ожидаю, что проблема станет намного проще. Но, эй, я бы хотел оказаться неправым.

Энди Друкер
источник
2
Кроме того, у Гауэрса в его блоге была дискуссия о сложности исключения по Гауссу. Я не прочитал это внимательно (это в форме длинного диалога), но это может быть полезно: gowers.wordpress.com/2009/11/03/…
Энди Друкер
Просто чтобы понять это правильно, приходит ограничение ширины, потому что у вас есть максимум n операций на столбец, и вы можете переходить от столбца к столбцу?
Мориц
Я думаю с точки зрения операций со строками. Ограничение ширины n соответствует тому факту, что у нас есть n строк для работы, в которых будет выполняться вся наша промежуточная работа. Ворота схемы n на глубине t представляют состояния n строк после t применений операций с рядами. (может быть, вы говорите то же самое, что и я)
Энди Друкер
Если бы вместо этого мы допустили дополнительные строки «вспомогательного рабочего пространства» в нашем исключении из Гаусса, я полагаю, что мы получили бы точное соответствие между сложностью сведения A к тождеству и сложностью линейной арифметической схемы Ax (которая по сути является арифметической сложностью ckt, поскольку умножения не помогают вычислить линейные функции за пределами постоянного множителя).
Энди Друкер
Да, это то, что я имел в виду. Я также согласен со вторым утверждением. Обычная линейная схема может создавать новые строки, когда захочет :-)
Moritz
9

Есть ссылки, и они довольно старые. Я сталкивался с ними, работая над комбинаторными алгоритмами для умножения булевых матриц.

В 1966 году Мун и Мозер доказали, что для вычисления обратной матрицы над GF (2) требуется Θ(N2/LограммN)журналN

Дж. В. Мун и Л. Мозер. Задача сокращения матриц. Математика вычислений 20 (94): 328–330, 1966.

Статья должна быть доступна на JSTOR.

Я почти уверен, что нижняя граница - это просто счетный аргумент, и никаких явных матриц, достигающих нижней границы, не было дано.

Райан Уильямс
источник