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

Материал из Алговики
Перейти к навигации Перейти к поиску
[непроверенная версия][выверенная версия]
м (Отмена правки 12046, сделанной участником Nikita270a (обс.))
Строка 1: Строка 1:
−
{{algorithm
+
{{Main page}}
−
| name              = Алгоритм Ланцоша с полной переортогонализацией
 
−
| serial_complexity = <math>O(n^2)</math>
 
−
| pf_height        = <math>O(k)</math>
 
−
| pf_width          = <math>O(n^2)</math>
 
−
| input_data        = <math>\frac{n(n + 1)}{2}</math>
 
−
| output_data      = <math>k(n + 1)</math>
 
−
}}
 
  
 +
__NOTOC__
  
−
 
+
[[en: Open Encyclopedia of Parallel Algorithmic Features]]
−
== Общее описание алгоритма. ==
 
−
 
 
−
Алгоритм Ланцоша ищет собвственные значения и собственные векторы для симетричной матрицы A вещественных чисел. Является итерацонным алгоритмом. Алгоритм Ланцоша использует степенной метод (<math> b_{k+1} = \frac{Ab_k}{||Ab_k||} </math>) для поиска наибольших собственных значений и векторов матриц. 
 
−
 
 
−
В отличие от прямых алгоритмов требует мешьше памяти и мощности, что является несомненным плюсом для больших матриц.
 
−
 
 
−
Несмотря на свою скорость работы и экономию памяти, сначала не был популярным алгоритмом из – за недостаточной вычислительной устойчивости. В 1970 году Ojalvo и Newman показали способ сделать алгоритм достаточно устойчивым. В этой же статье алгоритм был применен к расчету инженерной конструкции с большим количеством узлов, которые подвергались динамической нагрузке.
 
−
 
 
−
 
 
−
== Математическое описание алгоритма ==
 
−
 
 
−
Памятка:
 
−
Степенной метод нахождения наибольшего собственного числа матрицы можно сформулировать в предельном виде: если <math> b_0 </math> – случайный вектор, и <math> b_n+1 = Ab_n </math>, тогда для больших чисел n предел <math>x_n/||x_n|| </math> стремится к нормированному наибольшему собственному вектору.
 
−
 
 
−
Алгоритм Ланцоша комбинирует метод Ланцоша для нахождения крыловского подпространства и метод Релэя – Ритца.
 
−
 
 
−
Подпространство Крылова для степенного метода:
 
−
<math> K_m(v,A) = span[x_1, Ax_1, A^2x_1, ..., A^{k-1}x_1] </math>
 
−
 
 
−
В качестве входных данных для алгоритма Ланцоша подаются квадратная матрица размерности <math>n</math>X<math>n</math>: <math>A=A^T</math>; а так же вектор начального приближения <math>b</math>. Метод осуществляет поиск трехдиагональной симметричной матрицы <math>T_k=Q_k^TAQ_k</math>. Причем собственные значения <math>T_k</math> таковы, что приближают собственные значения исходной матрицы <math>A</math>. То есть на каждом <math>k</math>-м шаге из ортонормированных векторов Ланцоша строится матрица <math>Q_k = [q_1,q_2,...,q_k]</math> и в качестве приближенных собственных значений матрицы <math>A</math> принимаются числа Ритца. Пусть <math>T<sub>k</sub>=VAV<sup>T</sup></math> есть спектральное разложение матрицы <math>T_k</math>, столбцы матрицы <math>Q_kV</math> рассматриваются как приближения к соответсвующим собственным векторам матрицы <math>A</math><ref>Дж. Деммель «Вычислительная линейная алгебра» (стр. 391)</ref>:
 
−
 
 
−
 
 
−
== Схема ==
 
−
Input: A, b (random vector with unit norm)
 
−
: <math>
 
−
 
 
−
\begin{align}
 
−
q_1 = b/||b||_2, \beta_0 = 0, q_0 = 0 \\
 
−
for j = 1 ,...,k \\
 
−
q_1&=b/||b||,\beta_0=0,q_o=0. \\
 
−
z&=Aq_j, \\
 
−
\alpha_j&=q_j^Tz, \\
 
−
z&=z-\alpha_jq_j-\beta_{j-1}q_{j-1}, \\
 
−
\beta&=||z||,\\
 
−
q_{j+1}&=z/\beta_j, \quad j \in [1, k].
 
−
 
 
−
 
 
−
\end{align}
 
−
 
 
−
</math>
 
−
 
 
−
 
 
−
== Информационный граф ==
 
−
 
 
−
 
 
−
 
 
−
== Библиотеки реализующие алгоритм==
 
−
 
 
−
The IETL Project http://www.comp-phys.org/software/ietl/ C++
 
−
 
 
−
NAG Library http://www.nag.com/content/nag-library C, C++, Fortran, C#, MATLAB, R
 
−
 
 
−
ARPACK https://people.sc.fsu.edu/~jburkardt/m_src/arpack/arpack.html MATLAB
 
−
 
 
−
GrapLab https://turi.com/products/create/open_source.html C++
 
−
 
 
−
С частично переортаганализацией
 
−
 
 
−
LANSO/PLANSO http://web.cs.ucdavis.edu/~bai/ET/lanczos_methods/overview_PLANSO.html Fortran (уже распараллелена)
 

Версия 17:30, 18 октября 2016

Добро пожаловать! Присоединяйтесь!
AlgoWiki - это открытая энциклопедия по свойствам алгоритмов и особенностям их реализации на различных программно-аппаратных платформах от мобильных платформ до экзафлопсных суперкомпьютерных систем с возможностью коллективной работы всего мирового вычислительного сообщества.

Цель AlgoWiki - дать исчерпывающее описание алгоритма, которое поможет оценить его потенциал применительно к конкретной параллельной вычислительной платформе. Кроме классических свойств алгоритмов, например, последовательной сложности, в AlgoWiki представлены дополнительные сведения, составляющие в совокупности полную картину об алгоритме: параллельная сложность, параллельная структура, детерминированность, оценки локальности данных, эффективность и масштабируемость, коммуникационный профиль конкретных реализаций и многие другие.

Читать подробнее: О проекте
Структура проекта
Классификация алгоритмов - основной раздел AlgoWiki, содержащий описания всех алгоритмов. Алгоритмы добавляются в подходящий раздел классификации, при необходимости классификация расширяется за счет новых разделов.
Образцовая статья

Разложение Холецкого (метод квадратного корня)

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

  • Последовательная сложность алгоритма: [math]O(n^3)[/math]
  • Высота ярусно-параллельной формы: [math]O(n)[/math]
  • Ширина ярусно-параллельной формы: [math]O(n^2)[/math]
  • Объём входных данных: [math]\frac{n (n + 1)}{2}[/math]
  • Объём выходных данных: [math]\frac{n (n + 1)}{2}[/math]

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

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

Разложение Холецкого впервые предложено французским офицером и математиком Андре-Луи Холецким в конце Первой Мировой войны, незадолго до его гибели в бою в августе 1918 г. Идея этого разложения была опубликована в 1924 г. его сослуживцем. Потом оно было использовано поляком Т. Банашевичем в 1938 г. В советской математической литературе называется также методом квадратного корня [1-3]; название связано с характерными операциями, отсутствующими в родственном разложении Гаусса.

Первоначально разложение Холецкого использовалось исключительно для плотных симметричных положительно определенных матриц. В настоящее время его использование гораздо шире. Оно может быть применено также, например, к эрмитовым матрицам. Для повышения производительности вычислений часто применяется блочная версия разложения.

Для разреженных матриц разложение Холецкого также широко применяется в качестве основного этапа прямого метода решения линейных систем. В этом случае используют специальные упорядочивания для уменьшения ширины профиля исключения, а следовательно и уменьшения количества арифметических операций. Другие упорядочивания используются для выделения независимых блоков вычислений при работе на системах с параллельной организацией.

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

Исходные данные: положительно определённая симметрическая матрица [math]A[/math] (элементы [math]a_{ij}[/math]).

Вычисляемые данные: нижняя треугольная матрица [math]L[/math] (элементы [math]l_{ij}[/math]).

Формулы метода:

[math] \begin{align} l_{11} & = \sqrt{a_{11}}, \\ l_{j1} & = \frac{a_{j1}}{l_{11}}, \quad j \in [2, n], \\ l_{ii} & = \sqrt{a_{ii} - \sum_{p = 1}^{i - 1} l_{ip}^2}, \quad i \in [2, n], \\ l_{ji} & = \left (a_{ji} - \sum_{p = 1}^{i - 1} l_{ip} l_{jp} \right ) / l_{ii}, \quad i \in [2, n - 1], j \in [i + 1, n]. \end{align} [/math]

Существует также блочная версия метода, однако в данном описании разобран только точечный метод.

В ряде реализаций деление на диагональный элемент выполняется в два этапа: вычисление [math]1/l_{ii}[/math] и затем умножение на него всех (видоизменённых) [math]a_{ji}[/math] . Здесь мы этот вариант алгоритма не рассматриваем. Заметим только, что он имеет худшие параллельные характеристики, чем представленный.

Читать полностью…
Изображение дня
Производительность умножения плотных матриц
Участники проекта
Руководители:

Участники:

Источник — https://algowiki-project.org/w/ru/index.php?title=Открытая_энциклопедия_свойств_алгоритмов&oldid=13111