{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:32:49Z","timestamp":1787337169032,"version":"build-2736575974"},"reference-count":31,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Sci. Comput."],"published-print":{"date-parts":[[2005,1]]},"abstract":"<jats:p>This paper is concerned with solving large-scale eigenvalue problems by algebraic substructuring. Algebraic substructuring refers to the process of applying matrix reordering and partitioning algorithms to divide a large sparse matrix into smaller submatrices from which a subset of spectral components are extracted and combined to form approximate solutions to the original problem. Through an algebraic analysis, we identify critical conditions under which a simple version of algebraic substructuring works well. This particular version of substructuring is identical to the component mode synthesis (CMS) method (see [R. R. Craig and M. C. C. Bampton, {\\em Coupling of substructures for dynamic analysis}, AIAA J., 6 (1968), pp. 1313--1319] and [W. C. Hurty, {\\em Vibrations of structure systems by component-mode synthesis}, J. Engrg. Mech., 86 (1960), pp. 51--69]) when the matrix reordering is based on a geometric partitioning of the computational domain. We observe an interesting connection between the accuracy of an approximate eigenpair obtained through substructuring and the distribution of the components of eigenvectors of a canonical matrix pencil congruent to the original problem. A priori error bounds for the smallest eigenpair approximation are developed. This development leads to a simple heuristic for choosing spectral components (modes) from each substructure.The effectiveness of such a heuristic is demonstrated with numerical examples. We show that algebraic substructuring can be effectively used to solve a generalized eigenvalue problem arising from the finite element analysis of an accelerator structure.<\/jats:p>","DOI":"10.1137\/040613767","type":"journal-article","created":{"date-parts":[[2005,12,5]],"date-time":"2005-12-05T22:29:59Z","timestamp":1133821799000},"page":"873-892","source":"Crossref","is-referenced-by-count":36,"title":["An Algebraic Substructuring Method for Large-Scale Eigenvalue Calculation"],"prefix":"10.1137","volume":"27","author":[{"given":"Chao","family":"Yang","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Weiguo","family":"Gao","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Zhaojun","family":"Bai","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Xiaoye S.","family":"Li","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Lie-Quan","family":"Lee","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Parry","family":"Husbands","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Esmond","family":"Ng","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,25]]},"reference":[{"key":"R1","first-page":"141","volume":"2","author":"Abramov A.","year":"1962","journal-title":"\u017d. Vy\u010disl. Mat. i Mat. Fiz."},{"key":"R2","first-page":"644","volume":"7","author":"Abramov A.","year":"1967","journal-title":"\u017d. Vy\u00e7isl. Mat. i Mat. Fiz."},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1137\/S0895479800381331"},{"key":"R4","unstructured":"C. Bekas and Y. Saad,\n                      Computation of Smallest Eigenvalues Using Spectral Schur Complements\n                      , Technical report UMSI\u20102004\u20106, Minnesota Supercomputer Institute, University of Minnesota, Minneapolis, MN, 2004."},{"key":"R5","unstructured":"J. K. Bennighof,\n                      Adaptive multi\u2010level substructuring method for acoustic radiation and scattering from complex structures\n                      , in Computational Methods for Fluid\/Structure Interaction, A. J. Kalinowski, ed., AMSE, New York, 1993, pp. 25\u201338."},{"key":"R6","unstructured":"J. K. Bennighof and C. K. Kim,\n                      An adaptive multi\u2010level substructuring method for efficient modeling of complex structures\n                      , in Proceedings of the 33rd AIAA SDM Conference, Dallas, TX, 1992, pp. 1631\u20131639."},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827502400650"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1007\/BF01385608"},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1051\/m2an\/1992260303851"},{"key":"R10","first-page":"169","volume":"1","author":"Chichov V. S.","year":"1961","journal-title":"Zh. Vychisl. Mat. i Mat. Fiz.","ISSN":"https:\/\/id.crossref.org\/issn\/0044-4669","issn-type":"print"},{"key":"R10","unstructured":"USSR Comput. Math. Math. Phys., 1962, pp. 186\u2013190 (in English)."},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.2514\/3.4741"},{"key":"R12","unstructured":"R. R. Craig and C\u2010J. Chang,\n                      A review of substructure coupling methods for dynamic analysis\n                      , in Advances in Engineering Science, Vol. 2, National Aeronautics and Space Administration, Washington, DC, 1976, pp. 393\u2013408."},{"key":"R13","unstructured":"I. S. Duff, R. G. Grimes, and J. G. Lewis,\n                      Users\u2019 Guide for the Harwell\u2013Boeing Sparse Matrix Collection (Release 1)\n                      , Technical report RAL\u201092\u2010086, Rutherford Appleton Laboratory, Oxfordshire, UK, 1992."},{"key":"R14","unstructured":"K. Elssel and H. Voss,\n                      An A Priori Bound for Automated Multi\u2010level Substructuring\n                      , Technical report 81, Arbeitsbereich Mathematik, TU Hamburg\u2010Harburg, Germany, 2004."},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1137\/0710032"},{"key":"R16","doi-asserted-by":"publisher","DOI":"10.1137\/S0895479888151111"},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.1061\/JMCEA3.0000162"},{"key":"R18","unstructured":"M. F. Kaplan,\n                      Implementation of Automated Multilevel Substructuring for Frequency Response Analysis of Structures\n                      , Ph.D. thesis, University of Texas at Austin, Austin, TX, 2001."},{"key":"R19","unstructured":"G. Karypis and V. Kumar,\n                      \n                        METIS\n                        \u2014A Software Package for Partitioning Unstructured Graphs, Partitioning Meshes, and Computing Fill\u2010Reducing Orderings of Sparse Matrices\u2014Version 4.0\n                      \n                      , University of Minnesota, Duluth, MN, 1998."},{"key":"R20","unstructured":"K. Ko, N. Folwell, L. Ge, A. Guetz, V. Ivanov, L. Lee, Z. Li, I. Malik, W. Mi, C. Ng, and M. Wolf,\n                      Electromagnetic Systems Simulation\u2014from Simulation to Fabrication\n                      , SciDAC report, Stanford Linear Accelerator Center, Menlo Park, CA, 2003."},{"key":"R21","doi-asserted-by":"publisher","DOI":"10.1142\/S0218396X03001870"},{"key":"R22","unstructured":"R. B. Lehoucq, D. C. Sorensen, and C. Yang,\n                      ARPACK Users\u2019 Guide: Solution of Large\u2010Scale Eigenvalue Problems with Implicitly Restarted Arnoldi Methods\n                      , SIAM, Philadelphia, 1998."},{"key":"R23","unstructured":"R. H. MacNeal,\n                      Vibrations of Composite Systems\n                      , Technical report OSRTN\u201055\u2010120, Air Force Office of Scientific Research, Air Research and Development Command, Arlington, VA, 1954."},{"key":"R24","volume-title":"The symmetric eigenvalue problem","author":"Parlett Beresford","year":"1980"},{"key":"R25","doi-asserted-by":"publisher","DOI":"10.1093\/oso\/9780198501787.001.0001"},{"key":"R26","volume-title":"Numerical methods for large eigenvalue problems","author":"Saad Youcef","year":"1992"},{"key":"R27","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-02-01435-7"},{"key":"R28","volume-title":"Domain decomposition","author":"Smith Barry","year":"1996"},{"key":"R29","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898718058"},{"key":"R30","unstructured":"C. Yang, W. Gao, Z. Bai, X. Li, L. Lee, P. Husbands, and E. Ng,\n                      An Algebraic Substructuring Algorithm for Large\u2010Scale Eigenvalue Calculation\n                      , Technical report LBNL\u201055055, Lawrence Berkeley National Lab, Berkeley, CA, 2004."}],"container-title":["SIAM Journal on Scientific Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/040613767","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T17:47:32Z","timestamp":1787334452000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/040613767"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,1]]},"references-count":31,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2005,1]]}},"alternative-id":["10.1137\/040613767"],"URL":"https:\/\/doi.org\/10.1137\/040613767","relation":{},"ISSN":["1064-8275","1095-7197"],"issn-type":[{"value":"1064-8275","type":"print"},{"value":"1095-7197","type":"electronic"}],"subject":[],"published":{"date-parts":[[2005,1]]}}}