lennox 0 7 ноября, 2021 Опубликовано 7 ноября, 2021 · Жалоба Здравствуйте, подскажите хороший источник по QR декомпозиции методом вращений Гивенса для комплексных матриц. я нашел https://www.google.com/patents/US8473539 , но может быть посоветуете еще что-нибудь? ну и в целом по Гивенсу какое-нибудь подробное описание с примерами.. -спасибо Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
iiv 29 8 ноября, 2021 Опубликовано 8 ноября, 2021 · Жалоба http://www.netlib.org/lapack там самая понятная и наиболее устойчивая версия QR. Не пугайтесь фортрана, там есть клоны на С, которые даже на ембеддед хорошо компилируются. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
FatRobot 3 8 ноября, 2021 Опубликовано 8 ноября, 2021 · Жалоба Базовое описание здесь: 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 8 ноября, 2021 Опубликовано 8 ноября, 2021 · Жалоба 5 hours ago, iiv said: http://www.netlib.org/lapack там самая понятная и наиболее устойчивая версия QR. Не пугайтесь фортрана, там есть клоны на С, которые даже на ембеддед хорошо компилируются. Я может чего-то не знаю, но человек спросил про описание одного, а в него кидают ссылку на lapack в котором есть только dlarot(), который только умеет вращать по Гивенсу, но никак не QR декомпозицию методом вращений Гивенса для комплексных матриц. Householder и прочие методы не всегда так хороши и Гивенса иногда выгоднее использовать. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
lennox 0 8 ноября, 2021 Опубликовано 8 ноября, 2021 · Жалоба 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 29 11 ноября, 2021 Опубликовано 11 ноября, 2021 · Жалоба On 11/8/2021 at 7:29 PM, enclis_ said: Householder и прочие методы не всегда так хороши и Гивенса иногда выгоднее использовать. Не спорю, что Гивенс в применении к QR будет лучше, если у вас разреженная матрица и сложно переписать Хаусхолдера или Ранк-Ревеалинг под такую структуру, или у вас есть компьютерная архитектура типа CUDA и очень маленькая матрица, что хочется распараллелить QR, чтобы все считалось на одном мультипроцессоре CUDA аритектуры. В остальных случаях, особенно на компьютерах с иерархической структурой кешев (первого, второго и третьего уровней), хаусхолдер делает гивенса как тузик грелку, а, если применить ранк-ревеалинг, то и по точности уделывает гивенса. Собственно по этому я послал ТС почитать немного об этом в очень понятно написанный источник, с надеждой, что ТС таки или расколется почему все-таки Гивенс, или такии возьмет стандартное и проверенное временем решение. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
lennox 0 11 ноября, 2021 Опубликовано 11 ноября, 2021 · Жалоба 11 hours ago, iiv said: ТС таки или расколется почему все-таки Гивенс, или такии возьмет стандартное и проверенное временем решение. потому что FPGA. сорри не указал в теме. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
enclis_ 0 12 ноября, 2021 Опубликовано 12 ноября, 2021 · Жалоба 23 hours ago, iiv said: ... компьютерная архитектура типа CUDA ... Даже если это не GPU или FPGA, сейчас во многих процессорах (и даже микроконтроллерах) уже есть довольно мощные NPU и прочие сопроцессоры для параллельных вычислений и работы с матрицами. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
iiv 29 12 ноября, 2021 Опубликовано 12 ноября, 2021 · Жалоба 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 13 ноября, 2021 Опубликовано 13 ноября, 2021 · Жалоба 21 hours ago, iiv said: правильно ли я понимаю, что под NPU вы понимаете neural processing unit? Если да, то каким они относятся боком к обычному QR, который делают без использования нейронных сетей либо Граммом-Шмидтом, либо Хаусхолдером, либо Гивенсом, иногда еще с применением ранг-ревеалинга? не, тогда колитесь дальше - какова размерность матрицы, и как эта размерность соотносится к числу умножителей, и будете ли вы все в честной IEEE плавающей точке считать, или есть желание в псевдо-целочисленной посчитать? 8x8 матрица канала. fixed point. я еще в процессе изучения QR по Гивенсу. для действительных чисел понял "механику" преобразования. Переписал псевдо код из книжки Matrix Computations, Golub на матлаб для real данных. Работает, но математику, т.е. почему обнулялся элемент матрицы, еще не до конца понял. Потом нужно понять как это сделать для комплексных чисел, потом разобраться что такое систолические массивы ну т.д. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
thermit 1 13 ноября, 2021 Опубликовано 13 ноября, 2021 (изменено) · Жалоба 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 13 ноября, 2021 Опубликовано 13 ноября, 2021 · Жалоба @iiv, так и будете придираться к каждому слову? ваш lapack не был в тему, на этом можно было закончить. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
iiv 29 16 ноября, 2021 Опубликовано 16 ноября, 2021 · Жалоба 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 29 18 ноября, 2021 Опубликовано 18 ноября, 2021 · Жалоба On 11/7/2021 at 8:38 PM, lennox said: я нашел https://www.google.com/patents/US8473539 , но может быть посоветуете еще что-нибудь? только сейчас внимательно прочитал, и реально протащился - запатентованный метод, что там излагается в виде общей теоретической блоксхемы мне в 1994 году на лекциях по вычислительной математике рассказывали. Да, во время лекции никто это за уши на ПЛИСки не притаскивал, но ведь запатентовали же потом через 15 лет! Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться