Все эта информация с бородой. Метод обратной итерации в случае симметричных матриц применяется при нахождении с.в. трехдиагональных м-ц, полученных в результате приведения исходных матриц к трехдиагональной форме. Но возникают проблемы с ортогональностью собственных векторов в случае вырожденных с.з. Исправить этот недочет должен был RRR алгоритм, разработанный в конце прошлого тысячелетия. Но и у него свои проблемы, о которых говорил товарищ (я на него ссылку давал). Но он фиксирует проблемы, приводит свои фантастические результаты, но о самом этом чуде-алгоритме ничего, к сожалению, не говорит.
Re[17]: о алгоритмах диагонализации вещественных симметричны
Здравствуйте, Drednout, Вы писали:
D>Все эта информация с бородой. Метод обратной итерации в случае симметричных матриц применяется при нахождении с.в. трехдиагональных м-ц, полученных в результате приведения исходных матриц к трехдиагональной форме. Но возникают проблемы с ортогональностью собственных векторов в случае вырожденных с.з. Исправить этот недочет должен был RRR алгоритм, разработанный в конце прошлого тысячелетия. Но и у него свои проблемы, о которых говорил товарищ (я на него ссылку давал). Но он фиксирует проблемы, приводит свои фантастические результаты, но о самом этом чуде-алгоритме ничего, к сожалению, не говорит.
Исходные матрицы приводят к 3-диагональной форме, т.к. их обращать (разлагать в LU) очень просто. Но они (исходные) могут иметь какую-то специальную структуру — блочно-трехдиагональные, например, ну и/или имеют еще какие-нить хорошие свойства. Тогда есть довольно эффективные варианты различных неполных разложений (в качестве предобуславливателей), с которыми итерационный процесс обращения сходится быстро. Поэтому не исключено, что приведение к 3-диагональному виду может не понадобиться.
Re[18]: о алгоритмах диагонализации вещественных симметричны
Здравствуйте, Drednout, Вы писали:
D>К трехдиагонализации это не имеет никакого отношкния.
Гм. Последний раз я занимался диагонализацией матриц лет так 25 назад, поэтому что там нового — не знаю. Но в памяти осталось, что метод Хаусхолдера как раз и заключается в приведении к трехдиагональной форме. Посмотрел — так и есть.
Здравствуйте, Drednout, Вы писали:
D>Здравствуйте, Warturtle, Вы писали:
W>>Исходные матрицы приводят к 3-диагональной форме, т.к. их обращать (разлагать в LU) очень просто.
D>К трехдиагонализации это не имеет никакого отношкния.
А зачем тогда?
Re[20]: о алгоритмах диагонализации вещественных симметричны
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>метод Хаусхолдера как раз и заключается в приведении к трехдиагональной форме.
Да, это самый эффективный метод на сегодняшний день, но конечно не в том примитивном виде, как 25 лет назад. Единственный его существенный недостаток — это 2/3 операций от общего числа сложений и умножений жрет BLAS Level 2, а он очень плохо распараллеливается. Впрочем, на последних процессорах, где оперативная память завязана на процессор, лед, как говорится, тронулся и тронулся прилично (на предыдущих процессорвх BLAS Level 2 не имело смысла распараллеливать).
Re[20]: о алгоритмах диагонализации вещественных симметричны
Здравствуйте, Warturtle, Вы писали: W>А зачем тогда?
Я уже отвечал VsevolodC'у:
"овременный алгоритм диагонализации разбивается на несколько этапов. Я пользуюсь современным пакетом Intel MKL, в разработке которого принимают участие кадры из ведущих университетов США. Но и он не без греха. Постоянно пасясь на их форуме, слежу за последними новостями и вот что я надыбал: http://software.intel.com/en-us/forums/showthread.php?t=76595&o=d&s=lr . Там и интернетная страница этого товарища есть. Но я ему не очень верю: стянул, наверное. После этого и стал искать везде: если он стянул, то еще кто-то должен знать об этом чудо-алгоритме."
Вы там найдите интернет-страницу этого товарища: там подробно расписаны все шаги диагонализации на самом современном уровне.
Re[21]: о алгоритмах диагонализации вещественных симметричны
Здравствуйте, 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
Re[22]: о алгоритмах диагонализации вещественных симметричны
Здравствуйте, 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 — это для лохов.
Re[23]: о алгоритмах диагонализации вещественных симметричны
Здравствуйте, Drednout, Вы писали:
D> Смотря какой BLAS Level 2: дело в том, что в трехдиагонализации число операций пропорционально n в кубе. Вот Вы возьмите и попробуйте трехдиагонализацию распараллелить и получите фиг в кармане.
Конечно, я имею в виду грамотно написанный алгоритм, когда на 1-м ядре уже ничего не выжать.
Re[23]: о алгоритмах диагонализации вещественных симметричны
D> Смотря какой BLAS Level 2: дело в том, что в трехдиагонализации число операций пропорционально n в кубе. Вот Вы возьмите и попробуйте трехдиагонализацию распараллелить и получите фиг в кармане. И 90 раз — это с одинарной точностью, в серьезных научных задачах она на фиг не нужна. А для двойной точности скорость упадет раз в десять. И отсутствие кэша тоже затормозит задачу раз в 10 (современные алгоритмы диагонализации используют блочные методы обработки информации, а для них отсутствие кэша — это всё равно, что для рыбы отсутствие воды). И куда девался их выигрыш? И потом, сколько там памяти? Попробуйте, например, диагонализировать матрицу 40000*40000. Пока CUDA — это для лохов.
Ну допустим кэш там есть, самый разнообразный и памяти на тесле до 4 гигов и двойную точность на тесле(ферми) обещают с нормальной скоростью(правда, сам не щупал). И разреженную СЛАУ размером 350к я решал, правда ненулевых элементов там было мегабайт на 100 от силы.
Re[24]: о алгоритмах диагонализации вещественных симметричны
Здравствуйте, Sergey Chadov, Вы писали:
SC>Здравствуйте, Drednout, Вы писали:
D>> Смотря какой BLAS Level 2: дело в том, что в трехдиагонализации число операций пропорционально n в кубе. Вот Вы возьмите и попробуйте трехдиагонализацию распараллелить и получите фиг в кармане. И 90 раз — это с одинарной точностью, в серьезных научных задачах она на фиг не нужна. А для двойной точности скорость упадет раз в десять. И отсутствие кэша тоже затормозит задачу раз в 10 (современные алгоритмы диагонализации используют блочные методы обработки информации, а для них отсутствие кэша — это всё равно, что для рыбы отсутствие воды). И куда девался их выигрыш? И потом, сколько там памяти? Попробуйте, например, диагонализировать матрицу 40000*40000. Пока CUDA — это для лохов.
SC>Ну допустим кэш там есть, самый разнообразный и памяти на тесле до 4 гигов и двойную точность на тесле(ферми) обещают с нормальной скоростью(правда, сам не щупал). И разреженную СЛАУ размером 350к я решал, правда ненулевых элементов там было мегабайт на 100 от силы.
Утюг Tesla S1070 имеет еще более впечатляющие характеристики. А настоящий кэш очень дорог. Думаю, что с ним этот утюг стоил бы не около 10000$, а раз в десять дорже. Что касается СЛАУ с разреженными матрицми, то, например, задачи, заданные на графе типа дерева, можно и на ручном калькуляторе решать (число операций пропорционально размерности задачи). Вы меня не совсем правильно поняли: в этой теме речь идет не об утюгах,- я на это и намекал.
Re[21]: о алгоритмах диагонализации вещественных симметричны
Здравствуйте, 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> Вы там найдите интернет-страницу этого товарища: там подробно расписаны все шаги диагонализации на самом современном уровне.
Может конечно у нас разные понятия о "плохо" или мы просто польуемся разными наборами функций, но лично я реализовывал sparse matrix-vector multiply на CUDA с неплохим ускорением. 