Участник:VolkovNikita94/Алгоритм Ланцоша для точной арифметики (без переортогонализации): различия между версиями

Версия 14:52, 15 октября 2016

Содержание

1 Свойства и структура алгоритма
2 Программная реализация алгоритма

1 Свойства и структура алгоритма

1.1 Общее описание алгоритма

1.2 Математическое описание алгоритма

1.3 Вычислительное ядро алгоритма

1.4 Макроструктура алгоритма

1.5 Схема реализации последовательного алгоритма

1.6 Последовательная сложность алгоритма

1.7 Информационный граф

1.8 Ресурс параллелизма алгоритма

1.9 Входные и выходные данные алгоритма

1.10 Свойства алгоритма

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

@@ Строка 5: / Строка 5: @@
 ===Макроструктура алгоритма===
 ===Схема реализации последовательного алгоритма===
+===Последовательная сложность алгоритма===
 ===Информационный граф===
 ===Ресурс параллелизма алгоритма===
 ===Входные и выходные данные алгоритма===
 ===Свойства алгоритма===
 ==Программная реализация алгоритма==
 ===Особенности реализации последователього алгоритма===