Увожаемые форумчане, кто-либо имеет отношение к этой тематике?

Здравствуйте, Drednout, Вы писали:

D>Увожаемые форумчане, кто-либо имеет отношение к этой тематике?

А можно постановку задачи уточнить?
Посмотрите теорию здесь.

Здравствуйте, sanok, Вы писали:

S>А можно постановку задачи уточнить?
S>Посмотрите теорию здесь.
У меня есть некая система, различным состояниям которой ставится в соответствие симметричные квадратные матрицы. И нужны часть собственных значений и собственных векторов этих матриц. Дело еще в том, что матрицы большого размера (до 40000*40000), а у меня всего 8 гигов памяти. Вот и ищу быстрый и экономный алгоритм диагонализации.

Здравствуйте, Drednout, Вы писали:

D>Здравствуйте, sanok, Вы писали:

S>>А можно постановку задачи уточнить?
S>>Посмотрите теорию здесь.
D>У меня есть некая система, различным состояниям которой ставится в соответствие симметричные квадратные матрицы. И нужны часть собственных значений и собственных векторов этих матриц. Дело еще в том, что матрицы большого размера (до 40000*40000), а у меня всего 8 гигов памяти. Вот и ищу быстрый и экономный алгоритм диагонализации.

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

x[n+1] = A x[n] / | x[n] |

Если нужен второй (очередной) собственный вектор, то на каждом шаге ветор x[n] нужно проектировать на пространство, перпендикулярное уже найденным векторам.

Здравствуйте, Аноним, Вы писали:

А>Здравствуйте, Drednout, Вы писали:

D>>Здравствуйте, sanok, Вы писали:

S>>>А можно постановку задачи уточнить?
S>>>Посмотрите теорию здесь.
D>>У меня есть некая система, различным состояниям которой ставится в соответствие симметричные квадратные матрицы. И нужны часть собственных значений и собственных векторов этих матриц. Дело еще в том, что матрицы большого размера (до 40000*40000), а у меня всего 8 гигов памяти. Вот и ищу быстрый и экономный алгоритм диагонализации.

А>Для того, чтобы получить несколько (обычно, наибольших) собственных вектором и собственных значений, не обязательно диагонализировать всю матрицу. Есть итеративный алгоритм, который сходится к наибольшему собственному вектору:

А>x[n+1] = A x[n] / | x[n] |

А>Если нужен второй (очередной) собственный вектор, то на каждом шаге ветор x[n] нужно проектировать на пространство, перпендикулярное уже найденным векторам.

Вот здесь чуть более подробно

Здравствуйте, Аноним, Вы писали:

А>Для того, чтобы получить несколько (обычно, наибольших) собственных вектором и собственных значений, не обязательно диагонализировать всю матрицу. Есть итеративный алгоритм, который сходится к наибольшему собственному вектору:

А>x[n+1] = A x[n] / | x[n] |

А>Если нужен второй (очередной) собственный вектор, то на каждом шаге ветор x[n] нужно проектировать на пространство, перпендикулярное уже найденным векторам.

Дело в том, что мне нужен весь отрицательный спектр — это около половины с.з. и соответствующих им с.в. А они уже используются в дальнейших вычислениях.

Здравствуйте, Drednout, Вы писали:

D>Здравствуйте, Аноним, Вы писали:

А>>Для того, чтобы получить несколько (обычно, наибольших) собственных вектором и собственных значений, не обязательно диагонализировать всю матрицу. Есть итеративный алгоритм, который сходится к наибольшему собственному вектору:

А>>x[n+1] = A x[n] / | x[n] |

А>>Если нужен второй (очередной) собственный вектор, то на каждом шаге ветор x[n] нужно проектировать на пространство, перпендикулярное уже найденным векторам.

D>Дело в том, что мне нужен весь отрицательный спектр — это около половины с.з. и соответствующих им с.в. А они уже используются в дальнейших вычислениях.

Часто в задачах возникают матрицы с некими специальными свойствами, кроме симметрии, например, разреженность, или наличие ненулевых элементов только на специальных диагоналях — не тот случай?

Здравствуйте, sanok, Вы писали:

S>Часто в задачах возникают матрицы с некими специальными свойствами, кроме симметрии, например, разреженность, или наличие ненулевых элементов только на специальных диагоналях — не тот случай?

К сожалению, нет. Я пользуюсь пакетом Intel MKL, но в нем алгоритм работы с упакованными матрицами медленный.

Здравствуйте, Drednout, Вы писали:

D>Здравствуйте, sanok, Вы писали:

S>>А можно постановку задачи уточнить?
S>>Посмотрите теорию здесь.
D>У меня есть некая система, различным состояниям которой ставится в соответствие симметричные квадратные матрицы. И нужны часть собственных значений и собственных векторов этих матриц. Дело еще в том, что матрицы большого размера (до 40000*40000), а у меня всего 8 гигов памяти. Вот и ищу быстрый и экономный алгоритм диагонализации.

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

Здравствуйте, VsevolodC, Вы писали:

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

К сожалению, это крайне медленный алгоритм. Современный алгоритм диагонализации разбивается на несколько этапов. Я пользуюсь современным пакетом Intel MKL, в разработке которого принимают участие кадры из ведущих университетов США. Но и он не без греха. Постоянно пасясь на их форуме, слежу за последними новостями и вот что я надыбал: http://software.intel.com/en-us/forums/showthread.php?t=76595&o=d&s=lr . Там и интернетная страница этого товарища есть. Но я ему не очень верю: стянул, наверное. После этого и стал искать везде: если он стянул, то еще кто-то должен знать об этом чудо-алгоритме.

Здравствуйте, Drednout, Вы писали:

D>Здравствуйте, sanok, Вы писали:

S>>Часто в задачах возникают матрицы с некими специальными свойствами, кроме симметрии, например, разреженность, или наличие ненулевых элементов только на специальных диагоналях — не тот случай?

D>К сожалению, нет. Я пользуюсь пакетом Intel MKL, но в нем алгоритм работы с упакованными матрицами медленный.
А диагональное преобладание есть?

Здравствуйте, Warturtle, Вы писали:

W>А диагональное преобладание есть?

Диагонализация симметричной вещественной матрицы — это не решение СЛАУ.

Здравствуйте, Drednout, Вы писали:

D>Здравствуйте, Warturtle, Вы писали:

W>>А диагональное преобладание есть?

D>Диагонализация симметричной вещественной матрицы — это не решение СЛАУ.
Не может быть! Все пропало. Но все-таки: есть или нет?

Здравствуйте, Warturtle, Вы писали:

W>Здравствуйте, Drednout, Вы писали:

D>>Здравствуйте, Warturtle, Вы писали:

W>>>А диагональное преобладание есть?

D>>Диагонализация симметричной вещественной матрицы — это не решение СЛАУ.
W>Не может быть! Все пропало. Но все-таки: есть или нет?

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

Здравствуйте, Drednout, Вы писали:

D>Здравствуйте, Warturtle, Вы писали:

W>>Здравствуйте, Drednout, Вы писали:

D>>>Здравствуйте, Warturtle, Вы писали:

W>>>>А диагональное преобладание есть?

D>>>Диагонализация симметричной вещественной матрицы — это не решение СЛАУ.
W>>Не может быть! Все пропало. Но все-таки: есть или нет?

D>Вы сначала объясните, как связана диагонализация симметричной вещественной матрицы с диагональным преобладанием: я лично впервые узнал о возможности такой связи от Вас. А если Вы не это имели в виду, то в чем смысл вопроса?
Например, есть метод "обратных итераций" (или "обратных итераций со сдвигом"), в котором на каждом шаге нужно решать СЛАУ (но с одной и той же матрицей!) — этот метод может сходиться быстрее степенного метода. Подробности можно посмотреть, например, в книжке Икрамова "Несимметричная проблема собственных значений" (gen.lib.rus.ec что-то не работает, но найти наверное можно). А матрицу с диагональным преобладанием обращать (или приводить к треугольному виду) обычно легче, оттого и спросил.

Здравствуйте, Warturtle, Вы писали:

W>Например, есть метод "обратных итераций"... Подробности можно посмотреть, например, в книжке Икрамова "Несимметричная проблема собственных значений"... А матрицу с диагональным преобладанием обращать (или приводить к треугольному виду) обычно легче, оттого и спросил.

Дело в том, что несимметричная проблема собственных значений к симметричной проблеме собственных значений никакого отношения не имеет. Метод "обратных итераций" в проблеме с.в. и с.з. для симметричных матриц имеет быть место, но совершенно в другом аспекте. Вот тут некий товарищ далеко продвинулся в этом вопросе, значительно переплюнув знаменитую фирму Intel: http://software.intel.com/en-us/forums/showthread.php?t=76595&o=d&s=lr,а также http://software.intel.com/en-us/forums/showthread.php?t=73653&o=d&s=lr , http://depositfiles.com/files/fmy2ueaad (я о нем уже писал, и все ссылки мною найдены на форуме Intel), но не очень верится, что он все это сделал сам.

