Участник:Alexbashirov/Алгоритм Ланцоша для точной арифметики

Авторы: Баширов А.Д.

Алгоритм Ланцоша для точной арифметики
Последовательный алгоритм
Последовательная сложность	[math]\displaystyle{ O(kn^2) }[/math].
Объём входных данных	[math]\displaystyle{ n^2 + n + 1 }[/math]
Объём выходных данных	[math]\displaystyle{ k }[/math]
Параллельный алгоритм
Высота ярусно-параллельной формы	[math]\displaystyle{ O(n) }[/math]
Ширина ярусно-параллельной формы	[math]\displaystyle{ O(n^2) }[/math]

Свойства и структура алгоритма

Общее описание алгоритма

История

Алгоритм Ланцоша является прямым алгоритмом поиска собственных значений симметричной матрицы, разработанным венгерским физиком и математиком XX столетия Корнелием Ланцошем в 1950 году. Алгоритм совмещает в себе два других алгоритма: алгоритм построения подпространства Крылова (который также был создан Ланцошем) и процедуру Рэлея-Ритца приближения собственных значений матрицы. Алгоритм является вариацией степенного метода, позволяющего найти собственные значения и собственные вектора матрицы [math]\displaystyle{ n }[/math]-го порядка. Однако в алгоритме число итераций ограничено некоторым [math]\displaystyle{ k }[/math], где [math]\displaystyle{ k\lt \lt n }[/math]. Несмотря на заявленную вычислительную эффективность, алгоритм не получил широкого применения в своём первоначальном виде, ввиду его неустойчивости. 20 лет спустя, в 1970 году ученые Ojalvo и Newman показали доработанный алгоритм Ланцоша, который теперь стал устойчивым а также предложили способ выбора вектора начального приближения [math]\displaystyle{ v_0 }[/math]. Полученный последователями Ланцоша алгоритм получил название "Алгоритм Ланцоша с полной переортогонализацией".

Математическое описание алгоритма

Алгоритм Ланцоша работает с вещественной симметричной матрицей [math]\displaystyle{ A=A^T }[/math], таким образом в памяти достаточно хранить лишь немногим более половины элементов матрицы [math]\displaystyle{ A }[/math].

Прежде чем переходить к описанию алгоритма, следует упомянуть следующие понятия: подпространство Крылова и процесс Рэлея-Ритца, о которых уже было сказано в исторической справке выше. Подпространством Крылова называется набор векторов[math]\displaystyle{ K_n =[b,Ab,A^2b,...,A^{n-1}b] }[/math]. Начав свою работу с произвольного вектора [math]\displaystyle{ b }[/math], степенной метод вычисляет вектора [math]\displaystyle{ Ab, A^2b,...,A^{n-1}b }[/math] итерационно сохраняя полученный результат в вектор [math]\displaystyle{ b }[/math]. Полученная последовательность векторов сходится к собственному вектору, отвечающему максимальному собственному значению [math]\displaystyle{ \lambda_{max} }[/math]. Однако, использование лишь последнего полученного вектора и потеря всех предшествующих посчитанных величин не всегда является наилучшим выбором. Поэтому сохранив все вектора и объединив их в одну матрицу мы получим так называемую матрицу Крылова:

[math]\displaystyle{ K_j = [b,Ab,A^2b,...,A^{j-1}b] }[/math].

Столбцы получившейся матрицы не ортогональны, однако их можно ортогонализовать, применив процесс Грамма-Шмидта. Получившиеся вектора будут составлять базис подпространства Крылова [math]\displaystyle{ Q_j }[/math]. Можно ожидать, что вектора полученного базиса будут достаточно хорошо приближать [math]\displaystyle{ j }[/math] собственных векторов, отвечающих [math]\displaystyle{ j }[/math] наибольшим собственным значения.

Затем с использованием полученной матрицы из ортогональных векторов [math]\displaystyle{ Q_j }[/math] мы получим трехдиагональную матрицу [math]\displaystyle{ T_j }[/math] на основе исходной матрицы [math]\displaystyle{ A }[/math]: [math]\displaystyle{ T_j=Q_j^TAQ_j }[/math]. Наконец, к полученной матрице [math]\displaystyle{ T_j }[/math] будет применяться процесс Рэлея-Ритца, который найдет собственные значения трехдиагональной матрицы. В последствии эти значения и будут приближениями искомых собственных значений исходной матрицы [math]\displaystyle{ A }[/math].

