Устройство для вычисления собственных значений ( @ @ @ ) - матрицы Советский патент 1992 года по МПК G06F15/347 

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

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

На фиг.1 представлена структурная схема устройства для вычисления собственных значений (п х п)-матрицы; на фиг.2 - структурная схема устройства для случая п 3; на фиг.З-функциональная схема вычислительного блока; на фиг.4 - функциональная схема вычислительного модуля; на фиг.5 - функциональная схема блока вывода.

Устройство для вычисления собственных значений (п х п)-матрицы (фип1) содержит первую группу информационных входов 1jO 1,2п-1), вторую группу информационных входов2i(i Iji), вход3задания точности вычислений, первую группу настроечных входов 4jQ 1,2п-1). вторую группу настроечных входов 5i(l 1 ,п), синхровход 6, вычислительные блоки 7, вычислительные модули 8, блок 9 вывода, первый 10i и второй 102 выходы признака окончания вычислений и информационные выходы 11.

Вычислительный блок 7 (фиг.З) содержит первый 12 и второй 13 информационные входы, настроечный вход 14, синхровход 15, первый 16 и второй 17 регистры, узел 18 вычисления обратной величины числа, первый 19 и второй 20 триггеры, первую-пятую группы 21-25 элементов И,

XI

W ON

группу элементов ИЛИ 26, первый-четвер- тый элементы И 27-30, первый 31 и второй 32 информационные выходы и настроечный выход 33.

Вычислительный модуль 8 (фиг.4) содержит первый 34, второй 35 и третий 36 информационные входы, настроечный вход 37, синхровход 38, первый 39, второй 40 и третий 41 регистры, умножитель 42, сумматор 43, первый-четвертый триггеры 44-47, пер- вую-восьмую группы 48-55 элементов И, первую 56, вторую 57 и третью 58 группы элементов ИЛИ, первый-четвертый элементы И 59-62, первый 63, второй 64 и третий 65 информационные выходы и настроечный выход 66.

Блок 9 вывода (фиг.5) содержит группу информационных входов 67i(i 1 ,п), информационный вход 68, группу настроечных входов 69i(i 1,п), синхровход 70, регистры первой 711 и второй 72) групп (I Tin), вычитатели 73i (i iTn), схемы 74i сравнения (I T7n), триггеры первой 75|, второй 76i и третьей 77i групп (i 1,n), элементы И первой 78i, второй 79i и третьей 80i групп (I 1,п), первый 81 и второй 82 элементы И, информационные выходы 83i (i 1,n), первый 84 и второй 85 выходы признака окончания вычислений.

В основу работы устройства положен итерационный треугольный степенной метод вычисления собственных значений матрицы А {aij}, 1 l,j n, где имеет место распределение Uil fa .,. |Anl .

Пусть Со {Ci,/0)}, 1 i,j n - нижняя треугольная матрица с единичными элементами по главной диагонали. В основе вычислительной схемы метода лежит последовательное вычисление матриц

Ck {Cij(k)}, 1 i n, Cn(k) 1, Ci/k) 0 при i j

и

Rk { Ti/k)}, 1 i,j n, Tij(k) 0 при i j

по правилу:

ACo Bi, Bi CiRi; ACi 82, 62 C2R2; ACk-1 Bk, Bk CkRk.

При этом имеет место сходимость ЯГ ), k , 1 i k, следовательно, при достаточно больших k можно положить AI «Г|Гл 1 i п.

Таким образом, на каждом итерационном шаге необходимо выполнить операции перемножения двух матриц В А-С и произвести Ш-разложение полученной

0

матрицы В на верхнюю R и нижнюю С треугольные матрицы.

: Перемножение матриц А и С и Ш-разложение матрицы В представляются следующими рекуррентными соотношениями:В А-С;

bijj aij, 1 I n;

bijq bijq-i+akiCq, , 1 , n;

bij bijn, ,j n;

15 B C-R;

bijt by, 1 i,j n; q 1,2n;

A... .

J-Sn;

л,

Clq blqq Т qq, q i П,

лл

bljq+1 bljq - ClqRqj, q I П, q j П.

На фиг.1 и 2 представлена организация подачи входных данных. Начальные данные С|/° (1 i n, 1 j i) подаются в вычислительный блок 7(n-j+i) в моменты времени tcij 2i + j - 5. Данные aij(1 :Ј 1,j n) подаются в вычислительный модуль 8(n,n+i-j) в моменты времени tag i + j - 4 + (2k-1)n, k 1,2,...К, где К - число необходимых итерационных шагов. Режим ввода управляющих сигналов г и q, подаваемых соответственно на входы 4 и 5, приведен в табл.1.

