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

19

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

Благодарю.

Гил
источник
7
Я предполагаю, что сложность всегда максимально линейна (например, для матрицы n × m ). Вы заинтересованы в «общем пространстве» или «рабочем пространстве»? О(Nм)N×м
Юваль Фильмус
Я должен был упомянуть, что я заинтересован в рабочем пространстве.
Гил
Я уверен, что это для матрицы n × n . Основная причина в том, что я знаю два полезных метода их вычисления, и оба они квадратичны в пространстве. Во-первых, вычисление характеристического полинома (квадратичного) и поиск корней. Во-вторых, это использование некоторых методов аппроксимации, которые все должны хранить в модифицированной матрице (но я не могу подробно остановиться на этом, я давно изучал числовую линейную алгебру). О(N2)N×N
лет»
1
Чтобы расширить точку зрения @Yuval Filmus, сложность пространства весьма чувствительна к конкретной модели вычислений. В частности, поскольку выходные данные имеют линейный размер, можно использовать трюки, используя выходную ленту в качестве рабочего пространства, если модель четко не определяет выходную ленту только для записи. Чтобы избежать таких проблем, я хотел бы перефразировать их как решение проблем (например, в качестве входных трех матриц, проверьте, является ли третье произведение первых двух). Не могли бы вы указать модель, которую вы имели в виду? (Кроме того, мне не известны книги о сложности космоса, и я также не нашел полезных обзоров.)
Андрас Саламон
Что касается @ AndrásSalamon, то полезная для меня версия решения может быть такова: является k-е собственное значение больше, чем q. для целого числа k и рационального q. Благодарю.
Гил

Ответы:

20

Варианты решения многих общих задач в линейной алгебре над целыми числами (или рациональными числами) находятся в классе , см. СтатьюDЕT

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

содержится в D S P A C E ( журнал 2 ) .DЕTDSпAСЕ(журнал2)

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

1) В можно вычислить коэффициенты характеристического полинома.DSпAСЕ(журнал2)

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

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

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

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

Lограмм2NС2

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