Вычислительное ядро алгоритма

Вычислительным ядром алгоритма Ланцоша, то есть наиболее ресурсно-затратной частью алгоритма, является шаг на котором на каждой итерации происходит перемножение матрицы [math]\displaystyle{ A }[/math] на вектор [math]\displaystyle{ q_j }[/math], полученный на предыдущей итерации. Полученный в результате умножения вектор обозначается [math]\displaystyle{ z }[/math]:

[math]\displaystyle{ z=Aq_j }[/math].

Макроструктура алгоритма

Как уже говорилось в математическом описании, алгоритм объединяет в себе два алгоритма: метод построения подпространства Крылова и процедуру поиска собственных значений трехдиагональной матрицы (процес Рэлея-Ритца).

Первую составную часть (алгоритм построения подпространства Крылова) представляет итерационный процесс построения матрицы [math]\displaystyle{ Q_j=[q_1,q_2,...q_j] }[/math] из [math]\displaystyle{ j }[/math] ортонормированных вектров Ланцоша и последующее формирование трехдиагональной матрицы [math]\displaystyle{ T_j=Q_j^TAQ_j }[/math]. Число таких векторов и, следовательно, размер матрицы растет с каждой итерацией. Итерационный процесс завершается при [math]\displaystyle{ j=k }[/math].

На долю второй части алгоритма приходится поиск собственных значений и соответствующих им собственных векторов матрицы [math]\displaystyle{ T_j=Q_j^TAQ_j }[/math], полученной в первой части.

Схема последовательной реализации алгоритма

На рисунке выше представлен псевдокод, отражающий последовательность действий в алгоритме метода. Перечислим основные ступени в данном методе:

• Прежде чем войти в цикл, происходит инициализация констант [math]\displaystyle{ \Beta_0,q_0 }[/math], вычисление нормы вектора начального приближения [math]\displaystyle{ b }[/math] и нормализация этого вектора.
• Затем, в цикле, происходит: поиск вектора [math]\displaystyle{ z }[/math], являющегося результатом применения матричного оператора [math]\displaystyle{ A }[/math] к вектору [math]\displaystyle{ q_j }[/math]; скалярное произведение двух векторов [math]\displaystyle{ q_j }[/math] и [math]\displaystyle{ z }[/math]; вычисляется линейная комбинация векторов; вычисляется норма вектора [math]\displaystyle{ z }[/math]; проверяется условие выхода из цикла (равенство нулю нормы вектора [math]\displaystyle{ z }[/math]); в случае если норма не нулевая, то производим нормировку вектора; затем происходит процедура поиска собственных значений и векторов матрицы [math]\displaystyle{ T_j }[/math] и, наконец, переход на следующий шаг цикла.

Последовательная сложность алгоритма

Посчитаем количество операций, необходимых для поиска [math]\displaystyle{ k }[/math] собственных значений и векторов для матрицы [math]\displaystyle{ A }[/math] размерности [math]\displaystyle{ n\times n }[/math].

• [math]\displaystyle{ n^2 }[/math] действий для умножения матрицы на вектор
• [math]\displaystyle{ n }[/math] действия для перемножения двух векторов
• [math]\displaystyle{ n }[/math] операций для поэлементного сложения или вычитания двух векторов
• для отыскания нормы вектора помимо [math]\displaystyle{ n }[/math] сложений и [math]\displaystyle{ n }[/math] умножений требуется 1 операция извлечения корня
• для поиска собственных значений и векторов матрицы [math]\displaystyle{ T_j }[/math] требуется [math]\displaystyle{ O(k^3) }[/math] операций.

Суммарно для одной итерации алгоритма требуется совершить [math]\displaystyle{ O(n^2)+O(k^3) }[/math] операций.

Информационный граф

TODO

Ресурс параллелизма алгоритма

Поскольку алгоритм является итерационным, то выполнять параллельные операции возможно только внутри каждой итерации алгоритма. Сами итерации выполняются в строгой последовательности и не могут быть параллелизованны. Однако внутри каждой итерации происходят два процесса, которые могут быть параллелизованны:

• умножение матрицы на вектор,
• процесс поиска собственных значений.

Умножение квадратной матрицы размерности [math]\displaystyle{ n\times n }[/math] на вектор размерности [math]\displaystyle{ n }[/math] требует [math]\displaystyle{ n }[/math] ярусов умножений и сложений. В свою очередь ресурс параллелизма операции поиска собственных значений зависит от выбранного способа и не рассматривается в данной статье.

Таким образом, с точки зрения ресурса параллелизма, алгоритм Ланцоша обладает линейной сложностью по ширине ЯПФ и квадратичной сложностью по высоте ЯПФ. Основное время работы алгоритма будет уделено операции умножения матрицы на вектор, имеющей ширину яруса [math]\displaystyle{ n^2 }[/math].

Входные и выходные данные алгоритма

Алгоритм призван найти фиксированное число [math]\displaystyle{ k }[/math] первых собственных значений матрицы [math]\displaystyle{ A }[/math], следовательно на вход данный алгоритм во всяком случае получает 1 число и 1 матрицу размерности [math]\displaystyle{ n\times n }[/math]. Помимо этого для начала работы алгоритму нужен некоторый вектор [math]\displaystyle{ b_0 }[/math] начального приближения размерности [math]\displaystyle{ n }[/math], который тоже является входными данными.

После окончания работы алгоритма мы получаем набор собственных значений матрицы [math]\displaystyle{ A }[/math], состоящий из [math]\displaystyle{ k }[/math] элементов. Если помимо собственных значений выводятся еще и полученные собственные векторы, то суммарный объём всех таких векторов составляет [math]\displaystyle{ k\times n }[/math] элементов.

Таким образом, совокупный объём входных данных составляет: [math]\displaystyle{ n^2+n+1 }[/math] элемент, а на выходе получаем [math]\displaystyle{ k(n+1) }[/math] элементов.

Свойства алгоритма

Преимуществом алгоритма является то, что он начинает поиск собственных значений матрицы [math]\displaystyle{ T_j }[/math] (а значит и матрицы [math]\displaystyle{ A }[/math]) начиная с максимального в абсолютном смысле значения. Это выгодно отличает данный алгоритм с точки зрения поиска собственных значений матрицы, находящихся по краям её спектра.

Не является полностью детерминированным, т.к. может досрочно завершить работу, если будут найдены все ненулевые собственные значения.

В случае использования метода вычисления собственных значений с линейной сложностью, соотношение последовательной и параллельной сложностей будет равно [math]\displaystyle{ (k ^ 2 + n ^ 2) / (k + n) }[/math].

Программная реализация алгоритма

Масштабируемость алгоритма и его реализации

TODO

Существующие реализации алгоритма

В настоящее время алгоритм Ланцоша поиска собственных значений квадратной симметричной матрицы включён в несколько библиотек и реализован на различных языках, среди которых такие наиболее распространенные как C, C++, FORTRAN77/90, MathLab. Так, например, в языке MathLab во встроенном пакете ARPACK найти собственные значения методом Ланцоша можно при помощи вызова функции eigs().

На языке С существует библиотека PRIMME, название которой расшифровывается как PReconditioned Iterative MultiMethod Eigensolver (итерационные методы поиска собственных значений с предусловием).

Библиотека NAG Numerical Library также содержит обширный набор функций, позволяющих проводить математический анализ, среди которых есть и реализация алгоритма Ланцоша. Библиотека доступна в трех пакетах: NAG C Library, NAG Fortran Library и NAG Library for .NET, совместна со многими языками и с основными операционными системами (Windows, Linux and OS X, а также Solaris, AIX и HP-UX).

Литература

[1] Дж. Деммель «Вычислительная линейная алгебра», с 381.

[2] Wikipedia https://en.wikipedia.org/wiki/Lanczos_algorithm

[3] "Investigation and Implementation of an Eigensolver Method", Jorge Moreira, The University of Edinburgh, August 2014

[4] "Lanczos Vector Procedures", Travis Hoppe