НОВЫЕ АЛГОРИТМЫ БЫСТРОЙ ДИАГОНАЛИЗАЦИИ ВЕЩЕСТВЕННЫХ СИММЕТРИЧНЫХ МАТРИЦ.
Автор: Сиголаев Юрий Федорович (Санкт-Петербург). E-mail: y_sigolaev@hotmail.com
Последняя редакция: 24 мая, 2007
Мною разработан новый комплекс алгоритмов (SDIAG) диагонализации плотных вещественных симметричных матриц, имеющий ряд важных преимуществ по сравнению с другими известными пакетами, в которых реализованы алгоритмы диагонализации:
заметное увеличение скорости расчетов;
значительная экономия оперативной памяти.
Этих результатов удалось достичь благодаря решению фундаментальной проблемы численного анализа трехдиагональных матриц, разработке нового алгоритма векторного умножения и усовершенствованной реализации блочных методов для упакованных матриц. Часть алгоритмов использует поддержку IEEE-арифметики и использует SSE2 и SSE3 для эффективности. Для сравнительного анализа использовался пакет Intel MKL ввиду общего источника кода - пакета LAPACK.
Технология EM64T снимает ограничения на размер используемой оперативной памяти. Например, на компьютере с 4 GB RAM появляется возможность диагонализировать матрицы вплоть до размера 31000×31000. При этом оперативная память используется только для хранения информации размером немногим более половины квадратной матрицы. Программы диагонализации, в которых используется один из наиболее известных и, пожалуй, самый лучший на сегодняшний день The divide and conquer алгоритм, позволяют диагонализировать матрицы размером не более 13000×13000 на компьютере с 4 GB RAM. Использование дополнительных регистров позволяет провести оптимизацию программ с целью повышения их скорости. При этом увеличение скорости программ диагонализации Intel MKL более значительно, чем у SDIAG, т.к. проблемы, связанные с отсутствием дополнительных регистров в IA32, были мною частично решены (дополнительные регистры позволяют добиться хороших результатов, используя примитивные схемы программирования). Тем не менее, разрыв в скоростях по-прежнему достаточно велик. Например, в приведенном ниже примере скорость SDIAG на одном ядре не уступает скорости DSYEVD Intel MKL на двух ядрах.
Описание новых алгоритмов и список литературы приведены на странице, посвященной процессору P4: http://www.thesa-store.com/products.
Все замечания и предложения просьба присылать по адресу: y_sigolaev@hotmail.com
Tel/Fax: 7(812)2691898
Результаты сравнения.
Я сравнивал полученные мною результаты с результатами из известного пакета Intel MKL (Package ID: w_mkl_p_9.0.017). Конфигурация "железа": процессор Core 2 Duo 2.66 GHz, (Processor E6700, Speed: 3.00 GHz (BIOS setup: Overclock Options [FSB1200/DDR2-800])), Data cache size : L1 32 KB, L2 4096 KB, L3 0 KB, 1066 MHz FSB, Motherboard: P5WDG2 WS Professional, 1066 MHz FSB, DDR2 800 MHz (4 GB), ОС Windows XP Professional x64 Edition SP1.
Рассмотрим упакованную симметричную теплицеву матрицу:
Aij = arcsin(1 / (i - j + 1))/(i - j + 1)3 (i , j = 1, 2, ..., n; i >= j)
Применение алгоритмов, описанных в пунктах 1.1, 2 и 3.1 на странице, посвященной процессору P4, к решению полной алгебраической проблемы для этой матрицы, приводит к результатам, которые говорят о неэффективности DSYEVD Intel MKL (по существу, единственной на данный момент процедуре, сочетающей в себе скорость и точность расчета, но требующей непомерных затрат оперативной памяти). В таблице 1 приведены результаты сравнения при использовании одного ядра (OMP_NUM_THREADS=1), а в таблице 2 - двух ядер (OMP_NUM_THREADS=2).
ТАБЛИЦА 1
| n | t (sec) | Δt (%) | |
| SDIAG |
DSYEVD Intel MKL 9.0 |
||
|
1000 2000 3000 4000 5000 6000 7000 8000 9000 10000 11000 12000 13000 |
0.72 4.7 14.5 32.7 61.5 104 162 239 337 457 606 782 992 |
0.92 6.4 20.6 47.0 89.5 153 241 356 503 685 906 1170 1522 |
28 36 42 44 46 47 49 49 49 50 50 50 53 |
ТАБЛИЦА 2
| n | t (sec) | Δt (%) | |
| SDIAG |
DSYEVD Intel MKL 9.0 |
||
|
1000 2000 3000 4000 5000 6000 7000 8000 9000 10000 11000 12000 13000 |
0.45 3.0 9.6 22.3 42.6 72.9 115 169 240 326 434 560 712 |
0.66 4.8 15.1 33.8 64.2 109 171 251 353 483 636 825 1046 |
47 60 57 52 51 50 49 49 47 48 47 47 47 |