{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,29]],"date-time":"2025-09-29T20:09:05Z","timestamp":1759176545128},"reference-count":34,"publisher":"Wiley","issue":"4","license":[{"start":{"date-parts":[[2005,7,8]],"date-time":"2005-07-08T00:00:00Z","timestamp":1120780800000},"content-version":"vor","delay-in-days":3660,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Numerical Linear Algebra App"],"published-print":{"date-parts":[[1995,7]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>The problem of reordering a sparse symmetric matrix to reduce its envelope size is considered. A new spectral algorithm for computing an envelope\u2010reducing reordering is obtained by associating a Laplacian matrix with the given matrix and then sorting the components of a specified eigenvector of the Laplacian. This Laplacian eigenvector solves a continuous relaxation of a discrete problem related to envelope minimization called the minimum 2\u2010sum problem. The permutation vector computed by the spectral algorithm is a closest permutation vector to the specified Laplacian eigenvector. Numerical results show that the new reording algorithm usually computes smaller envelope sizes than those obtained from the current standards such as the Gibbs\u2014Poole\u2014Stockmeyer (GPS) algorithm or the reverse Cuthill\u2014McKee (RCM) algorithm in SPARSPAK, in some cases reducing the envelope by more than a factor of two.<\/jats:p>","DOI":"10.1002\/nla.1680020402","type":"journal-article","created":{"date-parts":[[2005,10,6]],"date-time":"2005-10-06T17:48:42Z","timestamp":1128620922000},"page":"317-334","source":"Crossref","is-referenced-by-count":88,"title":["A spectral algorithm for envelope reduction of sparse matrices"],"prefix":"10.1002","volume":"2","author":[{"given":"Stephen T.","family":"Barnard","sequence":"first","affiliation":[]},{"given":"Alex","family":"Pothen","sequence":"additional","affiliation":[]},{"given":"Horst","family":"Simon","sequence":"additional","affiliation":[]}],"member":"311","published-online":{"date-parts":[[2005,7,8]]},"reference":[{"key":"e_1_2_1_2_2","doi-asserted-by":"publisher","DOI":"10.1177\/109434208900300303"},{"key":"e_1_2_1_3_2","doi-asserted-by":"publisher","DOI":"10.1177\/109434208700100403"},{"key":"e_1_2_1_4_2","doi-asserted-by":"publisher","DOI":"10.1002\/cpe.4330060203"},{"key":"e_1_2_1_5_2","unstructured":"T. F.ChanandW. K.Szeto.On the near optimality of the recursive spectral bisection method for graph partitioning. February1993."},{"key":"e_1_2_1_6_2","first-page":"P69","volume-title":"Proceed. 24th Nat. Conf. Assoc. Comp. Mach","author":"Cuthill E.","year":"1969"},{"key":"e_1_2_1_7_2","doi-asserted-by":"publisher","DOI":"10.1137\/0613057"},{"key":"e_1_2_1_8_2","volume-title":"Direct Methods for Sparse Matrices","author":"Duff I.","year":"1986"},{"key":"e_1_2_1_9_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01932738"},{"key":"e_1_2_1_10_2","doi-asserted-by":"publisher","DOI":"10.21136\/CMJ.1973.101168"},{"key":"e_1_2_1_11_2","first-page":"69","volume-title":"Numerische Methoden bei graphentheoretischen und kombinatorischen Problemen, Oberwolfach 1974","author":"Fiedler M.","year":"1975"},{"issue":"100","key":"e_1_2_1_12_2","doi-asserted-by":"crossref","first-page":"619","DOI":"10.21136\/CMJ.1975.101357","article-title":"A property of eigenvectors of nonnegative symmetric matrices and its application to graph theory","volume":"25","author":"Fiedler M.","year":"1975","journal-title":"Czechoslovak Math. J."},{"key":"e_1_2_1_13_2","volume-title":"Computer Solution of Large Sparse Positive Definite Systems","author":"George A.","year":"1981"},{"key":"e_1_2_1_14_2","unstructured":"J. A.GeorgeandA.Pothen.An analysis of spectral envelope reduction via quadratic assignment problems. Technical report Dept. of Comp. Sci. Old Dominion Univ. Norfolk VA 1994(in preparation)."},{"key":"e_1_2_1_15_2","doi-asserted-by":"publisher","DOI":"10.1137\/0713023"},{"key":"e_1_2_1_16_2","doi-asserted-by":"publisher","DOI":"10.1145\/355705.355713"},{"key":"e_1_2_1_17_2","volume-title":"Matrix Computations","author":"Golub G.","year":"1989"},{"key":"e_1_2_1_18_2","doi-asserted-by":"publisher","DOI":"10.1137\/0611022"},{"key":"e_1_2_1_19_2","unstructured":"C.Helmberg B.Mohar S.PoljakandF.Rendl.A spectral approach to bandwidth and separator problems in graphs. February1993."},{"key":"e_1_2_1_20_2","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(92)90229-4"},{"key":"e_1_2_1_21_2","first-page":"359","volume-title":"Science and Engineering on Cray Supercomputers","author":"Knight N.","year":"1988"},{"key":"e_1_2_1_22_2","doi-asserted-by":"publisher","DOI":"10.1145\/355993.355998"},{"key":"e_1_2_1_23_2","doi-asserted-by":"publisher","DOI":"10.1137\/0909019"},{"key":"e_1_2_1_24_2","unstructured":"J.Liu.A generalized envelope method for sparse factorization by rows. Technical Report CS\u201088\u201009 Department of Computer Science York University 1988."},{"key":"e_1_2_1_25_2","doi-asserted-by":"publisher","DOI":"10.1137\/0713020"},{"key":"e_1_2_1_26_2","first-page":"107","volume-title":"Eigenvalues in Combinatorial Optimization","author":"Mohar B.","year":"1993"},{"key":"e_1_2_1_27_2","volume-title":"The Symmetric Eigenvalue Problem","author":"Parlett B.","year":"1980"},{"key":"e_1_2_1_28_2","volume-title":"Sparse Matrix Technology","author":"Pissanetzky S.","year":"1984"},{"key":"e_1_2_1_29_2","unstructured":"E. L.PooleandA. L.Overman.The solution of linear systems of equations with a structural analysis code on the NAS CRAY\u20102. Technical Report Contractor Report 4159 NASA Langley Research Center Hampton VA December1988."},{"key":"e_1_2_1_30_2","doi-asserted-by":"publisher","DOI":"10.1137\/0611030"},{"key":"e_1_2_1_31_2","unstructured":"A.Pothen H.SimonandL.Wang.Spectral nested dissection. Technical Report RNR\u2010092\u2010003 NASA Ames Research Center Moffett Field CA 94035 1992."},{"key":"e_1_2_1_32_2","first-page":"536","volume-title":"Proceedings of Supercomputing '92","author":"Pothen A.","year":"1992"},{"key":"e_1_2_1_33_2","unstructured":"H.Simon P.VuandC.Yang.Performance of a supernodal general sparse solver on the CRAY Y\u2010MP: 1.68 GFLOPS with autotasking. Technical Report RNR\u201089\/04 NASA Ames Research Center Moffett Field CA 94035 1989."},{"key":"e_1_2_1_34_2","doi-asserted-by":"publisher","DOI":"10.1016\/0956-0521(91)90014-V"},{"key":"e_1_2_1_35_2","first-page":"859","volume-title":"Proceedings of the AIAA\/ASME\/ASCE\/AHS\/ASC 30th Structures, Structural Dynamics and Materials Conference","author":"Storaasli O.","year":"1989"}],"container-title":["Numerical Linear Algebra with Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fnla.1680020402","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/nla.1680020402","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,25]],"date-time":"2023-10-25T18:40:13Z","timestamp":1698259213000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/nla.1680020402"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995,7]]},"references-count":34,"journal-issue":{"issue":"4","published-print":{"date-parts":[[1995,7]]}},"alternative-id":["10.1002\/nla.1680020402"],"URL":"https:\/\/doi.org\/10.1002\/nla.1680020402","archive":["Portico"],"relation":{},"ISSN":["1070-5325","1099-1506"],"issn-type":[{"value":"1070-5325","type":"print"},{"value":"1099-1506","type":"electronic"}],"subject":[],"published":{"date-parts":[[1995,7]]}}}