Алговики - Вклад [ru]

Обсуждение участника:Error0x0

2017-02-03T19:47:11Z

Error0x0:

== Статья [[Участник:Error0x0/Алгоритм Ланцоша для арифметики с плавающей точкой с полной переортогонализацией]] ==

* В разделе 1.3 не приведено описание вычислительного ядра
* Не указано ФИО автора
* Не приведена краткая сводка свойств алгоритма в начале статьи

Добавил.

* В разделе 1.4 требуется привести описание алгоритма на верхнем уровне (на основе макроопераций). [[Участник:ASA|Александр Сергеевич Антонов]] ([[Обсуждение участника:ASA|обсуждение]]) 17:35, 1 ноября 2016 (MSK)
* В разделе 1.5 кроме кода нужны также текстовые пояснения. [[Участник:ASA|Александр Сергеевич Антонов]] ([[Обсуждение участника:ASA|обсуждение]]) 17:35, 1 ноября 2016 (MSK)
* В разделе 1.10 должна быть оценка вычислительной мощности алгоритма. [[Участник:ASA|Александр Сергеевич Антонов]] ([[Обсуждение участника:ASA|обсуждение]]) 17:35, 1 ноября 2016 (MSK)
* Не заполнен раздел 2.4 описания. [[Участник:ASA|Александр Сергеевич Антонов]] ([[Обсуждение участника:ASA|обсуждение]]) 15:44, 16 ноября 2016 (MSK)

Пункты 1.4, 1.5, 1.10 исправлены, пункт 2.4 добавлен
* В разделе 1.4 должно быть не перечисление макроопераций, а нужно показать структуру алгоритма на макроуровне. [[Участник:ASA|Александр Сергеевич Антонов]] ([[Обсуждение участника:ASA|обсуждение]]) 17:10, 3 февраля 2017 (MSK)
* Граф, приведённый в разделе 1.7, не является информационным графом (направленный ациклический граф, вершины - операции, дуги - информационные зависимости). [[Участник:ASA|Александр Сергеевич Антонов]] ([[Обсуждение участника:ASA|обсуждение]]) 17:10, 3 февраля 2017 (MSK)
* В разделе 2.4 не приведены все параметры запуска теста - например, с какими опциями проводилась компиляция. [[Участник:ASA|Александр Сергеевич Антонов]] ([[Обсуждение участника:ASA|обсуждение]]) 17:10, 3 февраля 2017 (MSK)
* Из графиков в разделе 2.4 следует сделать выводы о масштабируемости реализации. [[Участник:ASA|Александр Сергеевич Антонов]] ([[Обсуждение участника:ASA|обсуждение]]) 17:10, 3 февраля 2017 (MSK)

Исправлено.

Участник:Error0x0/Алгоритм Ланцоша для арифметики с плавающей точкой с полной переортогонализацией

2017-02-03T19:46:45Z

Error0x0:

{{assignment}}
{{algorithm
| name = Алгоритм Ланцоша для арифметики с плавающей точкой с полной переортогонализацией
| serial_complexity = <math>O(k^2 n)</math>
| pf_height = <math>O(k \log k \log n)</math>
| pf_width = <math>O(kn)</math>
| input_data = <math>n^2</math>
| output_data = <math>n</math>
}}
Автор описания: [[Участник:Error0x0|В. А. Янушковский]]

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

== Общее описание алгоритма ==
Алгоритм Ланцоша представляет собой итерационный алгоритм для вычисления собственных значений симметрической матрицы.
Идея алгоритма заключается в построении матрицы <math>Q_k = [q_1, ..., q_k]</math> из ортонормированных векторов Ланцоша и использовании собственных значений трёхдиагональной матрицы <math>T_k = Q_k^T A Q_k</math> (чисел Ритца) как приближения к искомым собственным числам матрицы<ref name="Деммель">Деммель Дж. Вычислительная линейная алгебра</ref>.

== Математическое описание алгоритма ==
Пусть дана матрица <math>A</math>.
Пусть <math>q_1 = b/||b||_2, \beta_0=0, q_0=0</math>
Алгоритм производит <math>k</math> итераций на каждой из которых:
# вычисляется <math>z = Aq_j</math>,
# производится переортогонализация <math>z = z - \sum^{j-1}_{i=1} {(z^T q_i)q_i}</math>,
# <math>\beta_j = ||z||_2</math>, если <math>\beta_j = 0</math>, алгоритм останавливается,
# <math>q_{j+1} = z/\beta_j</math>,
# вычисляются собственные значения и векторы матрицы <math>T_j = Q_j^T A Q_j</math>.

== Вычислительное ядро алгоритма ==
Основной вклад в сложность алгоритма даёт полная переортогонализация внутри каждой итерации:

<math>z = z - \sum^{j-1}_{i=1} {(z^T q_i)q_i}</math>

== Макроструктура алгоритма ==
Алгоритм имеет следующую макроструктуру:
* Начальная инициализация (деление вектора на норму <math>q_1 = b/||b||_2</math>)
* Далее <math>k</math> итераций, каждая из которых может быть разложена:
** Умножение матрицы на вектор (<math>z = Aq_j</math>)
** Переортогонализация <math>z = z - \sum^{j-1}_{i=1} {(z^T q_i)q_i}</math>
** Нахождение следующего вектора <math>q_{j+1} = z/\beta_j</math>, где <math>\beta_j = ||z||_2</math>
** Нахождение следующего собственного значения и вектора матрицы <math>T_j = Q_j^T A Q_j</math> (числа Ритца, используется метод "разделяй и властвуй")

== Схема реализации последовательного алгоритма ==
<syntaxhighlight lang="python">
beta[0] = 0 # инициализация
q[0] = 0
q[1] = b / norm(b) # вычисление первого столбца
for j in [1 .. k]: # k итераций
z = mul(A, q[j]) # вектор Ланцоша как произведение матрицы A на столбец q[j]
alpha[j] = scalar_mul(q[j], z) # вычисление alpha[j]
for i in [1 .. j - 1]: # полная переортогонализация
z -= scalar_mul(z, q[i]) * q[i]
beta[j] = norm(z) # вычисление нормы z
if beta[j] == 0: # останов, если норма z равна нулю
break
result.append(next_ritz_number(alpha, beta, j)) # вычисление следующего собственного значения и вектора матрицы Tj
return result
</syntaxhighlight>

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

Основной вклад в сложность даёт полная переортогонализация: на каждой из <math>k</math> итераций для всех <math>i \in [0...j-1]</math> выполняется <math>2n</math> умножений и <math>2n</math> сложений, итого <math>\frac{k(k-1)}{2} 4n \approx 2k^2 n</math>.
Таким образом, для метода с полной переортогонализацией сложность составляет <math>O(k^2 n)</math>, сложность по памяти -- <math>O(kn)</math>.

== Информационный граф ==
На рисунке приведён информационный граф одной итерации алгоритма
[[File:Lanczos graph.png|thumb|center|800px|Рисунок 1. Информационный граф итерации алгоритма]]

== Ресурс параллелизма алгоритма ==
Для процесса переортогонализации возможна параллельная оптимизация в двух местах:
* Итерации внутреннего цикла могут вычисляться параллельно, однако, требуется суммирование вычитаемых векторов, соответственно, сложность переортогонализации можно снизить с <math>O(kn)</math> до <math>O(n \log k)</math>
* В каждой итерации внутреннего цикла возможно распараллеливание вычисления выражения справа (скалярное произведение и умножение вектора на число), что теоретически позволяет снизить сложность итерации с <math>O(n)</math> до <math>O(log(n))</math>

== Входные и выходные данные алгоритма ==
'''Входные данны'''е: квадратная симметрическая матрица <math>A</math> порядка <math>n</math>

'''Объём входных данных''': <math>n^2</math>

'''Выходные данные''': собственные числа матрицы

'''Объём выходных данных''': <math>n</math>

== Свойства алгоритма ==
Полная переортогонализация соответствует повторной процедуре ортогонализациии Грама-Шмидта для обеспечения ортогональности вектора <math>z</math> векторам <math>q_1, ..., q_k</math>. В случае идеально точной арифметики данная переортогонализация не требовалась бы, однако в реальных вычислениях ошибки округления приводят к потере ортогональности, в связи с чем требуется переортогонализация.
Однако, единственной проблемой, возникающей при отсутствии переортогонализации, является появление повторных копий чисел Ритца (собственных значений), что в случае, если не требуется установление кратностей собственных значений, допустимо.

Вычислительная мощность алгоритма примерно равна <math>2k^2 / n</math>.

= Программная реализация алгоритма =

== Особенности реализации последовательного алгоритма ==

== [[Локальность данных и вычислений]] ==

== Возможные способы и особенности параллельной реализации алгоритма ==

== Масштабируемость алгоритма и его реализации ==

Исследование масштабируемости алгоритма проводилось на суперкомпьютере IBM Blue Gene/P ВМК МГУ.

Алгоритм тестировался на следующих параметрах:
* размер входной матрицы: 2048-8192 с шагом 512
* число узлов: 1-256

Зависимость времени выполнения от параметров изображена на графике:

[[Файл:Lanczos full chart.png|center|border |800px]]
Из рисунка видно, что алгоритм хорошо масштабируется, время выполнения на одном ядре растёт существенно быстрее чем на множестве ядер. При этом, для маленькой матрице на большом числе ядер прирост эффективности практически отсутствует.

