Bibliography of Accuracy and Stability of Numerical Algorithms, Second Edition, SIAM, 2002 Nicholas J. Higham⁄ August 15, 2002 Bib This is the bibliography of the book [616], available as a TEX databas athttp://www.ma.man.ac.uk/~higham/asna/acc-stab-num-alg-2ed.bib References [1] Jan Ole Aasen. On the reduction of a symmetric matrix to tridiagonal form. BIT, 11:233{242, 1971. [2] Nabih N. Abdelmalek. Round ofi error analysis for Gram-Schmidt method and solution of linear least squares problems. BIT, 11:345{ 368, 1971. [3] ACM Turing Award Lectures: The First Twenty Years, 1966{1985. Addison-Wesley, Reading, MA, USA, 1987. ISBN 0-201-54885-2. xviii+483 pp. [4] Forman S. Acton. Numerical Methods That Work. Harper and Row, New York, 1970. ISBN 0-88385-450-3. xviii+541 pp. Reprinted by Mathematical Association of America, Washington, D.C., with new preface and additional problems, 1990. ⁄ Department of Mathematics, University of Manchester, Manchester, M13 9PL, Eng- land ([email protected], http://www.ma.man.ac.uk/~higham/). 1 [5] Forman S. Acton. Real Computing Made Real: Preventing Errors in Scientiflc and Engineering Calculations. Princeton University Press, Princeton, NJ, USA, 1996. ISBN 0-691-03663-2. xv+259 pp. [6] Duane A. Adams. A stopping criterion for polynomial root flnding. Comm. ACM, 10:655{658, 1967. [7] Vijay B. Aggarwal and James W. Burgmeier. A round-ofi error model with applications to arithmetic expressions. SIAM J. Comput., 8(1): 60{72, 1979. [8] Alan A. Ahac, John J. Buoni, and D. D. Olesky. Stable LU factor- ization of H-matrices. Linear Algebra Appl., 99:97{110, 1988. [9] J. H. Ahlberg and E. N. Nilson. Convergence properties of the spline flt. J. Soc. Indust. Appl. Math., 11(1):95{104, 1963. [10] Paul Halmos by parts (interviews by Donald J. Albers). In John H. EwingandF.W.Gehring,editors, Paul Halmos: Celebrating 50 Years of Mathematics, pages 3{32. Springer-Verlag, Berlin, 1991. [11] Go˜ltz Alefeld and Ju˜rgen Herzberger. Introduction to Interval Com- putations. Academic Press, New York, 1983. ISBN 0-12-049820-0. xviii+333 pp. [12] M. Almacany, C. B. Dunham, and J. Williams. Discrete Chebyshev approximation by interpolating rationals. IMA J. Numer. Anal., 4: 467{477, 1984. [13] P. Alonso, M. Gasca, and J. M. Pen~a. Backward error analysis of Neville elimination. Appl. Numer. Math., 23:193{204, 1997. [14] B. Alpert, G. Beylkin, R. Coifman, and V. Rokhlin. Wavelet-like bases for the fast solution of second-kind integral equations. SIAM J. Sci. Comput., 14(1):159{184, 1993. [15] H. Alt and J. van Leeuwen. The complexity of basic complex opera- tions. Computing, 27:205{215, 1981. [16] Steven C. Althoen and Renate Mclaughlin. Gauss-Jordan reduction: A brief history. Amer. Math. Monthly, 94(2):130{142, 1987. 2 [17] Fernando L. Alvarado, Alex Pothen, and Robert S. Schreiber. Highly parallelsparsetriangularsolution. InJ.AlanGeorge, JohnR.Gilbert, andJosephW.H.Liu,editors, Graph Theory and Sparse Matrix Com- putations, volume 56 of IMA Volumes in Mathematics and Its Appli- cations, pages 141{158. Springer-Verlag, New York, 1993. [18] Pierluigi Amodio and Francesca Mazzia. Backward error analysis of cyclic reduction for the solution of tridiagonal systems. Math. Comp., 62(206):601{617, 1994. [19] AndrewA.AndaandHaesunPark. Fastplanerotationswithdynamic scaling. SIAM J. Matrix Anal. Appl., 15(1):162{174, 1994. [20] E. Anderson, Z. Bai, C. H. Bischof, S. Blackford, J. W. Demmel, J. J. Dongarra, J. J. Du Croz, A. Greenbaum, S. J. Hammarling, A. McKenney, and D. C. Sorensen. LAPACK Users’ Guide. Society forIndustrialandAppliedMathematics,Philadelphia,PA,USA,third edition, 1999. ISBN 0-89871-447-8. xxvi+407 pp. [21] E. Anderson, Z. Bai, and J. Dongarra. Generalized QR factorization and its applications. Linear Algebra Appl., 162{164:243{271, 1992. [22] Edward Anderson. Robust triangular solves for use in condition esti- mation. Technical Report CS-91-142, Department of Computer Sci- ence, University of Tennessee, Knoxville, TN, USA, August 1991. 35 pp. LAPACK Working Note 36. [23] I. J. Anderson. A distillation algorithm for (cid:176)oating-point summation. SIAM J. Sci. Comput., 20(5):1797{1806, 1999. [24] T. W. Anderson. The Statistical Analysis of Time Series. Wiley, New York, 1971. ISBN 0-471-02900-9. xiv+704 pp. [25] T. W. Anderson, I. Olkin, and L. G. Underhill. Generation of random orthogonal matrices. SIAM J. Sci. Statist. Comput., 8(4):625{629, 1987. [26] T. Ando. Totally positive matrices. Linear Algebra Appl., 90:165{219, 1987. 3 [27] Alan L. Andrew. Eigenvalues and singular values of certain random matrices. J. Comput. Appl. Math., 30:165{171, 1990. [28] Anonymous. Le Commandant Cholesky. Bulletin G¶eod¶esique, pages 159{161, 1922. Translation by Richard W. Cottle (\Major Cholesky") appears in [810, Appendix] and in NA Digest, Volume 90, Issue 7, 1990. [29] Anonymous. James Wilkinson (1919{1986). Annals of the History of Computing, 9(2):205{210, 1987. From the introduction: \A series of lightly edited extracts from messages that were sent over various computer networks during the period October 5, 1986{February 13, 1987". [30] M. Arioli, J. W. Demmel, and I. S. Dufi. Solving sparse linear systems with sparse backward error. SIAM J. Matrix Anal. Appl., 10(2):165{ 190, 1989. [31] M. Arioli, I. S. Dufi, and P. P. M. de Rijk. On the augmented system approach to sparse least-squares problems. Numer. Math., 55:667{ 684, 1989. [32] M. Arioli and A. Laratta. Error analysis of an algorithm for solving an underdetermined linear system. Numer. Math., 46:255{268, 1985. [33] M. Arioli and A. Laratta. Error analysis of algorithms for computing the projection of a point onto a linear manifold. Linear Algebra Appl., 82:1{26, 1986. [34] MarioArioli. Astoppingcriterionfortheconjugategradientalgorithm inaflniteelementmethodframework. TechnicalReport1179, Istituto di Analisi Numerica - C.N.R., Pavia, Italy, 2000. 12 pp. [35] Mario Arioli, Iain S. Dufi, and Daniel Ruiz. Stopping criteria for iterative solvers. SIAM J. Matrix Anal. Appl., 13(1):138{144, 1992. [36] Mario Arioli and Francesco Romani. Stability, convergence, and con- ditioning of stationary iterative methods of the form x(i+1) = Px(i)+q for the solution of linear systems. IMA J. Numer. Anal., 12:21{30, 1992. 4 [37] William F. Arnold and Alan J. Laub. Generalized eigenproblem algo- rithms and software for algebraic Riccati equations. Proc. IEEE, 72 (12):1746{1754, 1984. [38] Cleve Ashcraft, Roger G. Grimes, and John G. Lewis. Accurate sym- metric indeflnite linear equation solvers. SIAM J. Matrix Anal. Appl., 20(2):513{561, 1998. [39] R. L. Ashenhurst and N. Metropolis. Error estimation in computer calculation. Amer. Math. Monthly, 72(2):47{58, 1965. [40] Edgar Asplund. Inverses of matrices fa g which satisfy a = 0 for ij ij j > i+p. Math. Scand., 7:57{60, 1959. [41] John V. Atanasofi. Computing machine for the solution of large sys- tems of linear algebraic equations. Unpublished manuscript, Iowa State College, Ames, IA, USA, August 1940. Reprinted in [978, pp. 315{335]. [42] Owe Axelsson. Iterative Solution Methods. Cambridge University Press, 1994. ISBN 0-521-44524-8. xiii+654 pp. [43] Ivo Babu•ska. Numerical stability in mathematical analysis. In Proc. IFIP Congress, Information Processing 68, pages 11{23. North-Hol- land, Amsterdam, The Netherlands, 1969. [44] Zhaojun Bai, David Day, James Demmel, and Jack Dongarra. A test matrix collection for non-Hermitian eigenvalue problems (release 1.0). Technical Report CS-97-355, Department of Computer Science, University of Tennessee, Knoxville, TN, USA, March 1997. 45 pp. LAPACK Working Note 123. [45] Zhaojun Bai and James W. Demmel. Computing the generalized singular value decomposition. SIAM J. Sci. Comput., 14(6):1464{ 1486, 1993. [46] Zhaojun Bai and James W. Demmel. On swapping diagonal blocks in real Schur form. Linear Algebra Appl., 186:73{95, 1993. [47] Zhaojun Bai, James W. Demmel, Jack J. Dongarra, Antoine Petitet, Howard Robinson, and K. Stanley. The spectral decomposition of 5 nonsymmetric matrices on distributed memory parallel computers. SIAM J. Sci. Comput., 18(5):1446{1461, 1997. [48] Zhaojun Bai, James W. Demmel, and Ming Gu. Inverse free parallel spectral divide and conquer algorithms for nonsymmetric eigenprob- lems. Numer. Math., 76:279{308, 1997. [49] ZhaojunBai, JamesW.Demmel, andAlanMcKenney. Oncomputing condition numbers for the nonsymmetric eigenproblem. ACM Trans. Math. Software, 19(2):202{223, 1993. [50] D. H. Bailey and H. R. P. Ferguson. A Strassen{Newton algorithm for high-speed parallelizable matrix inversion. In Proceedings of Su- percomputing ’88, pages 419{424. IEEE Computer Society Press, New York, 1988. [51] David H. Bailey. The computation of … to 29,360,000 decimal digits using Borweins’ quartically convergent algorithm. Math. Comp., 50 (181):283{296, 1988. [52] David H. Bailey. Extra high speed matrix multiplication on the Cray- 2. SIAM J. Sci. Statist. Comput., 9(3):603{607, 1988. [53] David H. Bailey. Algorithm 719: Multiprecision translation and exe- cution of FORTRAN programs. ACM Trans. Math. Software, 19(3): 288{319, 1993. [54] David H. Bailey. A Fortran 90-based multiprecision system. ACM Trans. Math. Software, 21(4):379{387, 1995. [55] DavidH.Bailey, RobertKrasny, andRichardPelz. Multipleprecision, multiple processor vortex sheet roll-up computation. In Richard F. Sincovec, David E. Keyes, Michael R. Leuze, Linda R. Petzold, and Daniel A. Reed, editors, Proceedings of the Sixth SIAM Conference on Parallel Processing for Scientiflc Computing, Volume I, pages 52{56. Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 1993. [56] DavidH.Bailey, KingLee, andHorstD.Simon. UsingStrassen’salgo- rithm to accelerate the solution of linear systems. J. Supercomputing, 4:357{371, 1991. 6 [57] David H. Bailey, Horst D. Simon, John T. Barton, and Martin J. Fouts. Floating point arithmetic in future supercomputers. Internat. J. Supercomputer Appl., 3(3):86{90, 1989. [58] J. K. Baksalary and R. Kala. The matrix equation AX ¡YB = C. Linear Algebra Appl., 25:41{43, 1979. [59] J.K.Baksalary andR.Kala. ThematrixequationAXB+CYD = E. Linear Algebra Appl., 30:141{147, 1980. [60] Susanne M. Balle, Per Christian Hansen, and Nicholas J. Higham. A Strassen-typematrixinversionalgorithmfortheConnectionMachine. Technical Report CNC/1993/028, Centre for Novel Computing, Uni- versity of Manchester, Manchester, England, October 1993. 29 pp. [61] C. Ballester and V. Pereyra. On the construction of discrete approx- imations to linear difierential expressions. Math. Comp., 21:297{302, 1967. [62] Randolph E. Bank and Donald J. Rose. Marching algorithms for ellip- tic boundary value problems. I: The constant coe–cient case. SIAM J. Numer. Anal., 14(5):792{829, 1977. [63] Yonathan Bard. Nonlinear Parameter Estimation. Academic Press, New York, 1974. [64] V. Bargmann, D. Montgomery, and J. von Neumann. Solution of linear systems of high order. Report prepared for Navy Bureau of Ordnance, 1946. Reprinted in [1135, pp. 421{477]. [65] V. A. Barker, L. S. Blackford, J. J. Dongarra, J. J. Du Croz, S. J. Hammarling, M. Marinova, J. Wa¶sniewski, and P. Yalamov. LA- PACK95 Users’ Guide. Society for Industrial and Applied Mathe- matics, Philadelphia, PA, USA, 2001. ISBN 0-89871-504-0. xviii+258 pp. [66] J. L. Barlow, N. K. Nichols, and R. J. Plemmons. Iterative methods for equality-constrained least squares problems. SIAM J. Sci. Statist. Comput., 9(5):892{906, 1988. 7 [67] Jesse L. Barlow. On the distribution of accumulated roundofi error in (cid:176)oating point arithmetic. In Proc. 5th IEEE Symposium on Computer Arithmetic, Ann Arbor, Michigan, pages 100{105, 1981. [68] Jesse L. Barlow. Probabilistic Error Analysis of Floating Point and CRD Arithmetics. PhD thesis, Northwestern University, Evanston, IL, USA, June 1981. [69] Jesse L. Barlow. A note on monitoring the stability of triangular decomposition of sparse matrices. SIAM J. Sci. Statist. Comput., 7 (1):166{168, 1986. [70] Jesse L. Barlow. Error analysis and implementation aspects of de- ferred correction for equality constrained least squares problems. SIAM J. Numer. Anal., 25(6):1340{1358, 1988. [71] Jesse L. Barlow. Error analysis of a pairwise summation algorithm to compute the sample variance. Numer. Math., 58:583{590, 1991. [72] Jesse L. Barlow and E. H. Bareiss. On roundofi error distributions in (cid:176)oating point and logarithmic arithmetic. Computing, 34:325{347, 1985. [73] JesseL.BarlowandE.H.Bareiss. ProbabilisticerroranalysisofGaus- sian elimination in (cid:176)oating point and logarithmic arithmetic. Com- puting, 34:349{364, 1985. [74] Jesse L. Barlow and Ilse C. F. Ipsen. Scaled Givens rotations for the solution of linear least squares problems on systolic arrays. SIAM J. Sci. Statist. Comput., 8(5):716{733, 1987. [75] Jesse L. Barlow and Udaya B. Vemulapati. A note on deferred correc- tion for equality constrained least squares problems. SIAM J. Numer. Anal., 29(1):249{256, 1992. [76] Jesse L. Barlow and Udaya B. Vemulapati. Rank detection methods for sparse matrices. SIAM J. Matrix Anal. Appl., 13(4):1279{1297, 1992. [77] Jesse L. Barlow and Hongyuan Zha. Growth in Gaussian elimination, orthogonal matrices, and the 2-norm. SIAM J. Matrix Anal. Appl., 19(3):807{815, 1998. 8 [78] S. Barnett and C. Storey. Some applications of the Lyapunov matrix equation. J. Inst. Maths. Applics., 4:33{42, 1968. [79] Geofi Barrett. Formal methods applied to a (cid:176)oating-point number system. IEEE Trans. Software Engrg., 15(5):611{621, 1989. [80] Richard Barrett, Michael Berry, Tony F. Chan, James Demmel, June Donato, Jack Dongarra, Victor Eijkhout, Roldan Pozo, Charles Romine, andHenkvanderVorst. Templates for the Solution of Linear Systems: Building Blocks for Iterative Methods. Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 1994. ISBN 0- 89871-328-5. xiii+112 pp. [81] Anders Barrlund. Perturbation bounds for the LDLH and LU de- compositions. BIT, 31:358{363, 1991. [82] Anders Barrlund. Perturbation bounds for the generalized QR fac- torization. Linear Algebra Appl., 207:251{271, 1994. [83] D.W.BarronandH.P.F.Swinnerton-Dyer. Solutionofsimultaneous linear equations using a magnetic-tape store. Comput. J., 3(1):28{33, 1960. [84] R. H. Bartels and G. W. Stewart. Algorithm 432: Solution of the matrix equation AX +XB = C. Comm. ACM, 15(9):820{826, 1972. [85] Sven G. Bartels. Two topics in matrix analysis: Structured sensi- tivity for Vandermonde-like systems and a subgradient method for matrix norm estimation. M.Sc. Thesis, Department of Mathemat- ics and Computer Science, University of Dundee, Dundee, Scotland, September 1991. [86] Sven G. Bartels and Desmond J. Higham. The structured sensitivity of Vandermonde-like systems. Numer. Math., 62:17{33, 1992. [87] Victor Barwell and Alan George. A comparison of algorithms for solving symmetric indeflnite systems of linear equations. ACM Trans. Math. Software, 2(3):242{251, 1976. [88] Basic Linear Algebra Subprograms Technical (BLAST) Forum Stan- dard. Int. J. High Performance Applications and Supercomputing, 2002. To appear. 9 [89] F. L. Bauer. Optimal scaling of matrices and the importance of the minimal condition. In Cicely M. Popplewell, editor, Proc. IFIP Congress 1962, Information Processing 62, pages 198{201. North-Hol- land, Amsterdam, The Netherlands, 1963. [90] F. L. Bauer. Optimally scaled matrices. Numer. Math., 5:73{87, 1963. [91] F. L. Bauer. Genauigkeitsfragen bei der Lo˜sung linearer Gle- ichungssysteme. Z. Angew. Math. Mech., 46(7):409{421, 1966. [92] F. L. Bauer. Remarks on optimally scaled matrices. Numer. Math., 13:1{3, 1969. [93] F. L. Bauer. Computational graphs and rounding errors. SIAM J. Numer. Anal., 11(1):87{96, 1974. [94] F. L. Bauer and C. Reinsch. Inversion of positive deflnite matrices by theGauss-Jordanmethod. InJ.H.WilkinsonandC.Reinsch, editors, Linear Algebra, volume II of Handbook for Automatic Computation, pages 45{49. Springer-Verlag, Berlin, 1971. Contribution I/3. [95] F. L. Bauer, J. Stoer, and C. Witzgall. Absolute and monotonic norms. Numer. Math., 3:257{264, 1961. [96] Richard M. Beam and Robert F. Warming. The asymptotic spectra of banded Toeplitz and quasi-Toeplitz matrices. SIAM J. Sci. Comput., 14(4):971{1006, 1993. [97] Albert E. Beaton, Donald B. Rubin, and John L. Barone. The ac- ceptability of regression solutions: Another look at computational accuracy. J. Amer. Statist. Assoc., 71(353):158{168, 1976. [98] Bernhard Beckermann. The condition number of real Vandermonde, Krylov and positive deflnite Hankel matrices. Numer. Math., 85:553{ 577, 2000. [99] C. Gordon Bell and Allen Newell. Computer Structures: Readings and Examples. McGraw-Hill, New York, 1971. [100] E. T. Bell. Review of \Contributions to the History of Determinants, 1900-1920", by Sir Thomas Muir. Amer. Math. Monthly, 38:161{164, 1931. 10