Реализуйте эффективный оборудованием пакет разложение QR

Открыть скрипт

Этот пример демонстрирует, как вычислить разложение QR матриц с помощью эффективного оборудованием кода MATLAB® в Simulink®. Эта модель совместно использует вычислительные ресурсы через шаги алгоритма разложения QR. Это таким образом использует меньше ресурсов на чипе, чем полностью конвейерный подход при принесении в жертву некоторой общей пропускной способности.

Решение матричных уравнений с разложением QR

При решении матричных уравнений редко, если когда-либо, необходимо вычислить инверсию матрицы [1] [3]. Блок Real Burst QR Decomposition предоставляет оборудованию эффективный способ решить уравнение

$Ax = B$

где $A$ m x n матрица, $x$ является n x p матрица и $B$ является m x p матрица. Это уравнение может быть преобразовано в форму

$Rx = Q^TB$

через ряд ортогональных преобразований. Здесь, $R$ m x n верхняя треугольная матрица, таким образом что $QR = A$ . Блок Real Burst QR Decomposition сохраняет только ненулевые строки $R$ , наряду с соответствующими строками $Q^TB$ .

Разложение QR хорошо подходит для архитектур фиксированной точки, потому что оно может быть полностью выполнено с вращениями Givens. Они имеют эффективную реализацию фиксированной точки в терминах алгоритма CORDIC. Для получения дополнительной информации об алгоритме для фиксированной точки разложение QR смотрите, Выполняют QR-факторизацию Используя CORDIC.

Чтобы начаться, откройте модель Simulink fxpdemo_real_burst_QR_model.

open_system('fxpdemo_real_burst_QR_model');

Эта модель работает с фиксированной точкой, дважды, одним, и масштабируемыми двойными типами данных. Полностью конвейерная версия этого алгоритма реализована в Simulink. Смотрите Реализацию Эффективное Оборудованием Разложение QR Используя CORDIC в Систолическом Массиве.

Введите параметры для действительного пакета разложение QR

Блок Real Burst QR Decomposition берет четыре входных параметра. Маску для этого блока показывают ниже:

Необходимо присвоить входные данные переменным в рабочем пространстве MATLAB. Чтобы настроить этот алгоритм, измените данные согласно процедурам, используемым в следующих разделах.

Задайте матричные размерности

Архитектура модели выделяет минимальную память, необходимую, чтобы хранить данные, должен был выполнить разложение QR. Поэтому размер входных матриц должен быть известен во время компиляции. Здесь, m количество строк в матрицах A и BN количество столбцов в A, и p количество столбцов в B.

Кроме того, поскольку блок может обработать разложение неопределенного количества матриц последовательно, много выборок задан. Модель завершает работу, когда все выборки использовались.

m = 4;
n = 4;
p = 4;
num_samples = 100;

Входные Define типы данных

Прежде, чем сгенерировать входные данные, важно задать тип данных матричных данных как показано ниже. Этот пример использует подписанные фиксированные точки с 16-битными размерами слова. Поскольку данные могут вырасти на коэффициент $sqrt(m)$ при вычислении матричного R, мы используем это ограничение, чтобы убедиться, что целая часть типа данных является достаточно большой. Смотрите Выполняют QR-факторизацию Используя CORDIC для получения дальнейшей информации.

word_length = 16;
integer_length = nextpow2(sqrt(m)) + 1;
fraction_length = word_length - 1 - integer_length;
nt = numerictype(1,word_length,fraction_length);

Задайте количество итераций CORDIC

Приближение CORDIC для вращений Givens является итеративным алгоритмом, который дает дополнительный бит точности на итерацию. Для типов данных фиксированной точки со знаком достигается самая большая точность, когда количество выполняемых итераций является тем меньше, чем wordlength.

NumberOfCORDICIterations = word_length - 1;

Инициализируйте случайные данные

Обработчик данных в этом примере берет матрицы A и B как входные параметры. В этом примере, A и B заданы как случайные элементы матриц, полученные из равномерного распределения от-1 до 1. Обратите внимание на то, что A и B каждый заданы как 3D массивы, где каждая демонстрационная матрица хранится в первых двух размерностях.

A = fi(2*(rand(m,n,num_samples) - 0.5),nt);
B = fi(2*(rand(m,p,num_samples) - 0.5),nt);

Передача данных к действительному пакету разложение QR

ready порт инициировал подсистему Обработчика Данных. Когда ready высоко, блок утверждает validIn и отправляет следующую строку A и B к aIn и bIn. Протокол для передачи данных позволяет данным быть отправленными каждый раз, когда готовый высоко, гарантируя, что все данные обрабатываются. Если данные отправляются, когда готовый не высоко, они не будут обработаны.

Обработка Выходных параметров

Блок Real Burst QR Decomposition выходные данные одна строка за один раз. Каждый раз, когда блок выводит строку результата, он утверждает validOut. Обратите внимание на то, что rOut выводит строки R, в то время как cOut выводит строки $Q^TB$ . Строки выводятся в обратном порядке, когда это - естественный порядок, чтобы использовать их для задней замены. В этом примере они сохранены как m * num_samples x n matrices, со строками, упорядоченными, когда они были получены.

Симулировать

sim fxpdemo_real_burst_QR_model

Восстановите решения от выходных данных

Поскольку данные выводятся в обратном порядке, необходимо восстановить данные, чтобы интерпретировать результаты. Следующий код помещает данные в правильном порядке.

C = cell(1,num_samples);
R = cell(1,num_samples);
for ii = 1:num_samples
    C{ii} = flipud(C_Out((ii-1)*m + 1:ii*m,:));
    R{ii} = flipud(R_Out((ii-1)*m + 1:ii*m,:));
end

Оцените точность результата

Чтобы оценить точность блока Real Burst QR Decomposition, исследуйте величину различия между решением матричного уравнения с помощью блока Real Burst QR Decomposition и полученное использование, которое удваивает встроенный backsolve MATLAB для. Постройте абсолютную погрешность и число обусловленности для каждой выборки. Данные показывают, что точность решения отслеживает число обусловленности, как ожидается [2].

xAct = cell(1,num_samples);
xExp = cell(1,num_samples);
xErr = zeros(1,num_samples);
condNumber = zeros(1,num_samples);
for ii = 1:num_samples
    xAct{ii} = double(R{ii})\double(C{ii});
    xExp{ii} = double(A(:,:,ii))\double(B(:,:,ii));
    xErr(ii) = norm(xAct{ii} - xExp{ii});
    condNumber(ii) = cond(double(A(:,:,ii)));
end
figure(1)
clf
h1 = subplot(2,1,1);
hold on;
h1.YScale = 'log';
plot(xErr)
grid on
title('Error of ''Real Burst QR Decomposition''');
ylabel('norm(R\\C - A\\B)');
h2 = subplot(2,1,2);
hold on;
h2.YScale = 'log';
plot(condNumber);
grid on
title('Condition Number of Samples');
ylabel('cond(A)');
xlabel('Test Point');
linkaxes([h1,h2],'x');

Закройте модель

close_system fxpdemo_real_burst_QR_model

Ссылки

[1] Джордж Э. Форсайт, М.А. Молком, и Клив Б. Молер. Компьютерные методы для математических вычислений. Englewood Cliffs, Нью-Джерси: Prentice Hall, 1977.

[2] Клив Б. Молер. Каково Число обусловленности Матрицы?, MathWorks, Inc. 2017.

[3] Клив Б. Молер. Числовое вычисление с MATLAB. SIAM, 2004. ISBN: 978-0-898716-60-3.

Документация