Участник:Почернина Елена/Метод Якоби вычисления сингулярных чисел и векторов

Метод Якоби вычисления сингулярных чисел и векторов
Последовательный алгоритм
Последовательная сложность	$O(n^3)$
Объём входных данных
Объём выходных данных
Параллельный алгоритм
Высота ярусно-параллельной формы
Ширина ярусно-параллельной формы

Авторы статьи: Почернина Елена (группа 601), Костюкова Светлана (группа 601)

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

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

Метод Якоби для вычисления сингулярных чисел и векторов является самым медленным из имеющихся алгоритмов поиска сингулярных чисел и векторов, но тем не менее, интерес к нему сохраняется. Для некоторых некоторых типов матриц $G$ он способен вычислять сингулярные числа и векторы намного точнее, чем другие методы. В частности, метод Якоби вычисляет сингулярные числа матрицы $G$ с высокой точностью, если G может быть представлена в виде $G = DX$, где $D$ – диагональная матрица, а $X$ – хорошо обусловлена. В этом случае заданная матрица обрабатывается без предварительного приведения к двухдиагональному виду, в то время как другие алгоритмы включают в себя приведение матрицы к двухдиагональной форме, из-за чего и теряют все верные разряды во всех сингулярных числах, кроме старшего.

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

Исходные данные: матрица $G$ (элементы $g_{ij}, i, j = 1, \ldots, n$).

Вычисляемые данные: матрица $\Sigma = diag(\sigma_{i})$, где $\sigma_{i}$ - сингулярные числа, $U$ - матрица левых сингулярных векторов, $V$ - матрица правых сингулярных векторов.

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

Метод можно описать следующим образом:

repeat
    for [math]j=1[/math] to [math]n-1[/math]
        for [math]k=j+1[/math] to [math]n[/math]
            обратиться к процедуре One-Sided-Jacobi-Rotation[math](G,j,k)[/math]
        end for
    end for
пока [math]G^TG[/math] не станет достаточно близка к диагональной матрице
Положить [math]\sigma_{i} = ||G(:,i)||_2 [/math] (норма [math]i[/math]-го столбца в [math]G[/math])
Положить [math]U = [u_{1},\dots, u_{n}][/math], где [math]u_{i} = G(:,i)/\sigma_{i}[/math]
Положить [math]V = J[/math], где [math]J[/math] - накопленное произведение вращений Якоби.

Метод Якоби для нахождения сингулярных чисел и векторов матрицы $G$ также использует метод односторонних вращений (процедура One-Sided-Jacobi-Rotation). Алгоритм выглядит следующим образом:

proc One-Sided-Jacobi-Rotation[math](G,j,k)[/math]
    вычислить [math]a_{jj} = (G^TG)_{jj}, a_{jk} = (G^TG)_{jk}[/math] и [math]a_{kk} = (G^TG)_{kk}[/math]
    if [math]|a_{jk}|[/math] не слишком мал
        [math]
         \begin{align}
         \tau &= {a_{jj} - a_{kk}}/{2a_{jk}} \\
         t &= {sign(\tau)}/(|\tau| + \sqrt{1 + \tau^2}) \\
         c &= 1/(\sqrt{1 + t^2}) \\
         s &= ct \\
         G &= GR(j,k,\theta)\end{align}[/math]
        if нужны правые сингулярные векторы 
            [math]J = JR(j,k,\theta)[/math]
        end if
    end if

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

Для вычисления сингулярных чисел и векторов матрицы порядка n в последовательном варианте требуется:

• делений,
• сложений (вычитаний),
• умножений.

Метод Якоби вычисления сингулярных чисел и векторов при классификации по последовательной сложности относится к алгоритмам с кубической сложностью.

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

Опишем граф алгоритма как аналитически, так и в виде рисунка.

Первая группа вершин расположена в двумерной области, соответствующая ей операция - вычисление $a_{jj}, a_{jk}, a_{kk}$. Естественно введённые координаты области таковы:

• $j$ — меняется в диапазоне от $1$ до $n-1$, принимая все целочисленные значения;
• $k$ — меняется в диапазоне от $j+1$ до $n$, принимая все целочисленные значения.

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

Входные данные: плотная матрица $G$ (элементы $g_{ij}$). Дополнительные ограничения:

• $A= G^TG$ – симметрическая матрица, т. е. $a_{ij}= a_{ji}, i, j = 1, \ldots, n$.

Объём входных данных: $n^2$

Выходные данные: матрица $\Sigma = diag(\sigma_{i})$, где $\sigma_{i}$ - сингулярные числа, матрица $U$ левых сингулярных векторов и матрица $V$ правых сингулярных векторов.

Объём выходных данных: $2n^2 + n$

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

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

Метод Якоби нахождения сингулярных значений и векторов реализован в пакете LAPACK. В связи с тем, что алгоритм считается медленным, он не включен во многие известные пакеты.

3 Литература

1. Дж. Деммель Вычислительная линейная алгебра. Изд. Мир, 2001.