Диагонализация плотных плохо обусловленных матриц

Я пытаюсь диагонализировать некоторые плотные, плохо обусловленные матрицы. В машинной точности результаты являются неточными (возвращая отрицательные собственные значения, собственные векторы не имеют ожидаемой симметрии). Я переключился на функцию Eigensystem [] Mathematica, чтобы использовать преимущества произвольной точности, но вычисления очень медленные. Я открыт для любого количества решений. Существуют ли пакеты / алгоритмы, которые хорошо подходят для плохо обусловленных проблем? Я не эксперт по предварительному кондиционированию, поэтому я не уверен, насколько это может помочь. В противном случае все, о чем я могу думать, - это распараллеленные решатели на собственные значения произвольной точности, но я не знаком ни с чем, кроме Mathematica, MATLAB и C ++.

Чтобы дать некоторое представление о проблеме, матрицы большие, но не огромные (максимум от 4096x4096 до 32768x32768). Они действительны, симметричны, и собственные значения ограничены между 0 и 1 (исключая), причем многие собственные значения очень близки к 0 и ни один не близок к 1. Матрица по существу является оператором свертки. Мне не нужно диагоналировать все мои матрицы, но чем больше я могу пойти, тем лучше. У меня есть доступ к вычислительным кластерам со многими процессорами и возможностями распределенных вычислений.

Спасибо

linear-algebra parallel-computing eigensystem precision dense-matrix Leigh
источник

Какую процедуру вы используете для диагонализации ваших реальных симметричных матриц? И в каком смысле неточное разложение по собственным значениям?

Джек Полсон,

Вот идея, связанная с ответом Арнольда: выполните декомпозицию Холецкого вашей SPD-матрицы, а затем найдите сингулярные значения только что полученного треугольника Холески, возможно, используя алгоритм типа dqd для сохранения точности.

@JM: Формирование декомпозиции Холецкого численно-положительной положительно-определенной матрицы численно нестабильно с обычным методом, поскольку, вероятно, встречаются отрицательные точки. (Например, chol (A) в Matlab обычно не работает.) Нужно было бы установить их на ноль и уничтожить соответствующие строки факторов. Это дает возможность надежно получить числовое нулевое пространство.

Арнольд Ноймайер

@Arnold, если память, есть адаптации Холецкого , которые используют симметричный поворот для тех случаев , когда матрица положителен пол -definite (или почти так). Может быть, они могут быть использованы ...

@JM: не нужно поворачиваться, чтобы разрешить полуопределенный случай; рецепт, который я дал, достаточно. Я просто хотел отметить, что нельзя использовать стандартные консервированные программы, но нужно изменить их самостоятельно.

Арнольд Ноймайер

Ответы:

Рассчитайте СВД вместо спектрального разложения. Результаты одинаковы в точной арифметике, так как ваша матрица симметрична положительно определена, но в арифметике конечной точности вы получите маленькие собственные значения с гораздо большей точностью.

Редактировать: См. Деммель и Кахан, Точные сингулярные значения двухдиагональных матриц, SIAM J. Sci. Стат. Вычи. 11 (1990), 873-912.
ftp://netlib2.cs.utk.edu/lapack/lawnspdf/lawn03.pdf

Edit2; Обратите внимание, что ни один метод не сможет разрешить собственные значения, меньшие, чем примерно норма, умноженная на точность используемой машины, так как изменение одной записи на один ulp может уже на столько изменить небольшое собственное значение. Таким образом, получение нулевых собственных значений вместо очень крошечных является целесообразным, и никакой метод (кроме работы с более высокой точностью) не будет распутывать соответствующие собственные векторы, а просто возвращает основу для общего числового нулевого пространства.

Арнольд Ноймайер
источник

