Какова пространственная сложность вычисления собственных значений?

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

Благодарю.

linear-algebra space-complexity Гил
источник

Я предполагаю, что сложность всегда максимально линейна (например,

для матрицы

). Вы заинтересованы в «общем пространстве» или «рабочем пространстве»?

O (n m)

$O(nm)$

n \times m

$n\times m$

Юваль Фильмус

Я должен был упомянуть, что я заинтересован в рабочем пространстве.

Гил

Я уверен, что это

для матрицы

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

O (n^{2})

$\mathcal O(n^2)$

n \times n

$n\times n$

лет»

Чтобы расширить точку зрения @Yuval Filmus, сложность пространства весьма чувствительна к конкретной модели вычислений. В частности, поскольку выходные данные имеют линейный размер, можно использовать трюки, используя выходную ленту в качестве рабочего пространства, если модель четко не определяет выходную ленту только для записи. Чтобы избежать таких проблем, я хотел бы перефразировать их как решение проблем (например, в качестве входных трех матриц, проверьте, является ли третье произведение первых двух). Не могли бы вы указать модель, которую вы имели в виду? (Кроме того, мне не известны книги о сложности космоса, и я также не нашел полезных обзоров.)

Андрас Саламон

Что касается @ AndrásSalamon, то полезная для меня версия решения может быть такова: является k-е собственное значение больше, чем q. для целого числа k и рационального q. Благодарю.

Гил

Ответы:

Варианты решения многих общих задач в линейной алгебре над целыми числами (или рациональными числами) находятся в классе , см. Статью $\mathsf{DET}$

Герхард Бантрок, Карстен Дамм, Ульрих Хертрампф, Кристоф Майнель: Структура и значение класса Logspace-MOD. Теория математических систем 25 (3): 223-237 (1992)

содержится в . $\mathsf{DET}$ $\mathsf{DSPACE}(\log^2)$

Вычисление собственных значений немного сложнее:

1) В можно вычислить коэффициенты характеристического полинома. $\mathsf{DSPACE}(\log^2)$

2) Затем вы можете использовать параллельный алгоритм Рейфа и Неффа для вычисления приближений к собственным значениям. Алгоритм работает на CREW-PRAM за логарифмическое время с полиномиально большим количеством процессоров, поэтому его можно моделировать с использованием полилогарифмического пространства. (Это явно не указано в статье, но их PRAM должны быть единообразными в лог-пространстве.) Используемое пространство является полилогарифмическим по размеру входной матрицы и точности . Точность означает, что вы получаете приближения с точностью до аддитивной ошибки . $p$ $p$ $2^{-p}$

Это объединение функций, вычислимых в полилогарифмическом пространстве. (Выходные ленты только для записи и одностороннего действия.)

C. Эндрю Нефф, Джон Х. Райф: Эффективный алгоритм для комплексной проблемы корней. J. Сложность 12 (2): 81-115 (1996)

Маркус Блезер
источник

$log^2$ $NC^2$

Лиор Эльдар
источник