Шаблон:Main page

Добро пожаловать! Присоединяйтесь! 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] . Здесь мы этот вариант алгоритма не рассматриваем. Заметим только, что он имеет худшие параллельные характеристики, чем представленный. Читать полностью…

Изображение дня Производительность умножения плотных матриц Участники проекта Руководители: Воеводин Вл. В., член-корр. РАН, д.ф.-м.н., проф. Донгарра Дж., проф. Участники: Тыртышников Е.Е., академик, д.ф.-м.н., проф. Арушанян О.Б., д.т.н., проф. Икрамов Х.Д., д.ф.-м.н., проф. Якобовский М.В., д.ф.-м.н., проф. Смирнов А.В., д.ф.-м.н. Антонов А.С., к.ф.-м.н. Воеводин Вад.В., к.ф.-м.н. Коньшин И.Н., к.ф.-м.н. Степаненко В.М., к.ф.-м.н. Фролов А.В., к.ф.-м.н. Чернявский А.Ю., к.ф.-м.н. Теплов А.М., к.ф.-м.н. Баруздин Н.Э. Волков Н.И. Полезные ссылки Московский государственный университет имени М.В.Ломоносова Научно-исследовательский вычислительный центр МГУ имени М.В.Ломоносова Информационно-аналитический центр по параллельным вычислениям Parallel.ru Международная конференция Суперкомпьютерные дни в России Шаблон:Main page/Readiness/title Шаблон:Main page/Readiness