[lennox 0]

Здравствуйте,

подскажите хороший источник по QR декомпозиции методом вращений Гивенса для комплексных матриц.

я нашел https://www.google.com/patents/US8473539 , но может быть посоветуете еще что-нибудь?

ну и в целом по Гивенсу какое-нибудь подробное описание с примерами..

-спасибо

 

 

[iiv 18]

http://www.netlib.org/lapack

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

[FatRobot 0]

Базовое описание здесь:

Matrix Computations
by Gene H. Golub (Author),
Charles F. van Van Loan (Author)

Применительно к задаче beamforming описано здесь:

13.7.2.3 Compressed beamforming weights feedback

Next Generation Wireless LANs
802.11n and 802.11ac

2nd Edition
Authors:
Eldad Perahia, Intel Corporation, Hillsboro, Oregon
Robert Stacey, Apple Inc.

18 hours ago, lennox said:

Здравствуйте,

подскажите хороший источник по QR декомпозиции методом вращений Гивенса для комплексных матриц.

я нашел https://www.google.com/patents/US8473539 , но может быть посоветуете еще что-нибудь?

ну и в целом по Гивенсу какое-нибудь подробное описание с примерами..

-спасибо

 

 

[enclis_ 0]

5 hours ago, iiv said:

http://www.netlib.org/lapack

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

Я может чего-то не знаю, но человек спросил про описание одного, а в него кидают ссылку на lapack в котором есть только dlarot(), который только умеет вращать по Гивенсу, но никак не QR декомпозицию методом вращений Гивенса для комплексных матриц. Householder и прочие методы не всегда так хороши и Гивенса иногда выгоднее использовать.

[lennox 0]

5 hours ago, FatRobot said:

Базовое описание здесь:

Matrix Computations
by Gene H. Golub (Author),
Charles F. van Van Loan (Author)

Применительно к задаче beamforming описано здесь:

13.7.2.3 Compressed beamforming weights feedback

Next Generation Wireless LANs
802.11n and 802.11ac

2nd Edition
Authors:
Eldad Perahia, Intel Corporation, Hillsboro, Oregon
Robert Stacey, Apple Inc.

спасибо!

[iiv 18]

On 11/8/2021 at 7:29 PM, enclis_ said:

Householder и прочие методы не всегда так хороши и Гивенса иногда выгоднее использовать.

Не спорю, что Гивенс в применении к QR будет лучше, если у вас разреженная матрица и сложно переписать Хаусхолдера или Ранк-Ревеалинг под такую структуру, или у вас есть компьютерная архитектура типа CUDA и очень маленькая матрица, что хочется распараллелить QR, чтобы все считалось на одном мультипроцессоре CUDA аритектуры. В остальных случаях, особенно на компьютерах с иерархической структурой кешев (первого, второго и третьего уровней), хаусхолдер делает гивенса как тузик грелку, а, если применить ранк-ревеалинг, то и по точности уделывает гивенса.

 

Собственно по этому я послал ТС почитать немного об этом в очень понятно написанный источник, с надеждой, что ТС таки или расколется почему все-таки Гивенс, или такии возьмет стандартное и проверенное временем решение.

[lennox 0]

11 hours ago, iiv said:

ТС таки или расколется почему все-таки Гивенс, или такии возьмет стандартное и проверенное временем решение.

потому что FPGA. сорри не указал в теме.

[enclis_ 0]

 

23 hours ago, iiv said:

... компьютерная архитектура типа CUDA ...

Даже если это не GPU или FPGA, сейчас во многих процессорах (и даже микроконтроллерах) уже есть довольно мощные NPU и прочие сопроцессоры для параллельных вычислений и работы с матрицами.

[iiv 18]

12 hours ago, enclis_ said:

NPU

правильно ли я понимаю, что под NPU вы понимаете neural processing unit? Если да, то каким они относятся боком к обычному QR, который делают без использования нейронных сетей либо Граммом-Шмидтом, либо Хаусхолдером, либо Гивенсом, иногда еще с применением ранг-ревеалинга?

On 11/11/2021 at 9:18 PM, lennox said:

потому что FPGA. сорри не указал в теме.

не, тогда колитесь дальше - какова размерность матрицы, и как эта размерность соотносится к числу умножителей, и будете ли вы все в честной IEEE плавающей точке считать, или есть желание в псевдо-целочисленной посчитать?

[lennox 0]

21 hours ago, iiv said:

