{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,1]],"date-time":"2026-06-01T16:49:40Z","timestamp":1780332580990,"version":"3.54.1"},"reference-count":39,"publisher":"Wiley","issue":"3","license":[{"start":{"date-parts":[[2019,1,31]],"date-time":"2019-01-31T00:00:00Z","timestamp":1548892800000},"content-version":"am","delay-in-days":365,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#am"},{"start":{"date-parts":[[2018,1,31]],"date-time":"2018-01-31T00:00:00Z","timestamp":1517356800000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"funder":[{"DOI":"10.13039\/100006227","name":"Lawrence Livermore National Laboratory","doi-asserted-by":"publisher","award":["DE-AC52-07NA27344"],"award-info":[{"award-number":["DE-AC52-07NA27344"]}],"id":[{"id":"10.13039\/100006227","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100006227","name":"Lawrence Livermore National Laboratory","doi-asserted-by":"publisher","award":["B600360"],"award-info":[{"award-number":["B600360"]}],"id":[{"id":"10.13039\/100006227","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000015","name":"U.S. Department of Energy","doi-asserted-by":"publisher","award":["(SC) DE-FC02-03ER25574"],"award-info":[{"award-number":["(SC) DE-FC02-03ER25574"]}],"id":[{"id":"10.13039\/100000015","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000015","name":"U.S. Department of Energy","doi-asserted-by":"publisher","award":["(NNSA) DE-NA0002376"],"award-info":[{"award-number":["(NNSA) DE-NA0002376"]}],"id":[{"id":"10.13039\/100000015","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Numerical Linear Algebra App"],"published-print":{"date-parts":[[2018,5]]},"abstract":"<jats:title>Summary<\/jats:title><jats:p>We propose nonsymmetric lean algebraic multigrid (NS\u2010LAMG), a new algebraic multigrid algorithm for directed graph Laplacian systems that combines ideas from undirected graph Laplacian multigrid solvers and multigrid algorithms for Markov chain stationary distribution systems. Low\u2010degree elimination, proposed in LAMG for undirected graphs, is generalized to directed graphs and is a key component of NS\u2010LAMG. In the setup phase, we propose a simple stationary\u2010aggregation multigrid algorithms for Markov chain stationary distribution systems solver enhanced by low\u2010degree elimination to find the right null\u2010space vector that is used for the intergrid transfer operators. Numerical results show that low\u2010degree elimination improves performance and that NS\u2010LAMG outperforms generalized minimal residual method with restart and stable bi\u2010conjugate gradient method for real\u2010world, directed graph Laplacian linear systems.<\/jats:p>","DOI":"10.1002\/nla.2152","type":"journal-article","created":{"date-parts":[[2018,1,31]],"date-time":"2018-01-31T14:26:14Z","timestamp":1517408774000},"source":"Crossref","is-referenced-by-count":4,"title":["Algebraic multigrid for directed graph Laplacian linear systems (NS\u2010LAMG)"],"prefix":"10.1002","volume":"25","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-7140-3614","authenticated-orcid":false,"given":"Alyson","family":"Fox","sequence":"first","affiliation":[{"name":"Center for Applied Scientific Computing Lawrence Livermore National Laboratory  Livermore CA 94551 USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Thomas","family":"Manteuffel","sequence":"additional","affiliation":[{"name":"Department of Applied Mathematics University of Colorado Boulder  Boulder CO 80303 USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"311","published-online":{"date-parts":[[2018,1,31]]},"reference":[{"key":"e_1_2_7_2_1","doi-asserted-by":"publisher","DOI":"10.21136\/CMJ.1973.101168"},{"key":"e_1_2_7_3_1","doi-asserted-by":"crossref","unstructured":"ChristianoP KelnerJA MadryA SpielmanDA TengSH.Electrical flows Laplacian systems and faster approximation of maximum flow in undirected graphs. Paper presented at: Proceedings of the 43rd Annual ACM Symposium on Theory of Computing STOC '11 ACM;2011;New York NY.http:\/\/doi.acm.org\/10.1145\/1993636.1993674","DOI":"10.1145\/1993636.1993674"},{"key":"e_1_2_7_4_1","doi-asserted-by":"crossref","unstructured":"TongH FaloutsosC.Center\u2010piece subgraphs: Problem definition and fast solutions. Paper presented at: Proceedings of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining KDD '06 ACM;2006;New York NY.http:\/\/doi.acm.org\/10.1145\/1150402.1150448","DOI":"10.1145\/1150402.1150448"},{"key":"e_1_2_7_5_1","doi-asserted-by":"crossref","unstructured":"KelnerJA OrecchiaL SidfordA ZhuZA.A simple combinatorial algorithm for solving SDD systems in nearly\u2010linear time. Paper presented at: Proceedings of the 45th Annual ACM Symposium on Theory of Computing STOC '13 ACM;2013;New York NY USA.http:\/\/doi.acm.org\/10.1145\/2488608.2488724","DOI":"10.1145\/2488608.2488724"},{"key":"e_1_2_7_6_1","first-page":"205","volume-title":"Is nearly\u2010linear the same in theory and practice? A case study with a combinatorial Laplacian solver","author":"Hoske D","year":"2015"},{"key":"e_1_2_7_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/090771430"},{"key":"e_1_2_7_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/110845914"},{"key":"e_1_2_7_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/110843563"},{"key":"e_1_2_7_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cviu.2011.05.013"},{"key":"e_1_2_7_11_1","first-page":"201","article-title":"An efficient multigrid method for graph Laplacian systems","volume":"45","author":"Napov A","year":"2016","journal-title":"Electron Trans Numer Anal"},{"key":"e_1_2_7_12_1","article-title":"An efficient multigrid method for graph Laplacian systems II: Robust aggregation","author":"Napov A","year":"2016","journal-title":"SIAM J Sci Comput"},{"key":"e_1_2_7_13_1","unstructured":"LiXS.Sparse Gaussian elimination on high performance computers[PhD Thesis]. Berkeley CA: University of California at Berkeley;1996."},{"key":"e_1_2_7_14_1","doi-asserted-by":"crossref","unstructured":"FengT LiuH.The computer realization of the QR decomposition on matrices with full column rank. Paper presented at: 2009 International Conference on Computational Intelligence and Security CIS '09 IEEE; vol. 2;2009Dec 11\u201014; Beijing China.","DOI":"10.1109\/CIS.2009.54"},{"key":"e_1_2_7_15_1","doi-asserted-by":"publisher","DOI":"10.1137\/0907058"},{"key":"e_1_2_7_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/355984.355989"},{"key":"e_1_2_7_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/0913035"},{"key":"e_1_2_7_18_1","doi-asserted-by":"crossref","unstructured":"CohenMB KelnerJ PeeblesJ et al.Almost\u2010linear\u2010time algorithms for Markov chains and new spectral primitives for directed graphs. Paper presented at: Proceedings of the 49th annual ACM SIGACT Symposium on Theory of Computing STOC 2017 ACM;2017;New York NY.http:\/\/doi.acm.org\/10.1145\/3055399.3055463","DOI":"10.1145\/3055399.3055463"},{"key":"e_1_2_7_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/0024-3795(95)00166-O"},{"key":"e_1_2_7_20_1","unstructured":"HortonG.On the multilevel solution algorithm for Markov chains. Technical Report NASA CR-201671 ICASE Report No. 97-17 NASA Langley Research Center;1997.\u00a0https:\/\/ntrs.nasa.gov\/search.jsp?R=19970017056"},{"key":"e_1_2_7_21_1","first-page":"403","volume-title":"Numerical solution of large finite Markov chains by algebraic multigrid techniques","author":"Krieger UR","year":"1995"},{"key":"e_1_2_7_22_1","doi-asserted-by":"publisher","DOI":"10.1137\/070685142"},{"key":"e_1_2_7_23_1","doi-asserted-by":"publisher","DOI":"10.1137\/090770114"},{"key":"e_1_2_7_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10444-010-9168-x"},{"key":"e_1_2_7_25_1","doi-asserted-by":"publisher","DOI":"10.1137\/090753589"},{"key":"e_1_2_7_26_1","doi-asserted-by":"publisher","DOI":"10.1137\/100791816"},{"key":"e_1_2_7_27_1","doi-asserted-by":"publisher","DOI":"10.1137\/080719157"},{"key":"e_1_2_7_28_1","doi-asserted-by":"publisher","DOI":"10.1002\/1099-1506(200007\/08)7:5<243::AID-NLA195>3.0.CO;2-Y"},{"key":"e_1_2_7_29_1","doi-asserted-by":"publisher","DOI":"10.1002\/nla.708"},{"key":"e_1_2_7_30_1","doi-asserted-by":"publisher","DOI":"10.1137\/100799034"},{"key":"e_1_2_7_31_1","doi-asserted-by":"publisher","DOI":"10.1080\/15427951.2005.10129111"},{"key":"e_1_2_7_32_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611971262"},{"key":"e_1_2_7_33_1","volume-title":"Introduction to the numerical solution of Markov chains","author":"Stewart W","year":"1994"},{"key":"e_1_2_7_34_1","doi-asserted-by":"publisher","DOI":"10.1137\/050626272"},{"key":"e_1_2_7_35_1","doi-asserted-by":"publisher","DOI":"10.1002\/nla.542"},{"key":"e_1_2_7_36_1","doi-asserted-by":"publisher","DOI":"10.1002\/nla.800"},{"key":"e_1_2_7_37_1","doi-asserted-by":"publisher","DOI":"10.1137\/141000671"},{"key":"e_1_2_7_38_1","unstructured":"SandersG ManteuffelT FoxA MonningN.An investigation into LAMG. Tech. report LLNL Livermore CA. Boulder CO: CU Boulder;\u00a02015."},{"key":"e_1_2_7_39_1","doi-asserted-by":"publisher","DOI":"10.1137\/080727336"},{"key":"e_1_2_7_40_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972757.25"}],"container-title":["Numerical Linear Algebra with Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fnla.2152","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/nla.2152","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/full-xml\/10.1002\/nla.2152","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/am-pdf\/10.1002\/nla.2152","content-type":"application\/pdf","content-version":"am","intended-application":"syndication"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/nla.2152","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,9,3]],"date-time":"2023-09-03T02:55:15Z","timestamp":1693709715000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/nla.2152"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,1,31]]},"references-count":39,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2018,5]]}},"alternative-id":["10.1002\/nla.2152"],"URL":"https:\/\/doi.org\/10.1002\/nla.2152","archive":["Portico"],"relation":{},"ISSN":["1070-5325","1099-1506"],"issn-type":[{"value":"1070-5325","type":"print"},{"value":"1099-1506","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,1,31]]},"article-number":"e2152"}}