Логика работы вычислительного блока 7 и вычислительного модуля 8 приведена соответственно в табл.2 и 3. Вычислительный блок 7 и вычислительный модуль 8 работают в четырех режимах, Режим работы вычислительного блока 7 определяют состояния триггеров 19 и 20, а режим работы вычислительного модуля 8 - состояния триггеров 44 и 45, которые устанавливаются соответствующими управляющими сигналами, подаваемыми соответственно на входы 14 и 37. Все регистры в вычислительных блоках 7 и в вычислительных модулях 8 построены на двухтактных триггерах и срабатывают по заднему фронту тактового импульса. В вычислительном блоке 7с прямого выхода регистра 17 снимается значение b, a с инверсного выхода - значение (-Ь).

Рассмотрим работу устройства для случая n 3. Организация входного и выходного потоков данных приведена на фиг.2 (в обозначении г индекс k в скобках указывает номер итерации, а в обозначении г

0

5

0

5

0

5

0

5

индекс t без скобок - номер такта работы устройства, В табл.4-9 показаны состояния регистров и триггеров вычислительных блоков 7 и вычислительных модулей 8, а также формируемые значения на их выходах при вычислении собственных значений ArkU,2 и для двух итераций.

На четвертом и десятом тактах в вычислительном блоке 7з формируются соответственно собственные значения Аг Гц и Ai® m , которые подаются на вход 67i блока 9 вывода. Кроме того, на четвертом и десятом тактах на вход 691 блока 9 вывода подается единичный сигнал.

На седьмом и тринадцатом тактах в вычислительном блоке 7а формируются соответственно 2 Г22 И А 2 Г22 , которые подаются на вход 672 блока 9 вывода, а на вход 692 - единичный сигнал.

На десятом и шестнадцатом тактах в вычислительном блоке 7з формируются соответственно Аз гзз и Аз гзз , которые подаются на вход 67з блока 9 вывода, на вход 69з подается единичный сигнал.

Таким образом, собственные значений Ark nr1 (i 1,п) формируются в вычислительном блоке 7(n-i+i) в моменты времени t i 3i - 5 + 2nk.

В блоке 9 вывода выполняется проверка точности вычислений |Ark+1 -Ark l. Если такое соотношение выполняется, то на выходе 10 признака окончания вычислений формируется единичный сигнал. При этом с выходов 11() в моменты времени 3 - 4 + 2nk снимаются значения AI. Если данное соотношение не выполняется, то итерационный процесс вычисления собственных значений AI продолжается,

В процессе вычисления Ark существуют случаи параллельной проверки соотношений )Щ ЕИ

1А& + 2) - AJ2k + 1) I Ј, i 1 )2. Поэтому для итераций k 1,3,5,... признак окончания вычислений «1 формируется на выходе 10i, a для итераций k 2,4,6,.. - признак окончания вычислений аг на выходе 102 в моменты времени t i 3n - 4 + 2nk. В этом случае блок 9 вывода работает следующим образом. В исходном состоянии регистры и триггеры блока 9 вывода обнулены. На l-м такте на входы 67j и 69i подаются соответственно значение Аг1 и единичный сигнал д. Значение Ар1 по заднему фронту тактового импульса записывается в регистр 7.11 (элемент И 781 открыт управляющим сигналом g 1). Триггер 75i устанавливается в единичное состояние и открывает элемент 79i (триггер 75i работает в счетном режиме,

т.е. с подачей на его вход единицы он меняет свое состояние на противоположное). На выходе вычитателя 73i определяется ДА) |Аг° - , а на выходе схемы 74| сравнения - соотношение ДА) Е. Если это

соотношение выполняется, то на выходе схемы 74| сравнения формируется единичный сигнал, который подается на информационные входы триггеров 76i и 77|. На (1+1)-м такте через элемент И 79| тактовый импульс

подается на синхровход триггера 76i и устанавливает его в единичное состояние, если на выходе схемы 74) сравнения сформирован единичный сигнал. Такая проверка на первом итерационном шаге выполняется

для всех i 1,п и на выходе элемента И 81 формируется единичный сигнал а 1, когда все триггеры 76| установлены в единичное состояние.

