Участник:VolkovNikita94/Алгоритм Ланцоша для точной арифметики (без переортогонализации): различия между версиями
Строка 17: | Строка 17: | ||
===Выводы для классов архитектур=== | ===Выводы для классов архитектур=== | ||
===Существующие реализации алгоритма=== | ===Существующие реализации алгоритма=== | ||
− | Существует несколько как последовательных, так и параллельных реализаций алгоритма Ланцоша, включенных в программные библиотеки для поиска собственных значений матриц. Свойства этих реализаций можно увидеть в таблицах ниже. Первая таблица — относительно недавние реализации, вторая - «музейные экспонаты». Следует уделить особенное внимание столбцам «тип метода» и «параллелизация». В первом из них значение N соответствует описанному варианту без реортогонализации, F – полной реортогонализации, P – частичной реортогонализации, S – выборочной реортогонализации. Во втором значние | + | Существует несколько как последовательных, так и параллельных реализаций алгоритма Ланцоша, включенных в программные библиотеки для поиска собственных значений матриц. Свойства этих реализаций можно увидеть в таблицах ниже. Первая таблица — относительно недавние реализации, вторая - «музейные экспонаты». Следует уделить особенное внимание столбцам «тип метода» и «параллелизация». В первом из них значение только N соответствует описанному варианту без реортогонализации, F – полной реортогонализации, P – частичной реортогонализации, S – выборочной реортогонализации. Во втором значние «none» соответствует отсутствию параллельной реализации, M – параллельной реализации посредством MPI, O – параллельной реализации посредством OpenMP. Их приведение целесообразно, так как на практике алгоритм Ланцоша без переортогонализации неустойчив. Также указываются библиотеки, в которых реализованы более глубокие модификации метода Ланцоша, с указанием изменений в графе «тип метода». |
− | <b>Таблица 1 - «современные» реализации.</b> | + | {| class="wikitable" |
− | + | |+<b>Таблица 1 - «современные» реализации.</b> | |
− | <b>Таблица 2 - «исторические» реализации.</b> | + | !Название библиотеки |
− | + | !Язык программирования | |
+ | !Дата появления, версия библиотки | ||
+ | !Тип метода | ||
+ | !Параллелизация | ||
+ | |- | ||
+ | |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 | ||
+ | |} | ||
+ | |||
+ | {| class="wikitable" | ||
+ | |+<b>Таблица 2 - «исторические» реализации.</b> | ||
+ | !Название библиотеки | ||
+ | !Язык программирования | ||
+ | !Дата появления, версия библиотки | ||
+ | !Тип метода | ||
+ | !Параллелизация | ||
+ | |- | ||
+ | |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 | ||
+ | |} |
Версия 14:51, 15 октября 2016
Содержание
- 1 Свойства и структура алгоритма
- 2 Программная реализация алгоритма
- 2.1 Особенности реализации последователього алгоритма
- 2.2 Локальность данных и вычислений
- 2.3 Возможные способы и особенности параллельной реализации алгоритма
- 2.4 Масштабируемость алгоритма и его реализации
- 2.5 Динамические характеристики и эффективность реализации алгоритма
- 2.6 Выводы для классов архитектур
- 2.7 Существующие реализации алгоритма
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. Их приведение целесообразно, так как на практике алгоритм Ланцоша без переортогонализации неустойчив. Также указываются библиотеки, в которых реализованы более глубокие модификации метода Ланцоша, с указанием изменений в графе «тип метода».
Название библиотеки | Язык программирования | Дата появления, версия библиотки | Тип метода | Параллелизация |
---|---|---|---|---|
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 |
Название библиотеки | Язык программирования | Дата появления, версия библиотки | Тип метода | Параллелизация |
---|---|---|---|---|
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 |