# Способы хранения и представления разреженных матриц, операции над ними: Методические указания к спецкурсу

• Published on
08-Dec-2016

• View
219

• Download
4

Embed Size (px)

Transcript

• ,

3

:

.. . .

..

2002

• - 2 -

1. .. 3 2. . ... 3 3. ... . 9 4. . 24 . 33

• - 3 -

1. ,

, . 1.1. ( ) ,

. 1.2. ,

, , . . :

1) ;

2) ( ); 3) .

() fAU = ( A ), .. . A , :

1) ; 2) .

2.

, , , .

2.1. ( ) .

mn { }ijaA = . : 1) AN A ; 2) JA - A; 3) IA , i - , c AN JA i - A . , AN JA .

• - 4 -

, i - A )(iAI ]1)1([ +iAI AN JA

I )()1( iAIiAI =+ , , i - . , . A m , AI )1( +m .

, .. A . , JA ( ), . : , , , . . . 1. A .

N : 7654321

=

0000000063000000005040002011

A .

N : 87654321

6354211:AN 6531421:JA 88641:AI

. AI 1 .

2. IAJAAN ,, A ( ). 9854321:AN 5432176:JA 86531:AI

• - 5 -

JAAN , : N : 7654321

9854321:AN 5432176:JA

, A 4 7 , 1- 6 1, 7- 2 ..

N : 7654321

3. 1 ,

.

2.2. ( ) , , .

. , JAT , ATI , A .

4. A 1

. a) N : 87654321 ANT : 6325141 JAT : 3312121 ATI : 8765431

5. A 1

, 5. 6. A .

=

001070000000000000000050003100

A .

=

0098000000050000000432100000

A

• - 6 -

2.3. { }n

jiijaA

1, == )( jiij aa =

( ) . : 1) ( )

( ); 2) A AD ,

( ) A ( ) ( ).

7.

=

3011030010101002

A

a) ; ) .

a) :NA 331112 ) :AN 11 :JA 434241 :JA 44 :AI 76531 :IA 33321 :AD 3312

2.4. ( ) 2.1. { }n

jiijaA

1, ==

)12( +m , 0=ija ji, , mji > || . )12( +m , m .

nm

• - 7 -

, , . :

, , . 8. A 1) m ; 2) AD ; 3) .

a)

=

70000000690000

121151000000104090000038000068200000001

A ; )

=

5020003000200010002000101

A .

) 1) 2=m ; ) 1) 2=m ; 2) )57( AD ; 2) )35( AD ;

3)

=

7000690

12115100010409003806820001

AD ; 3)

=

502300001201

AD .

9. - A AD .

• - 8 -

2.5. ( ) ,

, . .

)(min ijii = , i , )(min ij i - A , . . i - i .

2.2. { }njiij

aA1, =

=

i : =

==n

iiAprofileApr

1)()( .

2.3. A { }iij jia i i -

]1)1([ +iDA )(iDA . 11a )1(AN .

10.

=

20200018010

1700130

10

A

1) , AN ; 2) .

N : 87654321 2021801171310:AN 86321:DA

• - 9 -

11. AN DA A : 123456789:AN 976531:DA 3. . , .. . , ( ). . 1. , , , , . . IA , JA ; , . 2. . , . 3.1. 3.1.1. , , 3.1. (), . , . , , . : 1) N ; 2) A ; 3) NEXT , IP . 12. dcba ,,, , A : 7654321:N cadbA : : 427:NEXT ; 5=IP . 13. fedcba ,,,,, , : 654321:N

.853dim,3)(,1,2,0,0,0)1 54321

=+==

=====

ANApr

• - 10 -

fedcbaA : 12356:NEXT 4=IP : afbecd ,,,,, .

3.2. , . A , { }n,...,2,1 . 3.3. n . m . nm

• - 11 -

