Решение систем уравнений

Любая система линейных уравнений может быть описана в матричной форме как

где матрица известных данных, действительно ли-by-1 является вектором из неизвестных, и действительно ли-by-1 является вектором.

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

Любая матрица может анализироваться как

где, верхней треугольной матрицей и единичная матрица. Это позволяет нам преобразовывать систему уравнений в верхнюю треугольную форму

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

Алгоритм разложения CORDIC QR

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

Оборудование эффективные матричные расчеты фиксированной точки

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

При развертывании сложных алгоритмов в FPGA или устройства ASIC, часто существует компромисс между использованием ресурсов расчета и его общей пропускной способностью. В то время как полностью конвейерный и параллелизировано алгоритмы имеют самую большую пропускную способность, они являются часто слишком интенсивно использующими ресурсы, чтобы развернуться на физических устройствах. Путем реализации планирования логики вокруг одной или нескольких базовых вычислительных схем возможно снова использовать ресурсы в течение расчета. Результатом является реализация с намного меньшим местом, хотя за счет общей пропускной способности. Это часто - приемлемый компромисс, когда совместно использованные проекты ресурса могут все еще удовлетворить полные требования задержки.

Все ключевые вычислительные модули в Действительной Пакетной Матрице Решают использование, Разложение QR снова используется в жизненном цикле расчета. Это включает не, только схема CORDIC раньше выполняла вращения Givens во время разложения QR, но также и сумматоры и множители, используемые во время задней замены. Это сохраняет и DSP и ресурсы матрицы при развертывании к устройствам ASIC или FPGA.

Поддерживаемые типы данных

В симуляции одна, дважды, двоичная точка масштабировала фиксированную точку, и двоичная точка масштабировалась дважды, данные поддерживаются. Однако для генерации HDL-кода, только двоичная точка масштабировалась, фиксированные точки поддерживаются.

Параметры для действительной пакетной матрицы решают

Действительная Пакетная Матрица Решает использование, КР Декомпосайшн использует матрицы A и B или от рабочего пространства модели или от базового рабочего пространства, чтобы задать систему уравнений, чтобы решить. Требуется четыре входных параметра на своей маске: количество строк в матрицах A и B, количество столбцов в матричном A, количество столбцов в матричном B, и выходной тип данных. Маску блока показывают ниже.

Эти параметры заданы в рабочей области переменными mNP, и OutputType, соответственно. Кроме того, переменная num_samples потребности, которые будут заданы в рабочем пространстве модели или базовом рабочем пространстве.

Подготовка Данных модели

Чтобы начаться, мы должны к серии систем уравнений решить. Данные о реальном мире часто прибывают из Гауссовых ансамблей, таким образом, случайные матрицы, чертившие от стандартного нормального распределения, будут использоваться в этом примере. Стандартное нормальное распределение имеет среднее значение 0 и отклонение 1. Его свойства описывают многих, хотя не все, источники найденной в природе случайности. На основании этого мы будем использовать данные, чертившие от этого распределения как пример, чтобы продемонстрировать, как использовать Действительную Пакетную Матрицу, Решают использование Разложение QR.

Во-первых, выберите размер для решаемой системы.

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

Затем сгенерируйте случайные, данные с двойной точностью. Эти данные используются в качестве числового сравнительного теста для необходимого динамического диапазона. Это полезно при преобразовании в фиксированную точку.

A = randn(m,n,num_samples);
B = randn(m,p,num_samples);

Здесь, первые два индекса соответствуют матричным индексам в каждой выборке, в то время как третий индекс соответствует демонстрационному номеру. Например, A(1,2,3) соответствует элементу в первой строке и втором столбце третьей выборки.

Сгенерируйте модель в качестве примера для арифметики с плавающей точкой

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

Чтобы сгенерировать версию с плавающей точкой модели, используйте вызов функции ниже.

mdl = fixed.getMatrixSolveModel(A,B);

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

Передача данных от источника до матрицы решает блок

