Шаблон:Main page: различия между версиями

Материал из Алговики
Перейти к навигации Перейти к поиску
[выверенная версия][непроверенная версия]
(Удаление перевода строки.)
 
(не показано 38 промежуточных версий 2 участников)
Строка 1: Строка 1:
<div id="mainpage_topbox">
+
<div style="display: table>
<div id="mainpage_topbox_title">Бобро пожаловать!</div>
+
<div style="display: table-cell">
<div class="mainpage_boxcontents">{{Template:Main_page_about/{{{1}}}}}</div>
+
{{ blue box  | {{Main page/About/title}}    | {{Main page/About}}    | style-options=margin-bottom: 1em}}
 +
{{ blue box  | {{Main page/Structure/title}} | {{Main page/Structure}} | style-options=margin-bottom: 1em}}
 +
{{ orange box | {{Main page/Featured/title}} | {{Main page/Featured}} }}
 
</div>
 
</div>
 
+
<div style="display: table-cell; width: 1em">
{| width="100%" cellspacing="10"
 
| valign="top" class="mainpage_box" |
 
<div class="mainpage_box_title">Структура проекта</div>
 
<div class="mainpage_box_contents">
 
 
 
[[Классификация алгоритмов]]
 
 
 
[[Структура описания свойств алгоритмов]]
 
 
 
 
</div>
 
</div>
| valign="top" class="mainpage_box" |
+
<div style="display: table-cell">
<div class="mainpage_box_title">Организация работы</div>
+
{{ blue box  | {{Main page/Picture/title}}  | {{Main page/Picture}}  | style-options=margin-bottom: 1em}}
<div class="mainpage_box_contents">
+
{{ blue box  | {{Main page/Work/title}}      | {{Main page/Work}}      | style-options=margin-bottom: 1em}}
[[Глоссарий]]
+
{{ blue box  | {{Main page/Experts/title}}  | {{Main page/Experts}}  | style-options=margin-bottom: 1em}}
 
+
{{ blue box  | {{Main page/Links/title}}    | {{Main page/Links}}    }}
[[Помощь]]
 
 
 
[[Руководства|Руководства и методики]]
 
 
 
[https://www.google.ru/search?q=cats&tbm=isch Котики]
 
 
</div>
 
</div>
| valign="top" class="mainpage_box" |
+
</div><noinclude>
<div class="mainpage_box_title">Список экспертов</div>
+
[[en:Template:Main page]]
<div class="mainpage_box_contents">
+
</noinclude>
...
 
</div>
 
|}
 
 
 
{| width="100%" cellspacing="10" |
 
| valign="top" class="mainpage_box" width="80%"|
 
<div class="mainpage_box_title">Образцовая статья</div>
 
<div class="mainpage_box_contents">
 
Читать полностью [[Разложение_Холецкого_(метод_квадратного_корня)]]
 
 
 
{{:Разложение_Холецкого_(метод_квадратного_корня)_демо}}
 
</div>
 
 
 
| valign="top" class="mainpage_box"|
 
<div class="mainpage_box_title">Полезные ссылки</div>
 
<div class="mainpage_box_contents">
 
[http://parallel.ru Лаборатория Параллельных Информационных Технологий НИВЦ МГУ]
 
 
 
[http://machinelearning.ru Машинное обучение, распознавание образов и интеллектуальный анализ данных]
 
 
 
</div>
 
 
 
|}
 

Текущая версия на 17:04, 2 февраля 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] . Здесь мы этот вариант алгоритма не рассматриваем. Заметим только, что он имеет худшие параллельные характеристики, чем представленный.

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

Участники: