Метод Холецкого
Исследование метода Холецкого для СЛАУ
Разложение матриц на треугольные множители. Схема Холецкого
Если матрица системы является симметричной и положительно определенной, то для решения системы применяют метод Холецкого метод квадратных корней. Если разложение получено, то, как и в методе LU -разложения, решение системы сводится к последовательному решению двух систем с треугольными матрицами: Для нахождения коэффициентов матрицы L неизвестные коэффициенты матрицы приравнивают соответствующим элементам матрицы A. Затем последовательно находят требуемые коэффициенты по формулам:. Последовательно решаем системы и. Решением 1-ой системы является вектор , а решение 2-ой системы вектор. Студент - человек, постоянно откладывающий неизбежность Cуть методов численного интегрирования I. Методика изучения ценностных ориентаций М. Организационно-методический раздел II Основные теоретико-методологические понятия. Дисконтные методы анализа эффективности инвестиционных проектов. Метод начальных параметров II. Но предоставляет возможность бесплатного использования. Есть нарушение авторского права? Затем последовательно находят требуемые коэффициенты по формулам: Решение системы методом Холецкого. Находим элементы матрицы L: Таким образом, разложение матрицы A имеет вид:
Разложение Холецкого впервые предложено французским офицером и математиком Андре-Луи Холецким в конце Первой Мировой войны, незадолго до его гибели в бою в августе г. Идея этого разложения была опубликована в г. Потом оно было использовано поляком Т. Банашевичем [2] [3] в г. В советской математической литературе называется также методом квадратного корня [4] [5] [6] ; название связано с характерными операциями, отсутствующими в родственном разложении Гаусса. Первоначально разложение Холецкого использовалось исключительно для плотных симметричных положительно определенных матриц. В настоящее время его использование гораздо шире. Оно может быть применено также, например, к эрмитовым матрицам. Для повышения производительности вычислений часто применяется блочная версия разложения. Для разреженных матриц разложение Холецкого также широко применяется в качестве основного этапа прямого метода решения линейных систем. В этом случае используют специальные упорядочивания для уменьшения ширины профиля исключения, а следовательно и уменьшения количества арифметических операций. Другие упорядочивания используются для выделения независимых блоков вычислений при работе на системах с параллельной организацией. Варианты разложения Холецкого нашли успешные применения и в итерационных методах для построения переобусловливателей разреженных симметричных положительно определенных матриц. В зависимости от используемого порога фильтрации можно получить более точное, но и более заполненное разложение. Существует и алгоритм разложения второго порядка точности [7]. В нём при таком же заполнении множителей разложения удается улучшить точность. Для такого разложения в параллельном режиме используется специальный вариант аддитивного переобуславливания на основе разложения второго порядка [8]. На этой странице представлено исходное разложение Холецкого с новых позиций нашего суперкомпьютерного века. Приведено описание конкретной версии разложения Холецкого — для плотных вещественных симметричных положительно определённых матриц, но структура для ряда других версий, например, для комплексного случая, почти такая же, различия состоят в замене большинства вещественных операций на комплексные. Список остальных основных вариантов разложения можно посмотреть на странице Метод Холецкого нахождение симметричного треугольного разложения. Используется для разложения положительно определённых эрмитовых в вещественном случае - симметрических матриц в виде , — нижняя треугольная матрица,. Эти разложения совершенно эквивалентны друг другу по вычислениям и различаются только способом представления данных. Он заключается в реализации формул для элементов матрицы , получающихся из вышеприведённого равенства единственным образом. Получило широкое распространение благодаря следующим особенностям. Симметричность матрицы позволяет хранить и вычислять только чуть больше половины её элементов, что почти вдвое экономит как необходимые для вычислений объёмы памяти, так и количество операций в сравнении с, например, разложением по методу Гаусса. При этом альтернативное без вычисления квадратных корней LU-разложение, использующее симметрию матрицы, всё же несколько быстрее метода Холецкого не использует извлечение квадратных корней , но требует хранения всей матрицы. Благодаря тому, что разлагаемая матрица не только симметрична, но и положительно определена, её LU-разложения, в том числе и разложение методом Холецкого, имеют наименьшее эквивалентное возмущение из всех известных разложений матриц. Алгоритм позволяет использовать так называемый режим накопления , обусловленный тем, что значительную часть вычислений составляют вычисления скалярных произведений. В ряде реализаций деление на диагональный элемент выполняется в два этапа: Здесь мы этот вариант алгоритма не рассматриваем. Заметим только, что он имеет худшие параллельные характеристики, чем представленный. Вычислительное ядро последовательной версии метода Холецкого можно составить из множественных всего их вычислений скалярных произведений строк матрицы:. Во многих последовательных реализациях упомянутый способ представления не используется. Дело в том, что в них вычисление сумм типа. Поэтому следует считать вычислительным ядром метода не вычисления скалярных произведений, а вычисления выражений. Тем не менее, в популярных зарубежных реализациях точечного метода Холецкого, в частности, в библиотеках LINPACK и LAPACK, основанных на BLAS, используются именно вычисления скалярных произведений в виде вызова соответствующих подпрограмм BLAS конкретно — функции SDOT. Поэтому в данных вариантах ядром метода Холецкого будут вычисления этих скалярных произведений. Как записано и в описании ядра алгоритма , основную часть метода составляют множественные всего вычисления сумм. Далее для всех от до по нарастанию выполняются. Особо отметим, что вычисления сумм вида в обеих формулах производят в режиме накопления вычитанием из произведений для от до , c нарастанием. Для разложения матрицы порядка n методом Холецкого в последовательном наиболее быстром варианте требуется:. При классификации по последовательной сложности, таким образом, метод Холецкого относится к алгоритмам с кубической сложностью. Опишем граф алгоритма [9] [10] [11] как аналитически, так и в виде рисунка. Граф алгоритма состоит из трёх групп вершин, расположенных в целочисленных узлах трёх областей разной размерности. Первая группа вершин расположена в одномерной области, соответствующая ей операция вычисляет функцию SQRT. Единственная координата каждой из вершин меняется в диапазоне от до , принимая все целочисленные значения. Результат срабатывания операции является выходным данным. Вторая группа вершин расположена в двумерной области, соответствующая ей операция. Естественно введённые координаты области таковы:. Третья группа вершин расположена в трёхмерной области, соответствующая ей операция. Описанный граф можно посмотреть на рис. Здесь вершины первой группы обозначены жёлтым цветом и буквосочетанием sq, вершины второй — зелёным цветом и знаком деления, третьей — красным цветом и буквой f. Вершины, соответствующие операциям, производящим выходные данные алгоритма, выполнены более крупно. Дублирующие друг друга дуги даны как одна. Для разложения матрицы порядка методом Холецкого в параллельном варианте требуется последовательно выполнить следующие ярусы:. Таким образом, в параллельном варианте, в отличие от последовательного, вычисления квадратных корней и делений будут определять довольно значительную долю требуемого времени. При реализации на конкретных архитектурах наличие в отдельных ярусах ЯПФ отдельных вычислений квадратных корней может породить и другие проблемы. Таким образом, общая экономия в 2 раза, из-за которой метод Холецкого предпочитают в случае симметричных задач тому же методу Гаусса, в параллельном случае уже имеет место вовсе не по всем ресурсам, и главное - не по требуемому времени. При этом использование режима накопления требует совершения умножений и вычитаний в режиме двойной точности, а в параллельном варианте это означает, что практически все промежуточные вычисления для выполнения метода Холецкого в режиме накопления должны быть двойной точности. В отличие от последовательного варианта это означает увеличение требуемой памяти почти в 2 раза. При классификации по высоте ЯПФ, таким образом, метод Холецкого относится к алгоритмам со сложностью. При классификации по ширине ЯПФ его сложность будет. В разных реализациях эта экономия хранения может быть выполнена разным образом. Например, в библиотеке, реализованной в НИВЦ МГУ, матрица A хранилась в одномерном массиве длины по строкам своего нижнего треугольника. Например, в той же библиотеке, созданной в НИВЦ МГУ, матрица хранилась в одномерном массиве длины по строкам своей нижней части. Соотношение последовательной и параллельной сложности в случае неограниченных ресурсов, как хорошо видно, является квадратичным отношение кубической к линейной. При этом вычислительная мощность алгоритма, как отношение числа операций к суммарному объему входных и выходных данных — всего лишь линейна. При этом алгоритм почти полностью детерминирован, это гарантируется теоремой о единственности разложения. Использование другого порядка выполнения ассоциативных операций может привести к накоплению ошибок округления, однако это влияние в используемых вариантах алгоритма не так велико, как, скажем, отказ от использования режима накопления. Дуги информационного графа, исходящие из вершин, соответствующих операциям квадратного корня и деления, образуют пучки т. Наиболее известной является компактная укладка графа — его проекция на треугольник матрицы, который перевычисляется укладываемыми операциями. Эквивалентное возмущение у метода Холецкого всего вдвое больше, чем возмущение , вносимое в матрицу при вводе чисел в компьютер: Это явление обусловлено положительной определённостью матрицы. Среди всех используемых разложений матриц это наименьшее из эквивалентных возмущений. В простейшем без перестановок суммирования варианте метод Холецкого на Фортране можно записать так:. При этом для реализации режима накопления переменная должна быть двойной точности. Отдельно следует обратить внимание на используемую в такой реализации функцию DPROD. Её появление как раз связано с тем, как математики могли использовать режим накопления вычислений. Дело в том, что, как правило, при выполнении умножения двух чисел с плавающей запятой сначала результат получается с удвоенными длинами мантиссы и порядка, и только при выполнении присваивания переменной одинарной точности результат округляется. Эта возможность даёт выполнять умножение действительных чисел с двойной точностью без предварительного приведения их к типу двойной точности. На ранних этапах развития вычислительных библиотек снятие результата без округление реализовали вставками специального кода в фортран-программы, но уже в х гг. XX века в ряде трансляторов Фортрана появилась функция DPROD, реализующая это без обращения программиста к машинным кодам. Она была закреплена среди стандартных функций в стандарте Фортран 77, и реализована во всех современных трансляторах Фортрана. Для метода Холецкого существует блочная версия, которая отличается от точечной не тем, что операции над числами заменены на аналоги этих операций над блоками; её построение основано на том, что практически все циклы точечной версии имеют тип SchedDo в терминах методологии, основанной на исследовании информационного графа и, следовательно, могут быть развёрнуты. Тем не менее, обычно блочную версию метода Холецкого записывают не в виде программы с развёрнутыми и переставленными циклами, а в виде программы, подобной реализации точечного метода, в которой вместо соответствующих скалярных операций присутствуют операции над блоками. Особенностью размещения массивов в Фортране является хранение их "по столбцам" быстрее всего меняется первый индекс. Поэтому для обеспечения локальности работы с памятью представляется более эффективной такая схема метода Холецкого полностью эквивалентная описанной , когда исходная матрица и её разложение хранятся не в нижнем, а в верхнем треугольнике. Тогда при вычислениях скалярных произведений программа будет "идти" по последовательным ячейкам памяти компьютера. Есть и другой вариант точечной схемы: Такая программа будет выглядеть так:. Как видно, в этом варианте для реализации режима накопления одинарной точности мы должны будем объявить двойную точность для массива, хранящего исходные данные и результат. Подчеркнём, что граф алгоритма обеих схем - один и тот же из п. В программе задействован только 1 массив, поэтому в данном случае обращения в профиле происходят только к элементам этого массива. Программа состоит из одного основного этапа, который, в свою очередь, состоит из последовательности подобных итераций. Пример одной итерации выделен зеленым цветом. Видно, что на каждой -й итерации используются все адреса, начиная с некоторого, при этом адрес первого обрабатываемого элемента увеличивается. Также можно заметить, что число обращений в память на каждой итерации растет примерно до середины работы программы, после чего уменьшается вплоть до завершения работы. Это позволяет говорить о том, что данные в программе используются неравномерно, при этом многие итерации, особенно в начале выполнения программы, задействуют большой объем данных, что приводит к ухудшению локальности. Однако в данном случае основным фактором, влияющим на локальность работы с памятью, является строение итерации. Рассмотрим фрагмент профиля, соответствующий нескольким первым итерациям. Фрагмент 1 — последовательный перебор с некоторым шагом всех адресов, начиная с некоторого начального. При этом к каждому адресу происходит мало обращений. Фрагмент 2 устроен гораздо лучше с точки зрения локальности. После рассмотрения фрагмента профиля на рис. Однако стоит рассмотреть более подробно, как устроен каждый из фрагментов. В частности, каждый шаг фрагмента 1 состоит из нескольких обращений к соседним адресам, причем выполняется не последовательный перебор. Также можно увидеть, что фрагмент 2 на самом деле в свою очередь состоит из повторяющихся итераций, при этом видно, что каждый шаг фрагмента 1 соответствует одной итерации фрагмента 2 выделено зеленым на рис. Это лишний раз говорит о том, что для точного понимания локальной структуры профиля необходимо его рассмотреть на уровне отдельных обращений. Стоит отметить, что выводы на основе рис. Основной фрагмент реализации, на основе которого были получены количественные оценки, приведен здесь функция Kernel. Условия запуска описаны здесь. Первая оценка выполняется на основе характеристики daps, которая оценивает число выполненных обращений чтений и записей в память в секунду. Данная характеристика является аналогом оценки flops применительно к работе с памятью и является в большей степени оценкой производительности взаимодействия с памятью, чем оценкой локальности. Однако она служит хорошим источником информации, в том числе для сравнения с результатами по следующей характеристике cvg. Можно увидеть, что реализация метода Холецкого характеризуется достаточно высокой скоростью взаимодействия с памятью, однако ниже, чем, например, у теста Линпак или реализации метода Якоби. Вторая характеристика — cvg — предназначена для получения более машинно-независимой оценки локальности. Она определяет, насколько часто в программе необходимо подтягивать данные в кэш-память. Соответственно, чем меньше значение cvg, тем реже это нужно делать, тем лучше локальность. Можно увидеть, что, согласно данной оценке, реализация метода Холецкого оказалась ниже в списке по сравнению с оценкой daps. Как нетрудно видеть по структуре графа алгоритма, вариантов распараллеливания алгоритма довольно много. Например, во втором варианте см. Поэтому перед размещением операций и данных между процессорами вычислительной системы предпочтительно разбиение всего пространства вычислений на блоки, с сопутствующим разбиением обрабатываемого массива. Многое зависит от конкретного типа вычислительной системы. Присутствие конвейеров на узлах многопроцессорной системы делает рентабельным параллельное вычисление нескольких скалярных произведений сразу. Подобная возможность есть и на программировании ПЛИСов, но там быстродействие будет ограничено медленным последовательным выполнением операции извлечения квадратного корня. В принципе, возможно и использование т. Однако его на практике никто не использует, из-за усложнения управляющей структуры программы. Проведём исследование масштабируемости параллельной реализации разложения Холецкого согласно методике. Исследование проводилось на суперкомпьютере "Ломоносов" [14] Суперкомпьютерного комплекса Московского университета. Набор и границы значений изменяемых параметров запуска реализации алгоритма:. В результате проведённых экспериментов был получен следующий диапазон эффективности реализации алгоритма:. На следующих рисунках приведены графики производительности и эффективности выбранной реализации разложения Холецкого в зависимости от изменяемых параметров запуска. Исследованная параллельная реализация на языке C. Для проведения экспериментов использовалась реализация разложения Холецкого, представленная в пакете SCALAPACK библиотеки Intel MKL метод pdpotrf. Использовались процессоры Intel Xeon X с пиковой производительностью в 94 Гфлопс, а также компилятор Intel с опцией —O2. На рисунках показана эффективность реализации разложения Холецкого случай использования нижних треугольников матриц для размерности матрицы , запуск проводился на процессах. Это хорошая картина для программ, запущенных без использования технологии Hyper Threading. На Рисунке 11 показан график количества операций с плавающей точкой в секунду. Видно, что к концу каждой итерации число операций возрастает. Это указывает на то, что задача достаточно большая, и данные плохо укладываются в кэш-память. На графике чтений из памяти на протяжении всего времени работы программы наблюдается достаточно интенсивная и не сильно изменяющаяся работа с памятью. На графике записей в память видна периодичность: Это коррелирует с возрастанием числа операций с плавающей точкой и может объясняться тем, что при меньшем числе записей в память программа уменьшает накладные расходы и увеличивает эффективность. На графике скорости передачи данных по сети Infiniband наблюдается достаточно интенсивное использование коммуникационной сети на каждой итерации. Причем к концу каждой итерации интенсивность передачи данных сильно возрастает. Это указывает на большую необходимость в обмене данными между процессами к концу итерации. Это говорит о том, что, вероятно, процессы обмениваются сообщениями различной длины, что указывает на неравномерное распределение данных. Также наблюдается рост интенсивности использования сети к концу каждой итерации. На графике числа процессов, ожидающих вхождения в стадию счета Loadavg , видно, что на протяжении всей работы программы значение этого параметра постоянно и приблизительно равняется 8. Это свидетельствует о стабильной работе программы с восьмью процессами на каждом узле. Это указывает на рациональную и статичную загрузку аппаратных ресурсов процессами. В целом, по данным системного мониторинга работы программы можно сделать вывод о том, что программа работала достаточно эффективно и стабильно. Использование памяти и коммуникационной среды достаточно интенсивное, что может стать фактором снижения эффективности при существенном росте размера задачи или же числа процессоров. Для существующих параллельных реализаций характерно отнесение всего ресурса параллелизма на блочный уровень. Видно, что при некотором довольно большом оптимальном размере блока обмены влияют не так уж сильно. Как видно по показателям SCALAPACK на суперкомпьютерах, обмены при большом n хоть и уменьшают эффективность расчётов, но слабее, чем неоптимальность организации расчётов внутри одного узла. Поэтому, видимо, следует сначала оптимизировать не блочный алгоритм, а подпрограммы, используемые на отдельных процессорах: Ниже содержится информация о возможном направлении такой оптимизации. Вообще эффективность метода Холецкого для параллельных архитектур не может быть высокой. Это связано со следующим свойством информационной структуры алгоритма: Поэтому для эффективной реализации алгоритмов, столь же хороших по вычислительным характеристикам, как и метод квадратного корня, следует использовать не метод Холецкого, а его давно известную модификацию без извлечения квадратных корней — разложение матрицы в произведение [15]. Точечный метод Холецкого реализован как в основных библиотеках программ отечественных организаций, так и в западных пакетах LINPACK, LAPACK, SCALAPACK и др. При этом в отечественных реализациях, как правило, выполнены стандартные требования к методу с точки зрения ошибок округления, то есть, реализован режим накопления, и обычно нет лишних операций. Ряд старых отечественных реализаций использует для экономии памяти упаковку матриц и в одномерный массив. Реализация точечного метода Холецкого в современных западных пакетах обычно происходит из одной и той же реализации метода в LINPACK, а та использует пакет BLAS. В BLAS скалярное произведение реализовано без режима накопления, но это легко исправляется при желании. Интересно, что в крупнейших библиотеках алгоритмов до сих пор предлагается именно разложение Холецкого, а более быстрый алгоритм LU-разложения без извлечения квадратных корней используется только в особых случаях например, для трёхдиагональных матриц , в которых количество диагональных элементов уже сравнимо с количеством внедиагональных. Разложение Холецкого Последовательный алгоритм Последовательная сложность Объём входных данных Объём выходных данных Параллельный алгоритм Высота ярусно-параллельной формы Ширина ярусно-параллельной формы Основные авторы описания: Законченные статьи Разложения матриц Уровень алгоритма. Навигация Персональные инструменты Создать учётную запись Войти. Пространства имён Статья Обсуждение. Просмотры Читать Просмотр История. Навигация Заглавная страница Общий форум Технический форум Справка Случайная статья Свежие правки. Хранилище файлов Новые файлы Загрузить файл. На других языках English. Последнее изменение этой страницы: Содержимое доступно по лицензии Creative Commons Attribution если не указано иное. Политика конфиденциальности Описание Алговики Отказ от ответственности.
Через сколько дней можно подавать апелляцию
Врач лучевой терапии
Cat power wild is the wind перевод
Интерьер беседки внутри своими руками
Акт посещения семьи учащегося бланк