Модель, сгенерированная функцией выше, уже сконфигурирована, чтобы симулировать без модификации. Сгенерированная модель использует блок под названием Обработчик Данных, чтобы отправить данные в матричный решатель. Это связывается с матричным решателем путем слушания готового порта решателя и получения по запросу validIn высоко на возрастающее ребро ready. Это говорит, что Действительная Пакетная Матрица Решает использование Разложение QR, что текущие строки в портах А (i, :) и B (i, :) допустима. Каждый раз, когда готовый и допустимый одновременно высоки, данные этих портов обработаны как следующая допустимая строка матрицы.

Каждый раз, когда решатель видит, что и готовый и validIn верны, это использует ввод данных в портах А (i, :) и B (i, :). Это должно сохранить validIn сохраненным высоко, если это хочет сделать так. Затем Действительная Пакетная Матрица Решают использование, Разложение QR будет содержать эту строку в буфере, пока это не будет готово обработать его. Этот режим работы показывают ниже, в котором используются две выборки.

Каждый раз, когда готовые движения высоко, это может использовать две строки. Если две строки отправляются, Действительная Пакетная Матрица Решают использование, Разложение QR сохранит вторую строку во внутреннем buffer.It, не обязательно, чтобы отправить, две строки, когда готовый утверждается, и если только одна выборка отправляется, потому что validIn является deasserted, готовое желание deassert, и только подтвердите, когда больше данных является потребностью в расчете.

Обратите внимание на то, что добавление дополнительных задержек или пути с готового на Обработчик Данных, или между Обработчиком Данных к validIn добавит противодавление, которое не ожидается. В этом сценарии будут пропущены выборки. Мы рекомендуем, чтобы вы или только отправили данные по переднему краю ready, или что вы не вставляете дополнительные задержки между блоком и источником данных. Кроме того, если вы планируете сгенерировать HDL-код с помощью этого блока, мы рекомендуем выключить оптимизацию конвейеризации, когда они могут добавить задержки на этих путях.

Симулируйте модель

Чтобы симулировать модель, нажмите симулировать кнопку или используйте sim команда.

out = sim(mdl);

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

Действительная Пакетная Матрица Решает QR Decomposition использования данные выходных параметров одна строка за один раз. Каждый раз, когда блок выводит строку результата, он утверждает validOut. Решение выводится в поле X_out в переменной out. Эти данные все еще хранимы как 1 - p - n*num_samples массив строк. Прежде, чем оценить точность решения в MATLAB®, удобно преобразовать его в n - p - num_samples массив. Это может быть сделано со служебной функцией matrixSolveOutputToMatrix.

X = matrixSolveOutputToMatrix(out.X_out,n,p,num_samples);

Вычислите ожидаемое решение в MATLAB®

Точность решения, вычисленного в нашей модели Simulink®, может легко быть вычислена в MATLAB®. Обратите внимание на то, что теория ожидает, что относительная погрешность решения системы увеличивается с числом обусловленности матрицы. Чтобы видеть это, мы построим ошибку, данную по

против числа обусловленности.

condNumber = zeros(1,num_samples);
relativeError = zeros(1,num_samples);
for idx = 1:num_samples
   condNumber(idx) = cond(A(:,:,idx));
   relativeError(idx) = norm(B(:,:,idx) -  A(:,:,idx)*X(:,:,idx))./norm(B(:,:,idx));
end

Постройте выход

Теперь постройте выход ошибочного вычисления. Обратите внимание на то, что логарифмические шкалы используются на обеих осях, когда и числа обусловленности и ошибки охватывают несколько порядков величины. Положительная корреляция между этими двумя значениями довольно ясна здесь.

figure(1);
clf;
h1 = axes();
hold on;
plot(condNumber,relativeError,'bo');
h1.XScale = 'log';
h1.YScale = 'log';
xlabel('cond(A)');
ylabel('Relative Error');

Создание Версии Фиксированной точки модели

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

Выбор входного типа данных

Для Действительного Пакета Разложение QR, тип R(i,:) совпадает с типом A(i,:). Точно так же тип C(i,:) совпадает с типом B(i,:). Эти типы используются в течение вычисления. Таким образом входные типы данных должны вместить самые большие значения, необходимые в вычислении каждого R(i,:) и C(i,:).

