%!PS-Adobe-2.0 %%Creator: dvips(k) 5.86 Copyright 1999 Radical Eye Software %%Title: bench.dvi %%Pages: 11 %%PageOrder: Ascend %%BoundingBox: 0 0 596 842 %%EndComments %DVIPSWebPage: (www.radicaleye.com) %DVIPSCommandLine: dvips -o bench.ps bench.dvi %DVIPSParameters: dpi=600, compressed %DVIPSSource: TeX output 2001.01.23:1330 %%BeginProcSet: texc.pro %! /TeXDict 300 dict def TeXDict begin/N{def}def/B{bind def}N/S{exch}N/X{S N}B/A{dup}B/TR{translate}N/isls false N/vsize 11 72 mul N/hsize 8.5 72 mul N/landplus90{false}def/@rigin{isls{[0 landplus90{1 -1}{-1 1}ifelse 0 0 0]concat}if 72 Resolution div 72 VResolution div neg scale isls{ landplus90{VResolution 72 div vsize mul 0 exch}{Resolution -72 div hsize mul 0}ifelse TR}if Resolution VResolution vsize -72 div 1 add mul TR[ matrix currentmatrix{A A round sub abs 0.00001 lt{round}if}forall round exch round exch]setmatrix}N/@landscape{/isls true N}B/@manualfeed{ statusdict/manualfeed true put}B/@copies{/#copies X}B/FMat[1 0 0 -1 0 0] N/FBB[0 0 0 0]N/nn 0 N/IEn 0 N/ctr 0 N/df-tail{/nn 8 dict N nn begin /FontType 3 N/FontMatrix fntrx N/FontBBox FBB N string/base X array /BitMaps X/BuildChar{CharBuilder}N/Encoding IEn N end A{/foo setfont}2 array copy cvx N load 0 nn put/ctr 0 N[}B/sf 0 N/df{/sf 1 N/fntrx FMat N df-tail}B/dfs{div/sf X/fntrx[sf 0 0 sf neg 0 0]N df-tail}B/E{pop nn A definefont setfont}B/Cw{Cd A length 5 sub get}B/Ch{Cd A length 4 sub get }B/Cx{128 Cd A length 3 sub get sub}B/Cy{Cd A length 2 sub get 127 sub} B/Cdx{Cd A length 1 sub get}B/Ci{Cd A type/stringtype ne{ctr get/ctr ctr 1 add N}if}B/id 0 N/rw 0 N/rc 0 N/gp 0 N/cp 0 N/G 0 N/CharBuilder{save 3 1 roll S A/base get 2 index get S/BitMaps get S get/Cd X pop/ctr 0 N Cdx 0 Cx Cy Ch sub Cx Cw add Cy setcachedevice Cw Ch true[1 0 0 -1 -.1 Cx sub Cy .1 sub]/id Ci N/rw Cw 7 add 8 idiv string N/rc 0 N/gp 0 N/cp 0 N{ rc 0 ne{rc 1 sub/rc X rw}{G}ifelse}imagemask restore}B/G{{id gp get/gp gp 1 add N A 18 mod S 18 idiv pl S get exec}loop}B/adv{cp add/cp X}B /chg{rw cp id gp 4 index getinterval putinterval A gp add/gp X adv}B/nd{ /cp 0 N rw exit}B/lsh{rw cp 2 copy get A 0 eq{pop 1}{A 255 eq{pop 254}{ A A add 255 and S 1 and or}ifelse}ifelse put 1 adv}B/rsh{rw cp 2 copy get A 0 eq{pop 128}{A 255 eq{pop 127}{A 2 idiv S 128 and or}ifelse} ifelse put 1 adv}B/clr{rw cp 2 index string putinterval adv}B/set{rw cp fillstr 0 4 index getinterval putinterval adv}B/fillstr 18 string 0 1 17 {2 copy 255 put pop}for N/pl[{adv 1 chg}{adv 1 chg nd}{1 add chg}{1 add chg nd}{adv lsh}{adv lsh nd}{adv rsh}{adv rsh nd}{1 add adv}{/rc X nd}{ 1 add set}{1 add clr}{adv 2 chg}{adv 2 chg nd}{pop nd}]A{bind pop} forall N/D{/cc X A type/stringtype ne{]}if nn/base get cc ctr put nn /BitMaps get S ctr S sf 1 ne{A A length 1 sub A 2 index S get sf div put }if put/ctr ctr 1 add N}B/I{cc 1 add D}B/bop{userdict/bop-hook known{ bop-hook}if/SI save N @rigin 0 0 moveto/V matrix currentmatrix A 1 get A mul exch 0 get A mul add .99 lt{/QV}{/RV}ifelse load def pop pop}N/eop{ SI restore userdict/eop-hook known{eop-hook}if showpage}N/@start{ userdict/start-hook known{start-hook}if pop/VResolution X/Resolution X 1000 div/DVImag X/IEn 256 array N 2 string 0 1 255{IEn S A 360 add 36 4 index cvrs cvn put}for pop 65781.76 div/vsize X 65781.76 div/hsize X}N /p{show}N/RMat[1 0 0 -1 0 0]N/BDot 260 string N/Rx 0 N/Ry 0 N/V{}B/RV/v{ /Ry X/Rx X V}B statusdict begin/product where{pop false[(Display)(NeXT) (LaserWriter 16/600)]{A length product length le{A length product exch 0 exch getinterval eq{pop true exit}if}{pop}ifelse}forall}{false}ifelse end{{gsave TR -.1 .1 TR 1 1 scale Rx Ry false RMat{BDot}imagemask grestore}}{{gsave TR -.1 .1 TR Rx Ry scale 1 1 false RMat{BDot} imagemask grestore}}ifelse B/QV{gsave newpath transform round exch round exch itransform moveto Rx 0 rlineto 0 Ry neg rlineto Rx neg 0 rlineto fill grestore}B/a{moveto}B/delta 0 N/tail{A/delta X 0 rmoveto}B/M{S p delta add tail}B/b{S p tail}B/c{-4 M}B/d{-3 M}B/e{-2 M}B/f{-1 M}B/g{0 M} B/h{1 M}B/i{2 M}B/j{3 M}B/k{4 M}B/w{0 rmoveto}B/l{p -4 w}B/m{p -3 w}B/n{ p -2 w}B/o{p -1 w}B/q{p 1 w}B/r{p 2 w}B/s{p 3 w}B/t{p 4 w}B/x{0 S rmoveto}B/y{3 2 roll p a}B/bos{/SS save N}B/eos{SS restore}B end %%EndProcSet TeXDict begin 39158280 55380996 1000 600 600 (bench.dvi) @start %DVIPSBitmapFont: Fa cmsl10 10 31 /Fa 31 122 df<121E127FEAFF80A413005A123C0909788817>46 D58 D<160EA2161EA2163E163F5EA25EA25D83ED037FA21506A2150C83ED183FA2 1530A2156083EDC01F14011580140303007F5C0206130F140E140C141C02188002381307 14301470146091B6FC835B913880000349C7FCA2130683491401A25BA24981A201708013 F0486C4A1380D80FFC4A13C0B56C017F13FF93B6FC18FE383C7DBB3E>65 D<017FB612F017FEEFFF8001009039C0003FE06E48EB1FF0EF07F814FF92C7EA03FC18FE A21701A25B5CA21703A218FC010315074A15F8EF0FF0EF1FE0EF3FC0EF7F800107913801 FF004AEB07FC91B612F05F9139F80007FCEE00FE010FED7F804AEC3FC0171F18E018F017 0F131F4A15F8A5013F16F04A141FA218E0173FEF7FC0137F4AECFF804C13004C5AEE0FFC D801FFEC3FF0B812C094C7FC16F837397DB83B>II<013FB512E0A25B9039007FE0006E5AA2147F5DA514FF 92C7FCA55B5CA513035CA513075CA5130F5CA5131F5CA5133F5CA4EBFFE0007FEBFFC0A2 B6FC23397EB81E>73 D<023FB512F0A217E09139001FFC006F5AA35EA4151FA25EA4153F A25EA4157FA25EA415FFA293C7FCA45CA25DA41403A2D81F805BEA3FC0EA7FE0A24A5AEA FFC0140F01805B6C48485A00605C0070495A6C49C8FC6C13FE380F03F83803FFE0C690C9 FC2C3B7CB82B>I<017FB512F0A3010001C0C8FC6E5AA214FF92C9FCA55B5CA513035CA5 13075CA5130F5CA4EF0180011FED03005CA25F1706A2013F150E4A140CA2171C173C1738 017F15784A14F81601EE07F0161FD801FF14FFB8FC5FA231397DB834>76 D<90267FFF80923803FFFE81610100F0FE00027FEE0DFCDA6FE0151B14EF02CFEE33F8A2 DAC7F01563A219C71301028792380187F0DA83F8EC0307A21806190F90260381FC140C02 015F1818A218306E6C151F491660010604C05BA2037FEB0180A2943803003F130E010C03 065CED3F805F5F197F011C6D6C5A011895C7FC5FA25FDB0FE05C0138ECE180013002E3C7 5AA216E6ED07F604FC1301137001604A5C150301F05C00015DD807FCEE07FEB500E0D9C0 03B512FC150116804F397DB84C>I83 D<0007B812FCA3903AF8007FE003D80FC090383FC0004916 3C000EC7127F001E4B131C121CA212180038170C003014FF93C7FCA25A1818A2485BC749 1400A514035DA514075DA5140F5DA5141F5DA5143F5DA3147F4A7E0003B612F85AA23639 77B83C>I<14FF010713E090381F01F8903878007C01F8137E01FE7F0001801680A35BEA 007090C7FCA4EC0FFF49B5FC90390FFC3F00EB7FC03801FE00EA03F848485B485A484813 7E485A007F150690C7FC15FE48ECFC0C481301A21403007F9038077C18140E3A3F801C7E 303A1FC0F83FF03A07FFE01FC0C69038000F8027277CA52A>97 D99 DI<147F903803FFE090380F81F090383E00FC49137C48487F4848133F 0007805B48481480121F5B123FA248C7FCA3B71200A248C9FCA65A7EA2007E140EA25D6C 14186C14386D5B6C6C485A3907E003802601F01FC7FC38007FFCEB1FE021277BA525>I< 157F913801FFC0913807C1E091381F87F0EC3F0F147E14FCA2D901F813E0ED07C04948C7 FCA413075CA5130F5CA20007B512E0A326001FC0C7FC5CA5133F91C8FCA55B137EA513FE 5BA512015BA4487EB512F0A3243B7EBA19>IIII107 D<14FC137F14F8A213071303A314 F0A5130714E0A5130F14C0A5131F1480A5133F1400A55B137EA513FE5BA512015BA41203 B512E014C0A2163A7EB917>I<90270FC03FC0EB7F80D803FF903AFFF001FFE048903BC3 C0F80781F0913BCF007C1E00F826003FDCD97E387F6D485C02F0D93EE0137C4AD93FC013 7E4A5C047F14FE494891C75AA291C7127EA44902FE1301017E4A5CA501FE01011403494A 5CA5000102031407494A5CA4486C496C497EB500E1B500C3B51280A202C1028314004125 7EA445>I<90390FC03FC0D803FFEBFFF0489038C3C0F89138CF007C26003FDC137E6D5A 02F0133E4A133F5C5E4948137EA291C7FCA316FE5B017E5CA4150113FE495CA415031201 495CA400031407B500E1B512C0A202C114802A257EA42E>II<90 3901F80FE0017FEB3FFC01FFEBF03F9139FBC00F80902607FF0013C06D48EB07E04AEB03 F05C4A14F81601010715FC5CA5130F5CA41603011F15F85CEE07F0A2EE0FE0A2013FEC1F C01780163F6EEB7F0016FE9138E001F890397F7003F090397E3C0FC0DA0FFFC7FCEC03F8 91C9FC13FEA25BA41201A25BA2487EB512E0A32E3581A42E>I<90381F807C3903FF81FF 489038878F80EC8E1F39003F9C3FEB1F3814709138601F00ECE0044AC7FC133F5CA291C8 FCA35B137EA513FE5BA512015BA4487EB512F0A321257EA421>114 D<903803FE0C90380FFF9C90383E01FCEBF0004848137C4848133C1538485AA215181538 487E1530D807F0130013FCEBFFE06C13FC14FFC614806D13C0011F13E01300EC0FF01407 003013031401A31238007814E0A3007CEB03C0EC0780127EB4EB1F0038F3C07C38E1FFF0 38C03F801E277DA521>I<1306A4130EA2130C131CA2133C137C13FC5B12031207001FB5 FCB6FCA23803F8005BA512075BA5120F5BA5001F130C1380A4141C003F131813007E1438 EB80301470380FC0E03807C1C03803FF8038007E00183479B220>II<3A7FFFC01FFFB51280A23A07FC0007F86C48EB03E049 14C06D1480000115001506A25D7F00005C153815306D5B137E5DA24A5AEB3F0392C7FC5C 1406148C131F1498A214F0130F5C5CA25C130791C8FCA2282579A32C>I<90B538803FFE 5A150026000FF8EB0FF06D48EB07C017801700010314065EA26E5B0101143816305E8001 005CA24B5A1503027E90C7FC1506A25D147F6E5A1538153015E0141F5DA25D140F92C8FC 140EA2140CA25C143814305CA2003E5B127E38FE018049C9FC5BEAFC0EEA701C1378EA3F E0EA0F802F3580A32C>121 D E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fb cmtt10 10 23 /Fb 23 120 df<121FEA3F80EA7FC0EAFFE0A5EA7FC0EA3F80EA1F000B0B708A2C>46 D<1507ED0F80151FA2153F16005D157E15FE5D14015D14035DA214075D140F5D141F5D14 3F92C7FC5C147E14FE5CA213015C13035C13075C130F5C131F5CA2133F91C8FC5B137E13 FE5B12015B12035B12075BA2120F5B121F5B123F90C9FC5A127E12FE5AA25A127821417B B92C>I<121FEA3F80EA7FC0EAFFE0A5EA7FC0EA3F80EA1F00C7FCAE121FEA3F80EA7FC0 EAFFE0A5EA7FC0EA3F80EA1F000B2470A32C>58 D64 D<3801FFF0000713FE001F6D7E15E048809038C01FF81407EC01FC381F80000006C77EC8 127EA3ECFFFE131F90B5FC1203120F48EB807E383FF800EA7FC090C7FC12FE5AA47E007F 14FEEB8003383FE01F6CB612FC6C15FE6C14BF0001EBFE1F3A003FF007FC27247CA32C> 97 DI<903803FFE0011F13F8017F13FE48B5FC48804848C6FCEA0FF0485A49137E 4848131890C9FC5A127EA25AA8127EA2127F6C140F6DEB1F806C7E6D133F6C6CEB7F0039 07FE03FF6CB55A6C5C6C6C5B011F13E0010390C7FC21247AA32C>III103 DI<1307EB1FC0A2497EA36D5AA20107C7FC90C8FCA7387FFFC080B5FC7EA2 EA0007B3A8007FB512FCB612FEA36C14FC1F3479B32C>I107 D<387FFFE0B57EA37EEA 0003B3B3A5007FB61280B712C0A36C158022337BB22C>I<3A7F83F007E09039CFFC1FF8 3AFFDFFE3FFCD87FFF13FF91B57E3A07FE1FFC3E01FCEBF83F496C487E01F013E001E013 C0A301C01380B33B7FFC3FF87FF0027F13FFD8FFFE6D13F8D87FFC4913F0023F137F2D24 81A32C>I<397FF01FE039FFF87FFC9038F9FFFE01FB7F6CB6FC00019038F03F80ECC01F 02807FEC000F5B5BA25BB3267FFFE0B5FCB500F11480A36C01E0140029247FA32C>II<397FF01FE039FFF8FFF801FB13FE90B6FC6C158000019038F07FC09138801FE09138 0007F049EB03F85BED01FC491300A216FE167EA816FE6D14FCA2ED01F86D13036DEB07F0 150F9138801FE09138E07FC091B51280160001FB5B01F813F8EC3FC091C8FCAD387FFFE0 B57EA36C5B27367FA32C>I114 D<90387FF8700003B512F8120F5A5A387FC00F387E00034813015AA36C EB00F0007F140013F0383FFFC06C13FE6CEBFF80000314E0C66C13F8010113FCEB0007EC 00FE0078147F00FC143F151F7EA26C143F6D133E6D13FE9038F007FC90B5FC15F815E000 F8148039701FFC0020247AA32C>I<131E133FA9007FB6FCB71280A36C1500D8003FC8FC B1ED03C0ED07E0A5EC800F011FEB1FC0ECE07F6DB51280160001035B6D13F89038003FE0 232E7EAD2C>I<3A7FF003FF80486C487FA3007F7F0001EB000FB3A3151FA2153F6D137F 3900FE03FF90B7FC6D15807F6D13CF902603FE07130029247FA32C>I119 D E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fc cmex10 10 1 /Fc 1 81 df80 D E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fd cmmi6 6 1 /Fd 1 117 df<133013785BA4485AA4485AB51280A23803C000485AA448C7FCA4121EA2 5B1480383C03001306A25BEA1C38EA0FF0EA07C011217D9F18>116 D E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fe cmmi8 8 1 /Fe 1 66 df<1670A216F01501A24B7EA21507150DA2151915391531ED61FC156015C0EC 0180A2EC03005C14064A7F167E5C5CA25C14E05C4948137F91B6FC5B0106C7123FA25B13 1C1318491580161F5B5B120112031207000FED3FC0D8FFF8903807FFFEA22F2F7DAE35> 65 D E %EndDVIPSBitmapFont %DVIPSBitmapFont: Ff cmmi7 7 4 /Ff 4 117 df61 D<130E131F5BA2133E131C90C7FCA7EA03E0487EEA0C78EA187C1230A212605B 12C0A2EA01F0A3485AA2485AA2EBC180EA0F81A2381F0300A213066C5A131CEA07F06C5A 11287DA617>105 D<1407EC0F80141FA21500140E91C7FCA7EB03E0EB07F8EB0C3C1318 EB303E136013C0A248485AA2C7FCA25CA4495AA4495AA4495AA4495AA21238D87C1FC7FC 12FC133E485AEA70F8EA7FE0EA1F80193380A61B>I<131C133EA25BA45BA4485AB512E0 A23801F000485AA4485AA4485AA448C7FC1460A214C0123EEB0180EB0300EA1E06EA1F1C EA0FF8EA03E013267EA419>116 D E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fg cmsy10 10 6 /Fg 6 108 df<007FB81280B912C0A26C17803204799641>0 D<0060150600F8150F6C15 1F007E153F6C157E6C6C14FC6C6CEB01F86C6CEB03F06C6CEB07E06C6CEB0FC06C6CEB1F 80017EEB3F006D137E6D6C5A90380FC1F8903807E3F0903803F7E06DB45A6D5B6EC7FCA2 4A7E497F903803F7E0903807E3F090380FC1F890381F80FC90383F007E017E7F49EB1F80 4848EB0FC04848EB07E04848EB03F04848EB01F84848EB00FC48C8127E007E153F48151F 48150F00601506282874A841>2 D15 D20 D<1478A414F85CA213015C1303495AA2495A49 CCFC5B137E5B485A485AEA0FE0003FBA12FEBCFCA2003F19FED80FE0CCFCEA03F06C7E6C 7E137E7F7F6D7E6D7EA26D7E1301801300A2801478A4482C7BAA53>32 D<0070131C00F0131EB3B3B3B3A80070131C175277BD2A>107 D E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fh cmsy7 7 1 /Fh 1 1 df0 D E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fi cmmi10 10 23 /Fi 23 123 df<013FB612E090B712F05A120717E0270F807006C7FC391E00600E48140C 003813E04813C048141CEAC0011200148001035BA213071400A25B1578011E137CA3133E 133C137C157E13FC5B1201157F1203497FA3D801C0131C2C257EA32F>25 D<15FE913803FF8091380F83E091383E01F091387C00F85C494813FC0103147C4948137E 5C130F495AA249C7FC16FE5B137EA2150113FE4914FCA20001140316F85BED07F01203ED 0FE04914C0151F000715806DEB3F00157E6D5B390FEE01F09038E707E09038C3FF80D9C0 FCC7FC001F90C8FCA25BA2123FA290C9FCA25AA2127EA212FEA25AA2127027377EA42B> I<121C127FEAFF80A5EA7F00121C0909798817>58 D60 D<150C151E153EA2153C157CA2157815F8A215F01401 A215E01403A215C01407A21580140FA215005CA2141E143EA2143C147CA2147814F8A25C 1301A25C1303A2495AA25C130FA291C7FC5BA2131E133EA2133C137CA2137813F8A25B12 01A25B1203A25B1207A25B120FA290C8FC5AA2121E123EA2123C127CA2127812F8A25A12 601F537BBD2A>I<126012FCB4FCEA7FC0EA1FF0EA07FCEA01FF38007FC0EB1FF0EB07FC EB01FF9038007FC0EC1FF0EC07FCEC01FF9138007FC0ED1FF0ED07FCED01FF9238007FC0 EE1FF0EE07FCEE01FF9338007F80EF1FC0A2EF7F80933801FF00EE07FCEE1FF0EE7FC04B 48C7FCED07FCED1FF0ED7FC04A48C8FCEC07FCEC1FF0EC7FC04948C9FCEB07FCEB1FF0EB 7FC04848CAFCEA07FCEA3FF0EA7FC048CBFC12FC1270323279AD41>I<1760177017F016 01A21603A21607160FA24C7EA216331673166316C3A2ED0183A2ED0303150683150C1601 15181530A21560A215C014011580DA03007FA202061300140E140C5C021FB5FC5CA20260 C7FC5C83495A8349C8FC1306A25BA25B13385B01F01680487E000716FFB56C013F13FF5E A2383C7DBB3E>65 D<902603FFF893383FFF80496081D900079438FF80000206DC01BFC7 FCA2020E4C5A1A7E020C1606190CDA1C7E16FE4F5A02181630A20238166162023016C1F0 0181DA703F158395380303F002601506A202E0ED0C076202C01518183001016D6C140F06 605B028015C0A20103923801801FDD03005B140092380FC00649173F4D91C8FC01065DA2 010E4B5B4D137E130C6F6C5A011C17FEDCE1805B011802E3C7FCA2013802E6130104EC5C 1330ED03F8017016034C5C01F05CD807FC4C7EB500E0D9C007B512F01680150151397CB8 51>77 D<4BB4FC031F13F09238FE01FC913903F0007EDA07C0EB1F80DA1F80EB0FC0023E C7EA07E002FCEC03F0495A4948EC01F8495A4948EC00FC495A49C912FE49167E13FE4916 7F1201485AA2485AA2120F5B001F17FFA2485AA34848ED01FEA400FFEE03FC90C9FCA2EF 07F8A2EF0FF0A218E0171F18C0EF3F806C167F180017FE4C5A6C6C5D1603001F4B5A6D4A 5A000FED1F806C6C4AC7FC6D147E0003EC01F8D801FC495AD8007EEB0FC090263F807FC8 FC903807FFF801001380383D7CBA3F>79 D<147E903803FF8090390FC1C38090391F00EF C0017E137F49133F485A4848EB1F8012075B000F143F48481400A2485A5D007F147E90C7 FCA215FE485C5AA214015D48150CA21403EDF01C16181407007C1538007E010F1330003E 131F027B13706C01E113E03A0F83C0F9C03A03FF007F80D800FCEB1F0026267DA42C>97 D<133FEA1FFFA3C67E137EA313FE5BA312015BA312035BA31207EBE0FCEBE3FF9038E707 C0390FFE03E09038F801F001F013F8EBE000485A15FC5BA2123F90C7FCA214015A127EA2 140312FE4814F8A2140715F05AEC0FE0A215C0EC1F80143F00781400007C137E5C383C01 F86C485A380F07C06CB4C7FCEA01FC1E3B7CB924>II<14E0EB03F8A21307A314F0EB01 C090C7FCAB13F8EA03FEEA070F000E1380121C121812381230EA701F1260133F00E01300 12C05BEA007EA213FE5B1201A25B12035BA20007131813E01438000F133013C01470EB80 6014E014C01381EB838038078700EA03FEEA00F815397EB71D>105 D<150FED3F80A2157FA31600151C92C7FCABEC0F80EC3FE0ECF0F0903801C0F849487E14 005B130E130C131CEB1801133801305BA2EB0003A25DA21407A25DA2140FA25DA2141FA2 5DA2143FA292C7FCA25CA2147EA214FEA25CA21301001E5B123F387F83F0A238FF87E049 5A00FE5BD87C1FC8FCEA707EEA3FF8EA0FC0214981B722>I109 DI<90390F8003F090391FE00FFC903939F03C1F903A70F8700F80903AE0FD E007C09038C0FF80030013E00001491303018015F05CEA038113015CA2D800031407A25C A20107140FA24A14E0A2010F141F17C05CEE3F80131FEE7F004A137E16FE013F5C6E485A 4B5A6E485A90397F700F80DA383FC7FC90387E1FFCEC07E001FEC9FCA25BA21201A25BA2 1203A25B1207B512C0A32C3583A42A>112 D<02FC13C0903803FF0190380F838390383F 01C790397E00EF8049137F485A4848133F000715005B485A001F5C157E485AA2007F14FE 90C75AA3481301485CA31403485CA314075D140F127C141F007E495A003E137F381F01EF 380F839F3903FF1F80EA00FC1300143F92C7FCA35C147EA314FE5C130190387FFFF0A322 357DA425>I<3903E001F83907F807FE390E3C1E07391C3E381F3A183F703F800038EBE0 7F0030EBC0FF00705B00601500EC007E153CD8E07F90C7FCEAC07EA2120013FE5BA31201 5BA312035BA312075BA3120F5BA3121F5B0007C9FC21267EA425>I<01F8EB03C0D803FE EB07E0D8070F130F000E018013F0121C12180038140700301403D8701F130112601500D8 E03F14E000C090C7FC5BEA007E16C013FE5B1501000115805B150316001203495B150615 0E150C151C151815385D00015C6D485A6C6C485AD97E0FC7FCEB1FFEEB07F024267EA428 >118 D<903907E001F090391FF807FC9039783E0E0F9039E01F1C1FD801C09038383F80 3A03800FF07F0100EBE0FF5A000E4A1300000C157E021F133C001C4AC7FC1218A2C7123F A292C8FCA25CA2147EA214FEA24A130CA20101141C001E1518003F5BD87F81143801835C 00FF1560010714E03AFE0E7C01C0D87C1C495A2778383E0FC7FC391FF00FFC3907C003F0 29267EA42F>120 D<13F8D803FE1470D8070F14F8000EEB8001121C1218003814030030 15F0EA701F1260013F130700E0010013E012C05BD8007E130F16C013FE5B151F00011580 5BA2153F000315005BA25D157EA315FE5D1401000113033800F80790387C1FF8EB3FF9EB 0FE1EB00035DA2000E1307D83F805B007F495AA24A5A92C7FCEB003E007C5B00705B6C48 5A381E07C06CB4C8FCEA01FC25367EA429>II E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fj cmr8 8 40 /Fj 40 122 df<9138FF807E01079038E1FF80903A1F807FC3C0D93E00EB87E049EBFF07 4913FE485A00039138FC018049017CC7FCAAB712FCA22703E0007CC7FCB3A6486C13FE3A 7FFF0FFFF0A22B2F7FAE29>11 D<123C127EB4FCA21380A2127F123D1201A312031300A2 5A1206120E5A5A5A126009157A8714>44 DI<123C127E12FFA4 127E123C08087A8714>I<130C133C137CEA03FC12FFEAFC7C1200B3B113FE387FFFFEA2 172C7AAB23>49 DII<123C127E12FFA4127E12 3C1200AD123C127E12FE12FFA3127F123F1203A312071206A2120E120C121C1218123812 701260082A7A9C14>59 D66 DI70 DI73 D<90387FFFF0A201001300147EB3AD123812 FEA314FE5C1278387001F86C485A381E07E03807FF80D801FCC7FC1C2E7DAC24>I85 D87 D<13FF000713C0380F01F0381C00F8003F137C80 A2143F001E7FC7FCA4EB07FF137F3801FE1FEA07F0EA1FC0EA3F80EA7F00127E00FE1406 5AA3143F7E007E137F007FEBEF8C391F83C7FC390FFF03F83901FC01E01F207D9E23>97 DII<15F8141FA2 14011400ACEB0FE0EB7FF83801F81E3803E0073807C003380F8001EA1F00481300123E12 7EA25AA9127C127EA2003E13017EEB8003000F13073903E00EFC3A01F03CFFC038007FF0 90391FC0F800222F7EAD27>III<013F13F89038FFC3FE3903E1FF1E3807807C000F140C391F003E00A200 3E7FA76C133EA26C6C5A00071378380FE1F0380CFFC0D81C3FC7FC90C8FCA3121E121F38 0FFFF814FF6C14C04814F0391E0007F848130048147C12F848143CA46C147C007C14F86C EB01F06CEB03E03907E01F803901FFFE0038003FF01F2D7E9D23>III107 DI<2607C07FEB07F03B FFC3FFC03FFC903AC783F0783F3C0FCE01F8E01F803B07DC00F9C00F01F8D9FF8013C049 90387F000749137EA249137CB2486C01FEEB0FE03CFFFE0FFFE0FFFEA2371E7E9D3C>I< 3807C0FE39FFC3FF809038C703E0390FDE01F0EA07F8496C7EA25BA25BB2486C487E3AFF FE1FFFC0A2221E7E9D27>II<3807C0FE39FFC7FF80 9038CF03E0390FDC01F03907F800FC49137E49133E49133FED1F80A3ED0FC0A8151F1680 A2ED3F00A26D137E6D137C5D9038FC01F09038CE07E09038C7FF80D9C1FCC7FC01C0C8FC A9487EEAFFFEA2222B7E9D27>I<90380FE01890387FF8383801F81C3903E00E783807C0 07390F8003F8001F1301EA3F00A2007E1300A212FE5AA8127EA36C13017EEB8003380FC0 073803E00E3801F03C38007FF0EB1FC090C7FCA94A7E91381FFFC0A2222B7E9D25>I<38 0781F838FF87FEEB8E3FEA0F9CEA07B813B0EBF01EEBE000A45BB0487EB5FCA2181E7E9D 1C>I<3801FE183807FFB8381E01F8EA3C00481378481338A21418A27E7EB41300EA7FF0 6CB4FC6C13C06C13F0000113F838001FFC130138C0007E143EA26C131EA27EA26C133CA2 6C137838FF01F038E3FFC000C0130017207E9E1C>I<1360A413E0A312011203A2120712 1FB512F0A23803E000AF1418A714383801F03014703800F860EB3FE0EB0F80152A7FA81B >II<3AFFFC01FFC0A23A0FE0007E00000714 7C15380003143015706C6C1360A26C6C5BA390387C0180A26D48C7FCA2EB3F07EB1F06A2 EB0F8CA214DCEB07D8A2EB03F0A36D5AA26D5A221E7F9C25>I<3BFFFC3FFE07FFA23B0F E003F001F801C09038E000F00007010114E0812603E00314C0A2913807F8012701F00678 1380A29039F80E7C030000D90C3C1300A290397C181E06A2151F6D486C5AA2168C90391F 600798A216D890390FC003F0A36D486C5AA36DC75A301E7F9C33>I<3AFFFC07FF80A23A 0FF003FC000003EB01F0000114C06D485A000091C7FCEB7C06EB3E0E6D5A14B8EB0FB0EB 07E013036D7E497E1307EB067C497EEB1C1F01387FEB700F496C7E6E7ED803C07F00076D 7E391FE003FC3AFFF007FFC0A2221D7F9C25>I<3AFFFC01FFC0A23A0FE0007E00000714 7C1538000314306D137000011460A26C6C5BA2EBFC01017C5BEB7E03013E90C7FCA2EB1F 06A2148EEB0F8CA2EB07D8A2EB03F0A36D5AA26D5AA2495AA2130391C8FC1278EAFC06A2 5B131CEA7838EA7070EA3FE0EA0F80222B7F9C25>I E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fk cmbx10 10 40 /Fk 40 119 df<913A03FF8007FE027F9039F07FFF800103B500FDB512E0010F903A00FF FE0FF0D93FF8ECF81F90267FE0019038F03FF849485A4816E014804816C00200ED1FF081 F007C06F91C7FCA8B912E0A4000390C701C0C7FCB3ABB5D8FC3FEBFF80A43D3A7EB938> 11 D46 D<141E143E14FE1307133FB5FCA313CFEA000FB3B3A6007FB61280A4213779B630>49 DIII66 DIII71 D73 D76 DII80 D82 DI85 D87 D97 D<13FFB5FCA412077EAF4AB47E020F13F0023F13 FC9138FE03FFDAF00013804AEB7FC00280EB3FE091C713F0EE1FF8A217FC160FA217FEAA 17FCA3EE1FF8A217F06E133F6EEB7FE06E14C0903AFDF001FF80903AF8FC07FE009039F0 3FFFF8D9E00F13E0D9C00390C7FC2F3A7EB935>I<903801FFC0010F13FC017F13FFD9FF 8013802603FE0013C048485AEA0FF8121F13F0123F6E13804848EB7F00151C92C7FC12FF A9127FA27F123FED01E06C7E15036C6CEB07C06C6C14806C6C131FC69038C07E006DB45A 010F13F00101138023257DA42A>II<903803FF80011F13F0017F13FC3901FF83FE3A03FE007F804848 133F484814C0001FEC1FE05B003FEC0FF0A2485A16F8150712FFA290B6FCA301E0C8FCA4 127FA36C7E1678121F6C6C14F86D14F000071403D801FFEB0FE06C9038C07FC06DB51200 010F13FC010113E025257DA42C>II<161FD907FEEBFFC090387FFFE348B6EAEFE02607FE07138F26 0FF801131F48486C138F003F15CF4990387FC7C0EEC000007F81A6003F5DA26D13FF001F 5D6C6C4890C7FC3907FE07FE48B512F86D13E0261E07FEC8FC90CAFCA2123E123F7F6C7E 90B512F8EDFF8016E06C15F86C816C815A001F81393FC0000F48C8138048157F5A163FA3 6C157F6C16006D5C6C6C495AD81FF0EB07FCD807FEEB3FF00001B612C06C6C91C7FC0107 13F02B377DA530>I<13FFB5FCA412077EAFED7FC0913803FFF8020F13FE91381F03FFDA 3C01138014784A7E4A14C05CA25CA291C7FCB3A3B5D8FC3F13FFA4303A7DB935>II<13FFB5FCA412077EAF92380FFFE0A4923803FC0016F0ED0FE0ED1F804BC7 FC157E5DEC03F8EC07E04A5A141FEC7FE04A7E8181A2ECCFFEEC0FFF496C7F806E7F6E7F 82157F6F7E6F7E82150F82B5D8F83F13F8A42D3A7EB932>107 D<13FFB5FCA412077EB3 B3ACB512FCA4163A7DB91B>I<01FED97FE0EB0FFC00FF902601FFFC90383FFF80020701 FF90B512E0DA1F81903983F03FF0DA3C00903887801F000749DACF007F00034914DE6D48 D97FFC6D7E4A5CA24A5CA291C75BB3A3B5D8FC1FB50083B512F0A44C257DA451>I<01FE EB7FC000FF903803FFF8020F13FE91381F03FFDA3C011380000713780003497E6D4814C0 5CA25CA291C7FCB3A3B5D8FC3F13FFA430257DA435>I<903801FFC0010F13F8017F13FF D9FF807F3A03FE003FE048486D7E48486D7E48486D7EA2003F81491303007F81A300FF16 80A9007F1600A3003F5D6D1307001F5DA26C6C495A6C6C495A6C6C495A6C6C6CB45A6C6C B5C7FC011F13FC010113C029257DA430>I<9039FF01FF80B5000F13F0023F13FC9138FE 07FFDAF00113800003496C13C00280EB7FE091C713F0EE3FF8A2EE1FFCA3EE0FFEAA17FC 161FA217F8163F17F06E137F6E14E06EEBFFC0DAF00313809139FC07FE0091383FFFF802 0F13E0020390C7FC91C9FCACB512FCA42F357EA435>I<9038FE03F000FFEB0FFEEC3FFF 91387C7F809138F8FFC000075B6C6C5A5CA29138807F80ED3F00150C92C7FC91C8FCB3A2 B512FEA422257EA427>114 D<90383FF0383903FFFEF8000F13FF381FC00F383F000300 7E1301007C130012FC15787E7E6D130013FCEBFFE06C13FCECFF806C14C06C14F06C14F8 1203C614FC131F9038007FFE140700F0130114007E157E7E157C6C14FC6C14F8EB800190 38F007F090B512C000F8140038E01FF81F257DA426>I<130FA55BA45BA25B5BA25A1207 001FEBFFE0B6FCA3000390C7FCB21578A815F86CEB80F014816CEBC3E090383FFFC06D13 80903803FE001D357EB425>I<01FFEC3FC0B5EB3FFFA4000714016C80B3A35DA25DA26C 5C6E4813E06CD9C03E13FF90387FFFFC011F13F00103138030257DA435>II E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fl cmr7 7 3 /Fl 3 52 df<13381378EA01F8121F12FE12E01200B3AB487EB512F8A215267BA521>49 D<13FF000313E0380E03F0381800F848137C48137E00787F12FC6CEB1F80A4127CC7FC15 005C143E147E147C5C495A495A5C495A010EC7FC5B5B903870018013E0EA018039030003 0012065A001FB5FC5A485BB5FCA219267DA521>I<13FF000313E0380F01F8381C007C00 30137E003C133E007E133FA4123CC7123E147E147C5C495AEB07E03801FF8091C7FC3800 01E06D7E147C80143F801580A21238127C12FEA21500485B0078133E00705B6C5B381F01 F03807FFC0C690C7FC19277DA521>I E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fm cmr10 10 81 /Fm 81 124 df11 DIII<030C1303031E497EA2033E130FA2033C91C7FCA2037C5BA2 0378131EA303F8133EA24B133CA20201147CA24B1378A2020314F8A24B5BA30207130100 7FB91280BA12C0A26C1880C7271F0007C0C7FC021E5CA3023E130FA2023C91C8FCA2027C 5BA20278131EA302F8133E007FB91280BA12C0A26C1880280003E000F8C8FC4A5BA30107 1301A202805BA2010F1303A202005BA2491307A2011E5CA3013E130FA2013C91C9FCA201 7C5BA20178131EA20130130C3A4A7BB945>35 D<121C127FEAFF80A213C0A3127F121C12 00A412011380A2120313005A1206120E5A5A5A12600A1979B917>39 D<146014E0EB01C0EB0380EB0700130E131E5B5BA25B485AA2485AA212075B120F90C7FC A25A121EA2123EA35AA65AB2127CA67EA3121EA2121F7EA27F12077F1203A26C7EA26C7E 1378A27F7F130E7FEB0380EB01C0EB00E01460135278BD20>I<12C07E12707E7E7E120F 6C7E6C7EA26C7E6C7EA21378A2137C133C133E131EA2131F7FA21480A3EB07C0A6EB03E0 B2EB07C0A6EB0F80A31400A25B131EA2133E133C137C1378A25BA2485A485AA2485A48C7 FC120E5A5A5A5A5A13527CBD20>I<15301578B3A6007FB812F8B912FCA26C17F8C80078 C8FCB3A6153036367BAF41>43 D<121C127FEAFF80A213C0A3127F121C1200A412011380 A2120313005A1206120E5A5A5A12600A19798817>II<121C127F EAFF80A5EA7F00121C0909798817>I<150C151E153EA2153C157CA2157815F8A215F014 01A215E01403A215C01407A21580140FA215005CA2141E143EA2143C147CA2147814F8A2 5C1301A25C1303A2495AA25C130FA291C7FC5BA2131E133EA2133C137CA2137813F8A25B 1201A25B1203A25B1207A25B120FA290C8FC5AA2121E123EA2123C127CA2127812F8A25A 12601F537BBD2A>IIIII<1538A2157815F8A2140114031407A2140F141F141B14331473146314C313011483EB 030313071306130C131C131813301370136013C01201EA038013005A120E120C5A123812 305A12E0B712F8A3C73803F800AB4A7E0103B512F8A325397EB82A>I<0006140CD80780 133C9038F003F890B5FC5D5D158092C7FC14FC38067FE090C9FCABEB07F8EB3FFE903878 0F803907E007E090388003F0496C7E12066E7EC87EA28181A21680A4123E127F487EA490 C71300485C12E000605C12700030495A00385C6C1303001E495A6C6C485A3907E03F8000 01B5C7FC38007FFCEB1FE0213A7CB72A>II<123012 38123E003FB612E0A316C05A168016000070C712060060140E5D151800E01438485C5D5D C712014A5A92C7FC5C140E140C141C5CA25CA214F0495AA21303A25C1307A2130FA3495A A3133FA5137FA96DC8FC131E233B7BB82A>III<121C127FEAFF80A5EA7F00121CC7FCB2121C127FEAFF80A5EA7F00121C09 2479A317>I<121C127FEAFF80A5EA7F00121CC7FCB2121C127F5A1380A4127F121D1201 A412031300A25A1206A2120E5A121812385A1260093479A317>I<007FB812F8B912FCA2 6C17F8CCFCAE007FB812F8B912FCA26C17F836167B9F41>61 D<1538A3157CA315FEA34A 7EA34A6C7EA202077FEC063FA2020E7FEC0C1FA2021C7FEC180FA202387FEC3007A20270 7FEC6003A202C07F1501A2D901807F81A249C77F167FA20106810107B6FCA24981010CC7 121FA2496E7EA3496E7EA3496E7EA213E0707E1201486C81D80FFC02071380B56C90B512 FEA3373C7DBB3E>65 DI<913A01FF800180020FEBE003027F13F890 3A01FF807E07903A03FC000F0FD90FF0EB039F4948EB01DFD93F80EB00FF49C8127F01FE 153F12014848151F4848150FA248481507A2485A1703123F5B007F1601A35B00FF93C7FC AD127F6DED0180A3123F7F001F160318006C7E5F6C7E17066C6C150E6C6C5D0000161801 7F15386D6C5CD91FE05C6D6CEB03C0D903FCEB0F80902701FF803FC7FC9039007FFFFC02 0F13F002011380313D7BBA3C>IIIIIII<013FB512E0A39039001FFC00EC07F8B3B3A3123FEA7F80EAFF C0A44A5A1380D87F005B0070131F6C5C6C495A6C49C7FC380781FC3801FFF038007F8023 3B7DB82B>IIIIIIIIII<003FB812E0A3D9C003EB00 1F273E0001FE130348EE01F00078160000701770A300601730A400E01738481718A4C716 00B3B0913807FF80011FB612E0A335397DB83C>IIII<007FB590383FFFFC A3C601F801071380D97FE0D903FCC7FC013FEC01F06D6C5C5F6D6C5C6D6C13034CC8FC6D 6C1306160E6D6C5B6DEB8018163891387FC0306E6C5A16E06E6C5A91380FF18015FB6EB4 C9FC5D14036E7EA26E7F6F7EA24B7E15DF9138019FF09138038FF8150F91380607FC9138 0E03FE140C4A6C7EEC38000230804A6D7E14E04A6D7E49486D7E130391C76C7E01066E7E 130E010C6E7E011C1401013C8101FE822607FF80010713E0B500E0013FEBFF80A339397E B83E>II91 D93 D96 DIIIII<147E 903803FF8090380FC1E0EB1F8790383F0FF0137EA213FCA23901F803C091C7FCADB512FC A3D801F8C7FCB3AB487E387FFFF8A31C3B7FBA19>IIIIIII<2703F00FF0EB1FE000 FFD93FFCEB7FF8913AF03F01E07E903BF1C01F83803F3D0FF3800FC7001F802603F70013 CE01FE14DC49D907F8EB0FC0A2495CA3495CB3A3486C496CEB1FE0B500C1B50083B5FCA3 40257EA445>I<3903F00FF000FFEB3FFCECF03F9039F1C01F803A0FF3800FC03803F700 13FE496D7EA25BA35BB3A3486C497EB500C1B51280A329257EA42E>I I<3903F01FE000FFEB7FF89038F1E07E9039F3801F803A07F7000FC0D803FEEB07E049EB 03F04914F849130116FC150016FEA3167FAA16FEA3ED01FCA26DEB03F816F06D13076DEB 0FE001F614C09039F7803F009038F1E07E9038F0FFF8EC1FC091C8FCAB487EB512C0A328 357EA42E>II<3807E01F00FFEB7FC09038E1E3E09038E387F0380FE707EA03E613EE 9038EC03E09038FC0080491300A45BB3A2487EB512F0A31C257EA421>II<1318A51338A31378A313 F8120112031207001FB5FCB6FCA2D801F8C7FCB215C0A93800FC011580EB7C03017E1300 6D5AEB0FFEEB01F81A347FB220>IIIIII<003FB512FCA2EB8003D83E0013F8003CEB07 F00038EB0FE012300070EB1FC0EC3F800060137F150014FE495AA2C6485A495AA2495A49 5A495AA290387F000613FEA2485A485A0007140E5B4848130C4848131CA24848133C48C7 127C48EB03FC90B5FCA21F247EA325>II E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fn cmbx12 12 43 /Fn 43 119 df44 D47 DIIII<163FA25E5E5D5DA25D5D5D5DA25D92B5FCEC 01F7EC03E7140715C7EC0F87EC1F07143E147E147C14F8EB01F0EB03E0130714C0EB0F80 EB1F00133E5BA25B485A485A485A120F5B48C7FC123E5A12FCB91280A5C8000F90C7FCAC 027FB61280A531417DC038>I<0007150301E0143F01FFEB07FF91B6FC5E5E5E5E5E1680 4BC7FC5D15E092C8FC01C0C9FCAAEC3FF001C1B5FC01C714C001DF14F09039FFE03FFC91 38000FFE01FC6D7E01F06D13804915C0497F6C4815E0C8FC6F13F0A317F8A4EA0F80EA3F E0487E12FF7FA317F05B5D6C4815E05B007EC74813C0123E003F4A1380D81FC0491300D8 0FF0495AD807FEEBFFFC6CB612F0C65D013F1480010F01FCC7FC010113C02D427BC038> I<4AB47E021F13F0027F13FC49B6FC01079038807F8090390FFC001FD93FF014C0494813 7F4948EBFFE048495A5A1400485A120FA248486D13C0EE7F80EE1E00003F92C7FCA25B12 7FA2EC07FC91381FFF8000FF017F13E091B512F89039F9F01FFC9039FBC007FE9039FF80 03FF17804A6C13C05B6F13E0A24915F0A317F85BA4127FA5123FA217F07F121FA2000F4A 13E0A26C6C15C06D4913806C018014006C6D485A6C9038E01FFC6DB55A011F5C010714C0 010191C7FC9038003FF02D427BC038>I<121E121F13FC90B712FEA45A17FC17F817F017 E017C0A2481680007EC8EA3F00007C157E5E00785D15014B5A00F84A5A484A5A5E151FC8 48C7FC157E5DA24A5A14035D14074A5AA2141F5D143FA2147F5D14FFA25BA35B92C8FCA3 5BA55BAA6D5A6D5A6D5A2F447AC238>II67 DII72 DI<0107B7FCA590 C7001F1300B3B3A9EA1FE0487E487EA2487EA44B5AA26C48495A495C6C4813FF6C48485B 260FFC0713C06CB65A6C4AC7FCC66C13F8010F138030457DC33A>I77 D<923807FFC092B512FE0207ECFFC002 1F15F091267FFE0013FC902601FFF0EB1FFF01070180010313C04990C76C7FD91FFC6E6C 7E49486F7E49486F7E01FF8348496F7E48496F1380A248496F13C0A24890C96C13E0A248 19F04982003F19F8A3007F19FC49177FA400FF19FEAD007F19FC6D17FFA3003F19F8A26D 5E6C19F0A26E5D6C19E0A26C6D4B13C06C19806E5D6C6D4B13006C6D4B5A6D6C4B5A6D6C 4B5A6D6C4A5B6D01C001075B6D01F0011F5B010101FE90B5C7FC6D90B65A023F15F80207 15C002004AC8FC030713C047467AC454>79 DI82 DI86 D<903801FFE0011F13FE017F6D7E48B612E03A03FE007FF84848EB1FFC6D6D7E486C6D7E A26F7FA36F7F6C5A6C5AEA00F090C7FCA40203B5FC91B6FC1307013F13F19038FFFC0100 0313E0000F1380381FFE00485A5B127F5B12FF5BA35DA26D5B6C6C5B4B13F0D83FFE013E EBFFC03A1FFF80FC7F0007EBFFF86CECE01FC66CEB8007D90FFCC9FC322F7DAD36>97 DIIIIIII<137C48 B4FC4813804813C0A24813E0A56C13C0A26C13806C1300EA007C90C7FCAAEB7FC0EA7FFF A512037EB3AFB6FCA518467CC520>IIII<90277F 8007FEEC0FFCB590263FFFC090387FFF8092B5D8F001B512E002816E4880913D87F01FFC 0FE03FF8913D8FC00FFE1F801FFC0003D99F009026FF3E007F6C019E6D013C130F02BC5D 02F86D496D7EA24A5D4A5DA34A5DB3A7B60081B60003B512FEA5572D7CAC5E>I<90397F 8007FEB590383FFF8092B512E0028114F8913987F03FFC91388F801F000390399F000FFE 6C139E14BC02F86D7E5CA25CA35CB3A7B60083B512FEA5372D7CAC3E>II<90387F807FB53881FFE0028313F0028F13 F8ED8FFC91389F1FFE000313BE6C13BC14F8A214F0ED0FFC9138E007F8ED01E092C7FCA3 5CB3A5B612E0A5272D7DAC2E>114 D<90391FFC038090B51287000314FF120F381FF003 383FC00049133F48C7121F127E00FE140FA215077EA27F01E090C7FC13FE387FFFF014FF 6C14C015F06C14FC6C800003806C15806C7E010F14C0EB003F020313E0140000F0143FA2 6C141F150FA27EA26C15C06C141FA26DEB3F8001E0EB7F009038F803FE90B55A00FC5CD8 F03F13E026E007FEC7FC232F7CAD2C>IIII E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fo cmbx12 17.28 16 /Fo 16 119 df66 D73 D83 D<913803FFFE027FEBFFF00103B612FE010F6F7E4916E090273FFE001F7FD97FE001077F D9FFF801017F486D6D7F717E486D6E7F85717FA2717FA36C496E7FA26C5B6D5AEB1FC090 C9FCA74BB6FC157F0207B7FC147F49B61207010F14C0013FEBFE004913F048B512C04891 C7FC485B4813F85A5C485B5A5CA2B55AA45FA25F806C5E806C047D7F6EEB01F96C6DD903 F1EBFF806C01FED90FE114FF6C9027FFC07FC01580000191B5487E6C6C4B7E011F02FC13 0F010302F001011400D9001F90CBFC49437CC14E>97 D<92380FFFF04AB67E020F15F002 3F15FC91B77E01039039FE001FFF4901F8010113804901E0010713C04901804913E0017F 90C7FC49484A13F0A2485B485B5A5C5A7113E0485B7113C048701380943800FE0095C7FC 485BA4B5FCAE7EA280A27EA2806C18FCA26C6D150119F87E6C6D15036EED07F06C18E06C 6D150F6D6DEC1FC06D01E0EC7F806D6DECFF00010701FCEB03FE6D9039FFC03FFC010091 B512F0023F5D020F1580020102FCC7FCDA000F13C03E437BC148>99 D<92380FFFC04AB512FC020FECFF80023F15E091B712F80103D9FE037F499039F0007FFF 011F01C0011F7F49496D7F4990C76C7F49486E7F48498048844A804884485B727E5A5C48 717EA35A5C721380A2B5FCA391B9FCA41A0002C0CBFCA67EA380A27EA27E6E160FF11F80 6C183F6C7FF17F006C7F6C6D16FE6C17016D6C4B5A6D6D4A5A6D01E04A5A6D6DEC3FE001 0301FC49B45A6D9026FFC01F90C7FC6D6C90B55A021F15F8020715E0020092C8FC030713 F041437CC14A>101 D<903807FF80B6FCA6C6FC7F7FB3A8EF1FFF94B512F0040714FC04 1F14FF4C8193267FE07F7F922781FE001F7FDB83F86D7FDB87F07FDB8FC0814C7F039FC7 8015BE03BC8003FC825DA25DA25DA45DB3B2B7D8F007B71280A651647BE35A>104 DI<903807FF 80B6FCA6C6FC7F7FB3A90503B61280A6DD003FEB8000DE0FFCC7FCF01FF04E5AF0FFC04D 5B4D90C8FCEF07FC4D5AEF3FF04D5A4D5A4C90C9FC4C5AEE0FFC4C5A4C5AEE7FC04C7E03 837F03877F158F039F7F03BF7F92B5FC838403FC804B7E03F0804B6C7F4B6C7F1580707F 707F707FA270807080717FA2717F717F717FA2717F717F83867180727F95B57EB7D8E00F ECFFF0A64C647BE355>107 D<903807FF80B6FCA6C6FC7F7FB3B3B3B3ADB712E0A62364 7BE32C>I<902607FF80D91FFFEEFFF8B691B500F00207EBFF80040702FC023F14E0041F 02FF91B612F84C6F488193267FE07F6D4801037F922781FE001F9027E00FF0007FC6DA83 F86D9026F01FC06D7F6DD987F06D4A487F6DD98FC0DBF87EC7804C6D027C80039FC76E48 8203BEEEFDF003BC6E4A8003FC04FF834B5FA24B5FA24B94C8FCA44B5EB3B2B7D8F007B7 D8803FB612FCA67E417BC087>I<902607FF80EB1FFFB691B512F0040714FC041F14FF4C 8193267FE07F7F922781FE001F7FC6DA83F86D7F6DD987F07F6DD98FC0814C7F039FC780 15BE03BC8003FC825DA25DA25DA45DB3B2B7D8F007B71280A651417BC05A>I<923807FF E092B6FC020715E0021F15F8027F15FE494848C66C6C7E010701F0010F13E04901C00103 7F49496D7F4990C87F49486F7E49486F7E48496F13804819C04A814819E048496F13F0A2 4819F8A348496F13FCA34819FEA4B518FFAD6C19FEA46C6D4B13FCA36C19F8A26C6D4B13 F0A26C19E06C6D4B13C0A26C6D4B13806C6D4B13006D6C4B5A6D6D495B6D6D495B010701 F0010F13E06D01FE017F5B010090B7C7FC023F15FC020715E0020092C8FC030713E04843 7CC151>I114 D116 D118 D E %EndDVIPSBitmapFont end %%EndProlog %%BeginSetup %%Feature: *Resolution 600dpi TeXDict begin %%PaperSize: A4 %%EndSetup %%Page: 1 1 1 0 bop 374 930 a Fo(Iterativ)l(e)53 b(Solv)l(er)g(Benc)l(hmark)374 1220 y Fn(Jac)m(k)37 b(Dongarra,)h(Victor)e(Eijkhout,)h(Henk)g(v)-6 b(an)38 b(der)g(V)-9 b(orst)374 1471 y(2001/01/14)374 1836 y(1)156 b(In)m(tro)s(duction)374 1987 y Fm(The)33 b(traditional)g(p)r(erformance)g(measuremen)n(t)g(for)g(computers)g(on) h(scien)n(ti\014c)f(application)374 2087 y(has)39 b(b)r(een)h(the)h (Linpac)n(k)e(b)r(enc)n(hmark)g([2)o(],)h(whic)n(h)g(ev)-5 b(aluates)39 b(the)i(e\016ciency)e(with)i(whic)n(h)374 2186 y(a)34 b(mac)n(hine)g(can)g(solv)n(e)f(a)h(dense)h(system)f(of)g (equations.)g(Since)h(this)g(op)r(eration)e(allo)n(ws)g(for)374 2286 y(considerable)k(reuse)h(of)h(data,)f(it)i(is)e(p)r(ossible)h(to)g (sho)n(w)e(p)r(erformance)h(\014gures)g(a)g(sizeable)374 2385 y(p)r(ercen)n(tage)20 b(of)h(p)r(eak)g(p)r(erformance,)f(ev)n(en)h (for)f(mac)n(hines)h(with)h(a)f(sev)n(ere)e(un)n(balance)i(b)r(et)n(w)n (een)374 2485 y(memory)26 b(and)i(pro)r(cessor)d(sp)r(eed.)374 2634 y(In)h(practice,)f(sparse)g(linear)g(systems)g(are)g(equally)h (imp)r(ortan)n(t,)f(and)h(for)g(these)g(the)g(question)374 2734 y(of)19 b(data)g(reuse)g(is)g(more)g(complicated.)g(Sparse)f (systems)h(can)g(b)r(e)h(solv)n(ed)f(b)n(y)g(direct)g(or)g(iterativ)n (e)374 2834 y(metho)r(ds,)28 b(and)f(esp)r(ecially)h(for)f(iterativ)n (e)g(metho)r(ds)h(one)f(can)h(sa)n(y)e(that)i(there)g(is)g(little)g(or) f(no)374 2933 y(reuse)h(of)i(data.)f(Th)n(us,)g(suc)n(h)g(op)r (erations)f(will)h(ha)n(v)n(e)g(a)g(p)r(erformance)f(b)r(ound)i(b)n(y)f (the)h(slo)n(w)n(er)374 3033 y(of)d(the)h(pro)r(cessor)e(and)h(the)h (memory)-7 b(,)27 b(in)h(practice:)f(the)h(memory)-7 b(.)374 3182 y(W)g(e)34 b(aim)f(to)h(measure)f(the)h(p)r(erformance)f (of)h(a)f(represen)n(tativ)n(e)f(sample)h(of)h(iterativ)n(e)f(tec)n(h-) 374 3282 y(niques)k(on)h(an)n(y)f(giv)n(en)g(mac)n(hine;)g(w)n(e)h(are) f(not)g(in)n(terested)h(in)g(comparing,)e(sa)n(y)-7 b(,)37 b(one)g(pre-)374 3382 y(conditioner)f(on)i(one)f(mac)n(hine)g(against)f (another)h(preconditioner)f(on)i(another)e(mac)n(hine.)374 3481 y(Therefore)e(w)n(e)h(ha)n(v)n(e)f(strict)i(conformance)e(tests)h (on)g(the)h(results)f(of)h(the)f(b)r(enc)n(hmark,)g(ex-)374 3581 y(plained)27 b(b)r(elo)n(w.)374 3730 y(An)f(earlier)f(rep)r(ort)g (on)h(the)g(p)r(erformance)f(of)h(sup)r(ercomputers)f(on)h(sparse)e (equation)i(solv)n(ers)374 3830 y(can)h(b)r(e)h(found)g(in)g([3)o(].) 374 4195 y Fn(2)156 b(Motiv)-6 b(ation)374 4346 y Fm(The)28 b(sparse)f(b)r(enc)n(hmark)g(o\013ers)h(a)f(small)h(n)n(um)n(b)r(er)g (of)g(iterativ)n(e)g(metho)r(ds,)g(preconditioners)374 4445 y(and)h(storage)e(sc)n(hemes.)i(Rather)g(than)g(implemen)n(ting)h (all)f(kno)n(wn)f(metho)r(ds,)i(w)n(e)f(ha)n(v)n(e)f(c)n(ho-)374 4545 y(sen)33 b(those)h(that)g(ha)n(v)n(e)e(a)i(p)r(erformance)f (represen)n(tativ)n(e)f(of)h(larger)f(classes.)h(More)g(detailed)374 4645 y(discussion)26 b(will)i(follo)n(w)f(in)h(section)f(4.)374 4794 y(W)-7 b(e)24 b(w)n(an)n(t)f(to)g(stress)g(from)g(the)h(outset)g (that)g(w)n(e)f(did)h(not)g(aim)f(to)h(presen)n(t)f(the)h(most)f (sophisti-)374 4894 y(cated)28 b(metho)r(d.)i(Rather,)e(b)n(y)h (considering)e(com)n(binations)h(of)h(the)g(represen)n(tativ)n(e)e (elemen)n(ts)374 4993 y(used)h(in)h(the)g(b)r(enc)n(hmark)f(a)h(user)f (should)g(b)r(e)h(able)g(to)f(get)h(a)f(go)r(o)r(d)g(notion)h(of)f(the) h(exp)r(ected)374 5093 y(p)r(erformance)19 b(of)h(metho)r(ds)g(not)g (included.)h(Consisten)n(t)e(with)i(this)f(philosoph)n(y)-7 b(,)19 b(w)n(e)h(terminate)374 5193 y(eac)n(h)27 b(b)r(enc)n(hmark)h (run)g(after)g(a)g(\014xed)g(n)n(um)n(b)r(er)g(of)h(iterations,)e (since)h(w)n(e)g(are)g(not)g(in)n(terested)374 5292 y(in)f(con)n(v)n (ergence)f(sp)r(eed:)h(w)n(e)h(solely)e(measure)h(the)h(\015op)f(rate)g (p)r(er)h(iteration.)3329 5662 y(1)p eop %%Page: 2 2 2 1 bop 374 531 a Fm(As)34 b(storage)e(sc)n(hemes)h(w)n(e)h(o\013er)f (diagonal)g(storage,)f(and)i(compressed)f(ro)n(w)g(storage.)f(Both)374 631 y(of)f(these)g(formats)f(represen)n(t)g(t)n(ypical)g(matrices)g (for)h(three-dimensional)f(\014nite)i(elemen)n(t)f(or)374 731 y(\014nite)21 b(di\013erence)g(metho)r(ds.)g(The)g(diagonal)f (storage,)f(using)h(sev)n(en)g(diagonals,)f(is)i(the)h(natural)374 830 y(mo)r(de)f(for)h(problems)e(on)i(a)f(regular)f(\(`bric)n(k'\))i (domain;)f(the)h(compressed)e(ro)n(w)h(storage)3121 800 y Fl(1)3178 830 y Fm(is)g(the)374 930 y(natural)j(storage)f(sc)n(heme)h (for)g(irregular)f(domains.)h(Th)n(us)h(these)g(c)n(hoices)f(are)g (represen)n(tativ)n(e)374 1029 y(for)j(most)g(single-v)-5 b(ariable)26 b(ph)n(ysical)g(problems.)374 1175 y(The)h(iterativ)n(e)g (metho)r(ds)h(pro)n(vided)f(are)f(CG)i(and)g(GMRES.)f(The)h(plain)g (Conjugate)f(Gradi-)374 1275 y(en)n(ts)i(metho)r(d)h(is)g(represen)n (tativ)n(e)d(of)j(all)f(\014xed-storage)f(metho)r(ds,)i(including)f (sophisticated)374 1374 y(metho)r(ds)23 b(for)f(nonsymmetric)g (problems)g(suc)n(h)g(as)g(BiCGstab;)h(the)g(GMRES)g(metho)r(d)g (repre-)374 1474 y(sen)n(ts)h(the)h(class)f(of)h(metho)r(ds)h(that)f (ha)n(v)n(e)f(a)g(storage)f(demand)i(that)g(gro)n(ws)e(with)j(the)f(n)n (um)n(b)r(er)374 1574 y(of)i(iterations.)374 1719 y(Eac)n(h)37 b(iterativ)n(e)h(metho)r(d)h(can)f(b)r(e)h(run)f(unpreconditioned)g({)h (whic)n(h)f(is)h(computationally)374 1819 y(equiv)-5 b(alen)n(t)32 b(to)h(using)g(a)g(Jacobi)e(preconditioner)h({)h(or)f (with)i(an)e(ILU)i(preconditioner.)d(F)-7 b(or)374 1919 y(the)40 b(diagonal)f(storage)f(sc)n(heme)h(a)h(blo)r(c)n(k)f(Jacobi)g (metho)r(d)i(is)f(also)f(pro)n(vided;)g(this)h(giv)n(es)374 2018 y(a)d(go)r(o)r(d)g(indication)h(of)f(domain)h(decomp)r(osition)f (metho)r(ds.)h(If)g(these)g(metho)r(ds)g(are)f(used)374 2118 y(with)j(inexact)f(sub)r(domain)h(solv)n(es,)e(then)i(the)g(ILU)g (preconditioner)e(giv)n(es)g(the)i(exp)r(ected)374 2218 y(p)r(erformance)26 b(for)h(these.)374 2561 y Fn(3)156 b(Structure)37 b(of)g(the)h(b)s(enc)m(hmark)374 2707 y Fm(W)-7 b(e)37 b(ha)n(v)n(e)e(implemen)n(ted)i(a)f(b)r(enc)n(hmark)g (that)h(constructs)e(a)i(test)f(matrix)g(and)h(precondi-)374 2807 y(tioner,)f(and)h(solv)n(es)f(a)h(linear)f(system)h(with)h(them.)g (Separate)e(\015op)h(coun)n(ters)f(and)h(timers)374 2907 y(are)29 b(k)n(ept)g(for)h(the)g(w)n(ork)f(exp)r(ended)h(in)g(v)n (ector)f(op)r(erations,)g(matrix)g(v)n(ector)g(pro)r(ducts,)g(pre-)374 3006 y(conditioner)d(solv)n(es,)g(and)i(other)f(op)r(erations)f(in)n(v) n(olv)n(ed)g(in)i(the)g(iterativ)n(e)e(metho)r(d.)i(The)g(\015op)374 3106 y(coun)n(ts)f(and)h(\015ops)f(rates)g(in)i(eac)n(h)e(of)h(these)g (categories,)e(as)h(w)n(ell)h(as)f(the)h(o)n(v)n(erall)e(\015ops)i (rates,)374 3206 y(are)e(rep)r(orted)h(at)h(the)g(end)f(of)h(eac)n(h)f (run.)374 3351 y(The)i(b)r(enc)n(hmark)h(comprises)e(sev)n(eral)g (storage)g(formats,)h(iterativ)n(e)g(metho)r(ds,)h(and)g(precon-)374 3451 y(ditioners.)e(T)-7 b(ogether)27 b(these)h(form)g(a)g(represen)n (tativ)n(e)f(sample)h(of)g(the)h(tec)n(hniques)g(in)f(t)n(ypical)374 3551 y(sparse)e(matrix)h(applications.)g(W)-7 b(e)28 b(describ)r(e)f(these)g(elemen)n(ts)h(in)g(more)f(detail)g(in)h (section)f(4.)374 3696 y(W)-7 b(e)31 b(o\013er)f(a)g(reference)g(co)r (de,)h(whic)n(h)g(is)f(mean)n(t)h(to)g(represen)n(t)e(a)h(p)r(ortable)h (implemen)n(tation)374 3796 y(of)c(the)g(v)-5 b(arious)26 b(metho)r(ds,)i(without)g(an)n(y)e(mac)n(hine-sp)r(eci\014c)h (optimisations.)f(In)i(addition)f(to)374 3896 y(this)38 b(w)n(e)g(supply)g(a)f(n)n(um)n(b)r(er)h(of)g(v)-5 b(arian)n(ts)37 b(of)h(the)g(co)r(de)g(that)g(should)g(p)r(erform)g(b)r(etter)g(on)374 3995 y(certain)27 b(mac)n(hines,)g(and)g(most)g(lik)n(ely)g(w)n(orse)f (on)i(some)f(others;)g(see)g(section)g(6.)374 4231 y Fk(3.1)89 b(Conformance)31 b(of)g(the)h(b)s(enc)m(hmark)374 4378 y Fm(Since)25 b(w)n(e)g(lea)n(v)n(e)f(op)r(en)i(the)g(p)r (ossibilit)n(y)f(that)h(a)f(lo)r(cal)f(implemen)n(ter)i(mak)n(e)f (fargoing)e(c)n(hanges)374 4478 y(to)g(the)i(b)r(enc)n(hmark)e(co)r(de) g(\(see)h(section)g(3.2\),)f(ev)n(ery)g(submission)g(of)h(b)r(enc)n (hmark)f(results)g(has)374 4577 y(to)e(b)r(e)h(accompanied)e(b)n(y)h (pro)r(of)g(that)h(the)g(lo)r(cal)f(implemen)n(tation)g(conforms)g(to)g (the)h(reference)374 4677 y(co)r(de.)31 b(F)-7 b(or)32 b(conformance)e(testing)i(w)n(e)g(supply)g(a)f(script)h(that)g(matc)n (hes)g(the)g(error)e(norm)i(in)374 4777 y(the)i(\014nal)f(iteration)g (of)h(a)f(run)g(\(w)n(e)h(stop)f(the)h(iteration)f(after)g(ten)h (steps\))g(to)f(the)h(v)-5 b(alue)34 b(of)374 4876 y(that)27 b(error)f(stored)h(on)g(\014le.)374 5022 y(This)33 b(is)h(a)g(static)g (test,)g(and)g(in)g(practice)f(it)h(only)g(allo)n(ws)e(c)n(hanges)h(to) h(the)g(reference)f(co)r(de)374 5122 y(that)23 b(are)e(not)i(n)n (umerically)f(signi\014can)n(t.)g(In)g(particular,)g(it)h(precludes)f (an)g(implemen)n(ter)h(from)374 5221 y(replacing)g(the)j (preconditioner)d(b)n(y)i(a)g(di\013eren)n(t)g(one.)f(W)-7 b(e)26 b(justify)g(this)f(from)g(our)f(standp)r(oin)n(t)p 374 5318 213 4 v 374 5413 a Fj(1.)51 b(Use)23 b(of)h(compressed)f (column)g(storage)h(should)g(giv)n(e)g(roughly)g(the)h(same)e(p)r (erformance.)3329 5662 y Fm(2)p eop %%Page: 3 3 3 2 bop 374 531 a Fm(that)36 b(the)g(b)r(enc)n(hmark)f(is)h(not)f(a)h (test)g(of)f(the)i(b)r(est)f(p)r(ossible)f(preconditioner)g(or)g (iterativ)n(e)374 631 y(metho)r(d,)40 b(but)g(rather)e(of)i(metho)r(ds) f(represen)n(tativ)n(e)f(for)h(a)g(wider)g(class)g(with)h(resp)r(ect)f (to)374 731 y(computer)27 b(p)r(erformance.)374 880 y(Since)40 b(the)g(b)r(enc)n(hmark)f(includes)h(ILU)g(preconditioners,)e(this)i (static)g(conformance)e(test)374 980 y(w)n(ould)20 b(a)h(priori)e(seem) i(to)g(b)r(e)g(biased)g(against)f(parallel)f(implemen)n(tations)i(of)g (the)g(b)r(enc)n(hmark.)374 1079 y(This)27 b(p)r(oin)n(t)h(is)f (further)h(elab)r(orated)e(in)i(section)f(5.)374 1328 y Fk(3.2)89 b(Benc)m(hmark)32 b(rep)s(orting)374 1479 y Fm(An)24 b(implemen)n(ter)g(of)g(the)g(b)r(enc)n(hmark)f(can)g(rep)r (ort)g(p)r(erformance)g(results)g(on)h(v)-5 b(arious)22 b(lev)n(els,)374 1578 y(eac)n(h)k(next)i(lev)n(el)f(encompassing)f(all) i(of)f(the)h(earlier)e(options.)374 1703 y(1.)147 b(Using)27 b(only)g(compiler)g(\015ags)g(in)h(the)g(compilation)f(of)g(the)h (reference)f(co)r(de.)374 1803 y(2.)147 b(Using)27 b(compiler)g (directiv)n(es)g(in)h(the)g(source)e(of)i(the)g(reference)e(co)r(de.) 374 1902 y(3.)147 b(Rewriting)28 b(the)i(reference)e(co)r(de)h(in)g (suc)n(h)g(a)f(w)n(a)n(y)g(that)h(an)n(y)g(di\013erences)f(are)g (solely)h(in)586 2002 y(a)e(di\013eren)n(t)h(order)e(of)h(sc)n (heduling)g(the)h(op)r(erations.)374 2101 y(4.)147 b(Rewriting)33 b(the)g(reference)g(co)r(de)g(b)n(y)g(replacing)f(some)g(algorithm)g(b) n(y)h(a)g(mathemati-)586 2201 y(cally)25 b(equiv)-5 b(alen)n(t)25 b(form)n(ulation)g(of)h(the)g(algorithm)f(\(that)h(is:)g(in)g(exact)f (arithmetic)g(the)586 2301 y(\(in)n(termediate\))j(results)f(should)g (b)r(e)h(the)g(same\).)374 2425 y(The)d(last)h(t)n(w)n(o)f(lev)n(els)g (ma)n(y)g(or)g(will)h(in)g(general)e(in\015uence)i(the)g(n)n(umerical)f (results,)g(so)g(results)374 2525 y(from)f(co)r(des)g(th)n(us)g (rewritten)g(should)g(b)r(e)h(accompanied)e(b)n(y)h(pro)r(of)g(that)g (the)h(sp)r(eci\014c)g(realisa-)374 2624 y(tion)i(of)h(the)g(b)r(enc)n (hmark)f(repro)r(duces)f(the)i(reference)f(results)g(within)h(a)f (certain)g(tolerance.)374 2774 y(Eac)n(h)32 b(run)h(of)g(the)h(b)r(enc) n(hmark)e(co)r(de)h(ends)h(with)f(a)g(rep)r(ort)g(on)g(ho)n(w)f(man)n (y)h(\015oating)g(p)r(oin)n(t)374 2874 y(op)r(erations)20 b(w)n(ere)h(p)r(erformed)h(in)g(the)g(v)-5 b(arious)21 b(op)r(erations.)g(Implemen)n(ters)g(should)h(use)g(these)374 2973 y(n)n(um)n(b)r(ers)30 b(to)g(do)h(rep)r(orting)e(\(rather)h(than)h (using)g(hardw)n(are)d(\015op)j(coun)n(ters,)f(for)g(instance\),)374 3073 y(but)e(they)g(are)e(free)i(to)f(substitute)h(their)g(o)n(wn)f (timers.)374 3222 y(The)21 b(b)r(enc)n(hmark)g(comes)g(with)h(shell)f (scripts)g(that)h(run)f(a)g(n)n(um)n(b)r(er)g(of)h(tests,)f(and)h(rep)r (ort)e(b)r(oth)374 3322 y(b)r(est)29 b(p)r(erformance)f(and)h (asymptotic)f(p)r(erformance)g(for)g(the)i(whole)e(co)r(de)h(and)g (elemen)n(ts)g(of)374 3422 y(it.)21 b(Asymptotic)g(p)r(erformance)f(is) h(determined)g(b)n(y)g(making)f(a)g(least-squares)f(\014t)i Fi(y)26 b Fm(=)d Fi(a)5 b Fm(+)g Fi(bx)3282 3391 y Fh(\000)p Fl(1)374 3521 y Fm(through)23 b(the)i(data)f(p)r(oin)n(ts,)g(where)g Fi(y)j Fm(is)d(the)h(observ)n(ed)e(mega\015op)g(rate)g(and)i Fi(x)f Fm(is)h(the)f(dataset)374 3621 y(size.)j(The)h(asymptotic)f(p)r (erformance)f(is)i(then)g(the)g(v)-5 b(alue)27 b(of)h Fi(a)p Fm(.)374 3770 y(This)21 b(assumption)g(on)g(the)h(p)r (erformance)e(b)r(eha)n(viour)h(accomo)r(dates)f(b)r(oth)h(cac)n (he-pro)r(cessors,)374 3870 y(for)40 b(whic)n(h)g(w)n(e)g(exp)r(ect)h Fi(b)j(>)g Fm(0)c(as)g(the)h(dataset)e(size)i(o)n(v)n(er\015o)n(ws)c (the)k(cac)n(he,)f(and)g(v)n(ector)374 3969 y(pro)r(cessors,)e(for)h (whic)n(h)i(w)n(e)f(exp)r(ect)g Fi(b)k(<)g Fm(0)c(as)g(p)r(erformance)f (go)r(es)h(up)g(with)h(increasing)374 4069 y(v)n(ector)26 b(length.)374 4219 y(F)-7 b(or)23 b(cac)n(he-based)g(pro)r(cessors)f(w) n(e)i(ma)n(y)f(exp)r(ect)i(a)f(plateau)g(b)r(eha)n(viour)f(if)i(the)f (cac)n(he)g(is)g(large;)374 4318 y(w)n(e)j(discard)f(the)i(fron)n(t)g (of)f(this)h(plateau)f(when)h(calculating)f(the)h(asymptotic)f(p)r (erformance.)374 4683 y Fn(4)156 b(Elemen)m(ts)35 b(of)j(the)f(b)s(enc) m(hmark)h(co)s(de)374 4834 y Fm(The)25 b(user)f(of)h(the)h(b)r(enc)n (hmark)e(has)g(the)i(follo)n(wing)e(c)n(hoices)g(in)h(determining)g (the)g(problem)g(to)374 4933 y(run.)374 5183 y Fk(4.1)89 b(Storage)32 b(formats)374 5333 y Fm(The)27 b(matrix)g(can)h(b)r(e)g (in)f(the)h(follo)n(wing)f(formats:)3329 5662 y(3)p eop %%Page: 4 4 4 3 bop 374 531 a Fg(\017)170 b Fm(Diagonal)34 b(storage)f(for)h(a)h (sev)n(en-diagonal)d(matrix)i(corresp)r(onding)g(to)g(\014nite)i (di\013er-)586 631 y(ences)27 b(in)h(three)f(dimensions;)374 731 y Fg(\017)170 b Fm(Compressed)23 b(ro)n(w)g(storage)g(of)h(a)g (matrix)g(where)g(the)h(sparsit)n(y)e(structure)h(is)h(randomly)586 830 y(generated;)19 b(eac)n(h)g(ro)n(w)f(has)i(b)r(et)n(w)n(een)g(2)f (and)h(20)f(nonzeros,)f(eac)n(h)h(themselv)n(es)h(randomly)586 930 y(generated,)g(and)h(the)h(bandwidth)f(is)h Fg(\024)g Fi(n)1896 900 y Fl(2)p Ff(=)p Fl(3)2022 930 y Fm(whic)n(h)f(again)f (corresp)r(onds)f(to)i(a)g(problem)586 1029 y(in)28 b(three)f(space)g (dimensions.)374 1145 y(F)-7 b(or)23 b(b)r(oth)g(formats)g(a)g (symmetric)h(v)-5 b(arian)n(t)22 b(is)i(giv)n(en,)e(where)h(only)h (half)f(the)h(matrix)f(is)h(stored.)374 1286 y(The)i(diagonal)g (storage)e(is)j(v)n(ery)f(regular,)f(giving)h(co)r(de)g(that)h(has)f(a) h(structure)f(of)h(lo)r(op)f(nests)374 1386 y(of)36 b(depth)h(three.)f (V)-7 b(ector)36 b(computers)g(should)g(p)r(erform)g(v)n(ery)f (e\016cien)n(tly)i(on)f(this)h(storage)374 1486 y(sc)n(heme.)27 b(In)h(general,)e(all)h(index)h(calculation)f(of)g(o\013sets)g(can)h(b) r(e)g(done)f(statically)-7 b(.)374 1627 y(Matrix-v)n(ector)30 b(op)r(erations)i(on)g(compressed)g(ro)n(w)g(storage)e(ma)n(y)j(ha)n(v) n(e)e(a)i(di\013eren)n(t)g(p)r(erfor-)374 1726 y(mance)23 b(in)i(the)f(transp)r(ose)f(case)g(from)h(the)g(regular)e(case.)h(Suc)n (h)h(an)g(op)r(eration)f(in)h(the)h(regular)374 1826 y(case)h(is)i(based)e(on)i(inner)f(pro)r(ducts;)g(in)h(the)g(transp)r (ose)e(case)h(it)h(uses)f(v)n(ector)f(up)r(dates)h(\(axp)n(y)374 1925 y(op)r(erations\).)38 b(Since)h(these)g(t)n(w)n(o)f(op)r(erations) g(ha)n(v)n(e)g(di\013eren)n(t)h(load/store)e(c)n(haracteristics,)374 2025 y(they)f(ma)n(y)f(yield)i(di\013eren)n(t)f(\015ops)f(rates.)h(In)g (the)h(symmetric)e(case,)h(where)f(w)n(e)h(store)f(only)374 2125 y(half)29 b(the)h(matrix,)f(suc)n(h)g(op)r(erations)f(use)i(in)f (fact)h(the)g(regular)e(algorithm)g(for)h(half)g(the)h(ma-)374 2224 y(trix,)39 b(and)g(the)h(transp)r(ose)f(algorithm)f(for)h(the)h (other)f(half.)h(Th)n(us,)f(the)h(p)r(erformance)f(of,)374 2324 y(for)34 b(instance,)h(the)h(matrix-v)n(ector)d(pro)r(duct,)i (will)g(b)r(e)h(di\013eren)n(t)f(in)h(GMRES)f(from)g(in)g(the)374 2424 y(Conjugate)27 b(Gradien)n(t)g(metho)r(d.)374 2564 y(The)37 b(CRS)g(format)f(giv)n(es)g(algorithms)g(that)h(consist)f(of)h (an)g(outer)f(lo)r(op)h(o)n(v)n(er)e(the)i(matrix)374 2664 y(ro)n(ws,)24 b(with)j(an)e(inner)h(lo)r(op)g(that)g(in)n(v)n(olv) n(es)e(indirect)i(addressing.)f(Th)n(us,)h(w)n(e)f(exp)r(ect)i(a)e(lo)n (w)n(er)374 2764 y(p)r(erformance,)17 b(esp)r(ecially)i(on)f(mac)n (hines)g(where)g(the)i(indirect)e(addressing)g(in)n(v)n(olv)n(es)f(an)h (access)374 2863 y(to)27 b(memory)-7 b(.)374 3083 y Fk(4.2)89 b(Iterativ)m(e)33 b(metho)s(ds)374 3224 y Fm(The)e(follo)n(wing)e (iterativ)n(e)h(metho)r(ds)i(ha)n(v)n(e)d(b)r(een)j(implemen)n(ted)2428 3194 y Fl(2)2496 3224 y Fm(\(for)f(more)f(details)h(on)f(the)374 3324 y(metho)r(ds)d(men)n(tioned,)h(see)f(the)h(T)-7 b(emplates)28 b(b)r(o)r(ok)f([1]\):)374 3440 y Fg(\017)170 b Fm(Conjugate)20 b(Gradien)n(ts)f(metho)r(d;)i(this)g(is)f(the)h(arc)n (het)n(ypical)e(Krylo)n(v)g(space)g(metho)r(d)i(for)586 3540 y(symmetric)j(systems.)g(W)-7 b(e)25 b(ha)n(v)n(e)e(included)i (this,)g(rather)f(than)g(MINRES)h(or)f(SYMLQ,)586 3639 y(for)j(its)h(ease)f(of)h(co)r(ding,)g(and)g(for)f(the)i(fact)f(that)g (its)g(p)r(erformance)f(b)r(eha)n(viour)g(is)g(rep-)586 3739 y(resen)n(tativ)n(e)36 b(of)h(the)i(more)d(complicated)i(metho)r (ds.)g(The)f(results)g(for)g(CG)h(are)f(also)586 3839 y(more-or-less)23 b(represen)n(tativ)n(e)i(for)h(transp)r(ose-free)f (metho)r(ds)i(for)f(nonsymmetric)g(sys-)586 3938 y(tems,)32 b(suc)n(h)f(as)h(BiCGstab,)f(whic)n(h)h(also)f(ha)n(v)n(e)g(a)g (storage)f(demand)i(constan)n(t)f(in)h(the)586 4038 y(n)n(um)n(b)r(er) 27 b(of)h(iterations.)374 4138 y Fg(\017)170 b Fm(Generalized)29 b(Minim)n(um)h(Residual)f(metho)r(d,)h(GMRES.)g(This)f(p)r(opular)g (metho)r(d)h(has)586 4237 y(b)r(een)g(included)g(b)r(ecause)g(its)g(p)r (erformance)f(b)r(eha)n(viour)f(is)i(di\013eren)n(t)g(from)g(CG:)g (stor-)586 4337 y(age)25 b(and)i(computational)f(complexit)n(y)g(are)g (an)g(increasing)f(function)j(of)e(the)h(iteration)586 4436 y(coun)n(t.)j(F)-7 b(or)30 b(that)h(reason)f(GMRES)g(is)h(most)f (often)h(used)g(in)g(cycles)f(of)h Fi(m)g Fm(steps.)f(F)-7 b(or)586 4536 y(lo)n(w)21 b(v)-5 b(alues)21 b(of)h Fi(m)p Fm(,)g(the)g(computational)g(p)r(erformance)e(for)i(GMRES)g(will)g(not) g(b)r(e)g(m)n(uc)n(h)586 4636 y(di\013eren)n(t)f(than)g(for)g(CG.)g(F) -7 b(or)20 b(larger)f(v)-5 b(alues,)21 b(sa)n(y)f Fi(m)j(>)f Fm(5,)f(the)h Fi(j)k Fm(inner)20 b(pro)r(ducts)h(in)g(the)586 4735 y(j-th)28 b(iteration)f(ma)n(y)h(in\015uence)g(the)g(p)r (erformance.)f(W)-7 b(e)28 b(ha)n(v)n(e)f(included)h(GMRES\(20\))586 4835 y(in)g(our)e(b)r(enc)n(hmark.)p 374 4924 213 4 v 374 5019 a Fj(2.)51 b(W)-6 b(e)31 b(ha)n(v)n(e)g(not)g(included)g (metho)r(ds)f(suc)n(h)h(as)f(BiCG)g(in)g(the)h(b)r(enc)n(hmark,)f(whic) n(h)g(use)h(a)f(pro)r(duct)h(with)374 5098 y(the)c(transp)r(ose)h (matrix)d Fe(A)1103 5074 y Fd(t)1131 5098 y Fj(.)h(In)i(man)n(y)e (cases)h(forming)e(this)i(pro)r(duct)h(is)e(impractical,)f(and)i(for)f (this)h(reason)374 5176 y(suc)n(h)g(metho)r(ds)g(are)g(less)g(used)h (than)g(transp)r(ose-free)f(metho)r(ds)g(suc)n(h)h(as)f(BiCGstab.)g (BiCG)g(has)g(the)h(same)374 5255 y(p)r(erformance)h(b)r(eha)n(viour)h (as)g(CG,)f(except)j(for)c(the)j(di\013erence)g(b)r(et)n(w)n(een)g(the) g(regular)e(and)h(the)h(transp)r(ose)374 5334 y(matrix-v)n(ector)23 b(pro)r(duct.)i(F)-6 b(or)24 b(diagonal)g(matrix)f(storage)i(there)g (is)e(no)h(di\013erence;)h(for)e(compressed)h(storage)374 5413 y(it)f(is)g(the)i(di\013erence)f(b)r(et)n(w)n(een)i(a)e(dot)g(pro) r(duct)h(and)f(a)g(v)n(ector)h(up)r(date,)f(b)r(oth)h(indirectly)f (addressed.)3329 5662 y Fm(4)p eop %%Page: 5 5 5 4 bop 374 531 a Fm(The)31 b(Conjugate)f(and)h(BiConjugate)f(gradien)n (t)g(metho)r(ds)h(\(see)g(\014gure)f(1\))62 b(in)n(v)n(olv)n(e,)30 b(outside)p 374 643 1499 4 v 374 762 a(Let)d Fi(A)p Fm(,)h Fi(M)9 b Fm(,)28 b Fi(x)p Fm(,)g Fi(b)f Fm(b)r(e)h(giv)n(en;)374 862 y(compute)f Fi(r)747 874 y Fl(1)808 862 y Fm(=)c Fi(Ax)c Fg(\000)f Fi(b)p Fm(;)374 961 y(for)27 b Fi(i)22 b Fm(=)h(1)14 b Fi(:)g(:)g(:)f Fm(10)501 1061 y(solv)n(e)26 b(preconditioner:)g Fi(z)h Fm(=)22 b Fi(M)1519 1031 y Fh(\000)p Fl(1)1608 1061 y Fi(r)501 1161 y Fm(inner)27 b(pro)r(duct)h Fi(\032)1068 1173 y Ff(i)1118 1161 y Fm(=)23 b Fi(r)1245 1131 y Ff(t)1275 1161 y Fi(z)501 1260 y Fm(if)28 b Fi(i)22 b(>)h Fm(1,)k(up)r(date)h Fi(p)23 b Fg( )g Fi(z)f Fm(+)c Fi(p)p Fm(\()p Fi(\032)1519 1272 y Ff(i)1547 1260 y Fi(=\032)1632 1272 y Ff(i)p Fh(\000)p Fl(1)1744 1260 y Fm(\))501 1360 y(matrix)27 b(v)n(ector)f(pro)r(duct:)i Fi(q)e Fm(=)c Fi(Ap)501 1460 y Fm(inner)27 b(pro)r(duct)h Fi(\031)e Fm(=)d Fi(p)1228 1429 y Ff(t)1257 1460 y Fi(q)501 1559 y Fm(up)r(date)28 b Fi(x)23 b Fg( )g Fi(x)c Fg(\000)f Fi(p\031)780 1659 y(r)26 b Fg( )d Fi(r)e Fg(\000)d Fi(q)s(\031)1146 1817 y Fm(Figure)27 b(1:)g(Conjugate)g(Gradien)n(t)g(algorithm)p 374 1886 V 374 2052 a(the)34 b(matrix-v)n(ector)d(pro)r(duct)j(and)f (preconditioner)g(application,)g(only)g(simple)h(v)n(ector)e(op-)374 2152 y(erations.)27 b(Th)n(us,)h(their)g(p)r(erformance)f(can)h(b)r(e)h (c)n(haracterised)d(as)i(Blas1-lik)n(e.)e(The)j(GMRES)374 2251 y(metho)r(d)f(\(see)g(\014gure)f(2\),)56 b(on)27 b(the)h(other)g(hand,)f(uses)h(orthogonalisation)d(of)j(eac)n(h)f(new)g (gen-)p 374 2363 V 374 2482 a(Let)g Fi(A)p Fm(,)h Fi(M)9 b Fm(,)28 b Fi(x)p Fm(,)g Fi(b)f Fm(b)r(e)h(giv)n(en;)374 2582 y(for)f Fi(i)22 b Fm(=)h(1)14 b Fi(:)g(:)g(:)f Fm(10)501 2681 y(matrix)27 b(and)g(preconditioner)f(apply:)i Fi(z)e Fm(=)d Fi(AM)2038 2651 y Fh(\000)p Fl(1)2127 2681 y Fi(r)501 2781 y Fm(orthogonalize)i Fi(z)31 b Fm(against)26 b(all)i(earlier)e Fi(v)1779 2793 y Ff(j)1814 2781 y Fm(,)i Fi(j)g(<)22 b(i)501 2881 y Fm(normalize)k Fi(v)919 2893 y Ff(i)970 2881 y Fg( )d Fi(z)t(=)p Fg(k)p Fi(z)t Fg(k)p Fm(.)501 2980 y(up)r(date)28 b(QR)f(factorisation)f(of)i(size)f Fi(i)18 b Fm(+)g(1)g Fg(\002)g Fi(i)27 b Fm(Hessen)n(b)r(erg)g(matrix) 374 3080 y(Up)r(date)h Fi(x)23 b Fg( )g Fi(x)c Fg(\000)994 3018 y Fc(P)1082 3105 y Ff(i)1123 3080 y Fi(v)1163 3092 y Ff(i)1191 3080 y Fi(c)1227 3092 y Ff(i)530 3238 y Fm(Figure)27 b(2:)g(One)g(restart)g(cycle)g(of)h(the)g(Generalized)e(Minim)n(um)j (Residual)e(metho)r(d)p 374 3307 V 374 3473 a(erated)22 b(Krylo)n(v)g(v)n(ector)g(against)h(all)g(previous,)f(so)h(a)g(certain) g(amoun)n(t)g(of)h(cac)n(he)e(reuse)h(should)374 3573 y(b)r(e)28 b(p)r(ossible.)f(See)h(also)e(section)h(6)g(for)g(a)h (rewritten)f(v)n(ersion)f(that)i(uses)f(Blas3)f(k)n(ernels.)374 3796 y Fk(4.3)89 b(Preconditioners)374 3939 y Fm(The)27 b(follo)n(wing)g(preconditioners)f(are)g(a)n(v)-5 b(ailable)1930 3909 y Fl(3)1966 3939 y Fm(:)374 4056 y Fg(\017)170 b Fm(No)27 b(preconditioner;)374 4156 y Fg(\017)170 b Fm(P)n(oin)n(t)24 b(ILU;)h(for)f(the)i(diagonal)d(storage)g(a)i(true)g(ILU-D)g(is)g (implemen)n(ted,)h(in)f(the)g(CRS)586 4255 y(case)h(w)n(e)i(use)f (SSOR,)h(whic)n(h)f(has)g(the)h(same)f(algorithmic)g(structure)g(as)g (ILU;)374 4355 y Fg(\017)170 b Fm(Line)29 b(ILU)h(for)f(the)h(diagonal) e(storage)g(sc)n(heme)h(only;)g(this)h(mak)n(es)f(a)g(factorisation)f (of)586 4454 y(the)g(line)g(blo)r(c)n(ks.)374 4554 y Fg(\017)170 b Fm(Blo)r(c)n(k)39 b(Jacobi)f(for)h(the)h(diagonal)e (storage)g(sc)n(heme)h(only;)g(this)h(is)g(parallel)e(on)h(the)586 4654 y(lev)n(el)22 b(of)g(the)h(plane)f(blo)r(c)n(ks.)g(The)g(blo)r(c)n (k)g(Jacobi)f(preconditioner)h(giv)n(es)f(a)h(p)r(erformance)586 4753 y(represen)n(tativ)n(e)c(of)h(domain)h(decomp)r(osition)f(metho)r (ds,)h(including)g(Sc)n(h)n(w)n(arz)e(metho)r(ds.)374 4870 y(The)28 b(p)r(oin)n(t)h(ILU)g(metho)r(d)g(is)f(t)n(ypical)g(of)h (commonly)f(used)g(preconditioners.)f(It)i(has)f(largely)374 4970 y(the)g(structure)g(of)h(the)g(matrix-v)n(ector)d(pro)r(duct,)i (but)i(on)e(parallel)f(mac)n(hines)h(its)g(sequen)n(tial)374 5070 y(nature)f(inhibits)h(e\016cien)n(t)g(execution.)p 374 5160 213 4 v 374 5255 a Fj(3.)51 b(W)-6 b(e)25 b(ha)n(v)n(e)h(not)f (included)h(the)f(commonly)f(used)h(Jacobi)g(preconditioner,)h(since)f (this)f(is)g(mathematically)374 5334 y(equiv)l(alen)n(t)f(to)g(scaling) g(the)g(matrix)e(to)i(unit)g(diagonal,)f(a)h(strategy)g(that)h(has)f (the)g(exact)h(same)d(p)r(erformance)374 5413 y(as)i(using)h(no)g (preconditioner.)3329 5662 y Fm(5)p eop %%Page: 6 6 6 5 bop 374 531 a Fm(The)26 b(line)g(ILU)g(metho)r(d)h(uses)e(a)h(Lev)n (el)f(2)h(BLAS)g(k)n(ernel,)f(namely)h(the)h(solution)e(of)h(a)g (banded)374 631 y(system.)31 b(It)g(is)g(also)f(a)h(candidate)g(for)g (algorithm)f(replacemen)n(t,)g(substituting)i(a)e(Neumann)374 731 y(expansion)c(for)h(the)h(system)g(solution)f(with)h(the)g(line)g (blo)r(c)n(ks.)374 1096 y Fn(5)156 b(P)m(arallel)35 b(realisation)374 1246 y Fm(Large)c(parts)i(of)h(the)g(b)r(enc)n(hmark)e(co)r(de)i(are)e (conceptually)h(parallel.)f(Th)n(us)i(w)n(e)f(encourage)374 1346 y(the)24 b(submission)g(of)h(results)e(on)i(parallel)e(mac)n (hines.)h(Ho)n(w)n(ev)n(er,)e(the)j(actual)f(implemen)n(tation)374 1446 y(of)35 b(the)h(metho)r(ds)g(in)h(the)f(reference)f(co)r(de)g(is)h (sequen)n(tial.)f(In)h(particular,)e(the)i(b)r(enc)n(hmark)374 1545 y(includes)27 b(ILU)h(preconditioners)e(using)h(the)h(natural)f (ordering)f(of)i(the)g(v)-5 b(ariables.)374 1695 y(It)22 b(has)g(long)f(b)r(een)i(realised)e(that)i(ILU)f(factorisations)f(can)g (only)h(b)r(e)h(implemen)n(ted)g(e\016cien)n(tly)374 1794 y(on)h(a)h(parallel)f(arc)n(hitecture)g(if)i(the)f(v)-5 b(ariables)24 b(are)g(ren)n(um)n(b)r(ered)h(from)g(the)g(natural)f (ordering)374 1894 y(to,)j(for)g(instance,)h(a)f(m)n(ulti-colour)f(or)h (nested)h(dissection)f(ordering.)374 2043 y(Because)36 b(of)i(our)e(strict)i(conformance)e(test)i(\(see)f(section)g(3.1\),)g (the)h(implemen)n(ter)f(is)h(not)374 2143 y(immediately)25 b(at)f(lib)r(ert)n(y)h(to)g(replace)e(the)j(preconditioner)d(b)n(y)i (an)f(ILU)h(based)g(on)f(a)h(di\013eren)n(t)374 2243 y(ordering.)19 b(Instead,)j(w)n(e)f(facilitate)g(the)h(parallel)f (execution)g(of)g(the)h(b)r(enc)n(hmark)f(b)n(y)g(pro)n(viding)374 2342 y(sev)n(eral)k(orderings)h(of)i(the)g(test)g(matrices,)e(namely:) 374 2467 y Fg(\017)170 b Fm(Rev)n(erse)26 b(Cuthill-McKee)h(ordering.) 374 2566 y Fg(\017)170 b Fm(Multi-colour)21 b(ordering;)g(here)h(w)n(e) g(do)g(not)g(supply)g(the)h(n)n(um)n(b)r(ering)f(with)h(the)g(minimal) 586 2666 y(n)n(um)n(b)r(er)k(of)h(colours,)e(but)i(rather)f(a)g (colouring)f(based)h(on)g([4].)374 2766 y Fg(\017)170 b Fm(Nested)30 b(dissection)g(ordering;)e(this)j(is)f(an)f(ordering)g (based)g(on)h(edge-cutting,)g(rather)586 2865 y(than)d(\014nding)h(a)f (separator)f(set)h(of)h(no)r(des.)374 2990 y(The)e(implemen)n(ter)h (then)g(has)f(the)h(freedom)f(to)g(impro)n(v)n(e)f(parallel)g (e\016ciency)i(b)n(y)f(optimising)374 3089 y(the)i(implemen)n(tation)f (for)g(a)h(particular)e(ordering.)374 3239 y(Again,)20 b(the)i(implemen)n(ter)f(should)h(heed)f(the)h(distinction)f(of)g (section)g(3.2)g(b)r(et)n(w)n(een)g(execution)374 3338 y(b)n(y)31 b(using)f(only)h(compiler)g(\015ags)f(or)h(directiv)n(es)f (in)h(the)h(co)r(de,)f(and)g(explicit)h(rewrites)e(of)h(the)374 3438 y(co)r(de)c(to)g(force)g(the)h(parallel)f(distribution.)374 3803 y Fn(6)156 b(Co)s(de)38 b(v)-6 b(arian)m(ts)374 3954 y Fm(W)f(e)35 b(supply)h(a)f(few)g(v)-5 b(arian)n(ts)35 b(of)g(the)h(reference)e(co)r(de)h(that)h(incorp)r(orate)e (transformations)374 4053 y(that)h(are)f(unlik)n(ely)i(or)e(imp)r (ossible)h(to)g(b)r(e)h(done)f(b)n(y)g(a)g(compiler.)g(These)g (transformations)374 4153 y(target)g(sp)r(eci\014c)i(arc)n(hitecture)e (t)n(yp)r(es,)h(p)r(ossibly)g(giving)g(a)g(higher)g(p)r(erformance)f (than)h(the)374 4253 y(reference)26 b(co)r(de,)i(while)g(still)f (conforming)g(to)g(it;)h(see)g(section)f(3.1.)374 4377 y Fk(Naiv)m(e)32 b(co)s(ding)f(of)g(regular)h(ILU)43 b Fm(Putting)31 b(the)g(tests)g(for)f(b)r(oundary)g(conditions)g(in)h (the)586 4477 y(inner)40 b(lo)r(op)h(is)f(bad)h(co)r(ding)f(practice,)g (except)h(for)f(data\015o)n(w)g(mac)n(hines,)g(where)g(it)586 4577 y(exp)r(oses)26 b(the)i(structure)g(of)f(the)h(lo)r(op.)374 4676 y Fk(W)-8 b(a)m(v)m(efron)m(t)33 b(ordering)e(of)h(regular)g(ILU) 43 b Fm(W)-7 b(e)23 b(supply)g(a)g(v)-5 b(arian)n(t)22 b(of)h(the)h(co)r(de)f(where)f(the)586 4776 y(triple)27 b(lo)r(op)g(nest)g(has)f(b)r(een)i(rearranged)c(explicitly)k(to)f(a)f (sequen)n(tial)h(outer)f(lo)r(op)h(and)586 4875 y(t)n(w)n(o)22 b(fully)i(parallel)e(inner)h(lo)r(ops.)f(This)h(ma)n(y)g(b)r(ene\014t)h (data\015o)n(w)e(and)h(v)n(ector)e(mac)n(hines.)374 4975 y Fk(Long)31 b(v)m(ectors)43 b Fm(A)n(t)c(the)g(cost)f(of)h(a)f(few)h (sup)r(er\015uous)f(op)r(erations)f(on)i(zeros,)e(the)i(v)n(ector)586 5075 y(length)33 b(in)g(the)g(diagonal-storage)c(matrix-v)n(ector)i (pro)r(duct)i(can)f(b)r(e)h(increased)f(from)586 5174 y Fi(O)r Fm(\()p Fi(n)p Fm(\))c(to)g Fi(O)r Fm(\()p Fi(n)1042 5144 y Fl(3)1080 5174 y Fm(\).)g(This)g(should)f(b)r(ene\014t)h(v)n (ector)f(computers.)3329 5662 y(6)p eop %%Page: 7 7 7 6 bop 374 531 a Fk(Di\013eren)m(t)31 b(GMRES)g(orthogonalisation)f (algorithms)40 b Fm(There)c(are)g(at)g(least)h(t)n(w)n(o)f(re-)586 631 y(form)n(ulations)26 b(of)h(the)h(orthogonalisation)c(part)j(of)g (the)h(GMRES)f(metho)r(d.)h(They)f(can)586 731 y(enable)c(use)f(of)h (Lev)n(el)g(3)f(BLAS)i(op)r(erations)d(and,)i(in)h(parallel)e(con)n (text,)g(com)n(bine)h(inner)586 830 y(pro)r(duct)30 b(op)r(erations.)g (Ho)n(w)n(ev)n(er,)f(these)h(co)r(de)h(transformations)e(no)h(longer)g (preserv)n(e)586 930 y(the)e(seman)n(tics)f(under)g(computer)g({)g (rather)g(than)h(exact)f({)g(arithmetic.)374 1281 y Fn(7)156 b(Results)374 1429 y Fm(The)28 b(follo)n(wing)g(tables)h(con)n(tain)f (preliminary)f(results)i(for)f(the)h(mac)n(hines)f(listed)h(in)g(table) g(1.)374 1529 y(In)j(table)h(2)f(w)n(e)g(rep)r(ort)g(the)h(top)g(sp)r (eed)g(rep)r(orted)e(regardless)g(the)i(iterativ)n(e)e(metho)r(d,)i (pre-)374 1629 y(conditioner,)j(and)g(problem)g(size.)h(This)f(sp)r (eed)h(is)g(t)n(ypically)f(rep)r(orted)f(on)i(a)f(fairly)g(small)374 1728 y(problem,)27 b(where)g(presumably)g(the)h(whole)f(data)g(set)h (\014ts)f(in)h(cac)n(he.)374 1875 y(W)-7 b(e)24 b(compute)f(an)h (`asymptotic)f(sp)r(eed')h(b)n(y)f(a)h(least-squares)d(\014t)j(as)f (describ)r(ed)g(in)h(section)g(3.2.)374 1975 y(W)-7 b(e)28 b(rep)r(ort)e(this)i(asymptotic)f(sp)r(eed)h(for)f(the)h(follo)n(wing)f (comp)r(onen)n(ts:)374 2097 y Fg(\017)170 b Fm(The)34 b(matrix)g(v)n(ector)f(pro)r(duct.)i(W)-7 b(e)34 b(rep)r(ort)g(this)h (in)f(regular)f(storage,)g(and)h(in)g(com-)586 2197 y(pressed)28 b(ro)n(w)g(storage)g(separately)g(for)h(the)g(symmetric)g(case)g (\(cg\))g(and)h(the)g(nonsym-)586 2297 y(metric)37 b(case)f(since)h (these)h(ma)n(y)e(ha)n(v)n(e)g(di\013eren)n(t)i(p)r(erformance)e(c)n (haracteristics;)f(see)586 2396 y(section)27 b(4.1.)374 2496 y Fg(\017)170 b Fm(The)27 b(ILU)h(solv)n(e.)f(W)-7 b(e)28 b(also)e(rep)r(ort)h(this)h(lik)n(ewise)f(in)h(three)f(v)-5 b(arian)n(ts.)374 2595 y Fg(\017)170 b Fm(The)27 b(Blo)r(c)n(k)g (Jacobi)g(solv)n(e.)374 2695 y Fg(\017)170 b Fm(V)-7 b(ector)25 b(op)r(erations.)g(These)h(are)f(the)h(parts)f(of)h(the)h (algorithm)e(that)h(are)f(indep)r(enden)n(t)586 2795 y(of)31 b(storage)e(formats.)h(W)-7 b(e)31 b(rep)r(ort)f(the)h (e\016ciency)g(of)g(v)n(ector)e(op)r(erations)h(for)g(the)i(CG)586 2894 y(metho)r(d;)25 b(in)g(case)f(of)h(GMRES)g(a)f(higher)g (e\016ciency)h(can)g(b)r(e)g(attained)f(b)n(y)h(using)f(Lev)n(el)586 2994 y(2)j(BLAS)h(and)f(Lev)n(el)g(3)g(BLAS)h(routines.)f(W)-7 b(e)28 b(ha)n(v)n(e)e(not)i(tested)g(this.)p 374 3068 3136 4 v 372 3168 4 100 v 423 3138 a(Pro)r(cessor)p 977 3168 V 256 w(Man)n(ufacturer)e(/)i(t)n(yp)r(e)p 1824 3168 V 99 w(Clo)r(c)n(k)f(sp)r(eed)h(/)f(#pro)r(cs)p 2716 3168 V 99 w(Compiler)g(/)g(options)p 3508 3168 V 374 3171 3136 4 v 372 3271 4 100 v 423 3241 a(Alpha)h(EV56)p 977 3271 V 155 w(Compaq)p 1824 3271 V 1009 w(433)e(MHz)p 2716 3271 V 523 w(f77)h(-O5)p 3508 3271 V 372 3370 V 423 3340 a(Alpha)h(EV67)p 977 3370 V 155 w(Compaq)p 1824 3370 V 1009 w(500)e(MHz)p 2716 3370 V 523 w(f77)h(-O5)p 3508 3370 V 372 3470 V 423 3440 a(A)n(thlon)p 977 3470 V 356 w(AMD)p 1824 3470 V 1205 w(1)g(GHz)p 2716 3470 V 548 w(g77)f(-O)p 3508 3470 V 372 3570 V 423 3540 a(LX164)p 977 3570 V 365 w(DCG)p 1824 3570 V 1124 w(533)g(MHz)p 2716 3570 V 507 w(g77)g(-O5)p 3508 3570 V 372 3669 V 423 3639 a(MIPS)i(R10000)p 977 3669 V 97 w(SGI)g(Indigo)p 1824 3669 V 914 w(195)e(MHz)p 2716 3669 V 564 w(f77)h(-O)p 3508 3669 V 372 3769 V 423 3739 a(MIPS)h(R12000)p 977 3769 V 97 w(SGI)g(Octane)p 1824 3769 V 700 w(dual)f(270)f(MHz)p 2716 3769 V 564 w(f77)h(-O)p 3508 3769 V 372 3868 V 423 3839 a(PI)r(I)r(I)p 977 3868 V 454 w(Dell)p 1824 3868 V 1166 w(550)f(MHz)p 2716 3868 V 548 w(g77)g(-O)p 3508 3868 V 372 3968 V 423 3938 a(P4)p 977 3968 V 506 w(Dell)p 1824 3968 V 1223 w(1.5GHz)p 2716 3968 V 547 w(g77)g(-O)p 3508 3968 V 372 4068 V 423 4038 a(P)n(o)n(w)n(er3)p 977 4068 V 340 w(IBM)p 1824 4068 V 963 w(dual)h(200)f(MHz)p 2716 4068 V 581 w(xlf)h(-O)p 3508 4068 V 372 4167 V 423 4137 a(P)n(o)n(w)n(erPC)e(G4)p 977 4167 V 133 w(Apple)p 1824 4167 V 1098 w(450)h(MHz)p 2716 4167 V 548 w(g77)g(-O)p 3508 4167 V 372 4267 V 423 4237 a(UltraSparcI)r(I)p 977 4267 V 147 w(Sun)p 1824 4267 V 969 w(quad)h(296)f(MHz)p 2716 4267 V 564 w(f77)h(-O)p 3508 4267 V 374 4270 3136 4 v 1321 4419 a(T)-7 b(able)27 b(1:)g(List)h(of)g(mac)n(hines)f(used) 374 4615 y(W)-7 b(e)23 b(see)g(from)g(the)h(results)e(that)i(the)f(p)r (erformance)f(of)i(these)f(sparse)f(op)r(erations,)g(in)h(con)n(trast) 374 4714 y(to)e(the)h(dense)f(op)r(erations)f(in)i(for)f(instance)g (the)h(Linpac)n(k)e(b)r(enc)n(hmark,)h(is)g(almost)g(completely)374 4814 y(determined)27 b(b)n(y)h(the)g(qualit)n(y)f(of)g(the)h(memory)f (subsystem.)374 5165 y Fn(8)156 b(Obtaining)36 b(and)j(running)e(the)h (b)s(enc)m(hmark)374 5313 y Fm(The)18 b(b)r(enc)n(hmark)g(co)r(de)g (can)g(b)r(e)h(obtained)f(from)g Fb(http://www.netli)o(b.)o(or)o(g/b)o (en)o(chm)o(ar)o(k/s)o(pa)o(rs)o(ebe)o(nc)o(h)p Fm(.)374 5413 y(The)41 b(pac)n(k)-5 b(age)41 b(con)n(tains)f(F)-7 b(ortran)41 b(co)r(de,)h(and)f(shell)h(scripts)f(for)g(installation)g (and)h(p)r(ost-)3329 5662 y(7)p eop %%Page: 8 8 8 7 bop 374 531 a Fm(pro)r(cessing.)36 b(Results)j(can)e(b)r(e)i(rep)r (orted)f(automatically)f(to)h Fb(sparsebench@cs.u)o(tk)o(.e)o(du)p Fm(,)374 631 y(whic)n(h)27 b(address)f(can)i(also)e(b)r(e)i(used)g(for) f(questions)g(and)g(commen)n(ts.)p 374 750 966 4 v 374 850 4 100 v 418 833 a(Mac)n(hine)p 965 854 4 104 v 287 w(M\015op/s)p 1335 854 V 374 857 966 4 v 374 957 4 100 v 418 940 a(EV67)p 965 957 V 548 w(705)p 1335 957 V 374 1056 V 418 1040 a(P)n(o)n(w)n(er3)p 965 1056 V 486 w(550)p 1335 1056 V 374 1156 V 418 1139 a(P4)p 965 1156 V 652 w(425)p 1335 1156 V 374 1256 V 418 1239 a(EV56)p 965 1256 V 548 w(331)p 1335 1256 V 374 1355 V 418 1339 a(UltraSparcI)r(I)p 965 1355 V 293 w(259)p 1335 1355 V 374 1455 V 418 1438 a(LX164)p 965 1455 V 511 w(233)p 1335 1455 V 374 1555 V 418 1538 a(MIPS)h(R12000)p 965 1555 V 243 w(228)p 1335 1555 V 374 1654 V 418 1638 a(P)n(o)n(w)n(erPC)d(G4)p 965 1654 V 279 w(163)p 1335 1654 V 374 1754 V 418 1737 a(PI)r(I)r(I)p 965 1754 V 600 w(163)p 1335 1754 V 374 1853 V 418 1837 a(A)n(thlon)p 965 1853 V 502 w(163)p 1335 1853 V 374 1953 V 418 1936 a(MIPS)j(R10000)p 965 1953 V 243 w(151)p 1335 1953 V 374 1956 966 4 v 1173 2139 a(T)-7 b(able)27 b(2:)g(Highest)h(attained)g(p)r(erformance)p 374 2308 V 374 2408 4 100 v 418 2391 a(Mac)n(hine)p 965 2412 4 104 v 287 w(M\015op/s)p 1335 2412 V 374 2415 966 4 v 374 2515 4 100 v 418 2498 a(EV67)p 965 2515 V 590 w(86)p 1335 2515 V 374 2614 V 418 2598 a(P4)p 965 2614 V 694 w(73)p 1335 2614 V 374 2714 V 418 2697 a(P)n(o)n(w)n(er3)p 965 2714 V 528 w(68)p 1335 2714 V 374 2814 V 418 2797 a(MIPS)g(R12000)p 965 2814 V 285 w(49)p 1335 2814 V 374 2913 V 418 2897 a(A)n(thlon)p 965 2913 V 544 w(45)p 1335 2913 V 374 3013 V 418 2996 a(UltraSparcI)r(I)p 965 3013 V 335 w(40)p 1335 3013 V 374 3112 V 418 3096 a(LX164)p 965 3112 V 553 w(34)p 1335 3112 V 374 3212 V 418 3195 a(EV56)p 965 3212 V 590 w(34)p 1335 3212 V 374 3312 V 418 3295 a(PI)r(I)r(I)p 965 3312 V 642 w(24)p 1335 3312 V 374 3411 V 418 3395 a(P)n(o)n(w)n(erPC)d(G4)p 965 3411 V 321 w(21)p 1335 3411 V 374 3511 V 418 3494 a(MIPS)j(R10000)p 965 3511 V 285 w(18)p 1335 3511 V 374 3514 966 4 v 480 3697 a(T)-7 b(able)27 b(3:)g(Asymptotic)h(p)r(erformance)f(of)g (Diagonal)g(storage)e(Matrix-v)n(ector)h(pro)r(duct)374 4112 y Fn(References)374 4261 y Fm([1])41 b(Ric)n(hard)k(Barrett,)h (Mic)n(hael)g(Berry)-7 b(,)45 b(T)-7 b(on)n(y)46 b(F.)h(Chan,)f(James)f (Demmel,)j(June)e(Do-)503 4361 y(nato,)h(Jac)n(k)f(Dongarra,)f(Victor)i (Eijkhout,)g(Roldan)g(P)n(ozo,)e(Charles)i(Romine,)g(and)503 4461 y(Henk)64 b(v)-5 b(an)63 b(der)g(V)-7 b(orst.)144 b Fa(T)-7 b(emplates)63 b(for)g(the)h(Solution)g(of)f(Linear)g (Systems:)503 4560 y(Building)e(Blo)r(c)n(ks)f(for)g(Iterativ)n(e)h (Metho)r(ds)p Fm(.)136 b(SIAM,)62 b(Philadelphia)e(P)-7 b(A,)62 b(1994.)503 4660 y Fb(http://www.netli)o(b.)o(or)o(g/t)o(em)o (pla)o(te)o(s/t)o(em)o(pl)o(ate)o(s.)o(ps)p Fm(.)374 4760 y([2])41 b(Jac)n(k)28 b(Dongarra.)41 b(P)n(erformance)28 b(of)i(v)-5 b(arious)28 b(computers)h(using)h(standard)f(linear)g (equa-)503 4859 y(tions)e(soft)n(w)n(are.)35 b(h)n (ttp://www.netlib.org/b)r(enc)n(hmark/p)r(erformance.ps.)374 4959 y([3])41 b(Jac)n(k)20 b(Dongarra)f(and)i(Henk)h(v)-5 b(an)21 b(der)g(V)-7 b(orst.)26 b(P)n(erformance)19 b(of)i(v)-5 b(arious)20 b(computers)h(using)503 5058 y(sparse)f(linear)h(equations) g(soft)n(w)n(are)f(in)h(a)h(fortran)e(en)n(vironmen)n(t.)26 b Fa(Sup)r(ercomputer)p Fm(,)c(1992.)374 5158 y([4])41 b(M.T.)29 b(Jones)g(and)g(P)-7 b(.E.)29 b(Plassmann.)41 b(A)30 b(parallel)e(graph)g(coloring)g(heuristic.)42 b Fa(SIAM)30 b(J.)503 5258 y(Sci.)e(Stat.)g(Comput.)p Fm(,)f(14,)g(1993.)3329 5662 y(8)p eop %%Page: 9 9 9 8 bop 374 539 966 4 v 374 638 4 100 v 418 622 a Fm(Mac)n(hine)p 965 643 4 104 v 287 w(M\015op/s)p 1335 643 V 374 646 966 4 v 374 746 4 100 v 418 729 a(EV67)p 965 746 V 590 w(76)p 1335 746 V 374 845 V 418 829 a(P)n(o)n(w)n(er3)p 965 845 V 528 w(58)p 1335 845 V 374 945 V 418 928 a(P4)p 965 945 V 694 w(46)p 1335 945 V 374 1044 V 418 1028 a(MIPS)28 b(R12000)p 965 1044 V 285 w(39)p 1335 1044 V 374 1144 V 418 1127 a(A)n(thlon)p 965 1144 V 544 w(34)p 1335 1144 V 374 1244 V 418 1227 a(EV56)p 965 1244 V 590 w(28)p 1335 1244 V 374 1343 V 418 1327 a(LX164)p 965 1343 V 553 w(24)p 1335 1343 V 374 1443 V 418 1426 a(PI)r(I)r(I)p 965 1443 V 642 w(22)p 1335 1443 V 374 1543 V 418 1526 a(UltraSparcI)r(I)p 965 1543 V 335 w(18)p 1335 1543 V 374 1642 V 418 1626 a(MIPS)g(R10000)p 965 1642 V 285 w(16)p 1335 1642 V 374 1742 V 418 1725 a(P)n(o)n(w)n(erPC)d(G4)p 965 1742 V 362 w(9)p 1335 1742 V 374 1745 966 4 v 374 1928 a(T)-7 b(able)26 b(4:)g(Asymptotic)h(p)r(erformance)e(of)i (Symmetrically)f(stored)g(CRS)h(Matrix-v)n(ector)d(pro-)374 2027 y(duc)p 374 2272 V 374 2371 4 100 v 418 2355 a(Mac)n(hine)p 965 2375 4 104 v 287 w(M\015op/s)p 1335 2375 V 374 2379 966 4 v 374 2478 4 100 v 418 2462 a(P4)p 965 2478 V 694 w(97)p 1335 2478 V 374 2578 V 418 2561 a(EV67)p 965 2578 V 590 w(96)p 1335 2578 V 374 2678 V 418 2661 a(MIPS)k(R12000)p 965 2678 V 285 w(53)p 1335 2678 V 374 2777 V 418 2761 a(A)n(thlon)p 965 2777 V 544 w(39)p 1335 2777 V 374 2877 V 418 2860 a(LX164)p 965 2877 V 553 w(28)p 1335 2877 V 374 2976 V 418 2960 a(EV56)p 965 2976 V 590 w(28)p 1335 2976 V 374 3076 V 418 3059 a(UltraSparcI)r(I)p 965 3076 V 335 w(27)p 1335 3076 V 374 3176 V 418 3159 a(PI)r(I)r(I)p 965 3176 V 642 w(27)p 1335 3176 V 374 3275 V 418 3259 a(P)n(o)n(w)n(erPC)d(G4)p 965 3275 V 321 w(19)p 1335 3275 V 374 3375 V 418 3358 a(MIPS)j(R10000)p 965 3375 V 285 w(19)p 1335 3375 V 374 3475 V 418 3458 a(P)n(o)n(w)n(er3)p 965 3475 V 528 w(14)p 1335 3475 V 374 3478 966 4 v 700 3660 a(T)-7 b(able)28 b(5:)f(Asymptotic)h(p)r(erformance)e(of)i(CRS)g (Matrix-v)n(ector)d(pro)r(duct)p 374 3921 V 374 4020 4 100 v 418 4004 a(Mac)n(hine)p 965 4025 4 104 v 287 w(M\015op/s)p 1335 4025 V 374 4028 966 4 v 374 4127 4 100 v 418 4111 a(EV67)p 965 4127 V 590 w(86)p 1335 4127 V 374 4227 V 418 4210 a(MIPS)j(R12000)p 965 4227 V 285 w(41)p 1335 4227 V 374 4327 V 418 4310 a(A)n(thlon)p 965 4327 V 544 w(34)p 1335 4327 V 374 4426 V 418 4410 a(LX164)p 965 4426 V 553 w(29)p 1335 4426 V 374 4526 V 418 4509 a(EV56)p 965 4526 V 590 w(28)p 1335 4526 V 374 4626 V 418 4609 a(P4)p 965 4626 V 694 w(24)p 1335 4626 V 374 4725 V 418 4709 a(P)n(o)n(w)n(er3)p 965 4725 V 528 w(21)p 1335 4725 V 374 4825 V 418 4808 a(PI)r(I)r(I)p 965 4825 V 642 w(19)p 1335 4825 V 374 4924 V 418 4908 a(P)n(o)n(w)n(erPC)d(G4)p 965 4924 V 321 w(13)p 1335 4924 V 374 5024 V 418 5008 a(MIPS)j(R10000)p 965 5024 V 326 w(9)p 1335 5024 V 374 5124 V 418 5107 a(UltraSparcI)r(I)p 965 5124 V 376 w(7)p 1335 5124 V 374 5127 966 4 v 711 5310 a(T)-7 b(able)27 b(6:)h(Asymptotic)g(p)r(erformance)e(of)i (Diagonal)e(storage)g(ILU)h(solv)n(e)3329 5662 y(9)p eop %%Page: 10 10 10 9 bop 374 553 966 4 v 374 652 4 100 v 418 636 a Fm(Mac)n(hine)p 965 657 4 104 v 287 w(M\015op/s)p 1335 657 V 374 660 966 4 v 374 759 4 100 v 418 743 a(P4)p 965 759 V 694 w(70)p 1335 759 V 374 859 V 418 842 a(EV67)p 965 859 V 590 w(69)p 1335 859 V 374 959 V 418 942 a(P)n(o)n(w)n(er3)p 965 959 V 528 w(57)p 1335 959 V 374 1058 V 418 1042 a(A)n(thlon)p 965 1058 V 544 w(31)p 1335 1058 V 374 1158 V 418 1141 a(MIPS)28 b(R12000)p 965 1158 V 285 w(26)p 1335 1158 V 374 1258 V 418 1241 a(LX164)p 965 1258 V 553 w(26)p 1335 1258 V 374 1357 V 418 1341 a(EV56)p 965 1357 V 590 w(26)p 1335 1357 V 374 1457 V 418 1440 a(PI)r(I)r(I)p 965 1457 V 642 w(21)p 1335 1457 V 374 1556 V 418 1540 a(P)n(o)n(w)n(erPC)d(G4)p 965 1556 V 321 w(19)p 1335 1556 V 374 1656 V 418 1640 a(UltraSparcI)r(I)p 965 1656 V 335 w(17)p 1335 1656 V 374 1756 V 418 1739 a(MIPS)j(R10000)p 965 1756 V 285 w(10)p 1335 1756 V 374 1759 966 4 v 532 1942 a(T)-7 b(able)28 b(7:)f(Asymptotic)h(p)r(erformance)e(of)i (Symmetrically)f(stored)g(CRS)g(ILU)h(solv)n(e)p 374 2230 V 374 2329 4 100 v 418 2313 a(Mac)n(hine)p 965 2334 4 104 v 287 w(M\015op/s)p 1335 2334 V 374 2337 966 4 v 374 2437 4 100 v 418 2420 a(P4)p 965 2437 V 694 w(86)p 1335 2437 V 374 2536 V 418 2520 a(EV67)p 965 2536 V 590 w(48)p 1335 2536 V 374 2636 V 418 2619 a(P)n(o)n(w)n(er3)p 965 2636 V 528 w(45)p 1335 2636 V 374 2735 V 418 2719 a(A)n(thlon)p 965 2735 V 544 w(21)p 1335 2735 V 374 2835 V 418 2818 a(MIPS)g(R12000)p 965 2835 V 285 w(18)p 1335 2835 V 374 2935 V 418 2918 a(LX164)p 965 2935 V 553 w(16)p 1335 2935 V 374 3034 V 418 3018 a(EV56)p 965 3034 V 590 w(15)p 1335 3034 V 374 3134 V 418 3117 a(PI)r(I)r(I)p 965 3134 V 642 w(13)p 1335 3134 V 374 3234 V 418 3217 a(UltraSparcI)r(I)p 965 3234 V 376 w(8)p 1335 3234 V 374 3333 V 418 3317 a(MIPS)g(R10000)p 965 3333 V 326 w(6)p 1335 3333 V 374 3433 V 418 3416 a(P)n(o)n(w)n(erPC)d(G4)p 965 3433 V 362 w(5)p 1335 3433 V 374 3436 966 4 v 932 3619 a(T)-7 b(able)27 b(8:)g(Asymptotic)h(p)r(erformance)f(of)g(CRS)h (ILU)g(solv)n(e)p 374 3907 V 374 4006 4 100 v 418 3990 a(Mac)n(hine)p 965 4011 4 104 v 287 w(M\015op/s)p 1335 4011 V 374 4014 966 4 v 374 4114 4 100 v 418 4097 a(EV67)p 965 4114 V 548 w(201)p 1335 4114 V 374 4213 V 418 4197 a(P)n(o)n(w)n(er3)p 965 4213 V 486 w(113)p 1335 4213 V 374 4313 V 418 4296 a(MIPS)g(R12000)p 965 4313 V 243 w(113)p 1335 4313 V 374 4412 V 418 4396 a(P4)p 965 4412 V 694 w(79)p 1335 4412 V 374 4512 V 418 4495 a(EV56)p 965 4512 V 590 w(65)p 1335 4512 V 374 4612 V 418 4595 a(MIPS)g(R10000)p 965 4612 V 285 w(58)p 1335 4612 V 374 4711 V 418 4695 a(UltraSparcI)r(I)p 965 4711 V 335 w(47)p 1335 4711 V 374 4811 V 418 4794 a(PI)r(I)r(I)p 965 4811 V 642 w(44)p 1335 4811 V 374 4911 V 418 4894 a(LX164)p 965 4911 V 553 w(41)p 1335 4911 V 374 5010 V 418 4994 a(P)n(o)n(w)n(erPC)d(G4)p 965 5010 V 321 w(26)p 1335 5010 V 374 5110 V 418 5093 a(A)n(thlon)p 965 5110 V 544 w(10)p 1335 5110 V 374 5113 966 4 v 758 5296 a(T)-7 b(able)28 b(9:)f(Asymptotic)h(p)r(erformance)e(of)i(V)-7 b(ector)27 b(op)r(erations)f(in)i(CG)3288 5662 y(10)p eop %%Page: 11 11 11 10 bop 374 2230 966 4 v 374 2329 4 100 v 418 2313 a Fm(Mac)n(hine)p 965 2334 4 104 v 287 w(M\015op/s)p 1335 2334 V 374 2337 966 4 v 374 2437 4 100 v 418 2420 a(EV67)p 965 2437 V 548 w(106)p 1335 2437 V 374 2536 V 418 2520 a(MIPS)28 b(R12000)p 965 2536 V 285 w(65)p 1335 2536 V 374 2636 V 418 2619 a(P)n(o)n(w)n(er3)p 965 2636 V 528 w(53)p 1335 2636 V 374 2735 V 418 2719 a(P4)p 965 2735 V 694 w(51)p 1335 2735 V 374 2835 V 418 2818 a(LX164)p 965 2835 V 553 w(33)p 1335 2835 V 374 2935 V 418 2918 a(EV56)p 965 2935 V 590 w(32)p 1335 2935 V 374 3034 V 418 3018 a(A)n(thlon)p 965 3034 V 544 w(30)p 1335 3034 V 374 3134 V 418 3117 a(PI)r(I)r(I)p 965 3134 V 642 w(18)p 1335 3134 V 374 3234 V 418 3217 a(UltraSparcI)r(I)p 965 3234 V 335 w(16)p 1335 3234 V 374 3333 V 418 3317 a(P)n(o)n(w)n(erPC)d(G4)p 965 3333 V 321 w(12)p 1335 3333 V 374 3433 V 418 3416 a(MIPS)j(R10000)p 965 3433 V 285 w(12)p 1335 3433 V 374 3436 966 4 v 531 3619 a(T)-7 b(able)27 b(10:)g(Asymptotic)h(p)r(erformance)e(of)i(Diagonal)e (storage)g(Blo)r(c)n(k)g(Jacobi)h(solv)n(e)3288 5662 y(11)p eop %%Trailer end userdict /end-hook known{end-hook}if %%EOF .