Свойства и структура алгоритма
Общее описание алгоритма
Математическое описание алгоритма
Вычислительное ядро алгоритма
Макроструктура алгоритма
Схема реализации последовательного алгоритма
Информационный граф
Ресурс параллелизма алгоритма
Входные и выходные данные алгоритма
Свойства алгоритма
Программная реализация алгоритма
Особенности реализации последователього алгоритма
Локальность данных и вычислений
Возможные способы и особенности параллельной реализации алгоритма
Масштабируемость алгоритма и его реализации
Динамические характеристики и эффективность реализации алгоритма
Выводы для классов архитектур
Существующие реализации алгоритма
Существует несколько как последовательных, так и параллельных реализаций алгоритма Ланцоша, включенных в программные библиотеки для поиска собственных значений матриц. Свойства этих реализаций можно увидеть в таблицах ниже. Первая таблица — относительно недавние реализации, вторая - «музейные экспонаты». Следует уделить особенное внимание столбцам «тип метода» и «параллелизация». В первом из них значение только 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
|