Существует два эффекта, которые заставляют входные данные расти в величине во время расчета: рост элементов в A из-за Евклидовой природы сохранения нормы вращений, используемых в Разложении QR и внутреннем внутреннем росте реализации CORDIC этих вращений. Эти два эффекта связали элементы выходных параметров в величине

ceil(log2(1.65*sqrt(m)*max(abs(A(:)))))

для R(i,:), и

ceil(log2(1.65*sqrt(m)*max(abs(B(:)))))

для C(i,:). В этом примере, начиная с A и B чертились от того же статистического распределения, мы даем обоим тот же размер слова и дробную длину. В общем случае A и B не должны иметь той же дробной длины, при условии, что у них есть тот же размер слова.

maximumAbsValueInDataset = max(max(abs(A(:))),max(abs(B(:))))
inputIntegerLength = ceil(log2(1.65*sqrt(m)*maximumAbsValueInDataset))

maximumAbsValueInDataset =

    3.5784


inputIntegerLength =

     4

Мы будем использовать 18 битов wordlength тип как наш вход. Это может быть изменено, чтобы удовлетворить различным приложениям. Та переменная inputType вычисленный ниже кодирует информацию о типе в объекте NumericType.

inputWordLength = 18
inputFractionLength = 18 - inputIntegerLength - 1
inputType = numerictype(1, inputWordLength, inputFractionLength)

inputWordLength =

    18


inputFractionLength =

    13


inputType =


          DataTypeMode: Fixed-point: binary point scaling
            Signedness: Signed
            WordLength: 18
        FractionLength: 13

Для подробного описания границ роста в Алгоритме разложения CORDIC QR смотрите, Предотвращают Переполнение в Фиксированной точке R.

Вычислите Необходимый Динамический диапазон для Обратной замены

Данные могут также вырасти в заднем фрагменте замены алгоритма из-за деления маленькими значениями. Путем симуляции с соответствующими входными данными возможно сделать хороший выходной выбор типа данных. Для этого шага, величины выходного значения X(i,:) ограничен

1.65*sqrt(m)*max(abs(B(:)))/sigma_min,

где sigma_min самое маленькое сингулярное значение, наблюдаемое через все наши демонстрационные матрицы. Эти значения вычисляются ниже.

sigma = zeros(1, num_samples);
for idx = 1:num_samples
    sigma(idx) = min(svd(A(:,:,idx)));
end
sigma_min = min(sigma);
backsubstituteWordlengthGrowth = ceil(log2(1.65*sqrt(m)/sigma_min));

Это дает выходной тип данных, данный как показано ниже

outputWordlength = inputWordLength + backsubstituteWordlengthGrowth
outputFractionLength = inputFractionLength
OutputType = numerictype(1, outputWordlength, outputFractionLength)

outputWordlength =

    30


outputFractionLength =

    13


OutputType =


          DataTypeMode: Fixed-point: binary point scaling
            Signedness: Signed
            WordLength: 30
        FractionLength: 13

Создайте версию фиксированной точки модели

Чтобы симулировать в фиксированной точке, сначала преобразуйте входные данные в расчетный входной тип.

A_Fixed = fi(A, inputType);
B_Fixed = fi(B, inputType);

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

mdl_fi = fixed.getMatrixSolveModel(A_Fixed, B_Fixed, OutputType);

Симулируйте модель в фиксированной точке

out_fi = sim(mdl_fi);

Сохраните фиксированную точку Выход в MATLAB® Array

X_fi = matrixSolveOutputToMatrix(out_fi.X_out,n,p,num_samples);

Вычислите ожидаемое решение в MATLAB®

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

relativeErrorFixedPoint = zeros(1, num_samples);
for idx = 1:num_samples
   relativeErrorFixedPoint(idx) = norm(double(B_Fixed(:,:,idx) -  A_Fixed(:,:,idx)*X_fi(:,:,idx)))./norm(double(B_Fixed(:,:,idx)));
end

Постройте выход

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

figure(2);
clf;
h2 = axes();
hold on;
plot(condNumber,relativeErrorFixedPoint,'bo');
h2.XScale = 'log';
h2.YScale = 'log';
xlabel('cond(A)');
ylabel('Relative Error');