From stew Wed Feb 16 16:10:39 1994 Received: from taal.Stanford.EDU by oas.Stanford.EDU with SMTP id AA14541 (5.65c/IDA-1.4.4 for gopal); Wed, 16 Feb 1994 16:10:32 -0800 Return-Path: Received: by taal.Stanford.EDU id AA10559 (5.65c/IDA-1.4.4 for gopal@oas.stanford.edu); Wed, 16 Feb 1994 16:07:00 -0800 Date: Wed, 16 Feb 1994 16:07:00 -0800 From: Stewart Levin Message-Id: <199402170007.AA10559@taal.Stanford.EDU> To: jstern@minnie.nic.kingston.ibm.com, zhan@sccm.stanford.edu, rinaldo.digiorgio@east.sun.com, pyu@sccm.stanford.edu, sccmlab1@sep.stanford.edu, sccmlab2@sep.stanford.edu Subject: Yet another copy of Lab 4 instructions Content-Type: X-sun-attachment Status: R ---------- X-Sun-Data-Type: text X-Sun-Data-Description: text X-Sun-Data-Name: text X-Sun-Content-Lines: 10 Sorry for the goof, but I had a typo in the tridiagonal sample code that was, to say the least, confusing. I also had interchanged the role of input and output arrays, too. I am including a PostScript version of the lab 4 instructions with all known corrections. - Stew PS. We are still working on extending the Cray allocation to allow completion of the last Cray lab. ---------- X-Sun-Data-Type: postscript-file X-Sun-Data-Description: postscript-file X-Sun-Data-Name: Lab4 X-Sun-Content-Lines: 2491 %!PS-Adobe-3.0 %%Title: (Lab 4) %%Creator: (Microsoft Word: LaserWriter 8.0 8.0) %%CreationDate: (3:54 PM Wednesday, February 16, 1994) %%For: (christin) %%Pages: 3 %%DocumentFonts: Courier-Bold Courier Courier-Oblique MT-Extra %%DocumentNeededFonts: Courier-Bold Courier Courier-Oblique MT-Extra %%DocumentSuppliedFonts: %%DocumentData: Clean7Bit %%PageOrder: Ascend %%Orientation: Portrait %ADO_PaperArea: -31 -30 761 582 %ADO_ImageableArea: 0 0 730 552 %%EndComments /md 166 dict def md begin /currentpacking where {pop /sc_oldpacking currentpacking def true setpacking}if %%BeginFile: adobe_psp_basic %%Copyright: Copyright 1990-1993 Adobe Systems Incorporated. All Rights Reserved. /bd{bind def}bind def /xdf{exch def}bd /xs{exch store}bd /ld{load def}bd /Z{0 def}bd /T/true /F/false /:L/lineto /lw/setlinewidth /:M/moveto /rl/rlineto /rm/rmoveto /:C/curveto /:T/translate /:K/closepath /:mf/makefont /gS/gsave /gR/grestore /np/newpath 14{ld}repeat /$m matrix def /av 80 def /por true def /normland false def /psb-nosave{}bd /pse-nosave{}bd /us Z /psb{/us save store}bd /pse{us restore}bd /level2 /languagelevel where { pop languagelevel 2 ge }{ false }ifelse def /featurecleanup { stopped cleartomark countdictstack exch sub dup 0 gt { {end}repeat }{ pop }ifelse }bd /noload Z /startnoload { {/noload save store}if }bd /endnoload { {noload restore}if }bd level2 startnoload /setjob { statusdict/jobname 3 -1 roll put }bd /setcopies { userdict/#copies 3 -1 roll put }bd level2 endnoload level2 not startnoload /setjob { 1 dict begin/JobName xdf currentdict end setuserparams }bd /setcopies { 1 dict begin/NumCopies xdf currentdict end setpagedevice }bd level2 not endnoload /pm Z /mT Z /sD Z /realshowpage Z /initializepage { /pm save store mT concat }bd /endp { pm restore showpage }def /$c/DeviceRGB def /rectclip where { pop/rC/rectclip ld }{ /rC { np 4 2 roll :M 1 index 0 rl 0 exch rl neg 0 rl :K clip np }bd }ifelse /rectfill where { pop/rF/rectfill ld }{ /rF { gS np 4 2 roll :M 1 index 0 rl 0 exch rl neg 0 rl fill gR }bd }ifelse /rectstroke where { pop/rS/rectstroke ld }{ /rS { gS np 4 2 roll :M 1 index 0 rl 0 exch rl neg 0 rl :K stroke gR }bd }ifelse %%EndFile %%BeginFile: adobe_psp_colorspace_level1 %%Copyright: Copyright 1991-1993 Adobe Systems Incorporated. All Rights Reserved. /G/setgray ld /:F/setrgbcolor ld %%EndFile %%BeginFile: adobe_psp_customps %%Copyright: Copyright 1990-1993 Adobe Systems Incorporated. All Rights Reserved. /$t Z /$p Z /$s Z /$o 1. def /2state? false def /ps Z level2 startnoload /pushcolor/currentrgbcolor ld /popcolor/setrgbcolor ld /setcmykcolor where { pop/currentcmykcolor where { pop/pushcolor/currentcmykcolor ld /popcolor/setcmykcolor ld }if }if level2 endnoload level2 not startnoload /pushcolor { currentcolorspace $c eq { currentcolor currentcolorspace true }{ currentcmykcolor false }ifelse }bd /popcolor { { setcolorspace setcolor }{ setcmykcolor }ifelse }bd level2 not endnoload /pushstatic { ps 2state? $o $t $p $s }bd /popstatic { /$s xs /$p xs /$t xs /$o xs /2state? xs /ps xs }bd /pushgstate { save errordict/nocurrentpoint{pop 0 0}put currentpoint 3 -1 roll restore pushcolor currentlinewidth currentlinecap currentlinejoin currentdash exch aload length np clippath pathbbox $m currentmatrix aload pop }bd /popgstate { $m astore setmatrix 2 index sub exch 3 index sub exch rC array astore exch setdash setlinejoin setlinecap lw popcolor np :M }bd /bu { pushgstate gR pushgstate 2state? { gR pushgstate }if pushstatic pm restore mT concat }bd /bn { /pm save store popstatic popgstate gS popgstate 2state? { gS popgstate }if }bd /cpat{pop 64 div G 8{pop}repeat}bd %%EndFile %%BeginFile: adobe_psp_basic_text %%Copyright: Copyright 1990-1993 Adobe Systems Incorporated. All Rights Reserved. /S/show ld /A{ 0.0 exch ashow }bd /R{ 0.0 exch 32 exch widthshow }bd /W{ 0.0 3 1 roll widthshow }bd /J{ 0.0 32 4 2 roll 0.0 exch awidthshow }bd /V{ 0.0 4 1 roll 0.0 exch awidthshow }bd /fcflg true def /fc{ fcflg{ vmstatus exch sub 50000 lt{ (%%[ Warning: Running out of memory ]%%\r)print flush/fcflg false store }if pop }if }bd /$f[1 0 0 -1 0 0]def /:ff{$f :mf}bd /MacEncoding StandardEncoding 256 array copy def MacEncoding 39/quotesingle put MacEncoding 96/grave put /Adieresis/Aring/Ccedilla/Eacute/Ntilde/Odieresis/Udieresis/aacute /agrave/acircumflex/adieresis/atilde/aring/ccedilla/eacute/egrave /ecircumflex/edieresis/iacute/igrave/icircumflex/idieresis/ntilde/oacute /ograve/ocircumflex/odieresis/otilde/uacute/ugrave/ucircumflex/udieresis /dagger/degree/cent/sterling/section/bullet/paragraph/germandbls /registered/copyright/trademark/acute/dieresis/notequal/AE/Oslash /infinity/plusminus/lessequal/greaterequal/yen/mu/partialdiff/summation /product/pi/integral/ordfeminine/ordmasculine/Omega/ae/oslash /questiondown/exclamdown/logicalnot/radical/florin/approxequal/Delta/guillemotleft /guillemotright/ellipsis/space/Agrave/Atilde/Otilde/OE/oe /endash/emdash/quotedblleft/quotedblright/quoteleft/quoteright/divide/lozenge /ydieresis/Ydieresis/fraction/currency/guilsinglleft/guilsinglright/fi/fl /daggerdbl/periodcentered/quotesinglbase/quotedblbase/perthousand /Acircumflex/Ecircumflex/Aacute/Edieresis/Egrave/Iacute/Icircumflex/Idieresis/Igrave /Oacute/Ocircumflex/apple/Ograve/Uacute/Ucircumflex/Ugrave/dotlessi/circumflex/tilde /macron/breve/dotaccent/ring/cedilla/hungarumlaut/ogonek/caron MacEncoding 128 128 getinterval astore pop level2 startnoload /copyfontdict { findfont dup length dict begin { 1 index/FID ne{def}{pop pop}ifelse }forall }bd level2 endnoload level2 not startnoload /copyfontdict { findfont dup length dict copy begin }bd level2 not endnoload md/fontname known not{ /fontname/customfont def }if /Encoding Z /:mre { copyfontdict /Encoding MacEncoding def fontname currentdict end definefont :ff def }bd /:bsr { copyfontdict /Encoding Encoding 256 array copy def Encoding dup }bd /pd{put dup}bd /:esr { pop pop fontname currentdict end definefont :ff def }bd /scf { scalefont def }bd /scf-non { $m scale :mf setfont }bd /ps Z /fz{/ps xs}bd /sf/setfont ld /cF/currentfont ld /mbf { /makeblendedfont where { pop makeblendedfont /ABlend exch definefont }{ pop }ifelse def }def %%EndFile %%BeginFile: adobe_psp_derived_styles %%Copyright: Copyright 1990-1993 Adobe Systems Incorporated. All Rights Reserved. /wi version(23.0)eq { { gS 0 0 0 0 rC stringwidth gR }bind }{ /stringwidth load }ifelse def /$o 1. def /gl{$o G}bd /ms{:M S}bd /condensedmtx[.82 0 0 1 0 0]def /:mc { condensedmtx :mf def }bd /extendedmtx[1.18 0 0 1 0 0]def /:me { extendedmtx :mf def }bd /basefont Z /basefonto Z /dxa Z /dxb Z /dxc Z /dxd Z /dsdx2 Z /bfproc Z /:fbase { dup/FontType get 0 eq{ dup length dict begin dup{1 index/FID ne 2 index/UniqueID ne and{def}{pop pop}ifelse}forall /FDepVector exch/FDepVector get[exch/:fbase load forall]def }/bfproc load ifelse /customfont currentdict end definefont }bd /:mo { /bfproc{ dup dup length 2 add dict begin { 1 index/FID ne 2 index/UniqueID ne and{def}{pop pop}ifelse }forall /PaintType 2 def /StrokeWidth .012 0 FontMatrix idtransform pop def /customfont currentdict end definefont 8 dict begin /basefonto xdf /basefont xdf /FontType 3 def /FontMatrix[1 0 0 1 0 0]def /FontBBox[0 0 1 1]def /Encoding StandardEncoding def /BuildChar { exch begin basefont setfont ( )dup 0 4 -1 roll put dup wi setcharwidth 0 0 :M gS gl dup show gR basefonto setfont show end }def }store :fbase }bd /:mso { /bfproc{ 7 dict begin /basefont xdf /FontType 3 def /FontMatrix[1 0 0 1 0 0]def /FontBBox[0 0 1 1]def /Encoding StandardEncoding def /BuildChar { exch begin sD begin /dxa 1 ps div def basefont setfont ( )dup 0 4 -1 roll put dup wi 1 index 0 ne { exch dxa add exch }if setcharwidth dup 0 0 ms dup dxa 0 ms dup dxa dxa ms dup 0 dxa ms gl dxa 2. div dup ms end end }def }store :fbase }bd /:ms { /bfproc{ dup dup length 2 add dict begin { 1 index/FID ne 2 index/UniqueID ne and{def}{pop pop}ifelse }forall /PaintType 2 def /StrokeWidth .012 0 FontMatrix idtransform pop def /customfont currentdict end definefont 8 dict begin /basefonto xdf /basefont xdf /FontType 3 def /FontMatrix[1 0 0 1 0 0]def /FontBBox[0 0 1 1]def /Encoding StandardEncoding def /BuildChar { exch begin sD begin /dxb .05 def basefont setfont ( )dup 0 4 -1 roll put dup wi exch dup 0 ne { dxb add }if exch setcharwidth dup dxb .01 add 0 ms 0 dxb :T gS gl dup 0 0 ms gR basefonto setfont 0 0 ms end end }def }store :fbase }bd /:mss { /bfproc{ 7 dict begin /basefont xdf /FontType 3 def /FontMatrix[1 0 0 1 0 0]def /FontBBox[0 0 1 1]def /Encoding StandardEncoding def /BuildChar { exch begin sD begin /dxc 1 ps div def /dsdx2 .05 dxc 2 div add def basefont setfont ( )dup 0 4 -1 roll put dup wi exch dup 0 ne { dsdx2 add }if exch setcharwidth dup dsdx2 .01 add 0 ms 0 .05 dxc 2 div sub :T dup 0 0 ms dup dxc 0 ms dup dxc dxc ms dup 0 dxc ms gl dxc 2 div dup ms end end }def }store :fbase }bd /:msb { /bfproc{ 7 dict begin /basefont xdf /FontType 3 def /FontMatrix[1 0 0 1 0 0]def /FontBBox[0 0 1 1]def /Encoding StandardEncoding def /BuildChar { exch begin sD begin /dxd .03 def basefont setfont ( )dup 0 4 -1 roll put dup wi 1 index 0 ne { exch dxd add exch }if setcharwidth dup 0 0 ms dup dxd 0 ms dup dxd dxd ms 0 dxd ms end end }def }store :fbase }bd /italicmtx[1 0 -.212557 1 0 0]def /:mi { italicmtx :mf def }bd /:v { [exch dup/FontMatrix get exch dup/FontInfo known { /FontInfo get dup/UnderlinePosition known { dup/UnderlinePosition get 2 index 0 3 1 roll transform exch pop }{ .1 }ifelse 3 1 roll dup/UnderlineThickness known { /UnderlineThickness get exch 0 3 1 roll transform exch pop abs }{ pop pop .067 }ifelse }{ pop pop .1 .067 }ifelse ] }bd /$t Z /$p Z /$s Z /:p { aload pop 2 index mul/$t xs 1 index mul/$p xs .012 mul/$s xs }bd /:m {gS 0 $p rm $t lw 0 rl stroke gR }bd /:n { gS 0 $p rm $t lw 0 rl gS gl stroke gR strokepath $s lw /setstrokeadjust where{pop currentstrokeadjust true setstrokeadjust stroke setstrokeadjust }{ stroke }ifelse gR }bd /:o {gS 0 $p rm $t 2 div dup rm $t lw dup 0 rl stroke gR :n }bd %%EndFile /currentpacking where {pop sc_oldpacking setpacking}if end % md %%EndProlog %%BeginSetup md begin countdictstack [ {%stopped %%BeginFeature: *ManualFeed False level2 {1 dict dup /ManualFeed false put setpagedevice}{statusdict begin /manualfeed false store end} ifelse %%EndFeature }featurecleanup countdictstack [ {%stopped %%BeginFeature: *InputSlot Upper %%EndFeature }featurecleanup countdictstack [ {%stopped %%BeginFeature: *PageRegion LetterSmall level2 { 2 dict dup /PageSize [612 792] put dup /ImagingBBox null put setpagedevice }{ /lettersmall where {pop lettersmall} {letterR} ifelse } ifelse %%EndFeature }featurecleanup (christin)setjob /pT[1 0 0 -1 30 761]def/mT[1 0 0 -1 30 761]def /sD 16 dict def 300 level2{1 dict dup/WaitTimeout 4 -1 roll put setuserparams}{statusdict/waittimeout 3 -1 roll put}ifelse %%IncludeFont: Courier-Bold %%IncludeFont: Courier %%IncludeFont: Courier-Oblique %%IncludeFont: MT-Extra /f0_1/Courier-Bold :mre /f0_12 f0_1 12 scf /f1_1/Courier :mre /f1_12 f1_1 12 scf /f3_1/Courier-Oblique :mre /f3_12 f3_1 12 scf /f4_1/MT-Extra findfont :ff def /f4_12 f4_1 12 scf /Courier findfont[10 0 0 -10 0 0]:mf setfont %%EndSetup %%Page: 1 1 %%BeginPageSetup initializepage (christin; page: 1 of 3)setjob %%EndPageSetup gS 0 0 552 730 rC 51 51 :M f0_12 sf 2.733 .273(SCCM 240 Lab #4)J 51 75 :M 4.475 .447(1. Tridiagonal equations)J 51 99 :M f1_12 sf -.202(One of the performance challenges of vector and parallel)A 51 111 :M -.202(computing is efficient solution of tridiagonal equations.)A 51 123 :M -.202(Algebraically, tridiagonal systems are defined by)A 173 138 178 52 rC 351 190 :M -30 -31 :T psb currentpoint pse 30 31 :T 173 138 :M -30 -31 :T psb 30 dict begin currentpoint 3 -1 roll sub neg 3 1 roll sub 5696 div 1664 3 -1 roll exch div scale currentpoint translate 64 43 translate 10 261 moveto /fs 0 def /sf {exch dup /fs exch def dup neg matrix scale makefont setfont} def /f1 {findfont dup /cf exch def sf} def /ns {cf sf} def 384 /Times-Italic f1 (y) show 176 357 moveto 224 /Times-Roman f1 (0) show 422 261 moveto 384 /Symbol f1 (=) show 731 261 moveto 384 /Times-Italic f1 (b) show 906 357 moveto 224 /Times-Roman f1 (0) show 1055 261 moveto 384 /Times-Italic f1 (x) show 1232 357 moveto 224 /Times-Roman f1 (0) show 1463 261 moveto 384 /Symbol f1 (+) show 1753 261 moveto 384 /Times-Italic f1 (c) show 1919 357 moveto 224 /Times-Roman f1 (0) show 2068 261 moveto 384 /Times-Italic f1 (x) show 2226 357 moveto 224 /Times-Roman f1 (1) show 10 853 moveto 384 /Times-Italic f1 (y) show 205 949 moveto 224 ns (j) show 409 853 moveto 384 /Symbol f1 (=) show 722 853 moveto 384 /Times-Italic f1 (a) show 938 949 moveto 224 ns (j) show 1045 853 moveto 384 ns (x) show 1251 949 moveto 224 ns (j) show 1345 949 moveto 224 /Symbol f1 (-) show 1472 949 moveto 224 /Times-Roman f1 (1) show 1685 853 moveto 384 /Symbol f1 (+) show 1978 853 moveto 384 /Times-Italic f1 (b) show 2182 949 moveto 224 ns (j) show 2289 853 moveto 384 ns (x) show 2495 949 moveto 224 ns (j) show 2684 853 moveto 384 /Symbol f1 (+) show 2974 853 moveto 384 /Times-Italic f1 (c) show 3169 949 moveto 224 ns (j) show 3276 853 moveto 384 ns (x) show 3482 949 moveto 224 ns (j) show 3576 949 moveto 224 /Symbol f1 (+) show 3704 949 moveto 224 /Times-Roman f1 (1) show 3912 853 moveto 384 /Times-Roman f1 (,) show 4199 853 moveto 320 /Times-Italic f1 (j) show 4399 853 moveto 320 /Symbol f1 (=) show 4647 853 moveto 320 /Times-Roman f1 (1) show 4785 853 moveto 320 /Times-Roman f1 (,) show 4924 853 moveto 320 /Times-Italic f1 (N) show 5240 853 moveto 320 /Symbol f1 (-) show 5472 853 moveto 320 /Times-Roman f1 (1) show 10 1488 moveto 384 /Times-Italic f1 (y) show 189 1584 moveto 224 ns (N) show 485 1488 moveto 384 /Symbol f1 (=) show 798 1488 moveto 384 /Times-Italic f1 (a) show 998 1584 moveto 224 ns (N) show 1197 1488 moveto 384 ns (x) show 1387 1584 moveto 224 ns (N) show 1573 1584 moveto 224 /Symbol f1 (-) show 1700 1584 moveto 224 /Times-Roman f1 (1) show 1913 1488 moveto 384 /Symbol f1 (+) show 2206 1488 moveto 384 /Times-Italic f1 (b) show 2394 1584 moveto 224 ns (N) show 2593 1488 moveto 384 ns (x) show 2783 1584 moveto 224 ns (N) show end pse gR gS 0 0 552 730 rC 51 213 :M f1_12 sf -.22(where the )A 121 203 50 14 rC 171 217 :M -30 -31 :T psb currentpoint pse 30 31 :T 121 203 :M -30 -31 :T psb 30 dict begin currentpoint 3 -1 roll sub neg 3 1 roll sub 1600 div 448 3 -1 roll exch div scale currentpoint translate 64 59 translate -5 261 moveto /fs 0 def /sf {exch dup /fs exch def dup neg matrix scale makefont setfont} def /f1 {findfont dup /cf exch def sf} def /ns {cf sf} def 384 /Times-Italic f1 (a) show 185 261 moveto 384 /Times-Roman f1 (,) show 397 261 moveto 384 /Times-Italic f1 (b) show 677 261 moveto 384 /Times-Roman f1 (and) show 1327 261 moveto 384 /Times-Italic f1 (c) show end pse gR gS 0 0 552 730 rC 171 213 :M f1_12 sf -.206('s are known coefficients, )A 360 206 9 11 rC 369 217 :M -30 -31 :T psb currentpoint pse 30 31 :T 360 206 :M -30 -31 :T psb 30 dict begin currentpoint 3 -1 roll sub neg 3 1 roll sub 288 div 352 3 -1 roll exch div scale currentpoint translate 64 -37 translate 10 261 moveto /fs 0 def /sf {exch dup /fs exch def dup neg matrix scale makefont setfont} def /f1 {findfont dup /cf exch def sf} def /ns {cf sf} def 384 /Times-Italic f1 (y) show end pse gR gS 0 0 552 730 rC 369 213 :M f1_12 sf -.215( is the input)A 51 227 :M -.202(data vector and we are to solve for the unknowns )A 394 220 9 9 rC 403 229 :M -30 -31 :T psb currentpoint pse 30 31 :T 394 220 :M -30 -31 :T psb 30 dict begin currentpoint 3 -1 roll sub neg 3 1 roll sub 288 div 288 3 -1 roll exch div scale currentpoint translate 64 -37 translate 11 261 moveto /fs 0 def /sf {exch dup /fs exch def dup neg matrix scale makefont setfont} def /f1 {findfont dup /cf exch def sf} def /ns {cf sf} def 384 /Times-Italic f1 (x) show end pse gR gS 0 0 552 730 rC 403 227 :M f1_12 sf -.248(. In)A 51 240 :M -.204(terms of matrices, we want to solve )A 303 230 36 14 rC 339 244 :M -30 -31 :T psb currentpoint pse 30 31 :T 303 230 :M -30 -31 :T psb 30 dict begin currentpoint 3 -1 roll sub neg 3 1 roll sub 1152 div 448 3 -1 roll exch div scale currentpoint translate 64 59 translate 10 261 moveto /fs 0 def /sf {exch dup /fs exch def dup neg matrix scale makefont setfont} def /f1 {findfont dup /cf exch def sf} def /ns {cf sf} def 384 /Times-Italic f1 (y) show 279 261 moveto 384 /Symbol f1 (=) show 589 261 moveto 384 /Times-Bold f1 (A) show 866 261 moveto 384 /Times-Italic f1 (x) show end pse gR gS 0 0 552 730 rC 339 240 :M f1_12 sf -.211( where the matrix)A 51 245 12 11 rC 63 256 :M -30 -31 :T psb currentpoint pse 30 31 :T 51 245 :M -30 -31 :T psb 30 dict begin currentpoint 3 -1 roll sub neg 3 1 roll sub 384 div 352 3 -1 roll exch div scale currentpoint translate 64 59 translate -8 261 moveto /fs 0 def /sf {exch dup /fs exch def dup neg matrix scale makefont setfont} def /f1 {findfont dup /cf exch def sf} def /ns {cf sf} def 384 /Times-Bold f1 (A) show end pse gR gS 0 0 552 730 rC 63 255 :M f1_12 sf -.204( has the simple tridiagonal form:)A 203 270 118 143 rC 203 413 :M f4_12 sf .269 .027( )J 321 413 :M -30 -31 :T psb currentpoint pse 30 31 :T 203 270 :M -30 -31 :T psb 30 dict begin currentpoint 3 -1 roll sub neg 3 1 roll sub 3776 div 4576 3 -1 roll exch div scale currentpoint translate 64 59 translate 175 294 moveto /fs 0 def /sf {exch dup /fs exch def dup neg matrix scale makefont setfont} def /f1 {findfont dup /cf exch def sf} def /ns {cf sf} def 384 /Times-Italic f1 (b) show 350 390 moveto 224 /Times-Roman f1 (0) show 588 294 moveto 384 /Times-Italic f1 (c) show 754 390 moveto 224 /Times-Roman f1 (0) show 179 1144 moveto 384 /Times-Italic f1 (a) show 347 1240 moveto 224 /Times-Roman f1 (1) show 682 1144 moveto 384 /Times-Italic f1 (b) show 838 1240 moveto 224 /Times-Roman f1 (1) show 1170 1144 moveto 384 /Times-Italic f1 (c) show 1317 1240 moveto 224 /Times-Roman f1 (1) show 2651 1144 moveto 768 ns (0) show 627 1733 moveto 384 /Times-Italic f1 (a) show 813 1829 moveto 224 /Times-Roman f1 (2) show 1166 1733 moveto 384 /Times-Italic f1 (b) show 1340 1829 moveto 224 /Times-Roman f1 (2) show 1690 1733 moveto 384 /Times-Italic f1 (c) show 1855 1829 moveto 224 /Times-Roman f1 (2) show 926 2353 moveto 384 /MT-Extra f1 (O) show 1448 2353 moveto (O) show 1970 2353 moveto (O) show 1411 2929 moveto 384 /Times-Italic f1 (a) show 1611 3025 moveto 224 ns (N) show 1797 3025 moveto 224 /Symbol f1 (-) show 1924 3025 moveto 224 /Times-Roman f1 (1) show 2147 2929 moveto 384 /Times-Italic f1 (b) show 2335 3025 moveto 224 ns (N) show 2521 3025 moveto 224 /Symbol f1 (-) show 2648 3025 moveto 224 /Times-Roman f1 (1) show 2868 2929 moveto 384 /Times-Italic f1 (c) show 3047 3025 moveto 224 ns (N) show 3233 3025 moveto 224 /Symbol f1 (-) show 3360 3025 moveto 224 /Times-Roman f1 (1) show 390 3778 moveto 768 ns (0) show 2158 3778 moveto 384 /Times-Italic f1 (a) show 2358 3874 moveto 224 ns (N) show 2873 3778 moveto 384 ns (b) show 3061 3874 moveto 224 ns (N) show -15 355 moveto 384 /Symbol f1 (\346) show -15 3796 moveto (\350) show -15 806 moveto (\347) show -15 1177 moveto (\347) show -15 1548 moveto (\347) show -15 1919 moveto (\347) show -15 2290 moveto (\347) show -15 2661 moveto (\347) show -15 3032 moveto (\347) show -15 3403 moveto (\347) show -15 3577 moveto (\347) show 3492 355 moveto (\366) show 3492 3796 moveto (\370) show 3492 806 moveto (\367) show 3492 1177 moveto (\367) show 3492 1548 moveto (\367) show 3492 1919 moveto (\367) show 3492 2290 moveto (\367) show 3492 2661 moveto (\367) show 3492 3032 moveto (\367) show 3492 3403 moveto (\367) show 3492 3577 moveto (\367) show end pse gR gS 0 0 552 730 rC 51 423 :M f1_12 sf -.202(The most arithmetically efficient way to solve tridiagonal)A 51 435 :M -.202(equations is to use a marching algorithm. We start with the)A 51 447 :M -.202(first row and, as in high school algebra, use it to clear)A 51 450 11 14 rC 62 464 :M -30 -31 :T psb currentpoint pse 30 31 :T 51 450 :M -30 -31 :T psb 30 dict begin currentpoint 3 -1 roll sub neg 3 1 roll sub 352 div 448 3 -1 roll exch div scale currentpoint translate 64 59 translate -5 261 moveto /fs 0 def /sf {exch dup /fs exch def dup neg matrix scale makefont setfont} def /f1 {findfont dup /cf exch def sf} def /ns {cf sf} def 384 /Times-Italic f1 (a) show 163 357 moveto 224 /Times-Roman f1 (1) show end pse gR gS 0 0 552 730 rC 62 460 :M f1_12 sf -.218(. The new )A 139 450 11 14 rC 150 464 :M -30 -31 :T psb currentpoint pse 30 31 :T 139 450 :M -30 -31 :T psb 30 dict begin currentpoint 3 -1 roll sub neg 3 1 roll sub 352 div 448 3 -1 roll exch div scale currentpoint translate 64 59 translate -9 261 moveto /fs 0 def /sf {exch dup /fs exch def dup neg matrix scale makefont setfont} def /f1 {findfont dup /cf exch def sf} def /ns {cf sf} def 384 /Times-Italic f1 (b) show 147 357 moveto 224 /Times-Roman f1 (1) show end pse gR gS 0 0 552 730 rC 150 460 :M f1_12 sf -.21( is used to clear )A 276 450 12 14 rC 288 464 :M -30 -31 :T psb currentpoint pse 30 31 :T 276 450 :M -30 -31 :T psb 30 dict begin currentpoint 3 -1 roll sub neg 3 1 roll sub 384 div 448 3 -1 roll exch div scale currentpoint translate 64 59 translate -5 261 moveto /fs 0 def /sf {exch dup /fs exch def dup neg matrix scale makefont setfont} def /f1 {findfont dup /cf exch def sf} def /ns {cf sf} def 384 /Times-Italic f1 (a) show 181 357 moveto 224 /Times-Roman f1 (2) show end pse gR gS 0 0 552 730 rC 288 460 :M f1_12 sf -.206( and so on. When we reach)A 51 474 :M -.204(the bottom of the matrix, all of the )A 310 467 9 9 rC 319 476 :M -30 -31 :T psb currentpoint pse 30 31 :T 310 467 :M -30 -31 :T psb 30 dict begin currentpoint 3 -1 roll sub neg 3 1 roll sub 288 div 288 3 -1 roll exch div scale currentpoint translate 64 -37 translate -5 261 moveto /fs 0 def /sf {exch dup /fs exch def dup neg matrix scale makefont setfont} def /f1 {findfont dup /cf exch def sf} def /ns {cf sf} def 384 /Times-Italic f1 (a) show end pse gR gS 0 0 552 730 rC 319 474 :M f1_12 sf -.208( entries are now zero)A 51 486 :M -.202(and we are left with a bidiagonal system of the form:)A 208 501 109 154 rC 208 655 :M f4_12 sf .269 .027( )J 317 655 :M -30 -31 :T psb currentpoint pse 30 31 :T 208 501 :M -30 -31 :T psb 30 dict begin currentpoint 3 -1 roll sub neg 3 1 roll sub 3488 div 4928 3 -1 roll exch div scale currentpoint translate 64 48 translate 232 301 moveto /fs 0 def /sf {exch dup /fs exch def dup neg matrix scale makefont setfont} def /f1 {findfont dup /cf exch def sf} def /ns {cf sf} def 384 /Times-Roman f1 (\304) show 175 408 moveto 384 /Times-Italic f1 (b) show 350 504 moveto 224 /Times-Roman f1 (0) show 624 391 moveto 384 /Times-Roman f1 (\304) show 588 408 moveto 384 /Times-Italic f1 (c) show 754 504 moveto 224 /Times-Roman f1 (0) show 680 1151 moveto 384 /Times-Roman f1 (\304) show 623 1258 moveto 384 /Times-Italic f1 (b) show 779 1354 moveto 224 /Times-Roman f1 (1) show 1147 1241 moveto 384 /Times-Roman f1 (\304) show 1111 1258 moveto 384 /Times-Italic f1 (c) show 1258 1354 moveto 224 /Times-Roman f1 (1) show 2592 1258 moveto 768 ns (0) show 1128 1854 moveto 384 /Times-Roman f1 (\304) show 1071 1961 moveto 384 /Times-Italic f1 (b) show 1245 2057 moveto 224 /Times-Roman f1 (2) show 1631 1944 moveto 384 /Times-Roman f1 (\304) show 1595 1961 moveto 384 /Times-Italic f1 (c) show 1760 2057 moveto 224 /Times-Roman f1 (2) show 1262 2581 moveto 384 /MT-Extra f1 (O) show 1784 2581 moveto (O) show 1912 3164 moveto 384 /Times-Roman f1 (\304) show 1855 3271 moveto 384 /Times-Italic f1 (b) show 2043 3367 moveto 224 ns (N) show 2229 3367 moveto 224 /Symbol f1 (-) show 2356 3367 moveto 224 /Times-Roman f1 (1) show 2612 3254 moveto 384 /Times-Roman f1 (\304) show 2576 3271 moveto 384 /Times-Italic f1 (c) show 2755 3367 moveto 224 ns (N) show 2941 3367 moveto 224 /Symbol f1 (-) show 3068 3367 moveto 224 /Times-Roman f1 (1) show 390 4120 moveto 768 ns (0) show 2659 4013 moveto 384 /Times-Roman f1 (\304) show 2602 4120 moveto 384 /Times-Italic f1 (b) show 2790 4216 moveto 224 ns (N) show -15 355 moveto 384 /Symbol f1 (\346) show -15 4138 moveto (\350) show -15 806 moveto (\347) show -15 1177 moveto (\347) show -15 1548 moveto (\347) show -15 1919 moveto (\347) show -15 2290 moveto (\347) show -15 2661 moveto (\347) show -15 3032 moveto (\347) show -15 3403 moveto (\347) show -15 3774 moveto (\347) show 3200 355 moveto (\366) show 3200 4138 moveto (\370) show 3200 806 moveto (\367) show 3200 1177 moveto (\367) show 3200 1548 moveto (\367) show 3200 1919 moveto (\367) show 3200 2290 moveto (\367) show 3200 2661 moveto (\367) show 3200 3032 moveto (\367) show 3200 3403 moveto (\367) show 3200 3774 moveto (\367) show end pse endp %%Page: 2 2 %%BeginPageSetup initializepage (christin; page: 2 of 3)setjob %%EndPageSetup -30 -31 :T gS 30 31 552 730 rC 81 86 :M f1_12 sf -.203(We now march back from bottom to top using )A 382 73 14 18 rC 396 91 :M psb currentpoint pse 382 73 :M psb 30 dict begin currentpoint 3 -1 roll sub neg 3 1 roll sub 448 div 576 3 -1 roll exch div scale currentpoint translate 64 41 translate 48 268 moveto /fs 0 def /sf {exch dup /fs exch def dup neg matrix scale makefont setfont} def /f1 {findfont dup /cf exch def sf} def /ns {cf sf} def 384 /Times-Roman f1 (\304) show -9 375 moveto 384 /Times-Italic f1 (b) show 179 471 moveto 224 ns (N) show end pse gR gS 30 31 552 730 rC 396 86 :M f1_12 sf -.22( to clear )A 466 76 21 15 rC 487 91 :M psb currentpoint pse 466 76 :M psb 30 dict begin currentpoint 3 -1 roll sub neg 3 1 roll sub 672 div 480 3 -1 roll exch div scale currentpoint translate 64 35 translate 24 268 moveto /fs 0 def /sf {exch dup /fs exch def dup neg matrix scale makefont setfont} def /f1 {findfont dup /cf exch def sf} def /ns {cf sf} def 384 /Times-Roman f1 (\304) show -12 285 moveto 384 /Times-Italic f1 (c) show 167 381 moveto 224 ns (N) show 353 381 moveto 224 /Symbol f1 (-) show 480 381 moveto 224 /Times-Roman f1 (1) show end pse gR gS 30 31 552 730 rC 487 86 :M f1_12 sf (,)S 81 105 :M -.206(and so forth until finally )A 270 92 11 17 rC 281 109 :M psb currentpoint pse 270 92 :M psb 30 dict begin currentpoint 3 -1 roll sub neg 3 1 roll sub 352 div 544 3 -1 roll exch div scale currentpoint translate 64 41 translate 48 268 moveto /fs 0 def /sf {exch dup /fs exch def dup neg matrix scale makefont setfont} def /f1 {findfont dup /cf exch def sf} def /ns {cf sf} def 384 /Times-Roman f1 (\304) show -9 375 moveto 384 /Times-Italic f1 (b) show 147 471 moveto 224 /Times-Roman f1 (1) show end pse gR gS 30 31 552 730 rC 281 105 :M f1_12 sf -.231( clear )A 330 95 12 15 rC 342 110 :M psb currentpoint pse 330 95 :M psb 30 dict begin currentpoint 3 -1 roll sub neg 3 1 roll sub 384 div 480 3 -1 roll exch div scale currentpoint translate 64 35 translate 24 268 moveto /fs 0 def /sf {exch dup /fs exch def dup neg matrix scale makefont setfont} def /f1 {findfont dup /cf exch def sf} def /ns {cf sf} def 384 /Times-Roman f1 (\304) show -12 285 moveto 384 /Times-Italic f1 (c) show 154 381 moveto 224 /Times-Roman f1 (0) show end pse gR gS 30 31 552 730 rC 342 105 :M f1_12 sf -.21(, leaving a purely)A 81 120 :M -.202(diagonal matrix. The last step is then to simply divide)A 81 136 :M -.218(through by )A 158 123 12 19 rC 170 142 :M psb currentpoint pse 158 123 :M psb 30 dict begin currentpoint 3 -1 roll sub neg 3 1 roll sub 384 div 608 3 -1 roll exch div scale currentpoint translate 64 41 translate 48 268 moveto /fs 0 def /sf {exch dup /fs exch def dup neg matrix scale makefont setfont} def /f1 {findfont dup /cf exch def sf} def /ns {cf sf} def 384 /Times-Roman f1 (\304) show -9 375 moveto 384 /Times-Italic f1 (b) show 195 471 moveto 224 ns (j) show end pse gR gS 30 31 552 730 rC 170 136 :M f1_12 sf -.203( to get the solution. In Fortran, this might)A 81 152 :M -.215(be written as)A 81 176 :M -.203( SUBROUTINE tridiag\(N,a,b,c,y,x,bb\))A 81 188 :M -.211( INTEGER N)A 81 200 :M -.202( REAL a\(0:N\),b\(0:N\),c\(0:N\),y\(0:N\),x\(0:N\),bb\(0:N\))A 81 212 :M -.211( INTEGER j)A 81 236 :M -.211( x\(0\)=y\(0\))A 81 248 :M -.211( bb\(0\)=b\(0\))A 81 272 :M -.209( DO j=0,N-1,1)A 81 284 :M -.203( bb\(j+1\)=b\(j+1\)-c\(j\)*a\(j+1\)/bb\(j\))A 81 296 :M -.203( x\(j+1\)=y\(j+1\)-x\(j\)*a\(j+1\)/bb\(j\))A 81 308 :M -.216( ENDDO)A 81 332 :M -.21( DO j=N,1,-1)A 81 344 :M -.203( x\(j-1\)=x\(j-1\)-c\(j-1\)*x\(j\)/bb\(j\))A 81 356 :M -.216( ENDDO)A 81 380 :M -.211( DO j=0,N,1)A 81 392 :M -.207( x\(j\)=x\(j\)/bb\(j\))A 81 404 :M -.216( ENDDO)A 81 428 :M -.215( RETURN)A 81 440 :M -.22( END)A 81 464 :M -.202(where the elements a\(0\) and c\(N\) are dummy placeholders.)A 81 488 :M -.202(a\) Using the Cray, time this subroutine for a system of size)A 81 501 :M -.223(511 with )A 144 491 62 14 rC 206 505 :M psb currentpoint pse 144 491 :M psb 30 dict begin currentpoint 3 -1 roll sub neg 3 1 roll sub 1984 div 448 3 -1 roll exch div scale currentpoint translate 64 59 translate -5 261 moveto /fs 0 def /sf {exch dup /fs exch def dup neg matrix scale makefont setfont} def /f1 {findfont dup /cf exch def sf} def /ns {cf sf} def 384 /Times-Italic f1 (a) show 285 261 moveto 384 /Symbol f1 (=) show 591 261 moveto 384 /Times-Italic f1 (c) show 860 261 moveto 384 /Symbol f1 (=) show 1188 261 moveto 384 /Times-Italic f1 (y) show 1457 261 moveto 384 /Symbol f1 (=) show 1733 261 moveto 384 /Times-Roman f1 (1) show end pse gR gS 30 31 552 730 rC 206 501 :M f1_12 sf -.248( and )A 241 491 27 12 rC 268 503 :M psb currentpoint pse 241 491 :M psb 30 dict begin currentpoint 3 -1 roll sub neg 3 1 roll sub 864 div 384 3 -1 roll exch div scale currentpoint translate 64 59 translate -9 261 moveto /fs 0 def /sf {exch dup /fs exch def dup neg matrix scale makefont setfont} def /f1 {findfont dup /cf exch def sf} def /ns {cf sf} def 384 /Times-Italic f1 (b) show 281 261 moveto 384 /Symbol f1 (=) show 583 261 moveto 384 /Times-Roman f1 (3) show end pse gR gS 30 31 552 730 rC 268 501 :M f1_12 sf (.)S 81 527 :M -.202(b\) Modify the subroutine to avoid so many division)A 81 539 :M -.202(operations. \(Hint: store the reciprocal of bb.\))A 81 563 :M -.202(c\) Notice that the compiler did not vectorize the first two)A 81 575 :M -.202(loops because they are recursive, that is each new value)A 81 587 :M -.202(depends on the one just computed. There is an alternative)A 81 599 :M -.198(algorithm, called )A f3_12 sf -.198(cyclic reduction)A f1_12 sf -.207(, that allows us to avoid)A 81 611 :M -.202(this dependency. Consider 3 consecutive equations:)A 197 626 190 55 rC 387 681 :M psb currentpoint pse 197 626 :M psb 30 dict begin currentpoint 3 -1 roll sub neg 3 1 roll sub 6080 div 1760 3 -1 roll exch div scale currentpoint translate 64 32 translate 11 261 moveto /fs 0 def /sf {exch dup /fs exch def dup neg matrix scale makefont setfont} def /f1 {findfont dup /cf exch def sf} def /ns {cf sf} def 384 /Times-Italic f1 (y) show 176 357 moveto 224 /Times-Roman f1 (2) show 338 357 moveto 224 /Times-Italic f1 (j) show 432 357 moveto 224 /Symbol f1 (-) show 559 357 moveto 224 /Times-Roman f1 (1) show 787 261 moveto 384 /Symbol f1 (=) show 1100 261 moveto 384 /Times-Italic f1 (a) show 1286 357 moveto 224 /Times-Roman f1 (2) show 1448 357 moveto 224 /Times-Italic f1 (j) show 1542 357 moveto 224 /Symbol f1 (-) show 1669 357 moveto 224 /Times-Roman f1 (1) show 1800 261 moveto 384 /Times-Italic f1 (x) show 1976 357 moveto 224 /Times-Roman f1 (2) show 2138 357 moveto 224 /Times-Italic f1 (j) show 2232 357 moveto 224 /Symbol f1 (-) show 2377 357 moveto 224 /Times-Roman f1 (2) show 2608 261 moveto 384 /Symbol f1 (+) show 2901 261 moveto 384 /Times-Italic f1 (b) show 3075 357 moveto 224 /Times-Roman f1 (2) show 3237 357 moveto 224 /Times-Italic f1 (j) show 3331 357 moveto 224 /Symbol f1 (-) show 3458 357 moveto 224 /Times-Roman f1 (1) show 3589 261 moveto 384 /Times-Italic f1 (x) show 3765 357 moveto 224 /Times-Roman f1 (2) show 3927 357 moveto 224 /Times-Italic f1 (j) show 4021 357 moveto 224 /Symbol f1 (-) show 4148 357 moveto 224 /Times-Roman f1 (1) show 4361 261 moveto 384 /Symbol f1 (+) show 4651 261 moveto 384 /Times-Italic f1 (c) show 4816 357 moveto 224 /Times-Roman f1 (2) show 4978 357 moveto 224 /Times-Italic f1 (j) show 5072 357 moveto 224 /Symbol f1 (-) show 5199 357 moveto 224 /Times-Roman f1 (1) show 5330 261 moveto 384 /Times-Italic f1 (x) show 5506 357 moveto 224 /Times-Roman f1 (2) show 5668 357 moveto 224 /Times-Italic f1 (j) show 256 896 moveto 384 ns (y) show 421 992 moveto 224 /Times-Roman f1 (2) show 583 992 moveto 224 /Times-Italic f1 (j) show 787 896 moveto 384 /Symbol f1 (=) show 1100 896 moveto 384 /Times-Italic f1 (a) show 1286 992 moveto 224 /Times-Roman f1 (2) show 1448 992 moveto 224 /Times-Italic f1 (j) show 1555 896 moveto 384 ns (x) show 1731 992 moveto 224 /Times-Roman f1 (2) show 1893 992 moveto 224 /Times-Italic f1 (j) show 1987 992 moveto 224 /Symbol f1 (-) show 2114 992 moveto 224 /Times-Roman f1 (1) show 2567 896 moveto 384 /Symbol f1 (+) show 2860 896 moveto 384 /Times-Italic f1 (b) show 3034 992 moveto 224 /Times-Roman f1 (2) show 3196 992 moveto 224 /Times-Italic f1 (j) show 3303 896 moveto 384 ns (x) show 3479 992 moveto 224 /Times-Roman f1 (2) show 3641 992 moveto 224 /Times-Italic f1 (j) show 4294 896 moveto 384 /Symbol f1 (+) show 4584 896 moveto 384 /Times-Italic f1 (c) show 4749 992 moveto 224 /Times-Roman f1 (2) show 4911 992 moveto 224 /Times-Italic f1 (j) show 5018 896 moveto 384 ns (x) show 5194 992 moveto 224 /Times-Roman f1 (2) show 5356 992 moveto 224 /Times-Italic f1 (j) show 5450 992 moveto 224 /Symbol f1 (+) show 5578 992 moveto 224 /Times-Roman f1 (1) show 10 1531 moveto 384 /Times-Italic f1 (y) show 175 1627 moveto 224 /Times-Roman f1 (2) show 337 1627 moveto 224 /Times-Italic f1 (j) show 431 1627 moveto 224 /Symbol f1 (+) show 559 1627 moveto 224 /Times-Roman f1 (1) show 787 1531 moveto 384 /Symbol f1 (=) show 1100 1531 moveto 384 /Times-Italic f1 (a) show 1286 1627 moveto 224 /Times-Roman f1 (2) show 1448 1627 moveto 224 /Times-Italic f1 (j) show 1542 1627 moveto 224 /Symbol f1 (+) show 1670 1627 moveto 224 /Times-Roman f1 (1) show 1801 1531 moveto 384 /Times-Italic f1 (x) show 1977 1627 moveto 224 /Times-Roman f1 (2) show 2139 1627 moveto 224 /Times-Italic f1 (j) show 2568 1531 moveto 384 /Symbol f1 (+) show 2861 1531 moveto 384 /Times-Italic f1 (b) show 3035 1627 moveto 224 /Times-Roman f1 (2) show 3197 1627 moveto 224 /Times-Italic f1 (j) show 3291 1627 moveto 224 /Symbol f1 (+) show 3419 1627 moveto 224 /Times-Roman f1 (1) show 3550 1531 moveto 384 /Times-Italic f1 (x) show 3726 1627 moveto 224 /Times-Roman f1 (2) show 3888 1627 moveto 224 /Times-Italic f1 (j) show 3982 1627 moveto 224 /Symbol f1 (+) show 4110 1627 moveto 224 /Times-Roman f1 (1) show 4323 1531 moveto 384 /Symbol f1 (+) show 4613 1531 moveto 384 /Times-Italic f1 (c) show 4778 1627 moveto 224 /Times-Roman f1 (2) show 4940 1627 moveto 224 /Times-Italic f1 (j) show 5034 1627 moveto 224 /Symbol f1 (+) show 5162 1627 moveto 224 /Times-Roman f1 (1) show 5293 1531 moveto 384 /Times-Italic f1 (x) show 5469 1627 moveto 224 /Times-Roman f1 (2) show 5631 1627 moveto 224 /Times-Italic f1 (j) show 5725 1627 moveto 224 /Symbol f1 (+) show 5871 1627 moveto 224 /Times-Roman f1 (2) show end pse endp %%Page: 3 3 %%BeginPageSetup initializepage (christin; page: 3 of 3)setjob %%EndPageSetup -30 -31 :T gS 30 31 552 730 rC 81 83 :M f1_12 sf -.203(We can use the top equation to substitute for )A 403 73 24 16 rC 427 89 :M psb currentpoint pse 403 73 :M psb 30 dict begin currentpoint 3 -1 roll sub neg 3 1 roll sub 768 div 512 3 -1 roll exch div scale currentpoint translate 64 59 translate 11 261 moveto /fs 0 def /sf {exch dup /fs exch def dup neg matrix scale makefont setfont} def /f1 {findfont dup /cf exch def sf} def /ns {cf sf} def 384 /Times-Italic f1 (x) show 187 357 moveto 224 /Times-Roman f1 (2) show 349 357 moveto 224 /Times-Italic f1 (j) show 443 357 moveto 224 /Symbol f1 (-) show 570 357 moveto 224 /Times-Roman f1 (1) show end pse gR gS 30 31 552 730 rC 427 83 :M f1_12 sf -.231( in the)A 81 99 :M -.202(middle equation. Similarly, we can use the bottom equation)A 81 112 :M -.21(to substitute for )A 207 102 24 16 rC 231 118 :M psb currentpoint pse 207 102 :M psb 30 dict begin currentpoint 3 -1 roll sub neg 3 1 roll sub 768 div 512 3 -1 roll exch div scale currentpoint translate 64 59 translate 11 261 moveto /fs 0 def /sf {exch dup /fs exch def dup neg matrix scale makefont setfont} def /f1 {findfont dup /cf exch def sf} def /ns {cf sf} def 384 /Times-Italic f1 (x) show 187 357 moveto 224 /Times-Roman f1 (2) show 349 357 moveto 224 /Times-Italic f1 (j) show 443 357 moveto 224 /Symbol f1 (+) show 571 357 moveto 224 /Times-Roman f1 (1) show end pse gR gS 30 31 552 730 rC 231 112 :M f1_12 sf -.204( in the middle equation, too. The)A 81 128 :M -.203(resulting middle equation then assumes the form)A 216 143 153 19 rC 369 162 :M psb currentpoint pse 216 143 :M psb 30 dict begin currentpoint 3 -1 roll sub neg 3 1 roll sub 4896 div 608 3 -1 roll exch div scale currentpoint translate 64 41 translate 35 359 moveto /fs 0 def /sf {exch dup /fs exch def dup neg matrix scale makefont setfont} def /f1 {findfont dup /cf exch def sf} def /ns {cf sf} def 384 /Times-Roman f1 (\304) show 10 375 moveto 384 /Times-Italic f1 (y) show 175 471 moveto 224 /Times-Roman f1 (2) show 337 471 moveto 224 /Times-Italic f1 (j) show 541 375 moveto 384 /Symbol f1 (=) show 897 358 moveto 384 /Times-Roman f1 (\304) show 854 375 moveto 384 /Times-Italic f1 (a) show 1040 471 moveto 224 /Times-Roman f1 (2) show 1202 471 moveto 224 /Times-Italic f1 (j) show 1309 375 moveto 384 ns (x) show 1485 471 moveto 224 /Times-Roman f1 (2) show 1647 471 moveto 224 /Times-Italic f1 (j) show 1741 471 moveto 224 /Symbol f1 (-) show 1886 471 moveto 224 /Times-Roman f1 (2) show 2117 375 moveto 384 /Symbol f1 (+) show 2467 268 moveto 384 /Times-Roman f1 (\304) show 2410 375 moveto 384 /Times-Italic f1 (b) show 2584 471 moveto 224 /Times-Roman f1 (2) show 2746 471 moveto 224 /Times-Italic f1 (j) show 2853 375 moveto 384 ns (x) show 3029 471 moveto 224 /Times-Roman f1 (2) show 3191 471 moveto 224 /Times-Italic f1 (j) show 3380 375 moveto 384 /Symbol f1 (+) show 3706 358 moveto 384 /Times-Roman f1 (\304) show 3670 375 moveto 384 /Times-Italic f1 (c) show 3835 471 moveto 224 /Times-Roman f1 (2) show 3997 471 moveto 224 /Times-Italic f1 (j) show 4104 375 moveto 384 ns (x) show 4280 471 moveto 224 /Times-Roman f1 (2) show 4442 471 moveto 224 /Times-Italic f1 (j) show 4536 471 moveto 224 /Symbol f1 (+) show 4682 471 moveto 224 /Times-Roman f1 (2) show end pse gR gS 30 31 552 730 rC 81 184 :M f1_12 sf -.202(Which represents a tridiagonal system in the even-numbered)A 81 197 :M -.22(variables )A 151 187 16 16 rC 167 203 :M psb currentpoint pse 151 187 :M psb 30 dict begin currentpoint 3 -1 roll sub neg 3 1 roll sub 512 div 512 3 -1 roll exch div scale currentpoint translate 64 59 translate 11 261 moveto /fs 0 def /sf {exch dup /fs exch def dup neg matrix scale makefont setfont} def /f1 {findfont dup /cf exch def sf} def /ns {cf sf} def 384 /Times-Italic f1 (x) show 187 357 moveto 224 /Times-Roman f1 (2) show 349 357 moveto 224 /Times-Italic f1 (j) show end pse gR gS 30 31 552 730 rC 167 197 :M f1_12 sf -.203(. Because this system involves only the even-)A 81 213 :M -.202(numbered equations, it is half the size of the original)A 81 225 :M -.202(system we started with. If we apply this same even-odd)A 81 237 :M -.202(elimination scheme again, we form a tridiagonal system of)A 81 249 :M -.202(1/4 the original size involving every 4th unknown.)A 81 261 :M -.202(Continuing, we eventually reach a system of size 1, which we)A 81 273 :M -.202(solve by simple division. Turning this around, we can now)A 81 285 :M -.202(back substitute the solution to each smaller tridiagonal)A 81 297 :M -.202(system in the odd equations of the next size up until we)A 81 309 :M -.202(have returned to the original equations to complete the)A 81 321 :M -.223(solution.)A 81 345 :M -.202(Program this cyclic reduction algorithm for our test problem)A 81 357 :M -.202(of size 511 and time it. Comparing it to the original)A 81 369 :M -.202(algorithm, discuss why we do not get our solution 10 times)A 81 381 :M -.202(faster than before even though the vector-to-scalar)A 81 393 :M -.203(performance ratio for the Cray is 10:1.)A 81 417 :M -.202(d\) Recall our class dictum to think big. Replicate the)A 81 429 :M -.202(original size 511 tridiagonal equations 128 times and solve)A 81 441 :M -.202(them all at once. The declaration for array "a" should now)A 81 453 :M -.202(read "REAL a\(0:N,128\)" and so forth. Dividing the resulting)A 81 465 :M -.202(time by 128, how close have we now come to achieving our)A 81 477 :M -.22(10:1 goal?)A 81 501 :M f0_12 sf 4.738 .474(Extra Credit:)J 81 525 :M f1_12 sf -.202(Part c\) of this laboratory dealt with cyclic reduction by)A 81 537 :M -.202(powers of two. Try coding cyclic reduction by powers of 3)A 81 549 :M -.202(instead. That is, reduce the system at each step to a)A 81 561 :M -.202(tridiagonal system involving every 3rd unknown that is 1/3rd)A 81 573 :M -.202(the previous size. Discuss what advantages it might have)A 81 585 :M -.206(over the power of 2 method.)A endp %%Trailer end % md %%EOF