{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T07:38:51Z","timestamp":1740123531647,"version":"3.37.3"},"reference-count":39,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2022,2,20]],"date-time":"2022-02-20T00:00:00Z","timestamp":1645315200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,2,20]],"date-time":"2022-02-20T00:00:00Z","timestamp":1645315200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100017142","name":"Gruppo Nazionale per il Calcolo Scientifico","doi-asserted-by":"crossref","award":["GNCS"],"award-info":[{"award-number":["GNCS"]}],"id":[{"id":"10.13039\/100017142","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Sci Comput"],"published-print":{"date-parts":[[2022,4]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We present a class of fast subspace algorithms based on orthogonal iterations for structured matrices\/pencils that can be expressed as small rank perturbations of unitary matrices. The representation of the matrix by means of a new data-sparse factorization\u2014named LFR factorization\u2014using orthogonal Hessenberg matrices is at the core of these algorithms. The factorization can be computed at the cost of<jats:inline-formula><jats:alternatives><jats:tex-math>$$O(n k^2)$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mrow><mml:mi>O<\/mml:mi><mml:mo>(<\/mml:mo><mml:mi>n<\/mml:mi><mml:msup><mml:mi>k<\/mml:mi><mml:mn>2<\/mml:mn><\/mml:msup><mml:mo>)<\/mml:mo><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>arithmetic operations, where<jats:italic>n<\/jats:italic>and<jats:italic>k<\/jats:italic>are the sizes of the matrix and the small rank perturbation, respectively. At the same cost from the LFR format we can easily obtain suitable QR and RQ factorizations where the orthogonal factor Q is a product of orthogonal Hessenberg matrices and the upper triangular factor R is again given into the LFR format. The orthogonal iteration reduces to a hopping game where Givens plane rotations are moved from one side to the other side of these two factors. The resulting new algorithms approximate an invariant subspace of size<jats:italic>s<\/jats:italic>associated with a set of<jats:italic>s<\/jats:italic>leading or trailing eigenvalues using only<jats:italic>O<\/jats:italic>(<jats:italic>nks<\/jats:italic>) operations per iteration. The number of iterations required to reach an invariant subspace depends linearly on the ratio<jats:inline-formula><jats:alternatives><jats:tex-math>$$|\\lambda _{s+1}|\/|\\lambda _s|$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mrow><mml:mrow><mml:mo>|<\/mml:mo><\/mml:mrow><mml:msub><mml:mi>\u03bb<\/mml:mi><mml:mrow><mml:mi>s<\/mml:mi><mml:mo>+<\/mml:mo><mml:mn>1<\/mml:mn><\/mml:mrow><\/mml:msub><mml:mrow><mml:mo>|<\/mml:mo><mml:mo>\/<\/mml:mo><mml:mo>|<\/mml:mo><\/mml:mrow><mml:msub><mml:mi>\u03bb<\/mml:mi><mml:mi>s<\/mml:mi><\/mml:msub><mml:mrow><mml:mo>|<\/mml:mo><\/mml:mrow><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>. Numerical experiments confirm the effectiveness of our adaptations.<\/jats:p>","DOI":"10.1007\/s10915-022-01777-z","type":"journal-article","created":{"date-parts":[[2022,2,20]],"date-time":"2022-02-20T07:02:34Z","timestamp":1645340554000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Orthogonal Iterations on Companion-Like Pencils"],"prefix":"10.1007","volume":"91","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-6509-1140","authenticated-orcid":false,"given":"R.","family":"Bevilacqua","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5651-9368","authenticated-orcid":false,"given":"G. M.","family":"Del Corso","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8000-4906","authenticated-orcid":false,"given":"L.","family":"Gemignani","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,2,20]]},"reference":[{"issue":"1","key":"1777_CR1","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1093\/imanum\/drm051","volume":"29","author":"A Amiraslani","year":"2009","unstructured":"Amiraslani, A., Corless, R.M., Lancaster, P.: Linearization of matrix polynomials expressed in polynomial bases. IMA J. Numer. Anal. 29(1), 141\u2013157 (2009)","journal-title":"IMA J. Numer. Anal."},{"key":"1777_CR2","unstructured":"Arbenz, P.: Lecture Notes on Solving Large Scale Eigenvalue Problems (2016)"},{"key":"1777_CR3","doi-asserted-by":"publisher","first-page":"52","DOI":"10.14495\/jsiaml.1.52","volume":"1","author":"J Asakura","year":"2009","unstructured":"Asakura, J., Sakurai, T., Tadano, H., Ikegami, T., Kimura, K.: A numerical method for nonlinear eigenvalue problems using contour integrals. JSIAM Lett. 1, 52\u201355 (2009)","journal-title":"JSIAM Lett."},{"issue":"3","key":"1777_CR4","doi-asserted-by":"publisher","first-page":"942","DOI":"10.1137\/140983434","volume":"36","author":"JL Aurentz","year":"2015","unstructured":"Aurentz, J.L., Mach, T., Vandebril, R., Watkins, D.S.: Fast and backward stable computation of roots of polynomials. SIAM J. Matrix Anal. Appl. 36(3), 942\u2013973 (2015)","journal-title":"SIAM J. Matrix Anal. Appl."},{"key":"1777_CR5","doi-asserted-by":"crossref","unstructured":"Aurentz, J., Mach, T., Robol, L., Vandebril, R., Watkins, D.S.: Core-chasing Algorithms for the Eigenvalue Problem. Fundamentals of Algorithms. SIAM (2018)","DOI":"10.1137\/1.9781611975345"},{"issue":"315","key":"1777_CR6","doi-asserted-by":"publisher","first-page":"313","DOI":"10.1090\/mcom\/3338","volume":"88","author":"J Aurentz","year":"2019","unstructured":"Aurentz, J., Mach, T., Robol, L., Vandebril, R., Watkins, D.S.: Fast and backward stable computation of eigenvalues and eigenvectors of matrix polynomials. Math. Comput. 88(315), 313\u2013347 (2019)","journal-title":"Math. Comput."},{"issue":"2","key":"1777_CR7","doi-asserted-by":"publisher","first-page":"241","DOI":"10.3934\/mbe.2012.9.241","volume":"9","author":"MV Barbarossa","year":"2012","unstructured":"Barbarossa, M.V., Kuttler, C., Zinsl, J.: Delay equations modeling the effects of phase-specific drugs and immunotherapy on proliferating tumor cells. Math. Biosci. Eng. 9(2), 241\u2013257 (2012)","journal-title":"Math. Biosci. Eng."},{"key":"1777_CR8","doi-asserted-by":"crossref","unstructured":"Betcke, T.: Optimal scaling of generalized and polynomial eigenvalue problems. SIAM J. Matrix Anal. Appl. 30(4), 1320\u20131338 (2008\/09)","DOI":"10.1137\/070704769"},{"key":"1777_CR9","doi-asserted-by":"crossref","unstructured":"Betcke, T., Higham, N.J., Mehrmann, V., Schr\u00f6der, C., Tisseur, F.: NLEVP: a collection of nonlinear eigenvalue problems. ACM Trans. Math. Softw. 39(2), 7:1\u20137:28 (2013)","DOI":"10.1145\/2427023.2427024"},{"issue":"2","key":"1777_CR10","first-page":"57","volume":"76","author":"R Bevilacqua","year":"2018","unstructured":"Bevilacqua, R., Del Corso, G.M., Gemignani, L.: A QR based approach for the nonlinear eigenvalue problem. Rendcionti Sem. Mat. Univ. Pol. Torino 76(2), 57\u201367 (2018)","journal-title":"Rendcionti Sem. Mat. Univ. Pol. Torino"},{"issue":"3","key":"1777_CR11","doi-asserted-by":"publisher","first-page":"984","DOI":"10.1137\/19M1280363","volume":"41","author":"R Bevilacqua","year":"2020","unstructured":"Bevilacqua, R., Del Corso, G.M., Gemignani, L.: Efficient reduction of compressed unitary plus low rank matrices to Hessenberg form. SIAM J. Matrix Anal. Appl. 41(3), 984\u20131003 (2020)","journal-title":"SIAM J. Matrix Anal. Appl."},{"issue":"1","key":"1777_CR12","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1007\/s00211-019-01080-4","volume":"144","author":"R Bevilacqua","year":"2020","unstructured":"Bevilacqua, R., Del Corso, G.M., Gemignani, L.: Fast QR iterations for unitary plus low rank matrices. Numer. Math. 144(1), 23\u201353 (2020)","journal-title":"Numer. Math."},{"issue":"10","key":"1777_CR13","doi-asserted-by":"publisher","first-page":"3839","DOI":"10.1016\/j.laa.2011.03.030","volume":"436","author":"WJ Beyn","year":"2012","unstructured":"Beyn, W.J.: An integral method for solving nonlinear eigenvalue problems. Linear Algebra Appl. 436(10), 3839\u20133863 (2012)","journal-title":"Linear Algebra Appl."},{"key":"1777_CR14","doi-asserted-by":"crossref","unstructured":"Bini, D.A., Latouche, G. Meini, B.: Numerical Methods for Structured Markov Chains. Numerical Mathematics and Scientific Computation. Oxford University Press, New York (2005). (Oxford Science Publications)","DOI":"10.1093\/acprof:oso\/9780198527688.001.0001"},{"key":"1777_CR15","doi-asserted-by":"publisher","first-page":"275","DOI":"10.1016\/j.laa.2015.07.017","volume":"502","author":"DA Bini","year":"2016","unstructured":"Bini, D.A., Robol, L.: On a class of matrix pencils and $$\\ell $$-ifications equivalent to a given matrix polynomial. Linear Algebra Appl. 502, 275\u2013298 (2016)","journal-title":"Linear Algebra Appl."},{"key":"1777_CR16","doi-asserted-by":"crossref","unstructured":"Bini, D.A., Latouche, G., Meini, B.: A family of fast fixed point iterations for M\/G\/1-type Markov chains. IMA J. Numer. Anal (2021)","DOI":"10.1093\/imanum\/drab009"},{"key":"1777_CR17","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1016\/S0024-3795(02)00457-3","volume":"362","author":"MJ Cantero","year":"2003","unstructured":"Cantero, M.J., Moral, L., Vel\u00e1zquez, L.: Five-diagonal matrices and zeros of orthogonal polynomials on the unit circle. Linear Algebra Appl. 362, 29\u201356 (2003)","journal-title":"Linear Algebra Appl."},{"issue":"4","key":"1777_CR18","doi-asserted-by":"publisher","first-page":"357","DOI":"10.21136\/AM.2017.0016-17","volume":"62","author":"H Chen","year":"2017","unstructured":"Chen, H., Imakura, A., Sakurai, T.: Improving backward stability of Sakurai\u2013Sugiura method with balancing technique in polynomial eigenvalue problem. Appl. Math. 62(4), 357\u2013375 (2017)","journal-title":"Appl. Math."},{"key":"1777_CR19","doi-asserted-by":"crossref","unstructured":"Drma\u010d, Z., Glibi\u0107, I.\u0160.: An algorithm for the complete solution of the quartic eigenvalue problem (2021)","DOI":"10.1145\/3494528"},{"issue":"4","key":"1777_CR20","doi-asserted-by":"publisher","first-page":"933","DOI":"10.1007\/s10543-012-0381-5","volume":"52","author":"C Effenberger","year":"2012","unstructured":"Effenberger, C., Kressner, D.: Chebyshev interpolation for nonlinear eigenvalue problems. BIT 52(4), 933\u2013951 (2012)","journal-title":"BIT"},{"issue":"10","key":"1777_CR21","doi-asserted-by":"publisher","first-page":"1889","DOI":"10.1142\/S0218127498001595","volume":"8","author":"K Engelborghs","year":"1998","unstructured":"Engelborghs, K., Roose, D., Luzyanina, T.: Bifurcation analysis of periodic solutions of neutral functional-differential equations: a case study. Int. J. Bifur. Chaos Appl. Sci. Eng. 8(10), 1889\u20131905 (1998)","journal-title":"Int. J. Bifur. Chaos Appl. Sci. Eng."},{"issue":"10","key":"1777_CR22","doi-asserted-by":"publisher","first-page":"1925","DOI":"10.1080\/00207179.2015.1012651","volume":"88","author":"R Galindo","year":"2015","unstructured":"Galindo, R.: Stabilisation of matrix polynomials. Int. J. Control 88(10), 1925\u20131932 (2015)","journal-title":"Int. J. Control"},{"issue":"9","key":"1777_CR23","doi-asserted-by":"publisher","first-page":"1389","DOI":"10.1016\/j.camwa.2012.01.024","volume":"63","author":"Y Gu","year":"2012","unstructured":"Gu, Y., Ding, R.: Observable state space realizations for multivariable systems. Comput. Math. Appl. 63(9), 1389\u20131399 (2012)","journal-title":"Comput. Math. Appl."},{"key":"1777_CR24","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1017\/S0962492917000034","volume":"26","author":"S G\u00fcttel","year":"2017","unstructured":"G\u00fcttel, S., Tisseur, F.: The nonlinear eigenvalue problem. Acta Numer. 26, 1\u201394 (2017)","journal-title":"Acta Numer."},{"issue":"6","key":"1777_CR25","doi-asserted-by":"publisher","first-page":"A2842","DOI":"10.1137\/130935045","volume":"36","author":"S G\u00fcttel","year":"2014","unstructured":"G\u00fcttel, S., Van Beeumen, R., Meerbergen, K., Michiels, W.: NLEIGS: a class of fully rational Krylov methods for nonlinear eigenvalue problems. SIAM J. Sci. Comput. 36(6), A2842\u2013A2864 (2014)","journal-title":"SIAM J. Sci. Comput."},{"key":"1777_CR26","doi-asserted-by":"crossref","unstructured":"Hochstenbach , M.E., Plestenjak., B.: Computing several eigenvalues of nonlinear eigenvalue problems by selection. Calcolo 57(16) (2020)","DOI":"10.1007\/s10092-020-00363-9"},{"issue":"6","key":"1777_CR27","doi-asserted-by":"publisher","first-page":"625","DOI":"10.1016\/S0045-7949(98)00201-6","volume":"70","author":"HJ Jung","year":"1999","unstructured":"Jung, H.J., Kim, M.C., Lee, I.W.: An improved subspace iteration method with shifting. Comput. Struct. 70(6), 625\u2013633 (1999)","journal-title":"Comput. Struct."},{"key":"1777_CR28","doi-asserted-by":"crossref","unstructured":"Kravanja, P., Van Barel, M.: Computing the Zeros of Analytic Functions. Lecture Notes in Mathematics, vol. 1727. Springer, Berlin (2000)","DOI":"10.1007\/BFb0103927"},{"issue":"2","key":"1777_CR29","doi-asserted-by":"publisher","first-page":"599","DOI":"10.1137\/16M107774X","volume":"38","author":"W Michiels","year":"2017","unstructured":"Michiels, W., Boussaada, I., Niculescu, S.I.: An explicit formula for the splitting of multiple eigenvalues for nonlinear eigenvalue problems and connections with the linearization for the delay eigenvalue problem. SIAM J. Matrix Anal. Appl. 38(2), 599\u2013620 (2017)","journal-title":"SIAM J. Matrix Anal. Appl."},{"issue":"4","key":"1777_CR30","doi-asserted-by":"publisher","first-page":"538","DOI":"10.1109\/9.566665","volume":"42","author":"KT Ngo","year":"1997","unstructured":"Ngo, K.T., Erickson, K.T.: Stability of discrete-time matrix polynomials. IEEE Trans. Automat. Control 42(4), 538\u2013542 (1997)","journal-title":"IEEE Trans. Automat. Control"},{"key":"1777_CR31","doi-asserted-by":"publisher","first-page":"674","DOI":"10.1137\/0710059","volume":"10","author":"A Ruhe","year":"1973","unstructured":"Ruhe, A.: Algorithms for the nonlinear eigenvalue problem. SIAM J. Numer. Anal. 10, 674\u2013689 (1973)","journal-title":"SIAM J. Numer. Anal."},{"key":"1777_CR32","doi-asserted-by":"publisher","first-page":"4","DOI":"10.1007\/BF02165269","volume":"13","author":"H Rutishauser","year":"1969","unstructured":"Rutishauser, H.: Computational aspects of F.L. Bauer\u2019s simultaneous iteration method. Numer. Math. 13, 4\u201313 (1969)","journal-title":"Numer. Math."},{"issue":"1","key":"1777_CR33","doi-asserted-by":"publisher","first-page":"103","DOI":"10.1137\/141002037","volume":"37","author":"Y Saad","year":"2016","unstructured":"Saad, Y.: Analysis of subspace iteration for eigenvalue problems with evolving matrices. SIAM J. Matrix Anal. Appl. 37(1), 103\u2013122 (2016)","journal-title":"SIAM J. Matrix Anal. Appl."},{"key":"1777_CR34","doi-asserted-by":"crossref","unstructured":"Sinap, A., Van\u00a0Assche, W.: Orthogonal matrix polynomials and applications. In: Proceedings of the Sixth International Congress on Computational and Applied Mathematics (Leuven, 1994), vol.\u00a066, pp. 27\u201352 (1996)","DOI":"10.1016\/0377-0427(95)00193-X"},{"key":"1777_CR35","doi-asserted-by":"crossref","unstructured":"Solov\u2019\u00ebv, S.I.: Preconditioned iterative methods for a class of nonlinear eigenvalue problems. Linear Algebra and its Applications 415(1), 210\u2013229 (2006). (Special Issue on Large Scale Linear and Nonlinear Eigenvalue Problems)","DOI":"10.1016\/j.laa.2005.03.034"},{"key":"1777_CR36","doi-asserted-by":"crossref","unstructured":"Strobach, P.: The recursive companion matrix root tracker. IEEE Trans. Signal Proces. 45(8) (1997)","DOI":"10.1109\/78.611185"},{"issue":"9","key":"1777_CR37","doi-asserted-by":"publisher","first-page":"683","DOI":"10.1016\/0898-1221(88)90004-1","volume":"16","author":"JSH Tsai","year":"1988","unstructured":"Tsai, J.S.H., Shieh, L.S., Shen, T.T.C.: Block power method for computing solvents and spectral factors of matrix polynomials. Comput. Math. Appl. 16(9), 683\u2013699 (1988)","journal-title":"Comput. Math. Appl."},{"issue":"1","key":"1777_CR38","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1137\/100809167","volume":"32","author":"R Vandebril","year":"2011","unstructured":"Vandebril, R.: Chasing bulges or rotations? A metamorphosis of the QR-algorithm. SIAM J. Matrix Anal. Appl. 32(1), 217\u2013247 (2011)","journal-title":"SIAM J. Matrix Anal. Appl."},{"key":"1777_CR39","doi-asserted-by":"crossref","unstructured":"Vandebril, R., Van\u00a0Barel, M., Mastronardi, N.: Matrix Computations and Semiseparable Matrices, vol. II. Johns Hopkins University Press, Baltimore (2008). Eigenvalue and singular value methods","DOI":"10.1353\/book.3417"}],"container-title":["Journal of Scientific Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10915-022-01777-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10915-022-01777-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10915-022-01777-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,9,18]],"date-time":"2024-09-18T22:31:52Z","timestamp":1726698712000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10915-022-01777-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,2,20]]},"references-count":39,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2022,4]]}},"alternative-id":["1777"],"URL":"https:\/\/doi.org\/10.1007\/s10915-022-01777-z","relation":{},"ISSN":["0885-7474","1573-7691"],"issn-type":[{"type":"print","value":"0885-7474"},{"type":"electronic","value":"1573-7691"}],"subject":[],"published":{"date-parts":[[2022,2,20]]},"assertion":[{"value":"1 October 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"11 January 2022","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 January 2022","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 February 2022","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors have no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}],"article-number":"6"}}