Шаблон: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 Участники проекта Руководители: Воеводин Вл. В., член-корр. РАН, д.ф.-м.н., проф. Донгарра Дж., проф. Участники: Тыртышников Е.Е., академик, д.ф.-м.н., проф. Арушанян О.Б., д.т.н., проф. Икрамов Х.Д., д.ф.-м.н., проф. Якобовский М.В., д.ф.-м.н., проф. Смирнов А.В., д.ф.-м.н. Антонов А.С., к.ф.-м.н. Воеводин Вад.В., к.ф.-м.н. Коньшин И.Н., к.ф.-м.н. Степаненко В.М., к.ф.-м.н. Фролов А.В., к.ф.-м.н. Чернявский А.Ю., к.ф.-м.н. Теплов А.М., к.ф.-м.н. Баруздин Н.Э. Волков Н.И.