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

Здравствуйте, 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 — это вариант обратной итерации.
Кроме того, специально посмотрел в книгу Уилкинсона и что же — параграф "Обратная итерация" отчего-то располагается в главе "Эрмитовы матрицы", что какбэ неспроста

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

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

D>Все эта информация с бородой. Метод обратной итерации в случае симметричных матриц применяется при нахождении с.в. трехдиагональных м-ц, полученных в результате приведения исходных матриц к трехдиагональной форме. Но возникают проблемы с ортогональностью собственных векторов в случае вырожденных с.з. Исправить этот недочет должен был RRR алгоритм, разработанный в конце прошлого тысячелетия. Но и у него свои проблемы, о которых говорил товарищ (я на него ссылку давал). Но он фиксирует проблемы, приводит свои фантастические результаты, но о самом этом чуде-алгоритме ничего, к сожалению, не говорит.
Исходные матрицы приводят к 3-диагональной форме, т.к. их обращать (разлагать в LU) очень просто. Но они (исходные) могут иметь какую-то специальную структуру — блочно-трехдиагональные, например, ну и/или имеют еще какие-нить хорошие свойства. Тогда есть довольно эффективные варианты различных неполных разложений (в качестве предобуславливателей), с которыми итерационный процесс обращения сходится быстро. Поэтому не исключено, что приведение к 3-диагональному виду может не понадобиться.

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

W>Исходные матрицы приводят к 3-диагональной форме, т.к. их обращать (разлагать в LU) очень просто.

К трехдиагонализации это не имеет никакого отношкния.

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

D>К трехдиагонализации это не имеет никакого отношкния.

Гм. Последний раз я занимался диагонализацией матриц лет так 25 назад, поэтому что там нового — не знаю. Но в памяти осталось, что метод Хаусхолдера как раз и заключается в приведении к трехдиагональной форме. Посмотрел — так и есть.

http://www.cyberguru.ru/programming/programming-theory/matrix-vectors-values-page8.html

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

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

W>>Исходные матрицы приводят к 3-диагональной форме, т.к. их обращать (разлагать в LU) очень просто.

D>К трехдиагонализации это не имеет никакого отношкния.
А зачем тогда?

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

PD>метод Хаусхолдера как раз и заключается в приведении к трехдиагональной форме.

Да, это самый эффективный метод на сегодняшний день, но конечно не в том примитивном виде, как 25 лет назад. Единственный его существенный недостаток — это 2/3 операций от общего числа сложений и умножений жрет BLAS Level 2, а он очень плохо распараллеливается. Впрочем, на последних процессорах, где оперативная память завязана на процессор, лед, как говорится, тронулся и тронулся прилично (на предыдущих процессорвх BLAS Level 2 не имело смысла распараллеливать).

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

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

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

PD>>метод Хаусхолдера как раз и заключается в приведении к трехдиагональной форме.

D>Да, это самый эффективный метод на сегодняшний день, но конечно не в том примитивном виде, как 25 лет назад. Единственный его существенный недостаток — это 2/3 операций от общего числа сложений и умножений жрет BLAS Level 2, а он очень плохо распараллеливается. Впрочем, на последних процессорах, где оперативная память завязана на процессор, лед, как говорится, тронулся и тронулся прилично (на предыдущих процессорвх BLAS Level 2 не имело смысла распараллеливать).

Я не специалист по проблеме собственных значений, но вот c распараллеливанием Level 2 Blas сталкивался. И на мой взгялд, он неплохо распараллеливается Может конечно у нас разные понятия о "плохо" или мы просто польуемся разными наборами функций, но лично я реализовывал sparse matrix-vector multiply на CUDA с неплохим ускорением.
Я последние полгода немножко выпал из темы, но насколько мне видится, state-of-the-art в этом — работа здесь, где они хвастаются ускорением в 90 раз на GTX 295 по сравнениию с CoreDuo 8400

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

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

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

PD>>>метод Хаусхолдера как раз и заключается в приведении к трехдиагональной форме.

D>>Да, это самый эффективный метод на сегодняшний день, но конечно не в том примитивном виде, как 25 лет назад. Единственный его существенный недостаток — это 2/3 операций от общего числа сложений и умножений жрет BLAS Level 2, а он очень плохо распараллеливается. Впрочем, на последних процессорах, где оперативная память завязана на процессор, лед, как говорится, тронулся и тронулся прилично (на предыдущих процессорвх BLAS Level 2 не имело смысла распараллеливать).

