{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,6]],"date-time":"2022-04-06T00:58:10Z","timestamp":1649206690269},"reference-count":4,"publisher":"Association for Computing Machinery (ACM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Commun. ACM"],"published-print":{"date-parts":[[1974,1]]},"abstract":"\n The solution of linear systems having real, symmetric, diagonally dominant, tridiagonal coefficient matrices with constant diagonals is considered. It is proved that the diagonals of the\n LU<\/jats:italic>\n decomposition of the coefficient matrix rapidly converge to full floating-point precision. It is also proved that the computed\n LU<\/jats:italic>\n decomposition converges when floating-point arithmetic is used and that the limits of the\n LU<\/jats:italic>\n diagonals using floating point are roughly within machine precision of the limits using real arithmetic. This fact is exploited to reduce the number of floating-point operations required to solve a linear system from 8\n n<\/jats:italic>\n - 7 to 5\n n<\/jats:italic>\n + 2\n k<\/jats:italic>\n - 3, where\n k<\/jats:italic>\n is much less than\n n<\/jats:italic>\n , the order of the matrix. If the elements of the subdiagnals and superdiagonals are 1, then only 4\n n<\/jats:italic>\n + 2\n k<\/jats:italic>\n - 3 operations are needed. The entire\n LU<\/jats:italic>\n decomposition takes\n k<\/jats:italic>\n words of storage, and considerable savings in array subscripting are achieved. Upper and lower bounds on\n k<\/jats:italic>\n are obtained in terms of the ratio of the coefficient matrix diagonal constants and parameters of the floating-point number system.\n <\/jats:p>\n Various generalizations of these results are discussed.<\/jats:p>","DOI":"10.1145\/360767.360777","type":"journal-article","created":{"date-parts":[[2002,7,27]],"date-time":"2002-07-27T11:34:59Z","timestamp":1027769699000},"page":"14-17","source":"Crossref","is-referenced-by-count":24,"title":["A fast method for solving a class of tridiagonal linear systems"],"prefix":"10.1145","volume":"17","author":[{"given":"Michael A.","family":"Malcolm","sequence":"first","affiliation":[{"name":"Univ. of Waterloo, Waterloo, Ont., Canada"}]},{"given":"John","family":"Palmer","sequence":"additional","affiliation":[{"name":"Stanford Univ., Stanford, CA"}]}],"member":"320","reference":[{"key":"e_1_2_1_1_2","first-page":"285","article-title":"Ein direktes Iterationsverfahren zur Hurwitz-Zerlegung eines Polynoms. Archly der Elektrischen Uebertragung","volume":"9","author":"Bauer Friedrich L","year":"1955","journal-title":"Wiesbaden"},{"key":"e_1_2_1_2_2","unstructured":"Forsythe G.E. and Moler C.B. Computer Solution of Linear Algebraic Equations Prentice-Hall Englewood Cliffs N.J. 1967. Forsythe G.E. and Moler C.B. Computer Solution of Linear Algebraic Equations Prentice-Hall Englewood Cliffs N.J. 1967."},{"key":"e_1_2_1_3_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01386320"},{"key":"e_1_2_1_4_2","unstructured":"Wilkinson J.H. Rounding Errors in Algebraic Processes. Prentice-Hall Englewood Cliffs N.J. 1963. Wilkinson J.H. Rounding Errors in Algebraic Processes. Prentice-Hall Englewood Cliffs N.J. 1963."}],"container-title":["Communications of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/360767.360777","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,3,3]],"date-time":"2021-03-03T11:44:27Z","timestamp":1614771867000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/360767.360777"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1974,1]]},"references-count":4,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1974,1]]}},"alternative-id":["10.1145\/360767.360777"],"URL":"http:\/\/dx.doi.org\/10.1145\/360767.360777","relation":{},"ISSN":["0001-0782","1557-7317"],"issn-type":[{"value":"0001-0782","type":"print"},{"value":"1557-7317","type":"electronic"}],"subject":["General Computer Science"],"published":{"date-parts":[[1974,1]]}}}