
㭮 9-13.  ᫥⥫  ᮢ 㤠.

	GAUSSIAN.ELIMINATION (SISD) ;

	Global  n               {ࠧ  ⥬}
		a[1..n][1..n]   {樥 ࠢ}
		b[1..n]         {ࠢ  ࠢ}
		marked[1..n]    {뢠,  ப  pivot}
		pivot[1..n]     {--"--"--"--"--"--"--"--  뫨 pivot}
		picked          {ப, ࠭  pivot}
	begin
	   for i <- 1 to n do
		marked[i] <- 0
	   endfor
	   for i <- 1 to n-1 do
	      tmp <- 0
	      for j <- 0 to n do
		 if marked[j] = 0  and  | a[j][i] | > tmp  then
		    tmp <- | a[j][i] |
		    picked <- j
		 endif
	      endfor
	      marked[picked] <- 1
	      pivot[picked] <- i
	      for j <- 1 to n do
		 if marked[j] = 0  then
		    tmp <- a[j][i] / a[picked][i]
		    for k <- i+1 to n do
		       a[j][k] <- a[j][k] - a[picked][k] * tmp
		    endfor
		    b[j] <- b[j] - b[k] * tmp
		 endif
	      endfor
	    endfor
	    for i <- 1 to n do
	      if marked[i] = 0  then
		  pivot[i] <- N
		  break
	      endif
	    endfor
	 end




       n - 1  権 ,  ⨢   i
    .  1  n -  1.   祭 樨  i  
    n-i  蠣 ࠢ ⮡ । pivot ப. 
    ⮫쪮 pivot ப  ,   㬥  n-i
    ப,      蠣  㬥襭 ப ॡ
    2*(n - i) 樨  饩 窮 ⮡   -
    樥 A,    権  饩 ⮩ ⮡ -
     ப   b. ⥫쭮 饥 ᫮  権
     饩 ⮩  ࠢ -









    襥 ⢮  権 ந室  ᠬ
    ७ FOR 横.  ᨬ⥩   -
     뢠 ,    ७  FOR  横  -
      k  । FOR 横, ஢  j 
    믮 ࠫ쭮.  㣨  ᫮,  ᫨  ⮫쪮
    pivot ப 뫠 , 䨪樨  ન஢
    ப  ந室 ६.    
    ப,  ⮫쪮 ⥫  a[j][i] / a[picked][i] -
    , 䨪樨 ⮢  (i+1)..n    ப
     ந室 ६.   襥 -
    ⢮ 権 ⠭  ᫥ ࠢ ந-
       FOR 横,  뢠  -
    室騬  ᯠࠫ.
		  ᬮਬ  ॠ  ᮢ
    㤠  ⨪.  ਬ,    n - ⥫ p.
       ।    a  b  
     㠫 ஢?  ᫨  ᫥㥬 ⮪
     ⬠   樨  i (. 9-14 ),  , 
    । pivot ࠭ ப ॡ, ⮡  
      ⮫ i ࠢ,   । 
    祭 ᯥ᪮  a[j][k] ॡ饣  -
    祭 ஬ ⥪饣 祭 a[j][k].  祭 - a[j][i],
    a[picked][i],   a[picked][k].
		।    筮
    । ⬥⪨  ⬥,  ॡ . ।-
    ,   砥        뢭
    㯯 ப a  ᮮ⢥.  ⮢ b ( . 9-15 ).
    稢  । ,   -
    ⢮ ⮡ । pivot ப. ᫨  ⮫쪮  pivot
    ப ।,  騩 pivot ப  
    ।      㣨  ,  ⮬   
     ஢ 祭 㬥஢ ப, 묨
     ࠢ. ᥢ  ⮣ ⬠  
    . 9-16  9-17.


     9-14
    ᨬ   祭
    筮 樨  ᮢ
    ⬠ 㤠.  祭
     i ⮫ i  
      ન஢
    ப  ᫥,
    ⮡ । ⮦⢮
    pivot ࠭ ப. ᫨
    ⮫쪮 pivot ப 뫠
    ஢,  -
     a[j][k]   -
    ஢  ப  j  
     ,  ॡ -
      a[j][i],  a[picked][i],
      a[picked][k].


     9-15. 筮-ਥ㥬   
     ।祭  ⨪ ᮢ -
     㤠.  ⮬ ਬ n = 16  p = 4.



















     9-16.     ࠫ  ᮢ  
    㤠  ⨪ ⨯ , ਭ饣
    ਥ㥬 ப   樥⮢.

	ROW.ORIENTED.GAUSSIAN.ELIMINATION (HIPERCUBE MULTICOMPUTER):

	Local   n               {ࠧ  ⥬}
		a[1..n/p][1..n] {樥 ࠢ}
		b[1..n/p]       {ࠢ  ࠢ}
		marked[1..n/p]  {.  ப  pivot ப}
		pivot[1..n/p]   {--"--"--"--"--"--"-- 뫨 --"--"--"--"--}
		picked          {ப, ࠭  pivot ப}
		magnitude       {祭 pivot}
		winner          {, 㦨騩 pivot ப}
		i,j             {६ 横}
	begin
	   for all  Pid , where  i <= id <= p  do
	     {᭠砫  ப,   ᯮ짮  pivot}
	     for i <- 1 to n/p  do
	       marked[i] <- 0
	     endfor
	     for i <- 1 to n-1 do
	       {  室 ᢮   pivot}
	       magnitude <- 0
	       for j <- i to n/p  do
		 if marked[j] = 0 and | a[j][i] | > magnetude  then
		    magnetude <- | a[j][i] |
		    picked <- j
		 endif
	       endfor
	       winner <- id
	       {롮 襩  ।⠢ ப  pivot}
	       MAX.TOURNAMENT(id,magnetude,winner)
	       if id = winner then
		  marked[picked] <- 1 pivot[picked] <- i
		  for j <- i+1  to  n  do
		     tmp.vector[j] <- a[picked][j]
		     tmp.vector[n+1] <- b[picked]
		  endfor
	       endif

	       {  pivot ப ।  㣨 ࠬ}
	       NYPERCUBE.BROADCAST(id,winner,tmp.vector[(t+1)..(n+1)])

	       {  㤠 ⮫ i 祭  ᢮ }
	       { ન஢ ப }
	       for i <- 1 to n/p  do
		  if marked[j] = 0  then
		    tmp <- a[j][i] / tmp.vector[i]
		    for k <- i+1 to n do
		      a[j][k] <- a[j][k] - tmp.vector[k] * tmp
		    endfor
		    b[j] <- b[j] - tmp.vector[n+1] * tmp
		  endif
	       endfor
	     endfor

	     { ப  ᯮ짮襩  pivot ப}
	     for i <- 1 to n/p do
		if marked[i] = 0  then
		   pivot[i] <- n
		   break
		endif
	     endfor
	   endfor
	end





      뢠  ⢨    ⮡  ।
    pivot ப tournament, ⮬      ᮢ  
    । pivot ப (winner) 襩, 祬 稭 -
    祭 ࠭  ⮫ i  pivot ப  (    ).
    ᫨   ᮢ    ⮦⢥      ᠬ
    訬 祭,  뢠 ⢨         max
    - tournament. ᫨  ᮢ  । -
      ᠬ 쪨 祭,  뢠  ⢨
    min - tournament.   믮 tournament -
      ⮩ ਠ ⬠ 㬥襭. 㭮 9-18
        - tournament   㡠 .


     9-18 . ᥢ max-tournament 楤, 
       ⮦⢮   ᠬ 訬 祭.

    MAX.TOURNAMENT (id, value, winner)
    {  楤  뢠  ७ FOR ALL  }

	Reference       id
			value
			winner
	begin
	   for i <- 0  to  (log p) -1  do
	      partner <- id XOR 2^i
	      [partner]tmp.value <= value
	      [partner]tmp.winner <= winner
	      if tmp.value > value then
		 value <- tmp.value
		 winner <- tmp.winner
	      endif
	   endfor
	end



      蠣 ⬠, ᬠਢ   ६ .
    ६ Value ᮤন ᠬ 讥  祭 ,
       ⠫      ,    ६
    Winner ᮤন   , ᬠਢ饣  
    祭 .  ᥢ ࠦ  ⨬  -
    ﬨ   蠣 । ᮮ饭, ॠ쭠  ॠ
    㤥 ᮬ ꥤ  祭   -
        ।  ࠧ.
		筮  ।
      ਢ  ࠧ筮 ⨪-
    ୮ . ਬ, ᫨  砥    -
      ।㥬 㯯  ⮫殢 a      b,
    ⮣    ⢮ ⮡  ।-
     pivot ப. ,  祭 樨  i  
    ࠢ騩 ⮫殬  i  ᫥.    ᮮ⢥騥
    ન஢ ப     ᠬ 让 -
    稭.  tournament  室.   ⮣-
     ।  ⮫  i     (?) pivot  ப
     㣨 .
		ਬ,  ⥯ ⠫樨  ࠫ쭮
    ᫥  -  ⢮  ࠡ  믮塞   
     " 蠣 " .  ⨪    ஬  ६
     ᮮ饭 - ⭮⥫쭮  ᮪,  ᨬ騥
    ।⢠ ⥯ ⠫樨   ᫮  뫠-
     ᮮ饭.  ⭮, ᫨ ᮮ饭  쪨,  
      ꥤ  ᮮ饭   ⮣
     ᠬ - ⮡ 㬥  ந-
    ⥫  । ᮮ饭.
		ਬ ,   筮-ਥ㥬
    ᨨ  ࠫ쭮  ᮢ  㤠,   ,
    ࠢ騩 pivot ப     (i+1)..n
    ⮩ ப 㯭묨   ஢ , 믮
     FOR  横.  ।  祭  - , 
     । 楫    n-1  ப ⮢.
		筮, ⮫殢-ਥ㥬
    ࠫ   ᮢ 㤠   ⠪
    믮  祭 樨  i  , ᫨  ࠢ-
    騩 ⮫殬  i  ꥤ  ⮫  i   -
    ,  ᮤঠ騥 䨪 pivot ப  筮
    ᮮ饭.
	     ࠢ 筮-ਥ㥬  ⮫殢-
    ਥ㥬 ॠ権 ᮢ 㤠,    
    ⠬   ᮮ⭮襭 "-᫥" .


     9-19. ᪮७ , ⨣⮥ 筮-ਥ㥬
    ࠫ쭮 ॠ樥 ᮢ 㤠  nCUBE 3200  
    64- ࠬ    ⥬ ࠧ ࠧ஢.















    B 筮-ਥ㥬 ⬥,  ࠡ
     ⮡ । pivot ப.  ⥬ ࠧ n
     ᮤঠ饩 p ஢,  ஢,  㦤-
      祬 n/p 祭. ,   ⮫쪮  -
     ।  ᨬ,   뢠  
    㣨 ࠬ ⮡ ।   ᨬ.
     樨 i ਥ㥬 ⮫殬 ⬠    -
      믮 n-i ࠢ,    
    ॡ.  ⬠ ॡ 蠣 । ᫥ ⮣,
     pivot ப  뫠  .    砥  ਥ㥬
    ப ⬠ । 筠 ப .    砥
    ਥ㥬  ⮫殬  ⬠ । 
    ⮫ .
	        䨪஢ p,  n -> oo,  ६
    ॡ㥬 ਥ㥬 ப ⬮  ⮡  室
    pivot  ப        祬    ਥ㥬
    ⮫殬  ⬠ .   ⮩  稭,    ࠫ  
    ॠ樨  ਥ㥬  ப  .  㭮
    9-19  ⠡㥬 ᪮७ ᪠  த-
    樨 ⨣⮥ ਥ㥬 ப ࠫ쭮 ॠ-
    樥 ᮢ 㤠  64 - ୮  nCUBE  3200,
      ⥬ ࠧ ࠧ஢.


    9.5 JACOBI  .

     ᬠਢ 樮 ⮤  襭 ⥬
      ࠢ.  樮        -
     ⮡  訥, ࠧ०   -
    ⥬ ᣥ஢    ࠡ    묨  ७-
    樠묨 ࠢﬨ,  ᯮ騬    ⮤.
    樮 ⮤   २⢠  묨  -
    ⮤. -,  ⮤  ଠ쭮 뤠 襭 
    筮 ᫮ 蠣, ..    ⠪ 楤
    ᫥ 筮 ᫠ 権,   ந 筮
    訩 பᨬ騩 ⢥. -, 
    樮  奬   ਢ⥫쭮 ᮡ :
     ॡ 䬥᪨  権  ⮫쪮    ⫨
      樥  .
		襥 ⢮ 樮 ⬮ ,
    ᠭ   ᮡ: ᫨  室,  
    室  ࠢ쭮 襭. ,     -
         室. 㦤 ᫮
    ,    室  襭,  ᬠ-
    .
	    ᬠਢ 樮  - Jacobi
    .  ⠭⭮ । ,   ⨬
      ⥬   A x = b   । -
    ⭮    x.  , 

	      x_i = 1/a_ii * [ b_i - SUM_j<>i a_ij * x_j ]    (9.23)

	   ᫨    祭 x_j,  j<>i,  
    筮 ᫨  x_i . 筮,     -
    祭 ,   ஡㥬 । ,  ᫨   
    業   ⠪ 祭 x_j,   
    業  x_i . Jacobi     業 
       x ⮡   業 
    x .  ᯮ 祭, ᫥   ६-
     x_i  祭 樨 t ⮡  ஢  
    祭  祭 樨  t + 1 :

       x_i(t+1) = 1/a_ii * [ b_i - SUM_j<>i a_ij * x_j(t) ]    (9.24)


     9-20.  ᥢ ᫥⥫쭮 Jacobi ⬠.

	JACOBI.ALGORITHM.1(SISD);

	Input   n               {ࠧ୮  ⥬}
		e               {਩ 室}
		a[1..n][1..n]   {樥  ࠢ}
		b[1..n]         {⠭, ᮮ⢥. ࠢ}
	Output  x[1..n]         { 業  襭}
	Global  newx[1..n]      { 業  襭}
		diff            {ᨬ쭮   }
		i,j             {६ 横}
	begin
	   {業 祭 ⮢ x}
	   for i <- 1  to n  do
	      x[i] <- b[i]/a[i][i]
	   endfor

	   {⪠ 業 x  祭 室 (?)}
	   do
	     diff <- 0
	     for i <- 1 to n do
		newx[i] <- b[i]
		for j <- 1 to n do
		   if j<>i then
		      newx[i] <- newx[i] - a[i][j] * x[j]
		   endif
		endfor
		newx[i] <- newx[i] / a[i][i]
	     endfor
	     for i <- 1 to n do
		diff <- max( diff, | x[i] - newx[i] | )
		x[i] <- newx[i]
	     endfor
	   while diff > e
	end



	   Jacobi    ᯠࠫ, ⮬ 
    ᫥   x  室 ६.
     業  x    ன 業  x   祭
    A  b.
	   ᬮਬ ,  믮 ࠫ Jacobi -
      ⨪.   砥 ᮢ 㤠,
      ।,   ⬥  ॡ
    . ।,    ⢥⢥  -
    뢭  ப  A   ᮮ⢥  ⮢  b.
     ⮩ 樥 ,  ⢨  
    ந室          祭      樨
    DO...WHILE 横 . 砫,  
       ᥣ  x , ᫥  祭
    ।饩 樨 .  ⥫쭮 ,   
     ।  x   㣨 .
		  -,     -
     쭮 祭 diff  ᭮      
    祭 ᮡ⢥ ⮢ x,     祭
     oꥤ , ⮡ 뤠 쭮 祭
    diff . ⥫쭮,     ᨬ  㬥襭
    室.   蠣 ᨬ쭮  㬥襭,  
     㤥  ⠪ 祭  diff , ஥
     㤥 ⠢   室   DO..WHILE
    横  ⮩   ᠬ  樨.


     9-21. ࠫ쭮
    -⬠, 饣
     ⥬ ࠧ
    128*128  ⨪
  {뢠,  ப  pivot}
		pivot[1..n]     {--"--"--"--"--"--"--"--  뫨 pivot}
		picked          {ப, 