Автор: Julien Langou
Автор перевода: Дрозда Иван
Источник: CERFACS – Advanced methods for the numerical simulation and the algorithmic solution [Электронный ресурс]. – Режим доступа: http://www.cerfacs.fr/~langou/abstract-thesis.html
Толчком для начала исследования послужила задача поставленная группой исследователей электромагнетизма: «Как решить несколько систем линейных алгебраических уравнений с одинаковыми матрицами коэффициентов и различными векторами свободных членов?».
Матрицы в прикладных задачах комплексные, плотные и огромные (порядка нескольких миллионов элементов). Так как они не могут быть эффективно обработаны и храниться при численном моделировании в процессе проектирования, единственной альтернативой является использование итерационной схемы с приближенным матрично – векторным произведением. Произведение расчитывается быстрым мультипольным методом. Поэтому целью работы является адаптация решателей Крылова для взаимодействия с множеством векторов свободных членов. Некоторые предварительные работы, связанные с одной правой сторой (вектором свободных членов), показали, что эффективно в этом направлении может использоваться обобщенный метод минимальных остатков (GMRES). Значит основной упор в работе будет сделан на вариации метода GMRES.
Схемы ортогонализации для GMRES, которые мы реализовали, являются модификациями алгоритма Шмидта. В результате получены ответы на вопросы, которые стояли в течение последних двадцати пяти лет. Мы даем теоретическое объяснение наблюдаемых явлений, а именно:
Эти два высказывания справедливы когда исходная матрица «не слишком плохо обусловлена» или даже, четко определена. Кроме того, когда алгоритм Шмидта выполняется и повторяется с избирательной реортогонализацией, в третьей части, мы даем новый критерий. Доказано, что в результате алгоритм устойчив, в то время как наиболее часто используемый критерий может иметь некоторые слабости. В четвертой части мы обобщим стандартные результаты для модифицированного метода Грама – Шмидта. Это позволяет нам предлагать процедуру апостериорные реортогонализации для модифицированного метода Грама – Шмидта, основанного на обновлении малого ранга. Эти результаты имеют несколько прямых приложений. Мы приводим примеры методов Крылова для решения линейных систем и для решения проблемы собственных значений. Наконец, вместо того, чтобы использовать евклидово скалярное произведение, мы применили на методе Шмидта А – скалярное произведение, где А – положительная эрмитова матрица. Актуальность такого исследования доказана в сотрудничестве с глобальной командой CERFACS, использующей алгоритм Ланцоша с реортогонализацией для ассимиляции данных в задаче моделирования климата.
Во второй части мы реализовали варианты алгоритма GMRES для действительных и комплексных матриц, арифметики одинарной и двойной точности, компьтеров с последовательной разделяемой и распределенной памятью. Это программная реализация описана в деталях и соответствует стандартам качества научных библиотек . Ради простоты, гибкости и эффективности GMRES решателей для матрично – векторного произведения, они были реализованы с помощью механизма обратной связи. Несколько процедур ортогонализации были реализованы для уменьшения затрат на скалярное произведение, которое ,как известно, является узким местом метода Крылова в параллельной распределенной среде. Реализован критерий останова основанном на обратной normwise ошибке. Доступны варианты GMRES-DR, распределенный GMRES и блочный GMRES (что добавляет к стандартным GMRES, гибкий и GMRES SQMR). Шаг LU – матрично – векторного произведения выполняется в GMRES – DR для хранения приближенных собственных векторов первичных векторов Крылова. Неявные перезагрузки и неявная предварительная подготовка проводится в распределенном GMRES для обхода матрично – векторного произведения. Блочный GMRES позволяет пользователю выбрать как бездефляционную так и дефляционную на основе сингулярного разложения декомпозицию векторов Крылова. Наконец, мы расширяем существующий теоретический результат, касательно нормы невязки наименьшего сингулярного пространства решателя Крылова из GMRES на блочный GMRES.
Третья часть посвящена совершенствованию этих стандартные методов решения линейных систем для применения в области электромагнетизма. После глубокого представления используемого кода, мы исследуем влияние уровня асимметрии в алгоритме SQMR и иллюстрируем поведение GMRES – DR метода на нашем примере. Делаем упор на многовекторность свободных членов. Прежде всего, мы рассмотрели в деталях методы адаптации одновекторного способа к многовекторной задаче: повышение качества предварительной подготовки, начальной стратегии предположений или построения стратегии. Мы докажем, что число независимых правых частей конечно. Размерность пространства правых частей, предоставляемых нашей теорией и численные эксперименты вполне соответствует друг другу. Это свойство позволяет значительно сократить количество решаемых систем уравнений. В этом контексте даётся конкретная реализация блочного GMRES метода. Затем обсуждаются некоторые конкретные вопросы распределенного и блочного методов. Наконец, выводятся наиболеее перспективные результаты. Во – первых, приводятся и сравниваются различные стратегии извлечения и добавления спектральной информации в цикл GMRES. Затем, мы используем тот факт, что быстрый мультипольный метод – это неточное матрично – векторное произведение с регулируемой ошибкой. Чем меньше необходимая точность, тем быстрее расчет. Мы покажем, как извлечь из этого пользу с помощью расслабленным схем (неточные методы Крылова) или внешне – внутренних схемы (гибкий GMRES). Наконец, мы изучим актуальность обратной normwise ошибки в качестве критерия останова для итерационного решателя.