{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,29]],"date-time":"2026-04-29T22:00:51Z","timestamp":1777500051619,"version":"3.51.4"},"reference-count":64,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2024,12,9]],"date-time":"2024-12-09T00:00:00Z","timestamp":1733702400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,12,9]],"date-time":"2024-12-09T00:00:00Z","timestamp":1733702400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Found Comput Math"],"published-print":{"date-parts":[[2026,4]]},"abstract":"Abstract<\/jats:title>\n \n We present a randomized, inverse-free algorithm for producing an approximate diagonalization of any\n \n \n $$n \\times n$$<\/jats:tex-math>\n \n \n n<\/mml:mi>\n \u00d7<\/mml:mo>\n n<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n matrix pencil (\n A<\/jats:italic>\n ,\u00a0\n B<\/jats:italic>\n ). The bulk of the algorithm rests on a randomized divide-and-conquer eigensolver for the generalized eigenvalue problem originally proposed by Ballard, Demmel and Dumitriu (Technical Report 2010). We demonstrate that this divide-and-conquer approach can be formulated to succeed with high probability provided the input pencil is sufficiently well-behaved, which is accomplished by generalizing the recent pseudospectral shattering work of Banks, Garza-Vargas, Kulkarni and Srivastava (Foundations of Computational Mathematics 2023). In particular, we show that perturbing and scaling (\n A<\/jats:italic>\n ,\u00a0\n B<\/jats:italic>\n ) regularizes its pseudospectra, allowing divide-and-conquer to run over a simple random grid and in turn producing an accurate diagonalization of (\n A<\/jats:italic>\n ,\u00a0\n B<\/jats:italic>\n ) in the backward error sense. The main result of the paper states the existence of a randomized algorithm that with high probability (and in exact arithmetic) produces invertible\n S<\/jats:italic>\n ,\u00a0\n T<\/jats:italic>\n and diagonal\n D<\/jats:italic>\n such that\n \n \n $$||A - SDT^{-1}||_2 \\le \\varepsilon $$<\/jats:tex-math>\n \n \n \n |<\/mml:mo>\n |<\/mml:mo>\n A<\/mml:mi>\n <\/mml:mrow>\n -<\/mml:mo>\n S<\/mml:mi>\n D<\/mml:mi>\n \n T<\/mml:mi>\n \n -<\/mml:mo>\n 1<\/mml:mn>\n <\/mml:mrow>\n <\/mml:msup>\n \n \n |<\/mml:mo>\n |<\/mml:mo>\n <\/mml:mrow>\n 2<\/mml:mn>\n <\/mml:msub>\n \u2264<\/mml:mo>\n \u03b5<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n and\n \n \n $$||B - ST^{-1}||_2 \\le \\varepsilon $$<\/jats:tex-math>\n \n \n \n |<\/mml:mo>\n |<\/mml:mo>\n B<\/mml:mi>\n <\/mml:mrow>\n -<\/mml:mo>\n S<\/mml:mi>\n \n T<\/mml:mi>\n \n -<\/mml:mo>\n 1<\/mml:mn>\n <\/mml:mrow>\n <\/mml:msup>\n \n \n |<\/mml:mo>\n |<\/mml:mo>\n <\/mml:mrow>\n 2<\/mml:mn>\n <\/mml:msub>\n \u2264<\/mml:mo>\n \u03b5<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n in at most\n \n \n $$O \\left( \\log ^2 \\left( \\frac{n}{\\varepsilon } \\right) T_{\\text {MM}}(n) \\right) $$<\/jats:tex-math>\n \n \n O<\/mml:mi>\n \n \n log<\/mml:mo>\n 2<\/mml:mn>\n <\/mml:msup>\n \n \n n<\/mml:mi>\n \u03b5<\/mml:mi>\n <\/mml:mfrac>\n <\/mml:mfenced>\n \n T<\/mml:mi>\n MM<\/mml:mtext>\n <\/mml:msub>\n \n (<\/mml:mo>\n n<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mfenced>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n operations, where\n \n \n $$T_{\\text {MM}}(n)$$<\/jats:tex-math>\n \n \n \n T<\/mml:mi>\n MM<\/mml:mtext>\n <\/mml:msub>\n \n (<\/mml:mo>\n n<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n is the asymptotic complexity of matrix multiplication. This not only provides a new set of guarantees for highly parallel generalized eigenvalue solvers but also establishes nearly matrix multiplication time as an upper bound on the complexity of inverse-free, exact-arithmetic matrix pencil diagonalization.\n <\/jats:p>","DOI":"10.1007\/s10208-024-09682-7","type":"journal-article","created":{"date-parts":[[2024,12,9]],"date-time":"2024-12-09T13:46:37Z","timestamp":1733751997000},"page":"569-645","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Generalized Pseudospectral Shattering and Inverse-Free Matrix Pencil Diagonalization"],"prefix":"10.1007","volume":"26","author":[{"given":"James","family":"Demmel","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ioana","family":"Dumitriu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ryan","family":"Schneider","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,12,9]]},"reference":[{"issue":"5","key":"9682_CR1","doi-asserted-by":"publisher","first-page":"C480","DOI":"10.1137\/140954817","volume":"36","author":"B Adlerborn","year":"2014","unstructured":"B.\u00a0Adlerborn, B.\u00a0K\u00e5gstr\u00f6m, and D.\u00a0Kressner. A parallel QZ algorithm for distributed memory HPC systems. SIAM Journal on Scientific Computing, 36(5):C480\u2013C503, 2014.","journal-title":"SIAM Journal on Scientific Computing"},{"issue":"03","key":"9682_CR2","doi-asserted-by":"publisher","first-page":"1750028","DOI":"10.1142\/S0219199717500286","volume":"19","author":"M Aizenman","year":"2017","unstructured":"M.\u00a0Aizenman, R.\u00a0Peled, J.\u00a0Schenker, M.\u00a0Shamis, and S.\u00a0Sodin. Matrix regularizing effects of Gaussian perturbations. Communications in Contemporary Mathematics, 19(03):1750028, 2017.","journal-title":"Communications in Contemporary Mathematics"},{"key":"9682_CR3","doi-asserted-by":"publisher","first-page":"170","DOI":"10.1016\/j.laa.2018.11.031","volume":"564","author":"LM Anguas","year":"2019","unstructured":"L.\u00a0M. Anguas, M.\u00a0I. Bueno, and F.\u00a0M. Dopico. A comparison of eigenvalue condition numbers for matrix polynomials. Linear Algebra and its Applications, 564:170\u2013200, 2019.","journal-title":"Linear Algebra and its Applications"},{"key":"9682_CR4","doi-asserted-by":"publisher","first-page":"279","DOI":"10.1007\/s002110050264","volume":"76","author":"Z Bai","year":"1997","unstructured":"Z.\u00a0Bai, J.\u00a0Demmel, and M.\u00a0Gu. An inverse free parallel spectral divide and conquer algorithm for nonsymmetric eigenproblems. Numerische Mathematik, 76:279\u2013308, 1997.","journal-title":"Numerische Mathematik"},{"issue":"1","key":"9682_CR5","doi-asserted-by":"publisher","first-page":"494","DOI":"10.1214\/aop\/1024404298","volume":"25","author":"ZD Bai","year":"1997","unstructured":"Z.\u00a0D. Bai. Circular law. The Annals of Probability, 25(1):494\u2013529, 1997.","journal-title":"The Annals of Probability"},{"key":"9682_CR6","unstructured":"G.\u00a0Ballard, J.\u00a0Demmel, and I.\u00a0Dumitriu. Minimizing Communication for Eigenproblems and the Singular Value Decomposition. Technical Report UCB\/EECS-2011-14, EECS Department, University of California, Berkeley, 2011."},{"key":"9682_CR7","unstructured":"G.\u00a0Ballard, J.\u00a0Demmel, I.\u00a0Dumitriu, and A.\u00a0Rusciano. A Generalized Randomized Rank-Revealing Factorization. arXiv:1909.06524, 2019."},{"key":"9682_CR8","doi-asserted-by":"publisher","first-page":"866","DOI":"10.1137\/090769156","volume":"32","author":"G Ballard","year":"2011","unstructured":"G.\u00a0Ballard, J.\u00a0Demmel, O.\u00a0Holtz, and O.\u00a0Schwartz. Minimizing communication in numerical linear algebra. SIAM Journal on Matrix Analysis and Applications, 32:866\u2013901, 2011.","journal-title":"SIAM Journal on Matrix Analysis and Applications"},{"key":"9682_CR9","doi-asserted-by":"publisher","first-page":"1959","DOI":"10.1007\/s10208-022-09577-5","volume":"23","author":"J Banks","year":"2023","unstructured":"J.\u00a0Banks, J.\u00a0Garza-Vargas, A.\u00a0Kulkarni, and N.\u00a0Srivastava. Pseudospectral Shattering, the Sign Function, and Diagonalization in Nearly Matrix Multiplication Time. Foundations of Computational Mathematics, 23:1959\u20132047, 2023.","journal-title":"Foundations of Computational Mathematics"},{"key":"9682_CR10","doi-asserted-by":"publisher","first-page":"2114","DOI":"10.1002\/cpa.22017","volume":"74","author":"J Banks","year":"2021","unstructured":"J.\u00a0Banks, A.\u00a0Kulkarni, S.\u00a0Mukherjee, and N.\u00a0Srivastava. Gaussian regularization of the pseudospectrum and Davies\u2019 conjecture. Communications on Pure and Applied Mathematics, 74:2114\u20132131, 2021.","journal-title":"Communications on Pure and Applied Mathematics"},{"issue":"1","key":"9682_CR11","doi-asserted-by":"publisher","first-page":"137","DOI":"10.1007\/BF01386217","volume":"2","author":"FL Bauer","year":"1960","unstructured":"F.\u00a0L. Bauer and C.\u00a0T. Fike. Norms and exclusion theorems. Numerische Mathematik, 2(1):137\u2013141, 1960.","journal-title":"Numerische Mathematik"},{"issue":"1","key":"9682_CR12","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1016\/0025-5564(74)90111-4","volume":"21","author":"A Beavers","year":"1974","unstructured":"A.\u00a0Beavers and E.\u00a0Denman. A new similarity transformation method for eigenvalues and eigenvectors. Mathematical Biosciences, 21(1):143\u2013169, 1974.","journal-title":"Mathematical Biosciences"},{"key":"9682_CR13","first-page":"67","volume":"88\u201389","author":"TF Chan","year":"1987","unstructured":"T.\u00a0F. Chan. Rank revealing QR factorizations. Linear Algebra and its Applications, 88-89:67\u201382, 1987.","journal-title":"Linear Algebra and its Applications"},{"issue":"5","key":"9682_CR14","doi-asserted-by":"publisher","first-page":"1114","DOI":"10.1137\/0724073","volume":"24","author":"EK Chu","year":"1987","unstructured":"E.\u00a0K. Chu. Exclusion theorems and the perturbation analysis of the generalized eigenvalue problem. SIAM Journal on Numerical Analysis, 24(5):1114\u20131125, 1987.","journal-title":"SIAM Journal on Numerical Analysis"},{"issue":"2","key":"9682_CR15","doi-asserted-by":"publisher","first-page":"551","DOI":"10.1137\/S0895479802217928","volume":"25","author":"EK Chu","year":"2003","unstructured":"E.\u00a0K. Chu. Perturbation of eigenvalues for matrix polynomials via the Bauer-Fike theorems. SIAM Journal on Matrix Analysis and Applications, 25(2):551\u2013573, 2003.","journal-title":"SIAM Journal on Matrix Analysis and Applications"},{"issue":"3","key":"9682_CR16","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1016\/S0747-7171(08)80013-2","volume":"9","author":"D Coppersmith","year":"1990","unstructured":"D.\u00a0Coppersmith and S.\u00a0Winograd. Matrix multiplication via arithmetic progressions. Journal of Symbolic Computation, 9(3):251\u2013280, 1990.","journal-title":"Journal of Symbolic Computation"},{"key":"9682_CR17","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1007\/s00211-007-0114-x","volume":"108","author":"J Demmel","year":"2007","unstructured":"J.\u00a0Demmel, I.\u00a0Dumitriu, and O.\u00a0Holtz. Fast linear algebra is stable. Numerische Mathematik, 108:59\u201391, 2007.","journal-title":"Numerische Mathematik"},{"key":"9682_CR18","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1016\/0024-3795(87)90108-X","volume":"88\u201389","author":"JW Demmel","year":"1987","unstructured":"J.\u00a0W. Demmel and B.\u00a0K\u00e5gstr\u00f6m. Computing stable eigendecompositions of matrix pencils. Linear Algebra and its Applications, 88-89:139\u2013186, 1987.","journal-title":"Linear Algebra and its Applications"},{"key":"9682_CR19","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1016\/j.laa.2019.09.006","volume":"584","author":"FM Dopico","year":"2020","unstructured":"F.\u00a0M. Dopico and V.\u00a0Noferini. Root polynomials and their role in the theory of matrix polynomials. Linear Algebra and its Applications, 584:37\u201378, 2020.","journal-title":"Linear Algebra and its Applications"},{"issue":"4","key":"9682_CR20","doi-asserted-by":"publisher","first-page":"543","DOI":"10.1137\/0609045","volume":"9","author":"A Edelman","year":"1988","unstructured":"A.\u00a0Edelman. Eigenvalues and condition numbers of random matrices. SIAM Journal on Matrix Analysis and Applications, 9(4):543\u2013560, 1988.","journal-title":"SIAM Journal on Matrix Analysis and Applications"},{"key":"9682_CR21","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1017\/S0962492904000236","volume":"14","author":"A Edelman","year":"2005","unstructured":"A.\u00a0Edelman and N.\u00a0R. Rao. Random matrix theory. Acta Numerica, 14:233\u2013297, 2005.","journal-title":"Acta Numerica"},{"issue":"3","key":"9682_CR22","first-page":"262","volume":"3","author":"L Elsner","year":"1985","unstructured":"L.\u00a0Elsner and P.\u00a0Lancaster. The spectral variation of pencils of matrices. Journal of Computational Mathematics, 3(3):262\u2013274, 1985.","journal-title":"Journal of Computational Mathematics"},{"key":"9682_CR23","doi-asserted-by":"publisher","first-page":"341","DOI":"10.1016\/0024-3795(82)90120-3","volume":"48","author":"L Elsner","year":"1982","unstructured":"L.\u00a0Elsner and J.\u00a0Sun. Perturbation theorems for the generalized eigenvalue problem. Linear Algebra and its Applications, 48:341\u2013357, 1982.","journal-title":"Linear Algebra and its Applications"},{"key":"9682_CR24","first-page":"1251","volume":"35","author":"T Ericsson","year":"1980","unstructured":"T.\u00a0Ericsson and A.\u00a0Ruhe. The spectral transformation L\u00e1nczos method for the numerical solution of large sparse generalized symmetric eigenvalue problems. Mathematics of Computation, 35:1251\u20131268, 1980.","journal-title":"Mathematics of Computation"},{"key":"9682_CR25","doi-asserted-by":"crossref","unstructured":"B.\u00a0Farrell and R.\u00a0Vershynin. Smoothed analysis of symmetric random matrices with continuous distributions. Proceedings of the American Mathematical Society, 144, 2012.","DOI":"10.1090\/proc\/12844"},{"key":"9682_CR26","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1023\/A:1019112103049","volume":"20","author":"RD Fierro","year":"1999","unstructured":"R.\u00a0D. Fierro, P.\u00a0C. Hansen, and P.\u00a0S.\u00a0K. Hansen. UTV tools: Matlab templates for rank-revealing UTV decompositions. Numerical Algorithms, 20:165\u2013194, 1999.","journal-title":"Numerical Algorithms"},{"issue":"3","key":"9682_CR27","doi-asserted-by":"publisher","first-page":"493","DOI":"10.1137\/0313029","volume":"13","author":"GD Forney Jr","year":"1975","unstructured":"G.\u00a0D. Forney, Jr. Minimal bases of rational vector spaces, with applications to multivariable linear systems. SIAM Journal on Control, 13(3):493\u2013520, 1975.","journal-title":"SIAM Journal on Control"},{"key":"9682_CR28","volume-title":"Spectral portraits for matrix pencils","author":"V Frayss\u00e9","year":"1996","unstructured":"V.\u00a0Frayss\u00e9, M.\u00a0Gueury, F.\u00a0Nicoud, and V.\u00a0Toumazou. Spectral portraits for matrix pencils. Technical Report, CERFACS, 1996."},{"issue":"3","key":"9682_CR29","doi-asserted-by":"publisher","first-page":"823","DOI":"10.1080\/00207178608933634","volume":"44","author":"JD Gardiner","year":"1986","unstructured":"J.\u00a0D. Gardiner and A.\u00a0J. Laub. A generalization of the matrix-sign-function solution for algebraic Riccati equations. International Journal of Control, 44(3):823\u2013832, 1986.","journal-title":"International Journal of Control"},{"issue":"2","key":"9682_CR30","doi-asserted-by":"publisher","first-page":"463","DOI":"10.1137\/19M124784X","volume":"62","author":"A Greenbaum","year":"2020","unstructured":"A.\u00a0Greenbaum, R.-C. Li, and M.\u00a0L. Overton. First-order perturbation theory for eigenvalues and eigenvectors. SIAM Review, 62(2):463\u2013482, 2020.","journal-title":"SIAM Review"},{"issue":"4","key":"9682_CR31","doi-asserted-by":"publisher","first-page":"848","DOI":"10.1137\/0917055","volume":"17","author":"M Gu","year":"1996","unstructured":"M.\u00a0Gu and S.\u00a0C. Eisenstat. Efficient algorithms for computing a strong rank-revealing QR factorization. SIAM Journal on Scientific Computing, 17(4):848\u2013869, 1996.","journal-title":"SIAM Journal on Scientific Computing"},{"issue":"1","key":"9682_CR32","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1080\/10556780600883874","volume":"22","author":"MR Guarracino","year":"2007","unstructured":"M.\u00a0R. Guarracino, C.\u00a0Cifarelli, O.\u00a0Seref, and P.\u00a0M. Pardalos. A classification method based on generalized eigenvalue problems. Optimization Methods and Software, 22(1):73\u201381, 2007.","journal-title":"Optimization Methods and Software"},{"key":"9682_CR33","doi-asserted-by":"crossref","unstructured":"E.\u00a0Hairer and G.\u00a0Wanner. Solving Ordinary Differential Equations II. Stiff and Differential-Algebraic Problems, vol\u00a014 of Springer Verlag Series in Computational Mathematics. 1996.","DOI":"10.1007\/978-3-642-05221-7"},{"issue":"2","key":"9682_CR34","doi-asserted-by":"publisher","first-page":"493","DOI":"10.1137\/S0895479896313188","volume":"20","author":"DJ Higham","year":"1998","unstructured":"D.\u00a0J. Higham and N.\u00a0J. Higham. Structured backward error and condition of generalized eigenvalue problems. SIAM Journal on Matrix Analysis and Applications, 20(2):493\u2013512, 1998.","journal-title":"SIAM Journal on Matrix Analysis and Applications"},{"key":"9682_CR35","doi-asserted-by":"crossref","unstructured":"N.\u00a0J. Higham. Accuracy and Stability of Numerical Algorithms. Society for Industrial and Applied Mathematics, Second edition, 2002.","DOI":"10.1137\/1.9780898718027"},{"issue":"3","key":"9682_CR36","doi-asserted-by":"publisher","first-page":"1022","DOI":"10.1137\/18M1188628","volume":"40","author":"ME Hochstenbach","year":"2019","unstructured":"M.\u00a0E. Hochstenbach, C.\u00a0Mehl, and B.\u00a0Plestenjak. Solving singular generalized eigenvalue problems by a rank-completing perturbation. SIAM Journal on Matrix Analysis and Applications, 40(3):1022\u20131046, 2019.","journal-title":"SIAM Journal on Matrix Analysis and Applications"},{"key":"9682_CR37","unstructured":"R.\u00a0A. Horn and C.\u00a0R. Johnson. Matrix Analysis. Cambridge University Press, Second edition, 2012."},{"issue":"5","key":"9682_CR38","doi-asserted-by":"publisher","first-page":"814","DOI":"10.1109\/29.56027","volume":"38","author":"Y Hua","year":"1990","unstructured":"Y.\u00a0Hua and T.\u00a0Sarkar. Matrix pencil method for estimating parameters of exponentially damped\/undamped sinusoids in noise. IEEE Transactions on Acoustics, Speech, and Signal Processing, 38(5):814\u2013824, 1990.","journal-title":"IEEE Transactions on Acoustics, Speech, and Signal Processing"},{"issue":"1","key":"9682_CR39","doi-asserted-by":"publisher","first-page":"199","DOI":"10.1137\/05064521X","volume":"29","author":"B K\u00e5gstr\u00f6m","year":"2007","unstructured":"B.\u00a0K\u00e5gstr\u00f6m and D.\u00a0Kressner. Multishift variants of the QZ algorithm with aggressive early deflation. SIAM Journal on Matrix Analysis and Applications, 29(1):199\u2013227, 2007.","journal-title":"SIAM Journal on Matrix Analysis and Applications"},{"key":"9682_CR40","unstructured":"L.\u00a0Kronecker. Algebraische Reduction der Schaaren bilinearer Formen. Sitzungsberichte der Preussischen Akademie der Wissenschaften. 1890."},{"key":"9682_CR41","doi-asserted-by":"publisher","first-page":"1439","DOI":"10.1007\/s10208-020-09455-y","volume":"20","author":"M Lotz","year":"2020","unstructured":"M.\u00a0Lotz and V.\u00a0Noferini. Wilkinson\u2019s bus: Weak condition numbers, with an application to singular polynomial eigenproblems. Foundations of Computational Mathematics, 20:1439\u20131473, 2020.","journal-title":"Foundations of Computational Mathematics"},{"key":"9682_CR42","doi-asserted-by":"publisher","first-page":"489","DOI":"10.1016\/0024-3795(93)90477-6","volume":"188\u2013189","author":"AN Malyshev","year":"1993","unstructured":"A.\u00a0N. Malyshev. Parallel algorithm for solving some spectral problems of linear algebra. Linear Algebra and its Applications, 188-189:489\u2013520, 1993.","journal-title":"Linear Algebra and its Applications"},{"issue":"1","key":"9682_CR43","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1109\/TPAMI.2006.17","volume":"28","author":"O Mangasarian","year":"2006","unstructured":"O.\u00a0Mangasarian and E.\u00a0Wild. Multisurface proximal support vector machine classification via generalized eigenvalues. IEEE Transactions on Pattern Analysis and Machine Intelligence, 28(1):69\u201374, 2006.","journal-title":"IEEE Transactions on Pattern Analysis and Machine Intelligence"},{"issue":"2","key":"9682_CR44","doi-asserted-by":"publisher","first-page":"241","DOI":"10.1137\/0710024","volume":"10","author":"CB Moler","year":"1973","unstructured":"C.\u00a0B. Moler and G.\u00a0W. Stewart. An algorithm for generalized matrix eigenvalue problems. SIAM Journal on Numerical Analysis, 10(2):241\u2013256, 1973.","journal-title":"SIAM Journal on Numerical Analysis"},{"issue":"4","key":"9682_CR45","doi-asserted-by":"publisher","first-page":"677","DOI":"10.1080\/00207178008922881","volume":"32","author":"JD Roberts","year":"1980","unstructured":"J.\u00a0D. Roberts. Linear model reduction and solution of the algebraic Riccati equation by use of the sign function. International Journal of Control, 32(4):677\u2013687, 1980.","journal-title":"International Journal of Control"},{"issue":"7","key":"9682_CR46","doi-asserted-by":"publisher","first-page":"984","DOI":"10.1109\/29.32276","volume":"37","author":"R Roy","year":"1989","unstructured":"R.\u00a0Roy and T.\u00a0Kailath. ESPRIT-estimation of signal parameters via rotational invariance techniques. IEEE Transactions on Acoustics, Speech, and Signal Processing, 37(7):984\u2013995, 1989.","journal-title":"IEEE Transactions on Acoustics, Speech, and Signal Processing"},{"issue":"2","key":"9682_CR47","doi-asserted-by":"publisher","first-page":"600","DOI":"10.1016\/j.aim.2008.01.010","volume":"218","author":"M Rudelson","year":"2008","unstructured":"M.\u00a0Rudelson and R.\u00a0Vershynin. The Littlewood-Offord problem and invertibility of random matrices. Advances in Mathematics, 218(2):600\u2013633, 2008.","journal-title":"Advances in Mathematics"},{"issue":"1","key":"9682_CR48","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1016\/S0377-0427(03)00565-X","volume":"159","author":"T Sakurai","year":"2003","unstructured":"T.\u00a0Sakurai and H.\u00a0Sugiura. A projection method for generalized eigenvalue problems using numerical integration. Journal of Computational and Applied Mathematics, 159(1):119\u2013128, 2003.","journal-title":"Journal of Computational and Applied Mathematics"},{"issue":"6","key":"9682_CR49","doi-asserted-by":"publisher","first-page":"1243","DOI":"10.1137\/0719089","volume":"19","author":"AH Sameh","year":"1982","unstructured":"A.\u00a0H. Sameh and J.\u00a0A. Wisniewski. A trace minimization algorithm for the generalized eigenvalue problem. SIAM Journal on Numerical Analysis, 19(6):1243\u20131259, 1982.","journal-title":"SIAM Journal on Numerical Analysis"},{"issue":"2","key":"9682_CR50","doi-asserted-by":"publisher","first-page":"446","DOI":"10.1137\/S0895479803436202","volume":"28","author":"A Sankar","year":"2006","unstructured":"A.\u00a0Sankar, D.\u00a0A. Spielman, and S.\u00a0H. Teng. Smoothed analysis of the condition numbers and growth factors of matrices. SIAM Journal on Matrix Analysis and Applications, 28(2):446\u2013476, 2006.","journal-title":"SIAM Journal on Matrix Analysis and Applications"},{"key":"9682_CR51","unstructured":"R.\u00a0Schneider. Pseudospectral divide-and-conquer for the generalized eigenvalue problem. PhD Thesis, 2024."},{"issue":"13","key":"9682_CR52","doi-asserted-by":"publisher","first-page":"3218","DOI":"10.1016\/j.cam.2012.02.021","volume":"236","author":"X Shi","year":"2012","unstructured":"X.\u00a0Shi and Y.\u00a0Wei. A sharp version of Bauer-Fike\u2019s theorem. Journal of Computational and Applied Mathematics, 236(13):3218\u20133227, 2012.","journal-title":"Journal of Computational and Applied Mathematics"},{"issue":"130","key":"9682_CR53","first-page":"600","volume":"29","author":"GW Stewart","year":"1975","unstructured":"G.\u00a0W. Stewart. Gershgorin theory for the generalized eigenvalue problem $${A}x = \\lambda {B}x$$. Mathematics of Computation, 29(130):600\u2013606, 1975.","journal-title":"Mathematics of Computation"},{"issue":"2","key":"9682_CR54","doi-asserted-by":"publisher","first-page":"494","DOI":"10.1137\/0614034","volume":"14","author":"GW Stewart","year":"1993","unstructured":"G.\u00a0W. Stewart. Updating a rank-revealing ULV decomposition. SIAM Journal on Matrix Analysis and Applications, 14(2):494\u2013499, 1993.","journal-title":"SIAM Journal on Matrix Analysis and Applications"},{"key":"9682_CR55","volume-title":"Matrix Perturbation Theory","author":"GW Stewart","year":"1990","unstructured":"G.\u00a0W. Stewart and J.\u00a0Sun. Matrix Perturbation Theory. Computer Science and Scientific Computing. Elsevier Science, 1990."},{"key":"9682_CR56","doi-asserted-by":"publisher","first-page":"354","DOI":"10.1007\/BF02165411","volume":"13","author":"V Strassen","year":"1969","unstructured":"V.\u00a0Strassen. Gaussian elimination is not optimal. Numerische Mathematik, 13:354\u2013356, 1969.","journal-title":"Numerische Mathematik"},{"key":"9682_CR57","first-page":"04","volume":"20","author":"T Tao","year":"2009","unstructured":"T.\u00a0Tao and V.\u00a0Vu. Random matrices: the distribution of the smallest singular values. Geometric and Functional Analysis, 20, 04 2009.","journal-title":"Geometric and Functional Analysis"},{"key":"9682_CR58","doi-asserted-by":"crossref","unstructured":"L.\u00a0N. Trefethen and M.\u00a0Embree. Spectra and Pseudospectra: The Behavior of Nonnormal Matrices and Operators. Princeton University Press, 2020.","DOI":"10.2307\/j.ctvzxx9kj"},{"key":"9682_CR59","doi-asserted-by":"crossref","unstructured":"P.\u00a0Van\u00a0Dooren. Reducing subspaces: Definitions, properties and algorithms. In B.\u00a0K\u00e5gstr\u00f6m and A.\u00a0Ruhe, editors, Matrix Pencils, pp. 58\u201373, Berlin, Heidelberg, 1983. Springer Berlin Heidelberg.","DOI":"10.1007\/BFb0062094"},{"key":"9682_CR60","doi-asserted-by":"crossref","unstructured":"R.\u00a0Vershynin. High-Dimensional Probability: An Introduction with Applications in Data Science. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 2018.","DOI":"10.1017\/9781108231596"},{"issue":"6","key":"9682_CR61","doi-asserted-by":"publisher","first-page":"835","DOI":"10.1137\/0712062","volume":"12","author":"RC Ward","year":"1975","unstructured":"R.\u00a0C. Ward. The combination shift QZ algorithm. SIAM Journal on Numerical Analysis, 12(6):835\u2013853, 1975.","journal-title":"SIAM Journal on Numerical Analysis"},{"issue":"2","key":"9682_CR62","doi-asserted-by":"publisher","first-page":"364","DOI":"10.1137\/S0895479899360376","volume":"22","author":"DS Watkins","year":"2000","unstructured":"D.\u00a0S. Watkins. Performance of the QZ algorithm in the presence of infinite eigenvalues. SIAM Journal on Matrix Analysis and Applications, 22(2):364\u2013375, 2000.","journal-title":"SIAM Journal on Matrix Analysis and Applications"},{"key":"9682_CR63","doi-asserted-by":"crossref","unstructured":"V.\u00a0V. Williams. Multiplying Matrices Faster than Coppersmith-Winograd. In Proceedings of the Forty-Fourth Annual ACM Symposium on Theory of Computing, STOC \u201912, page 887\u2013898. Association for Computing Machinery, 2012.","DOI":"10.1145\/2213977.2214056"},{"key":"9682_CR64","doi-asserted-by":"crossref","unstructured":"V.\u00a0V. Williams, Y.\u00a0Xu, Z.\u00a0Xu, and R.\u00a0Zhou. New Bounds for Matrix Multiplication: from Alpha to Omega. arXiv:2307.07970, 2023.","DOI":"10.1137\/1.9781611977912.134"}],"container-title":["Foundations of Computational Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10208-024-09682-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10208-024-09682-7","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10208-024-09682-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,27]],"date-time":"2026-04-27T21:02:12Z","timestamp":1777323732000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10208-024-09682-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,12,9]]},"references-count":64,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2026,4]]}},"alternative-id":["9682"],"URL":"https:\/\/doi.org\/10.1007\/s10208-024-09682-7","relation":{},"ISSN":["1615-3375","1615-3383"],"issn-type":[{"value":"1615-3375","type":"print"},{"value":"1615-3383","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,12,9]]},"assertion":[{"value":"14 July 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"1 March 2024","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"26 July 2024","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"9 December 2024","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}