Здравствуйте, Drednout, Вы писали:

D>Здравствуйте, Warturtle, Вы писали:

W>>Например, есть метод "обратных итераций"... Подробности можно посмотреть, например, в книжке Икрамова "Несимметричная проблема собственных значений"... А матрицу с диагональным преобладанием обращать (или приводить к треугольному виду) обычно легче, оттого и спросил.

D>Дело в том, что несимметричная проблема собственных значений к симметричной проблеме собственных значений никакого отношения не имеет. Метод "обратных итераций" в проблеме с.в. и с.з. для симметричных матриц имеет быть место, но совершенно в другом аспекте. Вот тут некий товарищ далеко продвинулся в этом вопросе, значительно переплюнув знаменитую фирму Intel: http://software.intel.com/en-us/forums/showthread.php?t=76595&o=d&s=lr,а также http://software.intel.com/en-us/forums/showthread.php?t=73653&o=d&s=lr , http://depositfiles.com/files/fmy2ueaad (я о нем уже писал, и все ссылки мною найдены на форуме Intel), но не очень верится, что он все это сделал сам.
Ээээ... Как понимать "несимметричная проблема собственных значений к симметричной проблеме собственных значений никакого отношения не имеет" — то есть метод не работает, так что-ли? Я бы не стал делать далеко идущих выводов только из названия книжки.

Здравствуйте, Warturtle, Вы писали:

W>Здравствуйте, Drednout, Вы писали:

D>>Здравствуйте, Warturtle, Вы писали:

W>>>Например, есть метод "обратных итераций"... Подробности можно посмотреть, например, в книжке Икрамова "Несимметричная проблема собственных значений"... А матрицу с диагональным преобладанием обращать (или приводить к треугольному виду) обычно легче, оттого и спросил.

D>>Дело в том, что несимметричная проблема собственных значений к симметричной проблеме собственных значений никакого отношения не имеет. Метод "обратных итераций" в проблеме с.в. и с.з. для симметричных матриц имеет быть место, но совершенно в другом аспекте. Вот тут некий товарищ далеко продвинулся в этом вопросе, значительно переплюнув знаменитую фирму Intel: http://software.intel.com/en-us/forums/showthread.php?t=76595&o=d&s=lr,а также http://software.intel.com/en-us/forums/showthread.php?t=73653&o=d&s=lr , http://depositfiles.com/files/fmy2ueaad (я о нем уже писал, и все ссылки мною найдены на форуме Intel), но не очень верится, что он все это сделал сам.
W>Ээээ... Как понимать "несимметричная проблема собственных значений к симметричной проблеме собственных значений никакого отношения не имеет" — то есть метод не работает, так что-ли? Я бы не стал делать далеко идущих выводов только из названия книжки.

"никакого отношения не имеет": в том смысле, что не имеет смысла применять методы обработки несимметричных матриц к симметричным матрицам.Проблема с.з. для эрмитовых матриц проще чем для матриц общего вида. Эрмитова матрица всегда имеет линейные элементарные делители и всегда существует унитарная матрица, приводящая исходную матрицу к диагональной форме. Собственные значения всегда вещественны, а малые возмущения в элементах исходной матрицы приводят к малым возмущениям в собственных значениях. Хотя собственные векторы не обязательно хорошо определены, их плохое определение связано с близкими собственными значениями. Советую Вам почитать книгу: Дж.Х. Уилкинсон "Алгебраическая проблема собственных значений".

Здравствуйте, Drednout, Вы писали:

D>Здравствуйте, Warturtle, Вы писали:

W>>Здравствуйте, Drednout, Вы писали:

D>>>Здравствуйте, Warturtle, Вы писали:

W>>>>Например, есть метод "обратных итераций"... Подробности можно посмотреть, например, в книжке Икрамова "Несимметричная проблема собственных значений"... А матрицу с диагональным преобладанием обращать (или приводить к треугольному виду) обычно легче, оттого и спросил.