[http://pastebin.com/u7KThy6D Используемая реализация алгоритма на языке C++]

Пример компиляции и запуска:
$ mpixlcxx_r -o lanczos lanczos.cpp
$ mpisubmit.bg -n 256 -w 00:5:00 lanczos

== Динамические характеристики и эффективность реализации алгоритма ==

== Выводы для классов архитектур ==

== Существующие реализации алгоритма ==
Библиотека [http://www.nag.co.uk/numeric/fl/nagdoc_fl23/html/INDEXES/KWIC/lanczos.html NAG Library] содержит ряд процедур для решения СЛАУ и поиска собственных значений на основе алгоритма Ланцоша.

[http://www.mathworks.com/help/techdoc/ref/eigs.html MATLAB] и [https://www.gnu.org/software/octave/doc/interpreter/Sparse-Linear-Algebra.html#doc_002deigs GNU Octave] позволяют с помощью функции ''eigs()'' находить собственные значения на основе данного алгоритма.

Matlab-реализация доступна как часть [http://www.cs.cmu.edu/~bickson/gabp/#download Gaussian Belief Propagation Matlab Package]. [http://www.graphlab.ml.cmu.edu/pmf.html GraphLab] содержит несколько параллельных реализаций алгоритма на C++.

= Литература =

Участник:Error0x0/Алгоритм Ланцоша для арифметики с плавающей точкой с полной переортогонализацией

2017-02-03T19:46:15Z

Error0x0: /* Масштабируемость алгоритма и его реализации */

{{algorithm
| name = Алгоритм Ланцоша для арифметики с плавающей точкой с полной переортогонализацией
| serial_complexity = <math>O(k^2 n)</math>
| pf_height = <math>O(k \log k \log n)</math>
| pf_width = <math>O(kn)</math>
| input_data = <math>n^2</math>
| output_data = <math>n</math>
}}
Автор описания: [[Участник:Error0x0|В. А. Янушковский]]

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

== Общее описание алгоритма ==
Алгоритм Ланцоша представляет собой итерационный алгоритм для вычисления собственных значений симметрической матрицы.
Идея алгоритма заключается в построении матрицы <math>Q_k = [q_1, ..., q_k]</math> из ортонормированных векторов Ланцоша и использовании собственных значений трёхдиагональной матрицы <math>T_k = Q_k^T A Q_k</math> (чисел Ритца) как приближения к искомым собственным числам матрицы<ref name="Деммель">Деммель Дж. Вычислительная линейная алгебра</ref>.

== Математическое описание алгоритма ==
Пусть дана матрица <math>A</math>.
Пусть <math>q_1 = b/||b||_2, \beta_0=0, q_0=0</math>
Алгоритм производит <math>k</math> итераций на каждой из которых:
# вычисляется <math>z = Aq_j</math>,
# производится переортогонализация <math>z = z - \sum^{j-1}_{i=1} {(z^T q_i)q_i}</math>,
# <math>\beta_j = ||z||_2</math>, если <math>\beta_j = 0</math>, алгоритм останавливается,
# <math>q_{j+1} = z/\beta_j</math>,
# вычисляются собственные значения и векторы матрицы <math>T_j = Q_j^T A Q_j</math>.

== Вычислительное ядро алгоритма ==
Основной вклад в сложность алгоритма даёт полная переортогонализация внутри каждой итерации:

<math>z = z - \sum^{j-1}_{i=1} {(z^T q_i)q_i}</math>

== Макроструктура алгоритма ==
Алгоритм имеет следующую макроструктуру:
* Начальная инициализация (деление вектора на норму <math>q_1 = b/||b||_2</math>)
* Далее <math>k</math> итераций, каждая из которых может быть разложена:
** Умножение матрицы на вектор (<math>z = Aq_j</math>)
** Переортогонализация <math>z = z - \sum^{j-1}_{i=1} {(z^T q_i)q_i}</math>
** Нахождение следующего вектора <math>q_{j+1} = z/\beta_j</math>, где <math>\beta_j = ||z||_2</math>
** Нахождение следующего собственного значения и вектора матрицы <math>T_j = Q_j^T A Q_j</math> (числа Ритца, используется метод "разделяй и властвуй")

== Схема реализации последовательного алгоритма ==
<syntaxhighlight lang="python">
beta[0] = 0 # инициализация
q[0] = 0
q[1] = b / norm(b) # вычисление первого столбца
for j in [1 .. k]: # k итераций
z = mul(A, q[j]) # вектор Ланцоша как произведение матрицы A на столбец q[j]
alpha[j] = scalar_mul(q[j], z) # вычисление alpha[j]
for i in [1 .. j - 1]: # полная переортогонализация
z -= scalar_mul(z, q[i]) * q[i]
beta[j] = norm(z) # вычисление нормы z
if beta[j] == 0: # останов, если норма z равна нулю
break
result.append(next_ritz_number(alpha, beta, j)) # вычисление следующего собственного значения и вектора матрицы Tj
return result
</syntaxhighlight>

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

Основной вклад в сложность даёт полная переортогонализация: на каждой из <math>k</math> итераций для всех <math>i \in [0...j-1]</math> выполняется <math>2n</math> умножений и <math>2n</math> сложений, итого <math>\frac{k(k-1)}{2} 4n \approx 2k^2 n</math>.
Таким образом, для метода с полной переортогонализацией сложность составляет <math>O(k^2 n)</math>, сложность по памяти -- <math>O(kn)</math>.

== Информационный граф ==
На рисунке приведён информационный граф одной итерации алгоритма
[[File:Lanczos graph.png|thumb|center|800px|Рисунок 1. Информационный граф итерации алгоритма]]

== Ресурс параллелизма алгоритма ==
Для процесса переортогонализации возможна параллельная оптимизация в двух местах:
* Итерации внутреннего цикла могут вычисляться параллельно, однако, требуется суммирование вычитаемых векторов, соответственно, сложность переортогонализации можно снизить с <math>O(kn)</math> до <math>O(n \log k)</math>
* В каждой итерации внутреннего цикла возможно распараллеливание вычисления выражения справа (скалярное произведение и умножение вектора на число), что теоретически позволяет снизить сложность итерации с <math>O(n)</math> до <math>O(log(n))</math>

== Входные и выходные данные алгоритма ==
'''Входные данны'''е: квадратная симметрическая матрица <math>A</math> порядка <math>n</math>

'''Объём входных данных''': <math>n^2</math>

'''Выходные данные''': собственные числа матрицы

'''Объём выходных данных''': <math>n</math>

== Свойства алгоритма ==
Полная переортогонализация соответствует повторной процедуре ортогонализациии Грама-Шмидта для обеспечения ортогональности вектора <math>z</math> векторам <math>q_1, ..., q_k</math>. В случае идеально точной арифметики данная переортогонализация не требовалась бы, однако в реальных вычислениях ошибки округления приводят к потере ортогональности, в связи с чем требуется переортогонализация.
Однако, единственной проблемой, возникающей при отсутствии переортогонализации, является появление повторных копий чисел Ритца (собственных значений), что в случае, если не требуется установление кратностей собственных значений, допустимо.

Вычислительная мощность алгоритма примерно равна <math>2k^2 / n</math>.

= Программная реализация алгоритма =

== Особенности реализации последовательного алгоритма ==

== [[Локальность данных и вычислений]] ==

== Возможные способы и особенности параллельной реализации алгоритма ==

== Масштабируемость алгоритма и его реализации ==

Исследование масштабируемости алгоритма проводилось на суперкомпьютере IBM Blue Gene/P ВМК МГУ.

Алгоритм тестировался на следующих параметрах:
* размер входной матрицы: 2048-8192 с шагом 512
* число узлов: 1-256

Зависимость времени выполнения от параметров изображена на графике:

[[Файл:Lanczos full chart.png|center|border |800px]]
Из рисунка видно, что алгоритм хорошо масштабируется, время выполнения на одном ядре растёт существенно быстрее чем на множестве ядер. При этом, для маленькой матрице на большом числе ядер прирост эффективности практически отсутствует.

[http://pastebin.com/u7KThy6D Используемая реализация алгоритма на языке C++]

Пример компиляции и запуска:
$ mpixlcxx_r -o lanczos lanczos.cpp
$ mpisubmit.bg -n 256 -w 00:5:00 lanczos

== Динамические характеристики и эффективность реализации алгоритма ==

== Выводы для классов архитектур ==

== Существующие реализации алгоритма ==
Библиотека [http://www.nag.co.uk/numeric/fl/nagdoc_fl23/html/INDEXES/KWIC/lanczos.html NAG Library] содержит ряд процедур для решения СЛАУ и поиска собственных значений на основе алгоритма Ланцоша.

[http://www.mathworks.com/help/techdoc/ref/eigs.html MATLAB] и [https://www.gnu.org/software/octave/doc/interpreter/Sparse-Linear-Algebra.html#doc_002deigs GNU Octave] позволяют с помощью функции ''eigs()'' находить собственные значения на основе данного алгоритма.

Matlab-реализация доступна как часть [http://www.cs.cmu.edu/~bickson/gabp/#download Gaussian Belief Propagation Matlab Package]. [http://www.graphlab.ml.cmu.edu/pmf.html GraphLab] содержит несколько параллельных реализаций алгоритма на C++.

= Литература =

Участник:Error0x0/Алгоритм Ланцоша для арифметики с плавающей точкой с полной переортогонализацией

2017-02-03T19:41:25Z

Error0x0: /* Масштабируемость алгоритма и его реализации */

{{algorithm
| name = Алгоритм Ланцоша для арифметики с плавающей точкой с полной переортогонализацией
| serial_complexity = <math>O(k^2 n)</math>
| pf_height = <math>O(k \log k \log n)</math>
| pf_width = <math>O(kn)</math>
| input_data = <math>n^2</math>
| output_data = <math>n</math>
}}
Автор описания: [[Участник:Error0x0|В. А. Янушковский]]

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

== Общее описание алгоритма ==
Алгоритм Ланцоша представляет собой итерационный алгоритм для вычисления собственных значений симметрической матрицы.
Идея алгоритма заключается в построении матрицы <math>Q_k = [q_1, ..., q_k]</math> из ортонормированных векторов Ланцоша и использовании собственных значений трёхдиагональной матрицы <math>T_k = Q_k^T A Q_k</math> (чисел Ритца) как приближения к искомым собственным числам матрицы<ref name="Деммель">Деммель Дж. Вычислительная линейная алгебра</ref>.

== Математическое описание алгоритма ==
Пусть дана матрица <math>A</math>.
Пусть <math>q_1 = b/||b||_2, \beta_0=0, q_0=0</math>
Алгоритм производит <math>k</math> итераций на каждой из которых:
# вычисляется <math>z = Aq_j</math>,
# производится переортогонализация <math>z = z - \sum^{j-1}_{i=1} {(z^T q_i)q_i}</math>,
# <math>\beta_j = ||z||_2</math>, если <math>\beta_j = 0</math>, алгоритм останавливается,
# <math>q_{j+1} = z/\beta_j</math>,
# вычисляются собственные значения и векторы матрицы <math>T_j = Q_j^T A Q_j</math>.

== Вычислительное ядро алгоритма ==
Основной вклад в сложность алгоритма даёт полная переортогонализация внутри каждой итерации:

<math>z = z - \sum^{j-1}_{i=1} {(z^T q_i)q_i}</math>

== Макроструктура алгоритма ==
Алгоритм имеет следующую макроструктуру:
* Начальная инициализация (деление вектора на норму <math>q_1 = b/||b||_2</math>)
* Далее <math>k</math> итераций, каждая из которых может быть разложена:
** Умножение матрицы на вектор (<math>z = Aq_j</math>)
** Переортогонализация <math>z = z - \sum^{j-1}_{i=1} {(z^T q_i)q_i}</math>
** Нахождение следующего вектора <math>q_{j+1} = z/\beta_j</math>, где <math>\beta_j = ||z||_2</math>
** Нахождение следующего собственного значения и вектора матрицы <math>T_j = Q_j^T A Q_j</math> (числа Ритца, используется метод "разделяй и властвуй")

== Схема реализации последовательного алгоритма ==
<syntaxhighlight lang="python">
beta[0] = 0 # инициализация
q[0] = 0
q[1] = b / norm(b) # вычисление первого столбца
for j in [1 .. k]: # k итераций
z = mul(A, q[j]) # вектор Ланцоша как произведение матрицы A на столбец q[j]
alpha[j] = scalar_mul(q[j], z) # вычисление alpha[j]
for i in [1 .. j - 1]: # полная переортогонализация
z -= scalar_mul(z, q[i]) * q[i]
beta[j] = norm(z) # вычисление нормы z
if beta[j] == 0: # останов, если норма z равна нулю
break
result.append(next_ritz_number(alpha, beta, j)) # вычисление следующего собственного значения и вектора матрицы Tj
return result
</syntaxhighlight>

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

Основной вклад в сложность даёт полная переортогонализация: на каждой из <math>k</math> итераций для всех <math>i \in [0...j-1]</math> выполняется <math>2n</math> умножений и <math>2n</math> сложений, итого <math>\frac{k(k-1)}{2} 4n \approx 2k^2 n</math>.
Таким образом, для метода с полной переортогонализацией сложность составляет <math>O(k^2 n)</math>, сложность по памяти -- <math>O(kn)</math>.

== Информационный граф ==
На рисунке приведён информационный граф одной итерации алгоритма
[[File:Lanczos graph.png|thumb|center|800px|Рисунок 1. Информационный граф итерации алгоритма]]

== Ресурс параллелизма алгоритма ==
Для процесса переортогонализации возможна параллельная оптимизация в двух местах:
* Итерации внутреннего цикла могут вычисляться параллельно, однако, требуется суммирование вычитаемых векторов, соответственно, сложность переортогонализации можно снизить с <math>O(kn)</math> до <math>O(n \log k)</math>
* В каждой итерации внутреннего цикла возможно распараллеливание вычисления выражения справа (скалярное произведение и умножение вектора на число), что теоретически позволяет снизить сложность итерации с <math>O(n)</math> до <math>O(log(n))</math>

== Входные и выходные данные алгоритма ==
'''Входные данны'''е: квадратная симметрическая матрица <math>A</math> порядка <math>n</math>

'''Объём входных данных''': <math>n^2</math>

'''Выходные данные''': собственные числа матрицы

'''Объём выходных данных''': <math>n</math>

== Свойства алгоритма ==
Полная переортогонализация соответствует повторной процедуре ортогонализациии Грама-Шмидта для обеспечения ортогональности вектора <math>z</math> векторам <math>q_1, ..., q_k</math>. В случае идеально точной арифметики данная переортогонализация не требовалась бы, однако в реальных вычислениях ошибки округления приводят к потере ортогональности, в связи с чем требуется переортогонализация.
Однако, единственной проблемой, возникающей при отсутствии переортогонализации, является появление повторных копий чисел Ритца (собственных значений), что в случае, если не требуется установление кратностей собственных значений, допустимо.

Вычислительная мощность алгоритма примерно равна <math>2k^2 / n</math>.

= Программная реализация алгоритма =

== Особенности реализации последовательного алгоритма ==

== [[Локальность данных и вычислений]] ==

== Возможные способы и особенности параллельной реализации алгоритма ==

== Масштабируемость алгоритма и его реализации ==

Исследование масштабируемости алгоритма проводилось на суперкомпьютере IBM Blue Gene/P ВМК МГУ.

Алгоритм тестировался на следующих параметрах:
* размер входной матрицы: 2048-8192 с шагом 512
* число узлов: 1-256

Зависимость времени выполнения от параметров изображена на графике:

[[Файл:Lanczos full chart.png|center|border |800px]]
Из рисунка видно, что

[http://pastebin.com/u7KThy6D Используемая реализация алгоритма на языке C++]

Пример компиляции и запуска:
$ mpixlcxx_r -o lanczos lanczos.cpp
$ mpisubmit.bg -n 256 -w 00:5:00 lanczos

== Динамические характеристики и эффективность реализации алгоритма ==

== Выводы для классов архитектур ==

== Существующие реализации алгоритма ==
Библиотека [http://www.nag.co.uk/numeric/fl/nagdoc_fl23/html/INDEXES/KWIC/lanczos.html NAG Library] содержит ряд процедур для решения СЛАУ и поиска собственных значений на основе алгоритма Ланцоша.

[http://www.mathworks.com/help/techdoc/ref/eigs.html MATLAB] и [https://www.gnu.org/software/octave/doc/interpreter/Sparse-Linear-Algebra.html#doc_002deigs GNU Octave] позволяют с помощью функции ''eigs()'' находить собственные значения на основе данного алгоритма.

Matlab-реализация доступна как часть [http://www.cs.cmu.edu/~bickson/gabp/#download Gaussian Belief Propagation Matlab Package]. [http://www.graphlab.ml.cmu.edu/pmf.html GraphLab] содержит несколько параллельных реализаций алгоритма на C++.

= Литература =

Участник:Error0x0/Алгоритм Ланцоша для арифметики с плавающей точкой с полной переортогонализацией

2017-02-03T18:39:14Z

Error0x0: /* Информационный граф */

{{algorithm
| name = Алгоритм Ланцоша для арифметики с плавающей точкой с полной переортогонализацией
| serial_complexity = <math>O(k^2 n)</math>
| pf_height = <math>O(k \log k \log n)</math>
| pf_width = <math>O(kn)</math>
| input_data = <math>n^2</math>
| output_data = <math>n</math>
}}
Автор описания: [[Участник:Error0x0|В. А. Янушковский]]

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

== Общее описание алгоритма ==
Алгоритм Ланцоша представляет собой итерационный алгоритм для вычисления собственных значений симметрической матрицы.
Идея алгоритма заключается в построении матрицы <math>Q_k = [q_1, ..., q_k]</math> из ортонормированных векторов Ланцоша и использовании собственных значений трёхдиагональной матрицы <math>T_k = Q_k^T A Q_k</math> (чисел Ритца) как приближения к искомым собственным числам матрицы<ref name="Деммель">Деммель Дж. Вычислительная линейная алгебра</ref>.

== Математическое описание алгоритма ==
Пусть дана матрица <math>A</math>.
Пусть <math>q_1 = b/||b||_2, \beta_0=0, q_0=0</math>
Алгоритм производит <math>k</math> итераций на каждой из которых:
# вычисляется <math>z = Aq_j</math>,
# производится переортогонализация <math>z = z - \sum^{j-1}_{i=1} {(z^T q_i)q_i}</math>,
# <math>\beta_j = ||z||_2</math>, если <math>\beta_j = 0</math>, алгоритм останавливается,
# <math>q_{j+1} = z/\beta_j</math>,
# вычисляются собственные значения и векторы матрицы <math>T_j = Q_j^T A Q_j</math>.

== Вычислительное ядро алгоритма ==
Основной вклад в сложность алгоритма даёт полная переортогонализация внутри каждой итерации:

<math>z = z - \sum^{j-1}_{i=1} {(z^T q_i)q_i}</math>

== Макроструктура алгоритма ==
Алгоритм имеет следующую макроструктуру:
* Начальная инициализация (деление вектора на норму <math>q_1 = b/||b||_2</math>)
* Далее <math>k</math> итераций, каждая из которых может быть разложена:
** Умножение матрицы на вектор (<math>z = Aq_j</math>)
** Переортогонализация <math>z = z - \sum^{j-1}_{i=1} {(z^T q_i)q_i}</math>
** Нахождение следующего вектора <math>q_{j+1} = z/\beta_j</math>, где <math>\beta_j = ||z||_2</math>
** Нахождение следующего собственного значения и вектора матрицы <math>T_j = Q_j^T A Q_j</math> (числа Ритца, используется метод "разделяй и властвуй")

== Схема реализации последовательного алгоритма ==
<syntaxhighlight lang="python">
beta[0] = 0 # инициализация
q[0] = 0
q[1] = b / norm(b) # вычисление первого столбца
for j in [1 .. k]: # k итераций
z = mul(A, q[j]) # вектор Ланцоша как произведение матрицы A на столбец q[j]
alpha[j] = scalar_mul(q[j], z) # вычисление alpha[j]
for i in [1 .. j - 1]: # полная переортогонализация
z -= scalar_mul(z, q[i]) * q[i]
beta[j] = norm(z) # вычисление нормы z
if beta[j] == 0: # останов, если норма z равна нулю
break
result.append(next_ritz_number(alpha, beta, j)) # вычисление следующего собственного значения и вектора матрицы Tj
return result
</syntaxhighlight>

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

Основной вклад в сложность даёт полная переортогонализация: на каждой из <math>k</math> итераций для всех <math>i \in [0...j-1]</math> выполняется <math>2n</math> умножений и <math>2n</math> сложений, итого <math>\frac{k(k-1)}{2} 4n \approx 2k^2 n</math>.
Таким образом, для метода с полной переортогонализацией сложность составляет <math>O(k^2 n)</math>, сложность по памяти -- <math>O(kn)</math>.

== Информационный граф ==
На рисунке приведён информационный граф одной итерации алгоритма
[[File:Lanczos graph.png|thumb|center|800px|Рисунок 1. Информационный граф итерации алгоритма]]

== Ресурс параллелизма алгоритма ==
Для процесса переортогонализации возможна параллельная оптимизация в двух местах:
* Итерации внутреннего цикла могут вычисляться параллельно, однако, требуется суммирование вычитаемых векторов, соответственно, сложность переортогонализации можно снизить с <math>O(kn)</math> до <math>O(n \log k)</math>
* В каждой итерации внутреннего цикла возможно распараллеливание вычисления выражения справа (скалярное произведение и умножение вектора на число), что теоретически позволяет снизить сложность итерации с <math>O(n)</math> до <math>O(log(n))</math>

== Входные и выходные данные алгоритма ==
'''Входные данны'''е: квадратная симметрическая матрица <math>A</math> порядка <math>n</math>

'''Объём входных данных''': <math>n^2</math>

'''Выходные данные''': собственные числа матрицы

'''Объём выходных данных''': <math>n</math>

== Свойства алгоритма ==
Полная переортогонализация соответствует повторной процедуре ортогонализациии Грама-Шмидта для обеспечения ортогональности вектора <math>z</math> векторам <math>q_1, ..., q_k</math>. В случае идеально точной арифметики данная переортогонализация не требовалась бы, однако в реальных вычислениях ошибки округления приводят к потере ортогональности, в связи с чем требуется переортогонализация.
Однако, единственной проблемой, возникающей при отсутствии переортогонализации, является появление повторных копий чисел Ритца (собственных значений), что в случае, если не требуется установление кратностей собственных значений, допустимо.

Вычислительная мощность алгоритма примерно равна <math>2k^2 / n</math>.

= Программная реализация алгоритма =

== Особенности реализации последовательного алгоритма ==

== [[Локальность данных и вычислений]] ==

== Возможные способы и особенности параллельной реализации алгоритма ==

== Масштабируемость алгоритма и его реализации ==

Исследование масштабируемости алгоритма проводилось на суперкомпьютере IBM Blue Gene/P ВМК МГУ.

Для компиляции программы использовались компиляторы intel/15.0.090 и Openmpi/1.8.4-icc.

Алгоритм тестировался на следующих параметрах:
* размер входной матрицы: 5000-40000 с шагом 5000
* число узлов: 1-128

Зависимость времени выполнения от параметров изображена на графике:

[[Файл:Lanczos full chart.png|center|border |800px]]
[http://pastebin.com/u7KThy6D Используемая реализация алгоритма на языке C++]

== Динамические характеристики и эффективность реализации алгоритма ==

== Выводы для классов архитектур ==

== Существующие реализации алгоритма ==
Библиотека [http://www.nag.co.uk/numeric/fl/nagdoc_fl23/html/INDEXES/KWIC/lanczos.html NAG Library] содержит ряд процедур для решения СЛАУ и поиска собственных значений на основе алгоритма Ланцоша.

[http://www.mathworks.com/help/techdoc/ref/eigs.html MATLAB] и [https://www.gnu.org/software/octave/doc/interpreter/Sparse-Linear-Algebra.html#doc_002deigs GNU Octave] позволяют с помощью функции ''eigs()'' находить собственные значения на основе данного алгоритма.

Matlab-реализация доступна как часть [http://www.cs.cmu.edu/~bickson/gabp/#download Gaussian Belief Propagation Matlab Package]. [http://www.graphlab.ml.cmu.edu/pmf.html GraphLab] содержит несколько параллельных реализаций алгоритма на C++.

= Литература =

Участник:Error0x0/Алгоритм Ланцоша для арифметики с плавающей точкой с полной переортогонализацией

2017-02-03T18:38:35Z

Error0x0: /* Информационный граф */

{{algorithm
| name = Алгоритм Ланцоша для арифметики с плавающей точкой с полной переортогонализацией
| serial_complexity = <math>O(k^2 n)</math>
| pf_height = <math>O(k \log k \log n)</math>
| pf_width = <math>O(kn)</math>
| input_data = <math>n^2</math>
| output_data = <math>n</math>
}}
Автор описания: [[Участник:Error0x0|В. А. Янушковский]]

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

== Общее описание алгоритма ==
Алгоритм Ланцоша представляет собой итерационный алгоритм для вычисления собственных значений симметрической матрицы.
Идея алгоритма заключается в построении матрицы <math>Q_k = [q_1, ..., q_k]</math> из ортонормированных векторов Ланцоша и использовании собственных значений трёхдиагональной матрицы <math>T_k = Q_k^T A Q_k</math> (чисел Ритца) как приближения к искомым собственным числам матрицы<ref name="Деммель">Деммель Дж. Вычислительная линейная алгебра</ref>.

== Математическое описание алгоритма ==
Пусть дана матрица <math>A</math>.
Пусть <math>q_1 = b/||b||_2, \beta_0=0, q_0=0</math>
Алгоритм производит <math>k</math> итераций на каждой из которых:
# вычисляется <math>z = Aq_j</math>,
# производится переортогонализация <math>z = z - \sum^{j-1}_{i=1} {(z^T q_i)q_i}</math>,
# <math>\beta_j = ||z||_2</math>, если <math>\beta_j = 0</math>, алгоритм останавливается,
# <math>q_{j+1} = z/\beta_j</math>,
# вычисляются собственные значения и векторы матрицы <math>T_j = Q_j^T A Q_j</math>.

== Вычислительное ядро алгоритма ==
Основной вклад в сложность алгоритма даёт полная переортогонализация внутри каждой итерации:

<math>z = z - \sum^{j-1}_{i=1} {(z^T q_i)q_i}</math>

== Макроструктура алгоритма ==
Алгоритм имеет следующую макроструктуру:
* Начальная инициализация (деление вектора на норму <math>q_1 = b/||b||_2</math>)
* Далее <math>k</math> итераций, каждая из которых может быть разложена:
** Умножение матрицы на вектор (<math>z = Aq_j</math>)
** Переортогонализация <math>z = z - \sum^{j-1}_{i=1} {(z^T q_i)q_i}</math>
** Нахождение следующего вектора <math>q_{j+1} = z/\beta_j</math>, где <math>\beta_j = ||z||_2</math>
** Нахождение следующего собственного значения и вектора матрицы <math>T_j = Q_j^T A Q_j</math> (числа Ритца, используется метод "разделяй и властвуй")

== Схема реализации последовательного алгоритма ==
<syntaxhighlight lang="python">
beta[0] = 0 # инициализация
q[0] = 0
q[1] = b / norm(b) # вычисление первого столбца
for j in [1 .. k]: # k итераций
z = mul(A, q[j]) # вектор Ланцоша как произведение матрицы A на столбец q[j]
alpha[j] = scalar_mul(q[j], z) # вычисление alpha[j]
for i in [1 .. j - 1]: # полная переортогонализация
z -= scalar_mul(z, q[i]) * q[i]
beta[j] = norm(z) # вычисление нормы z
if beta[j] == 0: # останов, если норма z равна нулю
break
result.append(next_ritz_number(alpha, beta, j)) # вычисление следующего собственного значения и вектора матрицы Tj
return result
</syntaxhighlight>

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

Основной вклад в сложность даёт полная переортогонализация: на каждой из <math>k</math> итераций для всех <math>i \in [0...j-1]</math> выполняется <math>2n</math> умножений и <math>2n</math> сложений, итого <math>\frac{k(k-1)}{2} 4n \approx 2k^2 n</math>.
Таким образом, для метода с полной переортогонализацией сложность составляет <math>O(k^2 n)</math>, сложность по памяти -- <math>O(kn)</math>.

== Информационный граф ==
[[File:Lanczos graph.png|thumb|center|800px|Рисунок 1. Информационный граф]]

== Ресурс параллелизма алгоритма ==
Для процесса переортогонализации возможна параллельная оптимизация в двух местах:
* Итерации внутреннего цикла могут вычисляться параллельно, однако, требуется суммирование вычитаемых векторов, соответственно, сложность переортогонализации можно снизить с <math>O(kn)</math> до <math>O(n \log k)</math>
* В каждой итерации внутреннего цикла возможно распараллеливание вычисления выражения справа (скалярное произведение и умножение вектора на число), что теоретически позволяет снизить сложность итерации с <math>O(n)</math> до <math>O(log(n))</math>

== Входные и выходные данные алгоритма ==
'''Входные данны'''е: квадратная симметрическая матрица <math>A</math> порядка <math>n</math>

'''Объём входных данных''': <math>n^2</math>

'''Выходные данные''': собственные числа матрицы

'''Объём выходных данных''': <math>n</math>

== Свойства алгоритма ==
Полная переортогонализация соответствует повторной процедуре ортогонализациии Грама-Шмидта для обеспечения ортогональности вектора <math>z</math> векторам <math>q_1, ..., q_k</math>. В случае идеально точной арифметики данная переортогонализация не требовалась бы, однако в реальных вычислениях ошибки округления приводят к потере ортогональности, в связи с чем требуется переортогонализация.
Однако, единственной проблемой, возникающей при отсутствии переортогонализации, является появление повторных копий чисел Ритца (собственных значений), что в случае, если не требуется установление кратностей собственных значений, допустимо.

Вычислительная мощность алгоритма примерно равна <math>2k^2 / n</math>.

= Программная реализация алгоритма =

== Особенности реализации последовательного алгоритма ==

== [[Локальность данных и вычислений]] ==

== Возможные способы и особенности параллельной реализации алгоритма ==

== Масштабируемость алгоритма и его реализации ==

Исследование масштабируемости алгоритма проводилось на суперкомпьютере IBM Blue Gene/P ВМК МГУ.

Для компиляции программы использовались компиляторы intel/15.0.090 и Openmpi/1.8.4-icc.

Алгоритм тестировался на следующих параметрах:
* размер входной матрицы: 5000-40000 с шагом 5000
* число узлов: 1-128

Зависимость времени выполнения от параметров изображена на графике:

[[Файл:Lanczos full chart.png|center|border |800px]]
[http://pastebin.com/u7KThy6D Используемая реализация алгоритма на языке C++]

== Динамические характеристики и эффективность реализации алгоритма ==

== Выводы для классов архитектур ==

== Существующие реализации алгоритма ==
Библиотека [http://www.nag.co.uk/numeric/fl/nagdoc_fl23/html/INDEXES/KWIC/lanczos.html NAG Library] содержит ряд процедур для решения СЛАУ и поиска собственных значений на основе алгоритма Ланцоша.

[http://www.mathworks.com/help/techdoc/ref/eigs.html MATLAB] и [https://www.gnu.org/software/octave/doc/interpreter/Sparse-Linear-Algebra.html#doc_002deigs GNU Octave] позволяют с помощью функции ''eigs()'' находить собственные значения на основе данного алгоритма.

Matlab-реализация доступна как часть [http://www.cs.cmu.edu/~bickson/gabp/#download Gaussian Belief Propagation Matlab Package]. [http://www.graphlab.ml.cmu.edu/pmf.html GraphLab] содержит несколько параллельных реализаций алгоритма на C++.

= Литература =

Участник:Error0x0/Алгоритм Ланцоша для арифметики с плавающей точкой с полной переортогонализацией

2017-02-03T18:05:02Z

Error0x0:

{{algorithm
| name = Алгоритм Ланцоша для арифметики с плавающей точкой с полной переортогонализацией
| serial_complexity = <math>O(k^2 n)</math>
| pf_height = <math>O(k \log k \log n)</math>
| pf_width = <math>O(kn)</math>
| input_data = <math>n^2</math>
| output_data = <math>n</math>
}}
Автор описания: [[Участник:Error0x0|В. А. Янушковский]]

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

== Общее описание алгоритма ==
Алгоритм Ланцоша представляет собой итерационный алгоритм для вычисления собственных значений симметрической матрицы.
Идея алгоритма заключается в построении матрицы <math>Q_k = [q_1, ..., q_k]</math> из ортонормированных векторов Ланцоша и использовании собственных значений трёхдиагональной матрицы <math>T_k = Q_k^T A Q_k</math> (чисел Ритца) как приближения к искомым собственным числам матрицы<ref name="Деммель">Деммель Дж. Вычислительная линейная алгебра</ref>.

== Математическое описание алгоритма ==
Пусть дана матрица <math>A</math>.
Пусть <math>q_1 = b/||b||_2, \beta_0=0, q_0=0</math>
Алгоритм производит <math>k</math> итераций на каждой из которых:
# вычисляется <math>z = Aq_j</math>,
# производится переортогонализация <math>z = z - \sum^{j-1}_{i=1} {(z^T q_i)q_i}</math>,
# <math>\beta_j = ||z||_2</math>, если <math>\beta_j = 0</math>, алгоритм останавливается,
# <math>q_{j+1} = z/\beta_j</math>,
# вычисляются собственные значения и векторы матрицы <math>T_j = Q_j^T A Q_j</math>.

== Вычислительное ядро алгоритма ==
Основной вклад в сложность алгоритма даёт полная переортогонализация внутри каждой итерации:

<math>z = z - \sum^{j-1}_{i=1} {(z^T q_i)q_i}</math>

== Макроструктура алгоритма ==
Алгоритм имеет следующую макроструктуру:
* Начальная инициализация (деление вектора на норму <math>q_1 = b/||b||_2</math>)
* Далее <math>k</math> итераций, каждая из которых может быть разложена:
** Умножение матрицы на вектор (<math>z = Aq_j</math>)
** Переортогонализация <math>z = z - \sum^{j-1}_{i=1} {(z^T q_i)q_i}</math>
** Нахождение следующего вектора <math>q_{j+1} = z/\beta_j</math>, где <math>\beta_j = ||z||_2</math>
** Нахождение следующего собственного значения и вектора матрицы <math>T_j = Q_j^T A Q_j</math> (числа Ритца, используется метод "разделяй и властвуй")

== Схема реализации последовательного алгоритма ==
<syntaxhighlight lang="python">
beta[0] = 0 # инициализация
q[0] = 0
q[1] = b / norm(b) # вычисление первого столбца
for j in [1 .. k]: # k итераций
z = mul(A, q[j]) # вектор Ланцоша как произведение матрицы A на столбец q[j]
alpha[j] = scalar_mul(q[j], z) # вычисление alpha[j]
for i in [1 .. j - 1]: # полная переортогонализация
z -= scalar_mul(z, q[i]) * q[i]
beta[j] = norm(z) # вычисление нормы z
if beta[j] == 0: # останов, если норма z равна нулю
break
result.append(next_ritz_number(alpha, beta, j)) # вычисление следующего собственного значения и вектора матрицы Tj
return result
</syntaxhighlight>

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

Основной вклад в сложность даёт полная переортогонализация: на каждой из <math>k</math> итераций для всех <math>i \in [0...j-1]</math> выполняется <math>2n</math> умножений и <math>2n</math> сложений, итого <math>\frac{k(k-1)}{2} 4n \approx 2k^2 n</math>.
Таким образом, для метода с полной переортогонализацией сложность составляет <math>O(k^2 n)</math>, сложность по памяти -- <math>O(kn)</math>.

== Информационный граф ==
[[File:Lanczos graph.png|thumb|center|640px|Рисунок 1. Информационный граф]]

== Ресурс параллелизма алгоритма ==
Для процесса переортогонализации возможна параллельная оптимизация в двух местах:
* Итерации внутреннего цикла могут вычисляться параллельно, однако, требуется суммирование вычитаемых векторов, соответственно, сложность переортогонализации можно снизить с <math>O(kn)</math> до <math>O(n \log k)</math>
* В каждой итерации внутреннего цикла возможно распараллеливание вычисления выражения справа (скалярное произведение и умножение вектора на число), что теоретически позволяет снизить сложность итерации с <math>O(n)</math> до <math>O(log(n))</math>

== Входные и выходные данные алгоритма ==
'''Входные данны'''е: квадратная симметрическая матрица <math>A</math> порядка <math>n</math>

'''Объём входных данных''': <math>n^2</math>

'''Выходные данные''': собственные числа матрицы

'''Объём выходных данных''': <math>n</math>

== Свойства алгоритма ==
Полная переортогонализация соответствует повторной процедуре ортогонализациии Грама-Шмидта для обеспечения ортогональности вектора <math>z</math> векторам <math>q_1, ..., q_k</math>. В случае идеально точной арифметики данная переортогонализация не требовалась бы, однако в реальных вычислениях ошибки округления приводят к потере ортогональности, в связи с чем требуется переортогонализация.
Однако, единственной проблемой, возникающей при отсутствии переортогонализации, является появление повторных копий чисел Ритца (собственных значений), что в случае, если не требуется установление кратностей собственных значений, допустимо.

Вычислительная мощность алгоритма примерно равна <math>2k^2 / n</math>.

= Программная реализация алгоритма =

== Особенности реализации последовательного алгоритма ==

== [[Локальность данных и вычислений]] ==

== Возможные способы и особенности параллельной реализации алгоритма ==

== Масштабируемость алгоритма и его реализации ==

Исследование масштабируемости алгоритма проводилось на суперкомпьютере IBM Blue Gene/P ВМК МГУ.

Для компиляции программы использовались компиляторы intel/15.0.090 и Openmpi/1.8.4-icc.

Алгоритм тестировался на следующих параметрах:
* размер входной матрицы: 5000-40000 с шагом 5000
* число узлов: 1-128

Зависимость времени выполнения от параметров изображена на графике:

[[Файл:Lanczos full chart.png|center|border |800px]]
[http://pastebin.com/u7KThy6D Используемая реализация алгоритма на языке C++]

== Динамические характеристики и эффективность реализации алгоритма ==

== Выводы для классов архитектур ==

== Существующие реализации алгоритма ==
Библиотека [http://www.nag.co.uk/numeric/fl/nagdoc_fl23/html/INDEXES/KWIC/lanczos.html NAG Library] содержит ряд процедур для решения СЛАУ и поиска собственных значений на основе алгоритма Ланцоша.

[http://www.mathworks.com/help/techdoc/ref/eigs.html MATLAB] и [https://www.gnu.org/software/octave/doc/interpreter/Sparse-Linear-Algebra.html#doc_002deigs GNU Octave] позволяют с помощью функции ''eigs()'' находить собственные значения на основе данного алгоритма.

Matlab-реализация доступна как часть [http://www.cs.cmu.edu/~bickson/gabp/#download Gaussian Belief Propagation Matlab Package]. [http://www.graphlab.ml.cmu.edu/pmf.html GraphLab] содержит несколько параллельных реализаций алгоритма на C++.

= Литература =

Участник:Error0x0/Алгоритм Ланцоша для арифметики с плавающей точкой с полной переортогонализацией

2017-02-02T12:31:44Z

Error0x0:

{{assignment}}
{{algorithm
| name = Алгоритм Ланцоша для арифметики с плавающей точкой с полной переортогонализацией
| serial_complexity = <math>O(k^2 n)</math>
| pf_height = <math>O(k \log k \log n)</math>
| pf_width = <math>O(kn)</math>
| input_data = <math>n^2</math>
| output_data = <math>n</math>
}}
Автор описания: [[Участник:Error0x0|В. А. Янушковский]]

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

== Общее описание алгоритма ==
Алгоритм Ланцоша представляет собой итерационный алгоритм для вычисления собственных значений симметрической матрицы.
Идея алгоритма заключается в построении матрицы <math>Q_k = [q_1, ..., q_k]</math> из ортонормированных векторов Ланцоша и использовании собственных значений трёхдиагональной матрицы <math>T_k = Q_k^T A Q_k</math> (чисел Ритца) как приближения к искомым собственным числам матрицы<ref name="Деммель">Деммель Дж. Вычислительная линейная алгебра</ref>.

== Математическое описание алгоритма ==
Пусть дана матрица <math>A</math>.
Пусть <math>q_1 = b/||b||_2, \beta_0=0, q_0=0</math>
Алгоритм производит <math>k</math> итераций на каждой из которых:
# вычисляется <math>z = Aq_j</math>,
# производится переортогонализация <math>z = z - \sum^{j-1}_{i=1} {(z^T q_i)q_i}</math>,
# <math>\beta_j = ||z||_2</math>, если <math>\beta_j = 0</math>, алгоритм останавливается,
# <math>q_{j+1} = z/\beta_j</math>,
# вычисляются собственные значения и векторы матрицы <math>T_j = Q_j^T A Q_j</math>.

== Вычислительное ядро алгоритма ==
Основной вклад в сложность алгоритма даёт полная переортогонализация внутри каждой итерации:

<math>z = z - \sum^{j-1}_{i=1} {(z^T q_i)q_i}</math>

== Макроструктура алгоритма ==
используются следующие макрооперации:
* Нахождение нормы вектора (евклидовой)
* Умножение/деление вектора на число
* Умножение матрицы на вектор (<math>z = Aq_j</math>)
* Скалярное произведение двух векторов
* Вычитание векторов
* Вычисление собственных значений и векторов трёхдиагональной матрицы <math>T_j</math> (числа Ритца, используется метод "разделяй и властвуй")

== Схема реализации последовательного алгоритма ==
<syntaxhighlight lang="python">
beta[0] = 0 # инициализация
q[0] = 0
q[1] = b / norm(b) # вычисление первого столбца
for j in [1 .. k]: # k итераций
z = mul(A, q[j]) # вектор Ланцоша как произведение матрицы A на столбец q[j]
alpha[j] = scalar_mul(q[j], z) # вычисление alpha[j]
for i in [1 .. j - 1]: # полная переортогонализация
z -= scalar_mul(z, q[i]) * q[i]
beta[j] = norm(z) # вычисление нормы z
if beta[j] == 0: # останов, если норма z равна нулю
break
result.append(next_ritz_number(alpha, beta, j)) # вычисление следующего собственного значения и вектора матрицы Tj
return result
</syntaxhighlight>

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

Основной вклад в сложность даёт полная переортогонализация: на каждой из <math>k</math> итераций для всех <math>i \in [0...j-1]</math> выполняется <math>2n</math> умножений и <math>2n</math> сложений, итого <math>\frac{k(k-1)}{2} 4n \approx 2k^2 n</math>.
Таким образом, для метода с полной переортогонализацией сложность составляет <math>O(k^2 n)</math>, сложность по памяти -- <math>O(kn)</math>.

== Информационный граф ==
[[File:Lanczos graph.png|thumb|center|640px|Рисунок 1. Информационный граф]]

== Ресурс параллелизма алгоритма ==
Для процесса переортогонализации возможна параллельная оптимизация в двух местах:
* Итерации внутреннего цикла могут вычисляться параллельно, однако, требуется суммирование вычитаемых векторов, соответственно, сложность переортогонализации можно снизить с <math>O(kn)</math> до <math>O(n \log k)</math>
* В каждой итерации внутреннего цикла возможно распараллеливание вычисления выражения справа (скалярное произведение и умножение вектора на число), что теоретически позволяет снизить сложность итерации с <math>O(n)</math> до <math>O(log(n))</math>

== Входные и выходные данные алгоритма ==
'''Входные данны'''е: квадратная симметрическая матрица <math>A</math> порядка <math>n</math>

'''Объём входных данных''': <math>n^2</math>

'''Выходные данные''': собственные числа матрицы

'''Объём выходных данных''': <math>n</math>

== Свойства алгоритма ==
Полная переортогонализация соответствует повторной процедуре ортогонализациии Грама-Шмидта для обеспечения ортогональности вектора <math>z</math> векторам <math>q_1, ..., q_k</math>. В случае идеально точной арифметики данная переортогонализация не требовалась бы, однако в реальных вычислениях ошибки округления приводят к потере ортогональности, в связи с чем требуется переортогонализация.
Однако, единственной проблемой, возникающей при отсутствии переортогонализации, является появление повторных копий чисел Ритца (собственных значений), что в случае, если не требуется установление кратностей собственных значений, допустимо.

Вычислительная мощность алгоритма примерно равна <math>2k^2 / n</math>.

= Программная реализация алгоритма =

== Особенности реализации последовательного алгоритма ==

== [[Локальность данных и вычислений]] ==

== Возможные способы и особенности параллельной реализации алгоритма ==

== Масштабируемость алгоритма и его реализации ==

Исследование масштабируемости алгоритма проводилось на суперкомпьютере IBM Blue Gene/P ВМК МГУ.

Для компиляции программы использовались компиляторы intel/15.0.090 и Openmpi/1.8.4-icc.

Алгоритм тестировался на следующих параметрах:
* размер входной матрицы: 5000-40000 с шагом 5000
* число узлов: 1-128

Зависимость времени выполнения от параметров изображена на графике:

[[Файл:Lanczos full chart.png|center|border |800px]]
[http://pastebin.com/u7KThy6D Используемая реализация алгоритма на языке C++]

== Динамические характеристики и эффективность реализации алгоритма ==

== Выводы для классов архитектур ==

== Существующие реализации алгоритма ==
Библиотека [http://www.nag.co.uk/numeric/fl/nagdoc_fl23/html/INDEXES/KWIC/lanczos.html NAG Library] содержит ряд процедур для решения СЛАУ и поиска собственных значений на основе алгоритма Ланцоша.

[http://www.mathworks.com/help/techdoc/ref/eigs.html MATLAB] и [https://www.gnu.org/software/octave/doc/interpreter/Sparse-Linear-Algebra.html#doc_002deigs GNU Octave] позволяют с помощью функции ''eigs()'' находить собственные значения на основе данного алгоритма.

Matlab-реализация доступна как часть [http://www.cs.cmu.edu/~bickson/gabp/#download Gaussian Belief Propagation Matlab Package]. [http://www.graphlab.ml.cmu.edu/pmf.html GraphLab] содержит несколько параллельных реализаций алгоритма на C++.

= Литература =

Обсуждение участника:Error0x0

2017-02-01T21:04:02Z

Error0x0: /* Статья Участник:Error0x0/Алгоритм Ланцоша для арифметики с плавающей точкой с полной переортогонализацией */

Участник:Error0x0/Алгоритм Ланцоша для арифметики с плавающей точкой с полной переортогонализацией

2017-02-01T21:03:14Z

Error0x0: /* Масштабируемость алгоритма и его реализации */

{{algorithm
| name = Алгоритм Ланцоша для арифметики с плавающей точкой с полной переортогонализацией
| serial_complexity = <math>O(k^2 n)</math>
| pf_height = <math>O(k \log k \log n)</math>
| pf_width = <math>O(kn)</math>
| input_data = <math>n^2</math>
| output_data = <math>n</math>
}}
Автор описания: [[Участник:Error0x0|В. А. Янушковский]]

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

== Общее описание алгоритма ==
Алгоритм Ланцоша представляет собой итерационный алгоритм для вычисления собственных значений симметрической матрицы.
Идея алгоритма заключается в построении матрицы <math>Q_k = [q_1, ..., q_k]</math> из ортонормированных векторов Ланцоша и использовании собственных значений трёхдиагональной матрицы <math>T_k = Q_k^T A Q_k</math> (чисел Ритца) как приближения к искомым собственным числам матрицы<ref name="Деммель">Деммель Дж. Вычислительная линейная алгебра</ref>.

== Математическое описание алгоритма ==
Пусть дана матрица <math>A</math>.
Пусть <math>q_1 = b/||b||_2, \beta_0=0, q_0=0</math>
Алгоритм производит <math>k</math> итераций на каждой из которых:
# вычисляется <math>z = Aq_j</math>,
# производится переортогонализация <math>z = z - \sum^{j-1}_{i=1} {(z^T q_i)q_i}</math>,
# <math>\beta_j = ||z||_2</math>, если <math>\beta_j = 0</math>, алгоритм останавливается,
# <math>q_{j+1} = z/\beta_j</math>,
# вычисляются собственные значения и векторы матрицы <math>T_j = Q_j^T A Q_j</math>.

== Вычислительное ядро алгоритма ==
Основной вклад в сложность алгоритма даёт полная переортогонализация внутри каждой итерации:

<math>z = z - \sum^{j-1}_{i=1} {(z^T q_i)q_i}</math>

== Макроструктура алгоритма ==
используются следующие макрооперации:
* Нахождение нормы вектора (евклидовой)
* Умножение/деление вектора на число
* Умножение матрицы на вектор (<math>z = Aq_j</math>)
* Скалярное произведение двух векторов
* Вычитание векторов
* Вычисление собственных значений и векторов трёхдиагональной матрицы <math>T_j</math> (числа Ритца, используется метод "разделяй и властвуй")

== Схема реализации последовательного алгоритма ==
<syntaxhighlight lang="python">
beta[0] = 0 # инициализация
q[0] = 0
q[1] = b / norm(b) # вычисление первого столбца
for j in [1 .. k]: # k итераций
z = mul(A, q[j]) # вектор Ланцоша как произведение матрицы A на столбец q[j]
alpha[j] = scalar_mul(q[j], z) # вычисление alpha[j]
for i in [1 .. j - 1]: # полная переортогонализация
z -= scalar_mul(z, q[i]) * q[i]
beta[j] = norm(z) # вычисление нормы z
if beta[j] == 0: # останов, если норма z равна нулю
break
result.append(next_ritz_number(alpha, beta, j)) # вычисление следующего собственного значения и вектора матрицы Tj
return result
</syntaxhighlight>

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

Основной вклад в сложность даёт полная переортогонализация: на каждой из <math>k</math> итераций для всех <math>i \in [0...j-1]</math> выполняется <math>2n</math> умножений и <math>2n</math> сложений, итого <math>\frac{k(k-1)}{2} 4n \approx 2k^2 n</math>.
Таким образом, для метода с полной переортогонализацией сложность составляет <math>O(k^2 n)</math>, сложность по памяти -- <math>O(kn)</math>.

== Информационный граф ==
[[File:Lanczos graph.png|thumb|center|640px|Рисунок 1. Информационный граф]]

== Ресурс параллелизма алгоритма ==
Для процесса переортогонализации возможна параллельная оптимизация в двух местах:
* Итерации внутреннего цикла могут вычисляться параллельно, однако, требуется суммирование вычитаемых векторов, соответственно, сложность переортогонализации можно снизить с <math>O(kn)</math> до <math>O(n \log k)</math>
* В каждой итерации внутреннего цикла возможно распараллеливание вычисления выражения справа (скалярное произведение и умножение вектора на число), что теоретически позволяет снизить сложность итерации с <math>O(n)</math> до <math>O(log(n))</math>

== Входные и выходные данные алгоритма ==
'''Входные данны'''е: квадратная симметрическая матрица <math>A</math> порядка <math>n</math>

'''Объём входных данных''': <math>n^2</math>

'''Выходные данные''': собственные числа матрицы

'''Объём выходных данных''': <math>n</math>

== Свойства алгоритма ==
Полная переортогонализация соответствует повторной процедуре ортогонализациии Грама-Шмидта для обеспечения ортогональности вектора <math>z</math> векторам <math>q_1, ..., q_k</math>. В случае идеально точной арифметики данная переортогонализация не требовалась бы, однако в реальных вычислениях ошибки округления приводят к потере ортогональности, в связи с чем требуется переортогонализация.
Однако, единственной проблемой, возникающей при отсутствии переортогонализации, является появление повторных копий чисел Ритца (собственных значений), что в случае, если не требуется установление кратностей собственных значений, допустимо.

Вычислительная мощность алгоритма примерно равна <math>2k^2 / n</math>.

= Программная реализация алгоритма =

== Особенности реализации последовательного алгоритма ==

== [[Локальность данных и вычислений]] ==

== Возможные способы и особенности параллельной реализации алгоритма ==

== Масштабируемость алгоритма и его реализации ==

Исследование масштабируемости алгоритма проводилось на суперкомпьютере IBM Blue Gene/P ВМК МГУ.

Для компиляции программы использовались компиляторы intel/15.0.090 и Openmpi/1.8.4-icc.

Алгоритм тестировался на следующих параметрах:
* размер входной матрицы: 5000-40000 с шагом 5000
* число узлов: 1-128

Зависимость времени выполнения от параметров изображена на графике:

[[Файл:Lanczos full chart.png|center|border |800px]]
[http://pastebin.com/u7KThy6D Используемая реализация алгоритма на языке C++]

== Динамические характеристики и эффективность реализации алгоритма ==

== Выводы для классов архитектур ==

== Существующие реализации алгоритма ==
Библиотека [http://www.nag.co.uk/numeric/fl/nagdoc_fl23/html/INDEXES/KWIC/lanczos.html NAG Library] содержит ряд процедур для решения СЛАУ и поиска собственных значений на основе алгоритма Ланцоша.

[http://www.mathworks.com/help/techdoc/ref/eigs.html MATLAB] и [https://www.gnu.org/software/octave/doc/interpreter/Sparse-Linear-Algebra.html#doc_002deigs GNU Octave] позволяют с помощью функции ''eigs()'' находить собственные значения на основе данного алгоритма.

Matlab-реализация доступна как часть [http://www.cs.cmu.edu/~bickson/gabp/#download Gaussian Belief Propagation Matlab Package]. [http://www.graphlab.ml.cmu.edu/pmf.html GraphLab] содержит несколько параллельных реализаций алгоритма на C++.

= Литература =

Участник:Error0x0/Алгоритм Ланцоша для арифметики с плавающей точкой с полной переортогонализацией

2017-02-01T21:02:58Z

Error0x0: /* Масштабируемость алгоритма и его реализации */

{{algorithm
| name = Алгоритм Ланцоша для арифметики с плавающей точкой с полной переортогонализацией
| serial_complexity = <math>O(k^2 n)</math>
| pf_height = <math>O(k \log k \log n)</math>
| pf_width = <math>O(kn)</math>
| input_data = <math>n^2</math>
| output_data = <math>n</math>
}}
Автор описания: [[Участник:Error0x0|В. А. Янушковский]]

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

== Общее описание алгоритма ==
Алгоритм Ланцоша представляет собой итерационный алгоритм для вычисления собственных значений симметрической матрицы.
Идея алгоритма заключается в построении матрицы <math>Q_k = [q_1, ..., q_k]</math> из ортонормированных векторов Ланцоша и использовании собственных значений трёхдиагональной матрицы <math>T_k = Q_k^T A Q_k</math> (чисел Ритца) как приближения к искомым собственным числам матрицы<ref name="Деммель">Деммель Дж. Вычислительная линейная алгебра</ref>.

== Математическое описание алгоритма ==
Пусть дана матрица <math>A</math>.
Пусть <math>q_1 = b/||b||_2, \beta_0=0, q_0=0</math>
Алгоритм производит <math>k</math> итераций на каждой из которых:
# вычисляется <math>z = Aq_j</math>,
# производится переортогонализация <math>z = z - \sum^{j-1}_{i=1} {(z^T q_i)q_i}</math>,
# <math>\beta_j = ||z||_2</math>, если <math>\beta_j = 0</math>, алгоритм останавливается,
# <math>q_{j+1} = z/\beta_j</math>,
# вычисляются собственные значения и векторы матрицы <math>T_j = Q_j^T A Q_j</math>.

== Вычислительное ядро алгоритма ==
Основной вклад в сложность алгоритма даёт полная переортогонализация внутри каждой итерации:

<math>z = z - \sum^{j-1}_{i=1} {(z^T q_i)q_i}</math>

== Макроструктура алгоритма ==
используются следующие макрооперации:
* Нахождение нормы вектора (евклидовой)
* Умножение/деление вектора на число
* Умножение матрицы на вектор (<math>z = Aq_j</math>)
* Скалярное произведение двух векторов
* Вычитание векторов
* Вычисление собственных значений и векторов трёхдиагональной матрицы <math>T_j</math> (числа Ритца, используется метод "разделяй и властвуй")

== Схема реализации последовательного алгоритма ==
<syntaxhighlight lang="python">
beta[0] = 0 # инициализация
q[0] = 0
q[1] = b / norm(b) # вычисление первого столбца
for j in [1 .. k]: # k итераций
z = mul(A, q[j]) # вектор Ланцоша как произведение матрицы A на столбец q[j]
alpha[j] = scalar_mul(q[j], z) # вычисление alpha[j]
for i in [1 .. j - 1]: # полная переортогонализация
z -= scalar_mul(z, q[i]) * q[i]
beta[j] = norm(z) # вычисление нормы z
if beta[j] == 0: # останов, если норма z равна нулю
break
result.append(next_ritz_number(alpha, beta, j)) # вычисление следующего собственного значения и вектора матрицы Tj
return result
</syntaxhighlight>

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

Основной вклад в сложность даёт полная переортогонализация: на каждой из <math>k</math> итераций для всех <math>i \in [0...j-1]</math> выполняется <math>2n</math> умножений и <math>2n</math> сложений, итого <math>\frac{k(k-1)}{2} 4n \approx 2k^2 n</math>.
Таким образом, для метода с полной переортогонализацией сложность составляет <math>O(k^2 n)</math>, сложность по памяти -- <math>O(kn)</math>.

== Информационный граф ==
[[File:Lanczos graph.png|thumb|center|640px|Рисунок 1. Информационный граф]]

== Ресурс параллелизма алгоритма ==
Для процесса переортогонализации возможна параллельная оптимизация в двух местах:
* Итерации внутреннего цикла могут вычисляться параллельно, однако, требуется суммирование вычитаемых векторов, соответственно, сложность переортогонализации можно снизить с <math>O(kn)</math> до <math>O(n \log k)</math>
* В каждой итерации внутреннего цикла возможно распараллеливание вычисления выражения справа (скалярное произведение и умножение вектора на число), что теоретически позволяет снизить сложность итерации с <math>O(n)</math> до <math>O(log(n))</math>

== Входные и выходные данные алгоритма ==
'''Входные данны'''е: квадратная симметрическая матрица <math>A</math> порядка <math>n</math>

'''Объём входных данных''': <math>n^2</math>

'''Выходные данные''': собственные числа матрицы

'''Объём выходных данных''': <math>n</math>

== Свойства алгоритма ==
Полная переортогонализация соответствует повторной процедуре ортогонализациии Грама-Шмидта для обеспечения ортогональности вектора <math>z</math> векторам <math>q_1, ..., q_k</math>. В случае идеально точной арифметики данная переортогонализация не требовалась бы, однако в реальных вычислениях ошибки округления приводят к потере ортогональности, в связи с чем требуется переортогонализация.
Однако, единственной проблемой, возникающей при отсутствии переортогонализации, является появление повторных копий чисел Ритца (собственных значений), что в случае, если не требуется установление кратностей собственных значений, допустимо.

Вычислительная мощность алгоритма примерно равна <math>2k^2 / n</math>.

= Программная реализация алгоритма =

== Особенности реализации последовательного алгоритма ==

== [[Локальность данных и вычислений]] ==

== Возможные способы и особенности параллельной реализации алгоритма ==

== Масштабируемость алгоритма и его реализации ==

Исследование масштабируемости алгоритма проводилось на суперкомпьютере IBM Blue Gene/P ВМК МГУ.

Для компиляции программы использовались компиляторы intel/15.0.090 и Openmpi/1.8.4-icc.

Алгоритм тестировался на следующих параметрах:
* размер входной матрицы: 5000-40000 с шагом 5000
* число узлов: 1-128

Зависимость времени выполнения от параметров изображена на графике:

[[Файл:Lanczos full chart.png center|border |800px]]
[http://pastebin.com/u7KThy6D Используемая реализация алгоритма на языке C++]

== Динамические характеристики и эффективность реализации алгоритма ==

== Выводы для классов архитектур ==

== Существующие реализации алгоритма ==
Библиотека [http://www.nag.co.uk/numeric/fl/nagdoc_fl23/html/INDEXES/KWIC/lanczos.html NAG Library] содержит ряд процедур для решения СЛАУ и поиска собственных значений на основе алгоритма Ланцоша.

[http://www.mathworks.com/help/techdoc/ref/eigs.html MATLAB] и [https://www.gnu.org/software/octave/doc/interpreter/Sparse-Linear-Algebra.html#doc_002deigs GNU Octave] позволяют с помощью функции ''eigs()'' находить собственные значения на основе данного алгоритма.

Matlab-реализация доступна как часть [http://www.cs.cmu.edu/~bickson/gabp/#download Gaussian Belief Propagation Matlab Package]. [http://www.graphlab.ml.cmu.edu/pmf.html GraphLab] содержит несколько параллельных реализаций алгоритма на C++.

= Литература =

Участник:Error0x0/Алгоритм Ланцоша для арифметики с плавающей точкой с полной переортогонализацией

2017-02-01T20:59:35Z

Error0x0: /* Масштабируемость алгоритма и его реализации */

{{algorithm
| name = Алгоритм Ланцоша для арифметики с плавающей точкой с полной переортогонализацией
| serial_complexity = <math>O(k^2 n)</math>
| pf_height = <math>O(k \log k \log n)</math>
| pf_width = <math>O(kn)</math>
| input_data = <math>n^2</math>
| output_data = <math>n</math>
}}
Автор описания: [[Участник:Error0x0|В. А. Янушковский]]

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

== Общее описание алгоритма ==
Алгоритм Ланцоша представляет собой итерационный алгоритм для вычисления собственных значений симметрической матрицы.
Идея алгоритма заключается в построении матрицы <math>Q_k = [q_1, ..., q_k]</math> из ортонормированных векторов Ланцоша и использовании собственных значений трёхдиагональной матрицы <math>T_k = Q_k^T A Q_k</math> (чисел Ритца) как приближения к искомым собственным числам матрицы<ref name="Деммель">Деммель Дж. Вычислительная линейная алгебра</ref>.

== Математическое описание алгоритма ==
Пусть дана матрица <math>A</math>.
Пусть <math>q_1 = b/||b||_2, \beta_0=0, q_0=0</math>
Алгоритм производит <math>k</math> итераций на каждой из которых:
# вычисляется <math>z = Aq_j</math>,
# производится переортогонализация <math>z = z - \sum^{j-1}_{i=1} {(z^T q_i)q_i}</math>,
# <math>\beta_j = ||z||_2</math>, если <math>\beta_j = 0</math>, алгоритм останавливается,
# <math>q_{j+1} = z/\beta_j</math>,
# вычисляются собственные значения и векторы матрицы <math>T_j = Q_j^T A Q_j</math>.

== Вычислительное ядро алгоритма ==
Основной вклад в сложность алгоритма даёт полная переортогонализация внутри каждой итерации:

<math>z = z - \sum^{j-1}_{i=1} {(z^T q_i)q_i}</math>

== Макроструктура алгоритма ==
используются следующие макрооперации:
* Нахождение нормы вектора (евклидовой)
* Умножение/деление вектора на число
* Умножение матрицы на вектор (<math>z = Aq_j</math>)
* Скалярное произведение двух векторов
* Вычитание векторов
* Вычисление собственных значений и векторов трёхдиагональной матрицы <math>T_j</math> (числа Ритца, используется метод "разделяй и властвуй")

== Схема реализации последовательного алгоритма ==
<syntaxhighlight lang="python">
beta[0] = 0 # инициализация
q[0] = 0
q[1] = b / norm(b) # вычисление первого столбца
for j in [1 .. k]: # k итераций
z = mul(A, q[j]) # вектор Ланцоша как произведение матрицы A на столбец q[j]
alpha[j] = scalar_mul(q[j], z) # вычисление alpha[j]
for i in [1 .. j - 1]: # полная переортогонализация
z -= scalar_mul(z, q[i]) * q[i]
beta[j] = norm(z) # вычисление нормы z
if beta[j] == 0: # останов, если норма z равна нулю
break
result.append(next_ritz_number(alpha, beta, j)) # вычисление следующего собственного значения и вектора матрицы Tj
return result
</syntaxhighlight>

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

Основной вклад в сложность даёт полная переортогонализация: на каждой из <math>k</math> итераций для всех <math>i \in [0...j-1]</math> выполняется <math>2n</math> умножений и <math>2n</math> сложений, итого <math>\frac{k(k-1)}{2} 4n \approx 2k^2 n</math>.
Таким образом, для метода с полной переортогонализацией сложность составляет <math>O(k^2 n)</math>, сложность по памяти -- <math>O(kn)</math>.

== Информационный граф ==
[[File:Lanczos graph.png|thumb|center|640px|Рисунок 1. Информационный граф]]

== Ресурс параллелизма алгоритма ==
Для процесса переортогонализации возможна параллельная оптимизация в двух местах:
* Итерации внутреннего цикла могут вычисляться параллельно, однако, требуется суммирование вычитаемых векторов, соответственно, сложность переортогонализации можно снизить с <math>O(kn)</math> до <math>O(n \log k)</math>
* В каждой итерации внутреннего цикла возможно распараллеливание вычисления выражения справа (скалярное произведение и умножение вектора на число), что теоретически позволяет снизить сложность итерации с <math>O(n)</math> до <math>O(log(n))</math>

== Входные и выходные данные алгоритма ==
'''Входные данны'''е: квадратная симметрическая матрица <math>A</math> порядка <math>n</math>

'''Объём входных данных''': <math>n^2</math>

'''Выходные данные''': собственные числа матрицы

'''Объём выходных данных''': <math>n</math>

== Свойства алгоритма ==
Полная переортогонализация соответствует повторной процедуре ортогонализациии Грама-Шмидта для обеспечения ортогональности вектора <math>z</math> векторам <math>q_1, ..., q_k</math>. В случае идеально точной арифметики данная переортогонализация не требовалась бы, однако в реальных вычислениях ошибки округления приводят к потере ортогональности, в связи с чем требуется переортогонализация.
Однако, единственной проблемой, возникающей при отсутствии переортогонализации, является появление повторных копий чисел Ритца (собственных значений), что в случае, если не требуется установление кратностей собственных значений, допустимо.

Вычислительная мощность алгоритма примерно равна <math>2k^2 / n</math>.

= Программная реализация алгоритма =

== Особенности реализации последовательного алгоритма ==

== [[Локальность данных и вычислений]] ==

== Возможные способы и особенности параллельной реализации алгоритма ==

== Масштабируемость алгоритма и его реализации ==

Исследование масштабируемости алгоритма проводилось на суперкомпьютере IBM Blue Gene/P ВМК МГУ.

Для компиляции программы использовались компиляторы intel/15.0.090 и Openmpi/1.8.4-icc.

Алгоритм тестировался на следующих параметрах:
* размер входной матрицы: 5000-40000 с шагом 5000
* число узлов: 1-128

Зависимость времени выполнения от параметров изображена на графике:

[[Файл:Lanczos full chart.png]]

== Динамические характеристики и эффективность реализации алгоритма ==

== Выводы для классов архитектур ==

== Существующие реализации алгоритма ==
Библиотека [http://www.nag.co.uk/numeric/fl/nagdoc_fl23/html/INDEXES/KWIC/lanczos.html NAG Library] содержит ряд процедур для решения СЛАУ и поиска собственных значений на основе алгоритма Ланцоша.

[http://www.mathworks.com/help/techdoc/ref/eigs.html MATLAB] и [https://www.gnu.org/software/octave/doc/interpreter/Sparse-Linear-Algebra.html#doc_002deigs GNU Octave] позволяют с помощью функции ''eigs()'' находить собственные значения на основе данного алгоритма.

Matlab-реализация доступна как часть [http://www.cs.cmu.edu/~bickson/gabp/#download Gaussian Belief Propagation Matlab Package]. [http://www.graphlab.ml.cmu.edu/pmf.html GraphLab] содержит несколько параллельных реализаций алгоритма на C++.

= Литература =

Обсуждение участника:Error0x0

2017-02-01T18:16:59Z

Участник:Error0x0/Алгоритм Ланцоша для арифметики с плавающей точкой с полной переортогонализацией

2017-02-01T18:15:52Z

Error0x0: /* Последовательная сложность алгоритма */

{{algorithm
| name = Алгоритм Ланцоша для арифметики с плавающей точкой с полной переортогонализацией
| serial_complexity = <math>O(k^2 n)</math>
| pf_height = <math>O(k \log k \log n)</math>
| pf_width = <math>O(kn)</math>
| input_data = <math>n^2</math>
| output_data = <math>n</math>
}}
Автор описания: [[Участник:Error0x0|В. А. Янушковский]]

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

== Общее описание алгоритма ==
Алгоритм Ланцоша представляет собой итерационный алгоритм для вычисления собственных значений симметрической матрицы.
Идея алгоритма заключается в построении матрицы <math>Q_k = [q_1, ..., q_k]</math> из ортонормированных векторов Ланцоша и использовании собственных значений трёхдиагональной матрицы <math>T_k = Q_k^T A Q_k</math> (чисел Ритца) как приближения к искомым собственным числам матрицы<ref name="Деммель">Деммель Дж. Вычислительная линейная алгебра</ref>.

== Математическое описание алгоритма ==
Пусть дана матрица <math>A</math>.
Пусть <math>q_1 = b/||b||_2, \beta_0=0, q_0=0</math>
Алгоритм производит <math>k</math> итераций на каждой из которых:
# вычисляется <math>z = Aq_j</math>,
# производится переортогонализация <math>z = z - \sum^{j-1}_{i=1} {(z^T q_i)q_i}</math>,
# <math>\beta_j = ||z||_2</math>, если <math>\beta_j = 0</math>, алгоритм останавливается,
# <math>q_{j+1} = z/\beta_j</math>,
# вычисляются собственные значения и векторы матрицы <math>T_j = Q_j^T A Q_j</math>.

== Вычислительное ядро алгоритма ==
Основной вклад в сложность алгоритма даёт полная переортогонализация внутри каждой итерации:

<math>z = z - \sum^{j-1}_{i=1} {(z^T q_i)q_i}</math>

== Макроструктура алгоритма ==
используются следующие макрооперации:
* Нахождение нормы вектора (евклидовой)
* Умножение/деление вектора на число
* Умножение матрицы на вектор (<math>z = Aq_j</math>)
* Скалярное произведение двух векторов
* Вычитание векторов
* Вычисление собственных значений и векторов трёхдиагональной матрицы <math>T_j</math> (числа Ритца, используется метод "разделяй и властвуй")

== Схема реализации последовательного алгоритма ==
<syntaxhighlight lang="python">
beta[0] = 0 # инициализация
q[0] = 0
q[1] = b / norm(b) # вычисление первого столбца
for j in [1 .. k]: # k итераций
z = mul(A, q[j]) # вектор Ланцоша как произведение матрицы A на столбец q[j]
alpha[j] = scalar_mul(q[j], z) # вычисление alpha[j]
for i in [1 .. j - 1]: # полная переортогонализация
z -= scalar_mul(z, q[i]) * q[i]
beta[j] = norm(z) # вычисление нормы z
if beta[j] == 0: # останов, если норма z равна нулю
break
result.append(next_ritz_number(alpha, beta, j)) # вычисление следующего собственного значения и вектора матрицы Tj
return result
</syntaxhighlight>

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

Основной вклад в сложность даёт полная переортогонализация: на каждой из <math>k</math> итераций для всех <math>i \in [0...j-1]</math> выполняется <math>2n</math> умножений и <math>2n</math> сложений, итого <math>\frac{k(k-1)}{2} 4n \approx 2k^2 n</math>.
Таким образом, для метода с полной переортогонализацией сложность составляет <math>O(k^2 n)</math>, сложность по памяти -- <math>O(kn)</math>.

== Информационный граф ==
[[File:Lanczos graph.png|thumb|center|640px|Рисунок 1. Информационный граф]]

== Ресурс параллелизма алгоритма ==
Для процесса переортогонализации возможна параллельная оптимизация в двух местах:
* Итерации внутреннего цикла могут вычисляться параллельно, однако, требуется суммирование вычитаемых векторов, соответственно, сложность переортогонализации можно снизить с <math>O(kn)</math> до <math>O(n \log k)</math>
* В каждой итерации внутреннего цикла возможно распараллеливание вычисления выражения справа (скалярное произведение и умножение вектора на число), что теоретически позволяет снизить сложность итерации с <math>O(n)</math> до <math>O(log(n))</math>

== Входные и выходные данные алгоритма ==
'''Входные данны'''е: квадратная симметрическая матрица <math>A</math> порядка <math>n</math>

'''Объём входных данных''': <math>n^2</math>

'''Выходные данные''': собственные числа матрицы

'''Объём выходных данных''': <math>n</math>

== Свойства алгоритма ==
Полная переортогонализация соответствует повторной процедуре ортогонализациии Грама-Шмидта для обеспечения ортогональности вектора <math>z</math> векторам <math>q_1, ..., q_k</math>. В случае идеально точной арифметики данная переортогонализация не требовалась бы, однако в реальных вычислениях ошибки округления приводят к потере ортогональности, в связи с чем требуется переортогонализация.
Однако, единственной проблемой, возникающей при отсутствии переортогонализации, является появление повторных копий чисел Ритца (собственных значений), что в случае, если не требуется установление кратностей собственных значений, допустимо.

Вычислительная мощность алгоритма примерно равна <math>2k^2 / n</math>.

= Программная реализация алгоритма =

== Особенности реализации последовательного алгоритма ==

== [[Локальность данных и вычислений]] ==

== Возможные способы и особенности параллельной реализации алгоритма ==

== Масштабируемость алгоритма и его реализации ==

== Динамические характеристики и эффективность реализации алгоритма ==

== Выводы для классов архитектур ==

== Существующие реализации алгоритма ==
Библиотека [http://www.nag.co.uk/numeric/fl/nagdoc_fl23/html/INDEXES/KWIC/lanczos.html NAG Library] содержит ряд процедур для решения СЛАУ и поиска собственных значений на основе алгоритма Ланцоша.

[http://www.mathworks.com/help/techdoc/ref/eigs.html MATLAB] и [https://www.gnu.org/software/octave/doc/interpreter/Sparse-Linear-Algebra.html#doc_002deigs GNU Octave] позволяют с помощью функции ''eigs()'' находить собственные значения на основе данного алгоритма.

Matlab-реализация доступна как часть [http://www.cs.cmu.edu/~bickson/gabp/#download Gaussian Belief Propagation Matlab Package]. [http://www.graphlab.ml.cmu.edu/pmf.html GraphLab] содержит несколько параллельных реализаций алгоритма на C++.

= Литература =

Участник:Error0x0/Алгоритм Ланцоша для арифметики с плавающей точкой с полной переортогонализацией

2017-02-01T18:15:01Z

Error0x0:

{{algorithm
| name = Алгоритм Ланцоша для арифметики с плавающей точкой с полной переортогонализацией
| serial_complexity = <math>O(k^2 n)</math>
| pf_height = <math>O(k \log k \log n)</math>
| pf_width = <math>O(kn)</math>
| input_data = <math>n^2</math>
| output_data = <math>n</math>
}}
Автор описания: [[Участник:Error0x0|В. А. Янушковский]]

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

== Общее описание алгоритма ==
Алгоритм Ланцоша представляет собой итерационный алгоритм для вычисления собственных значений симметрической матрицы.
Идея алгоритма заключается в построении матрицы <math>Q_k = [q_1, ..., q_k]</math> из ортонормированных векторов Ланцоша и использовании собственных значений трёхдиагональной матрицы <math>T_k = Q_k^T A Q_k</math> (чисел Ритца) как приближения к искомым собственным числам матрицы<ref name="Деммель">Деммель Дж. Вычислительная линейная алгебра</ref>.

== Математическое описание алгоритма ==
Пусть дана матрица <math>A</math>.
Пусть <math>q_1 = b/||b||_2, \beta_0=0, q_0=0</math>
Алгоритм производит <math>k</math> итераций на каждой из которых:
# вычисляется <math>z = Aq_j</math>,
# производится переортогонализация <math>z = z - \sum^{j-1}_{i=1} {(z^T q_i)q_i}</math>,
# <math>\beta_j = ||z||_2</math>, если <math>\beta_j = 0</math>, алгоритм останавливается,
# <math>q_{j+1} = z/\beta_j</math>,
# вычисляются собственные значения и векторы матрицы <math>T_j = Q_j^T A Q_j</math>.

== Вычислительное ядро алгоритма ==
Основной вклад в сложность алгоритма даёт полная переортогонализация внутри каждой итерации:

<math>z = z - \sum^{j-1}_{i=1} {(z^T q_i)q_i}</math>

== Макроструктура алгоритма ==
используются следующие макрооперации:
* Нахождение нормы вектора (евклидовой)
* Умножение/деление вектора на число
* Умножение матрицы на вектор (<math>z = Aq_j</math>)
* Скалярное произведение двух векторов
* Вычитание векторов
* Вычисление собственных значений и векторов трёхдиагональной матрицы <math>T_j</math> (числа Ритца, используется метод "разделяй и властвуй")

== Схема реализации последовательного алгоритма ==
<syntaxhighlight lang="python">
beta[0] = 0 # инициализация
q[0] = 0
q[1] = b / norm(b) # вычисление первого столбца
for j in [1 .. k]: # k итераций
z = mul(A, q[j]) # вектор Ланцоша как произведение матрицы A на столбец q[j]
alpha[j] = scalar_mul(q[j], z) # вычисление alpha[j]
for i in [1 .. j - 1]: # полная переортогонализация
z -= scalar_mul(z, q[i]) * q[i]
beta[j] = norm(z) # вычисление нормы z
if beta[j] == 0: # останов, если норма z равна нулю
break
result.append(next_ritz_number(alpha, beta, j)) # вычисление следующего собственного значения и вектора матрицы Tj
return result
</syntaxhighlight>

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

Основной вклад в сложность даёт полная переортогонализация: на каждой из <math>k</math> итераций для всех <math>i \in [0...j-1]</math> выполняется <math>2n</math> умножений и <math>2n</math> сложений, итого <math>\frac{k(k-1)}{2} 4n \approx 2k^2 n</math>.
таким образом, для метода с полной переортогонализацией сложность составляет <math>O(k^2 n)</math>, сложность по памяти -- <math>O(kn)</math>.

== Информационный граф ==
[[File:Lanczos graph.png|thumb|center|640px|Рисунок 1. Информационный граф]]

== Ресурс параллелизма алгоритма ==
Для процесса переортогонализации возможна параллельная оптимизация в двух местах:
* Итерации внутреннего цикла могут вычисляться параллельно, однако, требуется суммирование вычитаемых векторов, соответственно, сложность переортогонализации можно снизить с <math>O(kn)</math> до <math>O(n \log k)</math>
* В каждой итерации внутреннего цикла возможно распараллеливание вычисления выражения справа (скалярное произведение и умножение вектора на число), что теоретически позволяет снизить сложность итерации с <math>O(n)</math> до <math>O(log(n))</math>

== Входные и выходные данные алгоритма ==
'''Входные данны'''е: квадратная симметрическая матрица <math>A</math> порядка <math>n</math>

'''Объём входных данных''': <math>n^2</math>

'''Выходные данные''': собственные числа матрицы

'''Объём выходных данных''': <math>n</math>

== Свойства алгоритма ==
Полная переортогонализация соответствует повторной процедуре ортогонализациии Грама-Шмидта для обеспечения ортогональности вектора <math>z</math> векторам <math>q_1, ..., q_k</math>. В случае идеально точной арифметики данная переортогонализация не требовалась бы, однако в реальных вычислениях ошибки округления приводят к потере ортогональности, в связи с чем требуется переортогонализация.
Однако, единственной проблемой, возникающей при отсутствии переортогонализации, является появление повторных копий чисел Ритца (собственных значений), что в случае, если не требуется установление кратностей собственных значений, допустимо.

Вычислительная мощность алгоритма примерно равна <math>2k^2 / n</math>.

= Программная реализация алгоритма =

== Особенности реализации последовательного алгоритма ==

== [[Локальность данных и вычислений]] ==

== Возможные способы и особенности параллельной реализации алгоритма ==

== Масштабируемость алгоритма и его реализации ==

== Динамические характеристики и эффективность реализации алгоритма ==

== Выводы для классов архитектур ==

== Существующие реализации алгоритма ==
Библиотека [http://www.nag.co.uk/numeric/fl/nagdoc_fl23/html/INDEXES/KWIC/lanczos.html NAG Library] содержит ряд процедур для решения СЛАУ и поиска собственных значений на основе алгоритма Ланцоша.

[http://www.mathworks.com/help/techdoc/ref/eigs.html MATLAB] и [https://www.gnu.org/software/octave/doc/interpreter/Sparse-Linear-Algebra.html#doc_002deigs GNU Octave] позволяют с помощью функции ''eigs()'' находить собственные значения на основе данного алгоритма.

Matlab-реализация доступна как часть [http://www.cs.cmu.edu/~bickson/gabp/#download Gaussian Belief Propagation Matlab Package]. [http://www.graphlab.ml.cmu.edu/pmf.html GraphLab] содержит несколько параллельных реализаций алгоритма на C++.

= Литература =

Участник:Error0x0/Алгоритм Ланцоша для арифметики с плавающей точкой с полной переортогонализацией

2017-02-01T18:05:13Z

Error0x0: /* Свойства алгоритма */

{{algorithm
| name = Алгоритм Ланцоша для арифметики с плавающей точкой с полной переортогонализацией
| serial_complexity = <math>O(k^2 n)</math>
| pf_height = <math>O(k \log k \log n)</math>
| pf_width = <math>O(kn)</math>
| input_data = <math>n^2</math>
| output_data = <math>n</math>
}}
Автор описания: [[Участник:Error0x0|В. А. Янушковский]]

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

== Общее описание алгоритма ==
Алгоритм Ланцоша представляет собой итерационный алгоритм для вычисления собственных значений симметрической матрицы.
Идея алгоритма заключается в построении матрицы <math>Q_k = [q_1, ..., q_k]</math> из ортонормированных векторов Ланцоша и использовании собственных значений трёхдиагональной матрицы <math>T_k = Q_k^T A Q_k</math> (чисел Ритца) как приближения к искомым собственным числам матрицы<ref name="Деммель">Деммель Дж. Вычислительная линейная алгебра</ref>.

== Математическое описание алгоритма ==
Пусть дана матрица <math>A</math>.
Пусть <math>q_1 = b/||b||_2, \beta_0=0, q_0=0</math>
Алгоритм производит <math>k</math> итераций на каждой из которых:
# вычисляется <math>z = Aq_j</math>,
# производится переортогонализация <math>z = z - \sum^{j-1}_{i=1} {(z^T q_i)q_i}</math>,
# <math>\beta_j = ||z||_2</math>, если <math>\beta_j = 0</math>, алгоритм останавливается,
# <math>q_{j+1} = z/\beta_j</math>,
# вычисляются собственные значения и векторы матрицы <math>T_j = Q_j^T A Q_j</math>.

== Вычислительное ядро алгоритма ==
Основной вклад в сложность алгоритма даёт полная переортогонализация внутри каждой итерации:

<math>z = z - \sum^{j-1}_{i=1} {(z^T q_i)q_i}</math>

== Макроструктура алгоритма ==
Основные элементы алгоритма:
* Нахождение векторов Ланцоша
* Полная переортогонализация (Грамма-Шмидта)
* Вычисление собственных значений и векторов матрицы <math>T_j</math> (числа Ритца)

== Схема реализации последовательного алгоритма ==
<syntaxhighlight lang="python">
beta[0] = 0 # инициализация
q[0] = 0
q[1] = b / norm(b) # вычисление первого столбца
for j in [1 .. k]: # k итераций
z = mul(A, q[j]) # вектор Ланцоша как произведение матрицы A на столбец q[j]
alpha[j] = scalar_mul(q[j], z) # вычисление alpha[j]
for i in [1 .. j - 1]: # полная переортогонализация
z -= mul(scalar_mul(z, q[i]), q[i])
beta[j] = norm(z) # вычисление нормы z
if beta[j] == 0: # останов, если норма z равна нулю
break
result.append(next_ritz_number(alpha, beta, j)) # вычисление следующего собственного значения и вектора матрицы Tj
return result
</syntaxhighlight>

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

Основной вклад в сложность даёт полная переортогонализация: на каждой из <math>k</math> итераций для всех <math>i \in [0...j-1]</math> выполняется <math>2n</math> умножений и <math>2n</math> сложений, итого <math>\frac{k(k-1)}{2} 4n \approx 2k^2 n</math>.
таким образом, для метода с полной переортогонализацией сложность составляет <math>O(k^2 n)</math>, сложность по памяти -- <math>O(kn)</math>.

== Информационный граф ==
[[File:Lanczos graph.png|thumb|center|640px|Рисунок 1. Информационный граф]]

== Ресурс параллелизма алгоритма ==
Для процесса переортогонализации возможна параллельная оптимизация в двух местах:
* Итерации внутреннего цикла могут вычисляться параллельно, однако, требуется суммирование вычитаемых векторов, соответственно, сложность переортогонализации можно снизить с <math>O(kn)</math> до <math>O(n \log k)</math>
* В каждой итерации внутреннего цикла возможно распараллеливание вычисления выражения справа (скалярное произведение и умножение вектора на число), что теоретически позволяет снизить сложность итерации с <math>O(n)</math> до <math>O(log(n))</math>

== Входные и выходные данные алгоритма ==
'''Входные данны'''е: квадратная симметрическая матрица <math>A</math> порядка <math>n</math>

'''Объём входных данных''': <math>n^2</math>

'''Выходные данные''': собственные числа матрицы

'''Объём выходных данных''': <math>n</math>

== Свойства алгоритма ==
Полная переортогонализация соответствует повторной процедуре ортогонализациии Грама-Шмидта для обеспечения ортогональности вектора <math>z</math> векторам <math>q_1, ..., q_k</math>. В случае идеально точной арифметики данная переортогонализация не требовалась бы, однако в реальных вычислениях ошибки округления приводят к потере ортогональности, в связи с чем требуется переортогонализация.
Однако, единственной проблемой, возникающей при отсутствии переортогонализации, является появление повторных копий чисел Ритца (собственных значений), что в случае, если не требуется установление кратностей собственных значений, допустимо.

Вычислительная мощность алгоритма примерно равна <math>2k^2 / n</math>.

= Программная реализация алгоритма =

== Особенности реализации последовательного алгоритма ==

== [[Локальность данных и вычислений]] ==

== Возможные способы и особенности параллельной реализации алгоритма ==

== Масштабируемость алгоритма и его реализации ==

== Динамические характеристики и эффективность реализации алгоритма ==

== Выводы для классов архитектур ==

== Существующие реализации алгоритма ==
Библиотека [http://www.nag.co.uk/numeric/fl/nagdoc_fl23/html/INDEXES/KWIC/lanczos.html NAG Library] содержит ряд процедур для решения СЛАУ и поиска собственных значений на основе алгоритма Ланцоша.

[http://www.mathworks.com/help/techdoc/ref/eigs.html MATLAB] и [https://www.gnu.org/software/octave/doc/interpreter/Sparse-Linear-Algebra.html#doc_002deigs GNU Octave] позволяют с помощью функции ''eigs()'' находить собственные значения на основе данного алгоритма.

Matlab-реализация доступна как часть [http://www.cs.cmu.edu/~bickson/gabp/#download Gaussian Belief Propagation Matlab Package]. [http://www.graphlab.ml.cmu.edu/pmf.html GraphLab] содержит несколько параллельных реализаций алгоритма на C++.

= Литература =

Участник:Error0x0/Алгоритм Ланцоша для арифметики с плавающей точкой с полной переортогонализацией

2017-02-01T18:04:44Z

Error0x0:

{{algorithm
| name = Алгоритм Ланцоша для арифметики с плавающей точкой с полной переортогонализацией
| serial_complexity = <math>O(k^2 n)</math>
| pf_height = <math>O(k \log k \log n)</math>
| pf_width = <math>O(kn)</math>
| input_data = <math>n^2</math>
| output_data = <math>n</math>
}}
Автор описания: [[Участник:Error0x0|В. А. Янушковский]]

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

== Общее описание алгоритма ==
Алгоритм Ланцоша представляет собой итерационный алгоритм для вычисления собственных значений симметрической матрицы.
Идея алгоритма заключается в построении матрицы <math>Q_k = [q_1, ..., q_k]</math> из ортонормированных векторов Ланцоша и использовании собственных значений трёхдиагональной матрицы <math>T_k = Q_k^T A Q_k</math> (чисел Ритца) как приближения к искомым собственным числам матрицы<ref name="Деммель">Деммель Дж. Вычислительная линейная алгебра</ref>.

== Математическое описание алгоритма ==
Пусть дана матрица <math>A</math>.
Пусть <math>q_1 = b/||b||_2, \beta_0=0, q_0=0</math>
Алгоритм производит <math>k</math> итераций на каждой из которых:
# вычисляется <math>z = Aq_j</math>,
# производится переортогонализация <math>z = z - \sum^{j-1}_{i=1} {(z^T q_i)q_i}</math>,
# <math>\beta_j = ||z||_2</math>, если <math>\beta_j = 0</math>, алгоритм останавливается,
# <math>q_{j+1} = z/\beta_j</math>,
# вычисляются собственные значения и векторы матрицы <math>T_j = Q_j^T A Q_j</math>.

== Вычислительное ядро алгоритма ==
Основной вклад в сложность алгоритма даёт полная переортогонализация внутри каждой итерации:

<math>z = z - \sum^{j-1}_{i=1} {(z^T q_i)q_i}</math>

== Макроструктура алгоритма ==
Основные элементы алгоритма:
* Нахождение векторов Ланцоша
* Полная переортогонализация (Грамма-Шмидта)
* Вычисление собственных значений и векторов матрицы <math>T_j</math> (числа Ритца)

== Схема реализации последовательного алгоритма ==
<syntaxhighlight lang="python">
beta[0] = 0 # инициализация
q[0] = 0
q[1] = b / norm(b) # вычисление первого столбца
for j in [1 .. k]: # k итераций
z = mul(A, q[j]) # вектор Ланцоша как произведение матрицы A на столбец q[j]
alpha[j] = scalar_mul(q[j], z) # вычисление alpha[j]
for i in [1 .. j - 1]: # полная переортогонализация
z -= mul(scalar_mul(z, q[i]), q[i])
beta[j] = norm(z) # вычисление нормы z
if beta[j] == 0: # останов, если норма z равна нулю
break
result.append(next_ritz_number(alpha, beta, j)) # вычисление следующего собственного значения и вектора матрицы Tj
return result
</syntaxhighlight>

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

Основной вклад в сложность даёт полная переортогонализация: на каждой из <math>k</math> итераций для всех <math>i \in [0...j-1]</math> выполняется <math>2n</math> умножений и <math>2n</math> сложений, итого <math>\frac{k(k-1)}{2} 4n \approx 2k^2 n</math>.
таким образом, для метода с полной переортогонализацией сложность составляет <math>O(k^2 n)</math>, сложность по памяти -- <math>O(kn)</math>.

== Информационный граф ==
[[File:Lanczos graph.png|thumb|center|640px|Рисунок 1. Информационный граф]]

== Ресурс параллелизма алгоритма ==
Для процесса переортогонализации возможна параллельная оптимизация в двух местах:
* Итерации внутреннего цикла могут вычисляться параллельно, однако, требуется суммирование вычитаемых векторов, соответственно, сложность переортогонализации можно снизить с <math>O(kn)</math> до <math>O(n \log k)</math>
* В каждой итерации внутреннего цикла возможно распараллеливание вычисления выражения справа (скалярное произведение и умножение вектора на число), что теоретически позволяет снизить сложность итерации с <math>O(n)</math> до <math>O(log(n))</math>

== Входные и выходные данные алгоритма ==
'''Входные данны'''е: квадратная симметрическая матрица <math>A</math> порядка <math>n</math>

'''Объём входных данных''': <math>n^2</math>

'''Выходные данные''': собственные числа матрицы

'''Объём выходных данных''': <math>n</math>

== Свойства алгоритма ==
Полная переортогонализация соответствует повторной процедуре ортогонализациии Грама-Шмидта для обеспечения ортогональности вектора <math>z</math> векторам <math>q_1, ..., q_k</math>. В случае идеально точной арифметики данная переортогонализация не требовалась бы, однако в реальных вычислениях ошибки округления приводят к потере ортогональности, в связи с чем требуется переортогонализация.
Однако, единственной проблемой, возникающей при отсутствии переортогонализации, является появление повторных копий чисел Ритца (собственных значений), что в случае, если не требуется установление кратностей собственных значений, допустимо.
Вычислительная мощность алгоритма примерно равна <math>2k^2 / n</math>.

Вычислительная мощность данного алгоритма: <math></math>.

= Программная реализация алгоритма =

== Особенности реализации последовательного алгоритма ==

== [[Локальность данных и вычислений]] ==

== Возможные способы и особенности параллельной реализации алгоритма ==

== Масштабируемость алгоритма и его реализации ==

== Динамические характеристики и эффективность реализации алгоритма ==

== Выводы для классов архитектур ==

== Существующие реализации алгоритма ==
Библиотека [http://www.nag.co.uk/numeric/fl/nagdoc_fl23/html/INDEXES/KWIC/lanczos.html NAG Library] содержит ряд процедур для решения СЛАУ и поиска собственных значений на основе алгоритма Ланцоша.

[http://www.mathworks.com/help/techdoc/ref/eigs.html MATLAB] и [https://www.gnu.org/software/octave/doc/interpreter/Sparse-Linear-Algebra.html#doc_002deigs GNU Octave] позволяют с помощью функции ''eigs()'' находить собственные значения на основе данного алгоритма.

Matlab-реализация доступна как часть [http://www.cs.cmu.edu/~bickson/gabp/#download Gaussian Belief Propagation Matlab Package]. [http://www.graphlab.ml.cmu.edu/pmf.html GraphLab] содержит несколько параллельных реализаций алгоритма на C++.

= Литература =

Участник:Error0x0/Алгоритм Ланцоша для арифметики с плавающей точкой с полной переортогонализацией

2017-02-01T15:21:58Z

Error0x0:

{{algorithm
| name = Алгоритм Ланцоша для арифметики с плавающей точкой с полной переортогонализацией
| serial_complexity = <math>O(k^2 n)</math>
| pf_height = <math>O(k \log k \log n)</math>
| pf_width = <math>O(kn)</math>
| input_data = <math>n^2</math>
| output_data = <math>n</math>
}}
Автор описания: [[Участник:Error0x0|В. А. Янушковский]]

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

== Общее описание алгоритма ==
Алгоритм Ланцоша представляет собой итерационный алгоритм для вычисления собственных значений симметрической матрицы.
Идея алгоритма заключается в построении матрицы <math>Q_k = [q_1, ..., q_k]</math> из ортонормированных векторов Ланцоша и использовании собственных значений трёхдиагональной матрицы <math>T_k = Q_k^T A Q_k</math> (чисел Ритца) как приближения к искомым собственным числам матрицы<ref name="Деммель">Деммель Дж. Вычислительная линейная алгебра</ref>.

== Математическое описание алгоритма ==
Пусть дана матрица <math>A</math>.
Пусть <math>q_1 = b/||b||_2, \beta_0=0, q_0=0</math>
Алгоритм производит <math>k</math> итераций на каждой из которых:
# вычисляется <math>z = Aq_j</math>,
# производится переортогонализация <math>z = z - \sum^{j-1}_{i=1} {(z^T q_i)q_i}</math>,
# <math>\beta_j = ||z||_2</math>, если <math>\beta_j = 0</math>, алгоритм останавливается,
# <math>q_{j+1} = z/\beta_j</math>,
# вычисляются собственные значения и векторы матрицы <math>T_j = Q_j^T A Q_j</math>.

== Вычислительное ядро алгоритма ==
Основной вклад в сложность алгоритма даёт полная переортогонализация внутри каждой итерации:

<math>z = z - \sum^{j-1}_{i=1} {(z^T q_i)q_i}</math>

== Макроструктура алгоритма ==
Основные элементы алгоритма:
* Нахождение векторов Ланцоша
* Полная переортогонализация (Грамма-Шмидта)
* Вычисление собственных значений и векторов матрицы <math>T_j</math> (числа Ритца)

== Схема реализации последовательного алгоритма ==
<syntaxhighlight lang="python">
q[1] = b / norm(b)
beta[0] = 0
q[0] = 0
for j in [1 .. k]:
z = mul(A, q[j])
zT = transposed(z)
for i in [1 .. j - 1]:
z -= mul(scalar_mul(zT, q[i]), q[i])
beta[j] = norm(z)
if beta[j] == 0:
break
result = ritz_numbers(mul(transpose(Q[j]), A, Q[j]))
return result
</syntaxhighlight>

== Последовательная сложность алгоритма ==
Для метода с полной переортогонализацией сложность составляет <math>O(k^2 n)</math>, сложность по памяти -- <math>O(kn)</math>.

== Информационный граф ==
[[File:Lanczos graph.png|thumb|center|640px|Рисунок 1. Информационный граф]]

== Ресурс параллелизма алгоритма ==
Для процесса переортогонализации возможна параллельная оптимизация в двух местах:
* Итерации внутреннего цикла могут вычисляться параллельно, однако, требуется суммирование вычитаемых векторов, соответственно, сложность переортогонализации можно снизить с <math>O(kn)</math> до <math>O(n \log k)</math>
* В каждой итерации внутреннего цикла возможно распараллеливание вычисления выражения справа (скалярное произведение и умножение вектора на число), что теоретически позволяет снизить сложность итерации с <math>O(n)</math> до <math>O(log(n))</math>

== Входные и выходные данные алгоритма ==
'''Входные данны'''е: квадратная симметрическая матрица <math>A</math> порядка <math>n</math>

'''Объём входных данных''': <math>n^2</math>

'''Выходные данные''': собственные числа матрицы

'''Объём выходных данных''': <math>n</math>

== Свойства алгоритма ==
Полная переортогонализация соответствует повторной процедуре ортогонализациии Грама-Шмидта для обеспечения ортогональности вектора <math>z</math> векторам <math>q_1, ..., q_k</math>. В случае идеально точной арифметики данная переортогонализация не требовалась бы, однако в реальных вычислениях ошибки округления приводят к потере ортогональности, в связи с чем требуется переортогонализация.
Однако, единственной проблемой, возникающей при отсутствии переортогонализации, является появление повторных копий чисел Ритца (собственных значений), что в случае, если не требуется установление кратностей собственных значений, допустимо.

Вычислительная мощность данного алгоритма: <math></math>.

= Программная реализация алгоритма =

== Особенности реализации последовательного алгоритма ==

== [[Локальность данных и вычислений]] ==

== Возможные способы и особенности параллельной реализации алгоритма ==

== Масштабируемость алгоритма и его реализации ==

== Динамические характеристики и эффективность реализации алгоритма ==

== Выводы для классов архитектур ==

== Существующие реализации алгоритма ==
Библиотека [http://www.nag.co.uk/numeric/fl/nagdoc_fl23/html/INDEXES/KWIC/lanczos.html NAG Library] содержит ряд процедур для решения СЛАУ и поиска собственных значений на основе алгоритма Ланцоша.

[http://www.mathworks.com/help/techdoc/ref/eigs.html MATLAB] и [https://www.gnu.org/software/octave/doc/interpreter/Sparse-Linear-Algebra.html#doc_002deigs GNU Octave] позволяют с помощью функции ''eigs()'' находить собственные значения на основе данного алгоритма.

Matlab-реализация доступна как часть [http://www.cs.cmu.edu/~bickson/gabp/#download Gaussian Belief Propagation Matlab Package]. [http://www.graphlab.ml.cmu.edu/pmf.html GraphLab] содержит несколько параллельных реализаций алгоритма на C++.

= Литература =

Участник:Error0x0/Алгоритм Ланцоша для арифметики с плавающей точкой с полной переортогонализацией

2017-02-01T15:18:41Z

Error0x0:

{{algorithm
| name = Алгоритм Ланцоша для арифметики с плавающей точкой с полной переортогонализацией
| serial_complexity = <math>O(k^2 n)</math>
| pf_height = <math>O(k \log k \log n)</math>
| pf_width = <math>O(kn)</math>
| input_data = <math>n^2</math>
| output_data = <math>n</math>
}}
Автор описания: [[Участник:Error0x0|В. А. Янушковский]]

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

== Общее описание алгоритма ==
Алгоритм Ланцоша представляет собой итерационный алгоритм для вычисления собственных значений симметрической матрицы.
Идея алгоритма заключается в построении матрицы <math>Q_k = [q_1, ..., q_k]</math> из ортонормированных векторов Ланцоша и использовании собственных значений трёхдиагональной матрицы <math>T_k = Q_k^T A Q_k</math> (чисел Ритца) как приближения к искомым собственным числам матрицы<ref name="Деммель">Деммель Дж. Вычислительная линейная алгебра</ref>.

== Математическое описание алгоритма ==
Пусть дана матрица <math>A</math>.
Пусть <math>q_1 = b/||b||_2, \beta_0=0, q_0=0</math>
Алгоритм производит <math>k</math> итераций на каждой из которых:
# вычисляется <math>z = Aq_j</math>,
# производится переортогонализация <math>z = z - \sum^{j-1}_{i=1} {(z^T q_i)q_i}</math>,
# <math>\beta_j = ||z||_2</math>, если <math>\beta_j = 0</math>, алгоритм останавливается,
# <math>q_{j+1} = z/\beta_j</math>,
# вычисляются собственные значения и векторы матрицы <math>T_j = Q_j^T A Q_j</math>.

== Вычислительное ядро алгоритма ==
Основной вклад в сложность алгоритма даёт полная переортогонализация внутри каждой итерации:

<math>z = z - \sum^{j-1}_{i=1} {(z^T q_i)q_i}</math>

== Макроструктура алгоритма ==
Основные элементы алгоритма:
* Нахождение векторов Ланцоша
* Полная переортогонализация (Грамма-Шмидта)
* Вычисление собственных значений и векторов матрицы <math>T_j</math> (числа Ритца)

== Схема реализации последовательного алгоритма ==
<syntaxhighlight lang="python">
q[1] = b / norm(b)
beta[0] = 0
q[0] = 0
for j in [1 .. k]:
z = mul(A, q[j])
zT = transposed(z)
for i in [1 .. j - 1]:
z -= mul(scalar_mul(zT, q[i]), q[i])
beta[j] = norm(z)
if beta[j] == 0:
break
result = ritz_numbers(mul(transpose(Q[j]), A, Q[j]))
return result
</syntaxhighlight>

== Последовательная сложность алгоритма ==
Для метода с полной переортогонализацией сложность составляет <math>O(k^2 n)</math>, сложность по памяти -- <math>O(kn)</math>.

== Информационный граф ==
[[File:Lanczos graph.png|thumb|center|640px|Рисунок 1. Информационный граф]]

== Ресурс параллелизма алгоритма ==
Для процесса переортогонализации возможна параллельная оптимизация в двух местах:
* Итерации внутреннего цикла могут вычисляться параллельно, однако, требуется суммирование вычитаемых векторов, соответственно, сложность переортогонализации можно снизить с <math>O(kn)</math> до <math>O(n \log k)</math>
* В каждой итерации внутреннего цикла возможно распараллеливание вычисления выражения справа (скалярное произведение и умножение вектора на число), что теоретически позволяет снизить сложность итерации с <math>O(n)</math> до <math>O(log(n))</math>

== Входные и выходные данные алгоритма ==
'''Входные данны'''е: квадратная симметрическая матрица <math>A</math> порядка <math>n</math>

'''Объём входных данных''': <math>n^2</math>

'''Выходные данные''': собственные числа матрицы

'''Объём выходных данных''': <math>n</math>

== Свойства алгоритма ==
Полная переортогонализация соответствует повторной процедуре ортогонализациии Грама-Шмидта для обеспечения ортогональности вектора <math>z</math> векторам <math>q_1, ..., q_k</math>. В случае идеально точной арифметики данная переортогонализация не требовалась бы, однако в реальных вычислениях ошибки округления приводят к потере ортогональности, в связи с чем требуется переортогонализация.
Однако, единственной проблемой, возникающей при отсутствии переортогонализации, является появление повторных копий чисел Ритца (собственных значений), что в случае, если не требуется установление кратностей собственных значений, допустимо.

Последовательная сложность данного алгоритма: <math>O(k^2 n)</math>.

= Программная реализация алгоритма =

== Особенности реализации последовательного алгоритма ==

== [[Локальность данных и вычислений]] ==

== Возможные способы и особенности параллельной реализации алгоритма ==

== Масштабируемость алгоритма и его реализации ==

== Динамические характеристики и эффективность реализации алгоритма ==

== Выводы для классов архитектур ==

== Существующие реализации алгоритма ==
Библиотека [http://www.nag.co.uk/numeric/fl/nagdoc_fl23/html/INDEXES/KWIC/lanczos.html NAG Library] содержит ряд процедур для решения СЛАУ и поиска собственных значений на основе алгоритма Ланцоша.

[http://www.mathworks.com/help/techdoc/ref/eigs.html MATLAB] и [https://www.gnu.org/software/octave/doc/interpreter/Sparse-Linear-Algebra.html#doc_002deigs GNU Octave] позволяют с помощью функции ''eigs()'' находить собственные значения на основе данного алгоритма.

Matlab-реализация доступна как часть [http://www.cs.cmu.edu/~bickson/gabp/#download Gaussian Belief Propagation Matlab Package]. [http://www.graphlab.ml.cmu.edu/pmf.html GraphLab] содержит несколько параллельных реализаций алгоритма на C++.

= Литература =

Обсуждение участника:Error0x0

2016-10-31T11:09:57Z

Участник:Error0x0/Алгоритм Ланцоша для арифметики с плавающей точкой с полной переортогонализацией

2016-10-31T11:07:18Z

Error0x0:

{{Assignment}}

{{algorithm
| name = Алгоритм Ланцоша для арифметики с плавающей точкой с полной переортогонализацией
| serial_complexity = <math>O(k^2 n)</math>
| pf_height = <math>O(k \log k \log n)</math>
| pf_width = <math>O(kn)</math>
| input_data = <math>n^2</math>
| output_data = <math>n</math>
}}
Автор описания: [[Участник:Error0x0|В. А. Янушковский]]

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

== Общее описание алгоритма ==
Алгоритм Ланцоша представляет собой итерационный алгоритм для вычисления собственных значений симметрической матрицы.
Идея алгоритма заключается в построении матрицы <math>Q_k = [q_1, ..., q_k]</math> из ортонормированных векторов Ланцоша и использовании собственных значений трёхдиагональной матрицы <math>T_k = Q_k^T A Q_k</math> (чисел Ритца) как приближения к искомым собственным числам матрицы<ref name="Деммель">Деммель Дж. Вычислительная линейная алгебра</ref>.

== Математическое описание алгоритма ==
Пусть дана матрица <math>A</math>.
Пусть <math>q_1 = b/||b||_2, \beta_0=0, q_0=0</math>
Алгоритм производит <math>k</math> итераций на каждой из которых:
# вычисляется <math>z = Aq_j</math>,
# производится переортогонализация <math>z = z - \sum^{j-1}_{i=1} {(z^T q_i)q_i}</math>,
# <math>\beta_j = ||z||_2</math>, если <math>\beta_j = 0</math>, алгоритм останавливается,
# <math>q_{j+1} = z/\beta_j</math>,
# вычисляются собственные значения и векторы матрицы <math>T_j = Q_j^T A Q_j</math>.

== Вычислительное ядро алгоритма ==
Основной вклад в сложность алгоритма даёт полная переортогонализация внутри каждой итерации:

<math>z = z - \sum^{j-1}_{i=1} {(z^T q_i)q_i}</math>

== Макроструктура алгоритма ==
Основные элементы алгоритма:
* Нахождение векторов Ланцоша
* Полная переортогонализация (Грамма-Шмидта)
* Вычисление собственных значений и векторов матрицы <math>T_j</math> (числа Ритца)

== Схема реализации последовательного алгоритма ==
<syntaxhighlight lang="python">
q[1] = b / norm(b)
beta[0] = 0
q[0] = 0
for j in [1 .. k]:
z = mul(A, q[j])
zT = transposed(z)
for i in [1 .. j - 1]:
z -= mul(scalar_mul(zT, q[i]), q[i])
beta[j] = norm(z)
if beta[j] == 0:
break
result = ritz_numbers(mul(transpose(Q[j]), A, Q[j]))
return result
</syntaxhighlight>

== Последовательная сложность алгоритма ==
Для метода с полной переортогонализацией сложность составляет <math>O(k^2 n)</math>, сложность по памяти -- <math>O(kn)</math>.

== Информационный граф ==
[[File:Lanczos graph.png|thumb|center|640px|Рисунок 1. Информационный граф]]

== Ресурс параллелизма алгоритма ==
Для процесса переортогонализации возможна параллельная оптимизация в двух местах:
* Итерации внутреннего цикла могут вычисляться параллельно, однако, требуется суммирование вычитаемых векторов, соответственно, сложность переортогонализации можно снизить с <math>O(kn)</math> до <math>O(n \log k)</math>
* В каждой итерации внутреннего цикла возможно распараллеливание вычисления выражения справа (скалярное произведение и умножение вектора на число), что теоретически позволяет снизить сложность итерации с <math>O(n)</math> до <math>O(log(n))</math>

== Входные и выходные данные алгоритма ==
'''Входные данны'''е: квадратная симметрическая матрица <math>A</math> порядка <math>n</math>

'''Объём входных данных''': <math>n^2</math>

'''Выходные данные''': собственные числа матрицы

'''Объём выходных данных''': <math>n</math>

== Свойства алгоритма ==
Полная переортогонализация соответствует повторной процедуре ортогонализациии Грама-Шмидта для обеспечения ортогональности вектора <math>z</math> векторам <math>q_1, ..., q_k</math>. В случае идеально точной арифметики данная переортогонализация не требовалась бы, однако в реальных вычислениях ошибки округления приводят к потере ортогональности, в связи с чем требуется переортогонализация.
Однако, единственной проблемой, возникающей при отсутствии переортогонализации, является появление повторных копий чисел Ритца (собственных значений), что в случае, если не требуется установление кратностей собственных значений, допустимо.

= Программная реализация алгоритма =

== Особенности реализации последовательного алгоритма ==

== [[Локальность данных и вычислений]] ==

== Возможные способы и особенности параллельной реализации алгоритма ==

== Масштабируемость алгоритма и его реализации ==

== Динамические характеристики и эффективность реализации алгоритма ==

== Выводы для классов архитектур ==

== Существующие реализации алгоритма ==
Библиотека [http://www.nag.co.uk/numeric/fl/nagdoc_fl23/html/INDEXES/KWIC/lanczos.html NAG Library] содержит ряд процедур для решения СЛАУ и поиска собственных значений на основе алгоритма Ланцоша.

[http://www.mathworks.com/help/techdoc/ref/eigs.html MATLAB] и [https://www.gnu.org/software/octave/doc/interpreter/Sparse-Linear-Algebra.html#doc_002deigs GNU Octave] позволяют с помощью функции ''eigs()'' находить собственные значения на основе данного алгоритма.

Matlab-реализация доступна как часть [http://www.cs.cmu.edu/~bickson/gabp/#download Gaussian Belief Propagation Matlab Package]. [http://www.graphlab.ml.cmu.edu/pmf.html GraphLab] содержит несколько параллельных реализаций алгоритма на C++.

= Литература =

Участник:Error0x0/Алгоритм Ланцоша для арифметики с плавающей точкой с полной переортогонализацией

2016-10-31T11:05:22Z

Error0x0:

{{algorithm
| name = Алгоритм Ланцоша для арифметики с плавающей точкой с полной переортогонализацией
| serial_complexity = <math>O(k^2 n)</math>
| pf_height = <math>O(k \log k \log n)</math>
| pf_width = <math>O(kn)</math>
| input_data = <math>n^2</math>
| output_data = <math>n</math>
}}
Автор описания: [[Участник:Error0x0|В. А. Янушковский]]

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

== Общее описание алгоритма ==
Алгоритм Ланцоша представляет собой итерационный алгоритм для вычисления собственных значений симметрической матрицы.
Идея алгоритма заключается в построении матрицы <math>Q_k = [q_1, ..., q_k]</math> из ортонормированных векторов Ланцоша и использовании собственных значений трёхдиагональной матрицы <math>T_k = Q_k^T A Q_k</math> (чисел Ритца) как приближения к искомым собственным числам матрицы<ref name="Деммель">Деммель Дж. Вычислительная линейная алгебра</ref>.

== Математическое описание алгоритма ==
Пусть дана матрица <math>A</math>.
Пусть <math>q_1 = b/||b||_2, \beta_0=0, q_0=0</math>
Алгоритм производит <math>k</math> итераций на каждой из которых:
# вычисляется <math>z = Aq_j</math>,
# производится переортогонализация <math>z = z - \sum^{j-1}_{i=1} {(z^T q_i)q_i}</math>,
# <math>\beta_j = ||z||_2</math>, если <math>\beta_j = 0</math>, алгоритм останавливается,
# <math>q_{j+1} = z/\beta_j</math>,
# вычисляются собственные значения и векторы матрицы <math>T_j = Q_j^T A Q_j</math>.

== Вычислительное ядро алгоритма ==
Основной вклад в сложность алгоритма даёт полная переортогонализация внутри каждой итерации:

<math>z = z - \sum^{j-1}_{i=1} {(z^T q_i)q_i}</math>

== Макроструктура алгоритма ==
Основные элементы алгоритма:
* Нахождение векторов Ланцоша
* Полная переортогонализация (Грамма-Шмидта)
* Вычисление собственных значений и векторов матрицы <math>T_j</math> (числа Ритца)

== Схема реализации последовательного алгоритма ==
<syntaxhighlight lang="python">
q[1] = b / norm(b)
beta[0] = 0
q[0] = 0
for j in [1 .. k]:
z = mul(A, q[j])
zT = transposed(z)
for i in [1 .. j - 1]:
z -= mul(scalar_mul(zT, q[i]), q[i])
beta[j] = norm(z)
if beta[j] == 0:
break
result = ritz_numbers(mul(transpose(Q[j]), A, Q[j]))
return result
</syntaxhighlight>

== Последовательная сложность алгоритма ==
Для метода с полной переортогонализацией сложность составляет <math>O(k^2 n)</math>, сложность по памяти -- <math>O(kn)</math>.

== Информационный граф ==
[[File:Lanczos graph.png|thumb|center|640px|Рисунок 1. Информационный граф]]

== Ресурс параллелизма алгоритма ==
Для процесса переортогонализации возможна параллельная оптимизация в двух местах:
* Итерации внутреннего цикла могут вычисляться параллельно, однако, требуется суммирование вычитаемых векторов, соответственно, сложность переортогонализации можно снизить с <math>O(kn)</math> до <math>O(n \log k)</math>
* В каждой итерации внутреннего цикла возможно распараллеливание вычисления выражения справа (скалярное произведение и умножение вектора на число), что теоретически позволяет снизить сложность итерации с <math>O(n)</math> до <math>O(log(n))</math>

== Входные и выходные данные алгоритма ==
'''Входные данны'''е: квадратная симметрическая матрица <math>A</math> порядка <math>n</math>

'''Объём входных данных''': <math>n^2</math>

'''Выходные данные''': собственные числа матрицы

'''Объём выходных данных''': <math>n</math>

== Свойства алгоритма ==
Полная переортогонализация соответствует повторной процедуре ортогонализациии Грама-Шмидта для обеспечения ортогональности вектора <math>z</math> векторам <math>q_1, ..., q_k</math>. В случае идеально точной арифметики данная переортогонализация не требовалась бы, однако в реальных вычислениях ошибки округления приводят к потере ортогональности, в связи с чем требуется переортогонализация.
Однако, единственной проблемой, возникающей при отсутствии переортогонализации, является появление повторных копий чисел Ритца (собственных значений), что в случае, если не требуется установление кратностей собственных значений, допустимо.

= Программная реализация алгоритма =

== Особенности реализации последовательного алгоритма ==

== [[Локальность данных и вычислений]] ==

== Возможные способы и особенности параллельной реализации алгоритма ==

== Масштабируемость алгоритма и его реализации ==

== Динамические характеристики и эффективность реализации алгоритма ==

== Выводы для классов архитектур ==

== Существующие реализации алгоритма ==
Библиотека [http://www.nag.co.uk/numeric/fl/nagdoc_fl23/html/INDEXES/KWIC/lanczos.html NAG Library] содержит ряд процедур для решения СЛАУ и поиска собственных значений на основе алгоритма Ланцоша.

[http://www.mathworks.com/help/techdoc/ref/eigs.html MATLAB] и [https://www.gnu.org/software/octave/doc/interpreter/Sparse-Linear-Algebra.html#doc_002deigs GNU Octave] позволяют с помощью функции ''eigs()'' находить собственные значения на основе данного алгоритма.

Matlab-реализация доступна как часть [http://www.cs.cmu.edu/~bickson/gabp/#download Gaussian Belief Propagation Matlab Package]. [http://www.graphlab.ml.cmu.edu/pmf.html GraphLab] содержит несколько параллельных реализаций алгоритма на C++.

= Литература =

Участник:Error0x0/Алгоритм Ланцоша для арифметики с плавающей точкой с полной переортогонализацией

2016-10-15T20:48:03Z

Error0x0: /* ЧАСТЬ. Программная реализация алгоритма */

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

== Общее описание алгоритма ==
Алгоритм Ланцоша представляет собой итерационный алгоритм для вычисления собственных значений симметрической матрицы.
Идея алгоритма заключается в построении матрицы <math>Q_k = [q_1, ..., q_k]</math> из ортонормированных векторов Ланцоша и использовании собственных значений трёхдиагональной матрицы <math>T_k = Q_k^T A Q_k</math> (чисел Ритца) как приближения к искомым собственным числам матрицы<ref name="Деммель">Деммель Дж. Вычислительная линейная алгебра</ref>.

== Математическое описание алгоритма ==
Пусть дана матрица <math>A</math>.
Пусть <math>q_1 = b/||b||_2, \beta_0=0, q_0=0</math>
Алгоритм производит <math>k</math> итераций на каждой из которых:
# вычисляется <math>z = Aq_j</math>,
# производится переортогонализация <math>z = z - \sum^{j-1}_{i=1} {(z^T q_i)q_i}</math>,
# <math>\beta_j = ||z||_2</math>, если <math>\beta_j = 0</math>, алгоритм останавливается,
# <math>q_{j+1} = z/\beta_j</math>,
# вычисляются собственные значения и векторы матрицы <math>T_j = Q_j^T A Q_j</math>.

== Вычислительное ядро алгоритма ==
Основной вклад в сложность алгоритма даёт полная переортогонализация.

== Макроструктура алгоритма ==
Основные элементы алгоритма:
* Нахождение векторов Ланцоша
* Полная переортогонализация (Грамма-Шмидта)
* Вычисление собственных значений и векторов матрицы <math>T_j</math> (числа Ритца)

== Схема реализации последовательного алгоритма ==
<syntaxhighlight lang="python">
q[1] = b / norm(b)
beta[0] = 0
q[0] = 0
for j in [1 .. k]:
z = mul(A, q[j])
zT = transposed(z)
for i in [1 .. j - 1]:
z -= mul(scalar_mul(zT, q[i]), q[i])
beta[j] = norm(z)
if beta[j] == 0:
break
result = ritz_numbers(mul(transpose(Q[j]), A, Q[j]))
return result
</syntaxhighlight>

== Последовательная сложность алгоритма ==
Для метода с полной переортогонализацией сложность составляет <math>O(k^2 n)</math>, сложность по памяти -- <math>O(kn)</math>.

== Информационный граф ==
[[File:Lanczos graph.png|thumb|center|640px|Рисунок 1. Информационный граф]]

== Ресурс параллелизма алгоритма ==
Для процесса переортогонализации возможна параллельная оптимизация в двух местах:
* Итерации внутреннего цикла могут вычисляться параллельно, однако, требуется суммирование вычитаемых векторов, соответственно, сложность переортогонализации можно снизить с <math>O(kn)</math> до <math>O(n \log k)</math>
* В каждой итерации внутреннего цикла возможно распараллеливание вычисления выражения справа (скалярное произведение и умножение вектора на число), что теоретически позволяет снизить сложность итерации с <math>O(n)</math> до <math>O(log(n))</math>

== Входные и выходные данные алгоритма ==
'''Входные данны'''е: квадратная симметрическая матрица <math>A</math> порядка <math>n</math>

'''Объём входных данных''': <math>n^2</math>

'''Выходные данные''': собственные числа матрицы

'''Объём выходных данных''': <math>n</math>

== Свойства алгоритма ==
Полная переортогонализация соответствует повторной процедуре ортогонализациии Грама-Шмидта для обеспечения ортогональности вектора <math>z</math> векторам <math>q_1, ..., q_k</math>. В случае идеально точной арифметики данная переортогонализация не требовалась бы, однако в реальных вычислениях ошибки округления приводят к потере ортогональности, в связи с чем требуется переортогонализация.
Однако, единственной проблемой, возникающей при отсутствии переортогонализации, является появление повторных копий чисел Ритца (собственных значений), что в случае, если не требуется установление кратностей собственных значений, допустимо.

= Программная реализация алгоритма =

== Особенности реализации последовательного алгоритма ==

== [[Локальность данных и вычислений]] ==

== Возможные способы и особенности параллельной реализации алгоритма ==

== Масштабируемость алгоритма и его реализации ==

== Динамические характеристики и эффективность реализации алгоритма ==

== Выводы для классов архитектур ==

== Существующие реализации алгоритма ==
Библиотека [http://www.nag.co.uk/numeric/fl/nagdoc_fl23/html/INDEXES/KWIC/lanczos.html NAG Library] содержит ряд процедур для решения СЛАУ и поиска собственных значений на основе алгоритма Ланцоша.

[http://www.mathworks.com/help/techdoc/ref/eigs.html MATLAB] и [https://www.gnu.org/software/octave/doc/interpreter/Sparse-Linear-Algebra.html#doc_002deigs GNU Octave] позволяют с помощью функции ''eigs()'' находить собственные значения на основе данного алгоритма.

Matlab-реализация доступна как часть [http://www.cs.cmu.edu/~bickson/gabp/#download Gaussian Belief Propagation Matlab Package]. [http://www.graphlab.ml.cmu.edu/pmf.html GraphLab] содержит несколько параллельных реализаций алгоритма на C++.

= Литература =

Участник:Error0x0/Алгоритм Ланцоша для арифметики с плавающей точкой с полной переортогонализацией

2016-10-15T20:47:47Z

Error0x0: /* ЧАСТЬ. Свойства и структура алгоритмов */

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

== Общее описание алгоритма ==
Алгоритм Ланцоша представляет собой итерационный алгоритм для вычисления собственных значений симметрической матрицы.
Идея алгоритма заключается в построении матрицы <math>Q_k = [q_1, ..., q_k]</math> из ортонормированных векторов Ланцоша и использовании собственных значений трёхдиагональной матрицы <math>T_k = Q_k^T A Q_k</math> (чисел Ритца) как приближения к искомым собственным числам матрицы<ref name="Деммель">Деммель Дж. Вычислительная линейная алгебра</ref>.

== Математическое описание алгоритма ==
Пусть дана матрица <math>A</math>.
Пусть <math>q_1 = b/||b||_2, \beta_0=0, q_0=0</math>
Алгоритм производит <math>k</math> итераций на каждой из которых:
# вычисляется <math>z = Aq_j</math>,
# производится переортогонализация <math>z = z - \sum^{j-1}_{i=1} {(z^T q_i)q_i}</math>,
# <math>\beta_j = ||z||_2</math>, если <math>\beta_j = 0</math>, алгоритм останавливается,
# <math>q_{j+1} = z/\beta_j</math>,
# вычисляются собственные значения и векторы матрицы <math>T_j = Q_j^T A Q_j</math>.

== Вычислительное ядро алгоритма ==
Основной вклад в сложность алгоритма даёт полная переортогонализация.

== Макроструктура алгоритма ==
Основные элементы алгоритма:
* Нахождение векторов Ланцоша
* Полная переортогонализация (Грамма-Шмидта)
* Вычисление собственных значений и векторов матрицы <math>T_j</math> (числа Ритца)

== Схема реализации последовательного алгоритма ==
<syntaxhighlight lang="python">
q[1] = b / norm(b)
beta[0] = 0
q[0] = 0
for j in [1 .. k]:
z = mul(A, q[j])
zT = transposed(z)
for i in [1 .. j - 1]:
z -= mul(scalar_mul(zT, q[i]), q[i])
beta[j] = norm(z)
if beta[j] == 0:
break
result = ritz_numbers(mul(transpose(Q[j]), A, Q[j]))
return result
</syntaxhighlight>

== Последовательная сложность алгоритма ==
Для метода с полной переортогонализацией сложность составляет <math>O(k^2 n)</math>, сложность по памяти -- <math>O(kn)</math>.

== Информационный граф ==
[[File:Lanczos graph.png|thumb|center|640px|Рисунок 1. Информационный граф]]

== Ресурс параллелизма алгоритма ==
Для процесса переортогонализации возможна параллельная оптимизация в двух местах:
* Итерации внутреннего цикла могут вычисляться параллельно, однако, требуется суммирование вычитаемых векторов, соответственно, сложность переортогонализации можно снизить с <math>O(kn)</math> до <math>O(n \log k)</math>
* В каждой итерации внутреннего цикла возможно распараллеливание вычисления выражения справа (скалярное произведение и умножение вектора на число), что теоретически позволяет снизить сложность итерации с <math>O(n)</math> до <math>O(log(n))</math>

== Входные и выходные данные алгоритма ==
'''Входные данны'''е: квадратная симметрическая матрица <math>A</math> порядка <math>n</math>

'''Объём входных данных''': <math>n^2</math>

'''Выходные данные''': собственные числа матрицы

'''Объём выходных данных''': <math>n</math>

== Свойства алгоритма ==
Полная переортогонализация соответствует повторной процедуре ортогонализациии Грама-Шмидта для обеспечения ортогональности вектора <math>z</math> векторам <math>q_1, ..., q_k</math>. В случае идеально точной арифметики данная переортогонализация не требовалась бы, однако в реальных вычислениях ошибки округления приводят к потере ортогональности, в связи с чем требуется переортогонализация.
Однако, единственной проблемой, возникающей при отсутствии переортогонализации, является появление повторных копий чисел Ритца (собственных значений), что в случае, если не требуется установление кратностей собственных значений, допустимо.

= ЧАСТЬ. Программная реализация алгоритма =

== Особенности реализации последовательного алгоритма ==

== [[Локальность данных и вычислений]] ==

== Возможные способы и особенности параллельной реализации алгоритма ==

== Масштабируемость алгоритма и его реализации ==

== Динамические характеристики и эффективность реализации алгоритма ==

== Выводы для классов архитектур ==

== Существующие реализации алгоритма ==
Библиотека [http://www.nag.co.uk/numeric/fl/nagdoc_fl23/html/INDEXES/KWIC/lanczos.html NAG Library] содержит ряд процедур для решения СЛАУ и поиска собственных значений на основе алгоритма Ланцоша.

[http://www.mathworks.com/help/techdoc/ref/eigs.html MATLAB] и [https://www.gnu.org/software/octave/doc/interpreter/Sparse-Linear-Algebra.html#doc_002deigs GNU Octave] позволяют с помощью функции ''eigs()'' находить собственные значения на основе данного алгоритма.

Matlab-реализация доступна как часть [http://www.cs.cmu.edu/~bickson/gabp/#download Gaussian Belief Propagation Matlab Package]. [http://www.graphlab.ml.cmu.edu/pmf.html GraphLab] содержит несколько параллельных реализаций алгоритма на C++.

= Литература =

Участник:Error0x0/Алгоритм Ланцоша для арифметики с плавающей точкой с полной переортогонализацией

2016-10-15T20:47:06Z

Error0x0: /* Литература */

= ЧАСТЬ. Свойства и структура алгоритмов =

== Общее описание алгоритма ==
Алгоритм Ланцоша представляет собой итерационный алгоритм для вычисления собственных значений симметрической матрицы.
Идея алгоритма заключается в построении матрицы <math>Q_k = [q_1, ..., q_k]</math> из ортонормированных векторов Ланцоша и использовании собственных значений трёхдиагональной матрицы <math>T_k = Q_k^T A Q_k</math> (чисел Ритца) как приближения к искомым собственным числам матрицы<ref name="Деммель">Деммель Дж. Вычислительная линейная алгебра</ref>.

== Математическое описание алгоритма ==
Пусть дана матрица <math>A</math>.
Пусть <math>q_1 = b/||b||_2, \beta_0=0, q_0=0</math>
Алгоритм производит <math>k</math> итераций на каждой из которых:
# вычисляется <math>z = Aq_j</math>,
# производится переортогонализация <math>z = z - \sum^{j-1}_{i=1} {(z^T q_i)q_i}</math>,
# <math>\beta_j = ||z||_2</math>, если <math>\beta_j = 0</math>, алгоритм останавливается,
# <math>q_{j+1} = z/\beta_j</math>,
# вычисляются собственные значения и векторы матрицы <math>T_j = Q_j^T A Q_j</math>.

== Вычислительное ядро алгоритма ==
Основной вклад в сложность алгоритма даёт полная переортогонализация.

== Макроструктура алгоритма ==
Основные элементы алгоритма:
* Нахождение векторов Ланцоша
* Полная переортогонализация (Грамма-Шмидта)
* Вычисление собственных значений и векторов матрицы <math>T_j</math> (числа Ритца)

== Схема реализации последовательного алгоритма ==
<syntaxhighlight lang="python">
q[1] = b / norm(b)
beta[0] = 0
q[0] = 0
for j in [1 .. k]:
z = mul(A, q[j])
zT = transposed(z)
for i in [1 .. j - 1]:
z -= mul(scalar_mul(zT, q[i]), q[i])
beta[j] = norm(z)
if beta[j] == 0:
break
result = ritz_numbers(mul(transpose(Q[j]), A, Q[j]))
return result
</syntaxhighlight>

== Последовательная сложность алгоритма ==
Для метода с полной переортогонализацией сложность составляет <math>O(k^2 n)</math>, сложность по памяти -- <math>O(kn)</math>.

== Информационный граф ==
[[File:Lanczos graph.png|thumb|center|640px|Рисунок 1. Информационный граф]]

== Ресурс параллелизма алгоритма ==
Для процесса переортогонализации возможна параллельная оптимизация в двух местах:
* Итерации внутреннего цикла могут вычисляться параллельно, однако, требуется суммирование вычитаемых векторов, соответственно, сложность переортогонализации можно снизить с <math>O(kn)</math> до <math>O(n \log k)</math>
* В каждой итерации внутреннего цикла возможно распараллеливание вычисления выражения справа (скалярное произведение и умножение вектора на число), что теоретически позволяет снизить сложность итерации с <math>O(n)</math> до <math>O(log(n))</math>

== Входные и выходные данные алгоритма ==
'''Входные данны'''е: квадратная симметрическая матрица <math>A</math> порядка <math>n</math>

'''Объём входных данных''': <math>n^2</math>

'''Выходные данные''': собственные числа матрицы

'''Объём выходных данных''': <math>n</math>

== Свойства алгоритма ==
Полная переортогонализация соответствует повторной процедуре ортогонализациии Грама-Шмидта для обеспечения ортогональности вектора <math>z</math> векторам <math>q_1, ..., q_k</math>. В случае идеально точной арифметики данная переортогонализация не требовалась бы, однако в реальных вычислениях ошибки округления приводят к потере ортогональности, в связи с чем требуется переортогонализация.
Однако, единственной проблемой, возникающей при отсутствии переортогонализации, является появление повторных копий чисел Ритца (собственных значений), что в случае, если не требуется установление кратностей собственных значений, допустимо.

= ЧАСТЬ. Программная реализация алгоритма =

== Особенности реализации последовательного алгоритма ==

== [[Локальность данных и вычислений]] ==

== Возможные способы и особенности параллельной реализации алгоритма ==

== Масштабируемость алгоритма и его реализации ==

== Динамические характеристики и эффективность реализации алгоритма ==

== Выводы для классов архитектур ==

== Существующие реализации алгоритма ==
Библиотека [http://www.nag.co.uk/numeric/fl/nagdoc_fl23/html/INDEXES/KWIC/lanczos.html NAG Library] содержит ряд процедур для решения СЛАУ и поиска собственных значений на основе алгоритма Ланцоша.

[http://www.mathworks.com/help/techdoc/ref/eigs.html MATLAB] и [https://www.gnu.org/software/octave/doc/interpreter/Sparse-Linear-Algebra.html#doc_002deigs GNU Octave] позволяют с помощью функции ''eigs()'' находить собственные значения на основе данного алгоритма.

Matlab-реализация доступна как часть [http://www.cs.cmu.edu/~bickson/gabp/#download Gaussian Belief Propagation Matlab Package]. [http://www.graphlab.ml.cmu.edu/pmf.html GraphLab] содержит несколько параллельных реализаций алгоритма на C++.

= Литература =

Участник:Error0x0/Алгоритм Ланцоша для арифметики с плавающей точкой с полной переортогонализацией

2016-10-15T20:46:52Z

Error0x0: /* Общее описание алгоритма */

Участник:Error0x0/Алгоритм Ланцоша для арифметики с плавающей точкой с полной переортогонализацией

2016-10-15T20:42:59Z

Error0x0: /* Вычислительное ядро алгоритма */

= ЧАСТЬ. Свойства и структура алгоритмов =

== Общее описание алгоритма ==
Алгоритм Ланцоша представляет собой итерационный алгоритм для вычисления собственных значений симметрической матрицы.
Идея алгоритма заключается в построении матрицы <math>Q_k = [q_1, ..., q_k]</math> из ортонормированных векторов Ланцоша и использовании собственных значений трёхдиагональной матрицы <math>T_k = Q_k^T A Q_k</math> (чисел Ритца) как приближения к искомым собственным числам матрицы.

== Математическое описание алгоритма ==
Пусть дана матрица <math>A</math>.
Пусть <math>q_1 = b/||b||_2, \beta_0=0, q_0=0</math>
Алгоритм производит <math>k</math> итераций на каждой из которых:
# вычисляется <math>z = Aq_j</math>,
# производится переортогонализация <math>z = z - \sum^{j-1}_{i=1} {(z^T q_i)q_i}</math>,
# <math>\beta_j = ||z||_2</math>, если <math>\beta_j = 0</math>, алгоритм останавливается,
# <math>q_{j+1} = z/\beta_j</math>,
# вычисляются собственные значения и векторы матрицы <math>T_j = Q_j^T A Q_j</math>.

== Вычислительное ядро алгоритма ==
Основной вклад в сложность алгоритма даёт полная переортогонализация.

== Макроструктура алгоритма ==
Основные элементы алгоритма:
* Нахождение векторов Ланцоша
* Полная переортогонализация (Грамма-Шмидта)
* Вычисление собственных значений и векторов матрицы <math>T_j</math> (числа Ритца)

== Схема реализации последовательного алгоритма ==
<syntaxhighlight lang="python">
q[1] = b / norm(b)
beta[0] = 0
q[0] = 0
for j in [1 .. k]:
z = mul(A, q[j])
zT = transposed(z)
for i in [1 .. j - 1]:
z -= mul(scalar_mul(zT, q[i]), q[i])
beta[j] = norm(z)
if beta[j] == 0:
break
result = ritz_numbers(mul(transpose(Q[j]), A, Q[j]))
return result
</syntaxhighlight>

== Последовательная сложность алгоритма ==
Для метода с полной переортогонализацией сложность составляет <math>O(k^2 n)</math>, сложность по памяти -- <math>O(kn)</math>.

== Информационный граф ==
[[File:Lanczos graph.png|thumb|center|640px|Рисунок 1. Информационный граф]]

== Ресурс параллелизма алгоритма ==
Для процесса переортогонализации возможна параллельная оптимизация в двух местах:
* Итерации внутреннего цикла могут вычисляться параллельно, однако, требуется суммирование вычитаемых векторов, соответственно, сложность переортогонализации можно снизить с <math>O(kn)</math> до <math>O(n \log k)</math>
* В каждой итерации внутреннего цикла возможно распараллеливание вычисления выражения справа (скалярное произведение и умножение вектора на число), что теоретически позволяет снизить сложность итерации с <math>O(n)</math> до <math>O(log(n))</math>

== Входные и выходные данные алгоритма ==
'''Входные данны'''е: квадратная симметрическая матрица <math>A</math> порядка <math>n</math>

'''Объём входных данных''': <math>n^2</math>

'''Выходные данные''': собственные числа матрицы

'''Объём выходных данных''': <math>n</math>

== Свойства алгоритма ==
Полная переортогонализация соответствует повторной процедуре ортогонализациии Грама-Шмидта для обеспечения ортогональности вектора <math>z</math> векторам <math>q_1, ..., q_k</math>. В случае идеально точной арифметики данная переортогонализация не требовалась бы, однако в реальных вычислениях ошибки округления приводят к потере ортогональности, в связи с чем требуется переортогонализация.
Однако, единственной проблемой, возникающей при отсутствии переортогонализации, является появление повторных копий чисел Ритца (собственных значений), что в случае, если не требуется установление кратностей собственных значений, допустимо.

= ЧАСТЬ. Программная реализация алгоритма =

== Особенности реализации последовательного алгоритма ==

== [[Локальность данных и вычислений]] ==

== Возможные способы и особенности параллельной реализации алгоритма ==

== Масштабируемость алгоритма и его реализации ==

== Динамические характеристики и эффективность реализации алгоритма ==

== Выводы для классов архитектур ==

== Существующие реализации алгоритма ==
Библиотека [http://www.nag.co.uk/numeric/fl/nagdoc_fl23/html/INDEXES/KWIC/lanczos.html NAG Library] содержит ряд процедур для решения СЛАУ и поиска собственных значений на основе алгоритма Ланцоша.

[http://www.mathworks.com/help/techdoc/ref/eigs.html MATLAB] и [https://www.gnu.org/software/octave/doc/interpreter/Sparse-Linear-Algebra.html#doc_002deigs GNU Octave] позволяют с помощью функции ''eigs()'' находить собственные значения на основе данного алгоритма.

Matlab-реализация доступна как часть [http://www.cs.cmu.edu/~bickson/gabp/#download Gaussian Belief Propagation Matlab Package]. [http://www.graphlab.ml.cmu.edu/pmf.html GraphLab] содержит несколько параллельных реализаций алгоритма на C++.

= Литература =
[1] Дж. Деммель «Вычислительная линейная алгебра»

Участник:Error0x0/Алгоритм Ланцоша для арифметики с плавающей точкой с полной переортогонализацией

2016-10-15T20:41:12Z

Error0x0: /* Информационный граф */

= ЧАСТЬ. Свойства и структура алгоритмов =

== Общее описание алгоритма ==
Алгоритм Ланцоша представляет собой итерационный алгоритм для вычисления собственных значений симметрической матрицы.
Идея алгоритма заключается в построении матрицы <math>Q_k = [q_1, ..., q_k]</math> из ортонормированных векторов Ланцоша и использовании собственных значений трёхдиагональной матрицы <math>T_k = Q_k^T A Q_k</math> (чисел Ритца) как приближения к искомым собственным числам матрицы.

== Математическое описание алгоритма ==
Пусть дана матрица <math>A</math>.
Пусть <math>q_1 = b/||b||_2, \beta_0=0, q_0=0</math>
Алгоритм производит <math>k</math> итераций на каждой из которых:
# вычисляется <math>z = Aq_j</math>,
# производится переортогонализация <math>z = z - \sum^{j-1}_{i=1} {(z^T q_i)q_i}</math>,
# <math>\beta_j = ||z||_2</math>, если <math>\beta_j = 0</math>, алгоритм останавливается,
# <math>q_{j+1} = z/\beta_j</math>,
# вычисляются собственные значения и векторы матрицы <math>T_j = Q_j^T A Q_j</math>.

== Вычислительное ядро алгоритма ==
Основной вклад в сложность алгоритма даёт полная переортогонализация

== Макроструктура алгоритма ==
Основные элементы алгоритма:
* Нахождение векторов Ланцоша
* Полная переортогонализация (Грамма-Шмидта)
* Вычисление собственных значений и векторов матрицы <math>T_j</math> (числа Ритца)

== Схема реализации последовательного алгоритма ==
<syntaxhighlight lang="python">
q[1] = b / norm(b)
beta[0] = 0
q[0] = 0
for j in [1 .. k]:
z = mul(A, q[j])
zT = transposed(z)
for i in [1 .. j - 1]:
z -= mul(scalar_mul(zT, q[i]), q[i])
beta[j] = norm(z)
if beta[j] == 0:
break
result = ritz_numbers(mul(transpose(Q[j]), A, Q[j]))
return result
</syntaxhighlight>

== Последовательная сложность алгоритма ==
Для метода с полной переортогонализацией сложность составляет <math>O(k^2 n)</math>, сложность по памяти -- <math>O(kn)</math>.

== Информационный граф ==
[[File:Lanczos graph.png|thumb|center|640px|Рисунок 1. Информационный граф]]

== Ресурс параллелизма алгоритма ==
Для процесса переортогонализации возможна параллельная оптимизация в двух местах:
* Итерации внутреннего цикла могут вычисляться параллельно, однако, требуется суммирование вычитаемых векторов, соответственно, сложность переортогонализации можно снизить с <math>O(kn)</math> до <math>O(n \log k)</math>
* В каждой итерации внутреннего цикла возможно распараллеливание вычисления выражения справа (скалярное произведение и умножение вектора на число), что теоретически позволяет снизить сложность итерации с <math>O(n)</math> до <math>O(log(n))</math>

== Входные и выходные данные алгоритма ==
'''Входные данны'''е: квадратная симметрическая матрица <math>A</math> порядка <math>n</math>

'''Объём входных данных''': <math>n^2</math>

'''Выходные данные''': собственные числа матрицы

'''Объём выходных данных''': <math>n</math>

== Свойства алгоритма ==
Полная переортогонализация соответствует повторной процедуре ортогонализациии Грама-Шмидта для обеспечения ортогональности вектора <math>z</math> векторам <math>q_1, ..., q_k</math>. В случае идеально точной арифметики данная переортогонализация не требовалась бы, однако в реальных вычислениях ошибки округления приводят к потере ортогональности, в связи с чем требуется переортогонализация.
Однако, единственной проблемой, возникающей при отсутствии переортогонализации, является появление повторных копий чисел Ритца (собственных значений), что в случае, если не требуется установление кратностей собственных значений, допустимо.

= ЧАСТЬ. Программная реализация алгоритма =

== Особенности реализации последовательного алгоритма ==

== [[Локальность данных и вычислений]] ==

== Возможные способы и особенности параллельной реализации алгоритма ==

== Масштабируемость алгоритма и его реализации ==

== Динамические характеристики и эффективность реализации алгоритма ==

== Выводы для классов архитектур ==

== Существующие реализации алгоритма ==
Библиотека [http://www.nag.co.uk/numeric/fl/nagdoc_fl23/html/INDEXES/KWIC/lanczos.html NAG Library] содержит ряд процедур для решения СЛАУ и поиска собственных значений на основе алгоритма Ланцоша.

[http://www.mathworks.com/help/techdoc/ref/eigs.html MATLAB] и [https://www.gnu.org/software/octave/doc/interpreter/Sparse-Linear-Algebra.html#doc_002deigs GNU Octave] позволяют с помощью функции ''eigs()'' находить собственные значения на основе данного алгоритма.

Matlab-реализация доступна как часть [http://www.cs.cmu.edu/~bickson/gabp/#download Gaussian Belief Propagation Matlab Package]. [http://www.graphlab.ml.cmu.edu/pmf.html GraphLab] содержит несколько параллельных реализаций алгоритма на C++.

= Литература =
[1] Дж. Деммель «Вычислительная линейная алгебра»

Участник:Error0x0/Алгоритм Ланцоша для арифметики с плавающей точкой с полной переортогонализацией

2016-10-15T20:39:58Z

Error0x0: /* Информационный граф */

= ЧАСТЬ. Свойства и структура алгоритмов =

== Общее описание алгоритма ==
Алгоритм Ланцоша представляет собой итерационный алгоритм для вычисления собственных значений симметрической матрицы.
Идея алгоритма заключается в построении матрицы <math>Q_k = [q_1, ..., q_k]</math> из ортонормированных векторов Ланцоша и использовании собственных значений трёхдиагональной матрицы <math>T_k = Q_k^T A Q_k</math> (чисел Ритца) как приближения к искомым собственным числам матрицы.

== Математическое описание алгоритма ==
Пусть дана матрица <math>A</math>.
Пусть <math>q_1 = b/||b||_2, \beta_0=0, q_0=0</math>
Алгоритм производит <math>k</math> итераций на каждой из которых:
# вычисляется <math>z = Aq_j</math>,
# производится переортогонализация <math>z = z - \sum^{j-1}_{i=1} {(z^T q_i)q_i}</math>,
# <math>\beta_j = ||z||_2</math>, если <math>\beta_j = 0</math>, алгоритм останавливается,
# <math>q_{j+1} = z/\beta_j</math>,
# вычисляются собственные значения и векторы матрицы <math>T_j = Q_j^T A Q_j</math>.

== Вычислительное ядро алгоритма ==
Основной вклад в сложность алгоритма даёт полная переортогонализация

== Макроструктура алгоритма ==
Основные элементы алгоритма:
* Нахождение векторов Ланцоша
* Полная переортогонализация (Грамма-Шмидта)
* Вычисление собственных значений и векторов матрицы <math>T_j</math> (числа Ритца)

== Схема реализации последовательного алгоритма ==
<syntaxhighlight lang="python">
q[1] = b / norm(b)
beta[0] = 0
q[0] = 0
for j in [1 .. k]:
z = mul(A, q[j])
zT = transposed(z)
for i in [1 .. j - 1]:
z -= mul(scalar_mul(zT, q[i]), q[i])
beta[j] = norm(z)
if beta[j] == 0:
break
result = ritz_numbers(mul(transpose(Q[j]), A, Q[j]))
return result
</syntaxhighlight>

== Последовательная сложность алгоритма ==
Для метода с полной переортогонализацией сложность составляет <math>O(k^2 n)</math>, сложность по памяти -- <math>O(kn)</math>.

== Информационный граф ==
[[File:Lanczos graph.png]]

== Ресурс параллелизма алгоритма ==
Для процесса переортогонализации возможна параллельная оптимизация в двух местах:
* Итерации внутреннего цикла могут вычисляться параллельно, однако, требуется суммирование вычитаемых векторов, соответственно, сложность переортогонализации можно снизить с <math>O(kn)</math> до <math>O(n \log k)</math>
* В каждой итерации внутреннего цикла возможно распараллеливание вычисления выражения справа (скалярное произведение и умножение вектора на число), что теоретически позволяет снизить сложность итерации с <math>O(n)</math> до <math>O(log(n))</math>

== Входные и выходные данные алгоритма ==
'''Входные данны'''е: квадратная симметрическая матрица <math>A</math> порядка <math>n</math>

'''Объём входных данных''': <math>n^2</math>

'''Выходные данные''': собственные числа матрицы

'''Объём выходных данных''': <math>n</math>

== Свойства алгоритма ==
Полная переортогонализация соответствует повторной процедуре ортогонализациии Грама-Шмидта для обеспечения ортогональности вектора <math>z</math> векторам <math>q_1, ..., q_k</math>. В случае идеально точной арифметики данная переортогонализация не требовалась бы, однако в реальных вычислениях ошибки округления приводят к потере ортогональности, в связи с чем требуется переортогонализация.
Однако, единственной проблемой, возникающей при отсутствии переортогонализации, является появление повторных копий чисел Ритца (собственных значений), что в случае, если не требуется установление кратностей собственных значений, допустимо.

= ЧАСТЬ. Программная реализация алгоритма =

== Особенности реализации последовательного алгоритма ==

== [[Локальность данных и вычислений]] ==

== Возможные способы и особенности параллельной реализации алгоритма ==

== Масштабируемость алгоритма и его реализации ==

== Динамические характеристики и эффективность реализации алгоритма ==

== Выводы для классов архитектур ==

== Существующие реализации алгоритма ==
Библиотека [http://www.nag.co.uk/numeric/fl/nagdoc_fl23/html/INDEXES/KWIC/lanczos.html NAG Library] содержит ряд процедур для решения СЛАУ и поиска собственных значений на основе алгоритма Ланцоша.

[http://www.mathworks.com/help/techdoc/ref/eigs.html MATLAB] и [https://www.gnu.org/software/octave/doc/interpreter/Sparse-Linear-Algebra.html#doc_002deigs GNU Octave] позволяют с помощью функции ''eigs()'' находить собственные значения на основе данного алгоритма.

Matlab-реализация доступна как часть [http://www.cs.cmu.edu/~bickson/gabp/#download Gaussian Belief Propagation Matlab Package]. [http://www.graphlab.ml.cmu.edu/pmf.html GraphLab] содержит несколько параллельных реализаций алгоритма на C++.

= Литература =
[1] Дж. Деммель «Вычислительная линейная алгебра»

Участник:Error0x0/Алгоритм Ланцоша для арифметики с плавающей точкой с полной переортогонализацией

2016-10-15T20:38:10Z

Error0x0: /* Информационный граф */

= ЧАСТЬ. Свойства и структура алгоритмов =

== Общее описание алгоритма ==
Алгоритм Ланцоша представляет собой итерационный алгоритм для вычисления собственных значений симметрической матрицы.
Идея алгоритма заключается в построении матрицы <math>Q_k = [q_1, ..., q_k]</math> из ортонормированных векторов Ланцоша и использовании собственных значений трёхдиагональной матрицы <math>T_k = Q_k^T A Q_k</math> (чисел Ритца) как приближения к искомым собственным числам матрицы.

== Математическое описание алгоритма ==
Пусть дана матрица <math>A</math>.
Пусть <math>q_1 = b/||b||_2, \beta_0=0, q_0=0</math>
Алгоритм производит <math>k</math> итераций на каждой из которых:
# вычисляется <math>z = Aq_j</math>,
# производится переортогонализация <math>z = z - \sum^{j-1}_{i=1} {(z^T q_i)q_i}</math>,
# <math>\beta_j = ||z||_2</math>, если <math>\beta_j = 0</math>, алгоритм останавливается,
# <math>q_{j+1} = z/\beta_j</math>,
# вычисляются собственные значения и векторы матрицы <math>T_j = Q_j^T A Q_j</math>.

== Вычислительное ядро алгоритма ==
Основной вклад в сложность алгоритма даёт полная переортогонализация

== Макроструктура алгоритма ==
Основные элементы алгоритма:
* Нахождение векторов Ланцоша
* Полная переортогонализация (Грамма-Шмидта)
* Вычисление собственных значений и векторов матрицы <math>T_j</math> (числа Ритца)

== Схема реализации последовательного алгоритма ==
<syntaxhighlight lang="python">
q[1] = b / norm(b)
beta[0] = 0
q[0] = 0
for j in [1 .. k]:
z = mul(A, q[j])
zT = transposed(z)
for i in [1 .. j - 1]:
z -= mul(scalar_mul(zT, q[i]), q[i])
beta[j] = norm(z)
if beta[j] == 0:
break
result = ritz_numbers(mul(transpose(Q[j]), A, Q[j]))
return result
</syntaxhighlight>

== Последовательная сложность алгоритма ==
Для метода с полной переортогонализацией сложность составляет <math>O(k^2 n)</math>, сложность по памяти -- <math>O(kn)</math>.

== Информационный граф ==
[[Файл:Lanczos_graph.png]]

== Ресурс параллелизма алгоритма ==
Для процесса переортогонализации возможна параллельная оптимизация в двух местах:
* Итерации внутреннего цикла могут вычисляться параллельно, однако, требуется суммирование вычитаемых векторов, соответственно, сложность переортогонализации можно снизить с <math>O(kn)</math> до <math>O(n \log k)</math>
* В каждой итерации внутреннего цикла возможно распараллеливание вычисления выражения справа (скалярное произведение и умножение вектора на число), что теоретически позволяет снизить сложность итерации с <math>O(n)</math> до <math>O(log(n))</math>

== Входные и выходные данные алгоритма ==
'''Входные данны'''е: квадратная симметрическая матрица <math>A</math> порядка <math>n</math>

'''Объём входных данных''': <math>n^2</math>

'''Выходные данные''': собственные числа матрицы

'''Объём выходных данных''': <math>n</math>

== Свойства алгоритма ==
Полная переортогонализация соответствует повторной процедуре ортогонализациии Грама-Шмидта для обеспечения ортогональности вектора <math>z</math> векторам <math>q_1, ..., q_k</math>. В случае идеально точной арифметики данная переортогонализация не требовалась бы, однако в реальных вычислениях ошибки округления приводят к потере ортогональности, в связи с чем требуется переортогонализация.
Однако, единственной проблемой, возникающей при отсутствии переортогонализации, является появление повторных копий чисел Ритца (собственных значений), что в случае, если не требуется установление кратностей собственных значений, допустимо.

= ЧАСТЬ. Программная реализация алгоритма =

== Особенности реализации последовательного алгоритма ==

== [[Локальность данных и вычислений]] ==

== Возможные способы и особенности параллельной реализации алгоритма ==

== Масштабируемость алгоритма и его реализации ==

== Динамические характеристики и эффективность реализации алгоритма ==

== Выводы для классов архитектур ==

== Существующие реализации алгоритма ==
Библиотека [http://www.nag.co.uk/numeric/fl/nagdoc_fl23/html/INDEXES/KWIC/lanczos.html NAG Library] содержит ряд процедур для решения СЛАУ и поиска собственных значений на основе алгоритма Ланцоша.

[http://www.mathworks.com/help/techdoc/ref/eigs.html MATLAB] и [https://www.gnu.org/software/octave/doc/interpreter/Sparse-Linear-Algebra.html#doc_002deigs GNU Octave] позволяют с помощью функции ''eigs()'' находить собственные значения на основе данного алгоритма.

Matlab-реализация доступна как часть [http://www.cs.cmu.edu/~bickson/gabp/#download Gaussian Belief Propagation Matlab Package]. [http://www.graphlab.ml.cmu.edu/pmf.html GraphLab] содержит несколько параллельных реализаций алгоритма на C++.

= Литература =
[1] Дж. Деммель «Вычислительная линейная алгебра»

Участник:Error0x0/Алгоритм Ланцоша для арифметики с плавающей точкой с полной переортогонализацией

2016-10-15T20:29:53Z

Error0x0: /* Математическое описание алгоритма */

= ЧАСТЬ. Свойства и структура алгоритмов =

== Общее описание алгоритма ==
Алгоритм Ланцоша представляет собой итерационный алгоритм для вычисления собственных значений симметрической матрицы.
Идея алгоритма заключается в построении матрицы <math>Q_k = [q_1, ..., q_k]</math> из ортонормированных векторов Ланцоша и использовании собственных значений трёхдиагональной матрицы <math>T_k = Q_k^T A Q_k</math> (чисел Ритца) как приближения к искомым собственным числам матрицы.

== Математическое описание алгоритма ==
Пусть дана матрица <math>A</math>.
Пусть <math>q_1 = b/||b||_2, \beta_0=0, q_0=0</math>
Алгоритм производит <math>k</math> итераций на каждой из которых:
# вычисляется <math>z = Aq_j</math>,
# производится переортогонализация <math>z = z - \sum^{j-1}_{i=1} {(z^T q_i)q_i}</math>,
# <math>\beta_j = ||z||_2</math>, если <math>\beta_j = 0</math>, алгоритм останавливается,
# <math>q_{j+1} = z/\beta_j</math>,
# вычисляются собственные значения и векторы матрицы <math>T_j = Q_j^T A Q_j</math>.

== Вычислительное ядро алгоритма ==
Основной вклад в сложность алгоритма даёт полная переортогонализация

== Макроструктура алгоритма ==
Основные элементы алгоритма:
* Нахождение векторов Ланцоша
* Полная переортогонализация (Грамма-Шмидта)
* Вычисление собственных значений и векторов матрицы <math>T_j</math> (числа Ритца)

== Схема реализации последовательного алгоритма ==
<syntaxhighlight lang="python">
q[1] = b / norm(b)
beta[0] = 0
q[0] = 0
for j in [1 .. k]:
z = mul(A, q[j])
zT = transposed(z)
for i in [1 .. j - 1]:
z -= mul(scalar_mul(zT, q[i]), q[i])
beta[j] = norm(z)
if beta[j] == 0:
break
result = ritz_numbers(mul(transpose(Q[j]), A, Q[j]))
return result
</syntaxhighlight>

== Последовательная сложность алгоритма ==
Для метода с полной переортогонализацией сложность составляет <math>O(k^2 n)</math>, сложность по памяти -- <math>O(kn)</math>.

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

== Ресурс параллелизма алгоритма ==
Для процесса переортогонализации возможна параллельная оптимизация в двух местах:
* Итерации внутреннего цикла могут вычисляться параллельно, однако, требуется суммирование вычитаемых векторов, соответственно, сложность переортогонализации можно снизить с <math>O(kn)</math> до <math>O(n \log k)</math>
* В каждой итерации внутреннего цикла возможно распараллеливание вычисления выражения справа (скалярное произведение и умножение вектора на число), что теоретически позволяет снизить сложность итерации с <math>O(n)</math> до <math>O(log(n))</math>

== Входные и выходные данные алгоритма ==
'''Входные данны'''е: квадратная симметрическая матрица <math>A</math> порядка <math>n</math>

'''Объём входных данных''': <math>n^2</math>

'''Выходные данные''': собственные числа матрицы

'''Объём выходных данных''': <math>n</math>

== Свойства алгоритма ==
Полная переортогонализация соответствует повторной процедуре ортогонализациии Грама-Шмидта для обеспечения ортогональности вектора <math>z</math> векторам <math>q_1, ..., q_k</math>. В случае идеально точной арифметики данная переортогонализация не требовалась бы, однако в реальных вычислениях ошибки округления приводят к потере ортогональности, в связи с чем требуется переортогонализация.
Однако, единственной проблемой, возникающей при отсутствии переортогонализации, является появление повторных копий чисел Ритца (собственных значений), что в случае, если не требуется установление кратностей собственных значений, допустимо.

= ЧАСТЬ. Программная реализация алгоритма =

== Особенности реализации последовательного алгоритма ==

== [[Локальность данных и вычислений]] ==

== Возможные способы и особенности параллельной реализации алгоритма ==

== Масштабируемость алгоритма и его реализации ==

== Динамические характеристики и эффективность реализации алгоритма ==

== Выводы для классов архитектур ==

== Существующие реализации алгоритма ==
Библиотека [http://www.nag.co.uk/numeric/fl/nagdoc_fl23/html/INDEXES/KWIC/lanczos.html NAG Library] содержит ряд процедур для решения СЛАУ и поиска собственных значений на основе алгоритма Ланцоша.

[http://www.mathworks.com/help/techdoc/ref/eigs.html MATLAB] и [https://www.gnu.org/software/octave/doc/interpreter/Sparse-Linear-Algebra.html#doc_002deigs GNU Octave] позволяют с помощью функции ''eigs()'' находить собственные значения на основе данного алгоритма.

Matlab-реализация доступна как часть [http://www.cs.cmu.edu/~bickson/gabp/#download Gaussian Belief Propagation Matlab Package]. [http://www.graphlab.ml.cmu.edu/pmf.html GraphLab] содержит несколько параллельных реализаций алгоритма на C++.

= Литература =
[1] Дж. Деммель «Вычислительная линейная алгебра»

Участник:Error0x0/Алгоритм Ланцоша для арифметики с плавающей точкой с полной переортогонализацией

2016-10-15T20:21:03Z

Error0x0: /* Общее описание алгоритма */

= ЧАСТЬ. Свойства и структура алгоритмов =

== Общее описание алгоритма ==
Алгоритм Ланцоша представляет собой итерационный алгоритм для вычисления собственных значений симметрической матрицы.
Идея алгоритма заключается в построении матрицы <math>Q_k = [q_1, ..., q_k]</math> из ортонормированных векторов Ланцоша и использовании собственных значений трёхдиагональной матрицы <math>T_k = Q_k^T A Q_k</math> (чисел Ритца) как приближения к искомым собственным числам матрицы.

== Математическое описание алгоритма ==
Пусть дана матрица <math>A</math>.
Пусть <math>q_1 = b/||b||_2, \beta_0=0, q_0=0</math>
Алгоритм производит <math>k</math> итераций на каждой из которых:
# вычисляется <math>z = Aq_j</math>,
# производится переортогонализация <math>z = z - \sum^{j-1}_{i=1} {(z^T q_i)q_i}</math>,
# <math>\beta_j = ||z||_2</math>, если <math>\beta_j = 0</math>, алгоритм останавливается,
# <math>q_j+1 = z/\beta_j</math>,
# вычисляются собственные значения и векторы матрицы <math>T_j = Q_j^T A Q_j</math>.

== Вычислительное ядро алгоритма ==
Основной вклад в сложность алгоритма даёт полная переортогонализация

== Макроструктура алгоритма ==
Основные элементы алгоритма:
* Нахождение векторов Ланцоша
* Полная переортогонализация (Грамма-Шмидта)
* Вычисление собственных значений и векторов матрицы <math>T_j</math> (числа Ритца)

== Схема реализации последовательного алгоритма ==
<syntaxhighlight lang="python">
q[1] = b / norm(b)
beta[0] = 0
q[0] = 0
for j in [1 .. k]:
z = mul(A, q[j])
zT = transposed(z)
for i in [1 .. j - 1]:
z -= mul(scalar_mul(zT, q[i]), q[i])
beta[j] = norm(z)
if beta[j] == 0:
break
result = ritz_numbers(mul(transpose(Q[j]), A, Q[j]))
return result
</syntaxhighlight>

== Последовательная сложность алгоритма ==
Для метода с полной переортогонализацией сложность составляет <math>O(k^2 n)</math>, сложность по памяти -- <math>O(kn)</math>.

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

== Ресурс параллелизма алгоритма ==
Для процесса переортогонализации возможна параллельная оптимизация в двух местах:
* Итерации внутреннего цикла могут вычисляться параллельно, однако, требуется суммирование вычитаемых векторов, соответственно, сложность переортогонализации можно снизить с <math>O(kn)</math> до <math>O(n \log k)</math>
* В каждой итерации внутреннего цикла возможно распараллеливание вычисления выражения справа (скалярное произведение и умножение вектора на число), что теоретически позволяет снизить сложность итерации с <math>O(n)</math> до <math>O(log(n))</math>

== Входные и выходные данные алгоритма ==
'''Входные данны'''е: квадратная симметрическая матрица <math>A</math> порядка <math>n</math>

'''Объём входных данных''': <math>n^2</math>

'''Выходные данные''': собственные числа матрицы

'''Объём выходных данных''': <math>n</math>

== Свойства алгоритма ==
Полная переортогонализация соответствует повторной процедуре ортогонализациии Грама-Шмидта для обеспечения ортогональности вектора <math>z</math> векторам <math>q_1, ..., q_k</math>. В случае идеально точной арифметики данная переортогонализация не требовалась бы, однако в реальных вычислениях ошибки округления приводят к потере ортогональности, в связи с чем требуется переортогонализация.
Однако, единственной проблемой, возникающей при отсутствии переортогонализации, является появление повторных копий чисел Ритца (собственных значений), что в случае, если не требуется установление кратностей собственных значений, допустимо.

= ЧАСТЬ. Программная реализация алгоритма =

== Особенности реализации последовательного алгоритма ==

== [[Локальность данных и вычислений]] ==

== Возможные способы и особенности параллельной реализации алгоритма ==

== Масштабируемость алгоритма и его реализации ==

== Динамические характеристики и эффективность реализации алгоритма ==

== Выводы для классов архитектур ==

== Существующие реализации алгоритма ==
Библиотека [http://www.nag.co.uk/numeric/fl/nagdoc_fl23/html/INDEXES/KWIC/lanczos.html NAG Library] содержит ряд процедур для решения СЛАУ и поиска собственных значений на основе алгоритма Ланцоша.

[http://www.mathworks.com/help/techdoc/ref/eigs.html MATLAB] и [https://www.gnu.org/software/octave/doc/interpreter/Sparse-Linear-Algebra.html#doc_002deigs GNU Octave] позволяют с помощью функции ''eigs()'' находить собственные значения на основе данного алгоритма.

Matlab-реализация доступна как часть [http://www.cs.cmu.edu/~bickson/gabp/#download Gaussian Belief Propagation Matlab Package]. [http://www.graphlab.ml.cmu.edu/pmf.html GraphLab] содержит несколько параллельных реализаций алгоритма на C++.

= Литература =
[1] Дж. Деммель «Вычислительная линейная алгебра»

Участник:Error0x0/Алгоритм Ланцоша для арифметики с плавающей точкой с полной переортогонализацией

2016-10-15T20:19:36Z

Error0x0: /* Литература */

= ЧАСТЬ. Свойства и структура алгоритмов =

== Общее описание алгоритма ==
Алгоритм Ланцоша представляет собой итерационный алгоритм для вычисления собственных значений симметрической матрицы.
Идея алгоритма заключается в построении матрицы <math>Q_k = [q_1, ..., q_k]</math> из ортонормированных векторов Ланцоша и нахождении собственных значений трёхдиагональной матрицы <math>T_k = Q_k^T A Q_k</math>.

== Математическое описание алгоритма ==
Пусть дана матрица <math>A</math>.
Пусть <math>q_1 = b/||b||_2, \beta_0=0, q_0=0</math>
Алгоритм производит <math>k</math> итераций на каждой из которых:
# вычисляется <math>z = Aq_j</math>,
# производится переортогонализация <math>z = z - \sum^{j-1}_{i=1} {(z^T q_i)q_i}</math>,
# <math>\beta_j = ||z||_2</math>, если <math>\beta_j = 0</math>, алгоритм останавливается,
# <math>q_j+1 = z/\beta_j</math>,
# вычисляются собственные значения и векторы матрицы <math>T_j = Q_j^T A Q_j</math>.

== Вычислительное ядро алгоритма ==
Основной вклад в сложность алгоритма даёт полная переортогонализация

== Макроструктура алгоритма ==
Основные элементы алгоритма:
* Нахождение векторов Ланцоша
* Полная переортогонализация (Грамма-Шмидта)
* Вычисление собственных значений и векторов матрицы <math>T_j</math> (числа Ритца)

== Схема реализации последовательного алгоритма ==
<syntaxhighlight lang="python">
q[1] = b / norm(b)
beta[0] = 0
q[0] = 0
for j in [1 .. k]:
z = mul(A, q[j])
zT = transposed(z)
for i in [1 .. j - 1]:
z -= mul(scalar_mul(zT, q[i]), q[i])
beta[j] = norm(z)
if beta[j] == 0:
break
result = ritz_numbers(mul(transpose(Q[j]), A, Q[j]))
return result
</syntaxhighlight>

== Последовательная сложность алгоритма ==
Для метода с полной переортогонализацией сложность составляет <math>O(k^2 n)</math>, сложность по памяти -- <math>O(kn)</math>.

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

== Ресурс параллелизма алгоритма ==
Для процесса переортогонализации возможна параллельная оптимизация в двух местах:
* Итерации внутреннего цикла могут вычисляться параллельно, однако, требуется суммирование вычитаемых векторов, соответственно, сложность переортогонализации можно снизить с <math>O(kn)</math> до <math>O(n \log k)</math>
* В каждой итерации внутреннего цикла возможно распараллеливание вычисления выражения справа (скалярное произведение и умножение вектора на число), что теоретически позволяет снизить сложность итерации с <math>O(n)</math> до <math>O(log(n))</math>

== Входные и выходные данные алгоритма ==
'''Входные данны'''е: квадратная симметрическая матрица <math>A</math> порядка <math>n</math>

'''Объём входных данных''': <math>n^2</math>

'''Выходные данные''': собственные числа матрицы

'''Объём выходных данных''': <math>n</math>

== Свойства алгоритма ==
Полная переортогонализация соответствует повторной процедуре ортогонализациии Грама-Шмидта для обеспечения ортогональности вектора <math>z</math> векторам <math>q_1, ..., q_k</math>. В случае идеально точной арифметики данная переортогонализация не требовалась бы, однако в реальных вычислениях ошибки округления приводят к потере ортогональности, в связи с чем требуется переортогонализация.
Однако, единственной проблемой, возникающей при отсутствии переортогонализации, является появление повторных копий чисел Ритца (собственных значений), что в случае, если не требуется установление кратностей собственных значений, допустимо.

= ЧАСТЬ. Программная реализация алгоритма =

== Особенности реализации последовательного алгоритма ==

== [[Локальность данных и вычислений]] ==

== Возможные способы и особенности параллельной реализации алгоритма ==

== Масштабируемость алгоритма и его реализации ==

== Динамические характеристики и эффективность реализации алгоритма ==

== Выводы для классов архитектур ==

== Существующие реализации алгоритма ==
Библиотека [http://www.nag.co.uk/numeric/fl/nagdoc_fl23/html/INDEXES/KWIC/lanczos.html NAG Library] содержит ряд процедур для решения СЛАУ и поиска собственных значений на основе алгоритма Ланцоша.

[http://www.mathworks.com/help/techdoc/ref/eigs.html MATLAB] и [https://www.gnu.org/software/octave/doc/interpreter/Sparse-Linear-Algebra.html#doc_002deigs GNU Octave] позволяют с помощью функции ''eigs()'' находить собственные значения на основе данного алгоритма.

Matlab-реализация доступна как часть [http://www.cs.cmu.edu/~bickson/gabp/#download Gaussian Belief Propagation Matlab Package]. [http://www.graphlab.ml.cmu.edu/pmf.html GraphLab] содержит несколько параллельных реализаций алгоритма на C++.

= Литература =
[1] Дж. Деммель «Вычислительная линейная алгебра»

Участник:Error0x0/Алгоритм Ланцоша для арифметики с плавающей точкой с полной переортогонализацией

2016-10-15T20:18:16Z

Error0x0: /* Существующие реализации алгоритма */

= ЧАСТЬ. Свойства и структура алгоритмов =

== Общее описание алгоритма ==
Алгоритм Ланцоша представляет собой итерационный алгоритм для вычисления собственных значений симметрической матрицы.
Идея алгоритма заключается в построении матрицы <math>Q_k = [q_1, ..., q_k]</math> из ортонормированных векторов Ланцоша и нахождении собственных значений трёхдиагональной матрицы <math>T_k = Q_k^T A Q_k</math>.

== Математическое описание алгоритма ==
Пусть дана матрица <math>A</math>.
Пусть <math>q_1 = b/||b||_2, \beta_0=0, q_0=0</math>
Алгоритм производит <math>k</math> итераций на каждой из которых:
# вычисляется <math>z = Aq_j</math>,
# производится переортогонализация <math>z = z - \sum^{j-1}_{i=1} {(z^T q_i)q_i}</math>,
# <math>\beta_j = ||z||_2</math>, если <math>\beta_j = 0</math>, алгоритм останавливается,
# <math>q_j+1 = z/\beta_j</math>,
# вычисляются собственные значения и векторы матрицы <math>T_j = Q_j^T A Q_j</math>.

== Вычислительное ядро алгоритма ==
Основной вклад в сложность алгоритма даёт полная переортогонализация

== Макроструктура алгоритма ==
Основные элементы алгоритма:
* Нахождение векторов Ланцоша
* Полная переортогонализация (Грамма-Шмидта)
* Вычисление собственных значений и векторов матрицы <math>T_j</math> (числа Ритца)

== Схема реализации последовательного алгоритма ==
<syntaxhighlight lang="python">
q[1] = b / norm(b)
beta[0] = 0
q[0] = 0
for j in [1 .. k]:
z = mul(A, q[j])
zT = transposed(z)
for i in [1 .. j - 1]:
z -= mul(scalar_mul(zT, q[i]), q[i])
beta[j] = norm(z)
if beta[j] == 0:
break
result = ritz_numbers(mul(transpose(Q[j]), A, Q[j]))
return result
</syntaxhighlight>

== Последовательная сложность алгоритма ==
Для метода с полной переортогонализацией сложность составляет <math>O(k^2 n)</math>, сложность по памяти -- <math>O(kn)</math>.

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

== Ресурс параллелизма алгоритма ==
Для процесса переортогонализации возможна параллельная оптимизация в двух местах:
* Итерации внутреннего цикла могут вычисляться параллельно, однако, требуется суммирование вычитаемых векторов, соответственно, сложность переортогонализации можно снизить с <math>O(kn)</math> до <math>O(n \log k)</math>
* В каждой итерации внутреннего цикла возможно распараллеливание вычисления выражения справа (скалярное произведение и умножение вектора на число), что теоретически позволяет снизить сложность итерации с <math>O(n)</math> до <math>O(log(n))</math>

== Входные и выходные данные алгоритма ==
'''Входные данны'''е: квадратная симметрическая матрица <math>A</math> порядка <math>n</math>

'''Объём входных данных''': <math>n^2</math>

'''Выходные данные''': собственные числа матрицы

'''Объём выходных данных''': <math>n</math>

== Свойства алгоритма ==
Полная переортогонализация соответствует повторной процедуре ортогонализациии Грама-Шмидта для обеспечения ортогональности вектора <math>z</math> векторам <math>q_1, ..., q_k</math>. В случае идеально точной арифметики данная переортогонализация не требовалась бы, однако в реальных вычислениях ошибки округления приводят к потере ортогональности, в связи с чем требуется переортогонализация.
Однако, единственной проблемой, возникающей при отсутствии переортогонализации, является появление повторных копий чисел Ритца (собственных значений), что в случае, если не требуется установление кратностей собственных значений, допустимо.

= ЧАСТЬ. Программная реализация алгоритма =

== Особенности реализации последовательного алгоритма ==

== [[Локальность данных и вычислений]] ==

== Возможные способы и особенности параллельной реализации алгоритма ==

== Масштабируемость алгоритма и его реализации ==

== Динамические характеристики и эффективность реализации алгоритма ==

== Выводы для классов архитектур ==

== Существующие реализации алгоритма ==
Библиотека [http://www.nag.co.uk/numeric/fl/nagdoc_fl23/html/INDEXES/KWIC/lanczos.html NAG Library] содержит ряд процедур для решения СЛАУ и поиска собственных значений на основе алгоритма Ланцоша.

[http://www.mathworks.com/help/techdoc/ref/eigs.html MATLAB] и [https://www.gnu.org/software/octave/doc/interpreter/Sparse-Linear-Algebra.html#doc_002deigs GNU Octave] позволяют с помощью функции ''eigs()'' находить собственные значения на основе данного алгоритма.

Matlab-реализация доступна как часть [http://www.cs.cmu.edu/~bickson/gabp/#download Gaussian Belief Propagation Matlab Package]. [http://www.graphlab.ml.cmu.edu/pmf.html GraphLab] содержит несколько параллельных реализаций алгоритма на C++.

= Литература =
[1] Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. - СПб.: БХВ-Петербург, 2002. - 608 с.

[2] Воеводин В.В., Воеводин Вад.В. Спасительная локальность суперкомпьютеров //Открытые системы. - 2013. - № 9. - С. 12-15.

[3] Воеводин Вад.В., Швец П. Метод покрытий для оценки локальности использования данных в программах // Вестник УГАТУ. — 2014. — Т. 18, № 1(62). — С. 224–229.

[4] Антонов А.С., Теплов А.М. О практической сложности понятия масштабируемости параллельных программ// Высокопроизводительные параллельные вычисления на кластерных системах (HPC 2014): Материалы XIV Международной конференции -Пермь: Издательство ПНИПУ, 2014. С. 20-27.

[5] Никитенко Д.А. Комплексный анализ производительности суперкомпьютерных систем, основанный на данных системного мониторинга // Вычислительные методы и программирование. 2014. 15. 85–97.

Участник:Error0x0/Алгоритм Ланцоша для арифметики с плавающей точкой с полной переортогонализацией

2016-10-15T20:13:43Z

Error0x0: /* Существующие реализации алгоритма */

= ЧАСТЬ. Свойства и структура алгоритмов =

== Общее описание алгоритма ==
Алгоритм Ланцоша представляет собой итерационный алгоритм для вычисления собственных значений симметрической матрицы.
Идея алгоритма заключается в построении матрицы <math>Q_k = [q_1, ..., q_k]</math> из ортонормированных векторов Ланцоша и нахождении собственных значений трёхдиагональной матрицы <math>T_k = Q_k^T A Q_k</math>.

== Математическое описание алгоритма ==
Пусть дана матрица <math>A</math>.
Пусть <math>q_1 = b/||b||_2, \beta_0=0, q_0=0</math>
Алгоритм производит <math>k</math> итераций на каждой из которых:
# вычисляется <math>z = Aq_j</math>,
# производится переортогонализация <math>z = z - \sum^{j-1}_{i=1} {(z^T q_i)q_i}</math>,
# <math>\beta_j = ||z||_2</math>, если <math>\beta_j = 0</math>, алгоритм останавливается,
# <math>q_j+1 = z/\beta_j</math>,
# вычисляются собственные значения и векторы матрицы <math>T_j = Q_j^T A Q_j</math>.

== Вычислительное ядро алгоритма ==
Основной вклад в сложность алгоритма даёт полная переортогонализация

== Макроструктура алгоритма ==
Основные элементы алгоритма:
* Нахождение векторов Ланцоша
* Полная переортогонализация (Грамма-Шмидта)
* Вычисление собственных значений и векторов матрицы <math>T_j</math> (числа Ритца)

== Схема реализации последовательного алгоритма ==
<syntaxhighlight lang="python">
q[1] = b / norm(b)
beta[0] = 0
q[0] = 0
for j in [1 .. k]:
z = mul(A, q[j])
zT = transposed(z)
for i in [1 .. j - 1]:
z -= mul(scalar_mul(zT, q[i]), q[i])
beta[j] = norm(z)
if beta[j] == 0:
break
result = ritz_numbers(mul(transpose(Q[j]), A, Q[j]))
return result
</syntaxhighlight>

== Последовательная сложность алгоритма ==
Для метода с полной переортогонализацией сложность составляет <math>O(k^2 n)</math>, сложность по памяти -- <math>O(kn)</math>.

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

== Ресурс параллелизма алгоритма ==
Для процесса переортогонализации возможна параллельная оптимизация в двух местах:
* Итерации внутреннего цикла могут вычисляться параллельно, однако, требуется суммирование вычитаемых векторов, соответственно, сложность переортогонализации можно снизить с <math>O(kn)</math> до <math>O(n \log k)</math>
* В каждой итерации внутреннего цикла возможно распараллеливание вычисления выражения справа (скалярное произведение и умножение вектора на число), что теоретически позволяет снизить сложность итерации с <math>O(n)</math> до <math>O(log(n))</math>

== Входные и выходные данные алгоритма ==
'''Входные данны'''е: квадратная симметрическая матрица <math>A</math> порядка <math>n</math>

'''Объём входных данных''': <math>n^2</math>

'''Выходные данные''': собственные числа матрицы

'''Объём выходных данных''': <math>n</math>

== Свойства алгоритма ==
Полная переортогонализация соответствует повторной процедуре ортогонализациии Грама-Шмидта для обеспечения ортогональности вектора <math>z</math> векторам <math>q_1, ..., q_k</math>. В случае идеально точной арифметики данная переортогонализация не требовалась бы, однако в реальных вычислениях ошибки округления приводят к потере ортогональности, в связи с чем требуется переортогонализация.
Однако, единственной проблемой, возникающей при отсутствии переортогонализации, является появление повторных копий чисел Ритца (собственных значений), что в случае, если не требуется установление кратностей собственных значений, допустимо.

= ЧАСТЬ. Программная реализация алгоритма =

== Особенности реализации последовательного алгоритма ==

== [[Локальность данных и вычислений]] ==

== Возможные способы и особенности параллельной реализации алгоритма ==

== Масштабируемость алгоритма и его реализации ==

== Динамические характеристики и эффективность реализации алгоритма ==

== Выводы для классов архитектур ==

== Существующие реализации алгоритма ==
Библиотека [[NAG Numerical Library|NAG Library]] содержит ряд процедур<ref>{{ cite web | author = The Numerical Algorithms Group | title = Keyword Index: Lanczos | work = NAG Library Manual, Mark 23 | url = http://www.nag.co.uk/numeric/fl/nagdoc_fl23/html/INDEXES/KWIC/lanczos.html | accessdate = 2012-02-09 }}</ref> для решения СЛАУ и поиска собственных значений на основе алгоритма Ланцоша.

[[MATLAB]] и [[GNU Octave]] позволяют с помощью функции ''eigs()'' находить собственные значения на основе данного алгоритма([http://www.mathworks.com/help/techdoc/ref/eigs.html Matlab]/[https://www.gnu.org/software/octave/doc/interpreter/Sparse-Linear-Algebra.html#doc_002deigs Octave]).

Matlab-реализация доступна как часть [http://www.cs.cmu.edu/~bickson/gabp/#download Gaussian Belief Propagation Matlab Package]. [[GraphLab]]<ref>[http://www.graphlab.ml.cmu.edu/pmf.html GraphLab]</ref> содержит несколько параллельных реализаций алгоритма на C++.

= Литература =
[1] Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. - СПб.: БХВ-Петербург, 2002. - 608 с.

[2] Воеводин В.В., Воеводин Вад.В. Спасительная локальность суперкомпьютеров //Открытые системы. - 2013. - № 9. - С. 12-15.

[3] Воеводин Вад.В., Швец П. Метод покрытий для оценки локальности использования данных в программах // Вестник УГАТУ. — 2014. — Т. 18, № 1(62). — С. 224–229.

[4] Антонов А.С., Теплов А.М. О практической сложности понятия масштабируемости параллельных программ// Высокопроизводительные параллельные вычисления на кластерных системах (HPC 2014): Материалы XIV Международной конференции -Пермь: Издательство ПНИПУ, 2014. С. 20-27.

[5] Никитенко Д.А. Комплексный анализ производительности суперкомпьютерных систем, основанный на данных системного мониторинга // Вычислительные методы и программирование. 2014. 15. 85–97.

Участник:Error0x0/Алгоритм Ланцоша для арифметики с плавающей точкой с полной переортогонализацией

2016-10-15T19:53:31Z

Error0x0: /* Ресурс параллелизма алгоритма */

= ЧАСТЬ. Свойства и структура алгоритмов =

== Общее описание алгоритма ==
Алгоритм Ланцоша представляет собой итерационный алгоритм для вычисления собственных значений симметрической матрицы.
Идея алгоритма заключается в построении матрицы <math>Q_k = [q_1, ..., q_k]</math> из ортонормированных векторов Ланцоша и нахождении собственных значений трёхдиагональной матрицы <math>T_k = Q_k^T A Q_k</math>.

== Математическое описание алгоритма ==
Пусть дана матрица <math>A</math>.
Пусть <math>q_1 = b/||b||_2, \beta_0=0, q_0=0</math>
Алгоритм производит <math>k</math> итераций на каждой из которых:
# вычисляется <math>z = Aq_j</math>,
# производится переортогонализация <math>z = z - \sum^{j-1}_{i=1} {(z^T q_i)q_i}</math>,
# <math>\beta_j = ||z||_2</math>, если <math>\beta_j = 0</math>, алгоритм останавливается,
# <math>q_j+1 = z/\beta_j</math>,
# вычисляются собственные значения и векторы матрицы <math>T_j = Q_j^T A Q_j</math>.

== Вычислительное ядро алгоритма ==
Основной вклад в сложность алгоритма даёт полная переортогонализация

== Макроструктура алгоритма ==
Основные элементы алгоритма:
* Нахождение векторов Ланцоша
* Полная переортогонализация (Грамма-Шмидта)
* Вычисление собственных значений и векторов матрицы <math>T_j</math> (числа Ритца)

== Схема реализации последовательного алгоритма ==
<syntaxhighlight lang="python">
q[1] = b / norm(b)
beta[0] = 0
q[0] = 0
for j in [1 .. k]:
z = mul(A, q[j])
zT = transposed(z)
for i in [1 .. j - 1]:
z -= mul(scalar_mul(zT, q[i]), q[i])
beta[j] = norm(z)
if beta[j] == 0:
break
result = ritz_numbers(mul(transpose(Q[j]), A, Q[j]))
return result
</syntaxhighlight>

== Последовательная сложность алгоритма ==
Для метода с полной переортогонализацией сложность составляет <math>O(k^2 n)</math>, сложность по памяти -- <math>O(kn)</math>.

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

== Ресурс параллелизма алгоритма ==
Для процесса переортогонализации возможна параллельная оптимизация в двух местах:
* Итерации внутреннего цикла могут вычисляться параллельно, однако, требуется суммирование вычитаемых векторов, соответственно, сложность переортогонализации можно снизить с <math>O(kn)</math> до <math>O(n \log k)</math>
* В каждой итерации внутреннего цикла возможно распараллеливание вычисления выражения справа (скалярное произведение и умножение вектора на число), что теоретически позволяет снизить сложность итерации с <math>O(n)</math> до <math>O(log(n))</math>

== Входные и выходные данные алгоритма ==
'''Входные данны'''е: квадратная симметрическая матрица <math>A</math> порядка <math>n</math>

'''Объём входных данных''': <math>n^2</math>

'''Выходные данные''': собственные числа матрицы

'''Объём выходных данных''': <math>n</math>

== Свойства алгоритма ==
Полная переортогонализация соответствует повторной процедуре ортогонализациии Грама-Шмидта для обеспечения ортогональности вектора <math>z</math> векторам <math>q_1, ..., q_k</math>. В случае идеально точной арифметики данная переортогонализация не требовалась бы, однако в реальных вычислениях ошибки округления приводят к потере ортогональности, в связи с чем требуется переортогонализация.
Однако, единственной проблемой, возникающей при отсутствии переортогонализации, является появление повторных копий чисел Ритца (собственных значений), что в случае, если не требуется установление кратностей собственных значений, допустимо.

= ЧАСТЬ. Программная реализация алгоритма =

== Особенности реализации последовательного алгоритма ==

== [[Локальность данных и вычислений]] ==

== Возможные способы и особенности параллельной реализации алгоритма ==

== Масштабируемость алгоритма и его реализации ==

== Динамические характеристики и эффективность реализации алгоритма ==

== Выводы для классов архитектур ==

== Существующие реализации алгоритма ==

= Литература =
[1] Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. - СПб.: БХВ-Петербург, 2002. - 608 с.

[2] Воеводин В.В., Воеводин Вад.В. Спасительная локальность суперкомпьютеров //Открытые системы. - 2013. - № 9. - С. 12-15.

[3] Воеводин Вад.В., Швец П. Метод покрытий для оценки локальности использования данных в программах // Вестник УГАТУ. — 2014. — Т. 18, № 1(62). — С. 224–229.

[4] Антонов А.С., Теплов А.М. О практической сложности понятия масштабируемости параллельных программ// Высокопроизводительные параллельные вычисления на кластерных системах (HPC 2014): Материалы XIV Международной конференции -Пермь: Издательство ПНИПУ, 2014. С. 20-27.

[5] Никитенко Д.А. Комплексный анализ производительности суперкомпьютерных систем, основанный на данных системного мониторинга // Вычислительные методы и программирование. 2014. 15. 85–97.

Участник:Error0x0/Алгоритм Ланцоша для арифметики с плавающей точкой с полной переортогонализацией

2016-10-15T19:39:22Z

Error0x0: /* Входные и выходные данные алгоритма */

= ЧАСТЬ. Свойства и структура алгоритмов =

== Общее описание алгоритма ==
Алгоритм Ланцоша представляет собой итерационный алгоритм для вычисления собственных значений симметрической матрицы.
Идея алгоритма заключается в построении матрицы <math>Q_k = [q_1, ..., q_k]</math> из ортонормированных векторов Ланцоша и нахождении собственных значений трёхдиагональной матрицы <math>T_k = Q_k^T A Q_k</math>.

== Математическое описание алгоритма ==
Пусть дана матрица <math>A</math>.
Пусть <math>q_1 = b/||b||_2, \beta_0=0, q_0=0</math>
Алгоритм производит <math>k</math> итераций на каждой из которых:
# вычисляется <math>z = Aq_j</math>,
# производится переортогонализация <math>z = z - \sum^{j-1}_{i=1} {(z^T q_i)q_i}</math>,
# <math>\beta_j = ||z||_2</math>, если <math>\beta_j = 0</math>, алгоритм останавливается,
# <math>q_j+1 = z/\beta_j</math>,
# вычисляются собственные значения и векторы матрицы <math>T_j = Q_j^T A Q_j</math>.

== Вычислительное ядро алгоритма ==
Основной вклад в сложность алгоритма даёт полная переортогонализация

== Макроструктура алгоритма ==
Основные элементы алгоритма:
* Нахождение векторов Ланцоша
* Полная переортогонализация (Грамма-Шмидта)
* Вычисление собственных значений и векторов матрицы <math>T_j</math> (числа Ритца)

== Схема реализации последовательного алгоритма ==
<syntaxhighlight lang="python">
q[1] = b / norm(b)
beta[0] = 0
q[0] = 0
for j in [1 .. k]:
z = mul(A, q[j])
zT = transposed(z)
for i in [1 .. j - 1]:
z -= mul(scalar_mul(zT, q[i]), q[i])
beta[j] = norm(z)
if beta[j] == 0:
break
result = ritz_numbers(mul(transpose(Q[j]), A, Q[j]))
return result
</syntaxhighlight>

== Последовательная сложность алгоритма ==
Для метода с полной переортогонализацией сложность составляет <math>O(k^2 n)</math>, сложность по памяти -- <math>O(kn)</math>.

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

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

== Входные и выходные данные алгоритма ==
'''Входные данны'''е: квадратная симметрическая матрица <math>A</math> порядка <math>n</math>

'''Объём входных данных''': <math>n^2</math>

'''Выходные данные''': собственные числа матрицы

'''Объём выходных данных''': <math>n</math>

== Свойства алгоритма ==
Полная переортогонализация соответствует повторной процедуре ортогонализациии Грама-Шмидта для обеспечения ортогональности вектора <math>z</math> векторам <math>q_1, ..., q_k</math>. В случае идеально точной арифметики данная переортогонализация не требовалась бы, однако в реальных вычислениях ошибки округления приводят к потере ортогональности, в связи с чем требуется переортогонализация.
Однако, единственной проблемой, возникающей при отсутствии переортогонализации, является появление повторных копий чисел Ритца (собственных значений), что в случае, если не требуется установление кратностей собственных значений, допустимо.

= ЧАСТЬ. Программная реализация алгоритма =

== Особенности реализации последовательного алгоритма ==

== [[Локальность данных и вычислений]] ==

== Возможные способы и особенности параллельной реализации алгоритма ==

== Масштабируемость алгоритма и его реализации ==

== Динамические характеристики и эффективность реализации алгоритма ==

== Выводы для классов архитектур ==

== Существующие реализации алгоритма ==

= Литература =
[1] Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. - СПб.: БХВ-Петербург, 2002. - 608 с.

[2] Воеводин В.В., Воеводин Вад.В. Спасительная локальность суперкомпьютеров //Открытые системы. - 2013. - № 9. - С. 12-15.

[3] Воеводин Вад.В., Швец П. Метод покрытий для оценки локальности использования данных в программах // Вестник УГАТУ. — 2014. — Т. 18, № 1(62). — С. 224–229.

[4] Антонов А.С., Теплов А.М. О практической сложности понятия масштабируемости параллельных программ// Высокопроизводительные параллельные вычисления на кластерных системах (HPC 2014): Материалы XIV Международной конференции -Пермь: Издательство ПНИПУ, 2014. С. 20-27.

[5] Никитенко Д.А. Комплексный анализ производительности суперкомпьютерных систем, основанный на данных системного мониторинга // Вычислительные методы и программирование. 2014. 15. 85–97.

Участник:Error0x0/Алгоритм Ланцоша для арифметики с плавающей точкой с полной переортогонализацией

2016-10-15T19:38:35Z

Error0x0: /* Схема реализации последовательного алгоритма */

= ЧАСТЬ. Свойства и структура алгоритмов =

== Общее описание алгоритма ==
Алгоритм Ланцоша представляет собой итерационный алгоритм для вычисления собственных значений симметрической матрицы.
Идея алгоритма заключается в построении матрицы <math>Q_k = [q_1, ..., q_k]</math> из ортонормированных векторов Ланцоша и нахождении собственных значений трёхдиагональной матрицы <math>T_k = Q_k^T A Q_k</math>.

== Математическое описание алгоритма ==
Пусть дана матрица <math>A</math>.
Пусть <math>q_1 = b/||b||_2, \beta_0=0, q_0=0</math>
Алгоритм производит <math>k</math> итераций на каждой из которых:
# вычисляется <math>z = Aq_j</math>,
# производится переортогонализация <math>z = z - \sum^{j-1}_{i=1} {(z^T q_i)q_i}</math>,
# <math>\beta_j = ||z||_2</math>, если <math>\beta_j = 0</math>, алгоритм останавливается,
# <math>q_j+1 = z/\beta_j</math>,
# вычисляются собственные значения и векторы матрицы <math>T_j = Q_j^T A Q_j</math>.

== Вычислительное ядро алгоритма ==
Основной вклад в сложность алгоритма даёт полная переортогонализация

== Макроструктура алгоритма ==
Основные элементы алгоритма:
* Нахождение векторов Ланцоша
* Полная переортогонализация (Грамма-Шмидта)
* Вычисление собственных значений и векторов матрицы <math>T_j</math> (числа Ритца)

== Схема реализации последовательного алгоритма ==
<syntaxhighlight lang="python">
q[1] = b / norm(b)
beta[0] = 0
q[0] = 0
for j in [1 .. k]:
z = mul(A, q[j])
zT = transposed(z)
for i in [1 .. j - 1]:
z -= mul(scalar_mul(zT, q[i]), q[i])
beta[j] = norm(z)
if beta[j] == 0:
break
result = ritz_numbers(mul(transpose(Q[j]), A, Q[j]))
return result
</syntaxhighlight>

== Последовательная сложность алгоритма ==
Для метода с полной переортогонализацией сложность составляет <math>O(k^2 n)</math>, сложность по памяти -- <math>O(kn)</math>.

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

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

== Входные и выходные данные алгоритма ==
'''Входные данны'''е: квадратная симметрическая матрица <math>A</math> порядка <math>n</math>
'''Объём входных данных''': <math>n^2</math>
'''Выходные данные''': собственные числа матрицы
'''Объём выходных данных''': <math>n</math>

== Свойства алгоритма ==
Полная переортогонализация соответствует повторной процедуре ортогонализациии Грама-Шмидта для обеспечения ортогональности вектора <math>z</math> векторам <math>q_1, ..., q_k</math>. В случае идеально точной арифметики данная переортогонализация не требовалась бы, однако в реальных вычислениях ошибки округления приводят к потере ортогональности, в связи с чем требуется переортогонализация.
Однако, единственной проблемой, возникающей при отсутствии переортогонализации, является появление повторных копий чисел Ритца (собственных значений), что в случае, если не требуется установление кратностей собственных значений, допустимо.

= ЧАСТЬ. Программная реализация алгоритма =

== Особенности реализации последовательного алгоритма ==

== [[Локальность данных и вычислений]] ==

== Возможные способы и особенности параллельной реализации алгоритма ==

== Масштабируемость алгоритма и его реализации ==

== Динамические характеристики и эффективность реализации алгоритма ==

== Выводы для классов архитектур ==

== Существующие реализации алгоритма ==

= Литература =
[1] Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. - СПб.: БХВ-Петербург, 2002. - 608 с.

[2] Воеводин В.В., Воеводин Вад.В. Спасительная локальность суперкомпьютеров //Открытые системы. - 2013. - № 9. - С. 12-15.

[3] Воеводин Вад.В., Швец П. Метод покрытий для оценки локальности использования данных в программах // Вестник УГАТУ. — 2014. — Т. 18, № 1(62). — С. 224–229.

[4] Антонов А.С., Теплов А.М. О практической сложности понятия масштабируемости параллельных программ// Высокопроизводительные параллельные вычисления на кластерных системах (HPC 2014): Материалы XIV Международной конференции -Пермь: Издательство ПНИПУ, 2014. С. 20-27.

[5] Никитенко Д.А. Комплексный анализ производительности суперкомпьютерных систем, основанный на данных системного мониторинга // Вычислительные методы и программирование. 2014. 15. 85–97.

Участник:Error0x0/Алгоритм Ланцоша для арифметики с плавающей точкой с полной переортогонализацией

2016-10-15T19:38:12Z

Error0x0: /* Схема реализации последовательного алгоритма */

= ЧАСТЬ. Свойства и структура алгоритмов =

== Общее описание алгоритма ==
Алгоритм Ланцоша представляет собой итерационный алгоритм для вычисления собственных значений симметрической матрицы.
Идея алгоритма заключается в построении матрицы <math>Q_k = [q_1, ..., q_k]</math> из ортонормированных векторов Ланцоша и нахождении собственных значений трёхдиагональной матрицы <math>T_k = Q_k^T A Q_k</math>.

== Математическое описание алгоритма ==
Пусть дана матрица <math>A</math>.
Пусть <math>q_1 = b/||b||_2, \beta_0=0, q_0=0</math>
Алгоритм производит <math>k</math> итераций на каждой из которых:
# вычисляется <math>z = Aq_j</math>,
# производится переортогонализация <math>z = z - \sum^{j-1}_{i=1} {(z^T q_i)q_i}</math>,
# <math>\beta_j = ||z||_2</math>, если <math>\beta_j = 0</math>, алгоритм останавливается,
# <math>q_j+1 = z/\beta_j</math>,
# вычисляются собственные значения и векторы матрицы <math>T_j = Q_j^T A Q_j</math>.

== Вычислительное ядро алгоритма ==
Основной вклад в сложность алгоритма даёт полная переортогонализация

== Макроструктура алгоритма ==
Основные элементы алгоритма:
* Нахождение векторов Ланцоша
* Полная переортогонализация (Грамма-Шмидта)
* Вычисление собственных значений и векторов матрицы <math>T_j</math> (числа Ритца)

== Схема реализации последовательного алгоритма ==
<syntaxhighlight lang="python">
q[1] = b / norm(b)
beta[0] = 0
q[0] = 0
for j in [1 .. k]:
z = mul(A, q[j])
zT = transposed(z)
for i in [1 .. j - 1]:
z -= mul(scalar_mul(zT,q[i]), q[i])
beta[j] = norm(z)
if beta[j] == 0:
break
result = ritz_numbers(mul(transpose(Q[j]), A, Q[j]))
return result
</syntaxhighlight>

== Последовательная сложность алгоритма ==
Для метода с полной переортогонализацией сложность составляет <math>O(k^2 n)</math>, сложность по памяти -- <math>O(kn)</math>.

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

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

== Входные и выходные данные алгоритма ==
'''Входные данны'''е: квадратная симметрическая матрица <math>A</math> порядка <math>n</math>
'''Объём входных данных''': <math>n^2</math>
'''Выходные данные''': собственные числа матрицы
'''Объём выходных данных''': <math>n</math>

== Свойства алгоритма ==
Полная переортогонализация соответствует повторной процедуре ортогонализациии Грама-Шмидта для обеспечения ортогональности вектора <math>z</math> векторам <math>q_1, ..., q_k</math>. В случае идеально точной арифметики данная переортогонализация не требовалась бы, однако в реальных вычислениях ошибки округления приводят к потере ортогональности, в связи с чем требуется переортогонализация.
Однако, единственной проблемой, возникающей при отсутствии переортогонализации, является появление повторных копий чисел Ритца (собственных значений), что в случае, если не требуется установление кратностей собственных значений, допустимо.

= ЧАСТЬ. Программная реализация алгоритма =

== Особенности реализации последовательного алгоритма ==

== [[Локальность данных и вычислений]] ==

== Возможные способы и особенности параллельной реализации алгоритма ==

== Масштабируемость алгоритма и его реализации ==

== Динамические характеристики и эффективность реализации алгоритма ==

== Выводы для классов архитектур ==

== Существующие реализации алгоритма ==

= Литература =
[1] Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. - СПб.: БХВ-Петербург, 2002. - 608 с.

[2] Воеводин В.В., Воеводин Вад.В. Спасительная локальность суперкомпьютеров //Открытые системы. - 2013. - № 9. - С. 12-15.

[3] Воеводин Вад.В., Швец П. Метод покрытий для оценки локальности использования данных в программах // Вестник УГАТУ. — 2014. — Т. 18, № 1(62). — С. 224–229.

[4] Антонов А.С., Теплов А.М. О практической сложности понятия масштабируемости параллельных программ// Высокопроизводительные параллельные вычисления на кластерных системах (HPC 2014): Материалы XIV Международной конференции -Пермь: Издательство ПНИПУ, 2014. С. 20-27.

[5] Никитенко Д.А. Комплексный анализ производительности суперкомпьютерных систем, основанный на данных системного мониторинга // Вычислительные методы и программирование. 2014. 15. 85–97.

Участник:Error0x0/Алгоритм Ланцоша для арифметики с плавающей точкой с полной переортогонализацией

2016-10-15T19:37:48Z

Error0x0: /* Схема реализации последовательного алгоритма */

= ЧАСТЬ. Свойства и структура алгоритмов =

== Общее описание алгоритма ==
Алгоритм Ланцоша представляет собой итерационный алгоритм для вычисления собственных значений симметрической матрицы.
Идея алгоритма заключается в построении матрицы <math>Q_k = [q_1, ..., q_k]</math> из ортонормированных векторов Ланцоша и нахождении собственных значений трёхдиагональной матрицы <math>T_k = Q_k^T A Q_k</math>.

== Математическое описание алгоритма ==
Пусть дана матрица <math>A</math>.
Пусть <math>q_1 = b/||b||_2, \beta_0=0, q_0=0</math>
Алгоритм производит <math>k</math> итераций на каждой из которых:
# вычисляется <math>z = Aq_j</math>,
# производится переортогонализация <math>z = z - \sum^{j-1}_{i=1} {(z^T q_i)q_i}</math>,
# <math>\beta_j = ||z||_2</math>, если <math>\beta_j = 0</math>, алгоритм останавливается,
# <math>q_j+1 = z/\beta_j</math>,
# вычисляются собственные значения и векторы матрицы <math>T_j = Q_j^T A Q_j</math>.

== Вычислительное ядро алгоритма ==
Основной вклад в сложность алгоритма даёт полная переортогонализация

== Макроструктура алгоритма ==
Основные элементы алгоритма:
* Нахождение векторов Ланцоша
* Полная переортогонализация (Грамма-Шмидта)
* Вычисление собственных значений и векторов матрицы <math>T_j</math> (числа Ритца)

== Схема реализации последовательного алгоритма ==
<syntaxhighlight lang="python">
q[1] = b / norm(b)
beta[0] = 0
q[0] = 0
for j in [1 .. k]:
z = mul(A, q[j])
z_fixed = z
for i in [1 .. j - 1]:
z -= mul(scalar_mul(transpose(z_fixed),q[i]), q[i])
beta[j] = norm(z)
if beta[j] == 0:
break
result = ritz_numbers(mul(transpose(Q[j]), A, Q[j]))
return result
</syntaxhighlight>

== Последовательная сложность алгоритма ==
Для метода с полной переортогонализацией сложность составляет <math>O(k^2 n)</math>, сложность по памяти -- <math>O(kn)</math>.

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

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

== Входные и выходные данные алгоритма ==
'''Входные данны'''е: квадратная симметрическая матрица <math>A</math> порядка <math>n</math>
'''Объём входных данных''': <math>n^2</math>
'''Выходные данные''': собственные числа матрицы
'''Объём выходных данных''': <math>n</math>

== Свойства алгоритма ==
Полная переортогонализация соответствует повторной процедуре ортогонализациии Грама-Шмидта для обеспечения ортогональности вектора <math>z</math> векторам <math>q_1, ..., q_k</math>. В случае идеально точной арифметики данная переортогонализация не требовалась бы, однако в реальных вычислениях ошибки округления приводят к потере ортогональности, в связи с чем требуется переортогонализация.
Однако, единственной проблемой, возникающей при отсутствии переортогонализации, является появление повторных копий чисел Ритца (собственных значений), что в случае, если не требуется установление кратностей собственных значений, допустимо.

= ЧАСТЬ. Программная реализация алгоритма =

== Особенности реализации последовательного алгоритма ==

== [[Локальность данных и вычислений]] ==

== Возможные способы и особенности параллельной реализации алгоритма ==

== Масштабируемость алгоритма и его реализации ==

== Динамические характеристики и эффективность реализации алгоритма ==

== Выводы для классов архитектур ==

== Существующие реализации алгоритма ==

= Литература =
[1] Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. - СПб.: БХВ-Петербург, 2002. - 608 с.

[2] Воеводин В.В., Воеводин Вад.В. Спасительная локальность суперкомпьютеров //Открытые системы. - 2013. - № 9. - С. 12-15.

[3] Воеводин Вад.В., Швец П. Метод покрытий для оценки локальности использования данных в программах // Вестник УГАТУ. — 2014. — Т. 18, № 1(62). — С. 224–229.

[4] Антонов А.С., Теплов А.М. О практической сложности понятия масштабируемости параллельных программ// Высокопроизводительные параллельные вычисления на кластерных системах (HPC 2014): Материалы XIV Международной конференции -Пермь: Издательство ПНИПУ, 2014. С. 20-27.

[5] Никитенко Д.А. Комплексный анализ производительности суперкомпьютерных систем, основанный на данных системного мониторинга // Вычислительные методы и программирование. 2014. 15. 85–97.

Участник:Error0x0/Алгоритм Ланцоша для арифметики с плавающей точкой с полной переортогонализацией

2016-10-15T19:35:22Z

Error0x0: /* Математическое описание алгоритма */

= ЧАСТЬ. Свойства и структура алгоритмов =

== Общее описание алгоритма ==
Алгоритм Ланцоша представляет собой итерационный алгоритм для вычисления собственных значений симметрической матрицы.
Идея алгоритма заключается в построении матрицы <math>Q_k = [q_1, ..., q_k]</math> из ортонормированных векторов Ланцоша и нахождении собственных значений трёхдиагональной матрицы <math>T_k = Q_k^T A Q_k</math>.

== Математическое описание алгоритма ==
Пусть дана матрица <math>A</math>.
Пусть <math>q_1 = b/||b||_2, \beta_0=0, q_0=0</math>
Алгоритм производит <math>k</math> итераций на каждой из которых:
# вычисляется <math>z = Aq_j</math>,
# производится переортогонализация <math>z = z - \sum^{j-1}_{i=1} {(z^T q_i)q_i}</math>,
# <math>\beta_j = ||z||_2</math>, если <math>\beta_j = 0</math>, алгоритм останавливается,
# <math>q_j+1 = z/\beta_j</math>,
# вычисляются собственные значения и векторы матрицы <math>T_j = Q_j^T A Q_j</math>.

== Вычислительное ядро алгоритма ==
Основной вклад в сложность алгоритма даёт полная переортогонализация

== Макроструктура алгоритма ==
Основные элементы алгоритма:
* Нахождение векторов Ланцоша
* Полная переортогонализация (Грамма-Шмидта)
* Вычисление собственных значений и векторов матрицы <math>T_j</math> (числа Ритца)

== Схема реализации последовательного алгоритма ==
<syntaxhighlight lang="python">
q[1] = b / norm(b)
beta[0] = 0
q[0] = 0
for j in [1 .. k]:
z = mul(A, q[j])
for i in [1 .. j - 1]:
z -= mul(scalar_mul(transpose(z),q[i]), q[i])
beta[j] = norm(z)
if beta[j] == 0:
break
result = ritz_numbers(mul(transpose(Q[j]), A, Q[j]))
return result
</syntaxhighlight>

== Последовательная сложность алгоритма ==
Для метода с полной переортогонализацией сложность составляет <math>O(k^2 n)</math>, сложность по памяти -- <math>O(kn)</math>.

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

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

== Входные и выходные данные алгоритма ==
'''Входные данны'''е: квадратная симметрическая матрица <math>A</math> порядка <math>n</math>
'''Объём входных данных''': <math>n^2</math>
'''Выходные данные''': собственные числа матрицы
'''Объём выходных данных''': <math>n</math>

== Свойства алгоритма ==
Полная переортогонализация соответствует повторной процедуре ортогонализациии Грама-Шмидта для обеспечения ортогональности вектора <math>z</math> векторам <math>q_1, ..., q_k</math>. В случае идеально точной арифметики данная переортогонализация не требовалась бы, однако в реальных вычислениях ошибки округления приводят к потере ортогональности, в связи с чем требуется переортогонализация.
Однако, единственной проблемой, возникающей при отсутствии переортогонализации, является появление повторных копий чисел Ритца (собственных значений), что в случае, если не требуется установление кратностей собственных значений, допустимо.

= ЧАСТЬ. Программная реализация алгоритма =

== Особенности реализации последовательного алгоритма ==

== [[Локальность данных и вычислений]] ==

== Возможные способы и особенности параллельной реализации алгоритма ==

== Масштабируемость алгоритма и его реализации ==

== Динамические характеристики и эффективность реализации алгоритма ==

== Выводы для классов архитектур ==

== Существующие реализации алгоритма ==

= Литература =
[1] Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. - СПб.: БХВ-Петербург, 2002. - 608 с.

[2] Воеводин В.В., Воеводин Вад.В. Спасительная локальность суперкомпьютеров //Открытые системы. - 2013. - № 9. - С. 12-15.

[3] Воеводин Вад.В., Швец П. Метод покрытий для оценки локальности использования данных в программах // Вестник УГАТУ. — 2014. — Т. 18, № 1(62). — С. 224–229.

[4] Антонов А.С., Теплов А.М. О практической сложности понятия масштабируемости параллельных программ// Высокопроизводительные параллельные вычисления на кластерных системах (HPC 2014): Материалы XIV Международной конференции -Пермь: Издательство ПНИПУ, 2014. С. 20-27.

[5] Никитенко Д.А. Комплексный анализ производительности суперкомпьютерных систем, основанный на данных системного мониторинга // Вычислительные методы и программирование. 2014. 15. 85–97.

Участник:Error0x0/Алгоритм Ланцоша для арифметики с плавающей точкой с полной переортогонализацией

2016-10-15T19:34:39Z

Error0x0: /* Математическое описание алгоритма */

= ЧАСТЬ. Свойства и структура алгоритмов =

== Общее описание алгоритма ==
Алгоритм Ланцоша представляет собой итерационный алгоритм для вычисления собственных значений симметрической матрицы.
Идея алгоритма заключается в построении матрицы <math>Q_k = [q_1, ..., q_k]</math> из ортонормированных векторов Ланцоша и нахождении собственных значений трёхдиагональной матрицы <math>T_k = Q_k^T A Q_k</math>.

== Математическое описание алгоритма ==
Пусть дана матрица <math>A</math>.
Пусть <math>q_1 = b/||b||_2, \beta_0=0, q_0=0</math>
Алгоритм производит <math>k</math> итераций на каждой из которых:
# вычисляются <math>z = Aq_j</math>,
# производится переортогонализация <math>z = z - \sum^{j-1}_{i=1} {(z^T q_i)q_i}</math>,
# <math>\beta_j = ||z||_2</math>, если <math>\beta_j = 0</math>, алгоритм останавливается,
# <math>q_j+1 = z/\beta_j</math>,
# вычисляются собственные значения и векторы матрицы <math>T_j = Q_j^T A Q_j</math>.

== Вычислительное ядро алгоритма ==
Основной вклад в сложность алгоритма даёт полная переортогонализация

== Макроструктура алгоритма ==
Основные элементы алгоритма:
* Нахождение векторов Ланцоша
* Полная переортогонализация (Грамма-Шмидта)
* Вычисление собственных значений и векторов матрицы <math>T_j</math> (числа Ритца)

== Схема реализации последовательного алгоритма ==
<syntaxhighlight lang="python">
q[1] = b / norm(b)
beta[0] = 0
q[0] = 0
for j in [1 .. k]:
z = mul(A, q[j])
for i in [1 .. j - 1]:
z -= mul(scalar_mul(transpose(z),q[i]), q[i])
beta[j] = norm(z)
if beta[j] == 0:
break
result = ritz_numbers(mul(transpose(Q[j]), A, Q[j]))
return result
</syntaxhighlight>

== Последовательная сложность алгоритма ==
Для метода с полной переортогонализацией сложность составляет <math>O(k^2 n)</math>, сложность по памяти -- <math>O(kn)</math>.

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

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

== Входные и выходные данные алгоритма ==
'''Входные данны'''е: квадратная симметрическая матрица <math>A</math> порядка <math>n</math>
'''Объём входных данных''': <math>n^2</math>
'''Выходные данные''': собственные числа матрицы
'''Объём выходных данных''': <math>n</math>

== Свойства алгоритма ==
Полная переортогонализация соответствует повторной процедуре ортогонализациии Грама-Шмидта для обеспечения ортогональности вектора <math>z</math> векторам <math>q_1, ..., q_k</math>. В случае идеально точной арифметики данная переортогонализация не требовалась бы, однако в реальных вычислениях ошибки округления приводят к потере ортогональности, в связи с чем требуется переортогонализация.
Однако, единственной проблемой, возникающей при отсутствии переортогонализации, является появление повторных копий чисел Ритца (собственных значений), что в случае, если не требуется установление кратностей собственных значений, допустимо.

= ЧАСТЬ. Программная реализация алгоритма =

== Особенности реализации последовательного алгоритма ==

== [[Локальность данных и вычислений]] ==

== Возможные способы и особенности параллельной реализации алгоритма ==

== Масштабируемость алгоритма и его реализации ==

== Динамические характеристики и эффективность реализации алгоритма ==

== Выводы для классов архитектур ==

== Существующие реализации алгоритма ==

= Литература =
[1] Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. - СПб.: БХВ-Петербург, 2002. - 608 с.

[2] Воеводин В.В., Воеводин Вад.В. Спасительная локальность суперкомпьютеров //Открытые системы. - 2013. - № 9. - С. 12-15.

[3] Воеводин Вад.В., Швец П. Метод покрытий для оценки локальности использования данных в программах // Вестник УГАТУ. — 2014. — Т. 18, № 1(62). — С. 224–229.

[4] Антонов А.С., Теплов А.М. О практической сложности понятия масштабируемости параллельных программ// Высокопроизводительные параллельные вычисления на кластерных системах (HPC 2014): Материалы XIV Международной конференции -Пермь: Издательство ПНИПУ, 2014. С. 20-27.

[5] Никитенко Д.А. Комплексный анализ производительности суперкомпьютерных систем, основанный на данных системного мониторинга // Вычислительные методы и программирование. 2014. 15. 85–97.

Участник:Error0x0/Алгоритм Ланцоша для арифметики с плавающей точкой с полной переортогонализацией

2016-10-15T19:34:08Z

Error0x0: /* Математическое описание алгоритма */

= ЧАСТЬ. Свойства и структура алгоритмов =

== Общее описание алгоритма ==
Алгоритм Ланцоша представляет собой итерационный алгоритм для вычисления собственных значений симметрической матрицы.
Идея алгоритма заключается в построении матрицы <math>Q_k = [q_1, ..., q_k]</math> из ортонормированных векторов Ланцоша и нахождении собственных значений трёхдиагональной матрицы <math>T_k = Q_k^T A Q_k</math>.

== Математическое описание алгоритма ==
Пусть дана матрица <math>A</math>.
Пусть <math>q_1 = b/||b||_2, \beta_0=0, q_0=0</math>
Алгоритм производит <math>k</math> итераций на каждой из которых:
# вычисляются <math>z = Aq_j</math>,
# производится переортогонализация <math>z = z - \sum^j-1 _i=1 {(z^T q_i)q_i}</math>,
# <math>\beta_j = ||z||_2</math>, если <math>\beta_j = 0</math>, алгоритм останавливается,
# <math>q_j+1 = z/\beta_j</math>,
# вычисляются собственные значения и векторы матрицы <math>T_j = Q_j^T A Q_j</math>.

== Вычислительное ядро алгоритма ==
Основной вклад в сложность алгоритма даёт полная переортогонализация

== Макроструктура алгоритма ==
Основные элементы алгоритма:
* Нахождение векторов Ланцоша
* Полная переортогонализация (Грамма-Шмидта)
* Вычисление собственных значений и векторов матрицы <math>T_j</math> (числа Ритца)

== Схема реализации последовательного алгоритма ==
<syntaxhighlight lang="python">
q[1] = b / norm(b)
beta[0] = 0
q[0] = 0
for j in [1 .. k]:
z = mul(A, q[j])
for i in [1 .. j - 1]:
z -= mul(scalar_mul(transpose(z),q[i]), q[i])
beta[j] = norm(z)
if beta[j] == 0:
break
result = ritz_numbers(mul(transpose(Q[j]), A, Q[j]))
return result
</syntaxhighlight>

== Последовательная сложность алгоритма ==
Для метода с полной переортогонализацией сложность составляет <math>O(k^2 n)</math>, сложность по памяти -- <math>O(kn)</math>.

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

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

== Входные и выходные данные алгоритма ==
'''Входные данны'''е: квадратная симметрическая матрица <math>A</math> порядка <math>n</math>
'''Объём входных данных''': <math>n^2</math>
'''Выходные данные''': собственные числа матрицы
'''Объём выходных данных''': <math>n</math>

== Свойства алгоритма ==
Полная переортогонализация соответствует повторной процедуре ортогонализациии Грама-Шмидта для обеспечения ортогональности вектора <math>z</math> векторам <math>q_1, ..., q_k</math>. В случае идеально точной арифметики данная переортогонализация не требовалась бы, однако в реальных вычислениях ошибки округления приводят к потере ортогональности, в связи с чем требуется переортогонализация.
Однако, единственной проблемой, возникающей при отсутствии переортогонализации, является появление повторных копий чисел Ритца (собственных значений), что в случае, если не требуется установление кратностей собственных значений, допустимо.

= ЧАСТЬ. Программная реализация алгоритма =

== Особенности реализации последовательного алгоритма ==

== [[Локальность данных и вычислений]] ==

== Возможные способы и особенности параллельной реализации алгоритма ==

== Масштабируемость алгоритма и его реализации ==

== Динамические характеристики и эффективность реализации алгоритма ==

== Выводы для классов архитектур ==

== Существующие реализации алгоритма ==

= Литература =
[1] Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. - СПб.: БХВ-Петербург, 2002. - 608 с.

[2] Воеводин В.В., Воеводин Вад.В. Спасительная локальность суперкомпьютеров //Открытые системы. - 2013. - № 9. - С. 12-15.

[3] Воеводин Вад.В., Швец П. Метод покрытий для оценки локальности использования данных в программах // Вестник УГАТУ. — 2014. — Т. 18, № 1(62). — С. 224–229.

[4] Антонов А.С., Теплов А.М. О практической сложности понятия масштабируемости параллельных программ// Высокопроизводительные параллельные вычисления на кластерных системах (HPC 2014): Материалы XIV Международной конференции -Пермь: Издательство ПНИПУ, 2014. С. 20-27.

[5] Никитенко Д.А. Комплексный анализ производительности суперкомпьютерных систем, основанный на данных системного мониторинга // Вычислительные методы и программирование. 2014. 15. 85–97.

Участник:Error0x0/Алгоритм Ланцоша для арифметики с плавающей точкой с полной переортогонализацией

2016-10-15T19:33:03Z

Error0x0: /* Математическое описание алгоритма */

= ЧАСТЬ. Свойства и структура алгоритмов =

== Общее описание алгоритма ==
Алгоритм Ланцоша представляет собой итерационный алгоритм для вычисления собственных значений симметрической матрицы.
Идея алгоритма заключается в построении матрицы <math>Q_k = [q_1, ..., q_k]</math> из ортонормированных векторов Ланцоша и нахождении собственных значений трёхдиагональной матрицы <math>T_k = Q_k^T A Q_k</math>.

== Математическое описание алгоритма ==
Пусть дана матрица <math>A</math>.
Пусть <math>q_1 = b/||b||_2, \beta_0=0, q_0=0</math>
Алгоритм производит <math>k</math> итераций на каждой из которых:
# вычисляются <math>z = Aq_j</math>,
# производится переортогонализация <math>z = z - \sum ^j-1 _i=1 {(z^T q_i)q_i}</math>,
# <math>\beta_j = ||z||_2</math>, если <math>\beta_j = 0</math>, алгоритм останавливается,
# <math>q_j+1 = z/\beta_j</math>,
# вычисляются собственные значения и векторы матрицы <math>T_j = Q_j^T A Q_j</math>.

== Вычислительное ядро алгоритма ==
Основной вклад в сложность алгоритма даёт полная переортогонализация

== Макроструктура алгоритма ==
Основные элементы алгоритма:
* Нахождение векторов Ланцоша
* Полная переортогонализация (Грамма-Шмидта)
* Вычисление собственных значений и векторов матрицы <math>T_j</math> (числа Ритца)

== Схема реализации последовательного алгоритма ==
<syntaxhighlight lang="python">
q[1] = b / norm(b)
beta[0] = 0
q[0] = 0
for j in [1 .. k]:
z = mul(A, q[j])
for i in [1 .. j - 1]:
z -= mul(scalar_mul(transpose(z),q[i]), q[i])
beta[j] = norm(z)
if beta[j] == 0:
break
result = ritz_numbers(mul(transpose(Q[j]), A, Q[j]))
return result
</syntaxhighlight>

== Последовательная сложность алгоритма ==
Для метода с полной переортогонализацией сложность составляет <math>O(k^2 n)</math>, сложность по памяти -- <math>O(kn)</math>.

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

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

== Входные и выходные данные алгоритма ==
'''Входные данны'''е: квадратная симметрическая матрица <math>A</math> порядка <math>n</math>
'''Объём входных данных''': <math>n^2</math>
'''Выходные данные''': собственные числа матрицы
'''Объём выходных данных''': <math>n</math>

== Свойства алгоритма ==
Полная переортогонализация соответствует повторной процедуре ортогонализациии Грама-Шмидта для обеспечения ортогональности вектора <math>z</math> векторам <math>q_1, ..., q_k</math>. В случае идеально точной арифметики данная переортогонализация не требовалась бы, однако в реальных вычислениях ошибки округления приводят к потере ортогональности, в связи с чем требуется переортогонализация.
Однако, единственной проблемой, возникающей при отсутствии переортогонализации, является появление повторных копий чисел Ритца (собственных значений), что в случае, если не требуется установление кратностей собственных значений, допустимо.

= ЧАСТЬ. Программная реализация алгоритма =

== Особенности реализации последовательного алгоритма ==

== [[Локальность данных и вычислений]] ==

== Возможные способы и особенности параллельной реализации алгоритма ==

== Масштабируемость алгоритма и его реализации ==

== Динамические характеристики и эффективность реализации алгоритма ==

== Выводы для классов архитектур ==

== Существующие реализации алгоритма ==

= Литература =
[1] Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. - СПб.: БХВ-Петербург, 2002. - 608 с.

[2] Воеводин В.В., Воеводин Вад.В. Спасительная локальность суперкомпьютеров //Открытые системы. - 2013. - № 9. - С. 12-15.

[3] Воеводин Вад.В., Швец П. Метод покрытий для оценки локальности использования данных в программах // Вестник УГАТУ. — 2014. — Т. 18, № 1(62). — С. 224–229.

[4] Антонов А.С., Теплов А.М. О практической сложности понятия масштабируемости параллельных программ// Высокопроизводительные параллельные вычисления на кластерных системах (HPC 2014): Материалы XIV Международной конференции -Пермь: Издательство ПНИПУ, 2014. С. 20-27.

[5] Никитенко Д.А. Комплексный анализ производительности суперкомпьютерных систем, основанный на данных системного мониторинга // Вычислительные методы и программирование. 2014. 15. 85–97.

Участник:Error0x0/Алгоритм Ланцоша для арифметики с плавающей точкой с полной переортогонализацией

2016-10-15T19:32:13Z

Error0x0: /* Математическое описание алгоритма */

= ЧАСТЬ. Свойства и структура алгоритмов =

== Общее описание алгоритма ==
Алгоритм Ланцоша представляет собой итерационный алгоритм для вычисления собственных значений симметрической матрицы.
Идея алгоритма заключается в построении матрицы <math>Q_k = [q_1, ..., q_k]</math> из ортонормированных векторов Ланцоша и нахождении собственных значений трёхдиагональной матрицы <math>T_k = Q_k^T A Q_k</math>.

== Математическое описание алгоритма ==
Пусть дана матрица <math>A</math>.
Пусть <math>q_1 = b/||b||_2, \beta_0=0, q_0=0</math>
Алгоритм производит <math>k</math> итераций на каждой из которых:
# вычисляются <math>z = Aq_j,
# производится переортогонализация <math>z = z - \sum ^j-1 _i=1 {(z^T q_i)q_i}</math>,
# <math>\beta_j = ||z||_2</math>, если <math>\beta_j = 0</math>, алгоритм останавливается,
# <math>q_j+1 = z/\beta_j</math>,
# вычисляются собственные значения и векторы матрицы <math>T_j = Q_j^T A Q_j</math>.

== Вычислительное ядро алгоритма ==
Основной вклад в сложность алгоритма даёт полная переортогонализация

== Макроструктура алгоритма ==
Основные элементы алгоритма:
* Нахождение векторов Ланцоша
* Полная переортогонализация (Грамма-Шмидта)
* Вычисление собственных значений и векторов матрицы <math>T_j</math> (числа Ритца)

== Схема реализации последовательного алгоритма ==
<syntaxhighlight lang="python">
q[1] = b / norm(b)
beta[0] = 0
q[0] = 0
for j in [1 .. k]:
z = mul(A, q[j])
for i in [1 .. j - 1]:
z -= mul(scalar_mul(transpose(z),q[i]), q[i])
beta[j] = norm(z)
if beta[j] == 0:
break
result = ritz_numbers(mul(transpose(Q[j]), A, Q[j]))
return result
</syntaxhighlight>

== Последовательная сложность алгоритма ==
Для метода с полной переортогонализацией сложность составляет <math>O(k^2 n)</math>, сложность по памяти -- <math>O(kn)</math>.

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

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

== Входные и выходные данные алгоритма ==
'''Входные данны'''е: квадратная симметрическая матрица <math>A</math> порядка <math>n</math>
'''Объём входных данных''': <math>n^2</math>
'''Выходные данные''': собственные числа матрицы
'''Объём выходных данных''': <math>n</math>

== Свойства алгоритма ==
Полная переортогонализация соответствует повторной процедуре ортогонализациии Грама-Шмидта для обеспечения ортогональности вектора <math>z</math> векторам <math>q_1, ..., q_k</math>. В случае идеально точной арифметики данная переортогонализация не требовалась бы, однако в реальных вычислениях ошибки округления приводят к потере ортогональности, в связи с чем требуется переортогонализация.
Однако, единственной проблемой, возникающей при отсутствии переортогонализации, является появление повторных копий чисел Ритца (собственных значений), что в случае, если не требуется установление кратностей собственных значений, допустимо.

= ЧАСТЬ. Программная реализация алгоритма =

== Особенности реализации последовательного алгоритма ==

== [[Локальность данных и вычислений]] ==

== Возможные способы и особенности параллельной реализации алгоритма ==

== Масштабируемость алгоритма и его реализации ==

== Динамические характеристики и эффективность реализации алгоритма ==

== Выводы для классов архитектур ==

== Существующие реализации алгоритма ==

= Литература =
[1] Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. - СПб.: БХВ-Петербург, 2002. - 608 с.

[2] Воеводин В.В., Воеводин Вад.В. Спасительная локальность суперкомпьютеров //Открытые системы. - 2013. - № 9. - С. 12-15.

[3] Воеводин Вад.В., Швец П. Метод покрытий для оценки локальности использования данных в программах // Вестник УГАТУ. — 2014. — Т. 18, № 1(62). — С. 224–229.

[4] Антонов А.С., Теплов А.М. О практической сложности понятия масштабируемости параллельных программ// Высокопроизводительные параллельные вычисления на кластерных системах (HPC 2014): Материалы XIV Международной конференции -Пермь: Издательство ПНИПУ, 2014. С. 20-27.

[5] Никитенко Д.А. Комплексный анализ производительности суперкомпьютерных систем, основанный на данных системного мониторинга // Вычислительные методы и программирование. 2014. 15. 85–97.

Участник:Error0x0/Алгоритм Ланцоша для арифметики с плавающей точкой с полной переортогонализацией

2016-10-15T19:29:11Z

Error0x0: /* Свойства алгоритма */

= ЧАСТЬ. Свойства и структура алгоритмов =

== Общее описание алгоритма ==
Алгоритм Ланцоша представляет собой итерационный алгоритм для вычисления собственных значений симметрической матрицы.
Идея алгоритма заключается в построении матрицы <math>Q_k = [q_1, ..., q_k]</math> из ортонормированных векторов Ланцоша и нахождении собственных значений трёхдиагональной матрицы <math>T_k = Q_k^T A Q_k</math>.

== Математическое описание алгоритма ==
Пусть дана матрица <math>A</math>.
Пусть <math>q_1 = b/||b||_2, \beta_0=0, q_0=0</math>
Алгоритм производит <math>k</math> итераций на каждой из которых:
# вычисляются <math>z = Aq_j, \alpha_j = q_j^T z</math>,
# производится переортогонализация <math>z = z - \sum ^j-1 _i=1 {(z^T q_i)q_i}</math>
# <math>\beta_j = ||z||_2</math>, если <math>\beta_j = 0</math>, алгоритм останавливается
# <math>q_j+1 = z/\beta_j</math>
# вычисляются собственные значения и векторы матрицы <math>T_j = Q_j^T A Q_j</math>

== Вычислительное ядро алгоритма ==
Основной вклад в сложность алгоритма даёт полная переортогонализация

== Макроструктура алгоритма ==
Основные элементы алгоритма:
* Нахождение векторов Ланцоша
* Полная переортогонализация (Грамма-Шмидта)
* Вычисление собственных значений и векторов матрицы <math>T_j</math> (числа Ритца)

== Схема реализации последовательного алгоритма ==
<syntaxhighlight lang="python">
q[1] = b / norm(b)
beta[0] = 0
q[0] = 0
for j in [1 .. k]:
z = mul(A, q[j])
for i in [1 .. j - 1]:
z -= mul(scalar_mul(transpose(z),q[i]), q[i])
beta[j] = norm(z)
if beta[j] == 0:
break
result = ritz_numbers(mul(transpose(Q[j]), A, Q[j]))
return result
</syntaxhighlight>

== Последовательная сложность алгоритма ==
Для метода с полной переортогонализацией сложность составляет <math>O(k^2 n)</math>, сложность по памяти -- <math>O(kn)</math>.

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

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

== Входные и выходные данные алгоритма ==
'''Входные данны'''е: квадратная симметрическая матрица <math>A</math> порядка <math>n</math>
'''Объём входных данных''': <math>n^2</math>
'''Выходные данные''': собственные числа матрицы
'''Объём выходных данных''': <math>n</math>

== Свойства алгоритма ==
Полная переортогонализация соответствует повторной процедуре ортогонализациии Грама-Шмидта для обеспечения ортогональности вектора <math>z</math> векторам <math>q_1, ..., q_k</math>. В случае идеально точной арифметики данная переортогонализация не требовалась бы, однако в реальных вычислениях ошибки округления приводят к потере ортогональности, в связи с чем требуется переортогонализация.
Однако, единственной проблемой, возникающей при отсутствии переортогонализации, является появление повторных копий чисел Ритца (собственных значений), что в случае, если не требуется установление кратностей собственных значений, допустимо.

= ЧАСТЬ. Программная реализация алгоритма =

== Особенности реализации последовательного алгоритма ==

== [[Локальность данных и вычислений]] ==

== Возможные способы и особенности параллельной реализации алгоритма ==

== Масштабируемость алгоритма и его реализации ==

== Динамические характеристики и эффективность реализации алгоритма ==

== Выводы для классов архитектур ==

== Существующие реализации алгоритма ==

= Литература =
[1] Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. - СПб.: БХВ-Петербург, 2002. - 608 с.

[2] Воеводин В.В., Воеводин Вад.В. Спасительная локальность суперкомпьютеров //Открытые системы. - 2013. - № 9. - С. 12-15.

[3] Воеводин Вад.В., Швец П. Метод покрытий для оценки локальности использования данных в программах // Вестник УГАТУ. — 2014. — Т. 18, № 1(62). — С. 224–229.

[4] Антонов А.С., Теплов А.М. О практической сложности понятия масштабируемости параллельных программ// Высокопроизводительные параллельные вычисления на кластерных системах (HPC 2014): Материалы XIV Международной конференции -Пермь: Издательство ПНИПУ, 2014. С. 20-27.

[5] Никитенко Д.А. Комплексный анализ производительности суперкомпьютерных систем, основанный на данных системного мониторинга // Вычислительные методы и программирование. 2014. 15. 85–97.

Участник:Error0x0/Алгоритм Ланцоша для арифметики с плавающей точкой с полной переортогонализацией

2016-10-15T19:19:01Z

Error0x0: /* Входные и выходные данные алгоритма */

Участник:Error0x0/Алгоритм Ланцоша для арифметики с плавающей точкой с полной переортогонализацией

2016-10-15T18:53:23Z

Error0x0: /* Последовательная сложность алгоритма */

Участник:Error0x0/Алгоритм Ланцоша для арифметики с плавающей точкой с полной переортогонализацией

2016-10-15T18:53:07Z

Error0x0: /* Последовательная сложность алгоритма */

Участник:Error0x0/Алгоритм Ланцоша для арифметики с плавающей точкой с полной переортогонализацией

2016-10-15T18:51:34Z

Error0x0: /* Схема реализации последовательного алгоритма */