%-12345X@PJL ENTER LANGUAGE = POSTSCRIPT %!PS-Adobe %%BeginProlog /wpdict 300 dict def wpdict begin /d{bind def}bind def/l{load def}d/ec{exec def}d/cp/closepath l/cup/currentpoint l/cs/currentscreen l /cv/curveto l/drx{dtransform round x round x}d/f/eofill l/g/setgray l/gr/grestore l /gs/gsave l/ife{ifelse}d/ix/index l/li/lineto l/lc/setlinecap l /lj/setlinejoin l/m/moveto l/mx/matrix l/mcm{mx currentmatrix}d/sm/setmatrix l /np/newpath l/p/pop l/re/rotate l/rh/readhexstring l/rl/rlineto l/rm/rmoveto l/rs/restore l /setfl{dup 1 le{p 1 setflat}{setflat}ife}def/languagelevel where{p languagelevel}{1}ife 2 lt{/sf{bzcnt 70 div setfl}d/fpath{bzcnt 4 div setflat}d}{/sf{}d/fpath{}d}ife /cf currentflat def/s{fpath flattenpath stroke}d/sc/scale l /sd/setdash l/ss/setscreen l/sv/save l/tr/translate l /w/setlinewidth l/x/exch l/xd{x def}d/c{3{255 div 3 1 roll}repeat setrgbcolor}d /bF false def/bF2 false def/bf 0 def/ds{gs 1 lc s gr}d/gd{255 div g}d /h{0 rm}d /lp{px li}d/mp{px m}d/nb 50 string def/osv 0 def/icl/initclip l/pf{gs f gr}def /pff{gs fill gr}def/pl{{px li}repeat}d/ps{gs s gr}def/plen 0 def/pwid 0 def /px{transform .25 sub round .25 add x .25 sub round .25 add x itransform}d /pxd{drx idtransform}d/rlp{pxd rl}d/rmp{pxd rm}d/_g{g}d/_lr{rlp}d/_s{s}d /_w{w}d/_m{mp}d/_rmxy{rmp}d/bzcnt 0 def/bzct{/bzcnt xd}def /bzcl{/bzcnt 0 def cf setflat}def/rF false def/sF false def/pth 0 def/ptw 0 def/pths 0 def/ptws 0 def/PColor 0 def /instpat 0 def/cm 0 def/slan 0 def/hscl 0 def/psz 0 def/xres 0 def/yres 0 def/pstr 0 def/lutb 0 def /rot 0 def/mir 0 def/HTd 0 def/WDd 0 def/ury 0 def/llx 0 def/lly 0 def/exstr 0 def/HTs 0 def/WDs 0 def /Hs 0 def/Ws 0 def/imc 0 def/Bdep 0 def/clu 0 def/curx 0 def/cury 0 def/Sx 0 def/Sy 0 def/xpos 0 def /ypos 0 def/lw 0 def/DUy 0 def/DUx 0 def/Ux 0 def/Uy 0 def/cml 0 def /cp3{3 copy}d/cp4{4 copy}d/cp6{6 copy}d/aosh{cp3 -4 -4 rm gs ashow gr cp3 4 0 rm gs ashow gr cp3 4 0 rm gs ashow gr cp3 0 4 rm gs ashow gr cp3 0 4 rm gs ashow gr cp3 -4 0 rm gs ashow gr cp3 -4 0 rm gs ashow gr cp3 0 -4 rm gs ashow gr currentrgbcolor 6 3 roll 1 g 4 0 rm ashow setrgbcolor}d /wosh{cp4 -4 -4 rm gs widthshow gr cp4 4 0 rm gs widthshow gr cp4 4 0 rm gs widthshow gr cp4 0 4 rm gs widthshow gr cp4 0 4 rm gs widthshow gr cp4 -4 0 rm gs widthshow gr cp4 -4 0 rm gs widthshow gr cp4 0 -4 rm gs widthshow gr currentrgbcolor 7 3 roll 1 g 4 0 rm widthshow setrgbcolor}d /awosh{cp6 -4 -4 rm gs awidthshow gr cp6 4 0 rm gs awidthshow gr cp6 4 0 rm gs awidthshow gr cp6 0 4 rm gs awidthshow gr cp6 0 4 rm gs awidthshow gr cp6 -4 0 rm gs awidthshow gr cp6 -4 0 rm gs awidthshow gr cp6 0 -4 rm gs awidthshow gr currentrgbcolor 9 3 roll 1 g 4 0 rm awidthshow setrgbcolor}d /assh{sv gs psz 20 div dup neg rm 4 1 roll cp3 ashow 4 -1 roll gr cp3 sv x currentfont/PaintType known {bf setfont}if 1 g ashow rs currentfont/PaintType known{currentfont mo setfont ashow}{aosh}ife cup 3 -1 roll rs m}d /wssh{sv gs psz 20 div dup neg rm 5 1 roll cp4 widthshow gr cp4 sv currentfont/PaintType known{bf setfont}if 1 g 5 1 roll widthshow rs currentfont/PaintType known{currentfont mo setfont widthshow}{wosh}ife cup 3 -1 roll rs m}d /awssh{sv gs psz 20 div dup neg rm 7 1 roll cp6 awidthshow gr cp6 sv x currentfont/PaintType known{bf setfont}if 1 g 7 1 roll awidthshow rs currentfont/PaintType known{currentfont mo setfont awidthshow}{awosh}ife cup 3 -1 roll rs m}d /B{/bF true def sF not{/S/bsh l/bF2 true def}if}d /b{/bF false def bF2{/S/show l/bF2 false def}if}d /bd{sv}d/bp{sv .06 .06 sc 0 0 m}d/bsh{gs psz 30 div 0 rm dup show gr show}d /clr{rF{6 3 roll p p p}{eq3{p p gd}{c}ife}ife}d/co{/pwid xd/plen xd osv 1 eq{0 pwid tr -90 re}if osv 2 eq{pwid plen tr 180 re}if osv 3 eq{plen 0 tr 90 re}if dup 1 eq{pwid 0 tr 90 re}if dup 2 eq{pwid plen tr 180 re}if dup 3 eq{0 plen tr -90 re}if/osv xd}d /cw{s initclip m 0 2 ix rl 0 rl 0 x neg rl clip np}d /DU{cup/DUy xd/DUx xd}d/du{gs sv 12 w cup -24 add m DUx DUy -24 add li s rs 12 w cup -48 add m DUx DUy -48 add li s gr}d/ed{rs}d/ep{rs showpage 0 0 m}d /eq3{3 copy 2 ix eq{eq{true}{false}ife}{p p false}ife}d /ff{x rc x 3 div dup/psz xd scalefont dup/bf xd setfont}d /ffs{/slan x 10 div def/hscl x 1000 div def/psz x 3 div def [psz hscl mul 0 slan dup sin x cos div psz mul psz 0 0] x rc x makefont dup/bf xd setfont}d/fr{72 0 rmtx defaultmatrix dtransform /yres xd/xres xd xres dup mul yres dup mul add sqrt}d /is{sv 4 1 roll dup/pstr x 7 add 8 idiv string def 3 1 roll tr dup 1 sc dup 1 1[5 -1 roll 0 0 1 0 0]{currentfile pstr rh p} cml 0 eq{image}{false 3 colorimage}ife rs}d/cexp{exstr 0 lutb 3 copy 7 -1 roll {get putinterval x 3 add x 3 copy}forall p p p p p}d/bwexp{dup 0 lutb 3 copy 7 -1 roll {get put x 1 add x 3 copy}forall p p p p p}d/NOM 0 def/INX 1 def/INY 2 def /p1x 0 def/p1y 0 def/p2x 0 def/p2y 0 def/p3x 0 def/p3y 0 def /idef{/p3y xd/p3x xd/p2y xd/p2x xd/p1y xd/p1x xd /rot xd/mir xd p3x p1x sub 1 add dup mul p1y p3y sub 1 add dup mul add sqrt/HTd xd p2y p1y sub 1 add dup mul p2x p1x sub 1 add dup mul add sqrt/WDd xd}def /mirror{mir NOM eq{Ws Hs sc}{mir INX eq{Ws neg Hs sc} {mir INY eq{Ws Hs neg sc}{Ws neg Hs neg sc}ife}ife}ife}def /ic{sv 6 1 roll tr 2 ix 2 ix sc[3 ix 0 0 5 ix neg 0 7 ix] 2 1 roll true 3 1 roll imagemask rs}d/ieps{/ury xd/urx xd/lly xd/llx xd idef ury lly sub/HTs xd urx llx sub/WDs xd WDd WDs div/Ws xd HTd HTs div/Hs xd p3x p3y tr rot re mirror llx neg lly neg tr}def /im{sv 15 1 roll dup/pstr x string def/exstr x 3 mul string def /HTs xd/WDs xd/imc xd/Bdep xd/clu xd idef p1x p1y m cup transform/cury xd/curx xd rot re /Ws WDd def/Hs HTd def mirror curx cury itransform tr WDs HTs Bdep [WDs 0 0 HTs neg 0 0]{currentfile pstr rh p clu 1 eq{cexp}if clu 2 eq{bwexp}if} imc 0 eq{image}{false 3 colorimage}ife rs}d /kp{initclip clip np}d/l1{cup osv plen pwid 6 -1 roll rs sv}d /l2{bp 7 2 roll co m}d/osh{dup -4 -4 rm gs show gr dup 4 0 rm gs show gr dup 4 0 rm gs show gr dup 0 4 rm gs show gr dup 0 4 rm gs show gr dup -4 0 rm gs show gr dup -4 0 rm gs show gr dup 0 -4 rm gs show gr currentrgbcolor 4 3 roll 1 g 4 0 rm show setrgbcolor}d /mo{dup/OutlineFlag known not{dup dup length 2 add dict begin {1 ix/FID ne{def}{p p}ife}forall/UniqueID known{/UniqueID UniqueID 10000 add def}if /PaintType PaintType 0 eq{2}{PaintType}ife def/StrokeWidth 15 def/OutlineFlag true def /OutlineFont currentdict end definefont}if}d/O{currentfont/PaintType known{currentfont mo setfont}{/S/osh l}ife}d /o{currentfont/PaintType known{bf setfont}{/S/show l}ife}d/R{/rF true def currentrgbcolor 1 .25 .25 setrgbcolor}d /r{/rF false def eq3{1 sub neg gd p p}{setrgbcolor}ife}d/rc{dup FontDirectory x known{findfont} {dup nb cvs dup length 1 sub get 82 eq{dup nb cvs dup length 1 sub 0 x getinterval findfont begin currentdict dup length dict begin {1 ix/FID ne{def}{p p}ife}forall/FontName xd/Encoding WPen def currentdict dup end end/FontName get x definefont} {findfont}ife}ife}d/rmtx mx def/S/show l/A/ashow l/W/widthshow l/AW/awidthshow l/sg{neg 100 add 100 div g}d/SH{bF2{/bF2 false def}if/S/ssh l/A/assh l/W/wssh l/AW/awssh l/sF true def}d /sh{/S/show l/A/ashow l/W/widthshow l/AW/awidthshow l/sF false def bF{B}if}d/sp{gs s gr}d/ssh{sv x gs psz 20 div dup neg rm dup show gr dup sv x currentfont/PaintType known{bf setfont}if 1 g show rs currentfont/PaintType known{currentfont mo setfont show}{osh}ife cup 3 -1 roll rs m}d/ST{cup/Sy xd/Sx xd}d /st{gs cup psz 4 div add mp Sx Sy psz 4 div add lp 10 w s gr}d /U{cup/Uy xd/Ux xd}d/u{gs cup -24 add m Ux Uy -24 add li 12 w s gr}d /ul{cup osv plen pwid 7 -2 roll rs rs bp 6 1 roll co m}d/WPen StandardEncoding 256 array copy def 0 [127/Aacute/Acircumflex/Adieresis/Agrave/Aring/Atilde/Ccedilla /Delta/Eacute/Ecircumflex/Edieresis/Egrave/Eth/Gamma/Iacute/Icircumflex/Idieresis/Igrave/Lambda/Ntilde/Oacute /Ocircumflex/Odieresis/Ograve/Omega/Otilde/Phi/Pi/Psi/Scaron/Sigma/TeXtext32/Theta/Thorn 176/Pts 181/dbar 190/Hbar 192/hbar 201/Ldot 204/ldot 209/Uacute/Ucircumflex/Udieresis/Ugrave/Upsilon/Xi/Yacute /Ydieresis/Zcaron/aacute/acircumflex/adieresis/agrave/aring/atilde/brokenbar 226/approxequal 228/ccedilla/copyright/degree/divide 236/dotlessj/eacute/ecircumflex/edieresis/egrave 242/eth/ff/ffi 246/ffl/iacute 252/icircumflex/idieresis/igrave/logicalnot 1/minus/mu/multiply/ntilde/oacute/ocircumflex/odieresis/ograve/onehalf/onequarter/onesuperior/otilde/plusminus /registered/scaron/thorn/threequarters/threesuperior/trademark/twosuperior/uacute/ucircumflex/udieresis /ugrave/yacute/ydieresis/zcaron/IJ/ij/Eng/eng ]{dup type/nametype eq{WPen 2 ix 2 ix put p 1 add}{x p}ife}forall p/URy 0 def/URx 0 def/LLy 0 def/LLx 0 def/dxcg 0 def/dx1 0 def/dx2 0 def/dx3 0 def /cgray 0 def/curstep -1 def/dis 0 def/steps 0 def/gsteps 0 def/grot 0 def/gtype 0 def/ry 0 def /rx 0 def/botg 0 def/topg 0 def/bgc 0 def/tgc 0 def/cgc 0 def /extents{fpath flattenpath pathbbox/URy xd/URx xd/LLy xd/LLx xd}def /dxcolor{cml 0 eq{cgray dxcg sub dup/cgray xd curstep -1 eq{g} {/curstep curstep 1 sub def curstep 1 eq{p botg gd}{g}ife}ife} {cgc aload p dx3 sub 3 1 roll dx2 sub 3 1 roll dx1 sub 3 1 roll 3 array astore/cgc xd cgc aload p setrgbcolor}ife}d/box{LLx LLy m URx LLy li URx URy li LLx URy li cp s}def /calcdx{sub gsteps 1 sub div 255 div}def /computegdx{topg botg calcdx/dxcg xd}def/computeRGBdx{mark tgc aload p bgc aload p 3 ix 1 ix calcdx/dx3 xd 4 ix 2 ix calcdx/dx2 xd 5 ix 3 ix calcdx/dx1 xd cleartomark}def /ccdx{cml 0 eq{computegdx}{computeRGBdx}ife}def/stclr{cml 0 eq{topg gd/cgray currentgray def} {tgc aload p c currentrgbcolor 3 array astore/cgc xd}ife}def/lgf{/steps gsteps def ry 1 ne{stclr/gf{add}def/top URy LLy sub ry mul LLy add def /lw URy top sub steps .5 sub div def lgfdo}if stclr/gf{sub}def ry 1 ne{/lw top LLy sub steps .5 sub div def}if lgfdo}def /lgfdo{ry 1 ne{/center top def lw 2 div w LLx center lw 4 div gf m URx center lw 4 div gf li s /center center lw gf def LLx center m dxcolor} {/lw URy LLy sub steps div def/top URy lw 2 div sub def /center top def LLx top m/steps steps 1 add def}ife lw w steps 1 sub dup/curstep xd{URx center li s center lw gf/center xd LLx center m dxcolor}repeat/curstep -1 def}def/sgf{/steps gsteps .5 sub def /midx URx LLx sub 1 rx sub mul def/midy URy LLy sub ry mul def /width URx LLx sub def/dx width midx sub steps div def /height URy LLy sub def/dy height midy sub steps div def /dw width steps div def/dl height steps div def width w stclr/xpos LLx def/ypos URy def/lw width def/lh height def gsteps{xpos lw 2 div add ypos m xpos lw 2 div add ypos lh sub li s/lw lw dw sub def/lh lh dl sub def/xpos xpos dx add def/ypos ypos dy sub def lw w dxcolor}repeat/curstep -1 def}def /dfc{dup mul x dup mul add sqrt dup dis gt{/dis xd}{p}ife}def /fdis{URx LLx sub rx mul LLx add/midx xd URy LLy sub ry mul LLy add/midy xd /width URx LLx sub def/gcx width rx mul def/height URy LLy sub def/gcy height ry mul def gcx gcy dfc width gcx sub gcy dfc width gcx sub height gcy sub dfc gcx height gcy sub dfc}def/rgf{/steps gsteps def fdis/lw dis steps .5 sub div def/radius lw def lw 2 div w stclr midx lw 2 div sub midy m midx midy radius 2 div 0 361 arc s lw w steps 1 sub dup/curstep xd/curstep curstep 1 add def {dxcolor midx midy radius 0 361 arc s/radius radius lw add def}repeat/curstep -1 def}def /gf{fpath flattenpath/gsteps xd/grot xd/gtype xd/ry x 100 div def/rx x 100 div def cml 0 eq{gtype 1 eq{x}if/botg xd/topg xd}{gtype 1 eq{6 3 roll}if 3 array astore/bgc xd 3 array astore/tgc xd}ife sv[]0 sd eoclip gsteps 1 eq {stclr f}{mcm 3 get 0 gt{/grot grot 180 add def}if grot re extents gsteps 0 eq{csteps}if ccdx gtype 0 eq {lgf}{gtype 1 eq{sgf}{rgf}ife}ife}ife rs}d/csteps{fdis dis 72 div fr mul cs p p dup xres eq{p p/gsteps xres def}{div/gsteps x round cvi dup 1 le{p 2}if def}ife}def /ssf{dup 0 eq{p}{cs 3 ix 3 1 roll ss p p}ife}d/ssa{cs 4 1 roll p 1 ix 4 -1 roll ss p}d /invalidcolortable? true def /PATmp{x dup length 2 add dict copy begin currentdict/Multi known not{/Multi 1 def}if Multi 1 ne{/UserProc/PaintProc load def /PaintProc{begin 0 1 Multi 1 sub{PaintColors 1 index get PATsc PaintData x get gs currentdict UserProc gr}for end}d }if currentdict end x makepattern }d/PATDict 3 dict def/PATsc{mark x aload p counttomark 1 eq{gd}if counttomark 3 eq{c}if cleartomark}d/PATsp{PATDict begin/CColor[currentcolor]def /CCSpace currentcolorspace def end dup/PaintType get 2 eq{x dup length dup 1 eq{[/Pattern/DeviceGray]setcolorspace}if dup 3 eq{[/Pattern/DeviceRGB]setcolorspace}if 4 eq{[/Pattern/DeviceCMYK]setcolorspace}if aload length 1 add -1 roll}if setpattern}d/PATusp{PATDict begin CCSpace setcolorspace CColor aload p setcolor end p}d /pdictt 20 dict def pdictt begin/dummy null def/PaintType 1 def/PatternType 1 def/TilingType 2 def/BBox[0 0 1 1]def /XStep 1 def/YStep 1 def/Multi 2 def/PaintData[{0 0 m 0 1 rl 1 0 rl 0 -1 rl cp PaintColors 0 get aload p null ne{f}if p p} {ptw pth true[ptw 0 0 pth neg 0 ptw]{Bitmap}imagemask}]def /PaintProc{begin exec end}d end/makedict{pdictt 20 dict copy dup begin x/Bitmap xd x/PaintColors xd gs initmatrix 1 1 drx idtransform sc [ptws 0 0 pths 0 0]PATmp gr end}d /setpat{/pth xd/ptw xd/pths xd/ptws xd makedict/instpat xd instpat PATsp}d/unsetpat{instpat PATusp}d /myappcolorspace/DeviceRGB def/rgbclut 0 def /doclutimage{/rgbclut xd p bpc dup 8 eq{p 255}{4 eq{15}{3}ife} ife/hival xd[/Indexed myappcolorspace hival rgbclut]setcolorspace myimagedict dup begin/Width iw def/Height ih def/Decode[0 hival]def/ImageMatrix[1 0 0 -1 0 ih]def /DataSource setupimageproc def/BitsPerComponent bpc def /Interpolate smoothflag def end image}d/do24image{myappcolorspace setcolorspace myimagedict dup begin/Width iw def/Height ih def/Decode[0 1 0 1 0 1]def/ImageMatrix[1 0 0 -1 0 ih]def /DataSource setupimageproc def/BitsPerComponent 8 def/Interpolate smoothflag def end image}d/setup1asciiproc{[currentfile mystring/rh cvx/p cvx]cvx bind}d /setup1binaryproc{[currentfile mystring/readstring cvx/p cvx]cvx bind}d /setup2asciiproc{currentfile/ASCII85Decode filter/RunLengthDecode filter}d /setup2binaryproc{currentfile/ASCIIHexDecode filter/RunLengthDecode filter}d /myimagedict 16 dict dup begin/ImageType 1 def/MultipleDataSource false def end def /im_save 0 def/setupimageproc 0 def/polarity 0 def/smoothflag 0 def/mystring 0 def /bpc 0 def/ih 0 def/iw 0 def/beginimage{/im_save sv def dup 2 eq{p/setup2binaryproc}{dup 3 eq{p/setup2asciiproc} {0 eq{/setup1binaryproc}{/setup1asciiproc}ife}ife}ife /setupimageproc x l{[1 0]}{[0 1]}ife/polarity xd/smoothflag xd tr sc/mystring x string def/bpc xd/ih xd/iw xd}d/endimage{im_save rs np}d/1bitbwcopyimage{1 g 0 0 m 0 1 rl 1 0 rl 0 -1 rl cp fill 0 g myimagedict dup begin/Width iw def/Height ih def/Decode polarity def /ImageMatrix[1 0 0 -1 0 ih]def/DataSource setupimageproc def /BitsPerComponent 1 def/Interpolate smoothflag def end imagemask}d/1bitcopyimage{ssc 0 0 m 0 1 rl 1 0 rl 0 -1 rl cp fill ssc myimagedict dup begin/Width iw def/Height ih def /Decode polarity def/ImageMatrix[1 0 0 -1 0 ih]def /DataSource setupimageproc def/BitsPerComponent 1 def/Interpolate smoothflag def end imagemask}d/1bitmaskimage{ssc myimagedict dup begin/Width iw def/Height ih def/Decode polarity def /ImageMatrix[1 0 0 -1 0 ih]def/DataSource setupimageproc def /BitsPerComponent 1 def/Interpolate smoothflag def end imagemask}d /BeginEPSF{end userdict begin/showpage{}def /b4 sv def/d_cnt countdictstack def/op_cnt count 1 sub def 0 setgray 0 setlinecap 1 setlinewidth 0 setlinejoin 10 setmiterlimit[]0 setdash newpath/languagelevel where{p languagelevel 1 ne {false setstrokeadjust false setoverprint}if}if}d end userdict begin/EndEPSF{count op_cnt sub{pop}repeat countdictstack d_cnt sub{end}repeat b4 end restore wpdict begin}bind def end %%EndProlog /#copies 1 def wpdict begin bd /cml 1 def %%Page: 1 1 <>setpagedevice bp 0 13200 10200 co /CourierR 600 ff 0 13200 10200 co 5040 1263 m (1)S 1411 11768 m /NewCenturySchlbk-BoldR 900 ff 14 0 32 (An AMD Preprocessor For Matrices With Some)W 3030 11336 m 14 0 32 (Dense Rows and Columns.)W /NewCenturySchlbk-RomanR 699 ff 4074 10610 m /NewCenturySchlbk-ItalicR 699 ff 13 0 32 (Joseph L. Carmen)W 13 0 32 ( )W 1362 9920 m /NewCenturySchlbk-RomanR 699 ff 13 0 32 (Department of Computer and Information Sciences and Engineering)W 2691 9575 m 13 0 32 (University of Florida, Gainesville, FL 32611)W 4582 8886 m /NewCenturySchlbk-BoldR 699 ff (Abstract)S /NewCenturySchlbk-RomanR 699 ff 1200 8195 m -3 0 (A)A 14 0 32 -3 0 ( preprocessor )AW 13 0 32 -3 0 (for the Approximate Minimum Degree ordering algorithm)AW 1200 7850 m 13 0 32 -1 0 (\(AMD\) is presented. The primary goal )AW 13 0 32 (of preprocessing is to reduce the)W 1200 7505 m 1 0 (orde)A (ring)S 32 0 32 ( time of AMD on large sparse matrices with some very dense)W 1200 7160 m 1 0 (rows)A 63 0 32 1 0 ( a)AW 63 0 32 (nd columns. We show that with preprocessing, matrices that)W 1200 6815 m -3 0 (normally)A 6 0 32 -3 0 ( require large amounts of ordering )AW 7 0 32 -3 0 (time can be done significantly)AW 1200 6470 m 13 0 32 (faster. )W 3673 5781 m /NewCenturySchlbk-BoldR 699 ff 11 0 32 (Keywords and Phrases.)W /NewCenturySchlbk-RomanR 699 ff 1200 5435 m 1 0 (ap)A (proximate)S 91 0 32 ( minimum degree ordering algorithm, sparse matrices,)W 1200 5090 m 13 0 32 (preprocessing algorithms.)W ep %%Page: 2 2 bp /NewCenturySchlbk-BoldR 600 ff 0 13200 10200 co mcm 3720 8020 tr 1 -1 sc np 0 0 m 15 0 li 15 1907 li 0 1907 li cp 0 255 div g [] 0 sd 15 w 0 lj 0 lc fill np 0 0 m 2339 0 li 2339 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 6060 8020 tr 1 -1 sc np 0 0 m 15 0 li 15 1907 li 0 1907 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 417 0 li 417 15 li 0 15 li cp 0 255 div g fill np 402 0 m 417 0 li 417 1907 li 402 1907 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 3720 6112 tr 1 -1 sc np 0 0 m 15 0 li 15 421 li 0 421 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 2339 0 li 2339 15 li 0 15 li cp 0 255 div g fill np 0 406 m 2339 406 li 2339 421 li 0 421 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 6060 6112 tr 1 -1 sc np 0 0 m 15 0 li 15 421 li 0 421 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 417 0 li 417 15 li 0 15 li cp 0 255 div g fill np 402 0 m 417 0 li 417 421 li 402 421 li cp 0 255 div g fill np 0 406 m 417 406 li 417 421 li 0 421 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 7860 10486 tr 1 -1 sc sm icl mcm 7960 10386 tr 1 -1 sc mcm -126.0 -160.0 tr 1.0 -1.0 sc 0.0 -324.0 tr mcm 22.0 92.0 tr np 66 48 m 74 48 li 90 48 102 48 106 50 cv 116 52 126 56 132 60 cv 142 70 150 84 150 98 cv 150 112 144 122 134 128 cv 128 132 118 134 100 134 cv 42 134 li 38 114 li 58 114 li 38 20 li 20 20 li 16 0 li 90 0 li 94 20 li 60 20 li cp 80 114 m 96 114 li 110 114 116 114 120 110 cv 126 108 128 102 128 96 cv 128 88 126 82 120 76 cv 114 70 106 68 78 68 cv 70 68 li cp 1 w gs eofill gr s bzcl 140.0 0.0 tr sm mcm 162.0 92.0 tr np 68 134 m 26 134 li 22 114 li 34 114 li 16 20 li 4 20 li 0 0 li 58 0 li 62 20 li 38 20 li 54 102 li 68 30 li 82 30 li 124 102 li 108 20 li 84 20 li 80 0 li 140 0 li 144 20 li 130 20 li 148 114 li 162 114 li 166 134 li 122 134 li 82 64 li cp 1 w gs eofill gr s bzcl 140.0 0.0 tr sm mcm 302.0 92.0 tr np 66 48 m 74 48 li 90 48 102 48 106 50 cv 116 52 126 56 132 60 cv 142 70 150 84 150 98 cv 150 112 144 122 134 128 cv 128 132 118 134 100 134 cv 42 134 li 38 114 li 58 114 li 38 20 li 20 20 li 16 0 li 90 0 li 94 20 li 60 20 li cp 80 114 m 96 114 li 110 114 116 114 120 110 cv 126 108 128 102 128 96 cv 128 88 126 82 120 76 cv 114 70 106 68 78 68 cv 70 68 li cp 1 w gs eofill gr s bzcl 140.0 0.0 tr sm mcm 503.0 191.0 tr np 24 86 m 18 60 li 24 60 li 28 80 li 60 80 li 44 6 li 26 6 li 24 0 li 68 0 li 70 6 li 50 6 li 66 80 li 96 80 li 92 60 li 98 60 li 104 86 li cp 1 w gs eofill gr s bzcl 93.0 0.0 tr sm mcm 596.0 92.0 tr np 122 82 m 122 90 li 34 90 li 34 82 li cp 122 46 m 122 54 li 34 54 li 34 46 li cp 1 w gs eofill gr s bzcl 140.0 0.0 tr sm mcm 736.0 92.0 tr np 78 114 m 104 114 li 108 134 li 36 134 li 32 114 li 56 114 li 36 20 li 14 20 li 10 0 li 130 0 li 142 64 li 122 64 li 112 20 li 58 20 li cp 1 w gs eofill gr s bzcl 140.0 0.0 tr sm mcm 876.0 92.0 tr np 78 114 m 104 114 li 108 134 li 36 134 li 32 114 li 56 114 li 36 20 li 14 20 li 10 0 li 130 0 li 142 64 li 122 64 li 112 20 li 58 20 li cp 1 w gs eofill gr s bzcl 140.0 0.0 tr sm mcm 1077.0 191.0 tr np 24 86 m 18 60 li 24 60 li 28 80 li 60 80 li 44 6 li 26 6 li 24 0 li 68 0 li 70 6 li 50 6 li 66 80 li 96 80 li 92 60 li 98 60 li 104 86 li cp 1 w gs eofill gr s bzcl 93.0 0.0 tr sm 150 255 div g 0 w sm sm icl mcm 1365 9856 tr 1 -1 sc sm icl mcm 1465 9756 tr 1 -1 sc mcm 0.0 -160.0 tr 1.0 -1.0 sc 0.0 -324.0 tr mcm 22.0 92.0 tr np 68 134 m 26 134 li 22 114 li 34 114 li 16 20 li 4 20 li 0 0 li 58 0 li 62 20 li 38 20 li 54 102 li 68 30 li 82 30 li 124 102 li 108 20 li 84 20 li 80 0 li 140 0 li 144 20 li 130 20 li 148 114 li 162 114 li 166 134 li 122 134 li 82 64 li cp 0 255 div g 1 w gs eofill gr s bzcl 140.0 0.0 tr sm mcm 162.0 92.0 tr np 122 82 m 122 90 li 34 90 li 34 82 li cp 122 46 m 122 54 li 34 54 li 34 46 li cp 1 w gs eofill gr s bzcl 140.0 0.0 tr sm mcm 302.0 92.0 tr np 78 114 m 104 114 li 108 134 li 36 134 li 32 114 li 56 114 li 36 20 li 14 20 li 10 0 li 130 0 li 142 64 li 122 64 li 112 20 li 58 20 li cp 1 w gs eofill gr s bzcl 140.0 0.0 tr sm mcm 442.0 92.0 tr np 78 114 m 104 114 li 108 134 li 36 134 li 32 114 li 56 114 li 36 20 li 14 20 li 10 0 li 130 0 li 142 64 li 122 64 li 112 20 li 58 20 li cp 1 w gs eofill gr s bzcl 140.0 0.0 tr sm mcm 643.0 191.0 tr np 24 86 m 18 60 li 24 60 li 28 80 li 60 80 li 44 6 li 26 6 li 24 0 li 68 0 li 70 6 li 50 6 li 66 80 li 96 80 li 92 60 li 98 60 li 104 86 li cp 1 w gs eofill gr s bzcl 93.0 0.0 tr sm mcm 736.0 92.0 tr np 54 0 m 84 0 li 84 36 li 54 36 li cp 1 w gs eofill gr s bzcl 140.0 0.0 tr sm 150 255 div g 0 w sm sm icl mcm 4503 9856 tr 1 -1 sc sm icl mcm 4603 9756 tr 1 -1 sc mcm -124.0 -160.0 tr 1.0 -1.0 sc 0.0 -324.0 tr mcm 22.0 92.0 tr np 66 48 m 74 48 li 90 48 102 48 106 50 cv 116 52 126 56 132 60 cv 142 70 150 84 150 98 cv 150 112 144 122 134 128 cv 128 132 118 134 100 134 cv 42 134 li 38 114 li 58 114 li 38 20 li 20 20 li 16 0 li 90 0 li 94 20 li 60 20 li cp 80 114 m 96 114 li 110 114 116 114 120 110 cv 126 108 128 102 128 96 cv 128 88 126 82 120 76 cv 114 70 106 68 78 68 cv 70 68 li cp 0 255 div g 1 w gs eofill gr s bzcl 140.0 0.0 tr sm mcm 162.0 92.0 tr np 68 134 m 26 134 li 22 114 li 34 114 li 16 20 li 4 20 li 0 0 li 58 0 li 62 20 li 38 20 li 54 102 li 68 30 li 82 30 li 124 102 li 108 20 li 84 20 li 80 0 li 140 0 li 144 20 li 130 20 li 148 114 li 162 114 li 166 134 li 122 134 li 82 64 li cp 1 w gs eofill gr s bzcl 140.0 0.0 tr sm mcm 302.0 92.0 tr np 66 48 m 74 48 li 90 48 102 48 106 50 cv 116 52 126 56 132 60 cv 142 70 150 84 150 98 cv 150 112 144 122 134 128 cv 128 132 118 134 100 134 cv 42 134 li 38 114 li 58 114 li 38 20 li 20 20 li 16 0 li 90 0 li 94 20 li 60 20 li cp 80 114 m 96 114 li 110 114 116 114 120 110 cv 126 108 128 102 128 96 cv 128 88 126 82 120 76 cv 114 70 106 68 78 68 cv 70 68 li cp 1 w gs eofill gr s bzcl 140.0 0.0 tr sm mcm 503.0 191.0 tr np 24 86 m 18 60 li 24 60 li 28 80 li 60 80 li 44 6 li 26 6 li 24 0 li 68 0 li 70 6 li 50 6 li 66 80 li 96 80 li 92 60 li 98 60 li 104 86 li cp 1 w gs eofill gr s bzcl 93.0 0.0 tr sm 150 255 div g 0 w sm sm icl 5040 1263 m /CourierR 600 ff 0 255 div g (2)S 1200 11846 m /NewCenturySchlbk-BoldR 600 ff 10 0 32 (1 Introduction)W 1200 11241 m -1 0 (1.1)A 5 0 32 -1 0 ( description.)AW /NewCenturySchlbk-RomanR 600 ff 6 0 32 -1 0 ( )AW 7 0 32 -1 0 ( )AW /NewCenturySchlbk-ItalicR 600 ff 7 0 32 -1 0 (The Approximate Minimum Degree Ordering Algorithm)AW /NewCenturySchlbk-RomanR 600 ff 7 0 32 -1 0 ( \(AMD\) [1])AW 1200 10937 m 1 0 (fo)A (r)S 30 0 32 ( preordering a sparse symmetric positive definite matrix )W /NewCenturySchlbk-BoldR 600 ff 29 0 32 (M )W /NewCenturySchlbk-RomanR 600 ff 30 0 32 (prior to numerical)W 1200 10633 m 1 0 (factori)A (zation)S 31 0 32 ( is used for a wide variety of scientific and engineering applications.)W 1200 10314 m 1 0 (AMD)A 55 0 32 1 0 ( fin)AW 55 0 32 (ds a permutation )W /NewCenturySchlbk-BoldR 600 ff 54 0 32 (P )W /NewCenturySchlbk-RomanR 600 ff 55 0 32 (so that the Cholesky factorization of )W 1140 h 55 0 32 ()W 1200 10005 m 1 0 (requi)A (res)S 40 0 32 ( less work and storage \(nonzeroes in )W /NewCenturySchlbk-BoldR 600 ff 39 0 32 (L)W /NewCenturySchlbk-RomanR 600 ff 40 0 32 (\) than the Cholesky factorization)W 1200 9684 m -1 0 (of)A 1097 h -1 0 (The)A 5 0 32 -1 0 ( permuted matrix )AW 569 h 5 0 32 -1 0 ()AW 5 0 32 -1 0 ( from AMD )AW 6 0 32 -1 0 (normally takes much less time)AW 1200 9376 m 1 0 (to)A 27 0 32 1 0 ( com)AW 27 0 32 (pute the numerical factorization. One important exception that this paper)W 1200 9074 m -3 0 (addresses)A 10 0 32 -3 0 ( is when )AW /NewCenturySchlbk-BoldR 600 ff 9 0 32 -3 0 (M )AW /NewCenturySchlbk-RomanR 600 ff 11 0 32 -3 0 (contains one or more dense \(or nearly dense\) rows and columns.)AW 1200 8770 m 1800 8770 m 1 0 (If)A 17 0 32 1 0 ( a mat)AW 17 0 32 (rix is not sparse, and simultaneously not extremely dense, it can be)W 1200 8468 m 11 0 32 (partitioned into four submatrices as shown in figure 1. )W 4799 7734 m /NewCenturySchlbk-BoldR 720 ff (A)S 6177 7734 m (B)S 4797 5826 m (C)S 6170 5826 m (D)S 3478 5234 m /NewCenturySchlbk-BoldR 600 ff 10 0 32 (Figure 1: Partitioning a matrix)W /NewCenturySchlbk-RomanR 600 ff 1200 4629 m -1 0 (Where)A 10 0 32 -1 0 ( submatrix )AW /NewCenturySchlbk-BoldR 600 ff 9 0 32 -1 0 (A)AW /NewCenturySchlbk-RomanR 600 ff 10 0 32 -1 0 ( is sparse and submatrices )AW /NewCenturySchlbk-BoldR 600 ff 9 0 32 -1 0 (B, C,)AW /NewCenturySchlbk-RomanR 600 ff 10 0 32 -1 0 ( and )AW /NewCenturySchlbk-BoldR 600 ff 9 0 32 -1 0 (D)AW /NewCenturySchlbk-RomanR 600 ff 10 0 32 -1 0 ( )AW 11 0 32 -1 0 (are dense \(or nearly so\).)AW 1200 4325 m -1 0 (After)A 4 0 32 -1 0 ( partitioning, )AW 5 0 32 -1 0 (AMD rapidly orders submatrix )AW /NewCenturySchlbk-BoldR 600 ff 4 0 32 -1 0 (A)AW /NewCenturySchlbk-RomanR 600 ff 5 0 32 -1 0 (, and )AW /NewCenturySchlbk-BoldR 600 ff 4 0 32 -1 0 (D )AW /NewCenturySchlbk-RomanR 600 ff 5 0 32 -1 0 (is ordered by sorting the)AW 1200 4021 m 1 0 (ro)A (ws)S 43 0 32 ( and columns according to the number of nonzeroes in )W /NewCenturySchlbk-BoldR 600 ff 42 0 32 (D)W /NewCenturySchlbk-RomanR 600 ff 43 0 32 (. Once both the)W 1200 3717 m 1 0 (submatric)A (es)S 36 0 32 ( )W /NewCenturySchlbk-BoldR 600 ff 35 0 32 (A)W /NewCenturySchlbk-RomanR 600 ff 36 0 32 ( and )W /NewCenturySchlbk-BoldR 600 ff 35 0 32 (D)W /NewCenturySchlbk-RomanR 600 ff 36 0 32 ( are ordered, then the user has the ordering for the entire)W 1200 3413 m -2 0 (matrix.)A 9 0 32 -2 0 ( For matrices )AW 10 0 32 -2 0 (with some dense rows this is much faster than preordering the)AW 1200 3111 m 11 0 32 (entire matrix, and, occasionally, yields a better ordering. )W 1200 1903 m 1800 1903 m 11 0 32 ( )W ep %%Page: 3 3 bp /NewCenturySchlbk-RomanR 600 ff 0 13200 10200 co mcm 7499 11352 tr 1 -1 sc sm icl mcm 7599 11252 tr 1 -1 sc mcm -90.0 -161.0 tr 1.0 -1.0 sc 0.0 -326.0 tr mcm 21.0 152.0 tr np 42 92 m 44 86 li 60 92 74 94 86 94 cv 106 94 114 86 112 68 cv 110 60 li 106 62 li 92 64 86 64 74 64 cv 46 64 24 50 20 30 cv 16 12 28 -2 50 -2 cv 68 -2 84 6 102 22 cv 98 0 li 128 0 li 130 8 li 108 8 li 120 70 li 122 82 120 90 112 96 cv 106 100 98 102 88 102 cv 74 102 62 100 42 92 cv cp 76 56 m 86 56 94 56 108 54 cv 104 32 li 96 26 94 22 86 18 cv 74 10 62 6 52 6 cv 36 6 26 16 30 30 cv 32 46 50 56 76 56 cv cp 0 255 div g 1 w gs eofill gr s bzcl 140.0 0.0 tr sm mcm 167.0 67.0 tr np 62 66 m 34 66 li 32 60 li 56 60 li 44 6 li 16 6 li 16 0 li 76 0 li 78 6 li 50 6 li cp 56 86 m 66 86 li 70 102 li 60 102 li cp 1 w gs eofill gr s bzcl 93.0 0.0 tr np 26 66 m 26 60 li 66 60 li 56 10 li 54 2 52 -2 52 -6 cv 48 -16 40 -20 28 -20 cv 20 -20 16 -20 10 -16 cv 6 -20 li 12 -24 18 -26 26 -26 cv 36 -26 44 -22 50 -18 cv 56 -12 58 -6 62 8 cv 72 66 li cp 62 86 m 72 86 li 76 102 li 66 102 li cp gs eofill gr s bzcl 93.0 0.0 tr sm mcm 353.0 152.0 tr np 116 48 m 116 56 li 70 56 li 80 78 li 116 78 li 116 86 li 84 86 li 96 116 li 90 118 li 76 86 li 28 86 li 28 78 li 72 78 li 60 56 li 28 56 li 28 48 li 58 48 li 44 18 li 50 14 li 66 48 li cp 1 w gs eofill gr s bzcl 140.0 0.0 tr sm mcm 493.0 152.0 tr np 96 132 m 68 132 48 108 40 66 cv 30 22 42 -2 70 -2 cv 98 -2 118 22 126 66 cv 134 108 124 132 96 132 cv cp 48 66 m 56 104 72 124 94 124 cv 116 124 124 104 116 66 cv 108 26 94 6 70 6 cv 48 6 42 26 48 66 cv cp 1 w gs eofill gr s bzcl 140.0 0.0 tr sm 150 255 div g 0 w sm sm icl mcm 8656 11362 tr 1 -1 sc sm icl mcm 8756 11362 tr 1 -1 sc mcm -159.0 -51.0 tr 1.0 -1.0 sc 0.0 -264.0 tr mcm 21.0 90.0 tr np 94 100 m 50 100 li 48 92 li 84 92 li 68 8 li 26 8 li 24 0 li 116 0 li 116 8 li 76 8 li cp 84 128 m 100 128 li 104 152 li 90 152 li cp 0 255 div g 1 w gs eofill gr s bzcl 140.0 0.0 tr sm mcm 161.0 90.0 tr np 116 48 m 116 56 li 70 56 li 80 78 li 116 78 li 116 86 li 84 86 li 96 116 li 90 118 li 76 86 li 28 86 li 28 78 li 72 78 li 60 56 li 28 56 li 28 48 li 58 48 li 44 18 li 50 14 li 66 48 li cp 1 w gs eofill gr s bzcl 140.0 0.0 tr sm mcm 301.0 90.0 tr np 40 100 m 38 92 li 100 92 li 84 14 li 82 4 80 -2 78 -8 cv 72 -22 60 -30 42 -30 cv 32 -30 26 -28 14 -24 cv 10 -32 li 18 -36 28 -38 40 -38 cv 54 -38 68 -34 76 -26 cv 84 -18 88 -8 92 14 cv 110 100 li cp 94 128 m 110 128 li 114 152 li 100 152 li cp 1 w gs eofill gr s bzcl 140.0 0.0 tr sm 150 255 div g 0 w sm sm icl mcm 7529 4424 tr 1 -1 sc sm icl mcm 7629 4324 tr 1 -1 sc mcm -84.0 -128.0 tr 1.0 -1.0 sc 0.0 -312.0 tr mcm 150.0 21.0 tr 0.19999 0.19699 sc np 0 1150 m 700 1150 li 700 1185 li 0 1185 li cp 0 255 div g 1 w gs fill gr s bzcl sm mcm 21.0 21.0 tr 0.23298 0.19699 sc np 30 475 m 117 592 li 232 128 li 536 1185 li 555 1185 li 555 1150 li 225 0 li 205 0 li 78 519 li 40 468 li 30 475 li 1 w gs eofill gr s bzcl sm mcm 150.0 90.0 tr np 30 100 m 28 92 li 48 92 li 30 8 li 10 8 li 10 0 li 58 0 li 58 8 li 38 8 li 52 74 li 70 88 84 94 100 94 cv 118 94 122 86 118 64 cv 106 8 li 88 8 li 86 0 li 134 0 li 136 8 li 116 8 li 126 64 li 130 76 130 82 128 88 cv 124 98 116 102 102 102 cv 84 102 70 96 54 82 cv 58 100 li cp 1 w gs eofill gr s bzcl 140.0 0.0 tr sm 150 255 div g 0 w sm sm icl mcm 3017 4071 tr 1 -1 sc sm icl mcm 3117 3971 tr 1 -1 sc mcm -84.0 -128.0 tr 1.0 -1.0 sc 0.0 -312.0 tr mcm 150.0 21.0 tr 0.19999 0.19699 sc np 0 1150 m 700 1150 li 700 1185 li 0 1185 li cp 0 255 div g 1 w gs fill gr s bzcl sm mcm 21.0 21.0 tr 0.23298 0.19699 sc np 30 475 m 117 592 li 232 128 li 536 1185 li 555 1185 li 555 1150 li 225 0 li 205 0 li 78 519 li 40 468 li 30 475 li 1 w gs eofill gr s bzcl sm mcm 150.0 90.0 tr np 30 100 m 28 92 li 48 92 li 30 8 li 10 8 li 10 0 li 58 0 li 58 8 li 38 8 li 52 74 li 70 88 84 94 100 94 cv 118 94 122 86 118 64 cv 106 8 li 88 8 li 86 0 li 134 0 li 136 8 li 116 8 li 126 64 li 130 76 130 82 128 88 cv 124 98 116 102 102 102 cv 84 102 70 96 54 82 cv 58 100 li cp 1 w gs eofill gr s bzcl 140.0 0.0 tr sm 150 255 div g 0 w sm sm icl mcm 8051 4071 tr 1 -1 sc sm icl mcm 8151 3971 tr 1 -1 sc mcm -84.0 -128.0 tr 1.0 -1.0 sc 0.0 -312.0 tr mcm 150.0 21.0 tr 0.19999 0.19699 sc np 0 1150 m 700 1150 li 700 1185 li 0 1185 li cp 0 255 div g 1 w gs fill gr s bzcl sm mcm 21.0 21.0 tr 0.23298 0.19699 sc np 30 475 m 117 592 li 232 128 li 536 1185 li 555 1185 li 555 1150 li 225 0 li 205 0 li 78 519 li 40 468 li 30 475 li 1 w gs eofill gr s bzcl sm mcm 150.0 90.0 tr np 30 100 m 28 92 li 48 92 li 30 8 li 10 8 li 10 0 li 58 0 li 58 8 li 38 8 li 52 74 li 70 88 84 94 100 94 cv 118 94 122 86 118 64 cv 106 8 li 88 8 li 86 0 li 134 0 li 136 8 li 116 8 li 126 64 li 130 76 130 82 128 88 cv 124 98 116 102 102 102 cv 84 102 70 96 54 82 cv 58 100 li cp 1 w gs eofill gr s bzcl 140.0 0.0 tr sm 150 255 div g 0 w sm sm icl mcm 4868 3718 tr 1 -1 sc sm icl mcm 4968 3618 tr 1 -1 sc mcm -84.0 -128.0 tr 1.0 -1.0 sc 0.0 -312.0 tr mcm 150.0 21.0 tr 0.19999 0.19699 sc np 0 1150 m 700 1150 li 700 1185 li 0 1185 li cp 0 255 div g 1 w gs fill gr s bzcl sm mcm 21.0 21.0 tr 0.23298 0.19699 sc np 30 475 m 117 592 li 232 128 li 536 1185 li 555 1185 li 555 1150 li 225 0 li 205 0 li 78 519 li 40 468 li 30 475 li 1 w gs eofill gr s bzcl sm mcm 150.0 90.0 tr np 30 100 m 28 92 li 48 92 li 30 8 li 10 8 li 10 0 li 58 0 li 58 8 li 38 8 li 52 74 li 70 88 84 94 100 94 cv 118 94 122 86 118 64 cv 106 8 li 88 8 li 86 0 li 134 0 li 136 8 li 116 8 li 126 64 li 130 76 130 82 128 88 cv 124 98 116 102 102 102 cv 84 102 70 96 54 82 cv 58 100 li cp 1 w gs eofill gr s bzcl 140.0 0.0 tr sm 150 255 div g 0 w sm sm icl mcm 5310 3718 tr 1 -1 sc sm icl mcm 5410 3618 tr 1 -1 sc mcm -84.0 -128.0 tr 1.0 -1.0 sc 0.0 -312.0 tr mcm 150.0 21.0 tr 0.19999 0.19699 sc np 0 1150 m 700 1150 li 700 1185 li 0 1185 li cp 0 255 div g 1 w gs fill gr s bzcl sm mcm 21.0 21.0 tr 0.23298 0.19699 sc np 30 475 m 117 592 li 232 128 li 536 1185 li 555 1185 li 555 1150 li 225 0 li 205 0 li 78 519 li 40 468 li 30 475 li 1 w gs eofill gr s bzcl sm mcm 150.0 90.0 tr np 30 100 m 28 92 li 48 92 li 30 8 li 10 8 li 10 0 li 58 0 li 58 8 li 38 8 li 52 74 li 70 88 84 94 100 94 cv 118 94 122 86 118 64 cv 106 8 li 88 8 li 86 0 li 134 0 li 136 8 li 116 8 li 126 64 li 130 76 130 82 128 88 cv 124 98 116 102 102 102 cv 84 102 70 96 54 82 cv 58 100 li cp 1 w gs eofill gr s bzcl 140.0 0.0 tr sm 150 255 div g 0 w sm sm icl 5040 1263 m /CourierR 600 ff 0 255 div g (3)S 1200 11845 m /NewCenturySchlbk-BoldR 600 ff 10 0 32 -1 0 (1.2 Approximate Minimum Degree Algorithm. )AW /NewCenturySchlbk-RomanR 600 ff 11 0 32 -1 0 (AMD)AW /NewCenturySchlbk-BoldR 600 ff 10 0 32 ( )W /NewCenturySchlbk-RomanR 600 ff 11 0 32 (uses a graph theoretical)W 1200 11541 m -2 0 (approach)A 7 0 32 -2 0 ( to represent a matrix. The nodes of the undirected )AW 8 0 32 -2 0 (graph are the diagonals)AW 1200 11239 m 11 0 32 -1 0 (of the matrix and the edges are the off-diagonal nonzer)AW 11 0 32 (os. Thus, if )W 675 h 11 0 32 ()W 11 0 32 ( and )W 344 h 11 0 32 ()W 1200 10921 m 11 0 32 -1 0 (then there exists an edg)AW 11 0 32 (e from node )W /NewCenturySchlbk-ItalicR 600 ff 11 0 32 (i)W /NewCenturySchlbk-BoldR 600 ff 10 0 32 ( )W /NewCenturySchlbk-RomanR 600 ff 11 0 32 (to node )W /NewCenturySchlbk-ItalicR 600 ff 11 0 32 (j)W /NewCenturySchlbk-RomanR 600 ff 11 0 32 (. AMD selects nodes from the graph)W 1200 10617 m -2 0 (to)A 12 0 32 -2 0 ( produce )AW 11 0 32 -2 0 (an ordering such that the degree of each node selected is minimized. The)AW 1200 10315 m 1 0 (degree)A 55 0 32 1 0 ( o)AW 55 0 32 (f a node is the number of nodes that are adjacent to it. The degree)W 1200 10013 m -2 0 (represents)A 9 0 32 -2 0 ( the number of nonzeroes in a row. )AW 10 0 32 -2 0 (The maximum degree of a node is )AW /NewCenturySchlbk-ItalicR 600 ff 10 0 32 -2 0 (n)AW /NewCenturySchlbk-RomanR 600 ff 10 0 32 -2 0 (-1,)AW 1200 9711 m 11 0 32 (where )W /NewCenturySchlbk-ItalicR 600 ff 11 0 32 (n)W /NewCenturySchlbk-RomanR 600 ff 11 0 32 ( is the order of the matrix. )W 1200 9409 m 1800 9409 m (Once)S 35 0 32 ( AMD selects a node, it eliminates the selected node from the graph.)W 1200 9107 m 11 0 32 -1 0 (However, to eliminate the node from the graph, edges are added )AW 11 0 32 (to the neighbors of)W 1200 8805 m 1 0 (the)A 16 0 32 1 0 ( node so th)AW 16 0 32 (at the neighbors become a clique. In the formation of a clique, each)W 1200 8503 m 1 0 (neighborin)A (g)S 13 0 32 ( node must be checked to see if it has an edge to the other neighboring)W 1200 8201 m -2 0 (nodes.)A 9 0 32 -2 0 ( If )AW 10 0 32 -2 0 (a neighboring node is dense \(or fully connected\), i.e. has )AW /NewCenturySchlbk-ItalicR 600 ff 10 0 32 -2 0 (n)AW /NewCenturySchlbk-RomanR 600 ff 10 0 32 -2 0 (-1 edges, then ,in)AW 1200 7899 m -1 0 (the)A 8 0 32 -1 0 ( worst )AW 9 0 32 -1 0 (case, )AW /NewCenturySchlbk-ItalicR 600 ff 9 0 32 -1 0 (n)AW /NewCenturySchlbk-RomanR 600 ff 9 0 32 -1 0 (-1 comparisons are made. Since this process must be done for each)AW 1200 7597 m 11 0 32 (node to be eliminated, i.e. )W /NewCenturySchlbk-ItalicR 600 ff 11 0 32 (n)W /NewCenturySchlbk-RomanR 600 ff 11 0 32 ( times, there will be at least )W /NewCenturySchlbk-ItalicR 600 ff 11 0 32 (n)W /NewCenturySchlbk-RomanR 600 ff 11 0 32 (\()W /NewCenturySchlbk-ItalicR 600 ff 11 0 32 (n)W /NewCenturySchlbk-RomanR 600 ff 11 0 32 (-1\) comparisons.)W 1200 7295 m 11 0 32 ( )W 1200 6994 m /NewCenturySchlbk-BoldR 600 ff 10 0 32 (2 The AMD Preprocessor Algorithm.)W 1200 6389 m -1 0 (2.1)A 4 0 32 -1 0 ( Introduction. )AW 5 0 32 -1 0 ( )AW /NewCenturySchlbk-RomanR 600 ff 6 0 32 -1 0 (The primary purpose of the preprocessor algorithm is reduce the)AW 1200 6085 m 1 0 (ordering)A 25 0 32 1 0 ( )AW 25 0 32 (time of AMD by partitioning matrix )W /NewCenturySchlbk-BoldR 600 ff 24 0 32 (M)W /NewCenturySchlbk-RomanR 600 ff 25 0 32 ( so that the partitioned matrix in)W 1200 5781 m 11 0 32 (figure 1 is formed. Appendix A contains the AMDpre algorithm \(AMDpre\).)W 1200 5479 m 1800 5479 m 1 0 (Th)A (e)S 15 0 32 ( key variable in AMDpre is the value of the threshold used to determine)W 1200 5177 m -2 0 (when)A 9 0 32 -2 0 ( a row or column is dense and )AW 10 0 32 -2 0 (is to be placed in the submatrix )AW /NewCenturySchlbk-BoldR 600 ff 9 0 32 -2 0 (D)AW /NewCenturySchlbk-RomanR 600 ff 10 0 32 -2 0 (. )AW 10 0 32 -2 0 (A good value)AW 1200 4873 m (for)S 12 0 32 ( this threshold)W 12 0 32 ( is the square root of )W /NewCenturySchlbk-ItalicR 600 ff 12 0 32 (n.)W /NewCenturySchlbk-RomanR 600 ff 12 0 32 ( )W 11 0 32 (For most matrices with some dense rows)W 1200 4571 m 1 0 (and)A 23 0 32 ( columns, this value for the threshold will yield the best ordering time than a)W 1200 4230 m 11 0 32 -1 0 (higher value for the threshold.)AW 11 0 32 -1 0 ( If a neig)AW 11 0 32 (hboring node )W /NewCenturySchlbk-ItalicR 600 ff 11 0 32 (i )W /NewCenturySchlbk-RomanR 600 ff 11 0 32 (has )W 11 0 32 (at most )W 344 h 11 0 32 ()W 11 0 32 ( edges, then)W 1200 3877 m 1 0 (,in)A 19 0 32 1 0 ( the wor)AW 19 0 32 (st case, )W 344 h 19 0 32 ()W /NewCenturySchlbk-ItalicR 600 ff 19 0 32 ( )W /NewCenturySchlbk-RomanR 600 ff 19 0 32 (comparisons are made. Since there are at most )W 344 h 19 0 32 ()W 19 0 32 ( nodes)W 1200 3524 m -1 0 (adjacent)A 6 0 32 -1 0 ( to node )AW /NewCenturySchlbk-ItalicR 600 ff 7 0 32 -1 0 (i )AW /NewCenturySchlbk-RomanR 600 ff 7 0 32 -1 0 (there will be at least )AW 343 h 7 0 32 -1 0 ()AW 7 0 32 -1 0 (*)AW 343 h 7 0 32 -1 0 ()AW 7 0 32 -1 0 ( or )AW /NewCenturySchlbk-ItalicR 600 ff 7 0 32 -1 0 (n )AW /NewCenturySchlbk-RomanR 600 ff 7 0 32 -1 0 (comparisons. )AW 7 0 32 -1 0 (The algorithm is)AW 1200 3210 m 1 0 (written)A 16 0 32 1 0 ( so the )AW 16 0 32 (user can pass in a single value, )W /NewCenturySchlbk-ItalicR 600 ff 16 0 32 (z)W /NewCenturySchlbk-RomanR 600 ff 16 0 32 (, that can increase or decrease the)W 1200 2908 m 11 0 32 (value of the threshold in relationship to the square root of )W /NewCenturySchlbk-ItalicR 600 ff 11 0 32 (n)W /NewCenturySchlbk-RomanR 600 ff 11 0 32 (. )W 1200 2606 m 1800 2606 m 11 0 32 -1 0 (An alternative valu)AW 11 0 32 (e for the threshold is to select those rows whose densities)W 1200 2304 m (are)S 1 h 27 0 32 ( significantly higher than the average density. Using this approach for linear)W 1200 2002 m 11 0 32 -1 0 (programming problems, such as GUPTA1 )AW 11 0 32 (\(see table 1\))W 11 0 32 (, a better ordering will result)W 1200 1700 m 1 0 (as)A 12 0 32 1 0 ( explained)AW 12 0 32 ( in [4]. The set of matrices obtained from Gupta contained a few rows)W ep %%Page: 4 4 bp /NewCenturySchlbk-RomanR 600 ff 0 13200 10200 co mcm 2457 10188 tr 1 -1 sc sm icl mcm 2557 10088 tr 1 -1 sc mcm -66.0 -160.0 tr 1.0 -1.0 sc 0.0 -324.0 tr mcm 22.0 92.0 tr np 28 20 m 10 20 li 6 0 li 66 0 li 94 0 110 6 124 22 cv 138 38 148 64 148 88 cv 148 102 144 116 134 124 cv 126 132 116 134 94 134 cv 32 134 li 28 114 li 46 114 li cp 68 114 m 90 114 li 106 114 112 112 118 106 cv 122 102 126 92 126 82 cv 126 66 118 46 108 34 cv 100 24 90 20 72 20 cv 50 20 li cp 0 255 div g 1 w gs eofill gr s bzcl 140.0 0.0 tr sm mcm 162.0 92.0 tr np 122 64 m 122 72 li 36 72 li 36 64 li cp 1 w gs eofill gr s bzcl 140.0 0.0 tr sm mcm 302.0 92.0 tr np 140 134 m 136 126 li 126 134 118 136 104 136 cv 60 136 24 98 24 52 cv 24 38 28 26 34 18 cv 42 6 58 -2 76 -2 cv 86 -2 96 0 106 4 cv 116 8 124 12 140 22 cv 130 38 li 108 24 94 18 80 18 cv 70 18 58 24 52 32 cv 48 38 46 44 46 54 cv 46 88 70 116 102 116 cv 118 116 130 106 130 92 cv 130 90 li 128 80 li 150 84 li 150 108 li 158 130 li cp 1 w gs eofill gr s bzcl 140.0 0.0 tr sm mcm 442.0 92.0 tr np 106 134 m 48 134 li 44 114 li 74 114 li 16 20 li 4 20 li 0 0 li 56 0 li 60 20 li 40 20 li 54 42 li 104 42 li 108 20 li 88 20 li 84 0 li 140 0 li 144 20 li 132 20 li cp 90 102 m 98 62 li 66 62 li cp 1 w gs eofill gr s bzcl 140.0 0.0 tr sm mcm 619.0 191.0 tr np 82 42 m 82 48 li 24 48 li 24 42 li cp 1 w gs eofill gr s bzcl 93.0 0.0 tr sm mcm 712.0 191.0 tr np 16 74 m 18 70 li 44 80 li 44 6 li 16 6 li 16 0 li 76 0 li 76 6 li 50 6 li 50 86 li 46 86 li cp 1 w gs eofill gr s bzcl 93.0 0.0 tr sm mcm 805.0 92.0 tr np 124 72 m 134 80 140 92 140 104 cv 140 112 138 118 134 124 cv 126 130 118 134 100 134 cv 34 134 li 30 114 li 48 114 li 30 20 li 12 20 li 8 0 li 72 0 li 84 0 92 0 98 2 cv 106 4 114 8 120 12 cv 132 20 138 34 138 46 cv 138 58 134 66 124 72 cv cp 70 114 m 96 114 li 112 114 118 110 118 100 cv 118 96 116 90 114 88 cv 108 82 102 80 90 80 cv 64 80 li cp 52 20 m 60 60 li 84 60 li 108 60 116 56 116 44 cv 116 38 114 32 108 28 cv 102 22 94 20 76 20 cv cp 1 w gs eofill gr s bzcl 140.0 0.0 tr sm 150 255 div g 0 w sm sm icl 5040 1263 m /CourierR 600 ff 0 255 div g (4)S 1200 11845 m /NewCenturySchlbk-RomanR 600 ff -2 0 (that)A 10 0 32 -2 0 ( are )AW 11 0 32 -2 0 (approximately two or three times more dense than the average row density.)AW 1200 11543 m -2 0 (The)A 5 0 32 -2 0 ( permutation using this method usually yields a better flop )AW 6 0 32 -2 0 (count and lower fill-in)AW 1200 11241 m 1 0 (from)A 14 0 32 1 0 ( factor)AW 14 0 32 (ization for linear programming problems, however, it will not be as fast)W 1200 10939 m 11 0 32 (as using the square root of )W /NewCenturySchlbk-ItalicR 600 ff 11 0 32 (n)W /NewCenturySchlbk-RomanR 600 ff 11 0 32 ( for the threshold.)W 1200 10637 m 1800 10637 m (In)S 1 h 33 0 32 ( either case, ordering the dense nodes by row density normally does not)W 1200 10335 m -3 0 (improve)A 10 0 32 -3 0 ( the flop count or fill-in. An alternative to this approach is to order )AW 11 0 32 -3 0 (the Schur)AW 1200 10016 m 11 0 32 (complement \()W 1035 h 11 0 32 (\) instead of )W /NewCenturySchlbk-BoldR 600 ff 10 0 32 (D)W /NewCenturySchlbk-RomanR 600 ff 11 0 32 ( )W 11 0 32 ([5]. )W 1200 9707 m 11 0 32 ( )W 1800 9707 m 1200 9405 m /NewCenturySchlbk-BoldR 600 ff 1 0 (2.2)A 18 0 32 1 0 ( Buckets.)AW /NewCenturySchlbk-RomanR 600 ff 19 0 32 1 0 ( )AW 19 0 32 (In section 1 of AMDpre, a bucket sort is used to sort all the nodes)W 1200 9101 m 1 0 (accord)A (ing)S 18 0 32 ( to their row densities, or degrees, that are greater than the value of the)W 1200 8799 m 1 0 (threshold.)A 13 0 32 1 0 ( Th)AW 13 0 32 (e node is simply placed in a bucket corresponding to its degree. The)W 1200 8497 m 1 0 (primary)A 15 0 32 1 0 ( func)AW 15 0 32 (tion of section 1 is to select the initial nodes for the submatrix )W /NewCenturySchlbk-BoldR 600 ff 14 0 32 (D )W /NewCenturySchlbk-RomanR 600 ff 15 0 32 (\(see)W 1200 8193 m -2 0 (figure)A 10 0 32 -2 0 ( 1\). )AW 11 0 32 -2 0 (The rest of the nodes are considered sparse and are placed in submartix )AW /NewCenturySchlbk-BoldR 600 ff 10 0 32 -2 0 (A)AW /NewCenturySchlbk-RomanR 600 ff 11 0 32 -2 0 (.)AW 1200 7889 m 1800 7889 m (The)S 1 h 30 0 32 ( primary function of section 2 of the algorithm, is to reduce the size of)W 1200 7587 m 1 0 (submatrix)A 20 0 32 1 0 ( )AW /NewCenturySchlbk-BoldR 600 ff 19 0 32 1 0 (D)AW 19 0 32 ( )W /NewCenturySchlbk-RomanR 600 ff 20 0 32 (made in section 1. AMDpre selects a node from the bucket with the)W 1200 7283 m 1 0 (highest)A 13 0 32 1 0 ( numbe)AW 13 0 32 (r. There may be more than one node in a bucket. The nodes in the)W 1200 6981 m (bucket)S 12 0 32 ( are in a singly linked list. )W 11 0 32 ( )W 11 0 32 ( AMDpre uses a control variable to indicate that)W 1200 6679 m 11 0 32 (there are more nodes remaining in the current bucket.)W 1200 6377 m 1800 6377 m 1 0 (Wh)A (en)S 39 0 32 ( a node in the list is selected, it is deleted from the list, essentially)W 1200 6075 m -2 0 (removing)A -1 h 11 0 32 -2 0 ( it from the bucket, and it is checked to see if its degree was changed. This)AW 1200 5773 m -1 0 (is)A 7 0 32 -1 0 ( a )AW 8 0 32 -1 0 (simple matter of comparing its value in the )AW /NewCenturySchlbk-ItalicR 600 ff 8 0 32 -1 0 (len )AW /NewCenturySchlbk-RomanR 600 ff 8 0 32 -1 0 (array with the bucket number it)AW 1200 5471 m 11 0 32 -1 0 (was in. )AW 11 0 32 -1 0 (The )AW /NewCenturySchlbk-ItalicR 600 ff 11 0 32 -1 0 (len )AW /NewCenturySchlbk-RomanR 600 ff 11 0 32 (array in AMDpre is used to keep a current record of the density of)W 1200 5169 m 1 0 (each)A 26 0 32 1 0 ( node. )AW 26 0 32 1 0 (I)AW 26 0 32 1 0 (f)AW 26 0 32 ( the value of the )W /NewCenturySchlbk-ItalicR 600 ff 26 0 32 (len )W /NewCenturySchlbk-RomanR 600 ff 26 0 32 (array is less than the bucket number, then the)W 1200 4867 m -1 0 (degree)A 8 0 32 -1 0 ( of that node must have )AW 9 0 32 -1 0 (been changed. )AW 9 0 32 -1 0 (If the degree is below the value of the)AW 1200 4565 m 1 0 (thresho)A (ld)S 35 0 32 ( then the node is placed into the submatrix )W /NewCenturySchlbk-BoldR 600 ff 34 0 32 (A)W /NewCenturySchlbk-RomanR 600 ff 35 0 32 (. )W 35 0 32 ( )W 35 0 32 (Otherwise, )W 35 0 32 (the node is)W 1200 4261 m 1 0 (placed)A 14 0 32 1 0 ( in th)AW 14 0 32 (e bucket equal to it current degree. It is very possible for a node to be)W 1200 3959 m -2 0 (moved)A 5 0 32 -2 0 ( from one bucket to another bucket many )AW 6 0 32 -2 0 (times before it is permanently placed)AW 1200 3657 m 11 0 32 -1 0 (in either submatrix )AW /NewCenturySchlbk-BoldR 600 ff 10 0 32 -1 0 (A )AW /NewCenturySchlbk-RomanR 600 ff 11 0 32 -1 0 (or s)AW 11 0 32 (ubmatrix )W /NewCenturySchlbk-BoldR 600 ff 10 0 32 (D. )W /NewCenturySchlbk-RomanR 600 ff 11 0 32 (If the density of the node equals the bucket)W 1200 3353 m 11 0 32 -1 0 (number then the node is place)AW 11 0 32 (d in submatrix )W /NewCenturySchlbk-BoldR 600 ff 10 0 32 (D)W /NewCenturySchlbk-RomanR 600 ff 11 0 32 (. )W /NewCenturySchlbk-BoldR 600 ff 10 0 32 ( )W /NewCenturySchlbk-RomanR 600 ff 11 0 32 (AMDpre then reduces the degree)W 1200 3049 m 11 0 32 (of all the adjacent nodes by 1. )W 1200 2445 m /NewCenturySchlbk-BoldR 600 ff 1 0 (2.3)A 16 0 32 1 0 ( Map)AW 16 0 32 (ping function.)W /NewCenturySchlbk-RomanR 600 ff 17 0 32 ( Once the nodes for submatrix )W /NewCenturySchlbk-BoldR 600 ff 16 0 32 (D )W /NewCenturySchlbk-RomanR 600 ff 17 0 32 (have been selected and)W 1200 2141 m 1 0 (ordered,)A 27 0 32 1 0 ( a re)AW 27 0 32 (cord is made of what nodes are in )W /NewCenturySchlbk-BoldR 600 ff 26 0 32 (A )W /NewCenturySchlbk-RomanR 600 ff 27 0 32 (and in )W /NewCenturySchlbk-BoldR 600 ff 26 0 32 (D. )W /NewCenturySchlbk-RomanR 600 ff 27 0 32 ( This is the primary)W 1200 1837 m 1 0 (functio)A (n)S 12 0 32 ( of section 3. This is called the mapping. This mapping is needed because)W ep %%Page: 5 5 bp /NewCenturySchlbk-RomanR 600 ff 0 13200 10200 co 5040 1263 m /CourierR 600 ff (5)S 1200 11845 m /NewCenturySchlbk-RomanR 600 ff 11 0 32 -1 0 (all the )AW 11 0 32 (numbers in submatrix )W /NewCenturySchlbk-BoldR 600 ff 10 0 32 (A )W /NewCenturySchlbk-RomanR 600 ff 11 0 32 (have to be sequentially renumbered. For example,)W 1200 11541 m -1 0 (given)A 8 0 32 -1 0 ( a matrix of size 5 and AMDpre finds that node )AW 9 0 32 -1 0 (2 is dense. It is then placed in)AW 1200 11239 m /NewCenturySchlbk-BoldR 600 ff -1 0 (D)A /NewCenturySchlbk-RomanR 600 ff -1 0 (.)A 8 0 32 -1 0 ( The nodes for submatrix )AW /NewCenturySchlbk-BoldR 600 ff 7 0 32 -1 0 (A )AW /NewCenturySchlbk-RomanR 600 ff 8 0 32 -1 0 (will be 1, )AW 9 0 32 -1 0 (3, 4, and 5. The node for submatrix )AW /NewCenturySchlbk-BoldR 600 ff 8 0 32 -1 0 (D )AW /NewCenturySchlbk-RomanR 600 ff 9 0 32 -1 0 (is 2.)AW 1200 10935 m (The)S 12 0 32 ( nodes in )W /NewCenturySchlbk-BoldR 600 ff 11 0 32 (A )W /NewCenturySchlbk-RomanR 600 ff 12 0 32 (will )W 11 0 32 (need to be renumbered. So the mapping is: 1 = 1, 2 = 3, 3 = 4,)W 1200 10631 m 11 0 32 (and 4 = 5. The 2 in )W /NewCenturySchlbk-BoldR 600 ff 10 0 32 (D)W /NewCenturySchlbk-RomanR 600 ff 11 0 32 ( is mapped to 5.)W 1200 10025 m /NewCenturySchlbk-BoldR 600 ff 10 0 32 -1 0 (2.4 Sending the submatrix. )AW /NewCenturySchlbk-RomanR 600 ff 11 0 32 -1 0 ( Section 4 eliminates the nodes in )AW 11 0 32 (submatrix )W /NewCenturySchlbk-BoldR 600 ff 10 0 32 (D )W /NewCenturySchlbk-RomanR 600 ff 11 0 32 (from)W 1200 9721 m -1 0 (the)A 10 0 32 -1 0 ( )AW /NewCenturySchlbk-ItalicR 600 ff 10 0 32 -1 0 (iw)AW /NewCenturySchlbk-RomanR 600 ff 10 0 32 -1 0 ( array. The )AW /NewCenturySchlbk-ItalicR 600 ff 10 0 32 -1 0 (pe)AW /NewCenturySchlbk-RomanR 600 ff 10 0 32 -1 0 ( array, which contains pointers )AW 11 0 32 -1 0 (to the )AW /NewCenturySchlbk-ItalicR 600 ff 11 0 32 -1 0 (iw)AW /NewCenturySchlbk-RomanR 600 ff 11 0 32 -1 0 ( array, is updated and)AW 1200 9419 m -2 0 (the)A 8 0 32 -2 0 ( )AW /NewCenturySchlbk-ItalicR 600 ff 8 0 32 -2 0 (len)AW /NewCenturySchlbk-RomanR 600 ff 8 0 32 -2 0 ( array is also updated to reflect )AW 9 0 32 -2 0 (only the nodes that are in submatrix )AW /NewCenturySchlbk-BoldR 600 ff 8 0 32 -2 0 (A. )AW /NewCenturySchlbk-RomanR 600 ff 9 0 32 -2 0 (AMD)AW 1200 9115 m 11 0 32 -1 0 (uses the )AW /NewCenturySchlbk-ItalicR 600 ff 11 0 32 -1 0 (iw )AW /NewCenturySchlbk-RomanR 600 ff 11 0 32 -1 0 (array to construct the graph of the matr)AW 11 0 32 (ix. Section 5 saves the original)W 1200 8813 m 11 0 32 (value of )W /NewCenturySchlbk-ItalicR 600 ff 11 0 32 (n)W /NewCenturySchlbk-RomanR 600 ff 11 0 32 ( then calls AMD with the new values of )W /NewCenturySchlbk-ItalicR 600 ff 11 0 32 (n, iw\(n\), pe\(n\), and len\(n\))W /NewCenturySchlbk-RomanR 600 ff 11 0 32 (.)W 1200 8209 m /NewCenturySchlbk-BoldR 600 ff 1 0 (2.5)A 41 0 32 1 0 ( Re)AW 41 0 32 (turning the permutation.)W /NewCenturySchlbk-RomanR 600 ff 42 0 32 ( After AMD returns the ordering, section 6)W 1200 7905 m 1 0 (restores)A 22 0 32 1 0 ( t)AW 22 0 32 (he original numbering to the submatrix )W /NewCenturySchlbk-BoldR 600 ff 21 0 32 (A.)W /NewCenturySchlbk-RomanR 600 ff 22 0 32 ( Section 7 makes the inverse)W 1200 7601 m -1 0 (permutation)A 8 0 32 -1 0 ( of the ordering and returns both the permutation and its inverse )AW 9 0 32 -1 0 (to the)AW 1200 7299 m 11 0 32 (calling program. )W 1200 6695 m /NewCenturySchlbk-BoldR 600 ff -1 0 (2.6)A 8 0 32 -1 0 ( A general AMDpre run-time analysis. )AW /NewCenturySchlbk-RomanR 600 ff 10 0 32 -1 0 (A casual glance at the algorithm may)AW 1200 6391 m 11 0 32 -1 0 (cause one to think )AW 11 0 32 (that section 2 may be the longest running function. On average)W 1200 6089 m -2 0 (section)A 7 0 32 -2 0 ( 4)AW /NewCenturySchlbk-BoldR 600 ff 6 0 32 -2 0 ( )AW /NewCenturySchlbk-RomanR 600 ff 7 0 32 -2 0 (will take the longest. )AW 8 0 32 -2 0 ( The run time of AMDpre is O\(|)AW /NewCenturySchlbk-ItalicR 600 ff 8 0 32 -2 0 (A)AW /NewCenturySchlbk-RomanR 600 ff 8 0 32 -2 0 (|\), where |)AW /NewCenturySchlbk-ItalicR 600 ff 8 0 32 -2 0 (A)AW /NewCenturySchlbk-RomanR 600 ff 8 0 32 -2 0 (| is the)AW 1200 5785 m 11 0 32 (number of non-zeroes in the matrix. )W 1200 5483 m 1800 5483 m 1 0 (Sectio)A (n)S 25 0 32 ( 4 contains a for-loop looping n times. On each loop, AMDpre looks)W 1200 5181 m -3 0 (through)A 9 0 32 -3 0 ( a part of the node adjacency list. The list has the length of )AW /NewCenturySchlbk-ItalicR 600 ff 9 0 32 -3 0 (iwlen)AW /NewCenturySchlbk-RomanR 600 ff 9 0 32 -3 0 (, )AW 10 0 32 -3 0 (where part)AW 1200 4879 m -3 0 (of)A 9 0 32 -3 0 ( that array contains all the non-zeroes in the matrix. The total non-zeroes )AW 10 0 32 -3 0 (in the list)AW 1200 4577 m (is)S 1 h 17 0 32 ( )W /NewCenturySchlbk-ItalicR 600 ff 17 0 32 (pfree)W /NewCenturySchlbk-RomanR 600 ff 17 0 32 ( -1. The part of the list section 4 looks at during a single loop is the nodes)W 1200 4275 m -1 0 (that)A 7 0 32 -1 0 ( are adjacent to the current node. AMDpre will only )AW 8 0 32 -1 0 (look at an entry in the list)AW 1200 3973 m -1 0 (on)A 11 0 32 (ce in the entire program. So, if it looked at a node\251s adjacency list in section 2 it)W 1200 3671 m 1 0 (will)A 12 0 32 1 0 ( not be lo)AW 12 0 32 (oking at that same node\251s list in section 4. )W 12 0 32 (Therefore, the run time of)W 1200 3369 m 11 0 32 (section 4 is O\(|)W /NewCenturySchlbk-ItalicR 600 ff 11 0 32 (A)W /NewCenturySchlbk-RomanR 600 ff 11 0 32 (|\). )W 1200 3068 m /NewCenturySchlbk-BoldR 600 ff 10 0 32 ( )W ep %%Page: 6 6 bp /NewCenturySchlbk-BoldR 600 ff 0 13200 10200 co mcm 1200 10186 tr 1 -1 sc np 0 0 m 15 0 li 15 681 li 0 681 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1331 0 li 1331 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 2532 10186 tr 1 -1 sc np 0 0 m 15 0 li 15 681 li 0 681 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1235 0 li 1235 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 3768 10186 tr 1 -1 sc np 0 0 m 15 0 li 15 681 li 0 681 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1235 0 li 1235 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 5004 10186 tr 1 -1 sc np 0 0 m 15 0 li 15 681 li 0 681 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 3993 0 li 3993 15 li 0 15 li cp 0 255 div g fill np 3978 0 m 3993 0 li 3993 681 li 3978 681 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 1200 9504 tr 1 -1 sc np 0 0 m 15 0 li 15 381 li 0 381 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1331 0 li 1331 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 2532 9504 tr 1 -1 sc np 0 0 m 15 0 li 15 381 li 0 381 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1235 0 li 1235 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 3768 9504 tr 1 -1 sc np 0 0 m 15 0 li 15 381 li 0 381 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1235 0 li 1235 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 5004 9504 tr 1 -1 sc np 0 0 m 15 0 li 15 381 li 0 381 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 3993 0 li 3993 15 li 0 15 li cp 0 255 div g fill np 3978 0 m 3993 0 li 3993 381 li 3978 381 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 1200 9122 tr 1 -1 sc np 0 0 m 15 0 li 15 379 li 0 379 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1331 0 li 1331 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 2532 9122 tr 1 -1 sc np 0 0 m 15 0 li 15 379 li 0 379 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1235 0 li 1235 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 3768 9122 tr 1 -1 sc np 0 0 m 15 0 li 15 379 li 0 379 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1235 0 li 1235 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 5004 9122 tr 1 -1 sc np 0 0 m 15 0 li 15 379 li 0 379 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 3993 0 li 3993 15 li 0 15 li cp 0 255 div g fill np 3978 0 m 3993 0 li 3993 379 li 3978 379 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 1200 8742 tr 1 -1 sc np 0 0 m 15 0 li 15 381 li 0 381 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1331 0 li 1331 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 2532 8742 tr 1 -1 sc np 0 0 m 15 0 li 15 381 li 0 381 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1235 0 li 1235 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 3768 8742 tr 1 -1 sc np 0 0 m 15 0 li 15 381 li 0 381 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1235 0 li 1235 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 5004 8742 tr 1 -1 sc np 0 0 m 15 0 li 15 381 li 0 381 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 3993 0 li 3993 15 li 0 15 li cp 0 255 div g fill np 3978 0 m 3993 0 li 3993 381 li 3978 381 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 1200 8360 tr 1 -1 sc np 0 0 m 15 0 li 15 379 li 0 379 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1331 0 li 1331 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 2532 8360 tr 1 -1 sc np 0 0 m 15 0 li 15 379 li 0 379 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1235 0 li 1235 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 3768 8360 tr 1 -1 sc np 0 0 m 15 0 li 15 379 li 0 379 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1235 0 li 1235 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 5004 8360 tr 1 -1 sc np 0 0 m 15 0 li 15 379 li 0 379 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 3993 0 li 3993 15 li 0 15 li cp 0 255 div g fill np 3978 0 m 3993 0 li 3993 379 li 3978 379 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 1200 7980 tr 1 -1 sc np 0 0 m 15 0 li 15 381 li 0 381 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1331 0 li 1331 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 2532 7980 tr 1 -1 sc np 0 0 m 15 0 li 15 381 li 0 381 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1235 0 li 1235 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 3768 7980 tr 1 -1 sc np 0 0 m 15 0 li 15 381 li 0 381 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1235 0 li 1235 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 5004 7980 tr 1 -1 sc np 0 0 m 15 0 li 15 381 li 0 381 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 3993 0 li 3993 15 li 0 15 li cp 0 255 div g fill np 3978 0 m 3993 0 li 3993 381 li 3978 381 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 1200 7598 tr 1 -1 sc np 0 0 m 15 0 li 15 379 li 0 379 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1331 0 li 1331 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 2532 7598 tr 1 -1 sc np 0 0 m 15 0 li 15 379 li 0 379 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1235 0 li 1235 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 3768 7598 tr 1 -1 sc np 0 0 m 15 0 li 15 379 li 0 379 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1235 0 li 1235 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 5004 7598 tr 1 -1 sc np 0 0 m 15 0 li 15 379 li 0 379 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 3993 0 li 3993 15 li 0 15 li cp 0 255 div g fill np 3978 0 m 3993 0 li 3993 379 li 3978 379 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 1200 7218 tr 1 -1 sc np 0 0 m 15 0 li 15 381 li 0 381 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1331 0 li 1331 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 2532 7218 tr 1 -1 sc np 0 0 m 15 0 li 15 381 li 0 381 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1235 0 li 1235 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 3768 7218 tr 1 -1 sc np 0 0 m 15 0 li 15 381 li 0 381 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1235 0 li 1235 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 5004 7218 tr 1 -1 sc np 0 0 m 15 0 li 15 381 li 0 381 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 3993 0 li 3993 15 li 0 15 li cp 0 255 div g fill np 3978 0 m 3993 0 li 3993 381 li 3978 381 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 1200 6836 tr 1 -1 sc np 0 0 m 15 0 li 15 379 li 0 379 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1331 0 li 1331 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 2532 6836 tr 1 -1 sc np 0 0 m 15 0 li 15 379 li 0 379 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1235 0 li 1235 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 3768 6836 tr 1 -1 sc np 0 0 m 15 0 li 15 379 li 0 379 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1235 0 li 1235 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 5004 6836 tr 1 -1 sc np 0 0 m 15 0 li 15 379 li 0 379 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 3993 0 li 3993 15 li 0 15 li cp 0 255 div g fill np 3978 0 m 3993 0 li 3993 379 li 3978 379 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 1200 6456 tr 1 -1 sc np 0 0 m 15 0 li 15 381 li 0 381 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1331 0 li 1331 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 2532 6456 tr 1 -1 sc np 0 0 m 15 0 li 15 381 li 0 381 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1235 0 li 1235 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 3768 6456 tr 1 -1 sc np 0 0 m 15 0 li 15 381 li 0 381 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1235 0 li 1235 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 5004 6456 tr 1 -1 sc np 0 0 m 15 0 li 15 381 li 0 381 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 3993 0 li 3993 15 li 0 15 li cp 0 255 div g fill np 3978 0 m 3993 0 li 3993 381 li 3978 381 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 1200 6074 tr 1 -1 sc np 0 0 m 15 0 li 15 379 li 0 379 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1331 0 li 1331 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 2532 6074 tr 1 -1 sc np 0 0 m 15 0 li 15 379 li 0 379 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1235 0 li 1235 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 3768 6074 tr 1 -1 sc np 0 0 m 15 0 li 15 379 li 0 379 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1235 0 li 1235 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 5004 6074 tr 1 -1 sc np 0 0 m 15 0 li 15 379 li 0 379 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 3993 0 li 3993 15 li 0 15 li cp 0 255 div g fill np 3978 0 m 3993 0 li 3993 379 li 3978 379 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 1200 5694 tr 1 -1 sc np 0 0 m 15 0 li 15 381 li 0 381 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1331 0 li 1331 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 2532 5694 tr 1 -1 sc np 0 0 m 15 0 li 15 381 li 0 381 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1235 0 li 1235 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 3768 5694 tr 1 -1 sc np 0 0 m 15 0 li 15 381 li 0 381 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1235 0 li 1235 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 5004 5694 tr 1 -1 sc np 0 0 m 15 0 li 15 381 li 0 381 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 3993 0 li 3993 15 li 0 15 li cp 0 255 div g fill np 3978 0 m 3993 0 li 3993 381 li 3978 381 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 1200 5312 tr 1 -1 sc np 0 0 m 15 0 li 15 379 li 0 379 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1331 0 li 1331 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 2532 5312 tr 1 -1 sc np 0 0 m 15 0 li 15 379 li 0 379 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1235 0 li 1235 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 3768 5312 tr 1 -1 sc np 0 0 m 15 0 li 15 379 li 0 379 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1235 0 li 1235 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 5004 5312 tr 1 -1 sc np 0 0 m 15 0 li 15 379 li 0 379 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 3993 0 li 3993 15 li 0 15 li cp 0 255 div g fill np 3978 0 m 3993 0 li 3993 379 li 3978 379 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 1200 4932 tr 1 -1 sc np 0 0 m 15 0 li 15 381 li 0 381 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1331 0 li 1331 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 2532 4932 tr 1 -1 sc np 0 0 m 15 0 li 15 381 li 0 381 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1235 0 li 1235 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 3768 4932 tr 1 -1 sc np 0 0 m 15 0 li 15 381 li 0 381 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1235 0 li 1235 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 5004 4932 tr 1 -1 sc np 0 0 m 15 0 li 15 381 li 0 381 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 3993 0 li 3993 15 li 0 15 li cp 0 255 div g fill np 3978 0 m 3993 0 li 3993 381 li 3978 381 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 1200 4550 tr 1 -1 sc np 0 0 m 15 0 li 15 379 li 0 379 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1331 0 li 1331 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 2532 4550 tr 1 -1 sc np 0 0 m 15 0 li 15 379 li 0 379 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1235 0 li 1235 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 3768 4550 tr 1 -1 sc np 0 0 m 15 0 li 15 379 li 0 379 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1235 0 li 1235 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 5004 4550 tr 1 -1 sc np 0 0 m 15 0 li 15 379 li 0 379 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 3993 0 li 3993 15 li 0 15 li cp 0 255 div g fill np 3978 0 m 3993 0 li 3993 379 li 3978 379 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 1200 4170 tr 1 -1 sc np 0 0 m 15 0 li 15 381 li 0 381 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1331 0 li 1331 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 2532 4170 tr 1 -1 sc np 0 0 m 15 0 li 15 381 li 0 381 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1235 0 li 1235 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 3768 4170 tr 1 -1 sc np 0 0 m 15 0 li 15 381 li 0 381 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1235 0 li 1235 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 5004 4170 tr 1 -1 sc np 0 0 m 15 0 li 15 381 li 0 381 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 3993 0 li 3993 15 li 0 15 li cp 0 255 div g fill np 3978 0 m 3993 0 li 3993 381 li 3978 381 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 1200 3788 tr 1 -1 sc np 0 0 m 15 0 li 15 379 li 0 379 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1331 0 li 1331 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 2532 3788 tr 1 -1 sc np 0 0 m 15 0 li 15 379 li 0 379 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1235 0 li 1235 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 3768 3788 tr 1 -1 sc np 0 0 m 15 0 li 15 379 li 0 379 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1235 0 li 1235 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 5004 3788 tr 1 -1 sc np 0 0 m 15 0 li 15 379 li 0 379 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 3993 0 li 3993 15 li 0 15 li cp 0 255 div g fill np 3978 0 m 3993 0 li 3993 379 li 3978 379 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 1200 3408 tr 1 -1 sc np 0 0 m 15 0 li 15 381 li 0 381 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1331 0 li 1331 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 2532 3408 tr 1 -1 sc np 0 0 m 15 0 li 15 381 li 0 381 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1235 0 li 1235 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 3768 3408 tr 1 -1 sc np 0 0 m 15 0 li 15 381 li 0 381 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1235 0 li 1235 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 5004 3408 tr 1 -1 sc np 0 0 m 15 0 li 15 381 li 0 381 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 3993 0 li 3993 15 li 0 15 li cp 0 255 div g fill np 3978 0 m 3993 0 li 3993 381 li 3978 381 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 1200 3026 tr 1 -1 sc np 0 0 m 15 0 li 15 379 li 0 379 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1331 0 li 1331 15 li 0 15 li cp 0 255 div g fill np 0 364 m 1331 364 li 1331 379 li 0 379 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 2532 3026 tr 1 -1 sc np 0 0 m 15 0 li 15 379 li 0 379 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1235 0 li 1235 15 li 0 15 li cp 0 255 div g fill np 0 364 m 1235 364 li 1235 379 li 0 379 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 3768 3026 tr 1 -1 sc np 0 0 m 15 0 li 15 379 li 0 379 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1235 0 li 1235 15 li 0 15 li cp 0 255 div g fill np 0 364 m 1235 364 li 1235 379 li 0 379 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 5004 3026 tr 1 -1 sc np 0 0 m 15 0 li 15 379 li 0 379 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 3993 0 li 3993 15 li 0 15 li cp 0 255 div g fill np 3978 0 m 3993 0 li 3993 379 li 3978 379 li cp 0 255 div g fill np 0 364 m 3993 364 li 3993 379 li 0 379 li cp 0 255 div g fill 0 w 0 lc sm icl 5040 1263 m /CourierR 600 ff 0 255 div g (6)S 1200 11846 m /NewCenturySchlbk-BoldR 600 ff 10 0 32 (3 Sparse matrices Run time analysis.)W /NewCenturySchlbk-RomanR 600 ff 1200 11241 m /NewCenturySchlbk-BoldR 600 ff -2 0 (3.1)A 8 0 32 -2 0 ( Sparse Matrices )AW 9 0 32 -2 0 (used.)AW /NewCenturySchlbk-RomanR 600 ff 10 0 32 -2 0 ( The matrices in Table 1 are a sampling of 520 matrices)AW 1200 10937 m -2 0 (used)A 7 0 32 -2 0 ( during the testing phase of AMDpre. Only the matrices in Table 1 )AW 8 0 32 -2 0 (will be used)AW 1200 10635 m 11 0 32 (in this paper.)W 1300 9931 m (Matrix)S 2632 9931 m (Matrix)S 2632 9629 m (order)S 3868 9931 m 11 0 32 (number of)W 3868 9629 m (nonzeros)S 5104 9931 m (description)S 1300 9248 m (BCSSTK29)S 2632 9248 m (13992)S 3868 9248 m (619488)S 5104 9248 m 11 0 32 (Structural engineering)W 1300 8867 m (BCSSTK30)S 2632 8867 m (28924)S 3868 8867 m (2043492)S 5104 8867 m 11 0 32 (Structural engineering)W 1300 8486 m (BCSSTK31)S 2632 8486 m (35588)S 3868 8486 m (1181416)S 5104 8486 m 11 0 32 (Structural engineering)W 1300 8105 m (BCSSTK32)S 2632 8105 m (44609)S 3868 8105 m (2014701)S 5104 8105 m 11 0 32 (Structural engineering)W 1300 7724 m (CT20STIF)S 2632 7724 m (52329)S 3868 7724 m (2698463)S 5104 7724 m 11 0 32 (Structural engineering)W 1300 7343 m (CRYSTK03)S 2632 7343 m (24696)S 3868 7343 m (1751178)S 5104 7343 m 11 0 32 (Structural engineering)W 1300 6962 m (EX11)S 2632 6962 m (16614)S 3868 6962 m (1096948)S 5104 6962 m 11 0 32 (Test matrix from FIDAP)W 1300 6581 m (EX19)S 2632 6581 m (12005)S 3868 6581 m (259879)S 5104 6581 m 11 0 32 (Test matrix from FIDAP)W 1300 6200 m (NASASRB)S 2632 6200 m (54870)S 3868 6200 m (2677324)S 5104 6200 m 11 0 32 (Shuttle Rocket Booster)W 1300 5819 m (AF23560)S 2632 5819 m (23560)S 3868 5819 m (484256)S 5104 5819 m 11 0 32 (Linear programming problem)W 1300 5438 m (LHR34)S 2632 5438 m (35152)S 3868 5438 m (764014)S 5104 5438 m 11 0 32 (Light hydrocarbon recovery)W 1300 5057 m (BBMAT)S 2632 5057 m (38744)S 3868 5057 m (1771722)S 5104 5057 m 11 0 32 (2D airfoil exact Jacobian)W 1300 4676 m (VENKAT50)S 2632 4676 m (62425)S 3868 4676 m (1780217)S 5104 4676 m 11 0 32 (Structural engineering )W 1300 4295 m (APPU)S 2632 4295 m (14000)S 3868 4295 m (1853104)S 5104 4295 m 11 0 32 (NASA test random matrix)W 1300 3914 m (WANG3)S 2632 3914 m (26064)S 3868 3914 m (177168)S 5104 3914 m 11 0 32 (Discretized electron continuity)W 1300 3533 m (GUPTA1)S 2632 3533 m (31802)S 3868 3533 m (2164210)S 5104 3533 m 11 0 32 (Linear programming problem)W 1300 3152 m (GUPTA2)S 2632 3152 m (62064)S 3868 3152 m (4248286)S 5104 3152 m 11 0 32 (Linear programming problem)W 1300 2771 m (GUPTA3)S 2632 2771 m (16783)S 3868 2771 m (9323427)S 5104 2771 m 11 0 32 (Linear programming problem)W 3335 2189 m /NewCenturySchlbk-BoldR 600 ff 10 0 32 (Table 1: Selected sparse matrices.)W /NewCenturySchlbk-RomanR 600 ff ep %%Page: 7 7 bp /NewCenturySchlbk-BoldR 600 ff 0 13200 10200 co mcm 1908 10486 tr 1 -1 sc np 0 0 m 15 0 li 15 681 li 0 681 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1331 0 li 1331 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 3240 10486 tr 1 -1 sc np 0 0 m 15 0 li 15 681 li 0 681 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1559 0 li 1559 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 4800 10486 tr 1 -1 sc np 0 0 m 15 0 li 15 681 li 0 681 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1163 0 li 1163 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 5964 10486 tr 1 -1 sc np 0 0 m 15 0 li 15 681 li 0 681 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1163 0 li 1163 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 7128 10486 tr 1 -1 sc np 0 0 m 15 0 li 15 681 li 0 681 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1161 0 li 1161 15 li 0 15 li cp 0 255 div g fill np 1146 0 m 1161 0 li 1161 681 li 1146 681 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 1908 9804 tr 1 -1 sc np 0 0 m 15 0 li 15 381 li 0 381 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1331 0 li 1331 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 3240 9804 tr 1 -1 sc np 0 0 m 15 0 li 15 381 li 0 381 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1559 0 li 1559 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 4800 9804 tr 1 -1 sc np 0 0 m 15 0 li 15 381 li 0 381 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1163 0 li 1163 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 5964 9804 tr 1 -1 sc np 0 0 m 15 0 li 15 381 li 0 381 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1163 0 li 1163 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 7128 9804 tr 1 -1 sc np 0 0 m 15 0 li 15 381 li 0 381 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1161 0 li 1161 15 li 0 15 li cp 0 255 div g fill np 1146 0 m 1161 0 li 1161 381 li 1146 381 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 1908 9422 tr 1 -1 sc np 0 0 m 15 0 li 15 379 li 0 379 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1331 0 li 1331 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 3240 9422 tr 1 -1 sc np 0 0 m 15 0 li 15 379 li 0 379 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1559 0 li 1559 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 4800 9422 tr 1 -1 sc np 0 0 m 15 0 li 15 379 li 0 379 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1163 0 li 1163 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 5964 9422 tr 1 -1 sc np 0 0 m 15 0 li 15 379 li 0 379 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1163 0 li 1163 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 7128 9422 tr 1 -1 sc np 0 0 m 15 0 li 15 379 li 0 379 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1161 0 li 1161 15 li 0 15 li cp 0 255 div g fill np 1146 0 m 1161 0 li 1161 379 li 1146 379 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 1908 9042 tr 1 -1 sc np 0 0 m 15 0 li 15 381 li 0 381 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1331 0 li 1331 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 3240 9042 tr 1 -1 sc np 0 0 m 15 0 li 15 381 li 0 381 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1559 0 li 1559 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 4800 9042 tr 1 -1 sc np 0 0 m 15 0 li 15 381 li 0 381 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1163 0 li 1163 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 5964 9042 tr 1 -1 sc np 0 0 m 15 0 li 15 381 li 0 381 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1163 0 li 1163 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 7128 9042 tr 1 -1 sc np 0 0 m 15 0 li 15 381 li 0 381 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1161 0 li 1161 15 li 0 15 li cp 0 255 div g fill np 1146 0 m 1161 0 li 1161 381 li 1146 381 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 1908 8660 tr 1 -1 sc np 0 0 m 15 0 li 15 379 li 0 379 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1331 0 li 1331 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 3240 8660 tr 1 -1 sc np 0 0 m 15 0 li 15 379 li 0 379 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1559 0 li 1559 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 4800 8660 tr 1 -1 sc np 0 0 m 15 0 li 15 379 li 0 379 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1163 0 li 1163 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 5964 8660 tr 1 -1 sc np 0 0 m 15 0 li 15 379 li 0 379 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1163 0 li 1163 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 7128 8660 tr 1 -1 sc np 0 0 m 15 0 li 15 379 li 0 379 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1161 0 li 1161 15 li 0 15 li cp 0 255 div g fill np 1146 0 m 1161 0 li 1161 379 li 1146 379 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 1908 8280 tr 1 -1 sc np 0 0 m 15 0 li 15 381 li 0 381 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1331 0 li 1331 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 3240 8280 tr 1 -1 sc np 0 0 m 15 0 li 15 381 li 0 381 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1559 0 li 1559 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 4800 8280 tr 1 -1 sc np 0 0 m 15 0 li 15 381 li 0 381 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1163 0 li 1163 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 5964 8280 tr 1 -1 sc np 0 0 m 15 0 li 15 381 li 0 381 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1163 0 li 1163 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 7128 8280 tr 1 -1 sc np 0 0 m 15 0 li 15 381 li 0 381 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1161 0 li 1161 15 li 0 15 li cp 0 255 div g fill np 1146 0 m 1161 0 li 1161 381 li 1146 381 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 1908 7898 tr 1 -1 sc np 0 0 m 15 0 li 15 379 li 0 379 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1331 0 li 1331 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 3240 7898 tr 1 -1 sc np 0 0 m 15 0 li 15 379 li 0 379 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1559 0 li 1559 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 4800 7898 tr 1 -1 sc np 0 0 m 15 0 li 15 379 li 0 379 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1163 0 li 1163 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 5964 7898 tr 1 -1 sc np 0 0 m 15 0 li 15 379 li 0 379 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1163 0 li 1163 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 7128 7898 tr 1 -1 sc np 0 0 m 15 0 li 15 379 li 0 379 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1161 0 li 1161 15 li 0 15 li cp 0 255 div g fill np 1146 0 m 1161 0 li 1161 379 li 1146 379 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 1908 7518 tr 1 -1 sc np 0 0 m 15 0 li 15 381 li 0 381 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1331 0 li 1331 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 3240 7518 tr 1 -1 sc np 0 0 m 15 0 li 15 381 li 0 381 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1559 0 li 1559 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 4800 7518 tr 1 -1 sc np 0 0 m 15 0 li 15 381 li 0 381 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1163 0 li 1163 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 5964 7518 tr 1 -1 sc np 0 0 m 15 0 li 15 381 li 0 381 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1163 0 li 1163 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 7128 7518 tr 1 -1 sc np 0 0 m 15 0 li 15 381 li 0 381 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1161 0 li 1161 15 li 0 15 li cp 0 255 div g fill np 1146 0 m 1161 0 li 1161 381 li 1146 381 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 1908 7136 tr 1 -1 sc np 0 0 m 15 0 li 15 379 li 0 379 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1331 0 li 1331 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 3240 7136 tr 1 -1 sc np 0 0 m 15 0 li 15 379 li 0 379 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1559 0 li 1559 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 4800 7136 tr 1 -1 sc np 0 0 m 15 0 li 15 379 li 0 379 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1163 0 li 1163 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 5964 7136 tr 1 -1 sc np 0 0 m 15 0 li 15 379 li 0 379 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1163 0 li 1163 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 7128 7136 tr 1 -1 sc np 0 0 m 15 0 li 15 379 li 0 379 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1161 0 li 1161 15 li 0 15 li cp 0 255 div g fill np 1146 0 m 1161 0 li 1161 379 li 1146 379 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 1908 6756 tr 1 -1 sc np 0 0 m 15 0 li 15 381 li 0 381 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1331 0 li 1331 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 3240 6756 tr 1 -1 sc np 0 0 m 15 0 li 15 381 li 0 381 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1559 0 li 1559 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 4800 6756 tr 1 -1 sc np 0 0 m 15 0 li 15 381 li 0 381 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1163 0 li 1163 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 5964 6756 tr 1 -1 sc np 0 0 m 15 0 li 15 381 li 0 381 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1163 0 li 1163 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 7128 6756 tr 1 -1 sc np 0 0 m 15 0 li 15 381 li 0 381 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1161 0 li 1161 15 li 0 15 li cp 0 255 div g fill np 1146 0 m 1161 0 li 1161 381 li 1146 381 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 1908 6374 tr 1 -1 sc np 0 0 m 15 0 li 15 379 li 0 379 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1331 0 li 1331 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 3240 6374 tr 1 -1 sc np 0 0 m 15 0 li 15 379 li 0 379 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1559 0 li 1559 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 4800 6374 tr 1 -1 sc np 0 0 m 15 0 li 15 379 li 0 379 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1163 0 li 1163 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 5964 6374 tr 1 -1 sc np 0 0 m 15 0 li 15 379 li 0 379 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1163 0 li 1163 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 7128 6374 tr 1 -1 sc np 0 0 m 15 0 li 15 379 li 0 379 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1161 0 li 1161 15 li 0 15 li cp 0 255 div g fill np 1146 0 m 1161 0 li 1161 379 li 1146 379 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 1908 5994 tr 1 -1 sc np 0 0 m 15 0 li 15 381 li 0 381 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1331 0 li 1331 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 3240 5994 tr 1 -1 sc np 0 0 m 15 0 li 15 381 li 0 381 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1559 0 li 1559 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 4800 5994 tr 1 -1 sc np 0 0 m 15 0 li 15 381 li 0 381 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1163 0 li 1163 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 5964 5994 tr 1 -1 sc np 0 0 m 15 0 li 15 381 li 0 381 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1163 0 li 1163 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 7128 5994 tr 1 -1 sc np 0 0 m 15 0 li 15 381 li 0 381 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1161 0 li 1161 15 li 0 15 li cp 0 255 div g fill np 1146 0 m 1161 0 li 1161 381 li 1146 381 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 1908 5612 tr 1 -1 sc np 0 0 m 15 0 li 15 379 li 0 379 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1331 0 li 1331 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 3240 5612 tr 1 -1 sc np 0 0 m 15 0 li 15 379 li 0 379 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1559 0 li 1559 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 4800 5612 tr 1 -1 sc np 0 0 m 15 0 li 15 379 li 0 379 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1163 0 li 1163 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 5964 5612 tr 1 -1 sc np 0 0 m 15 0 li 15 379 li 0 379 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1163 0 li 1163 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 7128 5612 tr 1 -1 sc np 0 0 m 15 0 li 15 379 li 0 379 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1161 0 li 1161 15 li 0 15 li cp 0 255 div g fill np 1146 0 m 1161 0 li 1161 379 li 1146 379 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 1908 5232 tr 1 -1 sc np 0 0 m 15 0 li 15 381 li 0 381 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1331 0 li 1331 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 3240 5232 tr 1 -1 sc np 0 0 m 15 0 li 15 381 li 0 381 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1559 0 li 1559 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 4800 5232 tr 1 -1 sc np 0 0 m 15 0 li 15 381 li 0 381 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1163 0 li 1163 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 5964 5232 tr 1 -1 sc np 0 0 m 15 0 li 15 381 li 0 381 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1163 0 li 1163 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 7128 5232 tr 1 -1 sc np 0 0 m 15 0 li 15 381 li 0 381 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1161 0 li 1161 15 li 0 15 li cp 0 255 div g fill np 1146 0 m 1161 0 li 1161 381 li 1146 381 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 1908 4850 tr 1 -1 sc np 0 0 m 15 0 li 15 379 li 0 379 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1331 0 li 1331 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 3240 4850 tr 1 -1 sc np 0 0 m 15 0 li 15 379 li 0 379 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1559 0 li 1559 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 4800 4850 tr 1 -1 sc np 0 0 m 15 0 li 15 379 li 0 379 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1163 0 li 1163 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 5964 4850 tr 1 -1 sc np 0 0 m 15 0 li 15 379 li 0 379 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1163 0 li 1163 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 7128 4850 tr 1 -1 sc np 0 0 m 15 0 li 15 379 li 0 379 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1161 0 li 1161 15 li 0 15 li cp 0 255 div g fill np 1146 0 m 1161 0 li 1161 379 li 1146 379 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 1908 4470 tr 1 -1 sc np 0 0 m 15 0 li 15 381 li 0 381 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1331 0 li 1331 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 3240 4470 tr 1 -1 sc np 0 0 m 15 0 li 15 381 li 0 381 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1559 0 li 1559 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 4800 4470 tr 1 -1 sc np 0 0 m 15 0 li 15 381 li 0 381 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1163 0 li 1163 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 5964 4470 tr 1 -1 sc np 0 0 m 15 0 li 15 381 li 0 381 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1163 0 li 1163 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 7128 4470 tr 1 -1 sc np 0 0 m 15 0 li 15 381 li 0 381 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1161 0 li 1161 15 li 0 15 li cp 0 255 div g fill np 1146 0 m 1161 0 li 1161 381 li 1146 381 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 1908 4088 tr 1 -1 sc np 0 0 m 15 0 li 15 379 li 0 379 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1331 0 li 1331 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 3240 4088 tr 1 -1 sc np 0 0 m 15 0 li 15 379 li 0 379 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1559 0 li 1559 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 4800 4088 tr 1 -1 sc np 0 0 m 15 0 li 15 379 li 0 379 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1163 0 li 1163 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 5964 4088 tr 1 -1 sc np 0 0 m 15 0 li 15 379 li 0 379 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1163 0 li 1163 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 7128 4088 tr 1 -1 sc np 0 0 m 15 0 li 15 379 li 0 379 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1161 0 li 1161 15 li 0 15 li cp 0 255 div g fill np 1146 0 m 1161 0 li 1161 379 li 1146 379 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 1908 3708 tr 1 -1 sc np 0 0 m 15 0 li 15 381 li 0 381 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1331 0 li 1331 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 3240 3708 tr 1 -1 sc np 0 0 m 15 0 li 15 381 li 0 381 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1559 0 li 1559 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 4800 3708 tr 1 -1 sc np 0 0 m 15 0 li 15 381 li 0 381 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1163 0 li 1163 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 5964 3708 tr 1 -1 sc np 0 0 m 15 0 li 15 381 li 0 381 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1163 0 li 1163 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 7128 3708 tr 1 -1 sc np 0 0 m 15 0 li 15 381 li 0 381 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1161 0 li 1161 15 li 0 15 li cp 0 255 div g fill np 1146 0 m 1161 0 li 1161 381 li 1146 381 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 1908 3326 tr 1 -1 sc np 0 0 m 15 0 li 15 379 li 0 379 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1331 0 li 1331 15 li 0 15 li cp 0 255 div g fill np 0 364 m 1331 364 li 1331 379 li 0 379 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 3240 3326 tr 1 -1 sc np 0 0 m 15 0 li 15 379 li 0 379 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1559 0 li 1559 15 li 0 15 li cp 0 255 div g fill np 0 364 m 1559 364 li 1559 379 li 0 379 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 4800 3326 tr 1 -1 sc np 0 0 m 15 0 li 15 379 li 0 379 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1163 0 li 1163 15 li 0 15 li cp 0 255 div g fill np 0 364 m 1163 364 li 1163 379 li 0 379 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 5964 3326 tr 1 -1 sc np 0 0 m 15 0 li 15 379 li 0 379 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1163 0 li 1163 15 li 0 15 li cp 0 255 div g fill np 0 364 m 1163 364 li 1163 379 li 0 379 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 7128 3326 tr 1 -1 sc np 0 0 m 15 0 li 15 379 li 0 379 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1161 0 li 1161 15 li 0 15 li cp 0 255 div g fill np 1146 0 m 1161 0 li 1161 379 li 1146 379 li cp 0 255 div g fill np 0 364 m 1161 364 li 1161 379 li 0 379 li cp 0 255 div g fill 0 w 0 lc sm icl 5040 1263 m /CourierR 600 ff 0 255 div g (7)S 1200 11845 m /NewCenturySchlbk-BoldR 600 ff (3.2)S 28 0 32 ( AMD and AMDpre ordering time for sparse matrices. )W /NewCenturySchlbk-RomanR 600 ff 29 0 32 (Table 3 lists the)W 1200 11541 m 1 0 (orderi)A (ng)S 29 0 32 ( times for the selected matrices. Column 3 is the ordering time of AMD)W 1200 11239 m 1 0 (wi)A (thout)S 29 0 32 ( any attempt at preprocessing, and column 4 is AMDpre. For most of the)W 1200 10937 m 11 0 32 (matrices no preprocessing is necessary )W /NewCenturySchlbk-BoldR 600 ff 10 0 32 ( )W 2008 10231 m /NewCenturySchlbk-RomanR 600 ff (Matrix)S 3340 10231 m 11 0 32 (Matrix order)W 4900 10231 m (AMD)S 4900 9929 m (time)S 6064 10231 m (AMDpre)S 6064 9929 m 11 0 32 (time )W 7228 10231 m 11 0 32 (Rows torn)W 2008 9548 m (BCSSTK29)S 4145 9548 m (13992)S 5586 9548 m (.19)S 6750 9548 m (.19)S 8081 9548 m (0)S 2008 9167 m (BCSSTK30)S 4145 9167 m (28924)S 5578 9168 m /NewCenturySchlbk-BoldR 600 ff (.47)S /NewCenturySchlbk-RomanR 600 ff 6750 9167 m (.62)S 7970 9167 m (96)S 2008 8786 m (BCSSTK31)S 4145 8786 m (35588)S 5586 8786 m (.71)S 6750 8786 m (.71)S 8081 8786 m (0)S 2008 8405 m (BCSSTK32)S 4145 8405 m (44609)S 5578 8406 m /NewCenturySchlbk-BoldR 600 ff (.64)S /NewCenturySchlbk-RomanR 600 ff 6750 8405 m (.80)S 8081 8405 m (4)S 2008 8024 m (CT20STIF)S 4145 8024 m (52329)S 5586 8024 m (.91)S 6750 8024 m (.91)S 8081 8024 m (0)S 2008 7643 m (CRYSTK03)S 4145 7643 m (24696)S 5586 7643 m (.44)S 6750 7643 m (.44)S 8081 7643 m (0)S 2008 7262 m (EX11)S 4145 7262 m (16614)S 5586 7262 m (.41)S 6750 7262 m (.41)S 8081 7262 m (0)S 2008 6881 m (EX19)S 4145 6881 m (12005)S 5586 6881 m (.16)S 6750 6881 m (.16)S 8081 6881 m (0)S 2008 6500 m (NASASRB)S 4145 6500 m (54870)S 5578 6501 m /NewCenturySchlbk-BoldR 600 ff (.98)S /NewCenturySchlbk-RomanR 600 ff 6639 6500 m (1.19)S 7970 6500 m (12)S 2008 6119 m (AF23560)S 4145 6119 m (23560)S 5475 6119 m (1.19)S 6639 6119 m (1.20)S 8081 6119 m (0)S 2008 5738 m (LHR34)S 4145 5738 m (35152)S 5475 5738 m (2.22)S 6639 5738 m (2.22)S 8081 5738 m (0)S 2008 5357 m (BBMAT)S 4145 5357 m (38744)S 5475 5357 m (3.49)S 6639 5357 m (3.50)S 8081 5357 m (0)S 2008 4976 m (VENKAT50)S 4145 4976 m (62425)S 5586 4976 m (.59)S 6750 4976 m (.60)S 8081 4976 m (0)S 2008 4595 m (APPU)S 4145 4595 m (14000)S 5364 4595 m (10.03)S 6627 4596 m /NewCenturySchlbk-BoldR 600 ff (4.56)S /NewCenturySchlbk-RomanR 600 ff 7748 4595 m (6497)S 2008 4214 m (WANG3)S 4145 4214 m (26064)S 5586 4214 m (.77)S 6750 4214 m (.77)S 8081 4214 m (0)S 2008 3833 m (GUPTA1)S 4145 3833 m (31802)S 5253 3833 m (563.40)S 6742 3834 m /NewCenturySchlbk-BoldR 600 ff (.72)S /NewCenturySchlbk-RomanR 600 ff 7859 3833 m (676)S 2008 3452 m (GUPTA2)S 4145 3452 m (62064)S 5142 3452 m (1655.07)S 6627 3453 m /NewCenturySchlbk-BoldR 600 ff (4.29)S /NewCenturySchlbk-RomanR 600 ff 7748 3452 m (1193)S 2008 3071 m (GUPTA3)S 4145 3071 m (16783)S 5253 3071 m (147.66)S 6742 3072 m /NewCenturySchlbk-BoldR 600 ff (.83)S /NewCenturySchlbk-RomanR 600 ff 7748 3071 m (1347)S 2979 2489 m /NewCenturySchlbk-BoldR 600 ff 10 0 32 (Table 3: Sparse matrices ordering times )W 4441 2187 m 10 0 32 (\(in seconds\) )W ep %%Page: 8 8 bp /NewCenturySchlbk-RomanR 600 ff 0 13200 10200 co 5040 1263 m /CourierR 600 ff (8)S 1200 11241 m /NewCenturySchlbk-RomanR 600 ff 1800 11241 m -3 0 (For)A 6 0 32 -3 0 ( the matrix BCSSTK30, 96 dense rows )AW 7 0 32 -3 0 (where removed. Note, however, that)AW 1200 10939 m 1 0 (this)A 17 0 32 1 0 ( )AW 17 0 32 (removal did not yield a positive change in run time. This is because those 96)W 1200 10637 m -1 0 (rows)A 10 0 32 -1 0 ( have )AW 11 0 32 -1 0 (degrees that were not significantly higher than the average density. The)AW 1200 10335 m 1 0 (av)A (erage)S 16 0 32 ( density for BCSSTK30 is 69.7 with a standard deviation of 31.7. While is)W 1200 10033 m 1 0 (possible)A 39 0 32 ( to change the value of the threshold, getting a better ordering time for)W 1200 9731 m 11 0 32 -1 0 (BCSSTK30 is not. This is because tho)AW 11 0 32 (se 96 rows each have densities that are close)W 1200 9429 m 11 0 32 (to the threshold and not significantly high enough to decrease AMD ordering time.)W 1200 9127 m 1800 9127 m 1 0 (The)A 28 0 32 1 0 ( NASA)AW 28 0 32 (SRB matrix has a different distribution. The NASASRB has an)W 1200 8825 m 1 0 (average)A 20 0 32 1 0 ( )AW 20 0 32 (density of 47.8 with a standard deviation of 8.5. The square root of n for)W 1200 8523 m (NASASRB)S 12 0 32 ( is 234 which is 21 standard deviations )W 11 0 32 ( from the average. Removing 12)W 1200 8221 m 1 0 (rows)A 68 0 32 1 0 ( )AW 68 0 32 (from 54870, or .0002 percent, caused an increase in the ordering time.)W 1200 7919 m -1 0 (Compared)A 8 0 32 -1 0 ( to the size of this matrix these 12 rows are not very )AW 9 0 32 -1 0 (dense and, therefore,)AW 1200 7617 m 11 0 32 (this matrix needs no preprocessing.)W 1200 7315 m 1800 7315 m -2 0 (One)A 10 0 32 -2 0 ( of the more interesting matrices in table 3 is )AW 11 0 32 -2 0 (the APPU, a random matrix)AW 1200 7013 m 11 0 32 -1 0 (with a relatively normal distribution and a very high ave)AW 11 0 32 (rage density. The average)W 1200 6711 m 11 0 32 -1 0 (density for the APP)AW 11 0 32 (U is 255.6 which is more than twice the square root of )W /NewCenturySchlbk-ItalicR 600 ff 11 0 32 (n)W /NewCenturySchlbk-RomanR 600 ff 11 0 32 (, which)W 1200 6409 m 1 0 (is)A 29 0 32 1 0 ( 118. Th)AW 29 0 32 (is is a good example of what the preprocessor does. Since the average)W 1200 6107 m -2 0 (density)A 5 0 32 -2 0 ( is above the threshold, the AMDpre removed 6497 rows, )AW 6 0 32 -2 0 (nearly half the rows,)AW 1200 5805 m 11 0 32 (with a 54 percent reduction of ordering time.)W 1200 5503 m 1800 5503 m -2 0 (All)A 8 0 32 -2 0 ( three Gupta matrices are difficult to order without )AW 9 0 32 -2 0 (AMDpre. It took AMD)AW 1200 5201 m 11 0 32 -1 0 (28 minutes to order GUPTA2. AMDpre, on the other hand)AW 11 0 32 (, removed only 2 percent)W 1200 4899 m 1 0 (of)A 20 0 32 1 0 ( the rows )AW 20 0 32 (\(1193\) and cut the ordering time to just over 4 seconds! The ordering)W 1200 4597 m 1 0 (time)A 12 0 32 1 0 ( redu)AW 12 0 32 (ctions of the other two Gupta matrices are almost as dramatic. All three)W 1200 4295 m 1 0 (Gupta)A 16 0 32 1 0 ( ma)AW 16 0 32 (trices have some dense rows that are several times more dense than the)W 1200 3993 m 11 0 32 (average. )W 1200 3691 m 1800 3691 m 1 0 (Although)A 21 0 32 1 0 ( st)AW 21 0 32 (atistics can tell you quite a bit about a matrix, statistics cannot)W 1200 3389 m 1 0 (ac)A (curately)S 30 0 32 ( predict the ordering time for a given matrix. As the next section will)W 1200 3087 m -1 0 (show,)A 7 0 32 -1 0 ( just adding one dense row, increasing the average density by just 1, )AW 8 0 32 -1 0 (can cause)AW 1200 2785 m (the)S 38 0 32 ( ordering time for a sparse matrix to increase dramatically. In other words,)W 1200 2483 m 1 0 (knowing)A 14 0 32 1 0 ( the)AW 14 0 32 ( average density and distribution of the rows and columns in a matrix)W 1200 2181 m 11 0 32 (will not indicate the existence of a very dense row or column. )W ep %%Page: 9 9 bp /NewCenturySchlbk-BoldR 600 ff 0 13200 10200 co mcm 1968 11094 tr 1 -1 sc np 0 0 m 15 0 li 15 681 li 0 681 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1331 0 li 1331 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 3300 11094 tr 1 -1 sc np 0 0 m 15 0 li 15 681 li 0 681 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1079 0 li 1079 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 4380 11094 tr 1 -1 sc np 0 0 m 15 0 li 15 681 li 0 681 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1283 0 li 1283 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 5664 11094 tr 1 -1 sc np 0 0 m 15 0 li 15 681 li 0 681 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1283 0 li 1283 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 6948 11094 tr 1 -1 sc np 0 0 m 15 0 li 15 681 li 0 681 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1281 0 li 1281 15 li 0 15 li cp 0 255 div g fill np 1266 0 m 1281 0 li 1281 681 li 1266 681 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 1968 10412 tr 1 -1 sc np 0 0 m 15 0 li 15 381 li 0 381 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1331 0 li 1331 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 3300 10412 tr 1 -1 sc np 0 0 m 15 0 li 15 381 li 0 381 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1079 0 li 1079 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 4380 10412 tr 1 -1 sc np 0 0 m 15 0 li 15 381 li 0 381 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1283 0 li 1283 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 5664 10412 tr 1 -1 sc np 0 0 m 15 0 li 15 381 li 0 381 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1283 0 li 1283 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 6948 10412 tr 1 -1 sc np 0 0 m 15 0 li 15 381 li 0 381 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1281 0 li 1281 15 li 0 15 li cp 0 255 div g fill np 1266 0 m 1281 0 li 1281 381 li 1266 381 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 1968 10030 tr 1 -1 sc np 0 0 m 15 0 li 15 379 li 0 379 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1331 0 li 1331 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 3300 10030 tr 1 -1 sc np 0 0 m 15 0 li 15 379 li 0 379 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1079 0 li 1079 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 4380 10030 tr 1 -1 sc np 0 0 m 15 0 li 15 379 li 0 379 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1283 0 li 1283 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 5664 10030 tr 1 -1 sc np 0 0 m 15 0 li 15 379 li 0 379 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1283 0 li 1283 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 6948 10030 tr 1 -1 sc np 0 0 m 15 0 li 15 379 li 0 379 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1281 0 li 1281 15 li 0 15 li cp 0 255 div g fill np 1266 0 m 1281 0 li 1281 379 li 1266 379 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 1968 9650 tr 1 -1 sc np 0 0 m 15 0 li 15 381 li 0 381 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1331 0 li 1331 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 3300 9650 tr 1 -1 sc np 0 0 m 15 0 li 15 381 li 0 381 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1079 0 li 1079 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 4380 9650 tr 1 -1 sc np 0 0 m 15 0 li 15 381 li 0 381 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1283 0 li 1283 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 5664 9650 tr 1 -1 sc np 0 0 m 15 0 li 15 381 li 0 381 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1283 0 li 1283 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 6948 9650 tr 1 -1 sc np 0 0 m 15 0 li 15 381 li 0 381 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1281 0 li 1281 15 li 0 15 li cp 0 255 div g fill np 1266 0 m 1281 0 li 1281 381 li 1266 381 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 1968 9268 tr 1 -1 sc np 0 0 m 15 0 li 15 379 li 0 379 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1331 0 li 1331 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 3300 9268 tr 1 -1 sc np 0 0 m 15 0 li 15 379 li 0 379 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1079 0 li 1079 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 4380 9268 tr 1 -1 sc np 0 0 m 15 0 li 15 379 li 0 379 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1283 0 li 1283 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 5664 9268 tr 1 -1 sc np 0 0 m 15 0 li 15 379 li 0 379 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1283 0 li 1283 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 6948 9268 tr 1 -1 sc np 0 0 m 15 0 li 15 379 li 0 379 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1281 0 li 1281 15 li 0 15 li cp 0 255 div g fill np 1266 0 m 1281 0 li 1281 379 li 1266 379 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 1968 8888 tr 1 -1 sc np 0 0 m 15 0 li 15 381 li 0 381 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1331 0 li 1331 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 3300 8888 tr 1 -1 sc np 0 0 m 15 0 li 15 381 li 0 381 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1079 0 li 1079 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 4380 8888 tr 1 -1 sc np 0 0 m 15 0 li 15 381 li 0 381 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1283 0 li 1283 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 5664 8888 tr 1 -1 sc np 0 0 m 15 0 li 15 381 li 0 381 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1283 0 li 1283 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 6948 8888 tr 1 -1 sc np 0 0 m 15 0 li 15 381 li 0 381 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1281 0 li 1281 15 li 0 15 li cp 0 255 div g fill np 1266 0 m 1281 0 li 1281 381 li 1266 381 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 1968 8506 tr 1 -1 sc np 0 0 m 15 0 li 15 379 li 0 379 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1331 0 li 1331 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 3300 8506 tr 1 -1 sc np 0 0 m 15 0 li 15 379 li 0 379 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1079 0 li 1079 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 4380 8506 tr 1 -1 sc np 0 0 m 15 0 li 15 379 li 0 379 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1283 0 li 1283 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 5664 8506 tr 1 -1 sc np 0 0 m 15 0 li 15 379 li 0 379 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1283 0 li 1283 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 6948 8506 tr 1 -1 sc np 0 0 m 15 0 li 15 379 li 0 379 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1281 0 li 1281 15 li 0 15 li cp 0 255 div g fill np 1266 0 m 1281 0 li 1281 379 li 1266 379 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 1968 8126 tr 1 -1 sc np 0 0 m 15 0 li 15 381 li 0 381 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1331 0 li 1331 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 3300 8126 tr 1 -1 sc np 0 0 m 15 0 li 15 381 li 0 381 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1079 0 li 1079 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 4380 8126 tr 1 -1 sc np 0 0 m 15 0 li 15 381 li 0 381 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1283 0 li 1283 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 5664 8126 tr 1 -1 sc np 0 0 m 15 0 li 15 381 li 0 381 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1283 0 li 1283 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 6948 8126 tr 1 -1 sc np 0 0 m 15 0 li 15 381 li 0 381 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1281 0 li 1281 15 li 0 15 li cp 0 255 div g fill np 1266 0 m 1281 0 li 1281 381 li 1266 381 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 1968 7744 tr 1 -1 sc np 0 0 m 15 0 li 15 379 li 0 379 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1331 0 li 1331 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 3300 7744 tr 1 -1 sc np 0 0 m 15 0 li 15 379 li 0 379 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1079 0 li 1079 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 4380 7744 tr 1 -1 sc np 0 0 m 15 0 li 15 379 li 0 379 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1283 0 li 1283 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 5664 7744 tr 1 -1 sc np 0 0 m 15 0 li 15 379 li 0 379 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1283 0 li 1283 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 6948 7744 tr 1 -1 sc np 0 0 m 15 0 li 15 379 li 0 379 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1281 0 li 1281 15 li 0 15 li cp 0 255 div g fill np 1266 0 m 1281 0 li 1281 379 li 1266 379 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 1968 7364 tr 1 -1 sc np 0 0 m 15 0 li 15 381 li 0 381 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1331 0 li 1331 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 3300 7364 tr 1 -1 sc np 0 0 m 15 0 li 15 381 li 0 381 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1079 0 li 1079 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 4380 7364 tr 1 -1 sc np 0 0 m 15 0 li 15 381 li 0 381 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1283 0 li 1283 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 5664 7364 tr 1 -1 sc np 0 0 m 15 0 li 15 381 li 0 381 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1283 0 li 1283 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 6948 7364 tr 1 -1 sc np 0 0 m 15 0 li 15 381 li 0 381 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1281 0 li 1281 15 li 0 15 li cp 0 255 div g fill np 1266 0 m 1281 0 li 1281 381 li 1266 381 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 1968 6982 tr 1 -1 sc np 0 0 m 15 0 li 15 379 li 0 379 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1331 0 li 1331 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 3300 6982 tr 1 -1 sc np 0 0 m 15 0 li 15 379 li 0 379 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1079 0 li 1079 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 4380 6982 tr 1 -1 sc np 0 0 m 15 0 li 15 379 li 0 379 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1283 0 li 1283 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 5664 6982 tr 1 -1 sc np 0 0 m 15 0 li 15 379 li 0 379 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1283 0 li 1283 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 6948 6982 tr 1 -1 sc np 0 0 m 15 0 li 15 379 li 0 379 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1281 0 li 1281 15 li 0 15 li cp 0 255 div g fill np 1266 0 m 1281 0 li 1281 379 li 1266 379 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 1968 6602 tr 1 -1 sc np 0 0 m 15 0 li 15 381 li 0 381 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1331 0 li 1331 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 3300 6602 tr 1 -1 sc np 0 0 m 15 0 li 15 381 li 0 381 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1079 0 li 1079 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 4380 6602 tr 1 -1 sc np 0 0 m 15 0 li 15 381 li 0 381 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1283 0 li 1283 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 5664 6602 tr 1 -1 sc np 0 0 m 15 0 li 15 381 li 0 381 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1283 0 li 1283 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 6948 6602 tr 1 -1 sc np 0 0 m 15 0 li 15 381 li 0 381 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1281 0 li 1281 15 li 0 15 li cp 0 255 div g fill np 1266 0 m 1281 0 li 1281 381 li 1266 381 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 1968 6220 tr 1 -1 sc np 0 0 m 15 0 li 15 379 li 0 379 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1331 0 li 1331 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 3300 6220 tr 1 -1 sc np 0 0 m 15 0 li 15 379 li 0 379 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1079 0 li 1079 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 4380 6220 tr 1 -1 sc np 0 0 m 15 0 li 15 379 li 0 379 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1283 0 li 1283 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 5664 6220 tr 1 -1 sc np 0 0 m 15 0 li 15 379 li 0 379 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1283 0 li 1283 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 6948 6220 tr 1 -1 sc np 0 0 m 15 0 li 15 379 li 0 379 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1281 0 li 1281 15 li 0 15 li cp 0 255 div g fill np 1266 0 m 1281 0 li 1281 379 li 1266 379 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 1968 5840 tr 1 -1 sc np 0 0 m 15 0 li 15 381 li 0 381 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1331 0 li 1331 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 3300 5840 tr 1 -1 sc np 0 0 m 15 0 li 15 381 li 0 381 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1079 0 li 1079 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 4380 5840 tr 1 -1 sc np 0 0 m 15 0 li 15 381 li 0 381 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1283 0 li 1283 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 5664 5840 tr 1 -1 sc np 0 0 m 15 0 li 15 381 li 0 381 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1283 0 li 1283 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 6948 5840 tr 1 -1 sc np 0 0 m 15 0 li 15 381 li 0 381 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1281 0 li 1281 15 li 0 15 li cp 0 255 div g fill np 1266 0 m 1281 0 li 1281 381 li 1266 381 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 1968 5458 tr 1 -1 sc np 0 0 m 15 0 li 15 379 li 0 379 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1331 0 li 1331 15 li 0 15 li cp 0 255 div g fill np 0 364 m 1331 364 li 1331 379 li 0 379 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 3300 5458 tr 1 -1 sc np 0 0 m 15 0 li 15 379 li 0 379 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1079 0 li 1079 15 li 0 15 li cp 0 255 div g fill np 0 364 m 1079 364 li 1079 379 li 0 379 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 4380 5458 tr 1 -1 sc np 0 0 m 15 0 li 15 379 li 0 379 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1283 0 li 1283 15 li 0 15 li cp 0 255 div g fill np 0 364 m 1283 364 li 1283 379 li 0 379 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 5664 5458 tr 1 -1 sc np 0 0 m 15 0 li 15 379 li 0 379 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1283 0 li 1283 15 li 0 15 li cp 0 255 div g fill np 0 364 m 1283 364 li 1283 379 li 0 379 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 6948 5458 tr 1 -1 sc np 0 0 m 15 0 li 15 379 li 0 379 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1281 0 li 1281 15 li 0 15 li cp 0 255 div g fill np 1266 0 m 1281 0 li 1281 379 li 1266 379 li cp 0 255 div g fill np 0 364 m 1281 364 li 1281 379 li 0 379 li cp 0 255 div g fill 0 w 0 lc sm icl 5040 1263 m /CourierR 600 ff 0 255 div g (9)S 2068 10839 m /NewCenturySchlbk-RomanR 600 ff (Matrix)S 3400 10839 m (Matrix)S 3400 10537 m (order)S 4480 10839 m 11 0 32 (AMD time)W 5764 10839 m (AMDpre)S 5764 10537 m 11 0 32 (time )W 7048 10839 m 11 0 32 (Rows torn)W 2068 10156 m (BCSSTK29)S 3725 10156 m (13993)S 5175 10156 m (1.35)S 6570 10156 m (.24)S 8021 10156 m (1)S 2068 9775 m (BCSSTK30)S 3725 9775 m (28925)S 5175 9775 m (5.04)S 6570 9775 m (.62)S 7910 9775 m (97)S 2068 9394 m (BCSSTK31)S 3725 9394 m (35589)S 5064 9394 m (13.98)S 6570 9394 m (.81)S 8021 9394 m (1)S 2068 9013 m (BCSSTK32)S 3725 9013 m (44610)S 5064 9013 m (14.24)S 6570 9013 m (.80)S 8021 9013 m (5)S 2068 8632 m (CT20STIF)S 3725 8632 m (52330)S 5064 8632 m (17.02)S 6459 8632 m (1.12)S 8021 8632 m (1)S 2068 8251 m (CRYSTK03)S 3725 8251 m (24697)S 5175 8251 m (2.21)S 6570 8251 m (.58)S 8021 8251 m (1)S 2068 7870 m (EX11)S 3725 7870 m (16615)S 5175 7870 m (1.62)S 6570 7870 m (.50)S 8021 7870 m (1)S 2068 7489 m (EX19)S 3725 7489 m (12006)S 5175 7489 m (2.99)S 6570 7489 m (.17)S 8021 7489 m (1)S 2068 7108 m (NASASRB)S 3725 7108 m (54871)S 5064 7108 m (15.88)S 6459 7108 m (1.21)S 7910 7108 m (13)S 2068 6727 m (AF23560)S 3725 6727 m (23561)S 5064 6727 m (21.21)S 6459 6727 m (1.68)S 8021 6727 m (1)S 2068 6346 m (LHR34)S 3725 6346 m (35153)S 5064 6346 m (49.70)S 6459 6346 m (2.30)S 8021 6346 m (1)S 2068 5965 m (BBMAT)S 3725 5965 m (38745)S 5064 5965 m (23.27)S 6459 5965 m (4.69)S 8021 5965 m (1)S 2068 5584 m (VENKAT50)S 3725 5584 m (62426)S 5064 5584 m (21.12)S 6570 5584 m (.88)S 8021 5584 m (1)S 2068 5203 m (WANG3)S 3725 5203 m (26065)S 5064 5203 m (48.02)S 6459 5203 m (1.06)S 8021 5203 m (1)S 2319 4621 m /NewCenturySchlbk-BoldR 600 ff 10 0 32 (Table 4: Sparse matrices ordering times )W 10 0 32 (\(in seconds\))W 3072 4319 m 10 0 32 ( with a dense row and column added. )W 1200 3413 m 1 0 (3.3)A 32 0 32 1 0 ( )AW 32 0 32 (AMD and AMDpre ordering time for matrices with a dense row and)W 1200 3110 m -1 0 (column)A -1 h 5 0 32 -1 0 ( added. )AW /NewCenturySchlbk-RomanR 600 ff 6 0 32 -1 0 ( Nearly 100 matrices, of the 520 matrices used during testing, were)AW 1200 2806 m 1 0 (also)A 16 0 32 1 0 ( t)AW 16 0 32 (ested by adding a dense row and column. This was done in part to see what)W 1200 2504 m 1 0 (effect)A 77 0 32 1 0 ( a dens)AW 77 0 32 (e row and column has on AMD ordering time and to test the)W 1200 2202 m -1 0 (effectiveness)A 7 0 32 -1 0 ( of AMDpre. The matrices of table 3 each had )AW 8 0 32 -1 0 (a dense row and column)AW 1200 1900 m 1 0 (added.)A 13 0 32 1 0 ( AMD)AW 13 0 32 (pre had no problem detecting the dense row, or rows, and no problem)W ep %%Page: 10 10 bp /NewCenturySchlbk-RomanR 600 ff 0 13200 10200 co 4980 1263 m /CourierR 600 ff (10)S 1200 11845 m /NewCenturySchlbk-RomanR 600 ff 1 0 (partition)A (ing)S 20 0 32 ( the matrix. In general, the resulting submatrix )W /NewCenturySchlbk-BoldR 600 ff 19 0 32 (A)W /NewCenturySchlbk-RomanR 600 ff 20 0 32 ( is the same as the)W 1200 11541 m (original)S 12 0 32 ( matrix from )W 11 0 32 (table 3, and the submatrix )W /NewCenturySchlbk-BoldR 600 ff 10 0 32 (D)W /NewCenturySchlbk-RomanR 600 ff 11 0 32 ( is just the dense node, or nodes.)W 1200 11237 m -1 0 (It)A -1 h 7 0 32 -1 0 ( was not necessary to add a dense row and column to APPU or the Gupta matrices)AW 1200 10935 m 11 0 32 (because those were already dense enough.)W 1200 10633 m 1800 10633 m 11 0 32 -1 0 (Comparing column 3 of both table 3 and 4, the ordering t)AW 11 0 32 (ime increased by an)W 1200 10331 m 1 0 (average)A 33 0 32 1 0 ( fa)AW 33 0 32 (ctor of 18.1. This is the effect one dense row has on the AMD and is)W 1200 10029 m 11 0 32 (convincing evidence for the use of AMDpre.)W 1200 9727 m 1800 9727 m -1 0 (Comparing)A 6 0 32 -1 0 ( column 4 of both table 3 and 4, only two ordering times stayed the)AW 1200 9425 m 1 0 (same)A (,)S 24 0 32 ( BCSSKT30 and BCSSTK32. The rest of the times increased an average of)W 1200 9123 m 1 0 (29.8)A 34 0 32 1 0 ( percen)AW 34 0 32 (t. This increase is roughly the time it took AMDpre to partition the)W 1200 8821 m 11 0 32 (matrix. )W 1200 8519 m 1800 8519 m -1 0 (Comparing)A 7 0 32 -1 0 ( columns 3 and 4 of table 4, the average reduction )AW 8 0 32 -1 0 (in ordering time)AW 1200 8217 m -1 0 (is)A 8 0 32 -1 0 ( 88.7 percent. The largest reduction in run )AW 9 0 32 -1 0 (time is the matrix LHR34, which went)AW 1200 7915 m 11 0 32 -1 0 (from 49.7 sec to 2.3 sec. This is a 95.4 percent reduction. )AW 11 0 32 ( Also note, from table 3, it)W 1200 7613 m 11 0 32 -1 0 (took 2.22 sec for AMDpre which )AW 11 0 32 (means that AMDpre consumed only .08 seconds as)W 1200 7311 m -1 0 (a)A 7 0 32 -1 0 ( result of the addition of one )AW 8 0 32 -1 0 (dense row. The largest reduction in percent change is)AW 1200 7009 m 1 0 (the)A 13 0 32 1 0 ( BCSST)AW 13 0 32 (K29 which is 97.8 percent. The smallest reduction in percent change is)W 1200 6707 m 11 0 32 (EX11 with a reduction of 69.1 percent.)W 1200 6405 m 1800 6405 m 11 0 32 -1 0 (As pointed out in section 1, and as evidenced b)AW 11 0 32 (y table 4, the AMD utilizes up)W 1200 6103 m 11 0 32 -2 0 (to 97 percent of its computing time dealing with just one dense row. It is completely)AW 1200 5801 m 1 0 (obvious)A 19 0 32 1 0 ( tha)AW 19 0 32 (t preordering is necessary in these matrices. However, in many cases,)W 1200 5499 m 11 0 32 -1 0 (knowing the distribution of )AW 11 0 32 (the row densities before hand is impossible. As seen in)W 1200 5197 m 1 0 (table)A 16 0 32 1 0 ( 3, )AW 16 0 32 (a matrix may have a row density greater than the threshold and not need)W 1200 4895 m 11 0 32 -1 0 (preprocessing. AMDp)AW 11 0 32 (re will yield positive results if there is one or more extremely)W 1200 4593 m -2 0 (dense)A 8 0 32 -2 0 ( rows and columns \(as in table 4\) or many )AW 9 0 32 -2 0 (slightly dense rows and columns \(as)AW 1200 4291 m 11 0 32 (with the Gupta matrices\).)W ep %%Page: 11 11 bp /NewCenturySchlbk-BoldR 600 ff 0 13200 10200 co mcm 1200 12000 tr 1 -1 sc np 0 0 m 15 0 li 15 379 li 0 379 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1355 0 li 1355 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 2556 12000 tr 1 -1 sc np 0 0 m 79 0 li 79 379 li 0 379 li cp 0 255 div g 79 w 0 lc fill np 0 0 m 911 0 li 911 15 li 0 15 li cp 0 255 div g 15 w fill 0 w 0 lc sm icl mcm 3468 12000 tr 1 -1 sc np 0 0 m 911 0 li 911 15 li 0 15 li cp 0 255 div g 15 w 0 lc fill 0 w 0 lc sm icl mcm 4380 12000 tr 1 -1 sc np 0 0 m 911 0 li 911 15 li 0 15 li cp 0 255 div g 15 w 0 lc fill np 832 0 m 911 0 li 911 379 li 832 379 li cp 0 255 div g 79 w fill 0 w 0 lc sm icl mcm 5292 12000 tr 1 -1 sc np 0 0 m 911 0 li 911 15 li 0 15 li cp 0 255 div g 15 w 0 lc fill 0 w 0 lc sm icl mcm 6204 12000 tr 1 -1 sc np 0 0 m 1091 0 li 1091 15 li 0 15 li cp 0 255 div g 15 w 0 lc fill 0 w 0 lc sm icl mcm 7296 12000 tr 1 -1 sc np 0 0 m 911 0 li 911 15 li 0 15 li cp 0 255 div g 15 w 0 lc fill 0 w 0 lc sm icl mcm 8208 12000 tr 1 -1 sc np 0 0 m 789 0 li 789 15 li 0 15 li cp 0 255 div g 15 w 0 lc fill np 710 0 m 789 0 li 789 379 li 710 379 li cp 0 255 div g 79 w fill 0 w 0 lc sm icl mcm 1200 11620 tr 1 -1 sc np 0 0 m 15 0 li 15 683 li 0 683 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1355 0 li 1355 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 2556 11620 tr 1 -1 sc np 0 0 m 79 0 li 79 683 li 0 683 li cp 0 255 div g 79 w 0 lc fill np 0 0 m 911 0 li 911 15 li 0 15 li cp 0 255 div g 15 w fill 0 w 0 lc sm icl mcm 3468 11620 tr 1 -1 sc np 0 0 m 15 0 li 15 683 li 0 683 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 911 0 li 911 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 4380 11620 tr 1 -1 sc np 0 0 m 15 0 li 15 683 li 0 683 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 911 0 li 911 15 li 0 15 li cp 0 255 div g fill np 832 0 m 911 0 li 911 683 li 832 683 li cp 0 255 div g 79 w fill 0 w 0 lc sm icl mcm 5292 11620 tr 1 -1 sc np 0 0 m 911 0 li 911 15 li 0 15 li cp 0 255 div g 15 w 0 lc fill 0 w 0 lc sm icl mcm 6204 11620 tr 1 -1 sc np 0 0 m 15 0 li 15 683 li 0 683 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1091 0 li 1091 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 7296 11620 tr 1 -1 sc np 0 0 m 15 0 li 15 683 li 0 683 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 911 0 li 911 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 8208 11620 tr 1 -1 sc np 0 0 m 15 0 li 15 683 li 0 683 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 789 0 li 789 15 li 0 15 li cp 0 255 div g fill np 710 0 m 789 0 li 789 683 li 710 683 li cp 0 255 div g 79 w fill 0 w 0 lc sm icl mcm 1200 10936 tr 1 -1 sc np 0 0 m 15 0 li 15 379 li 0 379 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1355 0 li 1355 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 2556 10936 tr 1 -1 sc np 0 0 m 79 0 li 79 379 li 0 379 li cp 0 255 div g 79 w 0 lc fill np 0 0 m 911 0 li 911 15 li 0 15 li cp 0 255 div g 15 w fill 0 w 0 lc sm icl mcm 3468 10936 tr 1 -1 sc np 0 0 m 15 0 li 15 379 li 0 379 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 911 0 li 911 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 4380 10936 tr 1 -1 sc np 0 0 m 15 0 li 15 379 li 0 379 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 911 0 li 911 15 li 0 15 li cp 0 255 div g fill np 832 0 m 911 0 li 911 379 li 832 379 li cp 0 255 div g 79 w fill 0 w 0 lc sm icl mcm 5292 10936 tr 1 -1 sc np 0 0 m 911 0 li 911 15 li 0 15 li cp 0 255 div g 15 w 0 lc fill 0 w 0 lc sm icl mcm 6204 10936 tr 1 -1 sc np 0 0 m 15 0 li 15 379 li 0 379 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1091 0 li 1091 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 7296 10936 tr 1 -1 sc np 0 0 m 15 0 li 15 379 li 0 379 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 911 0 li 911 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 8208 10936 tr 1 -1 sc np 0 0 m 15 0 li 15 379 li 0 379 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 789 0 li 789 15 li 0 15 li cp 0 255 div g fill np 710 0 m 789 0 li 789 379 li 710 379 li cp 0 255 div g 79 w fill 0 w 0 lc sm icl mcm 1200 10556 tr 1 -1 sc np 0 0 m 15 0 li 15 381 li 0 381 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1355 0 li 1355 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 2556 10556 tr 1 -1 sc np 0 0 m 79 0 li 79 381 li 0 381 li cp 0 255 div g 79 w 0 lc fill np 0 0 m 911 0 li 911 15 li 0 15 li cp 0 255 div g 15 w fill 0 w 0 lc sm icl mcm 3468 10556 tr 1 -1 sc np 0 0 m 15 0 li 15 381 li 0 381 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 911 0 li 911 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 4380 10556 tr 1 -1 sc np 0 0 m 15 0 li 15 381 li 0 381 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 911 0 li 911 15 li 0 15 li cp 0 255 div g fill np 832 0 m 911 0 li 911 381 li 832 381 li cp 0 255 div g 79 w fill 0 w 0 lc sm icl mcm 5292 10556 tr 1 -1 sc np 0 0 m 911 0 li 911 15 li 0 15 li cp 0 255 div g 15 w 0 lc fill 0 w 0 lc sm icl mcm 6204 10556 tr 1 -1 sc np 0 0 m 15 0 li 15 381 li 0 381 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1091 0 li 1091 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 7296 10556 tr 1 -1 sc np 0 0 m 15 0 li 15 381 li 0 381 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 911 0 li 911 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 8208 10556 tr 1 -1 sc np 0 0 m 15 0 li 15 381 li 0 381 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 789 0 li 789 15 li 0 15 li cp 0 255 div g fill np 710 0 m 789 0 li 789 381 li 710 381 li cp 0 255 div g 79 w fill 0 w 0 lc sm icl mcm 1200 10174 tr 1 -1 sc np 0 0 m 15 0 li 15 381 li 0 381 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1355 0 li 1355 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 2556 10174 tr 1 -1 sc np 0 0 m 79 0 li 79 381 li 0 381 li cp 0 255 div g 79 w 0 lc fill np 0 0 m 911 0 li 911 15 li 0 15 li cp 0 255 div g 15 w fill 0 w 0 lc sm icl mcm 3468 10174 tr 1 -1 sc np 0 0 m 15 0 li 15 381 li 0 381 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 911 0 li 911 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 4380 10174 tr 1 -1 sc np 0 0 m 15 0 li 15 381 li 0 381 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 911 0 li 911 15 li 0 15 li cp 0 255 div g fill np 832 0 m 911 0 li 911 381 li 832 381 li cp 0 255 div g 79 w fill 0 w 0 lc sm icl mcm 5292 10174 tr 1 -1 sc np 0 0 m 911 0 li 911 15 li 0 15 li cp 0 255 div g 15 w 0 lc fill 0 w 0 lc sm icl mcm 6204 10174 tr 1 -1 sc np 0 0 m 15 0 li 15 381 li 0 381 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1091 0 li 1091 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 7296 10174 tr 1 -1 sc np 0 0 m 15 0 li 15 381 li 0 381 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 911 0 li 911 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 8208 10174 tr 1 -1 sc np 0 0 m 15 0 li 15 381 li 0 381 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 789 0 li 789 15 li 0 15 li cp 0 255 div g fill np 710 0 m 789 0 li 789 381 li 710 381 li cp 0 255 div g 79 w fill 0 w 0 lc sm icl mcm 1200 9792 tr 1 -1 sc np 0 0 m 15 0 li 15 379 li 0 379 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1355 0 li 1355 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 2556 9792 tr 1 -1 sc np 0 0 m 79 0 li 79 379 li 0 379 li cp 0 255 div g 79 w 0 lc fill np 0 0 m 911 0 li 911 15 li 0 15 li cp 0 255 div g 15 w fill 0 w 0 lc sm icl mcm 3468 9792 tr 1 -1 sc np 0 0 m 15 0 li 15 379 li 0 379 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 911 0 li 911 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 4380 9792 tr 1 -1 sc np 0 0 m 15 0 li 15 379 li 0 379 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 911 0 li 911 15 li 0 15 li cp 0 255 div g fill np 832 0 m 911 0 li 911 379 li 832 379 li cp 0 255 div g 79 w fill 0 w 0 lc sm icl mcm 5292 9792 tr 1 -1 sc np 0 0 m 911 0 li 911 15 li 0 15 li cp 0 255 div g 15 w 0 lc fill 0 w 0 lc sm icl mcm 6204 9792 tr 1 -1 sc np 0 0 m 15 0 li 15 379 li 0 379 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1091 0 li 1091 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 7296 9792 tr 1 -1 sc np 0 0 m 15 0 li 15 379 li 0 379 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 911 0 li 911 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 8208 9792 tr 1 -1 sc np 0 0 m 15 0 li 15 379 li 0 379 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 789 0 li 789 15 li 0 15 li cp 0 255 div g fill np 710 0 m 789 0 li 789 379 li 710 379 li cp 0 255 div g 79 w fill 0 w 0 lc sm icl mcm 1200 9412 tr 1 -1 sc np 0 0 m 15 0 li 15 381 li 0 381 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1355 0 li 1355 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 2556 9412 tr 1 -1 sc np 0 0 m 79 0 li 79 381 li 0 381 li cp 0 255 div g 79 w 0 lc fill np 0 0 m 911 0 li 911 15 li 0 15 li cp 0 255 div g 15 w fill 0 w 0 lc sm icl mcm 3468 9412 tr 1 -1 sc np 0 0 m 15 0 li 15 381 li 0 381 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 911 0 li 911 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 4380 9412 tr 1 -1 sc np 0 0 m 15 0 li 15 381 li 0 381 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 911 0 li 911 15 li 0 15 li cp 0 255 div g fill np 832 0 m 911 0 li 911 381 li 832 381 li cp 0 255 div g 79 w fill 0 w 0 lc sm icl mcm 5292 9412 tr 1 -1 sc np 0 0 m 911 0 li 911 15 li 0 15 li cp 0 255 div g 15 w 0 lc fill 0 w 0 lc sm icl mcm 6204 9412 tr 1 -1 sc np 0 0 m 15 0 li 15 381 li 0 381 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1091 0 li 1091 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 7296 9412 tr 1 -1 sc np 0 0 m 15 0 li 15 381 li 0 381 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 911 0 li 911 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 8208 9412 tr 1 -1 sc np 0 0 m 15 0 li 15 381 li 0 381 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 789 0 li 789 15 li 0 15 li cp 0 255 div g fill np 710 0 m 789 0 li 789 381 li 710 381 li cp 0 255 div g 79 w fill 0 w 0 lc sm icl mcm 1200 9030 tr 1 -1 sc np 0 0 m 15 0 li 15 379 li 0 379 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1355 0 li 1355 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 2556 9030 tr 1 -1 sc np 0 0 m 79 0 li 79 379 li 0 379 li cp 0 255 div g 79 w 0 lc fill np 0 0 m 911 0 li 911 15 li 0 15 li cp 0 255 div g 15 w fill 0 w 0 lc sm icl mcm 3468 9030 tr 1 -1 sc np 0 0 m 15 0 li 15 379 li 0 379 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 911 0 li 911 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 4380 9030 tr 1 -1 sc np 0 0 m 15 0 li 15 379 li 0 379 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 911 0 li 911 15 li 0 15 li cp 0 255 div g fill np 832 0 m 911 0 li 911 379 li 832 379 li cp 0 255 div g 79 w fill 0 w 0 lc sm icl mcm 5292 9030 tr 1 -1 sc np 0 0 m 911 0 li 911 15 li 0 15 li cp 0 255 div g 15 w 0 lc fill 0 w 0 lc sm icl mcm 6204 9030 tr 1 -1 sc np 0 0 m 15 0 li 15 379 li 0 379 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1091 0 li 1091 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 7296 9030 tr 1 -1 sc np 0 0 m 15 0 li 15 379 li 0 379 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 911 0 li 911 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 8208 9030 tr 1 -1 sc np 0 0 m 15 0 li 15 379 li 0 379 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 789 0 li 789 15 li 0 15 li cp 0 255 div g fill np 710 0 m 789 0 li 789 379 li 710 379 li cp 0 255 div g 79 w fill 0 w 0 lc sm icl mcm 1200 8650 tr 1 -1 sc np 0 0 m 15 0 li 15 381 li 0 381 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1355 0 li 1355 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 2556 8650 tr 1 -1 sc np 0 0 m 79 0 li 79 381 li 0 381 li cp 0 255 div g 79 w 0 lc fill np 0 0 m 911 0 li 911 15 li 0 15 li cp 0 255 div g 15 w fill 0 w 0 lc sm icl mcm 3468 8650 tr 1 -1 sc np 0 0 m 15 0 li 15 381 li 0 381 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 911 0 li 911 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 4380 8650 tr 1 -1 sc np 0 0 m 15 0 li 15 381 li 0 381 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 911 0 li 911 15 li 0 15 li cp 0 255 div g fill np 832 0 m 911 0 li 911 381 li 832 381 li cp 0 255 div g 79 w fill 0 w 0 lc sm icl mcm 5292 8650 tr 1 -1 sc np 0 0 m 911 0 li 911 15 li 0 15 li cp 0 255 div g 15 w 0 lc fill 0 w 0 lc sm icl mcm 6204 8650 tr 1 -1 sc np 0 0 m 15 0 li 15 381 li 0 381 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1091 0 li 1091 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 7296 8650 tr 1 -1 sc np 0 0 m 15 0 li 15 381 li 0 381 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 911 0 li 911 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 8208 8650 tr 1 -1 sc np 0 0 m 15 0 li 15 381 li 0 381 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 789 0 li 789 15 li 0 15 li cp 0 255 div g fill np 710 0 m 789 0 li 789 381 li 710 381 li cp 0 255 div g 79 w fill 0 w 0 lc sm icl mcm 1200 8268 tr 1 -1 sc np 0 0 m 15 0 li 15 379 li 0 379 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1355 0 li 1355 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 2556 8268 tr 1 -1 sc np 0 0 m 79 0 li 79 379 li 0 379 li cp 0 255 div g 79 w 0 lc fill np 0 0 m 911 0 li 911 15 li 0 15 li cp 0 255 div g 15 w fill 0 w 0 lc sm icl mcm 3468 8268 tr 1 -1 sc np 0 0 m 15 0 li 15 379 li 0 379 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 911 0 li 911 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 4380 8268 tr 1 -1 sc np 0 0 m 15 0 li 15 379 li 0 379 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 911 0 li 911 15 li 0 15 li cp 0 255 div g fill np 832 0 m 911 0 li 911 379 li 832 379 li cp 0 255 div g 79 w fill 0 w 0 lc sm icl mcm 5292 8268 tr 1 -1 sc np 0 0 m 911 0 li 911 15 li 0 15 li cp 0 255 div g 15 w 0 lc fill 0 w 0 lc sm icl mcm 6204 8268 tr 1 -1 sc np 0 0 m 15 0 li 15 379 li 0 379 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1091 0 li 1091 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 7296 8268 tr 1 -1 sc np 0 0 m 15 0 li 15 379 li 0 379 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 911 0 li 911 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 8208 8268 tr 1 -1 sc np 0 0 m 15 0 li 15 379 li 0 379 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 789 0 li 789 15 li 0 15 li cp 0 255 div g fill np 710 0 m 789 0 li 789 379 li 710 379 li cp 0 255 div g 79 w fill 0 w 0 lc sm icl mcm 1200 7888 tr 1 -1 sc np 0 0 m 15 0 li 15 381 li 0 381 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1355 0 li 1355 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 2556 7888 tr 1 -1 sc np 0 0 m 79 0 li 79 381 li 0 381 li cp 0 255 div g 79 w 0 lc fill np 0 0 m 911 0 li 911 15 li 0 15 li cp 0 255 div g 15 w fill 0 w 0 lc sm icl mcm 3468 7888 tr 1 -1 sc np 0 0 m 15 0 li 15 381 li 0 381 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 911 0 li 911 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 4380 7888 tr 1 -1 sc np 0 0 m 15 0 li 15 381 li 0 381 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 911 0 li 911 15 li 0 15 li cp 0 255 div g fill np 832 0 m 911 0 li 911 381 li 832 381 li cp 0 255 div g 79 w fill 0 w 0 lc sm icl mcm 5292 7888 tr 1 -1 sc np 0 0 m 911 0 li 911 15 li 0 15 li cp 0 255 div g 15 w 0 lc fill 0 w 0 lc sm icl mcm 6204 7888 tr 1 -1 sc np 0 0 m 15 0 li 15 381 li 0 381 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1091 0 li 1091 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 7296 7888 tr 1 -1 sc np 0 0 m 15 0 li 15 381 li 0 381 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 911 0 li 911 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 8208 7888 tr 1 -1 sc np 0 0 m 15 0 li 15 381 li 0 381 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 789 0 li 789 15 li 0 15 li cp 0 255 div g fill np 710 0 m 789 0 li 789 381 li 710 381 li cp 0 255 div g 79 w fill 0 w 0 lc sm icl mcm 1200 7506 tr 1 -1 sc np 0 0 m 15 0 li 15 379 li 0 379 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1355 0 li 1355 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 2556 7506 tr 1 -1 sc np 0 0 m 79 0 li 79 379 li 0 379 li cp 0 255 div g 79 w 0 lc fill np 0 0 m 911 0 li 911 15 li 0 15 li cp 0 255 div g 15 w fill 0 w 0 lc sm icl mcm 3468 7506 tr 1 -1 sc np 0 0 m 15 0 li 15 379 li 0 379 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 911 0 li 911 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 4380 7506 tr 1 -1 sc np 0 0 m 15 0 li 15 379 li 0 379 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 911 0 li 911 15 li 0 15 li cp 0 255 div g fill np 832 0 m 911 0 li 911 379 li 832 379 li cp 0 255 div g 79 w fill 0 w 0 lc sm icl mcm 5292 7506 tr 1 -1 sc np 0 0 m 911 0 li 911 15 li 0 15 li cp 0 255 div g 15 w 0 lc fill 0 w 0 lc sm icl mcm 6204 7506 tr 1 -1 sc np 0 0 m 15 0 li 15 379 li 0 379 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1091 0 li 1091 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 7296 7506 tr 1 -1 sc np 0 0 m 15 0 li 15 379 li 0 379 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 911 0 li 911 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 8208 7506 tr 1 -1 sc np 0 0 m 15 0 li 15 379 li 0 379 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 789 0 li 789 15 li 0 15 li cp 0 255 div g fill np 710 0 m 789 0 li 789 379 li 710 379 li cp 0 255 div g 79 w fill 0 w 0 lc sm icl mcm 1200 7126 tr 1 -1 sc np 0 0 m 15 0 li 15 381 li 0 381 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1355 0 li 1355 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 2556 7126 tr 1 -1 sc np 0 0 m 79 0 li 79 381 li 0 381 li cp 0 255 div g 79 w 0 lc fill np 0 0 m 911 0 li 911 15 li 0 15 li cp 0 255 div g 15 w fill 0 w 0 lc sm icl mcm 3468 7126 tr 1 -1 sc np 0 0 m 15 0 li 15 381 li 0 381 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 911 0 li 911 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 4380 7126 tr 1 -1 sc np 0 0 m 15 0 li 15 381 li 0 381 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 911 0 li 911 15 li 0 15 li cp 0 255 div g fill np 832 0 m 911 0 li 911 381 li 832 381 li cp 0 255 div g 79 w fill 0 w 0 lc sm icl mcm 5292 7126 tr 1 -1 sc np 0 0 m 911 0 li 911 15 li 0 15 li cp 0 255 div g 15 w 0 lc fill 0 w 0 lc sm icl mcm 6204 7126 tr 1 -1 sc np 0 0 m 15 0 li 15 381 li 0 381 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1091 0 li 1091 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 7296 7126 tr 1 -1 sc np 0 0 m 15 0 li 15 381 li 0 381 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 911 0 li 911 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 8208 7126 tr 1 -1 sc np 0 0 m 15 0 li 15 381 li 0 381 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 789 0 li 789 15 li 0 15 li cp 0 255 div g fill np 710 0 m 789 0 li 789 381 li 710 381 li cp 0 255 div g 79 w fill 0 w 0 lc sm icl mcm 1200 6744 tr 1 -1 sc np 0 0 m 15 0 li 15 379 li 0 379 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1355 0 li 1355 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 2556 6744 tr 1 -1 sc np 0 0 m 79 0 li 79 379 li 0 379 li cp 0 255 div g 79 w 0 lc fill np 0 0 m 911 0 li 911 15 li 0 15 li cp 0 255 div g 15 w fill 0 w 0 lc sm icl mcm 3468 6744 tr 1 -1 sc np 0 0 m 15 0 li 15 379 li 0 379 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 911 0 li 911 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 4380 6744 tr 1 -1 sc np 0 0 m 15 0 li 15 379 li 0 379 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 911 0 li 911 15 li 0 15 li cp 0 255 div g fill np 832 0 m 911 0 li 911 379 li 832 379 li cp 0 255 div g 79 w fill 0 w 0 lc sm icl mcm 5292 6744 tr 1 -1 sc np 0 0 m 911 0 li 911 15 li 0 15 li cp 0 255 div g 15 w 0 lc fill 0 w 0 lc sm icl mcm 6204 6744 tr 1 -1 sc np 0 0 m 15 0 li 15 379 li 0 379 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1091 0 li 1091 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 7296 6744 tr 1 -1 sc np 0 0 m 15 0 li 15 379 li 0 379 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 911 0 li 911 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 8208 6744 tr 1 -1 sc np 0 0 m 15 0 li 15 379 li 0 379 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 789 0 li 789 15 li 0 15 li cp 0 255 div g fill np 710 0 m 789 0 li 789 379 li 710 379 li cp 0 255 div g 79 w fill 0 w 0 lc sm icl mcm 1200 6364 tr 1 -1 sc np 0 0 m 15 0 li 15 381 li 0 381 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1355 0 li 1355 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 2556 6364 tr 1 -1 sc np 0 0 m 79 0 li 79 381 li 0 381 li cp 0 255 div g 79 w 0 lc fill np 0 0 m 911 0 li 911 15 li 0 15 li cp 0 255 div g 15 w fill 0 w 0 lc sm icl mcm 3468 6364 tr 1 -1 sc np 0 0 m 15 0 li 15 381 li 0 381 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 911 0 li 911 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 4380 6364 tr 1 -1 sc np 0 0 m 15 0 li 15 381 li 0 381 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 911 0 li 911 15 li 0 15 li cp 0 255 div g fill np 832 0 m 911 0 li 911 381 li 832 381 li cp 0 255 div g 79 w fill 0 w 0 lc sm icl mcm 5292 6364 tr 1 -1 sc np 0 0 m 911 0 li 911 15 li 0 15 li cp 0 255 div g 15 w 0 lc fill 0 w 0 lc sm icl mcm 6204 6364 tr 1 -1 sc np 0 0 m 15 0 li 15 381 li 0 381 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1091 0 li 1091 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 7296 6364 tr 1 -1 sc np 0 0 m 15 0 li 15 381 li 0 381 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 911 0 li 911 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 8208 6364 tr 1 -1 sc np 0 0 m 15 0 li 15 381 li 0 381 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 789 0 li 789 15 li 0 15 li cp 0 255 div g fill np 710 0 m 789 0 li 789 381 li 710 381 li cp 0 255 div g 79 w fill 0 w 0 lc sm icl mcm 1200 5982 tr 1 -1 sc np 0 0 m 15 0 li 15 379 li 0 379 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1355 0 li 1355 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 2556 5982 tr 1 -1 sc np 0 0 m 79 0 li 79 379 li 0 379 li cp 0 255 div g 79 w 0 lc fill np 0 0 m 911 0 li 911 15 li 0 15 li cp 0 255 div g 15 w fill 0 w 0 lc sm icl mcm 3468 5982 tr 1 -1 sc np 0 0 m 15 0 li 15 379 li 0 379 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 911 0 li 911 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 4380 5982 tr 1 -1 sc np 0 0 m 15 0 li 15 379 li 0 379 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 911 0 li 911 15 li 0 15 li cp 0 255 div g fill np 832 0 m 911 0 li 911 379 li 832 379 li cp 0 255 div g 79 w fill 0 w 0 lc sm icl mcm 5292 5982 tr 1 -1 sc np 0 0 m 911 0 li 911 15 li 0 15 li cp 0 255 div g 15 w 0 lc fill 0 w 0 lc sm icl mcm 6204 5982 tr 1 -1 sc np 0 0 m 15 0 li 15 379 li 0 379 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1091 0 li 1091 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 7296 5982 tr 1 -1 sc np 0 0 m 15 0 li 15 379 li 0 379 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 911 0 li 911 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 8208 5982 tr 1 -1 sc np 0 0 m 15 0 li 15 379 li 0 379 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 789 0 li 789 15 li 0 15 li cp 0 255 div g fill np 710 0 m 789 0 li 789 379 li 710 379 li cp 0 255 div g 79 w fill 0 w 0 lc sm icl mcm 1200 5602 tr 1 -1 sc np 0 0 m 15 0 li 15 381 li 0 381 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1355 0 li 1355 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 2556 5602 tr 1 -1 sc np 0 0 m 79 0 li 79 381 li 0 381 li cp 0 255 div g 79 w 0 lc fill np 0 0 m 911 0 li 911 15 li 0 15 li cp 0 255 div g 15 w fill 0 w 0 lc sm icl mcm 3468 5602 tr 1 -1 sc np 0 0 m 15 0 li 15 381 li 0 381 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 911 0 li 911 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 4380 5602 tr 1 -1 sc np 0 0 m 15 0 li 15 381 li 0 381 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 911 0 li 911 15 li 0 15 li cp 0 255 div g fill np 832 0 m 911 0 li 911 381 li 832 381 li cp 0 255 div g 79 w fill 0 w 0 lc sm icl mcm 5292 5602 tr 1 -1 sc np 0 0 m 911 0 li 911 15 li 0 15 li cp 0 255 div g 15 w 0 lc fill 0 w 0 lc sm icl mcm 6204 5602 tr 1 -1 sc np 0 0 m 15 0 li 15 381 li 0 381 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1091 0 li 1091 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 7296 5602 tr 1 -1 sc np 0 0 m 15 0 li 15 381 li 0 381 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 911 0 li 911 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 8208 5602 tr 1 -1 sc np 0 0 m 15 0 li 15 381 li 0 381 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 789 0 li 789 15 li 0 15 li cp 0 255 div g fill np 710 0 m 789 0 li 789 381 li 710 381 li cp 0 255 div g 79 w fill 0 w 0 lc sm icl mcm 1200 5220 tr 1 -1 sc np 0 0 m 15 0 li 15 379 li 0 379 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1355 0 li 1355 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 2556 5220 tr 1 -1 sc np 0 0 m 79 0 li 79 379 li 0 379 li cp 0 255 div g 79 w 0 lc fill np 0 0 m 911 0 li 911 15 li 0 15 li cp 0 255 div g 15 w fill 0 w 0 lc sm icl mcm 3468 5220 tr 1 -1 sc np 0 0 m 15 0 li 15 379 li 0 379 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 911 0 li 911 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 4380 5220 tr 1 -1 sc np 0 0 m 15 0 li 15 379 li 0 379 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 911 0 li 911 15 li 0 15 li cp 0 255 div g fill np 832 0 m 911 0 li 911 379 li 832 379 li cp 0 255 div g 79 w fill 0 w 0 lc sm icl mcm 5292 5220 tr 1 -1 sc np 0 0 m 911 0 li 911 15 li 0 15 li cp 0 255 div g 15 w 0 lc fill 0 w 0 lc sm icl mcm 6204 5220 tr 1 -1 sc np 0 0 m 15 0 li 15 379 li 0 379 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1091 0 li 1091 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 7296 5220 tr 1 -1 sc np 0 0 m 15 0 li 15 379 li 0 379 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 911 0 li 911 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 8208 5220 tr 1 -1 sc np 0 0 m 15 0 li 15 379 li 0 379 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 789 0 li 789 15 li 0 15 li cp 0 255 div g fill np 710 0 m 789 0 li 789 379 li 710 379 li cp 0 255 div g 79 w fill 0 w 0 lc sm icl mcm 1200 4840 tr 1 -1 sc np 0 0 m 15 0 li 15 381 li 0 381 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1355 0 li 1355 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 2556 4840 tr 1 -1 sc np 0 0 m 79 0 li 79 381 li 0 381 li cp 0 255 div g 79 w 0 lc fill np 0 0 m 911 0 li 911 15 li 0 15 li cp 0 255 div g 15 w fill 0 w 0 lc sm icl mcm 3468 4840 tr 1 -1 sc np 0 0 m 15 0 li 15 381 li 0 381 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 911 0 li 911 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 4380 4840 tr 1 -1 sc np 0 0 m 15 0 li 15 381 li 0 381 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 911 0 li 911 15 li 0 15 li cp 0 255 div g fill np 832 0 m 911 0 li 911 381 li 832 381 li cp 0 255 div g 79 w fill 0 w 0 lc sm icl mcm 5292 4840 tr 1 -1 sc np 0 0 m 911 0 li 911 15 li 0 15 li cp 0 255 div g 15 w 0 lc fill 0 w 0 lc sm icl mcm 6204 4840 tr 1 -1 sc np 0 0 m 15 0 li 15 381 li 0 381 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1091 0 li 1091 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 7296 4840 tr 1 -1 sc np 0 0 m 15 0 li 15 381 li 0 381 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 911 0 li 911 15 li 0 15 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 8208 4840 tr 1 -1 sc np 0 0 m 15 0 li 15 381 li 0 381 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 789 0 li 789 15 li 0 15 li cp 0 255 div g fill np 710 0 m 789 0 li 789 381 li 710 381 li cp 0 255 div g 79 w fill 0 w 0 lc sm icl mcm 1200 4458 tr 1 -1 sc np 0 0 m 15 0 li 15 379 li 0 379 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1355 0 li 1355 15 li 0 15 li cp 0 255 div g fill np 0 364 m 1355 364 li 1355 379 li 0 379 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 2556 4458 tr 1 -1 sc np 0 0 m 79 0 li 79 379 li 0 379 li cp 0 255 div g 79 w 0 lc fill np 0 0 m 911 0 li 911 15 li 0 15 li cp 0 255 div g 15 w fill np 0 364 m 911 364 li 911 379 li 0 379 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 3468 4458 tr 1 -1 sc np 0 0 m 15 0 li 15 379 li 0 379 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 911 0 li 911 15 li 0 15 li cp 0 255 div g fill np 0 364 m 911 364 li 911 379 li 0 379 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 4380 4458 tr 1 -1 sc np 0 0 m 15 0 li 15 379 li 0 379 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 911 0 li 911 15 li 0 15 li cp 0 255 div g fill np 832 0 m 911 0 li 911 379 li 832 379 li cp 0 255 div g 79 w fill np 0 364 m 911 364 li 911 379 li 0 379 li cp 0 255 div g 15 w fill 0 w 0 lc sm icl mcm 5292 4458 tr 1 -1 sc np 0 0 m 911 0 li 911 15 li 0 15 li cp 0 255 div g 15 w 0 lc fill np 0 364 m 911 364 li 911 379 li 0 379 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 6204 4458 tr 1 -1 sc np 0 0 m 15 0 li 15 379 li 0 379 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 1091 0 li 1091 15 li 0 15 li cp 0 255 div g fill np 0 364 m 1091 364 li 1091 379 li 0 379 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 7296 4458 tr 1 -1 sc np 0 0 m 15 0 li 15 379 li 0 379 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 911 0 li 911 15 li 0 15 li cp 0 255 div g fill np 0 364 m 911 364 li 911 379 li 0 379 li cp 0 255 div g fill 0 w 0 lc sm icl mcm 8208 4458 tr 1 -1 sc np 0 0 m 15 0 li 15 379 li 0 379 li cp 0 255 div g 15 w 0 lc fill np 0 0 m 789 0 li 789 15 li 0 15 li cp 0 255 div g fill np 710 0 m 789 0 li 789 379 li 710 379 li cp 0 255 div g 79 w fill np 0 364 m 789 364 li 789 379 li 0 379 li cp 0 255 div g 15 w fill 0 w 0 lc sm icl 4980 1263 m /CourierR 600 ff 0 255 div g (11)S 1300 11745 m /NewCenturySchlbk-RomanR 600 ff (Matrix)S 3568 11745 m (AMD)S 6304 11745 m (AMDpre)S 2656 11364 m (time)S 3568 11364 m (fill-in)S 4480 11364 m (flops)S 5392 11364 m (time)S 6304 11364 m (fillin)S 7396 11364 m (flops)S 8308 11364 m (rows)S 8308 11062 m (torn)S 1300 10681 m (BCSSTK29)S 3090 10681 m (.19)S 3891 10681 m (1.66)S 4692 10681 m (395.1)S 5826 10681 m (.19)S 6807 10681 m (1.66)S 7608 10681 m (395.1)S 8789 10681 m (0)S 1300 10300 m (BCSSTK30)S 3082 10301 m /NewCenturySchlbk-BoldR 600 ff (.47)S /NewCenturySchlbk-RomanR 600 ff 3812 10300 m 11 0 32 ( )W /NewCenturySchlbk-BoldR 600 ff 10 0 32 (3.76)W /NewCenturySchlbk-RomanR 600 ff 4676 10301 m /NewCenturySchlbk-BoldR 600 ff (899.7)S /NewCenturySchlbk-RomanR 600 ff 5826 10300 m (.62)S 6807 10300 m (3.99)S 7497 10300 m (1091.5)S 8678 10300 m (96)S 1300 9918 m (BCSSTK31)S 3090 9918 m (.71)S 3891 9918 m (5.46)S 4581 9918 m (2799.5)S 5826 9918 m (.71)S 6807 9918 m (5.46)S 7497 9918 m (2799.5)S 8789 9918 m (0)S 1300 9537 m (BCSSTK32)S 3082 9538 m /NewCenturySchlbk-BoldR 600 ff (.64)S /NewCenturySchlbk-RomanR 600 ff 3891 9537 m (5.06)S 4581 9537 m (1051.0)S 5826 9537 m (.80)S 6795 9538 m /NewCenturySchlbk-BoldR 600 ff (5.06)S /NewCenturySchlbk-RomanR 600 ff 7477 9538 m /NewCenturySchlbk-BoldR 600 ff (1050.5)S /NewCenturySchlbk-RomanR 600 ff 8789 9537 m (4)S 1300 9156 m (CT20STIF)S 3090 9156 m (.91)S 3780 9156 m (11.10)S 4581 9156 m (7983.7)S 5826 9156 m (.91)S 6696 9156 m (11.10)S 7497 9156 m (7983.7)S 8789 9156 m (0)S 1300 8775 m (CRYSTK03)S 3090 8775 m (.44)S 3780 8775 m (11.60)S 4581 8775 m (9851.2)S 5826 8775 m (.44)S 6696 8775 m (11.60)S 7497 8775 m (9851.2)S 8789 8775 m (0)S 1300 8394 m (EX11)S 3090 8394 m (.41)S 3891 8394 m (5.87)S 4581 8394 m (3322.2)S 5826 8394 m (.41)S 6807 8394 m (5.87)S 7497 8394 m (3322.2)S 8789 8394 m (0)S 1300 8013 m (EX19)S 3090 8013 m (.16)S 4002 8013 m (.29)S 4803 8013 m (10.7)S 5826 8013 m (.16)S 6918 8013 m (.29)S 7719 8013 m (10.7)S 8789 8013 m (0)S 1300 7632 m (NASASRB)S 3082 7633 m /NewCenturySchlbk-BoldR 600 ff (.98)S /NewCenturySchlbk-RomanR 600 ff 3764 7633 m /NewCenturySchlbk-BoldR 600 ff (11.86)S /NewCenturySchlbk-RomanR 600 ff 4561 7633 m /NewCenturySchlbk-BoldR 600 ff (4692.7)S /NewCenturySchlbk-RomanR 600 ff 5715 7632 m (1.19)S 6696 7632 m (11.92)S 7497 7632 m (4771.2)S 8678 7632 m (12)S 1300 7251 m (AF23560)S 2979 7251 m (1.19)S 3891 7251 m (4.07)S 4581 7251 m (1262.1)S 5715 7251 m (1.20)S 6807 7251 m (4.07)S 7497 7251 m (1262.1)S 8789 7251 m (0)S 1300 6870 m (LHR34)S 2979 6870 m (2.22)S 3891 6870 m (2.86)S 4692 6870 m (500.7)S 5715 6870 m (2.22)S 6807 6870 m (2.86)S 7608 6870 m (500.7)S 8789 6870 m (0)S 1300 6489 m (BBMAT)S 2979 6489 m (3.49)S 3780 6489 m (22.52)S 4581 6489 m (20410.)S 5715 6489 m (3.50)S 6696 6489 m (22.52)S 7497 6489 m (20410.)S 8789 6489 m (0)S 1300 6108 m (VENKAT50)S 3090 6108 m (.59)S 3891 6108 m (5.79)S 4581 6108 m (1144.3)S 5826 6108 m (.60)S 6807 6108 m (5.79)S 7497 6108 m (1144.3)S 8789 6108 m (0)S 1300 5727 m (APPU)S 2868 5727 m (10.03)S 3780 5727 m (87.61)S 4692 5727 m (768.4)S 5703 5728 m /NewCenturySchlbk-BoldR 600 ff (4.56)S /NewCenturySchlbk-RomanR 600 ff 6680 5728 m /NewCenturySchlbk-BoldR 600 ff (87.61)S /NewCenturySchlbk-RomanR 600 ff 7592 5728 m /NewCenturySchlbk-BoldR 600 ff (767.4)S /NewCenturySchlbk-RomanR 600 ff 8456 5727 m (6497)S 1300 5346 m (WANG3)S 3090 5346 m (.77)S 3891 5346 m (5.57)S 4581 5346 m (5207.8)S 5826 5346 m (.77)S 6807 5346 m (5.57)S 7497 5346 m (5207.8)S 8789 5346 m (0)S 1300 4965 m (GUPTA1)S 2757 4965 m (563.40)S 3879 4966 m /NewCenturySchlbk-BoldR 600 ff (2.02)S /NewCenturySchlbk-RomanR 600 ff 4676 4966 m /NewCenturySchlbk-BoldR 600 ff (300.1)S /NewCenturySchlbk-RomanR 600 ff 5818 4966 m /NewCenturySchlbk-BoldR 600 ff (.72)S /NewCenturySchlbk-RomanR 600 ff 6807 4965 m (2.05)S 7608 4965 m (301.1)S 8567 4965 m (676)S 1300 4584 m (GUPTA2)S 2757 4584 m (1655.1)S 3879 4585 m /NewCenturySchlbk-BoldR 600 ff (5.83)S /NewCenturySchlbk-RomanR 600 ff 4581 4584 m (1875.1)S 5703 4585 m /NewCenturySchlbk-BoldR 600 ff (4.29)S /NewCenturySchlbk-RomanR 600 ff 6807 4584 m (6.24)S 7477 4585 m /NewCenturySchlbk-BoldR 600 ff (1850.0)S /NewCenturySchlbk-RomanR 600 ff 8456 4584 m (1193)S 1300 4203 m (GUPTA3)S 2757 4203 m (147.66)S 3891 4203 m (5.70)S 4581 4203 m (2652.3)S 5818 4204 m /NewCenturySchlbk-BoldR 600 ff (.83)S /NewCenturySchlbk-RomanR 600 ff 6795 4204 m /NewCenturySchlbk-BoldR 600 ff (5.59)S /NewCenturySchlbk-RomanR 600 ff 7477 4204 m /NewCenturySchlbk-BoldR 600 ff (2602.6)S /NewCenturySchlbk-RomanR 600 ff 8456 4203 m (1347)S 1726 3621 m /NewCenturySchlbk-BoldR 600 ff 10 0 32 (Table 5: Sparse matrices resulting fillins and flops \(in millions\) )W 3461 3319 m 10 0 32 (and ordering time \(in seconds\).)W ep %%Page: 12 12 bp /NewCenturySchlbk-BoldR 600 ff 0 13200 10200 co 4980 1263 m /CourierR 600 ff (12)S 1200 11846 m /NewCenturySchlbk-BoldR 600 ff (4)S 70 0 32 ( Floating point operations \(flops\) resulting from AMD and AMDpre)W 1200 11544 m (preordering.)S /NewCenturySchlbk-RomanR 600 ff 1200 10939 m /NewCenturySchlbk-BoldR 600 ff (4.1)S 12 0 32 ( Fill-in. )W /NewCenturySchlbk-RomanR 600 ff 13 0 32 ( In this section, the ordering is analyzed. When Gaussian elimination)W 1200 10635 m -1 0 (or)A 6 0 32 -1 0 ( Cholesky decomposition is performed, new )AW 7 0 32 -1 0 (nonzeroes will be created called fillins.)AW 1200 10333 m -1 0 (The)A 10 0 32 -1 0 ( primary goal of AMD is, in the )AW 11 0 32 -1 0 (best case, to minimize the fillin. Unfortunately,)AW 1200 10031 m 11 0 32 (this problem is NP-complete [1].)W 1200 9729 m 1800 9729 m 1 0 (There)A 47 0 32 1 0 ( )AW 47 0 32 (are many reasons why fillin is not desirable. Foremost is storage)W 1200 9427 m (allocation.)S 12 0 32 ( The amount of memory is )W 11 0 32 (finite and fillin maybe very large. Allocating)W 1200 9125 m 11 0 32 -1 0 (sufficient memory beforehand may not be possible. Anot)AW 11 0 32 (her reason is the computer)W 1200 8823 m 1 0 (time)A 19 0 32 1 0 ( req)AW 19 0 32 (uired to do the factorization increases rapidity with increase in fillin. The)W 1200 8521 m 11 0 32 (computer time is measured in floating point operations or flops.)W 1200 7917 m /NewCenturySchlbk-BoldR 600 ff -2 0 (4.2)A 11 0 32 -2 0 ( )AW 10 0 32 -2 0 (Comparing AMD and AMDpre. )AW /NewCenturySchlbk-RomanR 600 ff 11 0 32 -2 0 (In table 5, columns 2 and 5 are from table 3,)AW 1200 7613 m 1 0 (columns)A 37 0 32 1 0 ( )AW 37 0 32 (3 and 6 are the resulting fillin, columns 4 and 7 are the floating point)W 1200 7311 m -2 0 (operations)A 5 0 32 -2 0 ( per second required for Choleski decomposition, and the last column is the)AW 1200 7009 m 11 0 32 (total rows removed by AMDpre.)W 1200 6707 m 1800 6707 m 1 0 (In)A 12 0 32 1 0 ( ma)AW 12 0 32 (jority of the matrices tested and the selected matrices in table 4, there)W 1200 6405 m 1 0 (is)A 13 0 32 1 0 ( not )AW 13 0 32 (a significant change fillin. AMDpre on the average does not adversely effect)W 1200 6103 m 1 0 (the)A 39 0 32 ( fillin. Matrices BCSSTK30 and NASASRB are examples of significant fillin)W 1200 5801 m 1 0 (caused)A 37 0 32 1 0 ( )AW 37 0 32 (by preprocessing. With matrix BCSSTK32 more time was spend, but a)W 1200 5499 m 1 0 (slig)A (htly)S 16 0 32 ( better fillin was achieved. In all three Gupta matrices, the ordering time)W 1200 5197 m 11 0 32 (was better, however, fillin was not improved.)W 1200 4895 m 11 0 32 ( )W 1200 4594 m /NewCenturySchlbk-BoldR 600 ff 10 0 32 (5 Conclusion.)W 1200 4291 m /NewCenturySchlbk-RomanR 600 ff 1800 4291 m 1 0 (We)A 60 0 32 1 0 ( hav)AW 60 0 32 (e described a preprocessing algorithm based on the technique of)W 1200 3989 m 1 0 (partitio)A (ning)S 20 0 32 ( the matrix prior to finding a permutation )W 20 0 32 (matrix. With the speed of)W 1200 3687 m -1 0 (many)A 9 0 32 -1 0 ( computers available today and the increase in memory used by the )AW 10 0 32 -1 0 (cpu, many)AW 1200 3385 m 1 0 (large)A 33 0 32 1 0 ( sp)AW 33 0 32 (arse matrices that used to take days to preorder now only take seconds.)W 1200 3083 m 1 0 (AMD)A 16 0 32 1 0 ( is )AW 16 0 32 (primarily concerned with sparse matrices and is not designed to process a)W 1200 2781 m 1 0 (matri)A (x)S 68 0 32 ( with one or more very dense rows and columns in a timely manner.)W 1200 2479 m -1 0 (Preprocessing,)A 7 0 32 -1 0 ( or filtering out, these rows )AW 8 0 32 -1 0 (and columns now allows AMD to preorder)AW 1200 2177 m 11 0 32 (a larger number of matrices than with out preprocessing. )W /CourierR 600 ff ep %%Page: 13 13 bp /NewCenturySchlbk-RomanR 600 ff 0 13200 10200 co mcm 2355 11396 tr 1 -1 sc sm icl mcm 2455 11296 tr 1 -1 sc mcm -84.0 -128.0 tr 1.0 -1.0 sc 0.0 -312.0 tr mcm 150.0 21.0 tr 0.19999 0.19699 sc np 0 1150 m 700 1150 li 700 1185 li 0 1185 li cp 1 w gs fill gr s bzcl sm mcm 21.0 21.0 tr 0.23298 0.19699 sc np 30 475 m 117 592 li 232 128 li 536 1185 li 555 1185 li 555 1150 li 225 0 li 205 0 li 78 519 li 40 468 li 30 475 li 1 w gs eofill gr s bzcl sm mcm 150.0 90.0 tr np 30 100 m 28 92 li 48 92 li 30 8 li 10 8 li 10 0 li 58 0 li 58 8 li 38 8 li 52 74 li 70 88 84 94 100 94 cv 118 94 122 86 118 64 cv 106 8 li 88 8 li 86 0 li 134 0 li 136 8 li 116 8 li 126 64 li 130 76 130 82 128 88 cv 124 98 116 102 102 102 cv 84 102 70 96 54 82 cv 58 100 li cp 1 w gs eofill gr s bzcl 140.0 0.0 tr sm 150 255 div g 0 w sm sm icl 4980 1263 m /CourierR 600 ff 0 255 div g (13)S 1200 11846 m /NewCenturySchlbk-BoldR 600 ff 10 0 32 (Appendix A. The AMDpre algorithm.)W 1200 11543 m /NewCenturySchlbk-ItalicR 600 ff 11 0 32 (section 1. make hash table)W /NewCenturySchlbk-BoldR 600 ff 1200 11202 m /NewCenturySchlbk-RomanR 600 ff 11 0 32 (degree = Z *)W 344 h 11 0 32 ()W 1200 10888 m 11 0 32 (head\(1 .. n\) = 0; next\(1 .. n\) = 0)W 1200 10586 m 11 0 32 (for i = 1 to n do)W 1200 10284 m 1800 10284 m 11 0 32 (deg = len\(i\))W 1200 9982 m 1800 9982 m 11 0 32 (if \(deg > dense\) then)W 1200 9680 m 1800 9680 m 2400 9680 m /NewCenturySchlbk-ItalicR 600 ff 11 0 32 (** place into hash bucket)W /NewCenturySchlbk-RomanR 600 ff 1200 9378 m 1800 9378 m 2400 9378 m 11 0 32 (if \(head\(deg\) = 0\))W 1200 9076 m 1800 9076 m 2400 9076 m 3000 9076 m 11 0 32 (head\(deg\) = i)W 1200 8774 m 1800 8774 m 2400 8774 m (else)S 1200 8472 m 1800 8472 m 2400 8472 m 3000 8472 m 11 0 32 (number = head\(deg\))W 1200 8170 m 1800 8170 m 2400 8170 m 3000 8170 m 11 0 32 (while \(next\(number\) != 0\) do)W 1200 7868 m 1800 7868 m 2400 7868 m 3000 7868 m 3600 7868 m 11 0 32 (number = next\(number\))W 1200 7566 m 1800 7566 m 2400 7566 m 3000 7566 m 11 0 32 (end while)W 1200 7264 m 1800 7264 m 2400 7264 m 11 0 32 (end if)W 1200 6962 m 1800 6962 m 11 0 32 (end if)W 1200 6660 m 11 0 32 (end for)W 1200 6056 m /NewCenturySchlbk-ItalicR 600 ff 11 0 32 (section 2. construct submatrix B)W /NewCenturySchlbk-RomanR 600 ff 1200 5754 m 11 0 32 (lastnode = n)W 1200 5452 m 11 0 32 (current = n)W 1200 5150 m 11 0 32 (dense = dense + 1)W 1200 4848 m 11 0 32 (while \(current >= dense\) do)W 1200 4546 m 1800 4546 m 11 0 32 (top = 0)W 1200 4244 m 1800 4244 m /NewCenturySchlbk-ItalicR 600 ff 11 0 32 (** find last node in the bucket)W /NewCenturySchlbk-RomanR 600 ff 1200 3942 m 1800 3942 m 11 0 32 (number = head\(current\))W 1200 3640 m 1800 3640 m 11 0 32 (node = number)W 1200 3338 m 1800 3338 m 11 0 32 (while \(number > 0\) do)W 1200 3036 m 1800 3036 m 2400 3036 m 11 0 32 (pnum = node)W 1200 2734 m 1800 2734 m 2400 2734 m 11 0 32 (node = number)W 1200 2432 m 1800 2432 m 2400 2432 m 11 0 32 (number = next\(node\))W 1200 2130 m /NewCenturySchlbk-BoldR 600 ff 1800 2130 m 2400 2130 m /NewCenturySchlbk-RomanR 600 ff 11 0 32 (top = 1)W 1200 1828 m 1800 1828 m 11 0 32 (end while)W ep %%Page: 14 14 bp /NewCenturySchlbk-RomanR 600 ff 0 13200 10200 co 4980 1263 m /CourierR 600 ff (14)S 1200 11845 m /NewCenturySchlbk-RomanR 600 ff 1800 11845 m /NewCenturySchlbk-ItalicR 600 ff 11 0 32 (** remove node from list)W /NewCenturySchlbk-RomanR 600 ff 1200 11543 m 1800 11543 m 11 0 32 (if \(top = 1\) then next\(pnum\) = o )W 1200 11241 m 1800 11241 m 11 0 32 (deg = len\(node\))W 1200 10939 m 1800 10939 m 11 0 32 (if \(deg >= dense\) then )W 1200 10637 m 1800 10637 m 2400 10637 m 11 0 32 (if \(deg < current\) then)W 1200 10335 m 1800 10335 m 2400 10335 m 3000 10335 m /NewCenturySchlbk-ItalicR 600 ff 11 0 32 (** re-insert in lower hash bucket)W /NewCenturySchlbk-RomanR 600 ff 1200 10033 m 1800 10033 m 2400 10033 m 3000 10033 m 11 0 32 (if \(head\(deg\) = 0\))W 1200 9731 m 1800 9731 m 2400 9731 m 3000 9731 m 3600 9731 m 11 0 32 (head\(deg\) = i)W 1200 9429 m 1800 9429 m 2400 9429 m 3000 9429 m (else)S 1200 9127 m 1800 9127 m 2400 9127 m 3000 9127 m 3600 9127 m 11 0 32 (number = head\(deg\))W 1200 8825 m 1800 8825 m 2400 8825 m 3000 8825 m 3600 8825 m 11 0 32 (while \(next\(number\) != 0\) do)W 1200 8523 m 1800 8523 m 2400 8523 m 3000 8523 m 3600 8523 m 4200 8523 m 11 0 32 (number = next\(number\))W 1200 8221 m 1800 8221 m 2400 8221 m 3000 8221 m 3600 8221 m 11 0 32 (end while)W 1200 7919 m 1800 7919 m 2400 7919 m 3000 7919 m 11 0 32 (end if)W 1200 7617 m 1800 7617 m 2400 7617 m (else)S 1200 7315 m 1800 7315 m 2400 7315 m 3000 7315 m /NewCenturySchlbk-ItalicR 600 ff 11 0 32 (** place node in submatrix B)W /NewCenturySchlbk-RomanR 600 ff 1200 7013 m 1800 7013 m 2400 7013 m 3000 7013 m 11 0 32 (last\(lastnode\) = node)W 1200 6711 m 1800 6711 m 2400 6711 m 3000 6711 m 11 0 32 (lastnode = lastnode + 1)W 1200 6409 m 1800 6409 m 2400 6409 m 3000 6409 m 11 0 32 (len\(node\) = 2*n)W 1200 6107 m 1800 6107 m 2400 6107 m 3000 6107 m 11 0 32 (pnum = pe\(node + 1\) - 1)W 1200 5805 m 1800 5805 m 2400 5805 m 3000 5805 m 11 0 32 (if \(node = n\) then pnum = pfree - 1 )W 6600 5805 m 7200 5805 m 1200 5503 m 1800 5503 m 2400 5503 m 3000 5503 m /NewCenturySchlbk-ItalicR 600 ff 11 0 32 (** decrement adjacent nodes by 1)W /NewCenturySchlbk-RomanR 600 ff 1200 5201 m 1800 5201 m 2400 5201 m 3000 5201 m 11 0 32 (for i = pe\(node\) to pnum do)W 1200 4899 m 1800 4899 m 2400 4899 m 3000 4899 m 3600 4899 m 11 0 32 (len\(iw\(i\)\) = len\(iw\(i\)\) - 1)W 1200 4597 m 1800 4597 m 2400 4597 m 3000 4597 m 11 0 32 (end for)W 1200 4295 m 1800 4295 m 2400 4295 m 11 0 32 (end if)W 1200 3993 m 1800 3993 m 11 0 32 (end if)W 1200 3691 m 1800 3691 m 11 0 32 (if \(top == 0\) then current = current - 1)W 1200 3389 m 11 0 32 (end while)W 1200 2785 m /NewCenturySchlbk-ItalicR 600 ff 11 0 32 (section 3. make the mapping index)W /NewCenturySchlbk-RomanR 600 ff 11 0 32 ( array)W 1200 2483 m 11 0 32 (lastnode = n)W 1200 2181 m 11 0 32 (current = 1)W 1200 1879 m 11 0 32 (for i = 1 to n do)W ep %%Page: 15 15 bp /NewCenturySchlbk-RomanR 600 ff 0 13200 10200 co 4980 1263 m /CourierR 600 ff (15)S 1200 11845 m /NewCenturySchlbk-RomanR 600 ff 1800 11845 m 11 0 32 (if \(len\(i\) < dense\) then)W 1200 11543 m 1800 11543 m 2400 11543 m /NewCenturySchlbk-ItalicR 600 ff 11 0 32 (** nodes in submatrix A)W /NewCenturySchlbk-RomanR 600 ff 1200 11241 m 1800 11241 m 2400 11241 m 11 0 32 (elen\(i\) = current)W 1200 10939 m 1800 10939 m 2400 10939 m 11 0 32 (mapping\(current\) = i)W 1200 10637 m 1800 10637 m 2400 10637 m 11 0 32 (current = current + 1)W 1200 10335 m 1800 10335 m (else)S 1200 10033 m 1800 10033 m 2400 10033 m /NewCenturySchlbk-ItalicR 600 ff 11 0 32 (** nodes in submatrix B)W /NewCenturySchlbk-RomanR 600 ff 1200 9731 m 1800 9731 m 2400 9731 m 11 0 32 (elen\(i\) = lastnode)W 1200 9429 m 1800 9429 m 2400 9429 m 11 0 32 (mapping\(lastnode\) = i)W 1200 9127 m 1800 9127 m 2400 9127 m 11 0 32 (lastnode = lastnode + 1)W 1200 8825 m 1800 8825 m 11 0 32 (end if)W 1200 8523 m 11 0 32 (end for)W 1200 7919 m /NewCenturySchlbk-ItalicR 600 ff 11 0 32 (section 4. construct submatrix A \(including non-zeroes in A\).)W /NewCenturySchlbk-RomanR 600 ff 1200 7617 m 11 0 32 (current = 1)W 1200 7315 m 11 0 32 (node = 1)W 1200 7013 m 11 0 32 (for i = 1 to n)W 1200 6711 m 1800 6711 m 11 0 32 (if \(elen\(i\) < lastnode\))W 1200 6409 m 1800 6409 m 2400 6409 m /NewCenturySchlbk-ItalicR 600 ff 11 0 32 (** construct the new iw array)W /NewCenturySchlbk-RomanR 600 ff 1200 6107 m 1800 6107 m 2400 6107 m 11 0 32 (pnum = pe\(i\))W 1200 5805 m 1800 5805 m 2400 5805 m 11 0 32 (pe\(node\) = current)W 1200 5503 m 1800 5503 m 2400 5503 m 11 0 32 (nextnum = pe\(node + 1\) - 1)W 1200 5201 m 1800 5201 m 2400 5201 m 11 0 32 (if \(i = n\) then nextnum = pfree - 1 )W 6000 5201 m 6600 5201 m 1200 4899 m 1800 4899 m 2400 4899 m 11 0 32 (for j = pnum to nextnum do)W 1200 4597 m 1800 4597 m 2400 4597 m 3000 4597 m 11 0 32 (if \(elen\(iw\(j\) < lastnode\) then)W 1200 4295 m 1800 4295 m 2400 4295 m 3000 4295 m 3600 4295 m 11 0 32 (iw\(current\) = elen\(iw\(j\)\))W 1200 3993 m 1800 3993 m 2400 3993 m 3000 3993 m 3600 3993 m 11 0 32 (current = current + 1)W 1200 3691 m 1800 3691 m 2400 3691 m 3000 3691 m 11 0 32 (end if)W 1200 3389 m 1800 3389 m 2400 3389 m 11 0 32 (end for)W 1200 3087 m 1800 3087 m /NewCenturySchlbk-ItalicR 600 ff 11 0 32 (** place new degree length in len)W /NewCenturySchlbk-RomanR 600 ff 1200 2785 m 1800 2785 m 11 0 32 (len\(node\) = current - pe\(node\))W 1200 2483 m 1800 2483 m 11 0 32 (node = node + 1)W 1200 2181 m 11 0 32 (end for)W ep %%Page: 16 16 bp /NewCenturySchlbk-ItalicR 600 ff 0 13200 10200 co 4980 1263 m /CourierR 600 ff (16)S 1200 11845 m /NewCenturySchlbk-ItalicR 600 ff 11 0 32 (section 5. send submatrix A to the AMD)W /NewCenturySchlbk-RomanR 600 ff 1200 11543 m 11 0 32 (ntemp = n)W 1200 11241 m 11 0 32 (pfree = current)W 1200 10939 m 11 0 32 (n = lastnode)W 1200 10335 m 11 0 32 (call AMD)W 1200 9731 m /NewCenturySchlbk-ItalicR 600 ff 11 0 32 (section 6. map nodes in A to original matrix values)W /NewCenturySchlbk-RomanR 600 ff 1200 9429 m 11 0 32 (n = ntemp)W 1200 9127 m 11 0 32 (for i = 1 to lastnode do)W 1200 8825 m 1800 8825 m 11 0 32 (last\(i\) = mapping\(last\(i\)\))W 1200 8523 m 11 0 32 (end for)W 1200 7919 m /NewCenturySchlbk-ItalicR 600 ff 11 0 32 (section 7. make inverse permutation array)W /NewCenturySchlbk-RomanR 600 ff 1200 7617 m 11 0 32 (for i = 1 to n do)W 1200 7315 m 1800 7315 m 11 0 32 (elen\(last\(i\)\) = i)W 1200 7013 m 11 0 32 (end for)W 1200 6711 m 11 0 32 (end program)W 1200 6409 m 11 0 32 ( )W ep %%Page: 17 17 bp /NewCenturySchlbk-RomanR 600 ff 0 13200 10200 co 4980 1263 m /CourierR 600 ff (17)S 1200 11846 m /NewCenturySchlbk-BoldR 600 ff 10 0 32 (Appendix B. References)W /NewCenturySchlbk-RomanR 600 ff 1200 11241 m /NewCenturySchlbk-BoldR 600 ff (1.)S 1800 11241 m /NewCenturySchlbk-RomanR 600 ff 1 0 (Timo)A (thy)S 58 0 32 ( A. Davis, Patrick Amestoy, and Iain Duff. )W /NewCenturySchlbk-ItalicR 600 ff 58 0 32 ( An approximate)W 1800 10937 m 11 0 32 -1 0 (minimum degree ordering algorithm)AW /NewCenturySchlbk-RomanR 600 ff 11 0 32 -1 0 (. Technical Report TR)AW 11 0 32 (-94-039, Computer)W 1800 10635 m -1 0 (and)A -1 h 6 0 32 -1 0 ( Information Sciences Department, University Of Florida, Gainesville, FL,)AW 1800 10333 m (1994.)S 1200 10031 m /NewCenturySchlbk-BoldR 600 ff (2.)S 1800 10031 m /NewCenturySchlbk-RomanR 600 ff 1 0 (I.S.)A 24 0 32 1 0 ( Du)AW 24 0 32 (ff, A.M. Erisman, and J.K. Reid, )W /NewCenturySchlbk-ItalicR 600 ff 24 0 32 (Direct methods for Sparse, )W /NewCenturySchlbk-RomanR 600 ff 24 0 32 (London:)W 1800 9727 m 11 0 32 (Oxford Univ. Press, 1986.)W 1200 9425 m /NewCenturySchlbk-BoldR 600 ff (3.)S 1800 9425 m /NewCenturySchlbk-RomanR 600 ff 1 0 (A.)A 44 0 32 1 0 ( Georg)AW 44 0 32 (e and J.W.H. Liu, )W /NewCenturySchlbk-ItalicR 600 ff 44 0 32 (A fast implementation of the minimum degree)W 1800 9121 m (ordering)S 1 h 13 0 32 ( algorithm using quotient graphs, )W /NewCenturySchlbk-RomanR 600 ff 13 0 32 (ACM Transtions on Mathematical)W 1800 8819 m 11 0 32 (Software, 6 \(1980\), pp. 337-358.)W 1200 8517 m /NewCenturySchlbk-BoldR 600 ff (4.)S 1800 8517 m /NewCenturySchlbk-RomanR 600 ff -2 0 (Anshul)A 6 0 32 -2 0 ( Gupta. )AW 7 0 32 -2 0 ( )AW /NewCenturySchlbk-ItalicR 600 ff 7 0 32 -2 0 (Fast and effective algorithms for graph partitioning and sparse)AW 1800 8213 m -2 0 (matrix)A 9 0 32 -2 0 ( ordering. )AW /NewCenturySchlbk-RomanR 600 ff 9 0 32 -2 0 ( IBM Research Report RC 20496, IBM T. J. )AW 10 0 32 -2 0 (Watson Research)AW 1800 7911 m 11 0 32 (Center, Yorktown Heights, NY, 1996.)W /NewCenturySchlbk-ItalicR 600 ff 1200 7609 m /NewCenturySchlbk-BoldItalicR 600 ff (5.)S 1800 7609 m /NewCenturySchlbk-RomanR 600 ff -3 0 (Gene)A 9 0 32 -3 0 ( H. Golub and Charles F. )AW 10 0 32 -3 0 (Van Loan, )AW /NewCenturySchlbk-ItalicR 600 ff 10 0 32 -3 0 (Matrix Computations, )AW /NewCenturySchlbk-RomanR 600 ff 10 0 32 -3 0 (second edition,)AW 1800 7301 m 11 0 32 (The Johns Hopkins University Press, Baltimore, Maryland, 1989.)W ep ed end %-12345X .