правильно ли я понимаю, что под NPU вы понимаете neural processing unit? Если да, то каким они относятся боком к обычному QR, который делают без использования нейронных сетей либо Граммом-Шмидтом, либо Хаусхолдером, либо Гивенсом, иногда еще с применением ранг-ревеалинга?

не, тогда колитесь дальше - какова размерность матрицы, и как эта размерность соотносится к числу умножителей, и будете ли вы все в честной IEEE плавающей точке считать, или есть желание в псевдо-целочисленной посчитать?

8x8 матрица канала. fixed point. 

я еще в процессе изучения QR по Гивенсу. для действительных чисел понял "механику" преобразования. Переписал псевдо код из книжки Matrix Computations, Golub на матлаб для real данных. Работает, но математику, т.е. почему обнулялся элемент матрицы, еще не до конца понял. Потом нужно понять как это сделать для комплексных чисел, потом разобраться что такое систолические массивы ну т.д.

[thermit 1]

1 час назад, lennox сказал:

8x8 матрица канала. fixed point. 

я еще в процессе изучения QR по Гивенсу. для действительных чисел понял "механику" преобразования. Переписал псевдо код из книжки Matrix Computations, Golub на матлаб для real данных. Работает, но математику, т.е. почему обнулялся элемент матрицы, еще не до конца понял. Потом нужно понять как это сделать для комплексных чисел, потом разобраться что такое систолические массивы ну т.д.

Вектор-столбец  [ a b ]. Матрица вращения [ conj(a) conj(b) ]

                                                                         [   -b            a     ].

Результат умножения матрицы на вектор  [ |a|^2+|b|^2  -a*b+b*a ]. Вроде все просто с обнулением.

Ну и нормируется все это к евклидовой норме вектора:  sqrt(|a|^2+|b|^2) т е результирующий вектор [ sqrt(|a|^2+|b|^2)  0 ].

зы

Слава великому улучшайзингу, формулы теперь вставить хз как.

Изменено 13 ноября, 2021 пользователем thermit
улучшайзинг

[enclis_ 0]

@iiv, так и будете придираться к каждому слову? ваш lapack не был в тему, на этом можно было закончить. 

[iiv 18]

On 11/13/2021 at 6:58 PM, lennox said:

8x8 матрица канала. fixed point. 

Во, наконец-то с этого-то и надо было начинать. Тут-то как раз Гивенс и будет лучше других методов.

Комплексную матрицу Гивенса надо представить так:
c = cos(a) e^(i*b),
s = sin(a) e^(i*b),

причем у Вас a и b бегут от -Пи до +Пи, то есть их надо представлять в целочисленной арифметике разделив весь отрезок от -Пи до Пи равномерно. Если исходная матрица пришла из измерений и каждое число содержит N бит, то для представления a и b взять столько же бит. Просто запишите формулы вычисления коэффициентов в таком виде как я выше сказал, и все будет просто вычисляться.

 

Далее, Гивенс позволяет исключать впараллель несколько поддиагональных значений

(********)

(b*******)

(9a******)

(89a*****)

(4567****)

(34567***)

(234567**)

(1234567*)

здесь номером в шестнадцатиричной системе я обозначил какой поддиагональный элемент можно исключить на каком из шагов. Суммарно Вам потребуется 4 устройства для ваполнения одновременного исключения, но для матрицы 8х8 вы потратите только 11 шагов. Если выполнять Хаухолдера, то из-за скалярного произведения на каждом шаге у вас число шагов будет больше. Правда конкретно для матрицы 8х8 тут разница будет не столько большая, но зато существенно меньше заморочек по представлению Хаусхолдера в арифметике с фиксированной точностью.

 

Еще момент. Саму матрицу до и во время исключения можно хранить в арифметике с фиксированной точностью, так как роста элементов больше, чем в 8х2 раз нет, то все хорошо. Но я бы добавил и вверх 4 бита и вниз 3 бита, хотя конечно это утяжелит само разложение.

 

PS: а можно полюбопытствовать что Вы далее будете делать с полученным QR?

[iiv 18]

On 11/7/2021 at 8:38 PM, lennox said:

я нашел https://www.google.com/patents/US8473539 , но может быть посоветуете еще что-нибудь?

только сейчас внимательно прочитал, и реально протащился - запатентованный метод, что там излагается в виде общей теоретической блоксхемы мне в 1994 году на лекциях по вычислительной математике рассказывали. Да, во время лекции никто это за уши на ПЛИСки не притаскивал, но ведь запатентовали же потом через 15 лет!