{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,1]],"date-time":"2026-05-01T22:53:42Z","timestamp":1777676022933,"version":"3.51.4"},"reference-count":55,"publisher":"SAGE Publications","issue":"1","license":[{"start":{"date-parts":[[1997,3,1]],"date-time":"1997-03-01T00:00:00Z","timestamp":857174400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/journals.sagepub.com\/page\/policies\/text-and-data-mining-license"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["The International Journal of Supercomputer Applications and High Performance Computing"],"published-print":{"date-parts":[[1997,3]]},"abstract":"<jats:p>The multigrid method is a general and powerful means of accelerating the convergence of discrete iterative methods for solving partial differential equations (PDEs) and similar problems. The adaptation of the multigrid method to un structured meshes is important in solving problems with complex geometries. Such problems lie on the forefront of many scientific and engineering fields. Unfortunately, multi grid schemes on unstructured meshes require signifi cantly more preprocessing than on structured meshes. In fact, preprocessing can be a major part of the solution task and, for many applications, must be executed repeatedly. In addition, the large computational requirements of real istic PDEs, accurately discretized on unstructured meshes, make such computations candidates for parallel or distributed processing. This adds problem partitioning as a preprocessing task. We propose and examine experi mentally an automatic and unified strategy to perform several unstructured multigrid preprocessing tasks. Our strategy is based on dominating sets in the unstructured meshes. We also suggest several alternative related strategies. Our experiments evaluate the performance of two preprocessing tasks: coarse-mesh generation and domain partitioning. The experiments suggest that our preprocessing strategy produces high-quality meshes that give good multigrid performance. Our strategy also pro duces domain partitions that are reasonably load bal anced with relatively small edge cuts. Overall, we conclude that simple, integrated algorithmic strategies and data structures can make tedious preprocessing tasks more efficient and more automated\u2014a necessary step toward the practical application of unstructured multigrid methods.<\/jats:p>","DOI":"10.1177\/109434209701100102","type":"journal-article","created":{"date-parts":[[2007,3,4]],"date-time":"2007-03-04T20:17:47Z","timestamp":1173039467000},"page":"12-33","source":"Crossref","is-referenced-by-count":2,"title":["Toward Efficient Unstructured Multigrid Preprocessing"],"prefix":"10.1177","volume":"11","author":[{"given":"Susan E.","family":"Dorward","sequence":"first","affiliation":[{"name":"PRINCETON UNIVERSITY, PRINCETON, NJ 08544 NEC RESEARCH\rINSTITUTE, PRINCETON, NJ 08540"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lesley R.","family":"Matheson","sequence":"additional","affiliation":[{"name":"PRINCETON UNIVERSITY, PRINCETON, NJ 08544 NEC RESEARCH\rINSTITUTE, PRINCETON, NJ 08540"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Robert E.","family":"Tarjan","sequence":"additional","affiliation":[{"name":"PRINCETON UNIVERSITY, PRINCETON, NJ 08544 NEC RESEARCH\rINSTITUTE, PRINCETON, NJ 08540"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"179","published-online":{"date-parts":[[1997,3,1]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02187749"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1007\/s002110050181"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1002\/cpe.4330060203"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1987.1676942"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-1977-0431719-X"},{"key":"atypb6","volume-title":"Algebraic multigrid (AMG) for automatic multigrid solution with application to geodetic computations. Report","author":"Brandt, A.","year":"1982"},{"key":"atypb7","unstructured":"Brandt, A., McCormick, S., and Ruge, J. 1985. Algebraic multigrid (AMG) for sparse matrix equations . In Sparsity and its applications, edited by P. Evans. Cambridge , UK: Cambridge University Press, pp. 257-284."},{"key":"atypb8","volume-title":"A multigrid tutorial","author":"Briggs, W.","year":"1987"},{"key":"atypb9","volume-title":"Fundamental concepts in the numerical solution of differential equations","author":"Botha, J.","year":"1963"},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579448"},{"key":"atypb11","volume-title":"Proceedings of the Twenty-Sixth ACM\/IEEE Design Automation Conference","author":"Bui, T."},{"key":"atypb12","volume-title":"Geometric spectral partitioning","author":"Chan, T.","year":"1994"},{"key":"atypb13","volume-title":"Multilevel domain decomposition and multigrid methods for unstructured meshes: Algorithms and theory","author":"Chan, T.F.","year":"1995"},{"key":"atypb14","first-page":"171","volume":"2","author":"Chan, T.F.","year":"1994","journal-title":"Analysis"},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1007\/s002110050189"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1007\/BF01553881"},{"key":"atypb17","volume-title":"Proceedings of the 27th Annual Hawaii International Conference on System Sciences 2","author":"Dorward, S."},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0030101"},{"key":"atypb19","first-page":"922","volume":"1","author":"Fedorenko, R.","year":"1961","journal-title":"CISL Matem i Matem Fiz"},{"key":"atypb20","volume-title":"Proceedings of the Ninth IEEE International Parallel Processing Symposium","author":"Gilbert, J."},{"key":"atypb21","volume-title":"Matrix computations","author":"Golub, G.","year":"1989"},{"key":"atypb22","volume-title":"Pmceedings of the Sixth ACM-SIAM Symposium on Discrete Algorithms","author":"Guattery, S."},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1109\/43.159993"},{"key":"atypb24","doi-asserted-by":"publisher","DOI":"10.1137\/S0895479892238270"},{"key":"atypb25","volume-title":"Proceedings of Supercomputing '95","author":"Hendrickson, B."},{"key":"atypb26","unstructured":"Jespersen, D., 1984. Multigrid methods for partial differential equations . In Studies in numerical analysis, edited by G. Golub. Washington, DC: Mathematical Association of America, pp. 270-318."},{"key":"atypb27","volume-title":"A fast and high quality multilevel scheme for partitioning irregular graphs","author":"Karypis, G.","year":"1995"},{"key":"atypb28","doi-asserted-by":"publisher","DOI":"10.1002\/j.1538-7305.1970.tb01770.x"},{"key":"atypb29","doi-asserted-by":"publisher","DOI":"10.1126\/science.220.4598.671"},{"issue":"1","key":"atypb30","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0045-7930(92)90030-Y","volume":"21","author":"Lallemand, M.","year":"1992","journal-title":"Computers and Fluids"},{"key":"atypb31","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-322-92106-2"},{"key":"atypb32","doi-asserted-by":"publisher","DOI":"10.1137\/0136016"},{"key":"atypb33","doi-asserted-by":"publisher","DOI":"10.1137\/0215074"},{"key":"atypb34","volume-title":"Multigrid algorithms on massively parallel computers. Dissertation","author":"Matheson, L.","year":"1994"},{"key":"atypb35","doi-asserted-by":"publisher","DOI":"10.1006\/eujc.1996.0048"},{"key":"atypb36","volume-title":"Proceedings of the AIAA 10th Computational Fluid Dynamics Conference","author":"Mavriplis, D."},{"key":"atypb37","volume-title":"Presented at the 26th Computational Fluid Dynamics Lecture Series Program","author":"Mavriplis, D."},{"key":"atypb38","doi-asserted-by":"publisher","DOI":"10.2514\/3.9975"},{"key":"atypb39","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4613-8369-7_3"},{"key":"atypb40","volume-title":"Proceedings of the Thirty-Second IEEE Symposium on Foundations of Computer Science","author":"Miller, G."},{"key":"atypb41","volume-title":"Proceedings of the Twenty-Second ACM Symposium on Theory of Computing","author":"Miller, G."},{"key":"atypb42","volume-title":"Sparse matrix technology","author":"Pissanetzy, S.","year":"1984"},{"key":"atypb43","doi-asserted-by":"publisher","DOI":"10.1137\/0611030"},{"key":"atypb44","doi-asserted-by":"publisher","DOI":"10.1016\/0024-3795(88)90147-4"},{"key":"atypb45","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611971057.ch4"},{"key":"atypb46","doi-asserted-by":"publisher","DOI":"10.1016\/0956-0521(91)90014-V"},{"key":"atypb47","unstructured":"Smith, W. 1990. Multigrid solution of transonic flow on unstructured grids . In Recent advances and applications in computational fluid dynamics, edited by O. Baysal. New York: The American Society of Mechanical Engineers , pp. 145-152."},{"key":"atypb48","volume-title":"Spectral partitioning works: Planar graphs and finite element meshes. Technical report","author":"Spielman, D.","year":"1996"},{"key":"atypb49","doi-asserted-by":"publisher","DOI":"10.1016\/0096-3003(83)90023-1"},{"key":"atypb50","doi-asserted-by":"crossref","unstructured":"St\u00fcben, K., and Trottenberg, U. 1982. Multigrid methods: Fundamental algorithms, model problem analysis and applications. In Lecture notes in Mathematics 960, edited by W. Hackbusch and U. Trottenberg. Berlin, Germany: Springer-Verlag, pp. 1-176.","DOI":"10.1007\/BFb0069928"},{"key":"atypb51","volume-title":"Applied combinatorics","author":"Tucker, A.","year":"1980"},{"key":"atypb52","volume-title":"Matrix iterative analysis","author":"Varga, R.","year":"1962"},{"key":"atypb53","doi-asserted-by":"publisher","DOI":"10.2514\/3.12625"},{"key":"atypb54","volume-title":"An introduction to multigrid methods","author":"Wesseling, P.","year":"1991"},{"key":"atypb55","doi-asserted-by":"publisher","DOI":"10.1002\/cpe.4330030502"}],"container-title":["The International Journal of Supercomputer Applications and High Performance Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/109434209701100102","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/109434209701100102","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,29]],"date-time":"2026-04-29T08:17:25Z","timestamp":1777450645000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/10.1177\/109434209701100102"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1997,3]]},"references-count":55,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1997,3]]}},"alternative-id":["10.1177\/109434209701100102"],"URL":"https:\/\/doi.org\/10.1177\/109434209701100102","relation":{},"ISSN":["1078-3482"],"issn-type":[{"value":"1078-3482","type":"print"}],"subject":[],"published":{"date-parts":[[1997,3]]}}}