Устройство для решения систем линейных алгебраических уравнений

 

Изобретение относится к вычислительной технике и может быть использовано в высокопроизводительных специализированных вычислительных машинах и устройствах обработки сигналов для решения систем линейных алгебраических уравнений. Цель изобретения - сокращение объема оборудования устройства за счет решения системы n линейных алгебраических уравнений с помощью фиксированного числа l вычислительных модулей при l < n. Цель достигается тем, что устройство содержит l вычислительных модулей, p параллельных регистров, где p = (n + 1) (n + m) - l(n + 3), m - число столбцов в правой части системы линейных алгебраических уравнений, два сдвигающих p-разрядных регистра, блок элементов ИЛИ и два элемента ИЛИ, причем каждый вычислительный модуль содержит три триггера, узел задержки на n тактов, два триггера, две группы триггеров, умножитель, узел вычисления обратной величины числа, вычитатель, девять групп элементов И, четыре группы элементов ИЛИ, пять элементов И и два элемента НЕ. 2 ил.

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

Цель изобретения сокращение аппаратурных затрат.

На фиг. 1 представлена структурная схема устройства для решения систем линейных алгебраических уравнений; на фиг. 2 функциональная схема вычислительного модуля.

Устройство для решения систем линейных алгебраических уравнений (фиг. 1) содержит информационный вход 1, первый 2 и второй 3 входы режима, синхровход 4, вычислительные модули 5_i (i ), узел сдвигающих регистров 6_i (i ), первый 7 и второй 8 сдвигающие регистры, блок 9 элементов ИЛИ, первый 10 и второй 11 элементы ИЛИ, информационный выход 12.

Вычислительный модуль 5 (фиг. 2) содержит информационный вход 13, первый 14 и второй 15 входы режима, синхровход 16, первый 17, второй 18 и третий 19 регистры, узел 20 задержки на n тактов, регистры 21_i (i ), узел 22 вычисления обратной величины числа, умножитель 23, вычитатель 24, первый 25 и второй 26 триггеры, первый 27 и второй 28 блоки триггеров, триггеры 29_i первого блока (i ), триггеры 30_iвторого блока (i ), блоки 31-39 элементов И, блоки 40-43 элементов ИЛИ, элементы И 44-48, элементы НЕ 49, 50, первый 51, второй 52 и третий 53 выходы.

В основу работы устройства положен метод Гаусса-Жордана для решения СЛАУ, который представляется следующими рекурpентными соотношениями: a^(o_ij⁾ a_ij, i , j k a^(k_kk⁾= a^(k_kk^-1) a^(k_kj⁾= a^(k_kj^-1)/a^(k_kk⁾, j a^(k_ik⁾= a^(k_ik^-1), i a^(k_ij⁾= a^(k_ij^-1)- a^(k_ik⁾ a^(k_kj⁾_, i , j a^(k)_n+k,j= a^(k_kj⁾, j x_ij= a⁽ⁿ⁾_n+i,n+j, i , j При описании работы устройства в обозначении а^(k) индекс k в скобках указывает номер рекуррентного шага.

Вычислительный модуль 5 выполняет следующие функции:
U^{j+n+3 j};
V^{j+n+3 j}, где ^{j j} значения на первом 14 и втором 15 входах режима вычислительного модуля на j-м такте;
U^j, V^j значения на втором 52 и третьем 53 выходах вычислительного модуля на j-м такте.

W^j+1 где а^j значение на информационном входе вычислительного модуля на j-м такте;
bj a^j/a^j-m(n+1) при ( ^{j j} ) (1,0)
c^j a^j при ( ^{j j} ) (1,1),
р, m некоторые числа, определяемые алгоритмом;
W^j значение на первом выходе 51 вычислительного модуля на j-м такте.

Устройство работает следующим образом.

На вход 1 подаются элементы а_ij (i , j ) в моменты времени
t= i + (n+1)j n-2.

Управляющие сигналы ( ) подаются на входы 2 и 3 режима следующим образом: начиная с нулевого момента времени, они подаются последовательно n+1 раз ( ) (1,1), затем последовательно в порядке перечисления подается группа из n+1 управляющих сигналов ( ) (1,0), (0,0),(0,0), (0,1), которая повторяется еще n+m-2 раз.

Результаты вычислений x_ij(i , j ) для случая n/l целое число формируются на выходе 12 устройства в моменты времени
t= (n/l-1)(n+1)(n+m) + (l-1)(n+3) + i + (n+1)j + 1.

Если n/l нецелое число, то следует рассматривать систему уравнений вида , где , и и матрицы размеров соответственно n' x n', n' x m и n' x m, а n' наименьшее целое из всех чисел, кратных l и больших n, причем матрица получена добавлением к A₂(n'-n) нулевых строк, а матрица добавлением к A₁(n'-n) новых строк и столбцов, все элементы которых равны нулю, за исключением лежащих на диагонали, равных единице. При таком расширении первые n строк матрицы определяют решение Х, а остальные строки нулевые.

Формула изобретения

УСТРОЙСТВО ДЛЯ РЕШЕНИЯ СИСТЕМ ЛИНЕЙНЫХ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ, содержащее l вычислительных модулей, где l целое число, l < n, n порядок системы линейных алгебраических уравнений, причем первый выход i-го вычислительного модуля, где i 1, l 1, подключен к информационному входу (i + 1)-го вычислительного модуля, первый выход l-го вычислительного модуля подключен к выходу результата устройства, второй и третий выходы i-го вычислительного модуля подключены соответственно к первому и второму входам режима (i + 1)-го вычислительного модуля, синхровход устройства подключен к синхровходам всех вычислительных модулей, отличающееся тем, что, с целью сокращения аппаратурных затрат, оно содержит узел сдвигающих регистров, первый и второй сдвигающие регистры, блок элементов ИЛИ, первый и второй элементы ИЛИ, причем первый информационный вход устройства подключен к первому входу блока элементов ИЛИ, выход которого подключен к информационному входу первого вычислительного модуля, информационный выход l-го вычислительного модуля подключен к информационному входу узла сдвигающих регистров, выход переноса которого подключен к второму входу блока элементов ИЛИ, первый и второй входы режима устройства подключены соответственно к первым входам первого и второго элементов ИЛИ, выходы которых подключены к первому и второму входам режима первого вычислительного модуля, второй и третий выходы l-го вычислительного модуля подключены соответственно к информационным входам первого и второго сдвигающих регистров, выходы которых подключены соответственно к вторым входам первого и второго элементов ИЛИ, синхровход устройства подключен к входам сдвига всех сдвигающих регистров и узла сдвигающих регистров.