B , ),...,1( niAi = ( ).

16. B ,, , .2,7:;5,11,3:;5,3,7,2: B

, B , , , B . , .11,5,3,7,2:

, , . Y p . 1=p .

( 11). Y . , i , i - ( 1). ( j ) j M , , . . . .

: N : 1110987654321 :Y 00000000000 00001010110 A 10001010110 B 10001010110 C

3.1.3. ( ) .

( ), ( , ).

, . ( ) p .

1=p . p ( . . 1+= pp ), .

• - 12 -

17. B ,, 1 ED, 2 , p .

N : 13121110987654321 :Y 11121121122 0000000000000 22

3.2. ( ) 3.2.1. ( ) B, ,

BC += .

1. : JBJ, J .

2. 01 . X ,

J . X JC . 02 . J AN

X AN . - BN X .

03 . X , CN , ))(()(: iJCXiCNJ = .

18. B, .

1. JBJ, J : 547310 . 2. X :

N : 10987654321 X : 00000

2.04.07.03.0 AN 5.06.07.0 BN

7.04.06.003.0 6.004.03.07.0:CN

4,8,7:;11,5,4:

13,12,11:

CBA

=

=

).2(2,1,9,8,7,6:4,8,7:);1(8,7,5,4,13,12,11:9,8,7,6:

2

1

pEpMD

.1045:

5.07.06.0:

JBBN

;47310:7.04.03.02.0:

JAAN

• - 13 -

. , CN , . C :

57310:6.04.03.07.0:

JCCN

.

3.2.2. ( ) B, ,

BC += . CN .

1. : JBJ, J . 2.

01 . ( ) IX , J . J , )( jIX , CN j - , . . )( j . IX - .

02 . CN . ANJ, CN , IX CN , . BNJB, CN : )()))((()))((( iANiJAIXCNiJAIXCN += ; )()))((()))((( iBNiJBIXCNiJBIXCN += .

19. B, .

;43710:14.08.06.04.0:

JAAN

.1359:4.03.02.01.0:

JBBN

1. N : 7654321 N - J :JC 15943710 N N 2. 1) N : 10987654321 N JC (CN ) :IX 0000000000

1526437 2) N : 7654321

CN : 14.08.06.04.0 AN 4.02.01.03.0 BN

______________

4.02.01.014.01.16.04.0 N , 4.02.01.014.01.16.04.0: CN

• - 14 -

15943710:JC

3.3. )(, mnB

. BC += . Y

X . A B : mXY == dimdim .

A B .

1. ( ICJC, )

01 . 1=i ( ). 02 . JAIA, JBIB, ,

i - A B Y . , , 1- JC .

03 . 1+= ii 02 . , ni . JC .

04 . IC JC .

2. ( B, )

01 . 1=i . 02 . ICJC, ,

i - JA JB . 03 . X i - A

B , . CN JC .

04 . 1+= ii 02 . , ni . CN . . X . 20. B, . BC += .

;9731:

4261543153:1112733412:

IAJAAN

• - 15 -

1512951:432215631:

211642511:

IAJBBN

.

1. 34226154316153:JC 1512951:IC

N : 654321 :Y

324432 11422131000000

2. N : 654321 X : 0000 1

12 AN 511 BN 5111

000000 2 7334 AN 2 BN

5334 000000 3

12 AN 64 BN

162

000000 4 11 AN 211 BN

310

13061253345111: AN 3.4. B, n . P B . IX , , .3.2.2, ,

• - 16 -

, J . , . IX J . k JB , ki ,...,1= ))(( iJBIX . , JB ; ,

)))((()( iJBIXANIBNPP += JB . , : 1) 0=P ; 2) ki ,...,1= 0))(( =IJBIX JA 1+= ii )))((()( iJBIXANIBNPP JA+= 1+= ii

21.

N : 87654321 :JAIX 32000154 0=P , 8,...,1=i :1=i 0))1(( =JBIX JA 2=i : 01))2(( =JBIX JA 717)1()2(0 ==+= ANBNP :3=i 05))3(( =JBIX JA 47587)5()3(7 =+=+= ANBNP :4=i 4))4(( =JBIX JA 834947 =+=P

. . . . . . . . . . . . . . . . . . . . . . . .

3.5. ( ) B , ABC = . , , B .3.4 .

;21873:54321:

JAAN

.861234:

11109876:

JBBN

• - 17 -

1. IX ( ) B.

2. 1=i . 3. IA , JA

i - . 4. JA , i - .

)(kJA ( k - ) , ; , AN B )(iC .

5. , 1+= ii 3. , . . 1=k 0)( =k )()1( kIAkIA =+

1)1(),( += kAIkAIi 1+= kk 0))(( =IJAIX 1+= ii )))((()()()( iJAIXBNIANkCkC JA+= 1+= ii 1+= kk 22. ( ).

N : 121110987654321

N : 10987654321 :JBIX 7065043021

10875421:10875421:

JBBN

131211941:3110987523641:6210864297531:

IAJAAN

• - 18 -

1=k ; 0)1( = ; )1()2( AIAI = :3,...,1=i :1=i 01)1())1(( == IXJAIX

...