?
Процессорный массив для кватернионного преобразования Якоби
Метод Якоби применяется для вычисления собственных значений и сингулярного разложения матриц при решении многих задач линейной алгебры в физике и обработке сигналов и изображений. Он приводит симметричную действительную или комплексную эрмитову матрицу к диагональной форме с помощью некоторой последовательности плоских вращений в разных плоскостях исходного n-мерного векторного пространства, причем для эрмитовых матриц собственные значения совпадают с сингулярными. Сингулярное разложение используется при решении самых разных задач — от приближения методом наименьших квадратов и решения систем уравнений до сжатия и распознавания изображений. Высокая практическая важность быстрого решения подобного типа задач приводит к необходимо- сти реализации метода Якоби c помощью проблемно-ориентированных массивов процессорных элементов (ПЭ). Известен ряд подобных разработок с использованием специализированных процессоров типа CORDIC, которые с помощью операций 2D-вращения параллельно обрабатывают пары элементов действительной матрицы за время одной операции умножения. Для ускорения декомпозиции комплексных матриц был предложен 4DCORDIC алгоритм. Развитием этого подхода явилась разработка 8DCORDIC алгоритма для декомпозиции кватернионных матриц. Этот октонионный CORDIC-алгоритм (ОСА) параллельно вычисляет 8 компонент действительного вектора (2 компоненты кватернионного вектора) при вы- полнении вращения Гивенса за время, сравнимое с длительностью одной операции умножения.
Декомпозиция кватернионных матриц напрямую, вместо соответствующих им действительных или комплексных матриц, в том числе и методом Якоби в последнее время все чаще находит применение в связи с достигаемым при этом сокращении вычислительной сложности и по- вышении точности вычислений. Идея построения процессорного массива (Brent-Luk-Van Loan (BLV) систолический массив) для параллельной реализации метода Якоби была предложена еще в 1983 г. . Однако вопросы организации работы такого массива с элементами, реализующими ОСА, для кватернионных матриц требуют существенных дополнительных исследований. При рассмотрении мы ограничимся случаем эрмитовых матриц, как имеющих важное самостоятельное применение.