SC>Я не специалист по проблеме собственных значений, но вот c распараллеливанием Level 2 Blas сталкивался. И на мой взгялд, он неплохо распараллеливается Может конечно у нас разные понятия о "плохо" или мы просто польуемся разными наборами функций, но лично я реализовывал sparse matrix-vector multiply на CUDA с неплохим ускорением.
SC>Я последние полгода немножко выпал из темы, но насколько мне видится, state-of-the-art в этом — работа здесь, где они хвастаются ускорением в 90 раз на GTX 295 по сравнениию с CoreDuo 8400

Смотря какой BLAS Level 2: дело в том, что в трехдиагонализации число операций пропорционально n в кубе. Вот Вы возьмите и попробуйте трехдиагонализацию распараллелить и получите фиг в кармане. И 90 раз — это с одинарной точностью, в серьезных научных задачах она на фиг не нужна. А для двойной точности скорость упадет раз в десять. И отсутствие кэша тоже затормозит задачу раз в 10 (современные алгоритмы диагонализации используют блочные методы обработки информации, а для них отсутствие кэша — это всё равно, что для рыбы отсутствие воды). И куда девался их выигрыш? И потом, сколько там памяти? Попробуйте, например, диагонализировать матрицу 40000*40000. Пока CUDA — это для лохов.

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

D> Смотря какой BLAS Level 2: дело в том, что в трехдиагонализации число операций пропорционально n в кубе. Вот Вы возьмите и попробуйте трехдиагонализацию распараллелить и получите фиг в кармане.
Конечно, я имею в виду грамотно написанный алгоритм, когда на 1-м ядре уже ничего не выжать.

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


D> Смотря какой BLAS Level 2: дело в том, что в трехдиагонализации число операций пропорционально n в кубе. Вот Вы возьмите и попробуйте трехдиагонализацию распараллелить и получите фиг в кармане. И 90 раз — это с одинарной точностью, в серьезных научных задачах она на фиг не нужна. А для двойной точности скорость упадет раз в десять. И отсутствие кэша тоже затормозит задачу раз в 10 (современные алгоритмы диагонализации используют блочные методы обработки информации, а для них отсутствие кэша — это всё равно, что для рыбы отсутствие воды). И куда девался их выигрыш? И потом, сколько там памяти? Попробуйте, например, диагонализировать матрицу 40000*40000. Пока CUDA — это для лохов.

Ну допустим кэш там есть, самый разнообразный и памяти на тесле до 4 гигов и двойную точность на тесле(ферми) обещают с нормальной скоростью(правда, сам не щупал). И разреженную СЛАУ размером 350к я решал, правда ненулевых элементов там было мегабайт на 100 от силы.

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

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


D>> Смотря какой BLAS Level 2: дело в том, что в трехдиагонализации число операций пропорционально n в кубе. Вот Вы возьмите и попробуйте трехдиагонализацию распараллелить и получите фиг в кармане. И 90 раз — это с одинарной точностью, в серьезных научных задачах она на фиг не нужна. А для двойной точности скорость упадет раз в десять. И отсутствие кэша тоже затормозит задачу раз в 10 (современные алгоритмы диагонализации используют блочные методы обработки информации, а для них отсутствие кэша — это всё равно, что для рыбы отсутствие воды). И куда девался их выигрыш? И потом, сколько там памяти? Попробуйте, например, диагонализировать матрицу 40000*40000. Пока CUDA — это для лохов.

SC>Ну допустим кэш там есть, самый разнообразный и памяти на тесле до 4 гигов и двойную точность на тесле(ферми) обещают с нормальной скоростью(правда, сам не щупал). И разреженную СЛАУ размером 350к я решал, правда ненулевых элементов там было мегабайт на 100 от силы.

Утюг Tesla S1070 имеет еще более впечатляющие характеристики. А настоящий кэш очень дорог. Думаю, что с ним этот утюг стоил бы не около 10000$, а раз в десять дорже. Что касается СЛАУ с разреженными матрицми, то, например, задачи, заданные на графе типа дерева, можно и на ручном калькуляторе решать (число операций пропорционально размерности задачи). Вы меня не совсем правильно поняли: в этой теме речь идет не об утюгах,- я на это и намекал.

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

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

А я ошибался по поводу этого товарища: он и исходный код приводит
http://software.intel.com/ru-ru/forums/showpost.php?p=128709
Да, не перевелись еще яйцеголовые на Руси.