Устройство для операций над матрицами Советский патент 1979 года по МПК G06F17/16 

(54) УСТРОЙСТВО ДЛЯ ОПЕРАЦИЙ НАД МАТРИЦАМИ

Устройство относится к области вычиспитепьной техники и может быть использовано для приближенного вычиспени произведения цепочки матриц произврпьной длины, возведения матриц в степень вычисления матричных функционалов, .суммирования степенных матричных рядов с произвольными коэффициентами, обращения матриц, решения систем линейнь1к а1тгебраических уравнений. Известно специализированное устройство вероятностного типа для решения матричных задач Д , содержащее блок памяти на фотоэлектронных трубках и фотопленках и устройство управления: Недостатком известного устройства является ограниченность функциональных возможностей. Наиболее близким по тезшической сущности к данному изобретению явпяет устройство для операций над матрицами 2, содержащее блок ввода-вьгаода, блок управления и блок оперативной памяти, соединенный двухсторонними связями с блоком ввода-вывода. Однако это устройство требует предварительной нормализации матриц-сомножителей, что существенно увеличивает время решения при операциях над матрицами большой разномернссти, в его схеме имеется П -полюсник, что сильно усложняет схему. Кромр того, устройство не позволяет решать системы линейных алгебраических уравнений. Цель изобретения - повьшение надежности и расширение класса решаемых задач. Поставленная цель достигается тем, что устройство содержит блок памяти коэффициентов, датчик случайных чисел, дешифратор, блок контроля на нудь, блок умножения, блок умножения на коэффициенты и сумматор, причем вход блока памяти коэффициентов соединен с выходом блока ввода-вьгоода, а выход блока памяти коэффициентов соединен со вторым входом блока умножения на коэффициенты, первый выход блока управления соеоинен с первым входом бпока оператив.ной памяти, второй выход - с первым входом бпока умножения на коэффициент третий BbixojB - СОвторым входом сумм тора, а четвертый выход бпока управления - со входом датчика случайных чисел; выхо)з которого соединен со вхо дом дешифратора, выход дешифратора соединен со вторым входом блока опера тивной памяти, выход которого соединен с первым входом бпока контропя на нуль, первый выход которого соединен со входом блока управления, второй выход - с третьим входом блока умножения на коэффициенты, а третий выход входом блока умножения, выход которого соединен со вторым входом бпок контроля на нуль; выход бпока умножения на коэффициенты соединен с первым входом сумматора, выход которого соединен с третьим входом блока оперативной памяти. На чертеже представлена блок-схема предлагаемого устройства. Устройство операций над матрицами содержит блок 1 ввода-вьгоода, блок 2 оперативной памяти, блок 3 памяти коэ фициентов, блок управления 4, Датчик 5 случайных чисел, дешифратор 6, блок 7 контроля на нуль, блок умножения 8, блок О умножения на коэффициен ты, сумматор 1О. В основу работы предлагаемого устройства положен метод Монте-1 арло с формированием сомножителей по стохастической трассе, определяемой в результате случайных розыгрышей. При этом не требуется предварительной ндрмализации обрабатываемых матриц, что сильно сокращает время обработки матриц большей размерности.; Работа устройства состоит в следующем.. 1. Через блок 1 ввода-вывода вводятся. нсхош1ые данные в зависимости от цели использования устройства: или группа перемножаемых матриц, или матрица, возводимая в степень, или пер менная матрица ф нкционапа, иш основ ная матрица матричного ряда, или обращаемая матрица, или матрица коэффициентов при решении систем алгебраических уравнений. Все элементы вводи мой матрицы умножпкпся на величину выходной размерности матрицы, равную ЧИСЛУ столбцов. В блок 2 оперативной памяти вводятся перемножаемая последовательность матриц, в блок 3 памяти коэффициентов - единицы. Результирующая матрица вычисляется построчно. Можно вычислить любую произвольную строку, либо группу строк. Требуемая группа задается через блок управления 4, Если вычисляется вся матрица произведения, то устройством автоматически вычисляются все строки матрицы, начиная с первой. Блок управления 4 определяет исхош1ый номер строки | первой матрицы А i ; с которой начинается испытание. Затем блок управления 4 включает датчик 5 случайных чисел, вырабатьгеающий равномерно распределенное случайное число, .которое поступает в. дешифратор 6. Дешифратор определяет номер j столбца первой матрицы, из которого выбирается элемент а, :,исходя из соотношения значений полученного случайного числа и вероятности выбора элемента, равной J / Ч , где П 1 -число постолбцов матрицы. Элемент otVj ступает в блок 7 контроля на нуль, гйе он проверяется на нуль. Если & не равен О, то он поступает в блок умножения, если равен О, то испытание считается законченным, и блок 7 контропя на нуль включает блок управления 4, который да, т команду на начало нового испытания. Ее ли а j -не равен О, то испытание продолжается. Номер j элемента а Л определяет номер строки матрицы 7 которой датчиком 5 случайных чисеп и дешифратором случайным образом выбирается элемент dim, номер которого указывает на |U строку матрицы А «.Элемент о i OJ проверяется в блоке 7 контроля на нуль и, если он не равен нулю, поступает в блок умножения 8 и -умножа ется с ранее заведенным коэффициентом C3t j : . Произведение а j: к Qjiu проверяется в блоке 7 контроля на нуль на машинной нуль. Если оно равно, нулю, испытание заканчивается, и управление передается блоку 4 управления, котоиспытание. Если начинает новое (il Q не равно машинному нулю. то выбирается jU строка матрицы и описанная процедура повторяется до выбора элемента f из последней умножа- . смой aтpицы. Полученное произведение j 5м Й умножается в блоке 9 умножения на коэффициенты на единицу и заносится в ячейку суммирующего устройства с номером г , гд b -номер п следнего выбранного элемента, командой блока управления 4. На этом заканчивается одно испЁ1тание. Дпя вычиспения каждой строки матрицы произведения проводится N испытаний, где выбирается из требований точности и надежности определения элемен тов матрицы произведения. Всякий раз числа получаемые в бпоке умножения 8 после каждого испытания вспедствие спучайисстн строемой трассы будут слу чайны. Среднее арифь/1етическое по N трассам, зафиксированное в ячейках сумматора 10, будут являться приближе ными значениями V строки результиру щей матрицы произведения, где номер строки, с которой начинается сто хастическая трасса (испытание). Найден ная { строка матрицы произведения записьгеается в бпок 2 оперативной памяти на.место i строки первой матриц 2.При возведении матрицы в степен предлагаемое устройство работает так же, как и при умножении матриц, но в блок 2 оперативной памяти записьтаегся только одна матрица, возводимая в степень. В блок 3 памяти коэффициентов записьтаются единицы. Процесс построения стохастической трассы зацикливается на одну и ту же матрицу, и количество циклов определяется показателем степени, в которую возводится матрица. 3.При вычислении матричных функционалов в блоке 2 оперативной памяти записывается основная матрица функционала, в блок 3 памяти коэффициентов - коэффициенты функционала. Устройство работает так же, как и при возведении матрицы в степень. 4.При суммировании матричных рядов с произвольными коэффициентами в бпоке 2 оперативной памяти записывается матрица ряда, в блок 3 памяти коэффициентов записьгоаются коэффициенты ряда. Процесс построения стохастической трассы аналогичен процессу при возведении матрицы в степень. 5.При обращении матрицы в блок 2 оперативной памяти записывается обращаемая матрица, в блок 3 памяти, коэффициентов - единицы. Устройство работает так, как при суммировании матричных рядов с коэффициентами ряда, равными единице. 6.При решении системы линейных алгебраических уравнений в блок 2 оперативной памяти паписыв-иотся )и- 11Ы КОЭффиЦИ€ } ТОБ, В бЛОК 3 ПвМЯТИ коэффициентов - вектор свободных членов. Так как метод, реализуемый в устройстве, не требует предварительной операции нормализации обрабатываемых , матриц, то число подготовительных операций сокращается в X N j раз, где N-.-размерность с обрабатьгоасмой матрицы; К - количестве матриц. Предлагаемое устройство содержит только датчик случайных равномерно распределенных чисел, а не вероятностный, П - полюсник, что дает эффект упрощения схемы, сокращения требуекюго оборудования, а следовательно, повьтгения надежности схемы. Формула изобретения Устройство для операций над матрицами, содержащее блок ввода-вывода, блок управления и блок оперативной памяти, соединенный двухсторонними связями с блоком ввода-вывода, о тличающееся тем, что, с целью повышения надежности и расширения класса решаемых задач, оно содержит блок памяти коэффициентов, датчик случайных чисел, дешифратор, блок контроля на нуль, блок умножения, блок умножения на коэффициенты и сумматор, причем вход блока памяти коэф }«ициентов соединен с выходом блока ввода-сывода, а выход блока памяти коэффициентов соединен со вторым входом блока умножения на коэффициенты, первый выход блока управления соединен с первым входом блока оперативной памяти, второй выход - с первым входом блока умножения на коэффициенты, третий выход - со вторым входом сумматора, а четвертый выход блока управления - со входом датчика случайных чисел, выход которого соединен-ее входом дешифратора, выход дешифратора соединен со вторым входом блока оперативной памяти, выход которого соединен с первым входом блока контроля на нуль, первый выход которого соединен со входом блока управления, второй выход - с третьим входом блока умножения на коэффициенты, а третий выход - со входом блока умножения, выход которого соединен со вторым входом блбка контроля на нуль, выход бпока умножения на коэффициенты сое647687

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

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

8

2,Автс ское свидетельство СССР

5 №208340, кп. Q 06 F 15/36, 1965.

aij.