Устройство для решения систем ли-нейных уравнений c разреженнойматрицей

 

Союз Советскни

Социалкстическнк

Ресаублнк (61) Дополнительное к авт. саид-ву (22) Заявлено 201178 (21) 2685166 18-24 (51) М. Кл. с присоединением заявки Ио (23) Приоритет

G 06 F 15/324

Государствеииый комитет

СССР ао делам иэобретеиий и открытий

Опубликовано 150381 Бюллетень Ио10

Дата опубликования описания 15Q 331 (53) УДК 681. 14 (088. 8) (72) патрь изобретения

Л.Я.Нагорный и П.А.Лебедев

Киевский ордена Трудового Красного Знамени(внстйтут инженеров гражданской авиации

/ (71) Заявитель (54) УСТРОЙСТВО ДЛЯ РЕШЕНИЯ СИСТЕМ

ЛИНЕЙНЫХ УРАВНЕНИЙ С РАЗРЕЫЕННОЙ

ИАт Рице й

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

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

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

Наиболее близким по технической сущности и достигаемому результату к предлагаемому является устройство, содержащее первую, вторую и третью матрицы решающих блокон, ариФметический блок, блок упранления, блок вывода и индикации, .два программных блока, блок постоянной памяти, блок оперативной памяти, блок сравнения, блок ввода коэффициентов, три элемента ИЛИ, а каждый решающий блок содержит дна элемента И, элемент НЕ, регистр и элемент ИЛИ,каждый программный блок содержит счетчик столбцов и счетчик строк (2).

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

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

На чертеже представлена блок-схема устройства.

Устройство содержит матрицу 1 решающих блоков, арифметический блок 2, блок 3 управления, блок 4 вывода, программный блок 5, блок 6 постоян- 40 ной памяти, блок 7 сравнения, блок 8 ввода коэффициентов, элемент ИЛИ 9,блок

10 оперативкой памяти, счетчик 11 ст рок, с четчик 12 столбцов, решающий блок 13, элементы И 14, 15, элемент 45

HE 16, регистр 17, элемент ИЛИ 18 счетчик 19 синхронизации, В устройстве реализуется метод решения систем линейных уравнений с разреженной матрицой по частям. В общем случае система уравнений представляется в кратной форме:

Н ° X=q (1) где Н вЂ” неособенная матрица коэффициентов системы;

Х вЂ” вектор столбца неизвестных величин;

0 — известный вектор правых частей.

Используя операцию развертывания, исходную систему порядка и можно ф0 привести к виду

W 8 Хс (2)

65 где Х вЂ” квадратная подматрица связи;

Н вЂ” блочно-диагональная матрица исходной систеьн, содержащая N подматриц, размерностью 3.;

В ф — прямоугольные подматрицы после операции развертывания, количество которых равно N, размерностью

Х вЂ” вектор дополнительно введенных переменных;

 — порядок блочных матриц после разбиения сис тенг, Такая система решается по частям согласно ее разбиени я на прямоугольные блоки.

Согласно алгоритма определяется матричное произ ведение В и -1

В=Xe, ° H; ° ф;, (3) где Н, — обратная матрица подматрицы Н;.

Оп ределяем К (4)

Далее определяется вектор Q (с (5)

Находится йеизвестный вектор связи Х

Хс Кс 0ñ (6)

Далее определяются подвекторя О;, выраженные через вектор связи Хс, которые необходимы для окончательного решения по частям системя уравнений

Q,. =g,-ф Х, (7)

Далее решейие сводится к определению неизвестных подвекторов Х,,Х, Х,, ..., Х в виде матричного йроизведения

Х;=Н; 0 (8)

Полученные подвекторы Х; состоят из неизвестных численных величин вида

Ф

Х= Х., Х, ° ° . ° Х„=, Х, Х, Хиt

Устройство работает следующим образом, Счетчик 19 синхронизации вырабатывает синхронизирующие импульсы, которые поступают в блок 3 управления и арифметический блок 2 и стробируют обрабатываемую информацию, Информация в регистрах арифметического блока 2 обрабатывается при помощи микрокоманд, синхронизированных во в ремени счетчиком 19 синхронизации и поступающих с блока 3 Управления. Счетчик 19 синхронизации синхронизирует информацию так, что регистр 17 каждого решающего блока

13 матрицы 1 условно разбит на три регистра сс, 5, С по времени синхронизации, которое задает счетчик 19 синхронизации. Таким образом, в определенное время в одном регистре

17 можно хранить три числа в условно обозначенных регистрах а,,, с, 813444

25

40

S0

И

Следовательно, одна матрица 1 условно разбивается на три матрицы Ма, Мь, М по времени синхронизации определяемого счетчиком 19 синхронизации ° Регистр 17 каждого решающего блока прЕдставляет собой сдвиговый регистр с обратной связью через элемент НЕ 16 и элемент ИЛИ 18.

Один оборот регистра 17 равен времени счета счетчика синхронизации.

С помощью блока 8 ввода коэффициентов набираются построчно коэффициент за коэффициентом подматрицы

Н1, Прн наборе 1-ой строки счетчик

11 строк программного блока 5 устанавливается в 1-ое состояние,а при наборе первого коэффициента h счетчик 12 столбцов программного устройства 5 устанавливается в 1-ое состояние, по сигналам, поступающим с блока 8 ввода коэФфициентов. В этот момент счетчик строк 11 и счетчик столбцов 12 соответственно вырабатывают сигналы у„и 21, поступающие на входы второго элемента И

15 решающего блока 13 матрицы 1.

Таким образом произошел выбор реша- ющего блока С„„ . В эту ячейку С11 матрицы Мо заносится преобразованный на арифметическом блоке 2 коэффициент: h, При вводе коэффициента h<1 запускается блок 3 управления, который работает по микропрограмме преобразования коэффициентов подматрицы Н по методу разложения матрицы на треугольные множители с записью этих коэффициентов в виде таблицы множителей в матрицу М . Коэффициент 4„ заносится в арифметический блок 3, преобразуется и пересылается в ячейку С „решающего блока матрицы Мц через элемент И 15, на который поступает микрокоманда с блока 3 управления. Прн совпадении сигналов у, 21 и микрокоманды происходит запись элемента h«через элемент И 15, элемент ИЛИ 18 в регистр 17з, в котором h, хранится при помощи циклической перезаписи через элемент НЕ le и элемент ИЛИ 18.

Ввод последующих коэффициентов подматрицы Н осуществляется аналогично, при этом счетчик ll строк и счетчик 12 столбцов вырабатывают соответствующие координатные сигналы у и 2., которые выбирают соответствующйе решающие блоки С > мат- . рицы 1. Блок 7 сравнения сравнивает содержимое счетчиков строк и столбцов. Если эти счетчики равны, идет обработка диагональных элементов подматрицы Н1. Если содержимое счетчика 11 строк меньше содержимого счетчика 12 столбцов, то ведется обработка коэФФициентов выше главной диагонали подматрицы. Если содержимое счетчика 11 строк больше содержимого счетчика 12 столбцов, то об10

3S

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

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

Микропрограмм, выполняющие данные операции, служат, как микроподпрограммы для решения системы линейных уравнений.

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

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

ИЛИ 9 и арифметический блок 2.

Далее производится матричная операция умножения матрицы МЬ на матричные треугольные множители матрицы Ма. Результирующая матрица накапливается в матрице М, При умножении матриц коэффициенты вызываются в арифметический блок 2 через элемент ИЛИ 9 и происходит их умножение с алгебраическим накоплением.

Обратная матрица Н накапливаежя в матрице 1 М, Далее на блоке 8 ввода коэффициентов нажимается клавиша 6, это означает, что в матРиЦУ 1 Мо ввоДЯтсЯ коэффиЦиенты подматрицы 8 . Нажимается клавиша

Р

tl множить и происходит операция матричного умножения 61, на H„.Матричное произведение 6 Н хранится в матрице 1 Ма.

Нажимается клавиша Я и осуществляется ввод Q — часть йзвестного вектора, которая соответствует части матрицы Н . Ввод Q ïîýëåìåíòíî осуществляется в блок 10 оперативной памяти по микрокоманде с блока

3 управления, После этого нажимаетtl ся клавиша умножить и происходит матричное умножение матрицы мц на известный вектор Q >. Получим произведение 81 Н., ° Q1 йо выражению () в виде вектора размерностью Q .

Полученный вектор для накоплейия засылается в блок 6 постоянной памяти, где будет накапливаться вектор Q< по выражению (5).

По нажатию клавиши ф запускается блок 3 управления и происходит

8.1 3444 занесение коэффициентов подматрнцы

Ф1 в матрицу 1 Мф через арифметич ский блок 2 с блока 8 ввода коэффициенто, После чего нажимается

tI клавиша множить и происходит операция матричного умножения матрицы Мр на матрицы М . B результате получается матричное произведение 61 Н„ф, по выражению (3), которое хранится в матрице Мр.

Подматрица связи

Мс. Определяется Кс операцией матричного сложени я по выражению (4 )

Кс, =N -N =È - 9, Н 4 . Результат величнйы Кс накаплйвается в матри- це M .

Далее осуществляется ввод второй части исходной матрицы Н, т.е. осу-, ществляется последовательный ввод подматриц Н, eq, О» и 6» и про- делываются все матричные операции с этими подматрицами тем же способом, Последовательность нажатий клавиш остается без изменения.

После выполнения всех операций в блоке 6 постоянной памяти накалливается выражение 5, а в матри- .. це N накапливается результат К выражения (4) .

Осуществляя ввод последующих частей исходной матрицы Н по подматрицам Н;, 6 О; и 4;до последней части Н„, бк, Ощ и ф„и проделав матричные операции, получаем окончательный результат Qt и Кс по выражениям (5} и (4), которые накап- .ливаются соответственно в блоке б постоянной памяти и в матрице Nc.

Для определения неизвестного вектора связи Хс по выражению б нажимается клавиша Х, по которой происходит обращение К в обратную мат-1 с рицу К по методу прямых решений с использованием разложения матрицы на треугольные множители. Обращение идет тем же способом, когда находи-1 лась обратная матрица H1 . Далее происходит матричная операция умножения К ()с=Мр.Q .Äëÿ этого поэлементно на арифметический блок 2 вызываются Qt из блока б постоянной памяти и К из матрицы 1 Nt» через элемент ИЛИ 9. Результат вектора Х накапливается в блоке б постоянной памяти.

После получения вектора Х с можно на Ди неизвестный вектор Х по частям, Для этого нажимается клавиша Ф, по которой запускается блок 3 управления и происходит занесение коэффици-, ентов подматрицы Ф в матрицу 1 М .

По нажатию клавиши умножить происН ходит матричное умножение Ф1 Х © выражения (7) на арифметическом блоке

2 с вызовом поэлементно Ф„ и Хс из матрицы М и блока б постоянной памяти. Результат накапливается в блоке б постоянной памяти.

Х= Х1 Х .... Xtt Х Х Хз Х

1$

26

При нажатии клавиши Q осуществляется ввод Q1 — ЧастИ ИЗВестноГо вЕКтора в блок 10 оперативной памяти.

После ввода происходит векторное вычитание по выражению (7) „ = — Ф, Х

Вычитание происходит в арифметическом блоке с вызозом элементов вектора Q„ из блока 10 оперативной памяти и вектора Ф„ Х из блока б памяти. Результат засылается в блок б постоянной памяти.

Осуществляется ввод подматрицы

Н в .матрицу Мр. Находится обратная матрица Н1, которая записывается в матрицу М . После этого нажимаетIl с я клавиша „умножить, по которой происходит матричная операция умножения матрицы l Na на блок б постоянйой памяти, На арифметическом блоке 2 выполняется выражение (8) X„=H„ Q

t,1

Результат вектора Х, „ X» записывается в блок постоянной памяти. Численное значение найденного вектора Х передается в блок

4 вывода и индикации. Этот результат мэжет выпечатываться в устройстве вывода на бумажной ленте или высвечиваться на цифровом табло.

Осуществляется ввод последующих частей матрицы Н по подматрицам ф;, Q1 и Н; до последней части фн, Qtt, Нн . Произведя все матричные операции и вычисления по выражениям (7) и (8) получим все численные значения вектора Х

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

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

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

813444

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

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

Источники информации, принятые во внимание при экспертизе

20 1. Авторское свидетельство СССР

9 294144, кл. G 06 F 15/32, 1971.

2. Авторское свидетельство СССР по заявке 9 2531210/18-24, кл. 6 Об Р 15/32, 1977 (прототип) °

813444

Сос тави тель H. Палеева

Редактор И. Касарда Техред N.Табакович Корректор Е. Рошко

Заказ 775/63 Тираи 745 Подписное

ВНИИПИ Государстаенного комитета СССР по делам изобретений и открытий

113035, Москва, X-35, Раушская наб., д.4/5 филиал ППП Патент, r.уигород, ул.Проектная, 4