На втором итерационном шаге (k 2) на вход 67j подается значение АгЧ а на вход 69 - единичный сигнал, который устанавливает триггер 75i в нулевое состояние. При этом открывается элемент И 80i,

который обеспечивает запись результата сравнения I A/ AT I е на выходе схемы 74i сравнения в триггер 77i (0 или 1). Аналогично, на выходе элемента И 82 формируется сигнал Oi 1, если все триггеры 77,

установлены в единичное состояние. Таким образом, в блоке 9 вывода состояние три ггеров 76i и 77j зависит от состояния триггера 75i, что позволяет определить правильные значения признаков окончания

вычислений «1 и az для четных и нечетных итераций.

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

Устройство для вычисления собственных значений (n x п)-матрицы, содержащее п2/2 вычислительных модулей, отличающееся тем, что, с целью расширения функциональных возможностей путем вычисления собственных значений произвольной матрицы, в него введены (2п2-п)/2 вычислительных модулей, n вычислительных блоков и блок вывода, причем j-й вход информационных входов первой группы устройства 0 1,2п-1) подключен к первому информационному входу (n,j)-ro вычислительного модуля, первый информацион- кый вход (i.k)-ro вычислительного модуля (i 1,n-1, k 1,n) подключен к первому

информационному выходу(1+1,к)-го вычислительного модуля, первый информационный вход (1,1)-го вычислительного модуля (I n+1,2n-2, H п 2)подключен к первому информационному выходу (i+1,l)-ro вычислительного модуля, k-й вход второй группы информационных входов устройства подключен к первому информационному входу k-ro вычислительного блока, первый информационный выход которого подключен к второму информационному входу (k.l)-ro вычислительного модуля, второй информационный выход (k,i)-ro вычислительного модуля подключен к второму информационному входу (k,i-M)-ro вычислительного модуля, второй информационный выход (p.q)-ro вычислительного модуля (р 2,n, q n,2n-2, q-p n-2) подключен к второму информационному входу (p,q+1)-ro вычислительного модуля, третий информационный вход (p,q)-ro вычислительного модуля подключен к третьему информационному выходу (p,q+1)-ro вычислительного модуля, третий информационный вход (k,i)-ro вычислительного модуля подключен к третьему информационному входу (k,i+1)-ro вычислительного модуля, третий информационный вход (k,l)-ro вычислительного модуля подключен к второму информацйионному входу k-ro вычислитель- ного блока, второй информационный выход которого подключен к k-му входу групп информационных входов блока вывода, вход задания точности вычислений которого является одноименным входом устройства, j-й вход группы настроечных входов которого подключен к настроечному входу (n,j)-ro вычислительного модуля настроечный вход (q.p)-ro вычислительного модуля (q 2,n) подключен к настроечному входу (q + 1, р + 1)-го вычислительного модуля, настроечный выход (q,s)-ro вычислительного модуля (s n+1,2n-1, s-0 n-1) подключен к настроечному входу (q + 1, s + + 1)-го вычислительного модуля, k-й вход второй группы настроечных входов устройства подключен к настроечному входу k-ro вычислительного блока, настроечный выход которого подключен к k-му входу группы настроечных входов блока вывода, синхровход устройства подключен к синх- ровходу блока вывода, синхровходам всех вычислительных модулей и блоков, первый и второй выходы признака окончания вычислений блока вывода являются одно- именными выходами устройства, k-й информационный выход которого подключен к k-му выходу группы информационных выходов блока вывода, причем каждый вычислительный блок выполнен с возможностью реализации следующих функций:

