1 Свойства и структура алгоритма
1.1 Общее описание алгоритма
1.2 Математическое описание алгоритма
1.3 Вычислительное ядро алгоритма
1.4 Макроструктура алгоритма
1.5 Схема реализации последовательного алгоритма
1.6 Информационный граф
1.7 Ресурс параллелизма алгоритма
1.8 Входные и выходные данные алгоритма
1.9 Свойства алгоритма
2 Программная реализация алгоритма
2.1 Особенности реализации последователього алгоритма
2.2 Локальность данных и вычислений
2.3 Возможные способы и особенности параллельной реализации алгоритма
2.4 Масштабируемость алгоритма и его реализации
2.5 Динамические характеристики и эффективность реализации алгоритма
2.6 Выводы для классов архитектур
2.7 Существующие реализации алгоритма
Существует несколько как последовательных, так и параллельных реализаций алгоритма Ланцоша, включенных в программные библиотеки для поиска собственных значений матриц. Свойства этих реализаций можно увидеть в таблицах ниже. Первая таблица — относительно недавние реализации, вторая - «музейные экспонаты». Следует уделить особенное внимание столбцам «тип метода» и «параллелизация». В первом из них значение только N соответствует описанному варианту без реортогонализации, F – полной реортогонализации, P – частичной реортогонализации, S – выборочной реортогонализации. Во втором значние «none» соответствует отсутствию параллельной реализации, M – параллельной реализации посредством MPI, O – параллельной реализации посредством OpenMP. Их приведение целесообразно, так как на практике алгоритм Ланцоша без переортогонализации неустойчив. Также указываются библиотеки, в которых реализованы более глубокие модификации метода Ланцоша, с указанием изменений в графе «тип метода».
Таблица 1 - «современные» реализации.
| Название библиотеки
|
Язык программирования
|
Дата появления, версия библиотки
|
Тип метода
|
Параллелизация
|
| BLKLAN
|
C/Matlab
|
2003
|
P
|
none
|
| BLZPACK
|
F77
|
2000, 04/00
|
P + S
|
M
|
| IETL
|
C++
|
2006, 2.2
|
N
|
none
|
| SLEPc
|
C/F77
|
2009, 3.0.0
|
All
|
M
|
| TRLAN
|
F90
|
2006
|
Dynamic thick-restart
|
M
|
| PROPACK
|
F77/Matlab
|
2005, 2.1 / 1.1
|
P, finds SVD
|
O
|
| IRBLEIGS
|
Matlab
|
2000, 1.0
|
Indefinitie symmetric
|
none
|
Таблица 2 - «исторические» реализации.
| Название библиотеки
|
Язык программирования
|
Дата появления, версия библиотки
|
Тип метода
|
Параллелизация
|
| ARPACK
|
F77
|
1995, 2.1
|
Arnoldi iterations, impliicit restart
|
M
|
| ARPACK++
|
C++
|
1998, 1.1
|
Arnoldi iterations, impliicit restart
|
none
|
| LANCZOS
|
F77
|
1992
|
N
|
none
|
| LANZ
|
F77
|
1991, 1.0
|
P
|
none
|
| LASO
|
F77
|
1983, 2
|
S
|
none
|
| NAPACK
|
F77
|
1987
|
N
|
none
|
| QMRPACK
|
F77
|
1996
|
Designed for nonsymmetric matrices ( lookahead )
|
none
|
| SVDPACK
|
C/F77
|
1992
|
P, finds SVD
|
none
|
| Underwood
|
F77
|
1975
|
F, block version
|
none
|
