{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,19]],"date-time":"2026-09-19T19:24:53Z","timestamp":1789845893654,"version":"4.0.1"},"reference-count":52,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Matrix Anal. Appl."],"published-print":{"date-parts":[[2015,1]]},"abstract":"<jats:p>The $s$-step Lanczos method can achieve an $O(s)$ reduction in data movement over the classical Lanczos method for a fixed number of iterations, allowing the potential for significant speedups on modern computers. However, although the $s$-step Lanczos method is equivalent to the classical Lanczos method in exact arithmetic, it can behave quite differently in finite precision. Increased roundoff errors can manifest as a loss of accuracy or deterioration of convergence relative to the classical method, reducing the potential performance benefits of the $s$-step approach. In this paper, we present for the first time a complete rounding error analysis of the $s$-step Lanczos method. Our methodology is analogous to Paige's rounding error analysis for classical Lanczos [IMA J. Appl. Math., 18 (1976), pp. 341--349]. Our analysis gives upper bounds on the loss of normality of and orthogonality between the computed Lanczos vectors, as well as a recurrence for the loss of orthogonality. We further demonstrate that bounds on accuracy for the finite precision Lanczos method given by Paige [Linear Algebra Appl., 34 (1980), pp. 235--258] can be extended to the $s$-step Lanczos case assuming a bound on the maximum condition number of the precomputed $s$-step Krylov bases. Our results confirm that the conditioning of the precomputed Krylov bases plays a large role in determining finite precision behavior. In particular, if one can enforce that the condition numbers of the precomputed $s$-step Krylov bases are not too large in any iteration, then the finite precision behavior of the $s$-step Lanczos method will be similar to that of classical Lanczos.<\/jats:p>","DOI":"10.1137\/140990735","type":"journal-article","created":{"date-parts":[[2015,6,18]],"date-time":"2015-06-18T13:59:16Z","timestamp":1434635956000},"page":"793-819","source":"Crossref","is-referenced-by-count":13,"title":["Accuracy of the $s$-Step Lanczos Method for the Symmetric Eigenproblem in Finite Precision"],"prefix":"10.1137","volume":"36","author":[{"given":"Erin","family":"Carson","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"James W.","family":"Demmel","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2015,6,18]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1093\/imanum\/14.4.563"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1017\/S0962492914000038"},{"key":"atypb3","unstructured":"E. Carson and J. Demmel,\n                      Accuracy of the s-Step Lanczos Method for the Symmetric Eigenproblem\n                      , Technical report UCB\/EECS-2014-165, EECS Department, University of California, Berkeley, CA, 2014."},{"key":"atypb4","doi-asserted-by":"crossref","unstructured":"E. Carson and J. Demmel,\n                      Analysis of the Finite Precision s-Step Biconjugate Gradient Method\n                      , Technical report UCB\/EECS-2014-18, EECS Department, University of California, Berkeley, CA, 2014.","DOI":"10.21236\/ADA604544"},{"key":"atypb5","doi-asserted-by":"crossref","unstructured":"E. Carson and J. Demmel,\n                      Error Analysis of the s-Step Lanczos Method in Finite Precision\n                      , Technical report UCB\/EECS-2014-55, EECS Department, University of California, Berkeley, CA, 2014.","DOI":"10.21236\/ADA605332"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1137\/120893057"},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1137\/120881191"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1016\/0167-8191(89)90062-8"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1016\/0377-0427(89)90045-9"},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1016\/0167-8191(96)00022-1"},{"key":"atypb11","first-page":"505","author":"Cullum J.","year":"1974","journal-title":"IEEE"},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1016\/0167-8191(95)00057-7"},{"key":"atypb13","unstructured":"J. Demmel, M. Hoemmen, M. Mohiyuddin, and K. Yelick,\n                      Avoiding Communication in Computing Krylov Subspaces\n                      , Technical report UCB\/EECS-2007-123, EECS Department, University of California, Berkeley, CA, 2007."},{"key":"atypb14","first-page":"1","author":"Demmel J.","year":"2008","journal-title":"Proceedings of the International Symposium on Parallel and Distributed Processing, IEEE"},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1984.1676393"},{"key":"atypb16","unstructured":"G. Golub and C. Van Loan,\n                      Matrix Computations\n                      , 3rd ed., Johns Hopkins University Press, Baltimore, MD, 1996."},{"key":"atypb17","unstructured":"G. Golub and C. Van Loan,\n                      Matrix Computations\n                      , Vol. 3, Johns Hopkins University Press, Baltimore, MD, 2012."},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1016\/0024-3795(89)90285-1"},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1137\/0613011"},{"key":"atypb20","unstructured":"M. Gustafsson, J. Demmel, and S. Holmgren,\n                      Numerical evaluation of the communication-avoiding Lanczos algorithm\n                      , Technical report ISSN 1404-3203\/2012-001, Department of Information Technology, Uppsala University, Uppsala, Sweden, 2012."},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.1017\/S0962492900002737"},{"key":"atypb22","unstructured":"A. Hindmarsh and H. Walker,\n                      Note on a Householder implementation of the GMRES method\n                      , Technical report UCID-20899, Lawrence Livermore National Laboratory, Livermore, CA, 1986."},{"key":"atypb23","unstructured":"M. Hoemmen,\n                      Communication-avoiding Krylov Subspace Methods\n                      , Ph.D. thesis, EECS Department, University of California, Berkeley, CA, 2010."},{"key":"atypb24","doi-asserted-by":"publisher","DOI":"10.1080\/00207169208804107"},{"key":"atypb25","doi-asserted-by":"publisher","DOI":"10.2140\/pjm.1951.1.233"},{"key":"atypb26","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-8191(05)80065-1"},{"key":"atypb27","doi-asserted-by":"publisher","DOI":"10.1016\/0377-0427(92)90085-C"},{"key":"atypb28","doi-asserted-by":"publisher","DOI":"10.6028\/jres.045.026"},{"key":"atypb29","doi-asserted-by":"crossref","unstructured":"G. Meurant,\n                      The Lanczos and Conjugate Gradient Algorithms: From Theory to Finite Precision Computations\n                      , SIAM, Philadelphia, 2006.","DOI":"10.1137\/1.9780898718140"},{"key":"atypb30","doi-asserted-by":"publisher","DOI":"10.1017\/S096249290626001X"},{"key":"atypb31","unstructured":"M. Mohiyuddin,\n                      Tuning Hardware and Software for Multiprocessors\n                      , Ph.D. thesis, EECS Department, University of California, Berkeley, CA, 2012."},{"key":"atypb32","doi-asserted-by":"crossref","unstructured":"M. Mohiyuddin, M. Hoemmen, J. Demmel, and K. Yelick,\n                      Minimizing communication in sparse matrix solvers\n                      , in Proceedings of the Conference on High Performance Computing Networking, Storage and Analysis, ACM, New York, 2009.","DOI":"10.1145\/1654059.1654096"},{"key":"atypb33","unstructured":"C. Paige,\n                      The Computation of Eigenvalues and Eigenvectors of Very Large Sparse Matrices\n                      , Ph.D. thesis, London University, London, 1971."},{"key":"atypb34","doi-asserted-by":"publisher","DOI":"10.1093\/imamat\/10.3.373"},{"key":"atypb35","doi-asserted-by":"publisher","DOI":"10.1093\/imamat\/18.3.341"},{"key":"atypb36","doi-asserted-by":"publisher","DOI":"10.1016\/0024-3795(80)90167-6"},{"key":"atypb37","doi-asserted-by":"publisher","DOI":"10.1137\/090761343"},{"key":"atypb38","doi-asserted-by":"publisher","DOI":"10.1016\/j.laa.2013.05.009"},{"key":"atypb39","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-1979-0514820-3"},{"key":"atypb40","doi-asserted-by":"publisher","DOI":"10.1016\/j.apnum.2010.12.009"},{"key":"atypb41","doi-asserted-by":"publisher","DOI":"10.1007\/s10543-010-0294-0"},{"key":"atypb42","doi-asserted-by":"crossref","unstructured":"Y. Saad,\n                      Iterative Methods for Sparse Linear Systems\n                      , SIAM, Philadelphia, 2003.","DOI":"10.1137\/1.9780898718003"},{"key":"atypb43","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-1984-0725988-X"},{"key":"atypb44","doi-asserted-by":"publisher","DOI":"10.1016\/0024-3795(68)90005-0"},{"key":"atypb45","unstructured":"S. Toledo,\n                      Quantitative Performance Modeling of Scientific Computations and Creating Locality in Numerical Algorithms\n                      , Ph.D. thesis, MIT, Cambridge, MA, 1995."},{"key":"atypb46","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827599353865"},{"key":"atypb47","unstructured":"J. Van Rosendale,\n                      Minimizing Inner Product Data Dependencies in Conjugate Gradient Iteration\n                      , Technical report 172178, ICASE-NASA, 1983."},{"key":"atypb48","doi-asserted-by":"publisher","DOI":"10.1137\/0909010"},{"key":"atypb49","unstructured":"J. Wilkinson,\n                      The Algebraic Eigenvalue Problem\n                      , Vol. 87, Oxford University Press, Oxford, 1965."},{"key":"atypb50","doi-asserted-by":"crossref","unstructured":"S. Williams, M. Lijewski, A. Almgren, B. Van Straalen, E. Carson, N. Knight, and J. Demmel,\n                      s-step Krylov subspace methods as bottom solvers for geometric multigrid\n                      , in Proceedings of the International Symposium on Parallel and Distributed Processing, IEEE, 2014.","DOI":"10.1109\/IPDPS.2014.119"},{"key":"atypb51","doi-asserted-by":"publisher","DOI":"10.1137\/040608908"},{"key":"atypb52","unstructured":"J. Zemke,\n                      Krylov Subspace Methods in Finite Precision: A Unified Approach\n                      , Ph.D. thesis, Technische Universit\u00e4t Hamburg-Harburg, Hamburg, Germany, 2003."}],"container-title":["SIAM Journal on Matrix Analysis and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/140990735","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T17:51:17Z","timestamp":1787334677000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/140990735"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,1]]},"references-count":52,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2015,1]]}},"alternative-id":["10.1137\/140990735"],"URL":"https:\/\/doi.org\/10.1137\/140990735","relation":{},"ISSN":["0895-4798","1095-7162"],"issn-type":[{"value":"0895-4798","type":"print"},{"value":"1095-7162","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,1]]}}}