D>>>Дело в том, что несимметричная проблема собственных значений к симметричной проблеме собственных значений никакого отношения не имеет. Метод "обратных итераций" в проблеме с.в. и с.з. для симметричных матриц имеет быть место, но совершенно в другом аспекте. Вот тут некий товарищ далеко продвинулся в этом вопросе, значительно переплюнув знаменитую фирму Intel: http://software.intel.com/en-us/forums/showthread.php?t=76595&o=d&s=lr,а также http://software.intel.com/en-us/forums/showthread.php?t=73653&o=d&s=lr , http://depositfiles.com/files/fmy2ueaad (я о нем уже писал, и все ссылки мною найдены на форуме Intel), но не очень верится, что он все это сделал сам.
W>>Ээээ... Как понимать "несимметричная проблема собственных значений к симметричной проблеме собственных значений никакого отношения не имеет" — то есть метод не работает, так что-ли? Я бы не стал делать далеко идущих выводов только из названия книжки.

D>"никакого отношения не имеет": в том смысле, что не имеет смысла применять методы обработки несимметричных матриц к симметричным матрицам.Проблема с.з. для эрмитовых матриц проще чем для матриц общего вида. Эрмитова матрица всегда имеет линейные элементарные делители и всегда существует унитарная матрица, приводящая исходную матрицу к диагональной форме. Собственные значения всегда вещественны, а малые возмущения в элементах исходной матрицы приводят к малым возмущениям в собственных значениях. Хотя собственные векторы не обязательно хорошо определены, их плохое определение связано с близкими собственными значениями. Советую Вам почитать книгу: Дж.Х. Уилкинсон "Алгебраическая проблема собственных значений".
Спасибо, читал=)

Здравствуйте, Drednout, Вы писали:

D>Здравствуйте, Warturtle, Вы писали:

W>>Здравствуйте, Drednout, Вы писали:

D>>>Здравствуйте, Warturtle, Вы писали:

W>>>>Например, есть метод "обратных итераций"... Подробности можно посмотреть, например, в книжке Икрамова "Несимметричная проблема собственных значений"... А матрицу с диагональным преобладанием обращать (или приводить к треугольному виду) обычно легче, оттого и спросил.

D>>>Дело в том, что несимметричная проблема собственных значений к симметричной проблеме собственных значений никакого отношения не имеет. Метод "обратных итераций" в проблеме с.в. и с.з. для симметричных матриц имеет быть место, но совершенно в другом аспекте. Вот тут некий товарищ далеко продвинулся в этом вопросе, значительно переплюнув знаменитую фирму Intel: http://software.intel.com/en-us/forums/showthread.php?t=76595&o=d&s=lr,а также http://software.intel.com/en-us/forums/showthread.php?t=73653&o=d&s=lr , http://depositfiles.com/files/fmy2ueaad (я о нем уже писал, и все ссылки мною найдены на форуме Intel), но не очень верится, что он все это сделал сам.
W>>Ээээ... Как понимать "несимметричная проблема собственных значений к симметричной проблеме собственных значений никакого отношения не имеет" — то есть метод не работает, так что-ли? Я бы не стал делать далеко идущих выводов только из названия книжки.

D>"никакого отношения не имеет": в том смысле, что не имеет смысла применять методы обработки несимметричных матриц к симметричным матрицам.Проблема с.з. для эрмитовых матриц проще чем для матриц общего вида. Эрмитова матрица всегда имеет линейные элементарные делители и всегда существует унитарная матрица, приводящая исходную матрицу к диагональной форме. Собственные значения всегда вещественны, а малые возмущения в элементах исходной матрицы приводят к малым возмущениям в собственных значениях. Хотя собственные векторы не обязательно хорошо определены, их плохое определение связано с близкими собственными значениями. Советую Вам почитать книгу: Дж.Х. Уилкинсон "Алгебраическая проблема собственных значений".
Еще насчет "не имеет смысла применять методы обработки несимметричных матриц к симметричным матрицам". Метод обратных итераций (как степенной метод) не является "заточенным" под несимметричную задачу. Более того, для эрмитовых матриц он ведет себя лучше. Пара цитат (из книги Икрамова):

Однако первое исчерпывающее описание локального поведения RQI
и некоторых его вариантов дано в цикле работ Островского [150]. В частности,
Островский доказал, что для эрмитовой матрицы А сходимость RQI
асимптотически кубическая... Следующим шагом после работ Островского было описание глобального
поведения RQI в эрмитовом случае, полученное в 1966 г. Каханом... Малые возмущения векторов хк выводят из этого особого случая и возвращают
процесс к основному варианту с асимптотически кубической сходимостью... Однако асимптотическая сходимость метода для
анормальных матриц очень медленная — в лучшем случае линейная...

RQI — это вариант обратной итерации.
Кроме того, специально посмотрел в книгу Уилкинсона и что же — параграф "Обратная итерация" отчего-то располагается в главе "Эрмитовы матрицы", что какбэ неспроста