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

[Виктор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]

SVD операция затратная, но:
1) псевдоинверсия вычислительно устойчивый алгоритм
2) при переходе к матрице (A^H * A) вы будете работать с энергиями, т.к. это корреляционная матрица, разрядность вырастет в 2 раза, в общем случае вы не сможете откинуть добавочные разряды, т.к. потеряете информацию, которая в ней заключается (особенно это заметно в случае близком к вырождению, например АФАР, где собственные числа полезного сигнала много меньше собственных чисел помех).
3) SVD даст вам собственные числа матрицы данных, которые можно использовать с пользой в дальнейшем.
4) матрица данных у вас должна быть все таки Теплицевой или я чего то не понимаю, вы можете попробовать выиграть от SVD Теплицевой матрицы, а перейдя к (A^H * A) вы получете квадратную матрицу общего вида (она будет близка к Эрмитовой и тем ближе чем более длинные матрицы данных вы будете брать, но в общем случае она не Эрмитова, т.к. это только аппроксимация, поэтому я не уверен, что здесь можно выиграть от использования ее структуры)
5) если цель - алгоритм с фиксированной точкой, то по SVD есть литература как получить устойчивую имплементацию, хотя это будет сложно и весело. Можно в целых числах сделать инверсию (A^H * A) пользуясь QR декомпозицией, которая проще (и я бы даже мог поделиться матлабовскими скриптами по fixed point реализации), но см пункт 2 о росте разрядности.

В общем то, что я тут понаписал не претендует на истину в первой инстанции, т.к. я сам далеко не спец) но это мои соображения)

Сообщение отредактировал serjj - Apr 13 2015, 10:35