%!PS %%Version: 3.3.1 %%DocumentFonts: (atend) %%Pages: (atend) %%EndComments % % Version 3.3.1 prologue for troff files. % /#copies 1 store /aspectratio 1 def /formsperpage 1 def /landscape false def /linewidth .3 def /magnification 1 def /margin 0 def /orientation 0 def /resolution 720 def /rotation 1 def /xoffset 0 def /yoffset 0 def /roundpage true def /useclippath true def /pagebbox [0 0 612 792] def /R /Times-Roman def /I /Times-Italic def /B /Times-Bold def /BI /Times-BoldItalic def /H /Helvetica def /HI /Helvetica-Oblique def /HB /Helvetica-Bold def /HX /Helvetica-BoldOblique def /CW /Courier def /CO /Courier def /CI /Courier-Oblique def /CB /Courier-Bold def /CX /Courier-BoldOblique def /PA /Palatino-Roman def /PI /Palatino-Italic def /PB /Palatino-Bold def /PX /Palatino-BoldItalic def /Hr /Helvetica-Narrow def /Hi /Helvetica-Narrow-Oblique def /Hb /Helvetica-Narrow-Bold def /Hx /Helvetica-Narrow-BoldOblique def /KR /Bookman-Light def /KI /Bookman-LightItalic def /KB /Bookman-Demi def /KX /Bookman-DemiItalic def /AR /AvantGarde-Book def /AI /AvantGarde-BookOblique def /AB /AvantGarde-Demi def /AX /AvantGarde-DemiOblique def /NR /NewCenturySchlbk-Roman def /NI /NewCenturySchlbk-Italic def /NB /NewCenturySchlbk-Bold def /NX /NewCenturySchlbk-BoldItalic def /ZD /ZapfDingbats def /ZI /ZapfChancery-MediumItalic def /S /S def /S1 /S1 def /GR /Symbol def /inch {72 mul} bind def /min {2 copy gt {exch} if pop} bind def /setup { counttomark 2 idiv {def} repeat pop landscape {/orientation 90 orientation add def} if /scaling 72 resolution div def linewidth setlinewidth 1 setlinecap pagedimensions xcenter ycenter translate orientation rotation mul rotate width 2 div neg height 2 div translate xoffset inch yoffset inch neg translate margin 2 div dup neg translate magnification dup aspectratio mul scale scaling scaling scale addmetrics 0 0 moveto } def /pagedimensions { useclippath userdict /gotpagebbox known not and { /pagebbox [clippath pathbbox newpath] def roundpage currentdict /roundpagebbox known and {roundpagebbox} if } if pagebbox aload pop 4 -1 roll exch 4 1 roll 4 copy landscape {4 2 roll} if sub /width exch def sub /height exch def add 2 div /xcenter exch def add 2 div /ycenter exch def userdict /gotpagebbox true put } def /addmetrics { /Symbol /S null Sdefs cf /Times-Roman /S1 StandardEncoding dup length array copy S1defs cf } def /pagesetup { /page exch def currentdict /pagedict known currentdict page known and { page load pagedict exch get cvx exec } if } def /decodingdefs [ {counttomark 2 idiv {y moveto show} repeat} {neg /y exch def counttomark 2 idiv {y moveto show} repeat} {neg moveto {2 index stringwidth pop sub exch div 0 32 4 -1 roll widthshow} repeat} {neg moveto {spacewidth sub 0.0 32 4 -1 roll widthshow} repeat} {counttomark 2 idiv {y moveto show} repeat} {neg setfunnytext} ] def /setdecoding {/t decodingdefs 3 -1 roll get bind def} bind def /w {neg moveto show} bind def /m {neg dup /y exch def moveto} bind def /done {/lastpage where {pop lastpage} if} def /f { dup /font exch def findfont exch dup /ptsize exch def scaling div dup /size exch def scalefont setfont linewidth ptsize mul scaling 10 mul div setlinewidth /spacewidth ( ) stringwidth pop def } bind def /changefont { /fontheight exch def /fontslant exch def currentfont [ 1 0 fontheight ptsize div fontslant sin mul fontslant cos div fontheight ptsize div 0 0 ] makefont setfont } bind def /sf {f} bind def /cf { dup length 2 idiv /entries exch def /chtab exch def /newencoding exch def /newfont exch def findfont dup length 1 add dict /newdict exch def {1 index /FID ne {newdict 3 1 roll put}{pop pop} ifelse} forall newencoding type /arraytype eq {newdict /Encoding newencoding put} if newdict /Metrics entries dict put newdict /Metrics get begin chtab aload pop 1 1 entries {pop def} for newfont newdict definefont pop end } bind def % % A few arrays used to adjust reference points and character widths in some % of the printer resident fonts. If square roots are too high try changing % the lines describing /radical and /radicalex to, % % /radical [0 -75 550 0] % /radicalex [-50 -75 500 0] % % Move braceleftbt a bit - default PostScript character is off a bit. % /Sdefs [ /bracketlefttp [201 500] /bracketleftbt [201 500] /bracketrighttp [-81 380] /bracketrightbt [-83 380] /braceleftbt [203 490] /bracketrightex [220 -125 500 0] /radical [0 0 550 0] /radicalex [-50 0 500 0] /parenleftex [-20 -170 0 0] /integral [100 -50 500 0] /infinity [10 -75 730 0] ] def /S1defs [ /underscore [0 80 500 0] /endash [7 90 650 0] ] def % % Tries to round clipping path dimensions, as stored in array pagebbox, so they % match one of the known sizes in the papersizes array. Lower left coordinates % are always set to 0. % /roundpagebbox { 7 dict begin /papersizes [8.5 inch 11 inch 14 inch 17 inch] def /mappapersize { /val exch def /slop .5 inch def /diff slop def /j 0 def 0 1 papersizes length 1 sub { /i exch def papersizes i get val sub abs dup diff le {/diff exch def /j i def} {pop} ifelse } for diff slop lt {papersizes j get} {val} ifelse } def pagebbox 0 0 put pagebbox 1 0 put pagebbox dup 2 get mappapersize 2 exch put pagebbox dup 3 get mappapersize 3 exch put end } bind def %%EndProlog %%BeginSetup mark /resolution 720 def setup 2 setdecoding %%EndSetup %%Page: 1 1 /saveobj save def mark 1 pagesetup 10 R f (Appendix 3)1 469 1 2825 120 t (BANDED MATRICES)1 972 1 2574 360 t ( Solve)1 253( Back)1 380(BABS -)1 395 3 720 720 t ( Estimation)1 459( Condition)1 576(BACE -)1 400 3 720 840 t ( DeComposition)1 809(BADC -)1 411 2 720 960 t ( Solve)1 253( Forward)1 513(BAFS -)1 384 3 720 1080 t ( Equation solution)2 734( Linear)1 435(BALE -)1 394 3 720 1200 t ( decomposition)1 614( LU)1 308(BALU -)1 405 3 720 1320 t ( MuLtiplication)1 781(BAML -)1 422 2 720 1440 t ( NorM)1 419(BANM -)1 433 2 720 1560 t ( Solution)1 365( System)1 470(BASS -)1 384 3 720 1680 t cleartomark showpage saveobj restore %%EndPage: 1 1 %%Page: 2 2 /saveobj save def mark 2 pagesetup 10 R f (BABS \320 band upper triangular linear system solution)7 2174 1 1793 120 t 9 B f (Purpose:)720 480 w 10 R f ( solves AX = B where A is a banded upper triangular)11 2165(BABS \(BAnded matrix Back Solution\))4 1579 2 1296 480 t ( is)1 100(matrix. It can be used for the back solution phase of a banded linear system solution. \(It)16 3644 2 1296 600 t (used in this way by the routines BASS and BALE.\))9 2055 1 1296 720 t 9 B f (Usage:)720 1080 w 10 R f (CALL BABS \(N, G, IG, B, IB, NB, MU\))8 1655 1 1296 1080 t (N)1440 1320 w 14 S f (\256)1980 1340 w 10 R f (the number of equations)3 968 1 2196 1320 t (G)1440 1560 w 14 S f (\256)1980 1580 w 10 R f ( BACE, BADC,)2 649(a matrix \(which may have been created by the routines)9 2195 2 2196 1560 t (or BALU\) into which A has been packed as follows:)9 2099 1 2196 1680 t (G \(j-i + 1, i\) =)5 567 1 2916 1800 t 10 I f (a)3508 1800 w 7 I f (i j)1 45 1 3569 1820 t 10 R f (i.e. the diagonal is the \256rst row of G,)8 1468 1 2196 1920 t (\(See the introduction to this chapter.\))5 1487 1 2196 2040 t ( in the calling program, where)5 1348(G should be dimensioned \(IG,KG\))4 1496 2 2196 2160 t (IG)2196 2280 w 10 S f (\263)2301 2280 w 10 R f (MU and KG)2 499 1 2356 2280 t 10 S f (\263)2855 2280 w 10 R f (N.)2910 2280 w (IG)1440 2520 w 14 S f (\256)1980 2540 w 10 R f ( in the calling pro-)4 778(the row \(leading\) dimension of G, as dimensioned)7 2066 2 2196 2520 t (gram)2196 2640 w (B)1440 2880 w 14 S f (\256)1980 2900 w 10 R f ( right-hand sides, dimensioned \(IB,KB\) in the calling pro-)8 2328(the matrix of)2 516 2 2196 2880 t (gram, where IB)2 623 1 2196 3000 t 10 S f (\263)2819 3000 w 10 R f (N and KB)2 405 1 2874 3000 t 10 S f (\263)3279 3000 w 10 R f (NB)3334 3000 w 14 S f (\254)1980 3260 w 10 R f (the solution X)2 567 1 2196 3240 t (IB)1440 3480 w 14 S f (\256)1980 3500 w 10 R f ( dimension of B, as dimensioned in the calling pro-)9 2139(the row \(leading\))2 705 2 2196 3480 t (gram)2196 3600 w (NB)1440 3840 w 14 S f (\256)1980 3860 w 10 R f (the number of right-hand sides)4 1226 1 2196 3840 t (MU)1440 4080 w 14 S f (\256)1980 4100 w 10 R f (the number of nonzero bands in A)6 1364 1 2196 4080 t 9 B f (Notes:)720 4440 w 10 R f ( on the output matrix produced by BADC, BALU, or)9 2181(BAFS and BABS can be used directly)6 1563 2 1296 4440 t (BACE to solve a general linear system.)6 1573 1 1296 4560 t 9 B f (Error situations:)1 653 1 720 4920 t 10 R f ( see)1 183( \320)1 125( those errors marked with an asterisk)6 1505(*\(The user can elect to `recover' from)6 1546 4 1517 4920 t 10 I f (Er-)4907 4920 w (ror Handling)1 531 1 1512 5040 t 10 R f (, Framework Chapter\))2 884 1 2043 5040 t (Number Error)1 1506 1 1800 5280 t (1 N)1 1008 1 1944 5520 t 10 S f (<)2977 5520 w 10 R f (1)3057 5520 w (2 IG)1 1041 1 1944 5760 t 10 S f (<)3010 5760 w 10 R f (MU)3090 5760 w (3 IB)1 1036 1 1944 6000 t 10 S f (<)3005 6000 w 10 R f (N)3085 6000 w (4 NB)1 1075 1 1944 6240 t 10 S f (<)3044 6240 w 10 R f (1)3124 6240 w (5 MU)1 1097 1 1944 6480 t 10 S f (<)3066 6480 w 10 R f (1)3146 6480 w ( matrix with 0.0 in the kth position on the di-)10 1838( singular)1 952(10 + k*)2 306 3 1944 6720 t (agonal)2880 6840 w (Linear Algebra)1 606 1 360 7500 t (\320 2 \320)2 300 1 2730 7620 t (BABS)360 7740 w cleartomark showpage saveobj restore %%EndPage: 2 2 %%Page: 3 3 /saveobj save def mark 3 pagesetup 10 R f (-- --)1 5544 1 0 120 t 8 R f (PORT)360 600 w 10 R f ( Algebra)1 346(library Linear)1 4463 2 591 600 t ( BABS)1 4305(February 11, 1993)2 735 2 360 840 t 9 B f (Double-precision version:)1 988 1 720 1320 t 10 R f (DBABS with G and B declared double precision.)7 1970 1 1783 1320 t 9 B f (Complex version:)1 678 1 720 1680 t 10 R f (CBABS with G and B declared complex)6 1621 1 1473 1680 t 9 B f (Storage:)720 2040 w 10 R f (None)1296 2040 w 9 B f (Time:)720 2400 w 10 R f (NB)1296 2400 w 10 S f (\264)1435 2400 w 10 R f (N)1490 2400 w 10 S f (\264)1562 2400 w 10 R f (\(MU)1617 2400 w 10 S f (-)1836 2400 w 10 R f (1\) additions)1 475 1 1916 2400 t (NB)1296 2520 w 10 S f (\264)1435 2520 w 10 R f (N)1490 2520 w 10 S f (\264)1562 2520 w 10 R f (\(MU)1617 2520 w 10 S f (-)1836 2520 w 10 R f (1\) multiplications)1 709 1 1916 2520 t (NB)1296 2640 w 10 S f (\264)1435 2640 w 10 R f (N divisions)1 459 1 1490 2640 t 9 B f (See also:)1 333 1 720 3000 t 10 R f (BAFS, BADC, BALU, BACE, BASS, BALE)5 1830 1 1296 3000 t 9 B f (Author:)720 3360 w 10 R f (Linda Kaufman)1 629 1 1296 3360 t 9 B f (Reference:)720 3720 w 10 R f ( Band Equa-)2 519(Martin, R. S., and Wilkinson, J. H., Solution of Symmetric and Unsymmetric)11 3191 2 1330 3720 t (tions and the Calculation of Eigenvectors of Band Matrices,)8 2394 1 1296 3840 t 10 I f (Numer. Math. 9)2 633 1 3715 3840 t 10 R f (\(1967\) 279-301.)1 649 1 4373 3840 t 9 B f (Example:)720 4200 w 10 R f ( example we present a subroutine which implements the inverse iteration for \256nding)12 3482(In this)1 262 2 1296 4200 t (the eigenvector)1 619 1 1296 4320 t 10 I f (x)1947 4320 w 10 R f (corresponding to a speci\256ed real eigenvalue)5 1789 1 2023 4320 t 10 S f (l)3844 4320 w 10 R f ( The)1 211( banded matrix A.)3 739(of a)1 159 3 3931 4320 t (algorithm is essentially)2 928 1 1296 4440 t (Determine)1396 4680 w 10 I f (x)1842 4680 w 7 R f (0)1897 4700 w 10 R f (, an initial approximation to the eigenvector)6 1751 1 1940 4680 t (Until convergence)1 734 1 1396 4800 t (Solve \()1 286 1 1446 4920 t 10 I f (A)1740 4920 w 10 S f (- l)1 118 1 1809 4920 t 10 I f (I)1935 4920 w 10 R f (\))1976 4920 w 10 I f (x)2025 4920 w 7 I f (k)2080 4940 w 7 S f (+)2127 4940 w 7 R f (1)2177 4940 w 10 S f (= a)1 167 1 2269 4920 t 7 I f (k)2447 4940 w 10 I f (x)2527 4920 w 7 I f (k)2582 4940 w 10 R f (where 1/)1 346 1 1296 5160 t 10 S f (a)1642 5160 w 7 I f (k)1716 5180 w 10 R f (is the element of)3 663 1 1780 5160 t 10 I f (x)2468 5160 w 7 I f (k)2523 5180 w 10 R f (of maximum modulus.)2 909 1 2587 5160 t (Given the LU decomposition of)4 1283 1 1296 5400 t 10 I f (A)2607 5400 w 10 S f (- l)1 126 1 2692 5400 t 10 I f (I)2826 5400 w 10 R f (, the starting vector)3 780 1 2859 5400 t 10 I f (x)3667 5400 w 7 R f (0)3722 5420 w 10 R f (is usually set to)3 629 1 3793 5400 t 10 I f (U)4450 5400 w 7 S f (-)4533 5360 w 7 R f (1)4583 5360 w 10 R f (e, where e)2 414 1 4626 5400 t ( above reference indicates, a suitable stop-)6 1716( the)1 152( As)1 166(is the vector whose elements are all unity.)7 1710 4 1296 5520 t (ping criteria is)2 577 1 1296 5640 t 10 S f (\357 \357)1 106 1 1898 5640 t 10 I f (A)2012 5640 w 10 S f ( \357)1 57( e \263 \357)3 271(\357 \357)1 106 3 2081 5640 t 10 R f (\()2523 5640 w 10 S f (a)2564 5640 w 7 I f (k)2638 5660 w 7 S f (-)2685 5660 w 7 R f (1)2735 5660 w 10 I f (x)2786 5640 w 7 I f (k)2841 5660 w 7 S f (-)2888 5660 w 7 R f (1)2938 5660 w 10 S f (- b)1 126 1 2997 5640 t 7 I f (k)3134 5660 w 10 I f (x)3181 5640 w 7 I f (k)3236 5660 w 10 R f (\))3283 5640 w 10 S f (a)3332 5640 w 7 I f (k)3406 5660 w 10 S f (\357 \357)1 106 1 3453 5640 t 5 S f (\245)3594 5660 w 10 R f (where)1296 5880 w 10 S f (e)1568 5880 w 10 R f (is the machine precision given by R1MACH\(4\) and 1/)8 2202 1 1641 5880 t 10 S f (b)3843 5880 w 7 I f (k)3909 5900 w 10 R f (is the element of)3 678 1 3978 5880 t 10 I f (x)4686 5880 w 7 I f (k)4741 5900 w 10 R f (in the)1 230 1 4810 5880 t (same position as the unit element of)6 1438 1 1296 6000 t 10 S f (a)2759 6000 w 7 I f (k)2833 6020 w 7 S f (-)2880 6020 w 7 R f (1)2930 6020 w 10 I f (x)2981 6000 w 7 I f (k)3036 6020 w 7 S f (-)3083 6020 w 7 R f (1)3133 6020 w 10 R f (.)3176 6000 w ( obtain the initial ap-)4 877(In the subroutine EIGVEC below, BABS is referenced twice, once to)10 2867 2 1296 6240 t ( If)1 119(proximation and once within the iterative loop.)6 1897 2 1296 6360 t 10 S f (l)3339 6360 w 10 R f (is an eigenvalue of A,)4 881 1 3421 6360 t 10 I f (A)4329 6360 w 10 S f (- l)1 126 1 4414 6360 t 10 I f (I)4548 6360 w 10 R f (is theoreti-)1 432 1 4608 6360 t ( singular matrix and hence when BALU is invoked, one would expect the subroutine)13 3475(cally a)1 269 2 1296 6480 t ( after calling BALU the error \257ag is turned off if)10 1980( Thus)1 255(to terminate with a recoverable error.)5 1509 3 1296 6600 t ( than)1 206( BALU determines that a diagonal element of the U matrix is not greater)13 3002(necessary. If)1 536 3 1296 6720 t ( the computation continues. Al-)4 1303(EPS in magnitude, that diagonal element is set to EPS and)10 2441 2 1296 6840 t (Linear Algebra)1 606 1 4794 7500 t (\320 3 \320)2 300 1 2730 7620 t (BABS)5138 7740 w cleartomark showpage saveobj restore %%EndPage: 3 3 %%Page: 4 4 /saveobj save def mark 4 pagesetup 10 R f (-- --)1 5544 1 0 120 t (Linear Algebra)1 606 1 360 600 t 8 R f (PORT)4903 600 w 10 R f (library)5134 600 w ( 11, 1993)2 375(BABS February)1 4665 2 360 840 t (though the computed vectors)3 1172 1 1296 1320 t 10 I f (x)2498 1320 w 7 I f (k)2553 1340 w 10 R f ( lin-)1 170(will not be necessarily close to the true solutions of the)10 2248 2 2622 1320 t (ear systems, after these vectors are scaled, they will approach an eigenvector of the matrix.)14 3626 1 1296 1440 t 8 CW f (SUBROUTINE EIGVEC\(N,M,ML,G,IG,EVAL,EVEC,LIMIT\))1 2208 1 2040 1780 t (C)1656 1880 w (C GIVEN A BANDED MATRIX PACKED INTO G WITH)8 2016 1 1656 1980 t (C N ROWS, M NONZERO DIAGONALS AND ML NONZERO DIAGONALS)9 2592 1 1656 2080 t (C ON AND BELOW THE DIAGONAL AND GIVEN AN EIGENVALUE OF THE)11 2784 1 1656 2180 t (C MATRIX IN EVAL, THIS SUBROUTINE USES INVERSE ITERATION TO)9 2832 1 1656 2280 t (C DETERMINE THE CORRESPONDING EIGENVECTOR AND RETURNS IT)7 2688 1 1656 2380 t (C IN EVEC.)2 480 1 1656 2480 t (C LIMIT IS A BOUND ON THE NUMBER OF ITERATIONS)9 2208 1 1656 2580 t (C)1656 2680 w (INTEGER N, M, ML, IG, LIMIT)5 1296 1 1992 2780 t (INTEGER I, JAL, ISTKGT, JINTER, JX, MU, IERR, NERROR)8 2496 1 1992 2880 t (INTEGER LIM, JJ, ISAMAX, JXI, IST\(1000\))5 1872 1 1992 2980 t (REAL G\(IG, N\), EVEC\(N\), EVAL)4 1344 1 1992 3080 t (REAL BANM, SIZE, R1MACH, EPS, SC, BET, D1, SC2, ABS)9 2448 1 1992 3180 t (REAL R\(1000\))1 576 1 1992 3280 t (DOUBLE PRECISION D\(500\))2 1104 1 1992 3380 t (COMMON /CSTAK/ D)2 768 1 1992 3480 t (EQUIVALENCE \(D\(1\),IST\(1\)\),\(R\(1\),D\(1\)\))1 1776 1 1992 3580 t (CALL ENTER\(1\))1 624 1 1992 3680 t (C DETERMINE ITERATION TOLERANCE)3 1488 1 1656 3780 t (CALL BANM\(N,ML,M,G,IG,SIZE\))1 1296 1 1992 3880 t (EPS=SIZE*R1MACH\(4\))1992 3980 w (C SUBTRACT EIGENVALUE FROM DIAGONAL OF G)6 1920 1 1656 4080 t (DO 10 I=1,N)2 528 1 1992 4180 t (G\(ML,I\)=G\(ML,I\) - EVAL)2 1056 1 2136 4280 t (10 CONTINUE)1 624 1 1752 4380 t (C GET SPACE FROM STACK FOR AL,INTER, AND SCRATCH VECTOR)9 2640 1 1656 4480 t (JAL =ISTKGT\(N*\(ML-1\),3\))1 1104 1 1992 4580 t (JINTER=ISTKGT\(N,2\))1992 4680 w (JX=ISTKGT\(N,3\))1992 4780 w (C GET LU DECOMPOSITION OF MATRIX)5 1536 1 1656 4880 t (CALL BALU\(N,ML,M,G,IG,R\(JAL\),ML-1,IST\(JINTER\),MU,EPS\))1 2544 1 1992 4980 t (C OBTAIN INITIAL RIGHT HAND SIDE)5 1536 1 1656 5080 t (IF \(NERROR\(IERR\).NE.0\) CALL ERROFF)3 1632 1 1992 5180 t (DO 20 I=1,N)2 528 1 1992 5280 t (EVEC\(I\)=1.0)2136 5380 w (20 CONTINUE)1 624 1 1752 5480 t (CALL BABS\(N,G,IG,EVEC,N,1,MU\))1 1392 1 1992 5580 t (LIM=0)1992 5680 w (JJ=ISAMAX\(N,EVEC,1\))1992 5780 w (SC=1.0/EVEC\(JJ\))1992 5880 w (C SCALE FIRST RHS TO HAVE INFINITY NORM OF 1)9 2112 1 1656 5980 t (CALL SSCAL\(N,SC,EVEC,1\))1 1104 1 1992 6080 t (C ITERATIVE PHASE BEGINS HERE)4 1392 1 1656 6180 t (30 LIM=LIM+1)1 672 1 1752 6280 t (C MAKE A COPY OF OLD APPROXIMATION)6 1632 1 1656 6380 t (CALL MOVEFR\(N,EVEC,R\(JX\)\))1 1200 1 1992 6480 t (C GET NEW APPROXIMATION OF EIGNVECTOR)5 1776 1 1656 6580 t (CALL BAFS\(N,ML,R\(JAL\),ML-1,IST\(JINTER\),EVEC,N,1\))1 2304 1 1992 6680 t (CALL BABS\(N,G,IG,EVEC,N,1,MU\))1 1392 1 1992 6780 t (BET=1.0/EVEC\(JJ\))1992 6880 w 10 R f (Linear Algebra)1 606 1 360 7540 t (\320 4 \320)2 300 1 2730 7660 t (BABS)360 7780 w cleartomark showpage saveobj restore %%EndPage: 4 4 %%Page: 5 5 /saveobj save def mark 5 pagesetup 10 R f (-- --)1 5544 1 0 120 t 8 R f (PORT)360 600 w 10 R f ( Algebra)1 346(library Linear)1 4463 2 591 600 t ( BABS)1 4305(February 11, 1993)2 735 2 360 840 t 8 CW f (JJ=ISAMAX\(N,EVEC,1\))1992 1300 w (SC2=1.0/EVEC\(JJ\))1992 1400 w (C COMPUTE CONVERGENCE CRITERIA)3 1440 1 1656 1500 t (D1=0.0)1992 1600 w (DO 40 I=1,N)2 528 1 1992 1700 t (JXI=JX-1+I)2136 1800 w (D1=AMAX1\(D1,ABS\(\(R\(JXI\)-BET*EVEC\(I\)\)*SC2\)\))2136 1900 w (40 CONTINUE)1 624 1 1752 2000 t (SC=SC2)1992 2100 w (CALL SSCAL\(N,SC,EVEC,1\))1 1104 1 1992 2200 t (C TEST FOR CONVERGENCE AND IF ITERATION LIMIT EXCEEDED)8 2592 1 1656 2300 t (IF \(D1.GT.EPS.AND.LIM.LT.LIMIT\) GO TO 30)4 1920 1 1992 2400 t (CALL LEAVE)1 480 1 1992 2500 t (RETURN)1992 2600 w (END)1992 2700 w 10 R f ( works, a mainline program was written that packed into G)10 2419(To show that the above program)5 1325 2 1296 3060 t (the matrix)1 408 1 1296 3180 t (-.75 -.5)1 466 1 1786 3420 t ( -1.0)1 308(-.5 1.0)1 466 2 1786 3540 t ( -1.0)1 308(-1.0 1.0)1 466 2 2094 3660 t ( -1.)1 258(-1.0 1.0)1 466 2 2402 3780 t (...)2751 3900 w ( -1.0)1 308(-1.0 1.0)1 466 2 3018 4020 t ( -.5)1 258(-1.0 1.0)1 466 2 3326 4140 t (-.5 -.75)1 416 1 3684 4260 t (and invoked EIGVEC with the eigenvalue at -1.0.)7 1994 1 1296 4500 t 8 CW f (INTEGER N, I IWRITE, I1MACH)4 1296 1 1992 4840 t (REAL G\(3, 200\), EVEC\(100\))3 1200 1 1992 4940 t (N=10)1992 5040 w (DO 10 I=1,N)2 528 1 1992 5140 t (G\(1,I\)=-1.0)2136 5240 w (G\(2,I\)=1.0)2136 5340 w (G\(3,I\)=-1.0)2136 5440 w (10 CONTINUE)1 624 1 1752 5540 t (G\(2,1\)=-.75)1992 5640 w (G\(2,N\)=-.75)1992 5740 w (G\(3,1\)=-.5)1992 5840 w (G\(1,2\)=-.5)1992 5940 w (G\(1,N\)=-.5)1992 6040 w (G\(3,N-1\)=-.5)1992 6140 w (IWRITE=I1MACH\(2\))1992 6240 w (CALL EIGVEC\(N,3,2,G,3,-1.0,EVEC,2\))1 1632 1 1992 6340 t (DO 20 I=1,N)2 528 1 1992 6440 t (WRITE\(IWRITE,21\)EVEC\(I\))2136 6540 w (20 CONTINUE)1 720 1 1656 6640 t ( EIGENVECTOR,F16.8\))1 912(21 FORMAT\(12H)1 816 2 1656 6740 t (STOP)1992 6840 w 10 R f (Linear Algebra)1 606 1 4794 7500 t (\320 5 \320)2 300 1 2730 7620 t (BABS)5138 7740 w cleartomark showpage saveobj restore %%EndPage: 5 5 %%Page: 6 6 /saveobj save def mark 6 pagesetup 10 R f (-- --)1 5544 1 0 120 t (Linear Algebra)1 606 1 360 600 t 8 R f (PORT)4903 600 w 10 R f (library)5134 600 w ( 11, 1993)2 375(BABS February)1 4665 2 360 840 t 8 CW f (END)1992 1300 w 10 R f ( on the Honeywell 6000 machine at Bell Laboratories,)8 2174(When the above program was executed)5 1570 2 1296 1660 t (which has about 8 decimal digits of precision, the following was printed:)11 2914 1 1296 1780 t (EIGENVECTOR 1.00000000)1 1324 1 1321 2020 t (EIGENVECTOR 0.49999998)1 1324 1 1321 2140 t (EIGENVECTOR 0.49999996)1 1324 1 1321 2260 t (EIGENVECTOR 0.49999994)1 1324 1 1321 2380 t (EIGENVECTOR 0.49999991)1 1324 1 1321 2500 t (EIGENVECTOR 0.49999989)1 1324 1 1321 2620 t (EIGENVECTOR 0.49999986)1 1324 1 1321 2740 t (EIGENVECTOR 0.49999982)1 1324 1 1321 2860 t (EIGENVECTOR 0.49999976)1 1324 1 1321 2980 t (EIGENVECTOR 0.99999938)1 1324 1 1321 3100 t ( 1. 0 , 0. 5 , 0. 5 ,... , 0. 5 , 1. 0 \))16 986( is \()2 182(Since the true eigenvector)3 1084 3 1296 3340 t 7 I f (T)3559 3300 w 10 R f (, the fact that the eigenvector was)6 1434 1 3606 3340 t (computed by solving an ill-conditioned linear system did not affect our answer.)11 3174 1 1296 3460 t (Linear Algebra)1 606 1 360 7500 t (\320 6 \320)2 300 1 2730 7620 t (BABS)360 7740 w cleartomark showpage saveobj restore %%EndPage: 6 6 %%Page: 7 7 /saveobj save def mark 7 pagesetup 10 R f (-- --)1 5544 1 0 120 t 8 R f (PORT)360 600 w 10 R f ( Algebra)1 346(library Linear)1 4463 2 591 600 t ( BABS)1 4305(February 11, 1993)2 735 2 360 840 t ( decomposition of a banded unsymmetric matrix with condition estimation)9 2985( LU)1 183(BACE \320)1 392 3 1388 1320 t 9 B f (Purpose:)720 1680 w 10 R f ( bound for the condition number)5 1311(BACE \(BAnded matrix Condition Estimation\) gives a lower)7 2433 2 1296 1680 t ( LU decomposition of the matrix and may be)8 1798( also returns the)3 638( It)1 112(of a general banded matrix A.)5 1196 4 1296 1800 t (used in place of BADC in a linear equation package.)9 2101 1 1296 1920 t 9 B f (Usage:)720 2280 w 10 R f (CALL BACE \(N, ML, M, G, IG, AL, IAL, INTER, MU, COND\))11 2619 1 1296 2280 t (N)1440 2520 w 14 S f (\256)1980 2540 w 10 R f (the order of the matrix A)5 995 1 2196 2520 t (ML)1440 2760 w 14 S f (\256)1980 2780 w 10 R f (the number of nonzero bands on and below the diagonal of A)11 2448 1 2196 2760 t (M)1440 3000 w 14 S f (\256)1980 3020 w 10 R f (the number of nonzero bands in A)6 1364 1 2196 3000 t (G)1440 3240 w 14 S f (\256)1980 3260 w 10 R f (a matrix into which the matrix A has been packed as follows:)11 2449 1 2196 3240 t (G \(ML + j)3 414 1 2916 3420 t 10 S f (-)3330 3420 w 10 R f (i, i\) =)2 220 1 3385 3420 t 10 I f (a)3630 3420 w 7 I f (i j)1 45 1 3691 3440 t 10 R f (i.e. the leftmost diagonal of A is in the \256rst row of G)12 2104 1 2196 3600 t (\(See the introduction to this chapter.\))5 1487 1 2196 3720 t ( the calling program, where IG)5 1235(G should be dimensional \(IG,KG\) in)5 1465 2 2196 3840 t 10 S f (\263)4896 3840 w 10 R f (M)4951 3840 w (and KG)1 313 1 2196 3960 t 10 S f (\263)2509 3960 w 10 R f (N.)2564 3960 w 14 S f (\254)1980 4220 w 10 R f (the upper triangular factor of A \(see)6 1434 1 2196 4200 t 8 B f (Note 2)1 219 1 3655 4200 t 10 R f (\))3874 4200 w (IG)1440 4440 w 14 S f (\256)1980 4460 w 10 R f (the row \(leading\) dimension of G, as dimensioned in the)9 2253 1 2196 4440 t (calling program)1 635 1 2196 4560 t (AL)1440 4800 w 14 S f (\254)1980 4820 w 10 R f (the lower triangular factor of A \(see)6 1434 1 2196 4800 t 8 B f (Note 2)1 219 1 3655 4800 t 10 R f (\))3874 4800 w (IAL)1440 5040 w 14 S f (\256)1980 5060 w 10 R f (the row \(leading\) dimension of AL, as dimensioned in the)9 2314 1 2196 5040 t (calling program)1 635 1 2196 5160 t (INTER)1440 5400 w 14 S f (\254)1980 5420 w 10 R f ( N recording the row interchanges per-)6 1695(an integer vector of length)4 1149 2 2196 5400 t (formed during the decomposition \(see)4 1520 1 2196 5520 t 8 B f (Note 2)1 219 1 3741 5520 t 10 R f (\))3960 5520 w (MU)1440 5760 w 14 S f (\254)1980 5780 w 10 R f (the number of nonzero bands in the upper triangular factor)9 2336 1 2196 5760 t (COND)1440 6000 w 14 S f (\254)1980 6020 w 10 R f (an estimate of the condition number of A \(see)8 1830 1 2196 6000 t 8 B f (Note 1)1 219 1 4051 6000 t 10 R f (\))4270 6000 w (Linear Algebra)1 606 1 4794 7500 t (\320 7 \320)2 300 1 2730 7620 t (BACE)5133 7740 w cleartomark showpage saveobj restore %%EndPage: 7 7 %%Page: 8 8 /saveobj save def mark 8 pagesetup 10 R f (-- --)1 5544 1 0 120 t (Linear Algebra)1 606 1 360 600 t 8 R f (PORT)4903 600 w 10 R f (library)5134 600 w ( 11, 1993)2 375(BACE February)1 4665 2 360 840 t 9 B f (Note 1:)1 278 1 720 1320 t 10 R f ( to errors in)3 481(The condition number measures the sensitivity of the solution of a linear system)12 3263 2 1296 1320 t ( the elements of the matrix and the right-hand side\(s\))9 2134( If)1 118( and in the right-hand side.)5 1081(the matrix)1 411 4 1296 1440 t (of your linear system have)4 1091 1 1296 1560 t 10 B f (d)2420 1560 w 10 R f ( solution might have as few as)6 1264(decimal digits of precision, the)4 1267 2 2509 1560 t 10 B f (d)1296 1680 w 10 S f (-)1377 1680 w 10 R f (log)1457 1680 w 7 R f (10)1596 1700 w 10 R f ( if COND is greater than 10)6 1121( Thus)1 252(\(COND\) correct decimal digits.)3 1270 3 1674 1680 t 7 R f (Bd)4327 1640 w 7 I f (P)4419 1640 w 10 R f ( be)1 120(, there may)2 450 2 4470 1680 t (no correct digits.)2 674 1 1296 1800 t 9 B f (Note 2:)1 278 1 720 2280 t 10 R f ( AL are suitable for input into the forward)8 1744(After execution of BACE, the arrays INTER and)7 2000 2 1296 2280 t ( LU de-)2 320( The)1 210( and G is suitable for input into the back solver BABS.)11 2243(solve subroutine BAFS,)2 971 4 1296 2400 t ( a permutation matrix, L is a unit)7 1358(composition of A satis\256es the equation PA=LU where P is)9 2386 2 1296 2520 t ( return from BACE the ele-)5 1125( On)1 178( matrix.)1 317(lower triangular matrix and U is an upper triangular)8 2124 4 1296 2640 t (ment)1296 2760 w 10 I f (u)1525 2760 w 7 I f (i j)1 45 1 1586 2780 t 10 R f (is contained in G\(j)3 753 1 1668 2760 t 10 S f (-)2421 2760 w 10 R f ( occupies the \256rst row of the G)7 1269(i+1,i\), so that the main diagonal)5 1295 2 2476 2760 t ( etc. The matrix P can be obtained)7 1420(matrix, the \256rst super diagonal occupies the second row,)8 2324 2 1296 2880 t ( to this chapter\), and the)5 970(from INTER \(see the introduction)4 1359 2 1296 3000 t 10 I f (i)3651 3000 w 7 I f (th)3690 2960 w 10 R f (column of the L matrix appears)5 1261 1 3779 3000 t (permuted in the)2 635 1 1296 3120 t 10 I f (i)1960 3120 w 7 I f (th)1999 3080 w 10 R f ( are all 1, they)4 580( the diagonal elements of L)5 1110( Since)1 276(column of the AL array.)4 983 4 2091 3120 t (are not stored.)2 568 1 1296 3240 t 9 B f (Error situations:)1 653 1 720 3600 t 10 R f ( see)1 183( \320)1 125( those errors marked with an asterisk)6 1505(*\(The user can elect to `recover' from)6 1546 4 1517 3600 t 10 I f (Er-)4907 3600 w (ror Handling)1 531 1 1512 3720 t 10 R f (, Framework Chapter\))2 884 1 2043 3720 t (Number Error)1 1506 1 1800 3960 t (1 N)1 1008 1 1944 4200 t 10 S f (<)2977 4200 w 10 R f (1)3057 4200 w (2 ML)1 1086 1 1944 4440 t 10 S f (<)3055 4440 w 10 R f (1)3135 4440 w (3 M)1 1025 1 1944 4680 t 10 S f (<)2994 4680 w 10 R f (ML)3074 4680 w (4 IG)1 1041 1 1944 4920 t 10 S f (<)3010 4920 w 10 R f (M)3090 4920 w (5 IAL)1 1102 1 1944 5160 t 10 S f (<)3071 5160 w 10 R f (ML)3151 5160 w 10 S f (-)3326 5160 w 10 R f (1)3406 5160 w ( matrix whose rank is at least k)7 1240( singular)1 952(10 + k*)2 306 3 1944 5400 t 9 B f (Double-precision version:)1 988 1 720 5760 t 10 R f (DBACE with G, AL and EPS declared double precision.)8 2264 1 1783 5760 t 9 B f (Complex version:)1 678 1 720 6120 t 10 R f (CBACE with G and AL declared complex)6 1692 1 1448 6120 t 9 B f (Storage:)720 6480 w 10 R f ( precision for DBACE, complex for CBACE\) locations of scratch storage in)11 3150(N real \(double)2 594 2 1296 6480 t (the dynamic storage stack)3 1034 1 1296 6600 t (Linear Algebra)1 606 1 360 7500 t (\320 8 \320)2 300 1 2730 7620 t (BACE)360 7740 w cleartomark showpage saveobj restore %%EndPage: 8 8 %%Page: 9 9 /saveobj save def mark 9 pagesetup 10 R f (-- --)1 5544 1 0 120 t 8 R f (PORT)360 600 w 10 R f ( Algebra)1 346(library Linear)1 4463 2 591 600 t ( BACE)1 4305(February 11, 1993)2 735 2 360 840 t 9 B f (Time:)720 1320 w 10 R f (at most N)2 389 1 1296 1320 t 10 S f (\264)1685 1320 w 10 R f (\(M)1740 1320 w 10 S f (\264)1862 1320 w 10 R f (ML+6)1917 1320 w 10 S f (\264)2173 1320 w 10 R f (M+ML\) additions)1 720 1 2228 1320 t (at most N)2 389 1 1296 1440 t 10 S f (\264)1685 1440 w 10 R f (\(ML)1740 1440 w 10 S f (\264)1923 1440 w 10 R f (M+3)1978 1440 w 10 S f (\264)2173 1440 w 10 R f (M+ML)2228 1440 w 10 S f (-)2523 1440 w 10 R f (1\) multiplications)1 709 1 2578 1440 t (N)1296 1560 w 10 S f (\264)1368 1560 w 10 R f (\(ML+1\) divisions)1 709 1 1423 1560 t 9 B f (Method:)720 1920 w 10 R f (Gaussian elimination with partial pivoting)4 1689 1 1296 1920 t (See the reference below for the method used to estimate the condition number.)12 3141 1 1296 2040 t (BACE calls BALU with EPS=0.0)4 1354 1 1296 2160 t 9 B f (See also:)1 333 1 720 2520 t 10 R f (BADC, BAFS, BABS, BALU, BALE, BASS)5 1825 1 1296 2520 t 9 B f (Author:)720 2880 w 10 R f (Linda Kaufman)1 629 1 1296 2880 t 9 B f (Reference:)720 3240 w 10 R f ( W., and Wilkinson, J. H., An estimate for the condi-)10 2154(Cline, A. K., Moler, C. B., Stewart, G.)7 1562 2 1324 3240 t (tion number,)1 511 1 1296 3360 t 10 I f (SIAM J. Numer. Anal. 16)4 1007 1 1857 3360 t 10 R f (\(1979\), 368-375.)1 674 1 2889 3360 t 9 B f (Example:)720 3720 w 10 R f ( numbers of \256ve matrices)4 1095(In the following example we obtain estimates of the condition)9 2649 2 1296 3720 t ( by)1 126(whose nonzero elements are given)4 1382 2 1296 3840 t 10 I f (a)2830 3840 w 7 I f (i j)1 45 1 2891 3860 t 10 S f (=)2993 3840 w 10 I f (i)3097 3840 w 10 S f (+)3174 3840 w 10 I f (j)3286 3840 w 10 R f (For each matrix, the 2)4 883 1 3340 3840 t 10 S f (\264)4223 3840 w 10 R f (ML)4278 3840 w 10 S f (-)4428 3840 w 10 R f (1 main diago-)2 557 1 4483 3840 t ( nonzero. The program fragment packing the matrix A into the array G uses the fact)15 3432(nals are)1 312 2 1296 3960 t ( extra values that get)4 826( The)1 205( a column of G is equivalent to traversing a row of A.)12 2138(that traversing)1 575 4 1296 4080 t (put into G by the program below are made zero inside the subroutine BACE.)13 3068 1 1296 4200 t (In this example we compare the condition number)7 2096 1 1296 4440 t 10 I f (K)3430 4440 w 10 S f ( \357)1 57(= \357)1 153 2 3546 4440 t 10 R f (A)3764 4440 w 10 S f ( \357)1 57( \357)1 123(\357 \357)1 106 3 3844 4440 t 10 R f (A)4138 4440 w 7 S f (-)4221 4400 w 7 R f (1)4271 4400 w 10 S f (\357 \357)1 106 1 4346 4440 t 10 R f (with the esti-)2 550 1 4490 4440 t ( the program below A)4 896( In)1 138(mate obtained by BACE.)3 1023 3 1296 4560 t 7 S f (-)3364 4520 w 7 R f (1)3414 4520 w 10 R f (is computed one column at a time and)7 1553 1 3487 4560 t 10 I f (K)1296 4680 w 10 R f ( the 1-norm,)2 493( In)1 134( the 1-norm.)2 493(is computed using)2 728 4 1388 4680 t 10 S f (\357\357)3262 4680 w 10 R f (A)3360 4680 w 10 S f (\357\357)3432 4680 w 10 R f ( our)1 159( In)1 134(is the maximum column sum.)4 1191 3 3556 4680 t (example)1296 4800 w 10 S f (\357\357)1667 4800 w 10 R f (A)1765 4800 w 10 S f (\357\357)1837 4800 w 10 R f (is M)1 189 1 1968 4800 t 10 S f (\264)2157 4800 w 10 R f (\(N)2212 4800 w 10 S f (-)2317 4800 w 10 R f (ML+1\))2372 4800 w 10 S f (\264)2661 4800 w 10 R f ( obtained by summing the M elements in col-)8 1872(2, which is)2 452 2 2716 4800 t (umn N)1 275 1 1296 4920 t 10 S f (-)1571 4920 w 10 R f (ML+1.)1626 4920 w 8 CW f (INTEGER IG, IGL, N, ML, M, I, J, MU, IWRITE, I1MACH)10 2448 1 1992 5260 t (INTEGER INTER\(80\))1 816 1 1992 5360 t (REAL G\(13, 80\), B\(80\), X\(80\), GL\(6, 80\))6 1872 1 1992 5460 t (REAL START, FLOAT, AINNO, COND, CONDNO, ABS, AINNOI)7 2448 1 1992 5560 t (IG=13)1992 5660 w (IGL=6)1992 5760 w (N=80)1992 5860 w (IWRITE=I1MACH\(2\))1992 5960 w (DO 60 ML=2,6)2 576 1 1992 6060 t (C)1656 6160 w (C CONSTRUCT THE MATRIX A\(I,J\)=I+J AND PACK IT INTO G)9 2496 1 1656 6260 t (M=2*ML - 1)2 480 1 2232 6360 t (START=-FLOAT\(M-ML\))2232 6460 w (DO 20 I=1,N)2 528 1 2232 6560 t (G\(1,I\)=START+FLOAT\(2*I\))2376 6660 w (DO 10 J=2,M)2 528 1 2376 6760 t (G\(J,I\)=G\(J-1,I\)+1.)2520 6860 w 10 R f (Linear Algebra)1 606 1 4794 7520 t (\320 9 \320)2 300 1 2730 7640 t (BACE)5133 7760 w cleartomark showpage saveobj restore %%EndPage: 9 9 %%Page: 10 10 /saveobj save def mark 10 pagesetup 10 R f (-- --)1 5544 1 0 120 t (Linear Algebra)1 606 1 360 600 t 8 R f (PORT)4903 600 w 10 R f (library)5134 600 w ( 11, 1993)2 375(BACE February)1 4665 2 360 840 t 8 CW f (10 CONTINUE)1 1008 1 1752 1300 t (20 CONTINUE)1 864 1 1752 1400 t (C)1656 1500 w (C DETERMINE AN ESTIMATE OF THE CONDITION NUMBER)7 2256 1 1656 1600 t (C AND COMPUTE THE LU DECOMPOSITION)5 1632 1 1656 1700 t (C)1656 1800 w (CALL BACE\(N,ML,M,G,IG,GL,IGL,INTER,MU,COND\))1 2064 1 2232 1900 t (C)1656 2000 w (C DETERMINE THE NORM OF THE INVERSE MATRIX BY)8 2160 1 1656 2100 t (C SOLVING FOR ONE COLUMN OF THE INVERSE MATRIX)8 2208 1 1656 2200 t (C AT A TIME)3 528 1 1656 2300 t (C)1656 2400 w (AINNO=0.0)2232 2500 w (DO 50 I=1,N)2 528 1 2232 2600 t (C)1656 2700 w (C FIND THE ITH COLUMN OF THE INVERSE MATRIX BY)9 2208 1 1656 2800 t (C SETTING THE RIGHT HAND SIDE TO THE ITH COLUMN)9 2256 1 1656 2900 t (C OF THE IDENTITY MATRIX)4 1152 1 1656 3000 t (C)1656 3100 w (DO 30 J=1,N)2 528 1 2424 3200 t (B\(J\)=0.0)2568 3300 w (30 CONTINUE)1 1056 1 1752 3400 t (B\(I\)=1.0)2424 3500 w (CALL BAFS\(N,ML,GL,IGL,INTER,B,80,1\))1 1680 1 2424 3600 t (CALL BABS\(N,G,IG,B,80,1,MU\))1 1296 1 2424 3700 t (C FIND THE NORM OF THE ITH COLUMN)7 1584 1 1656 3800 t (AINNOI=0.0)2424 3900 w (DO 40 J=1,N)2 528 1 2424 4000 t (AINNOI=AINNOI+ABS\(B\(J\)\))2568 4100 w (40 CONTINUE)1 1056 1 1752 4200 t (IF\(AINNOI.GT.AINNO\)AINNO=AINNOI)2424 4300 w (50 CONTINUE)1 912 1 1752 4400 t (WRITE\(IWRITE,51\)ML)2280 4500 w ( ML IS ,I4\))3 528(51 FORMAT\(/6H)1 1008 2 1752 4600 t (WRITE\(IWRITE,52\)COND)2280 4700 w ( CONDITION ESTIMATE IS,1PE15.7\))3 1488(52 FORMAT\(22H)1 1008 2 1752 4800 t (CONDNO=AINNO*FLOAT\(M*\(N-ML+1\)*2\))2280 4900 w (WRITE\(IWRITE,53\)CONDNO)2280 5000 w ( TRUE CONDITION NO. IS,1PE15.7\))4 1488(53 FORMAT\(22H)1 1008 2 1752 5100 t (60 CONTINUE)1 768 1 1752 5200 t (STOP)2136 5300 w (END)2136 5400 w 10 R f (Linear Algebra)1 606 1 360 7500 t (\320 10 \320)2 350 1 2705 7620 t (BACE)360 7740 w cleartomark showpage saveobj restore %%EndPage: 10 10 %%Page: 11 11 /saveobj save def mark 11 pagesetup 10 R f (-- --)1 5544 1 0 120 t 8 R f (PORT)360 600 w 10 R f ( Algebra)1 346(library Linear)1 4463 2 591 600 t ( BACE)1 4305(February 11, 1993)2 735 2 360 840 t ( on the Honeywell 6000 machine at Bell Laboratories,)8 2174(When the above program was executed)5 1570 2 1296 1320 t (the following was printed:)3 1052 1 1296 1440 t 8 CW f ( 2)1 192(ML IS)1 240 2 1704 1880 t ( 03)1 144( 6.1040422E)1 576(CONDITION ESTIMATE IS)2 1008 3 1704 1980 t ( 04)1 144( 1.8941539E)1 576(TRUE CONDITION NO. IS)3 1008 3 1704 2080 t ( 3)1 192(ML IS)1 240 2 1704 2280 t ( 02)1 144( 5.9552785E)1 576(CONDITION ESTIMATE IS)2 1008 3 1704 2380 t ( 03)1 144( 2.1467948E)1 576(TRUE CONDITION NO. IS)3 1008 3 1704 2480 t ( 4)1 192(ML IS)1 240 2 1704 2680 t ( 07)1 144( 1.0581919E)1 576(CONDITION ESTIMATE IS)2 1008 3 1704 2780 t ( 07)1 144( 2.9246300E)1 576(TRUE CONDITION NO. IS)3 1008 3 1704 2880 t ( 5)1 192(ML IS)1 240 2 1704 3080 t ( 04)1 144( 3.2465961E)1 576(CONDITION ESTIMATE IS)2 1008 3 1704 3180 t ( 04)1 144( 6.7086635E)1 576(TRUE CONDITION NO. IS)3 1008 3 1704 3280 t ( 6)1 192(ML IS)1 240 2 1704 3480 t ( 07)1 144( 3.5264744E)1 576(CONDITION ESTIMATE IS)2 1008 3 1704 3580 t ( 07)1 144( 8.6640243E)1 576(TRUE CONDITION NO. IS)3 1008 3 1704 3680 t 10 R f ( by BACE and the true condition)6 1328( estimated)1 435( condition number)2 737(In the comparison above of the)5 1244 4 1296 4020 t (number, the order of magnitude of the estimate is correct, which is all one is usually inter-)16 3744 1 1296 4140 t ( band matrix is usually a full)6 1150(ested in. Note that the inverse of a)7 1364 2 1296 4260 t 10 I f (n)3836 4260 w 10 S f (\264)3894 4260 w 10 I f (n)3957 4260 w 10 R f (matrix, and should rarely)3 1007 1 4033 4260 t (be calculated.)1 548 1 1296 4380 t (Linear Algebra)1 606 1 4794 7500 t (\320 11 \320)2 350 1 2705 7620 t (BACE)5133 7740 w cleartomark showpage saveobj restore %%EndPage: 11 11 %%Page: 12 12 /saveobj save def mark 12 pagesetup 10 R f (-- --)1 5544 1 0 120 t (Linear Algebra)1 606 1 360 600 t 8 R f (PORT)4903 600 w 10 R f (library)5134 600 w ( 11, 1993)2 375(BACE February)1 4665 2 360 840 t (BADC \320 decomposition of a banded unsymmetric matrix)7 2340 1 1998 1320 t 9 B f (Purpose:)720 1680 w 10 R f ( general banded)2 665(BADC \(BAnded matrix DeComposition\) \256nds the LU decompostion of a)9 3079 2 1296 1680 t (matrix A using partial pivoting.)4 1264 1 1296 1800 t 9 B f (Usage:)720 2160 w 10 R f ( MU\))1 244(CALL BADC \(N, ML, M, G, IG, AL, IAL, INTER,)9 2078 2 1296 2160 t (N)1440 2400 w 14 S f (\256)1980 2420 w 10 R f (the order of the matrix A)5 995 1 2196 2400 t (ML)1440 2640 w 14 S f (\256)1980 2660 w 10 R f (the number of nonzero bands on and below the diagonal of A)11 2448 1 2196 2640 t (M)1440 2880 w 14 S f (\256)1980 2900 w 10 R f (the number of nonzero bands in A)6 1364 1 2196 2880 t (G)1440 3120 w 14 S f (\256)1980 3140 w 10 R f (a matrix into which the matrix A has been packed as follows:)11 2449 1 2196 3120 t (G \(ML + j)3 414 1 2916 3300 t 10 S f (-)3330 3300 w 10 R f (i, i\) =)2 220 1 3385 3300 t 10 I f (a)3630 3300 w 7 I f (i j)1 45 1 3691 3320 t 10 R f (i.e. the leftmost diagonal of A is in the \256rst row of G)12 2104 1 2196 3480 t (\(See the introduction to this chapter.\))5 1487 1 2196 3600 t ( the calling program, where IG)5 1235(G should be dimensional \(IG,KG\) in)5 1465 2 2196 3720 t 10 S f (\263)4896 3720 w 10 R f (M)4951 3720 w (and KG)1 313 1 2196 3840 t 10 S f (\263)2509 3840 w 10 R f (N.)2564 3840 w 14 S f (\254)1980 4100 w 10 R f (the upper triangular factor U of A \(see)7 1531 1 2196 4080 t 8 B f (Note 1)1 219 1 3752 4080 t 10 R f (\))3971 4080 w (IG)1440 4320 w 14 S f (\256)1980 4340 w 10 R f (the row \(leading\) dimension of G, as dimensioned in the)9 2253 1 2196 4320 t (calling program)1 635 1 2196 4440 t (AL)1440 4680 w 14 S f (\254)1980 4700 w 10 R f (the lower triangular factor of A \(see)6 1434 1 2196 4680 t 8 B f (Note 1)1 219 1 3655 4680 t 10 R f (\))3874 4680 w (IAL)1440 4920 w 14 S f (\256)1980 4940 w 10 R f (the row \(leading\) dimension of AL, as dimensioned in the)9 2314 1 2196 4920 t (calling program)1 635 1 2196 5040 t (INTER)1440 5280 w 14 S f (\256)1980 5300 w 10 R f ( N recording the row interchanges per-)6 1695(an integer vector of length)4 1149 2 2196 5280 t (formed during the decomposition \(see)4 1520 1 2196 5400 t 8 B f (Note 1)1 219 1 3741 5400 t 10 R f (\))3960 5400 w (MU)1440 5640 w 14 S f (\254)1980 5660 w 10 R f (the number of nonzero bands in the upper triangular factor \(MU)10 2555 1 2196 5640 t 10 S f (\243)4751 5640 w 10 R f (M\))4806 5640 w (Linear Algebra)1 606 1 360 7500 t (\320 12 \320)2 350 1 2705 7620 t (BADC)360 7740 w cleartomark showpage saveobj restore %%EndPage: 12 12 %%Page: 13 13 /saveobj save def mark 13 pagesetup 10 R f (-- --)1 5544 1 0 120 t 8 R f (PORT)360 600 w 10 R f ( Algebra)1 346(library Linear)1 4463 2 591 600 t ( BADC)1 4305(February 11, 1993)2 735 2 360 840 t 9 B f (Note 1:)1 278 1 720 1320 t 10 R f ( the arrays INTER and AL are suitable for input into the forward)12 2667(After execution of BADC,)3 1077 2 1296 1320 t ( The)1 205( G is suitable for input into the back solve subroutine BABS.)11 2433(solve subroutine BAFS and)3 1106 3 1296 1440 t (LU decomposition of A satis\256es the equation PA=LU where P is a permutation matrix, L is a)16 3744 1 1296 1560 t ( return from BADC the)4 952( On)1 177( is an upper triangular matrix.)5 1212(unit lower triangular matrix and U)5 1403 4 1296 1680 t (element)1296 1800 w 10 I f (u)1640 1800 w 7 I f (i j)1 45 1 1701 1820 t 10 R f (is contained in G\(j)3 750 1 1782 1800 t 10 S f (-)2532 1800 w 10 R f ( main diagonal occupies the \256rst row of the)8 1763(i+1,i\), so that the)3 690 2 2587 1800 t ( obtained)1 370(G matrix, the \256rst super diagonal occupies the second row, etc. The matrix P can be)15 3374 2 1296 1920 t (from INTER\(see the introduction to this chapter\), and the)8 2315 1 1296 2040 t 10 I f (i)3639 2040 w 7 I f (th)3678 2000 w 10 R f (column of the L matrix appears)5 1271 1 3769 2040 t (permuted in the)2 639 1 1296 2160 t 10 I f (i)1966 2160 w 7 I f (th)2005 2120 w 10 R f (column of the AL array. Since the diagonal elements of L are all 1, they)14 2942 1 2098 2160 t (are not stored.)2 568 1 1296 2280 t 9 B f (Note 2:)1 278 1 720 2640 t 10 R f (MU)1296 2640 w 10 S f (\243)1457 2640 w 10 R f (M)1512 2640 w 9 B f (Error situations:)1 653 1 720 3000 t 10 R f ( see)1 183( \320)1 125( those errors marked with an asterisk)6 1505(*\(The user can elect to `recover' from)6 1546 4 1517 3000 t 10 I f (Er-)4907 3000 w (ror Handling)1 531 1 1512 3120 t 10 R f (, Framework Chapter\))2 884 1 2043 3120 t (Number Error)1 1506 1 1800 3360 t (1 N)1 1008 1 1944 3600 t 10 S f (<)2977 3600 w 10 R f (1)3057 3600 w (2 ML)1 1086 1 1944 3840 t 10 S f (<)3055 3840 w 10 R f (1)3135 3840 w (3 M)1 1025 1 1944 4080 t 10 S f (<)2994 4080 w 10 R f (ML)3074 4080 w (4 IG)1 1041 1 1944 4320 t 10 S f (<)3010 4320 w 10 R f (M)3090 4320 w (5 IAL)1 1102 1 1944 4560 t 10 S f (<)3071 4560 w 10 R f (ML)3151 4560 w 10 S f (-)3326 4560 w 10 R f (1)3406 4560 w ( matrix whose rank is at least k)7 1240( singular)1 952(10 + k*)2 306 3 1944 4800 t 9 B f (Double-precision version:)1 988 1 720 5160 t 10 R f (DBADC with G, AL and EPS declared double precision.)8 2275 1 1783 5160 t 9 B f (Complex version:)1 678 1 720 5520 t 10 R f (CBADC with G and AL declared complex)6 1703 1 1498 5520 t 9 B f (Storage:)720 5880 w 10 R f (None)1296 5880 w 9 B f (Time:)720 6240 w 10 R f (M)1296 6240 w 10 S f (\264)1385 6240 w 10 R f (N+\(ML)1440 6240 w 10 S f (-)1751 6240 w 10 R f (1\))1806 6240 w 10 S f (\264)1889 6240 w 10 R f (N)1944 6240 w 10 S f (\264)2016 6240 w 10 R f (\(M)2071 6240 w 10 S f (-)2193 6240 w 10 R f (ML\))2248 6240 w 10 S f (\243)2456 6240 w 10 R f (additions)2536 6240 w 10 S f (\243)2928 6240 w 10 R f (\(ML)3008 6240 w 10 S f (-)3191 6240 w 10 R f (1\))3246 6240 w 10 S f (\264)3329 6240 w 10 R f (N)3384 6240 w 10 S f (\264)3456 6240 w 10 R f (\(M)3511 6240 w 10 S f (-)3633 6240 w 10 R f (1\)+N)3688 6240 w 10 S f (\264)3899 6240 w 10 R f (M)3954 6240 w (\(ML)1296 6360 w 10 S f (-)1479 6360 w 10 R f (1\))1534 6360 w 10 S f (\264)1617 6360 w 10 R f (N)1672 6360 w 10 S f (\264)1744 6360 w 10 R f (\(M)1799 6360 w 10 S f (-)1921 6360 w 10 R f (ML\))1976 6360 w 10 S f (\243)2184 6360 w 10 R f (multiplications)2264 6360 w 10 S f (\243)2890 6360 w 10 R f (\(ML)2970 6360 w 10 S f (-)3153 6360 w 10 R f (1\))3208 6360 w 10 S f (\264)3291 6360 w 10 R f (N)3346 6360 w 10 S f (\264)3418 6360 w 10 R f (\(M)3473 6360 w 10 S f (-)3595 6360 w 10 R f (1\))3650 6360 w (N)1296 6480 w 10 S f (\264)1368 6480 w 10 R f (\(ML)1423 6480 w 10 S f (-)1606 6480 w 10 R f (1\) divisions)1 470 1 1661 6480 t (Linear Algebra)1 606 1 4794 7500 t (\320 13 \320)2 350 1 2705 7620 t (BADC)5122 7740 w cleartomark showpage saveobj restore %%EndPage: 13 13 %%Page: 14 14 /saveobj save def mark 14 pagesetup 10 R f (-- --)1 5544 1 0 120 t (Linear Algebra)1 606 1 360 600 t 8 R f (PORT)4903 600 w 10 R f (library)5134 600 w ( 11, 1993)2 375(BADC February)1 4665 2 360 840 t 9 B f (Method:)720 1320 w 10 R f (Gaussian elimination with partial pivoting)4 1689 1 1296 1320 t (BADC calls BALU after setting EPS =)6 1609 1 1296 1440 t 10 S f (\357 \357)1 106 1 2938 1440 t 10 R f (A)3052 1440 w 10 S f ( e)1 85(\357 \357)1 106 2 3132 1440 t 10 R f (where)3356 1440 w 10 S f (e)3632 1440 w 10 R f ( machine precision, i.e. the)4 1109(is the)1 222 2 3709 1440 t (value returned by R1MACH\(4\) \(or, for double precision, by D1MACH\(4\)\).)9 3022 1 1296 1560 t 9 B f (See also:)1 333 1 720 1920 t 10 R f (BALU, BAFS, BABS, BACE, BALE, BASS)5 1814 1 1296 1920 t 9 B f (Author:)720 2280 w 10 R f (Linda Kaufman)1 629 1 1296 2280 t 9 B f (Example:)720 2640 w 10 R f ( for solving)2 481(In this example we implement a linearized version of Newton's method)10 2952 2 1296 2640 t 10 I f (f)4764 2640 w 10 R f (\()4808 2640 w 10 I f (x)4849 2640 w 10 R f (\)=0)4901 2640 w ( method is normally given as)5 1158( Newton's)1 438(where f and x are vectors of length N.)8 1509 3 1296 2760 t (Set k to 0. Initialize)4 786 1 1512 3000 t 10 I f (x)2323 3000 w 7 R f (\( 0 \))2 91 1 2378 2960 t 10 R f (Until)1512 3120 w 10 S f (\357 \357)1 106 1 1743 3120 t 10 I f (f)1865 3120 w 10 R f (\()1909 3120 w 10 I f (x)1950 3120 w 7 R f (\()2005 3080 w 7 I f (k)2033 3080 w 7 R f (\))2069 3080 w 10 R f (\))2108 3120 w 10 S f (\357 \357 \243 e)3 221 1 2157 3120 t 10 R f (iterate as follows:)2 710 1 2403 3120 t (Solve)1512 3360 w 10 I f (J)1765 3360 w 10 R f (\()1817 3360 w 10 I f (x)1858 3360 w 7 R f (\()1913 3320 w 7 I f (k)1941 3320 w 7 R f (\))1977 3320 w 10 R f (\))2016 3360 w 10 I f (y)2065 3360 w 10 S f (=)2158 3360 w 10 I f (f)2270 3360 w 10 R f (\()2314 3360 w 10 I f (x)2355 3360 w 7 R f (\()2410 3320 w 7 I f (k)2438 3320 w 7 R f (\))2474 3320 w 10 R f (\))2513 3360 w (where)1656 3540 w 10 I f (J)1924 3540 w 7 I f (i)1979 3560 w 7 R f (,)2004 3560 w 7 I f (l)2027 3560 w 10 S f (=)2104 3540 w (\266)2233 3610 w 10 I f (x)2290 3610 w 7 I f (l)2345 3630 w 10 S f (\266)2237 3460 w 10 I f (f)2302 3460 w 7 I f (i)2341 3480 w 10 S1 f (_ ___)1 170 1 2218 3510 t 10 I f (.)2406 3540 w 10 R f (Set)2456 3540 w 10 I f (x)2609 3540 w 7 R f (\()2664 3500 w 7 I f (k)2692 3500 w 7 S f (+)2739 3500 w 7 R f (1 \))1 63 1 2789 3500 t 10 S f (=)2917 3540 w 10 I f (x)3021 3540 w 7 R f (\()3076 3500 w 7 I f (k)3104 3500 w 7 R f (\))3140 3500 w 10 S f (-)3187 3540 w 10 I f (y)3258 3540 w 10 R f (Set k to k + 1)5 537 1 1656 3730 t ( problems, especially those occurring in algorithms for solving time-varying partial)10 3417(In some)1 327 2 1296 3970 t ( linearized)1 426(differential equations, J is banded and costly to evaluate. Thus to solve f\(x\)=0, a)13 3318 2 1296 4090 t (Newton's method is used in which)5 1650 1 1296 4210 t 10 I f (x)3024 4210 w 7 R f (\()3079 4170 w 7 I f (k)3107 4170 w 7 S f (+)3154 4170 w 7 R f (1 \))1 63 1 3204 4170 t 10 R f (is updated according to the formula)5 1687 1 3353 4210 t 10 I f (x)1296 4330 w 7 R f (\()1351 4290 w 7 I f (k)1379 4290 w 7 S f (+)1426 4290 w 7 R f (1 \))1 63 1 1476 4290 t 10 S f (=)1604 4330 w 10 I f (x)1708 4330 w 7 R f (\()1763 4290 w 7 I f (k)1791 4290 w 7 R f (\))1827 4290 w 10 S f (-)1874 4330 w 10 I f (J)1945 4330 w 10 R f (\()1997 4330 w 10 I f (x)2038 4330 w 7 R f (\( 0 \))2 91 1 2093 4290 t 10 R f (\))2200 4330 w 7 S f (-)2244 4290 w 7 R f (1)2294 4290 w 10 I f (f)2353 4330 w 10 R f (\()2397 4330 w 10 I f (x)2438 4330 w 7 R f (\()2493 4290 w 7 I f (k)2521 4290 w 7 R f (\))2557 4290 w 10 R f ( a linearized)2 529( the following subroutine, implementing)4 1702(\). In)1 213 3 2596 4330 t ( which evaluate the)3 776(Newton method, FUN and JAC are assumed to be user provided functions)11 2968 2 1296 4450 t ( function SNRM2 carefully computes the 2-norm of a vector.)9 2446( The)1 205(function and its Jacobian.)3 1021 3 1296 4570 t 8 CW f (SUBROUTINE NEWTON\(N,M,ML,X,EPS,FUN,JAC,LIMIT,F\))1 2256 1 1992 4910 t (C)1656 5010 w (C THIS SUBROUTINE IMPLEMENTS A LINEARIZED FORM OF NEWTONS)8 2736 1 1656 5110 t (C METHOD TO FIND THE ZERO OF A FUNCTION F DEFINED BY)11 2496 1 1656 5210 t (C FUN, WHOSE BAND JACOBIAN \(WITH BANDWIDTH M AND ML)9 2448 1 1656 5310 t (C LOWER DIAGONALS\) IS EVALUATED IN JAC. LIMIT GIVES)8 2448 1 1656 5410 t (C A BOUND ON THE NUMBER OF ITERATIONS AND IN F THE)11 2400 1 1656 5510 t (C FINAL FUNCTION VALUE IS RETURNED.)5 1680 1 1656 5610 t (C)1656 5710 w (INTEGER N, ML, M, LIMIT)4 1104 1 1992 5810 t (INTEGER JG, JAL, JINTER, ISTKGT, MU, LIM, I)7 2064 1 1992 5910 t (INTEGER IST\(1000\))1 816 1 1992 6010 t (REAL EPS, X\(N\), F\(N\))3 960 1 1992 6110 t (REAL FU, SNRM2, R\(1000\))3 1104 1 1992 6210 t (DOUBLE PRECISION D\(500\))2 1104 1 1992 6310 t (EXTERNAL FUN,JAC)1 768 1 1992 6410 t (COMMON /CSTAK/ D)2 768 1 1992 6510 t (EQUIVALENCE \(D\(1\),R\(1\)\),\(D\(1\),IST\(1\)\))1 1776 1 1992 6610 t (C)1656 6710 w (C GET SPACE FOR G,INTER, AND AL FROM)7 1728 1 1656 6810 t (C THE STORAGE STACK)3 912 1 1656 6910 t 10 R f (Linear Algebra)1 606 1 360 7570 t (\320 14 \320)2 350 1 2705 7690 t (BADC)360 7810 w cleartomark showpage saveobj restore %%EndPage: 14 14 %%Page: 15 15 /saveobj save def mark 15 pagesetup 10 R f (-- --)1 5544 1 0 120 t 8 R f (PORT)360 600 w 10 R f ( Algebra)1 346(library Linear)1 4463 2 591 600 t ( BADC)1 4305(February 11, 1993)2 735 2 360 840 t 8 CW f (C)1656 1300 w (JG= ISTKGT\(M*N,3\))1 816 1 1992 1400 t (JAL = ISTKGT \(\(ML-1\)*N,3\))3 1200 1 1992 1500 t (JINTER = ISTKGT\(N,2\))2 960 1 1992 1600 t (CALL JAC\(N,M,ML,X,R\(JG\),M\))1 1248 1 1992 1700 t (CALL BADC\(N,ML,M,R\(JH\),M,R\(JAL\),ML-1,IST\(JINTER\),MU\))1 2496 1 1992 1800 t (LIM=0)1992 1900 w ( FUN\(N,X,F\))1 528(10 CALL)1 432 2 1752 2000 t (FU=SNRM2\(N,F,1\))1992 2100 w (C)1656 2200 w (C CHECK FOR CONVERGENCE OR IF ITERATION LIMIT IS REACHED)9 2688 1 1656 2300 t (C)1656 2400 w (IF \(FU.LE.EPS.OR.LIM.GT.LIMIT\) RETURN)2 1776 1 1944 2500 t (LIM=LIM+1)1944 2600 w (C SOLVE THE LINEAR SYSTEM)4 1200 1 1656 2700 t (CALL BAFS\(N,ML,R\(JAL\),ML-1,IST\(JINTER\),F,N,1\))1 2160 1 1944 2800 t (CALL BABS\(N,R\(JG\),M,F,N,1,MU\))1 1392 1 1944 2900 t (C CORRECT THE CURRENT ESTIMATE OF THE SOLUTION)7 2208 1 1656 3000 t (DO 20 I=1,N)2 528 1 1944 3100 t (X\(I\)=X\(I\)-F\(I\))2088 3200 w (20 CONTINUE)1 576 1 1752 3300 t (GO TO 10)2 384 1 1944 3400 t (END)1944 3500 w 10 R f (Linear Algebra)1 606 1 4794 7500 t (\320 15 \320)2 350 1 2705 7620 t (BADC)5122 7740 w cleartomark showpage saveobj restore %%EndPage: 15 15 %%Page: 16 16 /saveobj save def mark 16 pagesetup 10 R f (-- --)1 5544 1 0 120 t (Linear Algebra)1 606 1 360 600 t 8 R f (PORT)4903 600 w 10 R f (library)5134 600 w ( 11, 1993)2 375(BADC February)1 4665 2 360 840 t 8 CW f (BALE \320 banded linear system solver)5 1632 1 2532 1300 t 7 B f (Purpose:)720 1600 w 8 CW f (BALE \(BAnded Linear Equation solution\) solves AX = B where A is a general banded)14 3840 1 1296 1600 t (matrix.)1296 1700 w 7 B f (Usage:)720 2000 w 8 CW f (CALL BALE \(N, ML, M, G, IG, B, IB, NB\))9 1824 1 1296 2000 t (N)1440 2200 w 12 S f (\256)1980 2216 w 8 CW f (the number of equations)3 1104 1 2196 2200 t (ML)1440 2400 w 12 S f (\256)1980 2416 w 8 CW f (the number of nonzero bands on and below the diagonal of A)11 2784 1 2196 2400 t (M)1440 2600 w 12 S f (\256)1980 2616 w 8 CW f (the number of nonzero bands of A)6 1536 1 2196 2600 t (G)1440 2800 w 12 S f (\256)1980 2816 w 8 CW f (a matrix into which the matrix A has been packed as follows:)11 2880 1 2196 2800 t (G\(ML + j)2 384 1 2916 2950 t 8 S f (-)3300 2950 w 8 CW f (i, i\) =)2 336 1 3344 2950 t 8 I f (a)3728 2950 w 5 I f (i j)1 32 1 3776 2966 t 8 CW f (i.e. the leftmost band of A is in the first row of G)12 2496 1 2196 3100 t (\(See the introduction to this chapter.\))5 1872 1 2196 3200 t (G should be dimensional \(IG,KG\) in the calling program, where IG)10 3072 1 2196 3300 t 8 S f (\263)5268 3300 w 8 CW f (M)5312 3300 w (and KG)1 288 1 2196 3400 t 8 S f (\263)2484 3400 w 8 CW f (N.)2528 3400 w (G is overwritten during the solution.)5 1776 1 2196 3500 t (IG)1440 3700 w 12 S f (\256)1980 3716 w 8 CW f (the row \(leading\) dimension of G, as dimensioned in the calling program)11 3408 1 2196 3700 t (B)1440 3900 w 12 S f (\256)1980 3916 w 8 CW f (the matrix of right-hand sides, dimensioned \(IB,KB\) in the calling)9 3168 1 2196 3900 t (program,)2196 4000 w (where IB)1 384 1 2196 4100 t 8 S f (\263)2580 4100 w 8 CW f (N and KB)2 384 1 2624 4100 t 8 S f (\263)3008 4100 w 8 CW f (NB.)3052 4100 w 12 S f (\254)1980 4316 w 8 CW f (the solution X)2 672 1 2196 4300 t (IB)1440 4500 w 12 S f (\256)1980 4516 w 8 CW f (the row \(leading\) dimension of B, as dimensioned in the calling program)11 3408 1 2196 4500 t (NB)1440 4700 w 12 S f (\256)1980 4716 w 8 CW f (the number of right-hand sides)4 1440 1 2196 4700 t 7 B f (Note 1:)1 215 1 720 5000 t 8 CW f (Unless the given matrix, A, is known in advance to be well-conditioned,)11 3408 1 1296 5000 t (the user should use the routine BASS in place of BALE.)10 2592 1 1296 5100 t 7 B f (Note 2:)1 215 1 720 5400 t 8 CW f (Users who wish to solve a sequence of problems)8 2208 1 1296 5400 t (with the same coefficient matrix, but different)6 2256 1 1296 5500 t (right-hand sides)1 768 1 1296 5600 t 8 I f (not all known in advance,)4 822 1 1296 5700 t 8 CW f (should not use BALE, but should call subprograms BADC, BAFS and BABS.)11 3312 1 1296 5800 t (\(See the example in BADC.\))4 1248 1 1296 5900 t (BADC is called once to get the LU decomposition \(see the)10 2688 1 1296 6000 t (introduction to this chapter\) and then the pair,)7 2304 1 1296 6100 t (BAFS \(forward solve\) and BABS \(back solve\), is called)8 2544 1 1296 6200 t (for each new right-hand side.)4 1392 1 1296 6300 t 7 B f (Error situations:)1 504 1 720 6600 t 8 CW f (*\(The user can elect to `recover' from)6 1824 1 1512 6600 t (those errors marked with an asterisk \320)6 1824 1 1512 6700 t (see)1512 6800 w 8 I f (Error Handling)1 504 1 1704 6800 t 8 CW f (, Framework Chapter\))2 960 1 2208 6800 t 10 R f (Linear Algebra)1 606 1 360 7500 t (\320 16 \320)2 350 1 2705 7620 t (BALE)360 7740 w cleartomark showpage saveobj restore %%EndPage: 16 16 %%Page: 17 17 /saveobj save def mark 17 pagesetup 10 R f (-- --)1 5544 1 0 120 t 8 R f (PORT)360 600 w 10 R f ( Algebra)1 346(library Linear)1 4463 2 591 600 t ( BALE)1 4305(February 11, 1993)2 735 2 360 840 t 8 CW f (Number Error)1 1536 1 1800 1300 t ( < 1)2 192(1 N)1 984 2 1944 1500 t ( < 1)2 192(2 ML)1 1032 2 1944 1700 t ( < ML)2 240(3 M)1 984 2 1944 1900 t ( < M)2 192(4 IG)1 1032 2 1944 2100 t ( < N)2 192(5 IB)1 1032 2 1944 2300 t ( < 1)2 192(6 NB)1 1032 2 1944 2500 t ( matrix whose rank is at least k)7 1536( singular)1 984(10 + k*)2 336 3 1944 2700 t 7 B f (Double-precision version:)1 769 1 720 3000 t 8 CW f (DBALE with G and B declared double precision.)7 2160 1 1633 3000 t 7 B f (Complex version:)1 527 1 720 3300 t 8 CW f (CBALE with G and B declared complex)6 1680 1 1440 3300 t 7 B f (Storage:)720 3600 w 8 CW f (N integer locations of scratch storage in the dynamic storage)9 2928 1 1296 3600 t (stack)1296 3700 w 7 B f (Time:)720 4000 w 8 CW f (at most N)2 432 1 1296 4000 t 8 S f (\264)1728 4000 w 8 CW f (\(M)1772 4000 w 8 S f (\264)1868 4000 w 8 CW f (\(ML+1\)+\(ML+M)1912 4000 w 8 S f (-)2488 4000 w 8 CW f (2\))2532 4000 w 8 S f (\264)2628 4000 w 8 CW f (\(NB)2672 4000 w 8 S f (-)2816 4000 w 8 CW f (1\)\) additions)1 624 1 2860 4000 t (at most N)2 432 1 1296 4100 t 8 S f (\264)1728 4100 w 8 CW f (\(ML)1772 4100 w 8 S f (\264)1916 4100 w 8 CW f (M+\(ML+M)1960 4100 w 8 S f (-)2296 4100 w 8 CW f (2\))2340 4100 w 8 S f (\264)2436 4100 w 8 CW f (\(NB)2480 4100 w 8 S f (-)2624 4100 w 8 CW f (1\)\) multiplications)1 912 1 2668 4100 t (N)1296 4200 w 8 S f (\264)1344 4200 w 8 CW f (\(NB+ML)1388 4200 w 8 S f (-)1676 4200 w 8 CW f (1\) divisions)1 576 1 1720 4200 t 7 B f (Method:)720 4500 w 8 CW f (Gaussian elimination with partial pivoting.)4 2064 1 1296 4500 t (Transformations to A are not saved.)5 1680 1 1296 4600 t 7 B f (See also:)1 259 1 720 4900 t 8 CW f (BABS, BACE, BADC, BAFS, BASS, BALU)5 1632 1 1296 4900 t 7 B f (Author:)720 5200 w 8 CW f (Linda Kaufman)1 624 1 1296 5200 t 7 B f (Example:)720 5500 w 8 CW f (In this example the relative efficiencies of BALE and BASS)9 2784 1 1296 5500 t (are compared for systems of various bandwidths and dimensions)8 2928 1 1296 5600 t (and various numbers of right-hand sides. The subroutine)7 2640 1 1296 5700 t (BASS solves a linear system with a banded matrix and also)10 2736 1 1296 5800 t (returns an estimate of the condition number of the matrix.)9 2784 1 1296 5900 t (The matrix used in this example is given by the formula)10 2640 1 1296 6000 t 8 I f (a)1296 6100 w 5 I f (i)1344 6116 w 5 R f (,)1362 6116 w 5 I f (j)1383 6116 w 8 S f (= \357)1 150 1 1470 6100 t 8 I f (i)1626 6100 w 8 S f (-)1667 6100 w 8 I f (j)1724 6100 w 8 S f (\357)1771 6100 w 8 CW f (Since each diagonal of the matrix)5 1584 1 1296 6200 t 8 I f (A)2928 6200 w 8 CW f (corresponds to a particular)3 1296 1 3025 6200 t (row of the array)3 768 1 1296 6300 t 8 I f (G)2112 6300 w 8 CW f (, and since all the elements on any diagonal)8 2112 1 2170 6300 t (of the matrix in our example)5 1344 1 1296 6400 t (are the same, each row of)5 1200 1 1296 6500 t 8 I f (G)2544 6500 w 8 CW f (in the program below was set to a constant.)8 2064 1 1296 6600 t (The right-hand sides were chosen randomly.)5 2016 1 1296 6700 t (The function ILAPSZ is a timer on the Honeywell 6000 machine)10 2880 1 1296 6900 t 10 R f (Linear Algebra)1 606 1 4794 7560 t (\320 17 \320)2 350 1 2705 7680 t (BALE)5139 7800 w cleartomark showpage saveobj restore %%EndPage: 17 17 %%Page: 18 18 /saveobj save def mark 18 pagesetup 10 R f (-- --)1 5544 1 0 120 t (Linear Algebra)1 606 1 360 600 t 8 R f (PORT)4903 600 w 10 R f (library)5134 600 w ( 11, 1993)2 375(BALE February)1 4665 2 360 840 t 8 CW f (with about a 1% accuracy.)4 1200 1 1296 1300 t (It counts in 1/64 milliseconds.)4 1488 1 1296 1400 t 6 CW f (INTEGER IG, IWRITE, I1MACH, N, ML, II, MP1, I, K)9 1728 1 1980 1660 t (INTEGER IB, NB, IT, ILAPSZ)4 936 1 1980 1740 t (REAL G\(19, 100\), B\(100, 10\), BB\(100, 10\), GG\(19, 100\))8 1908 1 1980 1820 t (REAL COND, TIME1, TIME2, UNI)4 1008 1 1980 1900 t (C)1656 1980 w (C THIS PROGRAM SOLVES BANDED SYSTEMS USING BALE AND)8 1836 1 1656 2060 t (C BASS AND COMPARES THE TIME FOR EACH OF THEM. THE)10 1800 1 1656 2140 t (C SYSTEMS HAVE VARIOUS BANDWIDTHS,DIMENSIONS, AND)5 1764 1 1656 2220 t (C NUMBERS OF RIGHT-HAND SIDES)4 1044 1 1656 2300 t (DOUBLE PRECISION D\(600\))2 828 1 1980 2380 t (COMMON /CSTAK/ D)2 576 1 1980 2460 t (C MAKE SURE THE STACK MECHANISM HAS SUFFICIENT SPACE)8 1872 1 1656 2540 t (C FOR BASS)2 360 1 1656 2620 t (CALL ISTKIN\(1200,3\))1 684 1 1980 2700 t (IG=19)1980 2780 w (IWRITE=I1MACH\(2\))1980 2860 w (IB=100)1980 2940 w (DO 70 N=50,100,50)2 612 1 1980 3020 t (DO 60 ML=2,10,8)2 540 1 2088 3100 t (M=2*ML - 1)2 360 1 2196 3180 t (MP1=M+1)2196 3260 w (DO 50 NB=1,10,9)2 540 1 2196 3340 t (WRITE\(IWRITE,1\)N,M,NB)2304 3420 w ( N IS,I4,6H M IS ,I3,7H NB IS ,I3\))8 1224(1 FORMAT\(/5H)1 936 2 1728 3500 t (C)1656 3580 w (C CONSTRUCT THE MATRIX A\(I,J\)=ABS\(I-J\) AND PACK IT INTO G)9 2052 1 1656 3660 t (C AND MAKE A COPY OF THE MATRIX SO THE SYSTEM CAN BE)12 1872 1 1656 3740 t (C SOLVED WITH BOTH BALE AND BASS)6 1152 1 1656 3820 t (C)1656 3900 w (K=ML - 1)2 288 1 2304 3980 t (DO 20 I=1,ML)2 432 1 2304 4060 t (II=MP1 - I)2 360 1 2412 4140 t (DO 10 J=1,N)2 396 1 2412 4220 t (G\(I,J\)=K)2520 4300 w (GG\(I,J\)=K)2520 4380 w (G\(II,J\)=K)2520 4460 w (GG\(II,J\)=K)2520 4540 w (10 CONTINUE)1 972 1 1728 4620 t (K=K - 1)2 252 1 2412 4700 t (20 CONTINUE)1 864 1 1728 4780 t (C)1656 4860 w (C CONSTRUCT RANDOM RIGHT-HAND SIDES)4 1260 1 1656 4940 t (C AND MAKE A COPY)4 612 1 1656 5020 t (C)1656 5100 w (DO 40 I=1,NB)2 432 1 2304 5180 t (DO 30 II=1,N)2 432 1 2412 5260 t (B\(II,I\)=UNI\(0\))2520 5340 w (BB\(II,I\)=B\(II,I\))2520 5420 w (30 CONTINUE)1 972 1 1728 5500 t (40 CONTINUE)1 864 1 1728 5580 t (C)1656 5660 w (C SOLVE THE SYSTEM USING BOTH BASS AND BALE)8 1548 1 1656 5740 t (C)1656 5820 w (IT=ILAPSZ\(0\))2304 5900 w (CALL BASS\(N,ML,M,G,IG,B,IB,NB,COND\))1 1260 1 2304 5980 t (TIME1=\(ILAPSZ\(0\)-IT\)/64.0)2304 6060 w (WRITE\(IWRITE,41\)TIME1)2304 6140 w ( TIME FOR BASS IN MILLISECONDS IS ,F10.1\))7 1476(41 FORMAT\(34H)1 936 2 1728 6220 t (IT=ILAPSZ\(0\))2304 6300 w (CALL BALE\(N,ML,M,GG,IG,BB,IB,NB\))1 1152 1 2304 6380 t (TIME2=\(ILAPSZ\(0\)-IT\)/64.0)2304 6460 w (WRITE\(IWRITE,42\)TIME2)2304 6540 w ( TIME FOR BALE IN MIILISECONDS IS ,F10.1\))7 1476(42 FORMAT\(34H)1 936 2 1728 6620 t (50 CONTINUE)1 756 1 1728 6700 t (60 CONTINUE)1 648 1 1728 6780 t (70 CONTINUE)1 540 1 1728 6860 t 10 R f (Linear Algebra)1 606 1 360 7520 t (\320 18 \320)2 350 1 2705 7640 t (BALE)360 7760 w cleartomark showpage saveobj restore %%EndPage: 18 18 %%Page: 19 19 /saveobj save def mark 19 pagesetup 10 R f (-- --)1 5544 1 0 120 t 8 R f (PORT)360 600 w 10 R f ( Algebra)1 346(library Linear)1 4463 2 591 600 t ( BALE)1 4305(February 11, 1993)2 735 2 360 840 t 6 CW f (STOP)1980 1280 w (END)1980 1360 w 8 CW f (When the above program was run on the Honeywell 6000 machine at Bell Labs with)14 3744 1 1296 1660 t (an optimizing compiler, the following was printed:)6 2400 1 1296 1760 t 10 R f (Linear Algebra)1 606 1 4794 7500 t (\320 19 \320)2 350 1 2705 7620 t (BALE)5139 7740 w cleartomark showpage saveobj restore %%EndPage: 19 19 %%Page: 20 20 /saveobj save def mark 20 pagesetup 10 R f (-- --)1 5544 1 0 120 t (Linear Algebra)1 606 1 360 600 t 8 R f (PORT)4903 600 w 10 R f (library)5134 600 w ( 11, 1993)2 375(BALE February)1 4665 2 360 840 t 6 CW f ( 1)1 144( NB IS)2 216( 3)1 144( M IS)2 180( 50)1 144(N IS)1 144 6 1692 1280 t ( 50.0)1 396(TIME FOR BASS IN MILLISECONDS IS)5 1152 2 1692 1360 t ( 20.0)1 396(TIME FOR BALE IN MIILISECONDS IS)5 1152 2 1692 1440 t ( 10)1 144( NB IS)2 216( 3)1 144( M IS)2 180( 50)1 144(N IS)1 144 6 1692 1600 t ( 99.0)1 396(TIME FOR BASS IN MILLISECONDS IS)5 1152 2 1692 1680 t ( 58.2)1 396(TIME FOR BALE IN MIILISECONDS IS)5 1152 2 1692 1760 t ( 1)1 144( NB IS)2 216( 19)1 144( M IS)2 180( 50)1 144(N IS)1 144 6 1692 1920 t ( 200.8)1 396(TIME FOR BASS IN MILLISECONDS IS)5 1152 2 1692 2000 t ( 147.8)1 396(TIME FOR BALE IN MIILISECONDS IS)5 1152 2 1692 2080 t ( 10)1 144( NB IS)2 216( 19)1 144( M IS)2 180( 50)1 144(N IS)1 144 6 1692 2240 t ( 397.5)1 396(TIME FOR BASS IN MILLISECONDS IS)5 1152 2 1692 2320 t ( 315.8)1 396(TIME FOR BALE IN MIILISECONDS IS)5 1152 2 1692 2400 t ( 1)1 144( NB IS)2 216( 3)1 144(N IS 100 M IS)4 468 4 1692 2560 t ( 102.8)1 396(TIME FOR BASS IN MILLISECONDS IS)5 1152 2 1692 2640 t ( 36.4)1 396(TIME FOR BALE IN MIILISECONDS IS)5 1152 2 1692 2720 t ( 10)1 144( NB IS)2 216( 3)1 144(N IS 100 M IS)4 468 4 1692 2880 t ( 204.0)1 396(TIME FOR BASS IN MILLISECONDS IS)5 1152 2 1692 2960 t ( 112.9)1 396(TIME FOR BALE IN MIILISECONDS IS)5 1152 2 1692 3040 t ( 1)1 144( NB IS)2 216( 19)1 144(N IS 100 M IS)4 468 4 1692 3200 t ( 416.6)1 396(TIME FOR BASS IN MILLISECONDS IS)5 1152 2 1692 3280 t ( 302.4)1 396(TIME FOR BALE IN MIILISECONDS IS)5 1152 2 1692 3360 t ( 10)1 144( NB IS)2 216( 19)1 144(N IS 100 M IS)4 468 4 1692 3520 t ( 859.0)1 396(TIME FOR BASS IN MILLISECONDS IS)5 1152 2 1692 3600 t ( 680.3)1 396(TIME FOR BALE IN MIILISECONDS IS)5 1152 2 1692 3680 t 8 CW f ( computing the condition es-)4 1364(The above example indicates that the overhead for)7 2380 2 1296 3960 t (timate in BASS can be quite substantial for narrow banded systems with one)12 3744 1 1296 4060 t (right-hand side, but inconsequential if the bandwidth is large or if the sys-)12 3744 1 1296 4160 t ( example also indicates that the execution)6 2040( The)1 244(tem has many right-hand sides.)4 1460 3 1296 4260 t ( the number of equations, but certainly not linear in the)10 2886(time is linear in)3 858 2 1296 4360 t ( with many right-hand sides, which are known)7 2112( Users)1 336(number of right-hand sides.)3 1296 3 1296 4460 t (in advance and which all correspond to the same coefficient matrix, should ob-)12 3744 1 1296 4560 t ( call BALE once with)4 972(viously not invoke BALE for each new right-hand side, but)9 2772 2 1296 4660 t (NB set appropriately.)2 1008 1 1296 4760 t 10 R f (Linear Algebra)1 606 1 360 7500 t (\320 20 \320)2 350 1 2705 7620 t (BALE)360 7740 w cleartomark showpage saveobj restore %%EndPage: 20 20 %%Page: 21 21 /saveobj save def mark 21 pagesetup 10 R f (-- --)1 5544 1 0 120 t 8 R f (PORT)360 600 w 10 R f ( Algebra)1 346(library Linear)1 4463 2 591 600 t ( BALE)1 4305(February 11, 1993)2 735 2 360 840 t 8 CW f ( decomposition of a banded unsymmetric matrix)6 2160( LU)1 192(BALU \320)1 288 3 1848 1300 t 7 B f (Purpose:)720 1600 w 8 CW f ( decomposition\) finds the LU decompostion of a general)8 2664(BALU \(BAnded matrix LU)3 1080 2 1296 1600 t (banded matrix A using partial pivoting. It allows the user to specify a)12 3744 1 1296 1700 t ( is called by the LU decom-)6 1320( BALU)1 292(threshold for considering a matrix singular.)5 2132 3 1296 1800 t (position routines BACE and BADC.)4 1536 1 1296 1900 t 7 B f (Usage:)720 2200 w 8 CW f (CALL BALU \(N, ML, M, G, IG, AL, IAL, INTER, MU, EPS\))11 2496 1 1296 2200 t (N)1440 2400 w 12 S f (\256)1980 2416 w 8 CW f (the order of the matrix A)5 1200 1 2196 2400 t (ML)1440 2600 w 12 S f (\256)1980 2616 w 8 CW f (the number of nonzero bands on and below the diagonal of A)11 2784 1 2196 2600 t (M)1440 2800 w 12 S f (\256)1980 2816 w 8 CW f (the number of nonzero bands in A)6 1536 1 2196 2800 t (G)1440 3000 w 12 S f (\256)1980 3016 w 8 CW f ( as fol-)2 414(a matrix into which the matrix A has been packed)9 2430 2 2196 3000 t (lows:)2196 3100 w (G \(ML + j)3 432 1 2916 3250 t 8 S f (-)3348 3250 w 8 CW f (i, i\) =)2 336 1 3392 3250 t 8 I f (a)3776 3250 w 5 I f (i j)1 32 1 3824 3266 t 8 CW f (i.e. the leftmost diagonal of A is in the first row of G)12 2688 1 2196 3400 t (\(See the introduction to this chapter.\))5 1872 1 2196 3500 t ( the calling program,)3 1062(G should be dimensioned \(IG, KG\) in)6 1782 2 2196 3600 t (where IG)1 384 1 2196 3700 t 8 S f (\263)2580 3700 w 8 CW f (M and KG)2 384 1 2624 3700 t 8 S f (\263)3008 3700 w 8 CW f (N.)3052 3700 w 12 S f (\254)1980 3916 w 8 CW f (the upper triangular factor of A \(see)6 1776 1 2196 3900 t 6 B f (Note 2)1 164 1 4020 3900 t 8 CW f (\))4184 3900 w (IG)1440 4100 w 12 S f (\256)1980 4116 w 8 CW f ( of G, as dimensioned in the)6 1482(the row \(leading\) dimension)3 1362 2 2196 4100 t (calling program)1 720 1 2196 4200 t (AL)1440 4400 w 12 S f (\254)1980 4416 w 8 CW f (the lower triangular factor of A \(see)6 1776 1 2196 4400 t 6 B f (Note 2)1 164 1 4020 4400 t 8 CW f (\))4184 4400 w (IAL)1440 4600 w 12 S f (\256)1980 4616 w 8 CW f ( dimensioned in the)3 966(the row \(leading\) dimension of AL, as)6 1878 2 2196 4600 t (calling program)1 720 1 2196 4700 t (INTER)1440 4900 w 12 S f (\254)1980 4916 w 8 CW f (an integer vector of length N recording the row inter-)9 2844 1 2196 4900 t (changes performed during the decomposition \(see)5 2256 1 2196 5000 t 6 B f (Note 2)1 164 1 4500 5000 t 8 CW f (\))4664 5000 w (MU)1440 5200 w 12 S f (\254)1980 5216 w 8 CW f (the number of nonzero bands in the upper triangular factor)9 2784 1 2196 5200 t (EPS)1440 5400 w 12 S f (\256)1980 5416 w 8 CW f ( an index k such that)5 1043( and there exists)3 834( = LU)2 240(if A)1 198 4 2196 5400 t 8 S f (\357)4566 5400 w 8 I f (u)4605 5400 w 5 I f (kk)4653 5416 w 8 S f (\357 \243)1 138 1 4703 5400 t 8 CW f (EPS)4896 5400 w (then A is considered singular)4 1392 1 2196 5500 t 10 R f (Linear Algebra)1 606 1 4794 7500 t (\320 21 \320)2 350 1 2705 7620 t (BALU)5128 7740 w cleartomark showpage saveobj restore %%EndPage: 21 21 %%Page: 22 22 /saveobj save def mark 22 pagesetup 10 R f (-- --)1 5544 1 0 120 t (Linear Algebra)1 606 1 360 600 t 8 R f (PORT)4903 600 w 10 R f (library)5134 600 w ( 11, 1993)2 375(BALU February)1 4665 2 360 840 t 7 B f (Note 1:)1 215 1 720 1300 t 8 CW f ( not found to be singular\), the)6 1602(After execution of BALU, \(if the matrix is)7 2142 2 1296 1300 t ( INTER\(N\))1 452(value of the determinant is)4 1380 2 1296 1400 t 8 S f (\264)3196 1400 w 8 CW f (G\(1,1\))3308 1400 w 8 S f (\264)3664 1400 w 8 CW f (G\(1,2\))3776 1400 w 8 S f (\264)4132 1400 w 8 CW f (. . .)2 280 1 4244 1400 t 8 S f (\264)4592 1400 w 8 CW f (G\(1,N\).)4704 1400 w (INTER\(N\) contains the sign of the permutation.)6 2208 1 1296 1500 t 7 B f (Note 2:)1 215 1 720 1800 t 8 CW f ( are suitable for input into)5 1384(After execution of BALU, the arrays INTER and AL)8 2360 2 1296 1800 t ( solve subroutine BAFS and G is suitable for input into the back)12 3204(the forward)1 540 2 1296 1900 t ( LU decomposition of A satisfies the equation PA=LU)8 2448( The)1 240(solve subroutine BABS.)2 1056 3 1296 2000 t ( permutation matrix, L is a unit lower triangular matrix and U is)12 3156(where P is a)3 588 2 1296 2100 t ( return from BALU the element)5 1437( On)1 201( matrix.)1 393(an upper triangular)2 928 4 1296 2200 t 8 I f (u)4312 2200 w 5 I f (i j)1 32 1 4360 2216 t 8 CW f (is contained)1 585 1 4455 2200 t (in G\(j)1 296 1 1296 2300 t 8 S f (-)1592 2300 w 8 CW f ( that the main diagonal occupies the first row of the G ma-)12 2916(i+1,i\), so)1 488 2 1636 2300 t ( occupies the second row, etc. The matrix P can)9 2292(trix, the first super diagonal)4 1452 2 1296 2400 t ( chapter\), and the)3 867(be obtained from INTER \(see the introduction to this)8 2512 2 1296 2500 t 8 I f (i)4724 2500 w 5 I f (th)4754 2468 w 8 CW f (col-)4848 2500 w ( matrix appears permuted in the)5 1528(umn of the L)3 597 2 1296 2600 t 8 I f (i)3477 2600 w 5 I f (th)3507 2568 w 8 CW f (column of the AL array. Since)5 1432 1 3608 2600 t (the diagonal elements of L are all 1, they are not stored.)11 2784 1 1296 2700 t 7 B f (Error situations:)1 534 1 720 3000 t 8 CW f (*\(The user can elect to `recover' from those errors marked with an)11 3498 1 1542 3000 t ( see)1 240(asterisk \320)1 480 2 1512 3100 t 8 I f (Error Handling)1 504 1 2280 3100 t 8 CW f (, Framework Chapter\))2 960 1 2784 3100 t (Number Error)1 1536 1 1800 3300 t ( < 1)2 192(1 N)1 984 2 1944 3500 t ( < 1)2 192(2 ML)1 1032 2 1944 3700 t ( < ML)2 240(3 M)1 984 2 1944 3900 t ( < M)2 192(4 IG)1 1032 2 1944 4100 t ( < ML)2 240(5 IAL)1 1080 2 1944 4300 t 8 S f (-)3312 4300 w 8 CW f (1)3404 4300 w ( matrix whose rank is at least k)7 1536( singular)1 984(10 + k*)2 336 3 1944 4500 t 7 B f (Double-precision version:)1 769 1 720 4800 t 8 CW f (DBALU with G, AL and EPS declared double precision.)8 2448 1 1633 4800 t 7 B f (Complex version:)1 527 1 720 5100 t 8 CW f (CBALU with G and AL declared complex)6 1728 1 1488 5100 t 7 B f (Storage:)720 5400 w 8 CW f (None)1296 5400 w 7 B f (Time:)720 5700 w 8 CW f (N)1296 5700 w 8 S f (\264)1344 5700 w 8 CW f (\(ML)1388 5700 w 8 S f (-)1532 5700 w 8 CW f (1\) divisions)1 576 1 1576 5700 t (\(ML)1296 5800 w 8 S f (-)1440 5800 w 8 CW f (1\))1484 5800 w 8 S f (\264)1580 5800 w 8 CW f (N)1624 5800 w 8 S f (\264)1672 5800 w 8 CW f (\(M)1716 5800 w 8 S f (-)1812 5800 w 8 CW f (ML\))1856 5800 w 8 S f (\243)2000 5800 w 8 CW f (multiplications)2044 5800 w 8 S f (\243)2812 5800 w 8 CW f (\(ML)2856 5800 w 8 S f (-)3000 5800 w 8 CW f (1\))3044 5800 w 8 S f (\264)3140 5800 w 8 CW f (N)3184 5800 w 8 S f (\264)3232 5800 w 8 CW f (\(M)3276 5800 w 8 S f (-)3372 5800 w 8 CW f (1\))3416 5800 w (\(ML)1296 5900 w 8 S f (-)1440 5900 w 8 CW f (1\))1484 5900 w 8 S f (\264)1580 5900 w 8 CW f (N)1624 5900 w 8 S f (\264)1672 5900 w 8 CW f (\(M)1716 5900 w 8 S f (-)1812 5900 w 8 CW f (ML\))1856 5900 w 8 S f (\243)2000 5900 w 8 CW f (additions)2092 5900 w 8 S f (\243)2572 5900 w 8 CW f (\(ML)2616 5900 w 8 S f (-)2760 5900 w 8 CW f (1\))2804 5900 w 8 S f (\264)2900 5900 w 8 CW f (N)2944 5900 w 8 S f (\264)2992 5900 w 8 CW f (\(M)3036 5900 w 8 S f (-)3132 5900 w 8 CW f (1\))3176 5900 w 7 B f (Method:)720 6200 w 8 CW f (Gaussian elimination with partial pivoting)4 2016 1 1296 6200 t 7 B f (See also:)1 259 1 720 6500 t 8 CW f (BADC, BAFS, BABS, BACE, BALE, BASS)5 1632 1 1296 6500 t 10 R f (Linear Algebra)1 606 1 360 7500 t (\320 22 \320)2 350 1 2705 7620 t (BALU)360 7740 w cleartomark showpage saveobj restore %%EndPage: 22 22 %%Page: 23 23 /saveobj save def mark 23 pagesetup 10 R f (-- --)1 5544 1 0 120 t 8 R f (PORT)360 600 w 10 R f ( Algebra)1 346(library Linear)1 4463 2 591 600 t ( BALU)1 4305(February 11, 1993)2 735 2 360 840 t 7 B f (Author:)720 1300 w 8 CW f (Linda Kaufman)1 624 1 1296 1300 t 7 B f (Example:)720 1600 w 8 CW f ( the determinant of a band matrix stored in G in)10 2454(The program below computes)3 1290 2 1296 1600 t ( INT\(N\))1 354( the call to BALU the determinant is just)8 2120( After)1 355(packed form.)1 595 4 1296 1700 t 8 S f (\264)4786 1700 w 8 CW f (the)4896 1700 w ( G. Since the subroutine BADET re-)6 1656(product of the elements in the first row of)8 2088 2 1296 1800 t ( hold the original matrix,)4 1260(quires the user to provide only the space needed to)9 2484 2 1296 1900 t ( get the extra space needed by)6 1464(it uses the stack mechanism provided in PORT to)8 2280 2 1296 2000 t ( avoid underflow and overflow during the calcu-)7 2284( subroutine tries to)3 975(BALU. The)1 485 3 1296 2100 t ( subroutine UMKFL is used to decompose a floating-point number, F,)10 3168(lation. The)1 576 2 1296 2200 t (into a mantissa, S, and an exponent E such that)9 2337 1 1296 2300 t 8 R f (F)3690 2300 w 8 S f (=)3802 2300 w 8 R f (Sb)3913 2300 w 5 R f (E)4002 2268 w 8 CW f (where b is the base)4 944 1 4096 2300 t (of the machine and 1/b)4 1056 1 1296 2400 t 8 S f (\243 \357)1 131 1 2400 2400 t 8 CW f (S)2531 2400 w 8 S f (\357)2579 2400 w 8 CW f (< 1)1 144 1 2666 2400 t 6 CW f (SUBROUTINE BADET\(N,ML,M,A,IA,DETMAN,IDETEX\))1 1548 1 1908 2660 t (C)1656 2740 w (C THIS SUBROUTINE COMPUTES THE DETERMINANT OF A)7 1692 1 1656 2820 t (C BANDED MATRIX STORED IN PACKED FORM IN A)8 1512 1 1656 2900 t (C THE DETERMINANT IS COMPUTED AS DETMAN*BETA**IDETEX,)6 1908 1 1656 2980 t (C WHERE BETA IS THE BASE OF THE MACHINE AND)9 1548 1 1656 3060 t (C DETMAN IS BETWEEN 1/BETA AND 1 IN ABSOLUTE VALUE)9 1800 1 1656 3140 t (C)1656 3220 w (INTEGER ML, M, N, IA, IDETEX)5 1008 1 1908 3300 t (INTEGER E, ISPAC, IALOW, ISTKGT, ISIGN, INTER, I, MU)8 1872 1 1908 3380 t (INTEGER IN\(1000\))1 576 1 1908 3460 t (REAL A\(IA,1\), DETMAN, BETA, ONOVBE, S)5 1332 1 1908 3540 t (REAL R\(1000\))1 432 1 1908 3620 t (DOUBLE PRECISION D\(500\))2 828 1 1908 3700 t (COMMON /CSTAK/D)1 540 1 1908 3780 t (EQUIVALENCE\(D\(1\),R\(1\)\),\(D\(1\),IN\(1\)\))1908 3860 w (C)1656 3940 w (C ALLOCATE SPACE FROM THE STACK FOR THE PIVOT ARRAY)9 1836 1 1656 4020 t (C AND THE EXTRA SPACE TO HOLD THE LOWER TRIANGLE)9 1728 1 1656 4100 t (C)1656 4180 w (ISPAC=\(ML-1\)*N)1908 4260 w (IALOW=ISTKGT\(ISPAC,3\))1908 4340 w (INTER=ISTKGT\(N,2\))1908 4420 w (CALL BALU\(N,ML,M,A,IA,R\(IALOW\),ML-1,IN\(INTER\),MU,0.0\))1 1908 1 1908 4500 t (C)1656 4580 w (C THE DETERMINANT IS THE PRODUCT OF THE ELEMENTS OF)9 1836 1 1656 4660 t (C ROW 1 OF A TIMES THE LAST ELEMENT IN THE ARRAY INTER.)12 1980 1 1656 4740 t (C WE TRY TO COMPUTE THIS PRODUCT IN A WAY THAT WILL)11 1836 1 1656 4820 t (C AVOID UNDERFLOW AND OVERFLOW.)4 1116 1 1656 4900 t (C)1656 4980 w (BETA=FLOAT\(I1MACH\(10\)\))1908 5060 w (ONOVBE=1.0/BETA)1908 5140 w (ISIGN=INTER+N-1)1908 5220 w (DETMAN=IN\(ISIGN\)*ONOVBE)1908 5300 w (IDETEX=1)1908 5380 w (DO 10 I=1,N)2 396 1 1908 5460 t (CALL UMKFL\(A\(1,I\),E,S\))1 792 1 2016 5540 t (DETMAN=DETMAN*S)2016 5620 w (IDETEX=IDETEX+E)2016 5700 w (IF \(ABS\(DETMAN\).GE.ONOVBE\) GO TO 10)4 1260 1 2016 5780 t (IDETEX=IDETEX-1)2124 5860 w (DETMAN=DETMAN*BETA)2124 5940 w (10 CONTINUE)1 576 1 1656 6020 t (CALL ISTKRL\(2\))1 504 1 1944 6100 t (RETURN)1944 6180 w (END)1944 6260 w 10 R f (Linear Algebra)1 606 1 4794 7500 t (\320 23 \320)2 350 1 2705 7620 t (BALU)5128 7740 w cleartomark showpage saveobj restore %%EndPage: 23 23 %%Page: 24 24 /saveobj save def mark 24 pagesetup 10 R f (-- --)1 5544 1 0 120 t (Linear Algebra)1 606 1 360 600 t 8 R f (PORT)4903 600 w 10 R f (library)5134 600 w ( 11, 1993)2 375(BALU February)1 4665 2 360 840 t 8 CW f (BAML \320 banded matrix - vector multiplication)6 2112 1 2112 1300 t 7 B f (Purpose:)720 1600 w 8 CW f ( \(BAnded matrix MuLtiplication\) forms the product)6 2406(BAML matrix)1 536 2 1296 1600 t 8 I f (Ax)4295 1600 w 8 CW f (where)4436 1600 w 8 I f (A)4733 1600 w 8 CW f (is a)1 201 1 4839 1600 t (general banded matrix stored in packed form.)6 2112 1 1296 1700 t 7 B f (Usage:)720 2000 w 8 CW f (CALL BAML \(N, ML, M, G, IG, X, B\))8 1584 1 1296 2000 t (N)1440 2200 w 12 S f (\256)1980 2216 w 8 CW f (the order of the matrix A)5 1200 1 2196 2200 t (ML)1440 2400 w 12 S f (\256)1980 2416 w 8 CW f (the number of nonzero bands on and below the diagonal of A)11 2784 1 2196 2400 t (M)1440 2600 w 12 S f (\256)1980 2616 w 8 CW f (the number of nonzero bands of A)6 1536 1 2196 2600 t (G)1440 2800 w 12 S f (\256)1980 2816 w 8 CW f ( as fol-)2 414(a matrix into which the matrix A has been packed)9 2430 2 2196 2800 t (lows:)2196 2900 w (G\(ML + j)2 384 1 2916 3050 t 8 S f (-)3300 3050 w 8 CW f (i, i\) =)2 336 1 3344 3050 t 8 R f (a)3728 3050 w 5 R f (ij)3771 3066 w 8 CW f (i.e. the leftmost band of A is in the first row of G)12 2496 1 2196 3200 t (\(See the introduction to this chapter.\))5 1872 1 2196 3300 t ( in the calling program,)4 1256(G should be dimensioned \(IG,KG\))4 1588 2 2196 3400 t (where IG)1 384 1 2196 3500 t 8 S f (\263)2580 3500 w 8 CW f (M and KG)2 384 1 2624 3500 t 8 S f (\263)3008 3500 w 8 CW f (N.)3052 3500 w (IG)1440 3700 w 12 S f (\256)1980 3716 w 8 CW f ( of G, as dimensioned in the)6 1482(the row \(leading\) dimension)3 1362 2 2196 3700 t (calling program)1 720 1 2196 3800 t (X)1440 4000 w 12 S f (\256)1980 4016 w 8 CW f (the vector)1 480 1 2196 4000 t 8 I f (x)2724 4000 w 8 CW f (to be multiplied)2 768 1 2807 4000 t (B)1440 4200 w 12 S f (\254)1980 4216 w 8 CW f (the vector A)2 576 1 2196 4200 t 8 I f (x)2772 4200 w 7 B f (Error situations:)1 504 1 720 4500 t 8 CW f (\(All errors in this subprogram are fatal \320)7 2016 1 1512 4500 t (see)1512 4600 w 8 I f (Error Handling)1 504 1 1704 4600 t 8 CW f (, Framework Chapter\))2 960 1 2208 4600 t (Number Error)1 1536 1 1800 4800 t ( < 1)2 192(1 N)1 984 2 1944 5000 t ( < 1)2 192(2 ML)1 1032 2 1944 5200 t ( < ML)2 240(3 M)1 984 2 1944 5400 t ( < M)2 192(4 IG)1 1032 2 1944 5600 t 7 B f (Double-precision version:)1 769 1 720 5900 t 8 CW f (DBAML with G, X, and B declared double precision.)8 2352 1 1800 5900 t 7 B f (Complex version:)1 527 1 720 6200 t 8 CW f (CBAML with G, X, and B declared complex)7 1872 1 1440 6200 t 7 B f (Storage:)720 6500 w 8 CW f (None)1296 6500 w 10 R f (Linear Algebra)1 606 1 360 7500 t (\320 24 \320)2 350 1 2705 7620 t (BAML)360 7740 w cleartomark showpage saveobj restore %%EndPage: 24 24 %%Page: 25 25 /saveobj save def mark 25 pagesetup 10 R f (-- --)1 5544 1 0 120 t 8 R f (PORT)360 600 w 10 R f ( Algebra)1 346(library Linear)1 4463 2 591 600 t ( BAML)1 4305(February 11, 1993)2 735 2 360 840 t 7 B f (Time:)720 1300 w 8 CW f (M)1296 1300 w 8 S f (\264)1344 1300 w 8 CW f (N additions)1 528 1 1388 1300 t (M)1296 1400 w 8 S f (\264)1344 1400 w 8 CW f (N multiplications)1 816 1 1388 1400 t 7 B f (See also:)1 259 1 720 1700 t 8 CW f (BABS, BACE, BADC, BALU, BALE, BASS)5 1632 1 1296 1700 t 7 B f (Author:)720 2000 w 8 CW f (Linda Kaufman)1 624 1 1296 2000 t 7 B f (Example:)720 2300 w 8 CW f (This example checks the consistency of BAML and BASS the banded system solver.)12 3744 1 1296 2300 t (First the example uses BAML to compute for a given vector)10 2766 1 1296 2400 t 8 I f (x)4085 2400 w 8 CW f (and a given matrix)3 870 1 4170 2400 t 8 I f (A)1296 2500 w 8 CW f (the vector)1 481 1 1393 2500 t 8 I f (b)1923 2500 w 8 S f (=)2030 2500 w 8 I f (Ax.)2141 2500 w 8 CW f (Then the problem is inverted, i.e., BASS is used to find)10 2698 1 2342 2500 t (the vector)1 487 1 1296 2600 t 8 I f (x)1838 2600 w 8 CW f (which satisfies)1 727 1 1928 2600 t 8 I f (Ax)2682 2600 w 8 S f (=)2833 2600 w 8 I f (b)2944 2600 w 8 CW f (. This)1 343 1 2984 2600 t 8 I f (x)3382 2600 w 8 CW f ( with the origi-)3 786(is then compared)2 782 2 3472 2600 t ( vector)1 355( The)1 259(nal vector.)1 547 3 1296 2700 t 8 I f (x)2524 2700 w 8 CW f (is generated randomly and the 10)5 1636 1 2627 2700 t 8 S f (\264)4263 2700 w 8 CW f (10 matrix)1 452 1 4307 2700 t 8 I f (A)4827 2700 w 8 CW f (is)4944 2700 w (given by)1 384 1 1296 2800 t (0 1 2)2 384 1 2556 3000 t (1 0 1 2)3 552 1 2556 3100 t (2 1 0 1 2)4 720 1 2556 3200 t (2 1 0 1 2)4 720 1 2724 3300 t (. . .)2 384 1 3060 3400 t (2 1 0 1 2)4 720 1 3060 3500 t (2 1 0 1)3 552 1 3228 3600 t (2 1 0)2 384 1 3396 3700 t 6 CW f (INTEGER IG, M, ML, N, I, IWRITE, I1MACH)7 1404 1 1980 3980 t (REAL G\(5,20\), X\(20\), B\(20\), UNI, ERR, SASUM, ABS, COND)8 1944 1 1980 4060 t (IG=5)1980 4140 w (M=5)1980 4220 w (N=10)1980 4300 w (ML=3)1980 4380 w (C)1656 4460 w (C CONSTRUCT THE A MATRIX AND PACK IT INTO G)9 1548 1 1656 4540 t (C)1656 4620 w (DO 10 I=1,N)2 396 1 2016 4700 t (G\(1,I\)=2.0)2124 4780 w (G\(2,I\)=1.0)2124 4860 w (G\(3,I\)=0.0)2124 4940 w (G\(4,I\)=1.0)2124 5020 w (G\(5,I\)=2.0)2124 5100 w (10 CONTINUE)1 576 1 1728 5180 t (C)1656 5260 w (C CONSTRUCT A RANDOM VECTOR)4 972 1 1656 5340 t (C)1656 5420 w (DO 20 I=1,N)2 396 1 2016 5500 t (X\(I\)=UNI\(0\))2124 5580 w (20 CONTINUE)1 576 1 1728 5660 t (C)1656 5740 w (C CONSTRUCT B=AX)2 576 1 1656 5820 t (C)1656 5900 w (CALL BAML\(N,ML,M,G,IG,X,B\))1 936 1 2016 5980 t (C)1656 6060 w (C SOLVE THE SYSTEM AX=B)4 828 1 1656 6140 t (C)1656 6220 w (CALL BASS\(N,ML,M,G,IG,B,N,1,COND\))1 1188 1 2016 6300 t (C)1656 6380 w (C PRINT OUT THE TRUE SOLUTION AND THE COMPUTED SOLUTION)9 1980 1 1656 6460 t (C)1656 6540 w (IWRITE=I1MACH\(2\))2016 6620 w (WRITE\(IWRITE,21\))2016 6700 w ( SOLUTION\))1 360( COMPUTED)1 396( TRUE SOLUTION)2 504(21 FORMAT\(34H)1 648 4 1728 6780 t (WRITE\(IWRITE,22\)\(X\(I\),B\(I\),I=1,N\))2016 6860 w 10 R f (Linear Algebra)1 606 1 4794 7520 t (\320 25 \320)2 350 1 2705 7640 t (BAML)5111 7760 w cleartomark showpage saveobj restore %%EndPage: 25 25 %%Page: 26 26 /saveobj save def mark 26 pagesetup 10 R f (-- --)1 5544 1 0 120 t (Linear Algebra)1 606 1 360 600 t 8 R f (PORT)4903 600 w 10 R f (library)5134 600 w ( 11, 1993)2 375(BAML February)1 4665 2 360 840 t 6 CW f ( ,2E17.8\))1 324(22 FORMAT\(1H)1 612 2 1728 1280 t (C)1656 1360 w (C COMPUTE THE RELATIVE ERROR)4 1008 1 1656 1440 t (C)1656 1520 w (ERR=0.0)2016 1600 w (DO 30 I=1,N)2 396 1 2016 1680 t (ERR=ERR+ABS\(B\(I\)-X\(I\)\))2124 1760 w (30 CONTINUE)1 576 1 1728 1840 t (ERR=ERR/SASUM\(N,X,1\))2016 1920 w (WRITE\(IWRITE,31\)ERR)2016 2000 w ( RELATIVE ERROR IS ,1PE15.7\))4 1008(31 FORMAT\(19H)1 648 2 1728 2080 t (WRITE\(IWRITE,32\)COND)2016 2160 w ( CONDITION NUMBER IS,1PE15.7\))3 1044(32 FORMAT\(20H)1 648 2 1728 2240 t (STOP)2016 2320 w (END)2016 2400 w 10 R f (Linear Algebra)1 606 1 360 7500 t (\320 26 \320)2 350 1 2705 7620 t (BAML)360 7740 w cleartomark showpage saveobj restore %%EndPage: 26 26 %%Page: 27 27 /saveobj save def mark 27 pagesetup 10 R f (-- --)1 5544 1 0 120 t 8 R f (PORT)360 600 w 10 R f ( Algebra)1 346(library Linear)1 4463 2 591 600 t ( BAML)1 4305(February 11, 1993)2 735 2 360 840 t 8 CW f (When the above program was executed on the Honeywell 6000 machine at Bell Lab-)13 3744 1 1296 1300 t (oratories, which has a machine precision of)6 2064 1 1296 1400 t 8 R f (1.)3408 1400 w 8 S f (\264)3474 1400 w 8 R f (10)3524 1400 w 5 S f (-)3608 1368 w 5 R f (8)3640 1368 w 8 CW f (, the following was printed:)4 1344 1 3671 1400 t 6 CW f ( SOLUTION)1 324( COMPUTED)1 396(TRUE SOLUTION)1 468 3 1692 1680 t ( 00)1 108( 0.22925605E)1 504(0.22925607E 00)1 504 3 1800 1760 t ( 00)1 108( 0.76687499E)1 504(0.76687502E 00)1 504 3 1800 1840 t ( 00)1 108( 0.68317685E)1 504(0.68317685E 00)1 504 3 1800 1920 t ( 00)1 108( 0.50919110E)1 504(0.50919111E 00)1 504 3 1800 2000 t ( 00)1 108( 0.87455962E)1 504(0.87455959E 00)1 504 3 1800 2080 t ( 00)1 108( 0.64464102E)1 504(0.64464101E 00)1 504 3 1800 2160 t ( 00)1 108( 0.84746839E)1 504(0.84746840E 00)1 504 3 1800 2240 t ( 00)1 108( 0.35396345E)1 504(0.35396343E 00)1 504 3 1800 2320 t ( 00)1 108( 0.39889155E)1 504(0.39889160E 00)1 504 3 1800 2400 t ( 00)1 108( 0.45709425E)1 504(0.45709422E 00)1 504 3 1800 2480 t ( 3.8447574E)1 468(RELATIVE ERROR IS)2 612 2 1692 2560 t 6 S f (-)2772 2560 w 6 CW f (08)2805 2560 w ( 01)1 108( 4.3333333E)1 432(CONDITION NUMBER IS)2 684 3 1692 2640 t 8 CW f (The condition number of the matrix and the precision of the Honeywell suggest)12 3744 1 1296 2940 t ( error of)2 482(that even in the absence of roundoff error in BAML, a relative)11 3262 2 1296 3040 t (4.3)1296 3140 w 8 S f (\264)1440 3140 w 8 CW f (10)1484 3140 w 5 S f (-)1588 3108 w 5 R f (7)1624 3108 w 8 CW f ( value computed above is quite reason-)6 1890( The)1 251(would not be surprising.)3 1185 3 1714 3140 t (able.)1296 3240 w 10 R f (Linear Algebra)1 606 1 4794 7500 t (\320 27 \320)2 350 1 2705 7620 t (BAML)5111 7740 w cleartomark showpage saveobj restore %%EndPage: 27 27 %%Page: 28 28 /saveobj save def mark 28 pagesetup 10 R f (-- --)1 5544 1 0 120 t (Linear Algebra)1 606 1 360 600 t 8 R f (PORT)4903 600 w 10 R f (library)5134 600 w ( 11, 1993)2 375(BAML February)1 4665 2 360 840 t 8 CW f ( of a banded unsymmetric matrix)5 1488( norm)1 288(BANM \320)1 288 3 2136 1300 t 7 B f (Purpose:)720 1600 w 8 CW f (BANM \(BAnded matrix NorM\) computes the infinity norm of a general banded ma-)12 3744 1 1296 1600 t (trix A. The infinity norm is defined as)7 1872 1 1296 1740 t 5 R f (1)3216 1796 w 5 S f (\243)3249 1796 w 5 I f (i)3289 1796 w 5 S f (\243)3315 1796 w 5 I f (n)3351 1796 w 8 R f (max)3227 1740 w 5 I f (j)3391 1820 w 5 S f (=)3413 1820 w 5 R f (1)3449 1820 w 13 S f (S)3394 1764 w 5 I f (n)3420 1660 w 8 S f (\357)3490 1740 w 8 I f (a)3535 1740 w 5 I f (i j)1 32 1 3583 1756 t 8 S f (\357)3627 1740 w 7 B f (Type:)720 2104 w 8 CW f (Real function)1 624 1 1296 2104 t 7 B f (Usage:)720 2404 w 8 CW f ( = BANM \(N, ML, M, G, IG\))7 1584 1 1296 2404 t (N)1440 2604 w 12 S f (\256)1980 2620 w 8 CW f (the number of rows in A)5 1104 1 2196 2604 t (ML)1440 2804 w 12 S f (\256)1980 2820 w 8 CW f (the number of nonzero bands on and below the diagonal of A)11 2784 1 2196 2804 t (M)1440 3004 w 12 S f (\256)1980 3020 w 8 CW f (the number of nonzero bands in A)6 1536 1 2196 3004 t (G)1440 3204 w 12 S f (\256)1980 3220 w 8 CW f ( as fol-)2 414(a matrix into which the matrix A has been packed)9 2430 2 2196 3204 t (lows:)2196 3304 w (G \(ML + j)3 432 1 2916 3454 t 8 S f (-)3348 3454 w 8 CW f (i, i\) =)2 336 1 3392 3454 t 8 I f (a)3776 3454 w 5 I f (i j)1 32 1 3824 3470 t 8 CW f (i.e. the leftmost diagonal of A is in the first row of G)12 2688 1 2196 3604 t (\(See the introduction to this chapter.\))5 1872 1 2196 3704 t ( in the calling program,)4 1256(G should be dimensioned \(IG,KG\))4 1588 2 2196 3804 t (where IG)1 384 1 2196 3904 t 8 S f (\263)2580 3904 w 8 CW f (M and KG)2 384 1 2624 3904 t 8 S f (\263)3008 3904 w 8 CW f (N.)3052 3904 w (IG)1440 4104 w 12 S f (\256)1980 4120 w 8 CW f (the row \(leading\) dimension of G, as dimensioned in the)9 2640 1 2196 4104 t (calling program)1 720 1 2196 4204 t ()1440 4444 w 12 S f (\254)1980 4460 w 5 R f (1)2196 4500 w 5 S f (\243)2229 4500 w 5 I f (i)2265 4500 w 5 S f (\243)2283 4500 w 5 I f (n)2315 4500 w 8 R f (max)2199 4444 w 5 I f (j)2355 4524 w 5 S f (=)2377 4524 w 5 R f (1)2413 4524 w 13 S f (S)2358 4468 w 5 I f (n)2384 4364 w 8 S f (\357)2454 4444 w 8 I f (a)2499 4444 w 5 I f (i j)1 32 1 2547 4460 t 8 S f (\357)2591 4444 w 7 B f (Error situations:)1 504 1 720 4808 t 8 CW f (\(All errors in this subprogram are fatal \320)7 2016 1 1512 4808 t (see)1512 4908 w 8 I f (Error Handling)1 504 1 1704 4908 t 8 CW f (, Framework Chapter\))2 960 1 2208 4908 t (Number Error)1 1536 1 1800 5108 t ( < 1)2 192(1 N)1 984 2 1944 5308 t ( < 1)2 192(2 ML)1 1032 2 1944 5508 t ( < ML)2 240(3 M)1 984 2 1944 5708 t ( < M)2 192(4 IG)1 1032 2 1944 5908 t 7 B f (Double-precision version:)1 769 1 720 6208 t 8 CW f (DBANM with G and DBANM declared double precision)7 2304 1 1633 6208 t 7 B f (Complex version:)1 527 1 720 6508 t 8 CW f (CBANM with G declared complex)4 1392 1 1392 6508 t 10 R f (Linear Algebra)1 606 1 360 7500 t (\320 28 \320)2 350 1 2705 7620 t (BANM)360 7740 w cleartomark showpage saveobj restore %%EndPage: 28 28 %%Page: 29 29 /saveobj save def mark 29 pagesetup 10 R f (-- --)1 5544 1 0 120 t 8 R f (PORT)360 600 w 10 R f ( Algebra)1 346(library Linear)1 4463 2 591 600 t ( BANM)1 4305(February 11, 1993)2 735 2 360 840 t 7 B f (Storage:)720 1300 w 8 CW f (None)1296 1300 w 7 B f (Time:)720 1600 w 8 CW f (N)1296 1600 w 8 S f (\264)1392 1600 w 8 CW f (M additions)1 528 1 1484 1600 t (N comparisons)1 624 1 1296 1700 t 7 B f (See also:)1 259 1 720 2000 t 8 CW f (BADC, BALU, BALE, BASS, BACE)4 1344 1 1296 2000 t 7 B f (Author:)720 2300 w 8 CW f (Linda Kaufman)1 624 1 1296 2300 t 7 B f (Example:)720 2600 w 8 CW f ( by obtaining norms of five)5 1336(In this example we verify the correctness of BANM)8 2408 2 1296 2600 t ( elements are given by)4 1068(matrices of various bandwidths whose nonzero)5 2132 2 1296 2700 t 8 I f (a)4547 2700 w 5 I f (i j)1 32 1 4595 2716 t 8 S f (=)4700 2700 w 8 I f (i)4811 2700 w 8 S f (+)4900 2700 w 8 I f (j)5018 2700 w 8 CW f (For each matrix, the 2)4 1092 1 1296 2800 t 8 S f (\264)2388 2800 w 8 CW f (ML)2432 2800 w 8 S f (-)2528 2800 w 8 CW f ( are nonzero. The program fragment)5 1682(1 main diagonals)2 786 2 2572 2800 t ( a column)2 444(packing the matrix A into the array G uses the fact that traversing)12 3300 2 1296 2900 t ( extra values that get put)5 1298( The)1 250( row of A.)3 510(of G is equivalent to traversing a)6 1686 4 1296 3000 t (into G by the program are not referenced by BANM.)9 2352 1 1296 3100 t (In our example the norm computed by BANM is compared with the true norm, known)14 3744 1 1296 3300 t (to be M)2 378 1 1296 3400 t 8 S f (\264)1674 3400 w 8 CW f (\(N)1718 3400 w 8 S f (-)1814 3400 w 8 CW f (ML+1\))1858 3400 w 8 S f (\264)2098 3400 w 8 CW f (2, which is obtained by summing the M elements in column)10 2898 1 2142 3400 t (N)1296 3500 w 8 S f (-)1344 3500 w 8 CW f (ML+1.)1388 3500 w 6 CW f ( IWRITE, I1MACH)2 540( ML, M, N, I, J,)5 756(INTEGER IG,)1 396 3 1872 3780 t ( 80\), START, BANM, TRNORM)4 1044(REAL G\(13,)1 360 2 1872 3860 t (IG=13)1872 3940 w (N=80)1872 4020 w (DO 30 ML=2,6)2 432 1 1872 4100 t (C)1656 4180 w (C CONSTRUCT THE MATRIX A\(I,J\)=I+J AND PACK IT INTO G)9 1872 1 1656 4260 t (C)1656 4340 w (M=2*ML-1)1980 4420 w (START=-FLOAT\(M-ML\))1980 4500 w (DO 20 I=1,N)2 396 1 1980 4580 t (G\(1,I\)=START+FLOAT\(2*I\))2088 4660 w (DO 10 J=2,M)2 396 1 2088 4740 t (G\(J,I\)=G\(J-1,I\)+1.0)2196 4820 w (10 CONTINUE)1 684 1 1692 4900 t (20 CONTINUE)1 576 1 1692 4980 t (C)1656 5060 w (C PRINT OUT THE NORM CALCULATED FROM BANM AND THE TRUE NORM)11 2124 1 1656 5140 t (C)1656 5220 w (TRNORM=M*\(N-ML+1\)*2)1980 5300 w (IWRITE=I1MACH\(2\))1980 5380 w (WRITE\(IWRITE,21\)ML)1980 5460 w ( ML IS ,I4\))3 396(21 FORMAT\(/6H)1 648 2 1692 5540 t (WRITE\(IWRITE,22\)TRNORM,BANM\(N,ML,M,G,IG\))1980 5620 w ( THE TRUE NORM=,E15.5,15H COMPUTED NORM=,E15.5\))5 1692(22 FORMAT\(15H)1 648 2 1692 5700 t (30 CONTINUE)1 468 1 1692 5780 t (STOP)1872 5860 w (END)1872 5940 w 8 CW f (When the above program was executed on the Honeywell 6000 machine at Bell Lab-)13 3744 1 1296 6220 t (oratories, the following was printed:)4 1776 1 1296 6320 t 6 CW f ( 2)1 144(ML IS)1 180 2 1692 6680 t ( 03)1 108( 0.47400E)1 432( 03 COMPUTED NORM=)3 648( 0.47400E)1 432(THE TRUE NORM=)2 504 5 1692 6760 t 10 R f (Linear Algebra)1 606 1 4794 7500 t (\320 29 \320)2 350 1 2705 7620 t (BANM)5100 7740 w cleartomark showpage saveobj restore %%EndPage: 29 29 %%Page: 30 30 /saveobj save def mark 30 pagesetup 10 R f (-- --)1 5544 1 0 120 t (Linear Algebra)1 606 1 360 600 t 8 R f (PORT)4903 600 w 10 R f (library)5134 600 w ( 11, 1993)2 375(BANM February)1 4665 2 360 840 t 6 CW f ( 3)1 144(ML IS)1 180 2 1692 1280 t ( 03)1 108( 0.78000E)1 432( 03 COMPUTED NORM=)3 648( 0.78000E)1 432(THE TRUE NORM=)2 504 5 1692 1360 t ( 4)1 144(ML IS)1 180 2 1692 1520 t ( 04)1 108( 0.10780E)1 432( 04 COMPUTED NORM=)3 648( 0.10780E)1 432(THE TRUE NORM=)2 504 5 1692 1600 t ( 5)1 144(ML IS)1 180 2 1692 1760 t ( 04)1 108( 0.13680E)1 432( 04 COMPUTED NORM=)3 648( 0.13680E)1 432(THE TRUE NORM=)2 504 5 1692 1840 t ( 6)1 144(ML IS)1 180 2 1692 2000 t ( 04)1 108( 0.16500E)1 432( 04 COMPUTED NORM=)3 648( 0.16500E)1 432(THE TRUE NORM=)2 504 5 1692 2080 t 10 R f (Linear Algebra)1 606 1 360 7500 t (\320 30 \320)2 350 1 2705 7620 t (BANM)360 7740 w cleartomark showpage saveobj restore %%EndPage: 30 30 %%Page: 31 31 /saveobj save def mark 31 pagesetup 10 R f (-- --)1 5544 1 0 120 t 8 R f (PORT)360 600 w 10 R f ( Algebra)1 346(library Linear)1 4463 2 591 600 t ( BANM)1 4305(February 11, 1993)2 735 2 360 840 t 8 CW f (BASS \320 banded linear system solution with condition estimation)8 2976 1 1680 1300 t 7 B f (Purpose:)720 1600 w 8 CW f (BASS \(BAnded System Solution\) solves AX=B where A is a general banded matrix.)12 3744 1 1296 1600 t (An estimate of the condition number of A is provided.)9 2544 1 1296 1700 t 7 B f (Usage:)720 2000 w 8 CW f (CALL BASS \(N, ML, M, G, IG, B, IB, NB, COND\))10 2112 1 1296 2000 t (N)1440 2200 w 12 S f (\256)1980 2216 w 8 CW f (the number of equations)3 1104 1 2196 2200 t (ML)1440 2400 w 12 S f (\256)1980 2416 w 8 CW f (the number of nonzero bands on and below the diagonal of A)11 2784 1 2196 2400 t (M)1440 2600 w 12 S f (\256)1980 2616 w 8 CW f (the number of nonzero bands of A)6 1536 1 2196 2600 t (G)1440 2800 w 12 S f (\256)1980 2816 w 8 CW f ( as fol-)2 414(a matrix into which the matrix A has been packed)9 2430 2 2196 2800 t (lows:)2196 2900 w (G\(ML+j)2916 3050 w 8 S f (-)3204 3050 w 8 CW f (i, i\) =)2 336 1 3248 3050 t 8 I f (a)3632 3050 w 5 I f (i j)1 32 1 3680 3066 t 8 CW f (i.e. the leftmost band of A is in the first row of G)12 2496 1 2196 3200 t (\(See the introduction to this chapter.\))5 1872 1 2196 3300 t ( in the calling program,)4 1256(G should be dimensioned \(IG,KG\))4 1588 2 2196 3400 t (where IG)1 384 1 2196 3500 t 8 S f (\263)2580 3500 w 8 CW f (M and KG)2 384 1 2624 3500 t 8 S f (\263)3008 3500 w 8 CW f (N.)3052 3500 w (G is overwritten during the solution)5 1728 1 2196 3600 t (IG)1440 3800 w 12 S f (\256)1980 3816 w 8 CW f ( of G, as dimensioned in the)6 1482(the row \(leading\) dimension)3 1362 2 2196 3800 t (calling program)1 720 1 2196 3900 t (B)1440 4100 w 12 S f (\256)1980 4116 w 8 CW f (the matrix of right-hand sides, dimensioned \(IB, KB\) in)8 2640 1 2196 4100 t (the calling program, where IB)4 1392 1 2196 4200 t 8 S f (\263)3588 4200 w 8 CW f (N and KB)2 384 1 3632 4200 t 8 S f (\263)4016 4200 w 8 CW f (NB.)4060 4200 w 12 S f (\254)1980 4416 w 8 CW f (the solution X)2 672 1 2196 4400 t (IB)1440 4600 w 12 S f (\256)1980 4616 w 8 CW f (the row \(leading\) dimension of B, as dimensioned in the)9 2640 1 2196 4600 t (calling program)1 720 1 2196 4700 t (NB)1440 4900 w 12 S f (\256)1980 4916 w 8 CW f (the number of right-hand sides)4 1440 1 2196 4900 t (COND)1440 5100 w 12 S f (\254)1980 5116 w 8 CW f ( \(See)1 288(an estimate of the condition number of A)7 1920 2 2196 5100 t 6 B f (Note 1)1 164 1 4452 5100 t 8 CW f (\))4616 5100 w 7 B f (Note 1:)1 215 1 720 5400 t 8 CW f (The condition number measures the sensitivity of the solution of a linear sys-)12 3744 1 1296 5400 t ( the elements of)3 798( If)1 202( matrix and in the right-hand side.)6 1740(tem to errors in the)4 1004 4 1296 5500 t ( have)1 257(the matrix and the right-hand side\(s\) of your linear system)9 2976 2 1296 5600 t 8 B f (d)4594 5600 w 8 CW f (decimal)4704 5600 w ( might have as few as)5 1043(digits of precision, the solution)4 1616 2 1296 5700 t 8 B f (d)4010 5700 w 8 S f (-)4103 5700 w 8 R f (log)4195 5700 w 5 R f (10)4305 5716 w 8 CW f (\(COND\) correct)1 679 1 4361 5700 t ( if COND is greater than)5 1207( Thus)1 299(decimal digits.)1 731 3 1296 5800 t 8 R f (10)3592 5800 w 5 CW f (Bd)3680 5768 w 5 I f (P)3748 5768 w 8 CW f (, there may be no correct)5 1255 1 3785 5800 t (digits.)1296 5900 w ( to be well-conditioned, then the)5 1624(If the given matrix, A, is known in advance)8 2120 2 1296 6100 t ( little faster than BASS.)4 1252(user may wish to use the routine BALE, which is a)10 2492 2 1296 6200 t (Ordinarily, however, the user is strongly urged to choose BASS, and to follow)12 3744 1 1296 6300 t (it by a test of the condition estimate.)7 1872 1 1296 6400 t 10 R f (Linear Algebra)1 606 1 4794 7500 t (\320 31 \320)2 350 1 2705 7620 t (BASS)5149 7740 w cleartomark showpage saveobj restore %%EndPage: 31 31 %%Page: 32 32 /saveobj save def mark 32 pagesetup 10 R f (-- --)1 5544 1 0 120 t (Linear Algebra)1 606 1 360 600 t 8 R f (PORT)4903 600 w 10 R f (library)5134 600 w ( 11, 1993)2 375(BASS February)1 4665 2 360 840 t 7 B f (Note 2:)1 215 1 720 1300 t 8 CW f ( with the same coefficient ma-)5 1480(Users who wish to solve a sequence of problems)8 2264 2 1296 1300 t (trix, but different right-hand sides)4 1780 1 1296 1400 t 8 I f (not all known in advance,)4 874 1 3109 1400 t 8 CW f (should not use BASS,)3 996 1 4044 1400 t ( the example of BADC.\))4 1088( \(See)1 296(but should call subprograms BACE, BAFS and BABS.)7 2360 3 1296 1500 t ( the introduction to this)4 1212(BACE is called once to get the LU decomposition \(see)9 2532 2 1296 1600 t (chapter\) and then the pair, BAFS \(forward solve\) and BABS \(back solve\), is)12 3744 1 1296 1700 t (called for each new right-hand side.)5 1728 1 1296 1800 t 7 B f (Error situations:)1 534 1 720 2100 t 8 CW f (*\(The user can elect to `recover' from those errors marked with an)11 3498 1 1542 2100 t ( see)1 240(asterisk \320)1 480 2 1512 2200 t 8 I f (Error Handling)1 504 1 2280 2200 t 8 CW f (, Framework Chapter\))2 960 1 2784 2200 t (Number Error)1 1536 1 1800 2400 t ( < 1)2 192(1 N)1 984 2 1944 2600 t ( < 1)2 192(2 ML)1 1032 2 1944 2800 t ( < ML)2 240(3 M)1 984 2 1944 3000 t ( < M)2 192(4 IG)1 1032 2 1944 3200 t ( < N)2 192(5 IB)1 1032 2 1944 3400 t ( < 1)2 192(6 NB)1 1032 2 1944 3600 t ( matrix whose rank is at least k)7 1536( singular)1 984(10 + k*)2 336 3 1944 3800 t 7 B f (Double-precision version:)1 769 1 720 4100 t 8 CW f (DBASS with G, B, and COND declared double precision.)8 2496 1 1633 4100 t 7 B f (Complex version:)1 527 1 720 4400 t 8 CW f (CBASS with G and B declared complex)6 1680 1 1440 4400 t 7 B f (Storage:)720 4700 w 8 CW f ( and N)2 324(N integer locations)2 946 2 1296 4700 t 8 S f (\264)2566 4700 w 8 CW f (ML real \(double precision for DBASS, complex for)7 2430 1 2610 4700 t (CBASS\) locations of scratch storage in the dynamic storage stack)9 3072 1 1296 4800 t 7 B f (Time:)720 5100 w 8 CW f (at most N)2 432 1 1296 5100 t 8 S f (\264)1728 5100 w 8 CW f (\(\(ML+M)1772 5100 w 8 S f (-)2060 5100 w 8 CW f (2\))2104 5100 w 8 S f (\264)2200 5100 w 8 CW f (\(NB+1\)+M)2244 5100 w 8 S f (\264)2628 5100 w 8 CW f (\(ML+5\)+3\) additions)1 912 1 2672 5100 t (at most N)2 432 1 1296 5200 t 8 S f (\264)1728 5200 w 8 CW f (\(\(ML+M)1772 5200 w 8 S f (-)2060 5200 w 8 CW f (2\))2104 5200 w 8 S f (\264)2200 5200 w 8 CW f (\(NB+1\)+M)2244 5200 w 8 S f (\264)2628 5200 w 8 CW f (\(ML+2\)+2\) multiplications)1 1200 1 2672 5200 t (N)1296 5300 w 8 S f (\264)1344 5300 w 8 CW f (\(NB+ML+1\) divisions)1 912 1 1388 5300 t 7 B f (Method:)720 5600 w 8 CW f (Gaussian elimination with partial pivoting)4 2016 1 1296 5600 t (See the reference below for the method to estimate the condition number.)11 3456 1 1296 5700 t (BASS calls BACE, BAFS, and BABS)5 1488 1 1296 5800 t 7 B f (See also:)1 259 1 720 6100 t 8 CW f (BABS, BACE, BADC, BALU, BALE, BAFS)5 1632 1 1296 6100 t 7 B f (Author:)720 6400 w 8 CW f (Linda Kaufman)1 624 1 1296 6400 t 7 B f (Reference:)720 6700 w 8 CW f (Cline, A. K., Moler, C. B., Stewart, G. W., and Wilkinson, J. H., An estimate)14 3696 1 1344 6700 t (for the condition number,)3 1200 1 1296 6800 t 8 I f (SIAM J. Numer. Anal. 16)4 805 1 2592 6800 t 8 CW f (\(1979\), 368-375.)1 768 1 3445 6800 t 10 R f (Linear Algebra)1 606 1 360 7500 t (\320 32 \320)2 350 1 2705 7620 t (BASS)360 7740 w cleartomark showpage saveobj restore %%EndPage: 32 32 %%Page: 33 33 /saveobj save def mark 33 pagesetup 10 R f (-- --)1 5544 1 0 120 t 8 R f (PORT)360 600 w 10 R f ( Algebra)1 346(library Linear)1 4463 2 591 600 t ( BASS)1 4305(February 11, 1993)2 735 2 360 840 t 7 B f (Example:)720 1300 w 8 CW f ( banded linear systems are solved with various number)8 2616(In this example several)3 1128 2 1296 1300 t ( the condition num-)3 936( of)1 153( Estimates)1 537(of diagonals and two right-hand sides each.)6 2118 4 1296 1400 t ( are found and the relative errors in the so-)9 2196(bers of the coefficient matrices)4 1548 2 1296 1500 t ( the example the nonzero elements of the matrix are)9 2484( In)1 196(lution are calculated.)2 1064 3 1296 1600 t (given by)1 397 1 1296 1700 t 8 I f (a)1754 1700 w 5 I f (i j)1 32 1 1802 1716 t 8 S f (=)1853 1700 w 8 I f (i)1910 1700 w 8 S f (+)1951 1700 w 8 I f (j)2008 1700 w 8 CW f ( matrix the 2)3 666(For each)1 397 2 2091 1700 t 8 S f (\264)3154 1700 w 8 CW f (ML)3198 1700 w 8 S f (-)3294 1700 w 8 CW f ( The)1 254(1 main diagonals are nonzero.)4 1448 2 3338 1700 t ( the array G uses the fact that)7 1614(program fragment packing the matrix A into)6 2130 2 1296 1800 t ( right-)1 343( The)1 247( of G is equivalent to traversing a row of A.)10 2230(traversing a column)2 924 4 1296 1900 t ( the elements of the first solution are all)8 2120(hand sides are determined so that)5 1624 2 1296 2000 t (ones and the)2 616 1 1296 2100 t 8 I f (i)1952 2100 w 5 I f (th)1982 2068 w 8 CW f ( second solution is)3 975(element of the)2 712 2 2095 2100 t 8 I f (i)3851 2100 w 8 CW f ( subroutine BAML,)2 858(. The)1 309 2 3873 2100 t ( by a banded matrix packed appropriately into G, is)9 2484( vector)1 388(which multiplies a)2 872 3 1296 2200 t (invoked to compute the right-hand sides.)5 1920 1 1296 2300 t 6 CW f (INTEGER N, IG, ML, M, I, J, IWRITE, I1MACH)8 1512 1 1908 2580 t (REAL G\(13,80\), B\(80,2\), X\(80\))3 1044 1 1908 2660 t (REAL START, FLOAT, ERR, ERR2, ABS, COND)6 1404 1 1908 2740 t (IG=13)1908 2820 w (N=80)1908 2900 w (DO 60 ML=2,6)2 432 1 1908 2980 t (C)1656 3060 w (C CONSTRUCT THE MATRIX A\(I,J\)=I+J AND PACK IT INTO G)9 1872 1 1656 3140 t (C)1656 3220 w (M=2*ML-1)2088 3300 w (START=-FLOAT\(M-ML\))2088 3380 w (DO 20 I=1,N)2 396 1 2088 3460 t (G\(1,I\)=START+FLOAT\(2*I\))2196 3540 w (IF\(M.EQ.1\) GO TO 20)3 684 1 2196 3620 t (DO 10 J=2,M)2 396 1 2196 3700 t (G\(J,I\)=G\(J-1,I\)+1.)2304 3780 w (10 CONTINUE)1 756 1 1728 3860 t (20 CONTINUE)1 648 1 1728 3940 t (C CONSTRUCT FIRST RIGHT-HAND SIDE SO SOLUTION IS ALL 1S)9 1980 1 1656 4020 t (DO 30 I=1,N)2 396 1 2088 4100 t (30 X\(I\)=1)1 684 1 1728 4180 t (CALL BAML\(N,ML,M,G,IG,X,B\))1 936 1 2088 4260 t (C CONSTRUCT THE SECOND COLUMN SO X\(I\)=I)6 1404 1 1656 4340 t (DO 40 I=1,N)2 396 1 2088 4420 t (40 X\(I\)=I)1 684 1 1728 4500 t (CALL BAML\(N,ML,M,G,IG,X,B\(1,2\)\))1 1116 1 2088 4580 t (C SOLVE THE SYSTEM)3 648 1 1656 4660 t (CALL BASS\(N,ML,M,G,IG,B,80,2,COND\))1 1224 1 2088 4740 t (C COMPUTE THE ERRORS IN THE SOLUTION)6 1296 1 1656 4820 t (ERR=0.0)2088 4900 w (ERR2=0.0)2088 4980 w (DO 50 I=1,N)2 396 1 2088 5060 t (ERR=ERR+ABS\(B\(I,1\)-1.0\))2196 5140 w (ERR2=ERR2+ABS\(B\(I,2\)-FLOAT\(I\)\))2196 5220 w (50 CONTINUE)1 648 1 1728 5300 t (ERR=ERR/FLOAT\(N\))2088 5380 w (ERR2=ERR2/FLOAT\(N*\(N+1\)\)*2.0)2088 5460 w (IWRITE=I1MACH\(2\))2088 5540 w (WRITE\(IWRITE,51\)ML,COND)2088 5620 w ( WHEN ML=,I4,21H THE CONDITION NO. IS,1PE15.7\))6 1656(51 FORMAT\(/9H)1 720 2 1728 5700 t (WRITE\(IWRITE,52\)ERR)2088 5780 w ( ,1PE15.7\))1 396( REL. ERROR IN THE FIRST SOLUTION IS)7 1296(52 FORMAT\(38H)1 720 3 1728 5860 t (WRITE\(IWRITE,53\)ERR2)2088 5940 w ( REL. ERROR IN THE SECOND SOLUTION IS ,1PE15.7\))8 1692(53 FORMAT\(38H)1 720 2 1728 6020 t (60 CONTINUE)1 540 1 1728 6100 t (70 CONTINUE)1 432 1 1728 6180 t (STOP)1872 6260 w (END)1872 6340 w 8 CW f ( executed on on the Honeywell 6000 computer at Bell)9 2484(When the above program was)4 1260 2 1296 6620 t (Labs, the following was printed.)4 1536 1 1296 6720 t 10 R f (Linear Algebra)1 606 1 4794 7500 t (\320 33 \320)2 350 1 2705 7620 t (BASS)5149 7740 w cleartomark showpage saveobj restore %%EndPage: 33 33 %%Page: 34 34 /saveobj save def mark 34 pagesetup 10 R f (-- --)1 5544 1 0 120 t (Linear Algebra)1 606 1 360 600 t 8 R f (PORT)4903 600 w 10 R f (library)5134 600 w ( 11, 1993)2 375(BASS February)1 4665 2 360 840 t 6 CW f ( 03)1 108( 6.1040422E)1 432( THE CONDITION NO. IS)4 756( 2)1 144(WHEN ML=)1 288 5 1692 1280 t ( 5.0114468E-07)1 612(REL. ERROR IN THE FIRST SOLUTION IS)6 1260 2 1692 1360 t ( 6.0025235E-07)1 576(REL. ERROR IN THE SECOND SOLUTION IS)6 1296 2 1692 1440 t ( 02)1 108( 5.9552785E)1 432( THE CONDITION NO. IS)4 756( 3)1 144(WHEN ML=)1 288 5 1692 1600 t ( 1.2554228E-07)1 612(REL. ERROR IN THE FIRST SOLUTION IS)6 1260 2 1692 1680 t ( 1.1807790E-07)1 576(REL. ERROR IN THE SECOND SOLUTION IS)6 1296 2 1692 1760 t ( 07)1 108( 1.0581919E)1 432( THE CONDITION NO. IS)4 756( 4)1 144(WHEN ML=)1 288 5 1692 1920 t ( 5.9645883E-04)1 612(REL. ERROR IN THE FIRST SOLUTION IS)6 1260 2 1692 2000 t ( 2.1994722E-03)1 576(REL. ERROR IN THE SECOND SOLUTION IS)6 1296 2 1692 2080 t ( 04)1 108( 3.2465961E)1 432( THE CONDITION NO. IS)4 756( 5)1 144(WHEN ML=)1 288 5 1692 2240 t ( 2.4201348E-06)1 612(REL. ERROR IN THE FIRST SOLUTION IS)6 1260 2 1692 2320 t ( 7.6222429E-07)1 576(REL. ERROR IN THE SECOND SOLUTION IS)6 1296 2 1692 2400 t ( 07)1 108( 3.5264744E)1 432( THE CONDITION NO. IS)4 756( 6)1 144(WHEN ML=)1 288 5 1692 2560 t ( 4.2312816E-04)1 612(REL. ERROR IN THE FIRST SOLUTION IS)6 1260 2 1692 2640 t ( 2.4684287E-03)1 576(REL. ERROR IN THE SECOND SOLUTION IS)6 1296 2 1692 2720 t 8 CW f ( a correlation between the)4 1268(The above program certainly indicates that there is)7 2476 2 1296 3020 t ( in the solution and the condition number of the coefficient)10 3010(relative errors)1 734 2 1296 3120 t ( error depends also on the)5 1338( it indicates that the relative)5 1573(matrix. Moreover)1 833 3 1296 3220 t (choice of the right-hand side. Although the relative errors for some of the)12 3744 1 1296 3320 t (systems might appear quite large, they are not unreasonably large in light of)12 3744 1 1296 3420 t (the following analysis:)2 1104 1 1296 3520 t (Let)1296 3720 w 8 S f (D)1536 3720 w 8 I f (b)1591 3720 w 8 CW f (represent a perturbation in the right-hand side of a linear system.)10 3216 1 1679 3720 t (If)1296 3888 w 8 I f (Ax)1446 3888 w 8 S f (=)1597 3888 w 8 I f (b)1708 3888 w 8 CW f (then)1802 3888 w 8 I f (A)2048 3888 w 8 R f (\()2103 3888 w 8 I f (x)2135 3888 w 8 S f (+ D)1 106 1 2189 3888 t 8 I f (x)2301 3888 w 8 R f (\))2342 3888 w 8 S f (=)2442 3888 w 8 I f (b)2553 3888 w 8 S f (+ D)1 106 1 2612 3888 t 8 I f (b)2724 3888 w 8 CW f (where)2818 3888 w 8 S f (\357 \357)1 84 1 3159 3944 t 8 I f (x)3249 3944 w 8 S f (\357 \357)1 84 1 3290 3944 t (\357 \357 D)2 139 1 3132 3840 t 8 I f (x)3277 3840 w 8 S f (\357 \357)1 84 1 3318 3840 t 8 S1 f (_ _______)1 294 1 3120 3864 t 8 S f (\243)3482 3888 w 8 I f (K)3586 3888 w 8 R f (\()3646 3888 w 8 I f (A)3678 3888 w 8 R f (\))3733 3888 w 8 S f (\354)3778 3818 w (\357)3778 3898 w (\356)3778 3978 w (\357 \357)1 84 1 3864 3944 t 8 I f (b)3954 3944 w 8 S f (\357 \357)1 84 1 4000 3944 t (\357 \357 D)2 139 1 3837 3840 t 8 I f (b)3982 3840 w 8 S f (\357 \357)1 84 1 4028 3840 t 8 S1 f (_ _______)1 299 1 3825 3864 t 8 S f (\374)4132 3818 w (\357)4132 3898 w (\376)4132 3978 w 8 CW f (where)4225 3888 w 8 I f (K)4519 3888 w 8 R f (\()4579 3888 w 8 I f (A)4611 3888 w 8 R f (\))4666 3888 w 8 CW f (is the)1 294 1 4746 3888 t (condition number of)2 954 1 1296 4072 t 8 I f (A)2318 4072 w 8 CW f (,)2367 4072 w 8 I f (K)2455 4072 w 8 R f (\()2515 4072 w 8 I f (A)2547 4072 w 8 R f (\))2602 4072 w 8 S f ( \357)1 45(= \357)1 150 2 2702 4072 t 8 I f (A)2903 4072 w 8 S f ( \357)1 45( \357)1 99(\357 \357)1 84 3 2958 4072 t 8 I f (A)3192 4072 w 5 S f (-)3249 4040 w 5 R f (1)3285 4040 w 8 S f (\357 \357)1 84 1 3341 4072 t 8 CW f (and)3493 4072 w 8 S f (\357 \357)1 84 1 3705 4072 t 8 CW f (.)3795 4048 w 8 S f (\357 \357)1 84 1 3868 4072 t 8 CW f (, is some norm, e.g.,)4 1088 1 3952 4072 t 8 S f (\357 \357)1 84 1 1296 4212 t 8 I f (x)1386 4212 w 8 S f (\357 \357)1 84 1 1427 4212 t 5 R f (1)1519 4228 w 8 S f (=)1617 4212 w 5 I f (i)1736 4292 w 5 S f (=)1762 4292 w 5 R f (1)1798 4292 w 13 S f (S)1741 4236 w 5 I f (n)1767 4132 w 8 S f (|)1837 4212 w 8 I f (x)1859 4212 w 5 I f (i)1902 4228 w 8 S f (|)1928 4212 w 8 CW f (if)1992 4212 w 8 I f (x)2108 4212 w 8 CW f (is a vector.)2 576 1 2191 4212 t (The methods used in our linear equation package are guaranteed to provide an)12 3744 1 1296 4476 t ( we assume that our method)5 1248( If)1 192(accurate answer to a slightly perturbed problem.)6 2304 3 1296 4576 t ( to a problem where)4 924(produces the correct answer)3 1302 2 1296 4676 t 8 S f (\357 \357 D)2 139 1 3573 4676 t 8 I f (b)3718 4676 w 8 S f ( \357 \357)2 90( \243 e)2 199(\357 \357)1 84 3 3764 4676 t 8 I f (b)4143 4676 w 8 S f (\357 \357)1 84 1 4189 4676 t 8 CW f (, where)1 339 1 4273 4676 t 8 S f (e)4663 4676 w 8 CW f (is the)1 291 1 4749 4676 t ( on the Honeywell 6000 where)5 1344(machine precision, then)2 1106 2 1296 4776 t 8 S f (e)3794 4776 w 8 CW f (is about)1 384 1 3877 4776 t 8 R f (10)4309 4776 w 5 S f (-)4397 4744 w 5 R f (8)4433 4744 w 8 CW f (, a relative)2 576 1 4464 4776 t (error for the above problem \(when ML=6\) of)7 2016 1 1296 4876 t 8 R f (3. 5)1 106 1 3360 4876 t 8 S f (\264)3472 4876 w 8 R f (10)3522 4876 w 5 S f (-)3610 4844 w 5 R f (1)3646 4844 w 8 CW f (is not surprising.)2 864 1 3725 4876 t 10 R f (Linear Algebra)1 606 1 360 7500 t (\320 34 \320)2 350 1 2705 7620 t (BASS)360 7740 w (-- --)1 5544 1 0 8030 t cleartomark showpage saveobj restore %%EndPage: 34 34 %%Trailer done %%Pages: 34 %%DocumentFonts: Courier Times-Bold Times-Italic Times-Roman Times-Roman Symbol