Я не уверен, что верю в это, так как большинство реализаций SVD начинаются с унитарного приведения к реальной двухдиагональной форме и затем по существу вычисляют эрмитово EVD связанной матрицы, такой как , которую легко переставить в вещественную симметричную трехугольную форму. Относительная точность сильно зависит от того, какой метод используется для решения сжатого EVP / SVD, и я не вижу, в чем преимущество SVD ... Я уверен, что это обсуждается в одной или нескольких статьях Деммеля.

[0, B^{T}; B, 0]

$[0, B^T; B, 0]$

Джек Поулсон

@JackPoulson: Дело в том, что двунаправленная форма намного лучше определяет малые сингулярные значения. Соответствующая симметричная трехдиагональная форма имеет нули на диагонали, которые сохраняются при двунаправленном уменьшении до диагонали, но не QR, применяемом к трехдиагональной.

Арнольд Ноймайер

Ссылка? Известно, что метод Якоби является очень точным (хотя и медленным).

Джек Поулсон

@JackPoulson: попробуй и посмотри. Деммель и Кахан, Точные единичные значения двухдиагональных матриц, 202.38.126.65/oldmirrors/ftp.netlib.org/lapack/lawnspdf/…

Арнольд Ноймайер,

Я вижу, к чему вы стремитесь: алгоритм QR для двухдиагональной SVD может быть сделан относительно точным из-за нулевой диагонали переставленных матрица, в то время как этот метод «нулевого сдвига» не работает для произвольных трехдиагональных матриц, поэтому трехдиагональные EVP на основе QR-алгоритма будут менее точными для малых собственных значений. Суть в том, что это рассуждение предполагает собственный алгоритм, основанный на использовании алгоритма QR в сжатой форме; Якоби является заметным исключением, но, возможно, он медленнее, чем SVD на основе QR-алгоритма. MRRR может иногда также достигать высокой относительной точности.

[0, B^{T}; B, 0]

$[0,B^T; B,0]$

Джек Полсон

Спасибо за это предложение. Я попробовал команду SVD Mathematica, но я не получил заметного улучшения (все еще не хватает соответствующих симметрий, «собственные значения» неправильно равны нулю там, где они ранее неправильно выходили отрицательными). Может быть, мне потребуется реализовать один из описанных выше алгоритмов вместо встроенной функции? Я бы, вероятно, хотел бы избежать проблем, связанных с использованием определенного метода, подобного этому, если я не был заранее уверен, что он предложит значительное улучшение.

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

Leigh
источник

Я не проверял это, но здесь есть реализация MATLAB: groups.google.com/forum/?fromgroups#!msg/sci.math.num-analysis/…

Джек Полсон,

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

Арнольд Ноймайер

@ArnoldNeumaier: Я провел несколько тестов в MATLAB с собственными значениями в диапазоне [0,1], с одним собственным значением, вручную установленным на значения, такими как 6.3e-16, и процедурой SVD Октавы (основанной на dgesvd, которая использует приведение к бидиагоналу и затем QR) собирает эти значения гораздо точнее, чем Eig Октавии. Связанный код Якоби, кажется, слишком медленный для использования, даже на скромных матрицах.

Джек Поулсон

@ ДжекПулсон: Да. Но Ли, похоже, жалуется на множественные очень маленькие собственные значения, и их собственные векторы редко будут такими, которые рассчитаны, но будут смешиваться свободно, независимо от того, какой метод используется. И положительные очень крошечные положительные значения (меньше чем 1e-16), конечно, будут найдены равными нулю.

Арнольд Ноймайер

@ArnoldNeumaier прав в том, что я нахожу несколько очень маленьких собственных значений, которые, я думаю, усугубляет проблему. Я не осознавал (хотя в ретроспективе это очевидно), что собственные значения меньше 1e-16 будут равны нулю в плавающей точке. Я думаю, хотя число может быть сохранено, ошибка округления возникает при добавлении его к большему числу. Собственные векторы говорят мне, если определенная проблема разрешима. Собственный вектор позволяет разложить задачу на разрешимые и неразрешимые части. Если я принципиально ограничен в точности, то можете ли вы порекомендовать какие-либо пакеты для более быстрого решения?

Ли