bj, если (0,$ (0,1)

1/bJ, если (о1, $ (0,0) -bj, если (о1, $ (1,0) aj, если(а,$ (1,1)

Bj+1 bs, если (a1,/) (0,1);

Gi+1

0если (a1, ft - (0,0), (0,1), (1,0),

1если (a1, $ (0,1)

где се tf ($ - значения соответственно на первом и втором настроечных входах вычислительного модуля блока на j-м такте;

а и bj - значения соответственно на первом и втором информационных входах вычислительного блока на j-м такте;

А и В - значения соответственно на первом и втором информационных выходах вычислительного блока на j-м такте;

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

а ;

J

bj, если («,$ (0,0)

ajcj, если (d.ft) (1.1); cj + ajbj, если (d,fi) (0,0) cj, если (о1, $(0,1) Ы, если («,$ (1,0); ajcj, если (о1, $ (1,1)

где alb и с - значения соответственно на втором, первом и третьем информационных входах вычислительного модуля на j-м такте; А .В и d - значения соответственно на втором, первом и третьем информационных выходах вычислительного модуля на j-м такте.

Таблица 1

Изобретение относится к вычислительной технике и может быть использовано в высокопроизводительных специализированных вычислительных машинах и устройствах обработки сигналов для вычисления всех собственных значений (n x п)-матрицы. Цель изобретения - расширение функциональных возможностей устройства за счет вычисления собственных значений произвольной матрицы. Поставленная цель достигается тем, что устройство содержит п вычислительных блоков, (Зп2-п)/2 вычислительных модулей и блок вывода. В основу устройства положен итерационный треугольный степенной метод вычисления собственных значений для произвольной (п х л)-матрицы. 5 ил.. 9 табл, Ј

(n-j+0

(n4 + 0

(0,1)7(

(0,0)7(n.j4.)

,i-0

,niM

)8(п,п+Ч1

° ° «Wi-П

2i + j - 5

2i + j - 5 + 2nk

3j - 5 + 2nk

2i + j - 2nk

i - 3 + 2nk

i -.3 + (2k - 1)n

i + 4 + (2k-1)n

i + j - 4 - (2k-1)n

Режим i Tp iTp j Pr : Pr I Pr

работы

44 45 I 40

40

00

01

10

11

0 1

I

2

3

4 0

5

6 0

7

8 0

9

1C 0

1C4IC«

C,

1b« 1/r«r

.1-1 ,W

0 1

C2(C2(

0 I

о о

«Sf « С с «) ая b ,; 0 0c(« a,s b« cj a(1 b( .00

0000cf а„ Ь& с .„ hfi

1/ { «S° °

« . . is 4,1

1 I

0 1

-a

с(Л

C2i

-

4S

0100

о о , c a(} b« .„ ь

0000

о о

«Й - Ь с ал Ь™

с .„ Ь с ч, Ь

26 iЈ n, 1 jc i 1 Ј i j n, 1 6 k Ј: К 1 J6 -,

1€ j L ifen, 1 $ k К

2Јifcn, 1 1$ ii n, 1 ЈkЈK

n + 26 j 2n, , 1 ign, 2 j6n, 16 k К

Таблица З

Т1 :Г iTp j Pr : Pr I Pr

Выходы

I 40

39 i 41

40 39

64 j63,65

с a b c+a-bi с ас

b с a a-c a-c

.-5-Wг 1

C2(C2(

о о

-a

с(Л

C2i

-

«Й - Ь с ал Ь™

о о

с .„ Ь с ч, Ь

О О

О О

0 1

1 1

«я «а

hi, VЈr«

11

О О

о о

1

О

О

1

О

О

1

О

Ьн

О с« ... Ь с , ,n bji

1 О

I О

«МL (01. (О

О 0 с а„ Ъ,„ С14| а,г Ь,и

О eg .w b(4 c« а„ Ь«

1 О

(

О с ,1 .„ Ь 0 .„ С.1 О

О О ,t b c а,г ЬЙ О с«« а„ «И .„ Ь

.в) ь,«

1 О

asi

О СИ а,2 Ь с .„ Ь«1

1 О

1 0 с2 а,г Ь аи Ъ«

Продолжение табл. 4

r.

Ь 1/г с с00

1 1

, ,

с„II

О О

ьоо

о о

с 71 сн сз

.,, Ь« с„ .«

1Л21 tf« «лГс« с

Ь,„ ся а« Ьиа

„BI . . „(Л „ .№

CW a«S b2ll с)1 а« Ь21

Таблица 5

I О

bvi

1 О

1 О

00

1 О

0 О

1 О

1 О

о о

1 О

о о

142(О

1 О

СМ а ка) см a bW

СЪг33 C-J2. a33 D-J2.

1О

«) 5 322

И

О)

аа

(2)

3222

1О

1И

к(2)

Ь322

г) ,.w

(г)

аэз ггг -&г &

1О

liZ.

(i)

Э222

ь«

«3

л

(0 ft) М( bj3« ri C3i ээг

NJ

О

гз

) ьгэ

г («)„)М4) ft) (4) «,«

rt с Я 931 Г« с «I

00

Таблица 9

Фиг. I.

-4

§