Сложность нахождения собственного разложения матрицы

40

Мой вопрос прост:

Что наихудшее время работы наилучшего известного алгоритма для вычисления eigendecomposition в качестве матрицы? $n \times n$

Собственное разложение сводится к умножению матриц или в худшем случае наиболее известные алгоритмы (через SVD )? $O(n^3)$

Обратите внимание, что я прошу провести анализ наихудшего случая (только в терминах ), а не для границ с зависимыми от задачи константами, такими как номер условия. $n$

РЕДАКТИРОВАТЬ : Учитывая некоторые ответы ниже, позвольте мне уточнить вопрос: я был бы счастлив с $\epsilon$ -приближением. Аппроксимация может быть мультипликативной, аддитивной, входной или любым разумным определением, которое вы хотите. Мне интересно, есть ли известный алгоритм, который имеет лучшую зависимость от $n$ чем что-то вроде $O(\mathrm{poly}(1/\epsilon)n^3)$ ?

РЕДАКТИРОВАТЬ 2 : см. Этот связанный вопрос на симметричных матриц .

ds.algorithms time-complexity matrices linear-algebra na.numerical-analysis Лев Рейзин
источник

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

Уоррен Шуди

Да, кажется, они распространяются на поиск LU-разложения, но я не знаю, как заставить это работать для собственного разложения.

Лев Рейзин

Знаете ли вы, если

O (n^{3})

$O(n^3)$ является самым известным алгоритмом для вычисления SVD?

Робин Котари

1

O (min (m n^{2}, m^{2} n))

$O(\min(mn^2, m^2n))$

n \times n

$n \times n$

Хорошо. Я тоже не очень разбираюсь в этой области, но, возможно, вычисление SVD можно свести к собственному разложению, поскольку, если вы сможете самостоятельно разложить AA * и A * A, вы получите правую и левую матрицы для SVD.

Робин Котари

18

Райан ответил на аналогичный вопрос о mathoverflow. Вот ссылка: mathoverflow-answer

По сути, вы можете уменьшить вычисление собственных значений до умножения матриц, вычисляя символьный определитель. Это дает время работы O ( ), чтобы получить битов собственных значений; наилучшее известное время выполнения - O ( ) для приближения в пределах . $n^{\omega+1}m$ $m$ $n^3+n^2\log^2 n\log b$ $2^{-b}$

Ссылка Райана: `` Виктор Й. Пан, Чжао К. Чен: Сложность матричной собственной проблемы. STOC 1999: 507-516 ''.

(Я полагаю, что существует дискуссия о взаимосвязи между сложностями собственных значений и умножением матриц в более ранней книге Aho, Hopcroft и Ullman `` Разработка и анализ компьютерных алгоритмов '', однако у меня нет книги в передо мной, и я не могу дать вам точный номер страницы.)

Virgi
источник

13

Поиск собственных значений по своей природе является итеративным процессом: поиск собственных значений эквивалентен нахождению корней многочлена. Более того, теорема Абеля – Руффини утверждает, что в общем случае вы не можете выразить корни произвольного многочлена в простой замкнутой форме (т. Е. С радикалами, подобными квадратной формуле). Таким образом, вы не можете надеяться вычислить собственные значения «точно».

Это означает, что алгоритм спектрального разложения должен быть приближенным. Время выполнения любого общего алгоритма должно зависеть от желаемой точности; это не может зависеть только от измерения.

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

Ознакомьтесь с http://en.wikipedia.org/wiki/List_of_numeric_analysis_topics#Eigenvalue_algorithms

Томас
источник

Спасибо за ваш ответ - мне нужно время, чтобы переварить это! Но если использовать умножение матрицы на вектор, зависимость от n, возможно, будет лучше, чем n ^ 3.

Лев Рейзин

6

Я дам только частичный ответ, касающийся собственных значений матрицы.

Как упоминалось ранее, существует много итерационных методов для нахождения собственных значений матрицы (например, степенная итерация), но в целом нахождение собственных значений сводится к нахождению корней характеристического полинома. Найти характеристический многочлен можно в , где $O(n^3 M_B[n(log n + L)] )$ $M_B(s)$ $s$ $L$ , См. Книгу Япа о «Основах алгоритмической алгебры» , в частности, гл. 10, «Линейные системы» .

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

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

user834
источник

интересно, но это кажется еще хуже, чем п ^ 3. мы знаем, что это самое лучшее?

Лев Рейзин

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

user834

Таким образом, вы говорите, что если меня не волнуют проблемы со стабильностью чисел, мы можем уменьшить его до O (n ^ 2.376)?

Лев Рейзин

5

Вы можете проверить новую статью Commandur и Kale, в которой дан комбинаторный алгоритм для Max-Cut. Кажется (из беглого прочтения), что их алгоритм основан на комбинаторном нахождении собственного вектора, соответствующего максимальному собственному значению, и затем использовании алгоритма Луки Тревизана, как только у них есть этот собственный вектор.

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

звездочка
источник

1

Это старый вопрос, но некоторая важная литература, кажется, пропущена.

$(O^{\omega+\eta})$ $\omega$ $\eta$ $>0$

Да, есть статья Пан + Чэнь + Чжэн, в которой предлагается собрать характеристический полином и вычислить в BigFloat, потому что в конце вы теряете много битов точности, но не многие люди считают это практическим подходом.

Я также упоминаю, что наиболее широко используемый алгоритм, итерация Фрэнсиса QR, не имеет доказательств сходимости для общих матриц; В книге Кресснера обсуждаются несколько контрпримеров.

Себастьян Луазель
источник

0

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

Вот еще одна ссылка - быстрая линейная алгебра стабильна http://www.netlib.org/lapack/lawnspdf/lawn186.pdf

анонимное
источник

3

Спасибо за указатель, но, выполняя поиск по книге в книгах Google, я не смог найти сокращения для умножения матриц. У вас есть указатель на какую-то конкретную ссылку или алгоритм? И их алгоритмы SVD, похоже, зависят от номера условия матрицы, что не является худшим анализом ситуации. Что касается проблем числовой стабильности и т. Д., Давайте предположим идеализированный случай, когда все умножения и деления занимают единицу времени и дают точные ответы.

Лев Рейзин

Сложность нахождения собственного разложения матрицы

Ответы: