{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:22:48Z","timestamp":1725664968212},"publisher-location":"Berlin, Heidelberg","reference-count":51,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540631385"},{"type":"electronic","value":"9783540691570"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1997]]},"DOI":"10.1007\/3-540-63138-0_23","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T23:07:50Z","timestamp":1330297670000},"page":"273-286","source":"Crossref","is-referenced-by-count":7,"title":["Unstructured graph partitioning for sparse linear system solving"],"prefix":"10.1007","author":[{"given":"Jean","family":"Michel","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Fran\u00e7ois","family":"Pellegrini","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jean","family":"Roman","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,8]]},"reference":[{"key":"23_CR1","unstructured":"P. Amestoy, T. Davis, and I. Duff. An approximate minimum degree ordering algorithm. Technical Report RT\/APO\/95\/5, ENSEEIHT-IRIT, 1995. To appear in SIAM Journal of Matrix Analysis and Applications."},{"key":"23_CR2","doi-asserted-by":"crossref","unstructured":"C. Ashcraft, S. Eisenstat, J. W.-H. Liu, and A. Sherman. A comparison of three column based distributed sparse factorization schemes. In Proc. Fifth SIAM Conf. on Parallel Processing for Scientific Computing, 1991.","DOI":"10.21236\/ADA228143"},{"issue":"4","key":"23_CR3","doi-asserted-by":"crossref","first-page":"10","DOI":"10.1177\/109434208700100403","volume":"1","author":"C. Ashcraft","year":"1987","unstructured":"C. Ashcraft, R. Grimes, J. Lewis, B. Peyton, and H. Simon. Recent progress in sparse matrix methods for large linear systems. Intl. J. of Supercomputer Applications, 1(4):10\u201330, 1987.","journal-title":"Intl. J. of Supercomputer Applications"},{"issue":"2","key":"23_CR4","doi-asserted-by":"crossref","first-page":"101","DOI":"10.1002\/cpe.4330060203","volume":"6","author":"S. T. Barnard","year":"1994","unstructured":"S. T. Barnard and H. D. Simon. A fast multilevel implementation of recursive spectral bisection for partitioning unstructured problems. Concurrency: Practice and Experience, 6(2):101\u2013117, 1994.","journal-title":"Concurrency: Practice and Experience"},{"key":"23_CR5","unstructured":"S. W. Bollinger and S. F. Midkiff. Processor and link assignment in multicom-puters using simulated annealing. In Proceedings of the 11th Int. Conf. on Parallel Processing, pages 1\u20137. The Penn. State Univ. Press, August 1988."},{"issue":"2","key":"23_CR6","doi-asserted-by":"crossref","first-page":"171","DOI":"10.1007\/BF02579448","volume":"7","author":"T. N. Bui","year":"1987","unstructured":"T. N. Bui, S. Chaudhuri, F. T. Leighton, and M. Sipser. Graph bisection algorithms with good average case behavior. Combinatorica, 7(2):171\u2013191, 1987.","journal-title":"Combinatorica"},{"key":"23_CR7","volume-title":"Technical Report CSL-96-01","author":"F. Cao","year":"1996","unstructured":"F. Cao, J. R. Gilbert, and S.-H. Teng. Partitioning meshes with lines and planes. Technical Report CSL-96-01, XEROX Corporation, Palo Alto, California, 1996."},{"key":"23_CR8","doi-asserted-by":"crossref","first-page":"463","DOI":"10.1007\/BF01396049","volume":"55","author":"P. Charrier","year":"1989","unstructured":"P. Charrier and J. Roman. Algorithmique et calculs de complexit\u00e9 pour un solveur de type dissections embo\u00eet\u00e9es. Numerische Mathematik, 55:463\u2013476, 1989.","journal-title":"Numerische Mathematik"},{"key":"23_CR9","doi-asserted-by":"crossref","first-page":"1157","DOI":"10.1016\/0167-8191(92)90062-C","volume":"18","author":"T. Chockalingam","year":"1992","unstructured":"T. Chockalingam and S. Arunkumar. A randomized heuristics for the mapping problem: The genetic approach. Parallel Computing, 18:1157\u20131165, 1992.","journal-title":"Parallel Computing"},{"key":"23_CR10","first-page":"938","volume":"15","author":"W. Donath","year":"1972","unstructured":"W. Donath and A. Hoffman. Algorithms for partitioning of graphs and computer logic based on eigenvectors of connection matrices. IBM Technical Disclosure Bulletin, 15:938\u2013944, 1972.","journal-title":"IBM Technical Disclosure Bulletin"},{"key":"23_CR11","unstructured":"M. Dormanns and H.-U. Hei\u00df. Mapping large-scale FEM-graphs to highly parallel computers with grid-like topology by self-organization. Technical Report 5\/94, Fakult\u00e4t f\u00fcr Informatik, Universit\u00e4t Karlsruhe, February 1994."},{"issue":"3","key":"23_CR12","doi-asserted-by":"crossref","first-page":"315","DOI":"10.1145\/355958.355963","volume":"7","author":"I. Duff","year":"1981","unstructured":"I. Duff. On algorithms for obtaining a maximum transversal. ACM Trans. Math. Software, 7(3):315\u2013330, September 1981.","journal-title":"ACM Trans. Math. Software"},{"key":"23_CR13","first-page":"35","volume":"10","author":"F. Ercal","year":"1990","unstructured":"F. Ercal, J. Ramanujam, and P. Sadayappan. Task allocation onto a hypercube by recursive mincut bipartitioning. JPDC, 10:35\u201344, 1990.","journal-title":"JPDC"},{"key":"23_CR14","doi-asserted-by":"crossref","unstructured":"C. M. Fiduccia and R. M. Mattheyses. A linear-time heuristic for improving network partitions. In Proc. 19th Design Autom. Conf., pages 175\u2013181. IEEE, 1982.","DOI":"10.1109\/DAC.1982.1585498"},{"key":"23_CR15","doi-asserted-by":"crossref","first-page":"298","DOI":"10.21136\/CMJ.1973.101168","volume":"23","author":"M. Fiedler","year":"1973","unstructured":"M. Fiedler. Algebraic connectivity of graphs. Czech. Math. J., 23:298\u2013305, 1973.","journal-title":"Czech. Math. J."},{"key":"23_CR16","volume-title":"Computers and Intractablility: A Guide to the Theory of NP-completeness","author":"M. R. Garey","year":"1979","unstructured":"M. R. Garey and D. S. Johnson. Computers and Intractablility: A Guide to the Theory of NP-completeness. W. H. Freeman, San Francisco, 1979."},{"issue":"4","key":"23_CR17","doi-asserted-by":"crossref","first-page":"291","DOI":"10.1007\/BF01407861","volume":"18","author":"G. A. Geist","year":"1989","unstructured":"G. A. Geist and E. G.-Y. Ng. Task scheduling for parallel sparse Cholesky factorization. International Journal of Parallel Programming, 18(4):291\u2013314, 1989.","journal-title":"International Journal of Parallel Programming"},{"key":"23_CR18","doi-asserted-by":"crossref","first-page":"327","DOI":"10.1137\/0909021","volume":"9","author":"A. George","year":"1988","unstructured":"A. George, M. T. Heath, J. W.-H. Liu, and E. G.-Y. Ng. Sparse Cholesky factorization on a local memory multiprocessor. SIAM J. Sci. Stat. Comp., 9:327\u2013340, 1988.","journal-title":"SIAM J. Sci. Stat. Comp."},{"key":"23_CR19","unstructured":"J. A. George and J. W.-H. Liu. Computer solution of large sparse positive definite systems. Prentice Hall, 1981."},{"key":"23_CR20","unstructured":"A. Gupta, G. Karypis, and V. Kumar. Highly scalable parallel algorithms for sparse matrix factorization. TR 94-063, University of Minnesota, 1994. To appear in IEEE Trans, on Parallel and Distributed Systems, 1997."},{"key":"23_CR21","first-page":"97","volume-title":"Proc. Stratagem'96","author":"A. Gupta","year":"1996","unstructured":"A. Gupta, G. Karypis, and V. Kumar. Scalable parallel algorithms for sparse linear systems. In Proc. Stratagem'96, Sophia-Antipolis, pages 97\u2013110. INRIA, July 1996."},{"key":"23_CR22","unstructured":"S. W. Hammond. Mapping unstructured grid computations to massively parallel computers. PhD thesis, Rensselaer Polytechnic Institute, February 1992."},{"key":"23_CR23","unstructured":"B. Hendrickson. Mapping results. Personal communication, July 1996."},{"key":"23_CR24","doi-asserted-by":"crossref","unstructured":"B. Hendrickson and R. Leland. Multidimensional spectral load balancing. Technical Report SAND93-0074, Sandia National Laboratories, January 1993.","DOI":"10.2172\/6691328"},{"key":"23_CR25","doi-asserted-by":"crossref","unstructured":"B. Hendrickson and R. Leland. The CHACO user's guide \u2014 version 2.0. Technical Report SAND94-2692, Sandia National Laboratories, 1994.","DOI":"10.2172\/10106339"},{"key":"23_CR26","first-page":"682","volume-title":"Proc. SHPCC'94","author":"B. Hendrickson","year":"1994","unstructured":"B. Hendrickson and R. Leland. An empirical study of static load balancing algorithms. In Proc. SHPCC'94, Knoxville, pages 682\u2013685. IEEE, May 1994."},{"key":"23_CR27","doi-asserted-by":"crossref","unstructured":"B. Hendrickson, R. Leland, and R. Van Driessche. Enhancing data locality by using terminal propagation. In Proceedings of the 29 th Hawaii International Conference on System Sciences. IEEE, January 1996.","DOI":"10.1109\/HICSS.1996.495507"},{"key":"23_CR28","unstructured":"B. Hendrickson, R. Leland, and R. Van Driessche. Skewed graph partitioning. In Proceedings of the 8 th SIAM Conference on Parallel Processing for Scientific Computing. IEEE, March 1997."},{"key":"23_CR29","unstructured":"B. Hendrickson and E. Rothberg. Improving the runtime and quality of nested dissection ordering. Technical Report SAND96-0868J, Sandia National Laboratories, March 1996."},{"issue":"4","key":"23_CR30","doi-asserted-by":"crossref","first-page":"225","DOI":"10.1137\/0202019","volume":"2","author":"J. Hopcroft","year":"1973","unstructured":"J. Hopcroft and R. Karp. An n 5\/2 algorithm for maximum matchings in bipartite graphs. SIAM Journal of Computing, 2(4):225\u2013231, December 1973.","journal-title":"SIAM Journal of Computing"},{"key":"23_CR31","unstructured":"G. Karypis and V. Kumar. A fast and high quality multilevel scheme for partitioning irregular graphs. TR 95-035, University of Minnesota, June 1995."},{"key":"23_CR32","unstructured":"G. Karypis and V. Kumar. METIS \u2014 Unstructured Graph Partitioning and Sparse Matrix Ordering System \u2014 Version 2.0. University of Minnesota, June 1995."},{"key":"23_CR33","doi-asserted-by":"crossref","unstructured":"G. Karypis and V. Kumar. Multilevel k-way partitioning scheme for irregular graphs. Technical Report 95-064, University of Minnesota, August 1995.","DOI":"10.1145\/369028.369103"},{"key":"23_CR34","doi-asserted-by":"crossref","unstructured":"G. Karypis and V. Kumar. Parallel multilevel k-way partitioning scheme for irregular graphs. TR 96-036, University of Minnesota, 1996.","DOI":"10.1145\/369028.369103"},{"key":"23_CR35","doi-asserted-by":"crossref","unstructured":"B. W. Kernighan and S. Lin. An efficient heuristic procedure for partitionning graphs. BELL System Technical Journal, pages 291\u2013307, February 1970.","DOI":"10.1002\/j.1538-7305.1970.tb01770.x"},{"key":"23_CR36","volume-title":"Orderings for parallel sparse symmetric factorization","author":"C. Leiserson","year":"1987","unstructured":"C. Leiserson and J. Lewis. Orderings for parallel sparse symmetric factorization. In Third SIAM Conference on Parallel Processing for Scientific Computing, Troms\u00f8. SIAM, 1987."},{"issue":"2","key":"23_CR37","doi-asserted-by":"crossref","first-page":"141","DOI":"10.1145\/214392.214398","volume":"11","author":"J. W. Liu","year":"1985","unstructured":"J. W.-H. Liu. Modification of the minimum-degree algorithm by multiple elimination. ACM Trans. Math. Software, 11(2):141\u2013153, 1985.","journal-title":"ACM Trans. Math. Software"},{"key":"23_CR38","first-page":"71","volume":"2","author":"T. Muntean","year":"1991","unstructured":"T. Muntean and E.-G. Talbi. A parallel genetic algorithm for process-processors mapping. High performance computing, 2:71\u201382, 1991.","journal-title":"High performance computing"},{"key":"23_CR39","doi-asserted-by":"crossref","first-page":"1034","DOI":"10.1137\/0914063","volume":"14","author":"E. Ng","year":"1993","unstructured":"E. Ng and B. Peyton. Block sparse Cholesky algorithms on advanced uniprocessor computers. SIAM J. on Scientific Computing, 14:1034\u20131056, 1993.","journal-title":"SIAM J. on Scientific Computing"},{"key":"23_CR40","doi-asserted-by":"crossref","first-page":"119","DOI":"10.1006\/jpdc.1994.1126","volume":"23","author":"D. M. Nicol","year":"1994","unstructured":"D. M. Nicol. Rectilinear partitioning of irregular data parallel computations. Journal of Parallel and Distributed Computing, 23:119\u2013134, 1994.","journal-title":"Journal of Parallel and Distributed Computing"},{"key":"23_CR41","doi-asserted-by":"crossref","unstructured":"F. Pellegrini. Static mapping by dual recursive bipartitioning of process and architecture graphs. In Proc. SHPCC'94, Knoxville, pages 486\u2013493. IEEE, May 1994.","DOI":"10.1109\/SHPCC.1994.296682"},{"key":"23_CR42","unstructured":"F. Pellegrini. Application of graph partitioning techniques to static mapping and domain decomposition. In ETPSC 3, Faverges-de-la-Tour, August 1996. To appear in a special issue of Parallel Computing."},{"key":"23_CR43","unstructured":"F. Pellegrini and J. Roman. Experimental Analysis of the Dual Recursive Bipartitioning Algorithm for Static Mapping. Research Report 1138-96, LaBRI, Universit\u00e9 Bordeaux I, September 1996. Available at URL http:\/\/www.labri.u-bordeaux. fr\/~pelegrin\/papers\/scotch_expanalysis.ps.gz."},{"key":"23_CR44","doi-asserted-by":"crossref","unstructured":"F. Pellegrini and J. Roman. Sparse matrix ordering with SCOTCH. In Proc. HPCN'97, Vienna, April 1997. To appear.","DOI":"10.1007\/BFb0031609"},{"key":"23_CR45","unstructured":"A. Pothen. MMD code. Personal communication, February 1997."},{"issue":"4","key":"23_CR46","doi-asserted-by":"crossref","first-page":"303","DOI":"10.1145\/98267.98287","volume":"16","author":"A. Pothen","year":"1990","unstructured":"A. Pothen and C.-J. Fan. Computing the block triangular form of a sparse matrix. ACM Trans. Math. Software, 16(4):303\u2013324, December 1990.","journal-title":"ACM Trans. Math. Software"},{"issue":"3","key":"23_CR47","doi-asserted-by":"crossref","first-page":"430","DOI":"10.1137\/0611030","volume":"11","author":"A. Pothen","year":"1990","unstructured":"A. Pothen, H. D. Simon, and K.-P. Liou. Partitioning sparse matrices with eigenvectors of graphs. SIAM Journal of Matrix Analysis, 11(3):430\u2013452, July 1990.","journal-title":"SIAM Journal of Matrix Analysis"},{"key":"23_CR48","first-page":"324","volume-title":"Proceedings of SHPCC'94","author":"E. Rothberg","year":"1994","unstructured":"E. Rothberg. Performance of panel and block approaches to sparse Cholesky factorization on the iPSC\/860 and Paragon multicomputers. In Proceedings of SHPCC'94, Knoxville, pages 324\u2013333. IEEE, May 1994."},{"key":"23_CR49","doi-asserted-by":"crossref","unstructured":"E. Rothberg and A. Gupta. An efficient block-oriented approach to parallel sparse Cholesky factorization. In Supercomputing'93 Proceedings. IEEE, 1993.","DOI":"10.1145\/169627.169791"},{"key":"23_CR50","doi-asserted-by":"crossref","unstructured":"E. Rothberg and R. Schreiber. Improved load distribution in parallel sparse Cholesky factorization. In Supercomputing'94 Proceedings. IEEE, 1994.","DOI":"10.1109\/SUPERC.1994.344344"},{"key":"23_CR51","unstructured":"R. Schreiber. Scalability of sparse direct solvers. Technical Report TR 92.13, RIACS, NASA Ames Research Center, May 1992."}],"container-title":["Lecture Notes in Computer Science","Solving Irregularly Structured Problems in Parallel"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-63138-0_23.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,6,20]],"date-time":"2023-06-20T19:25:17Z","timestamp":1687289117000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-63138-0_23"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1997]]},"ISBN":["9783540631385","9783540691570"],"references-count":51,"URL":"https:\/\/doi.org\/10.1007\/3-540-63138-0_23","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1997]]}}}