Умножение теплицевых матриц Опции

[Виктор39]

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

Я заметил, что перемножаемые матрицы являются якобы теплицевыми, но не симметричными и не квадратными, т.е. примерно следующих форматов:

{ a+0, a+1, a+2, a+3;
a-1, a+0, a+1, a+2;
a-2, a-1, a+0, a+1 }

{ a+0, a+1, a+2;
a-1, a+0, a+1;
a-2, a-1, a+0;
a-3, a-2, a-1 }

Встречал алгоритмы, которые позволяют работать с теплицевыми матрицами размером [NxN].

Существуют ли оптимизированные алгоритмы, которые позволяют перемножать теплицевые не квадратные матрицы размером [NxM], где N != M ???
Может кто-нибудь встречал, подскажите, пожалуйста...

может быть теплицевыми являются только квадратные матрицы?

[serjj]

Он же, кстати, обычно является первой обязательной стадией QR/QL и SVD разложений, т.к. итерации делают не по плотной матрице, а по три- или дву- диагональным формам.

Xenia, для QR/QL/SVD декомпозиций можно использовать только вращение Гивенса, без Хаусхолдера. Или можно комбинировать Хаусхолдера и Гивенса для ускорения вычисления? Можете поделиться какими нибудь статьями с примерами?

Как я понимаю, применяемый метод зависит от архитектуры, на которой все будет реализовываться. Например целочисленная QR декомпозиция легко разбивается на вычисление множества вращений Гивенса, которое суть поворот матрицы 2х2, параллелится и делается на обычном кордике.

[Xenia]

Xenia, для QR/QL/SVD декомпозиций можно использовать только вращение Гивенса, без Хаусхолдера. Или можно комбинировать Хаусхолдера и Гивенса для ускорения вычисления? Можете поделиться какими нибудь статьями с примерами?

Насколько я знаю, метод Хаусхолдера применялся для этой цели еще со времен "Справочника" (Уилкинсон, Райнш). Оттуда же попал в большинство известных мне матпакетов, где для нахождения собственных значений и векторов приходилось вызывать не одну функцию, а последовательно три штуки: приведение к тридиагональной, QR-итерации и обратные итерации для восстановления соб.векторов. Но потом, когда в пакетах появилась для этих целей одна функция, стало сложно определить, как она внутри себя устроена. Например, MATLAB пишет, что qr() это его встроенная функция и кода не показывает. Тем не менее, подозреваю, что и там используется старый добрый Хаусхолдер. Вот и функция hess(), вычисляющая форму Гессенберга, использует все те же отражения Хаусхолдера, хотя его именем не называется.

По части применения в микроконтроллерах взгляните на это:
"Применение QR алгоритма для расчёта собственных структур корреляционных матриц на платформе ADSP-TS201 фирмы Analog Devices"
- там тоже Хаусхолдер.

И, наконец, цитата из "Алгебраическая проблема собственных значений – Часть 64":

... метод Хаусхолдера требует вдвое меньше умножений, чем метод Гивенса.

Уилкинсон Дж.Х., Алгебраическая проблема собственных значений(1970):

Число умножений, необходимое для выполнения процесса Шмидта, равно n³, тогда как триангуляризации Хаусхолдера и Гивенса требуют соответственно 2/3 n³ и 4/3 n³.

что, видимо, объясняет причину популярности метода отражений.