{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,3,30]],"date-time":"2022-03-30T17:02:42Z","timestamp":1648659762079},"reference-count":23,"publisher":"Association for Computing Machinery (ACM)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ACM Trans. Math. Softw."],"published-print":{"date-parts":[[1988,6]]},"abstract":"\n Many iterative algorithms for the solution of large linear systems may be effectively vectorized if the diagonal of the matrix is surrounded by a large band of zeroes, whose width is called the zero stretch. In this paper, a multicolor numbering technique is suggested for maximizing the zero stretch of irregularly sparse matrices. The technique, which is a generalization of a known multicoloring algorithm for regularly sparse matrices, executes in linear time, and produces a zero stretch approximately equal to\n n<\/jats:italic>\n \/2\u03c3, where 2\u03c3 is the number of colors used in the algorithm. For triangular meshes, it is shown that \u03c3 \u2264 3, and that it is possible to obtain \u03c3 = 2 by applying a simple backtracking scheme.\n <\/jats:p>","DOI":"10.1145\/45054.214373","type":"journal-article","created":{"date-parts":[[2002,7,27]],"date-time":"2002-07-27T11:29:03Z","timestamp":1027769343000},"page":"117-138","source":"Crossref","is-referenced-by-count":14,"title":["Multicolor reordering of sparse matrices resulting from irregular grids"],"prefix":"10.1145","volume":"14","author":[{"given":"Rami G.","family":"Melhem","sequence":"first","affiliation":[{"name":"Department of Computer Science, The University of Pittsburgh, Pittsburgh, PA"}]},{"given":"K. V. S.","family":"Ramarao","sequence":"additional","affiliation":[{"name":"Department of Computer Science, The University of Pittsburgh, Pittsburgh, PA"}]}],"member":"320","reference":[{"key":"e_1_2_1_1_2","first-page":"53","volume-title":"Proceedings of the 1982 International Conference on Parallel Processing. Computer Society Press","author":"ADAMS L.","year":"1982"},{"key":"e_1_2_1_2_2","first-page":"433","article-title":"Planar permutation graphs. Ann. Inst. H. Poincare","volume":"3","author":"CHARTRAND G.","year":"1967","journal-title":"Sect. B"},{"key":"e_1_2_1_3_2","doi-asserted-by":"crossref","first-page":"12","DOI":"10.1016\/0095-8956(71)90065-7","article-title":"Graphs with forbidden subgraphs","volume":"10","author":"CHARTRAND G.","year":"1971","journal-title":"J. Comb. Theor. Set. B"},{"key":"e_1_2_1_4_2","doi-asserted-by":"crossref","first-page":"157","DOI":"10.1145\/800195.805928","volume-title":"Proceedings of the ACM National Conference (1969)","volume":"24","author":"CUTHILL E.","year":"1969"},{"key":"e_1_2_1_5_2","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1137\/0134037","article-title":"Complexity results for bandwidth minimization","volume":"34","author":"GAREY M.","year":"1978","journal-title":"SIAM J. App. Math."},{"key":"e_1_2_1_6_2","doi-asserted-by":"publisher","DOI":"10.1145\/355705.355707"},{"key":"e_1_2_1_7_2","volume-title":"Academic Press","author":"HAGEMAN L.","year":"1981"},{"key":"e_1_2_1_9_2","unstructured":"LAw K. AND FENVES J. A node-addition model for symbolic factorization. ACM Trans. Math. So{tw. 12 1 (1986) 37-50. 10.1145\/5960.5963 LAw K. AND FENVES J. A node-addition model for symbolic factorization. ACM Trans. Math. So{tw. 12 1 (1986) 37-50. 10.1145\/5960.5963"},{"key":"e_1_2_1_10_2","doi-asserted-by":"publisher","DOI":"10.1137\/0213040"},{"key":"e_1_2_1_11_2","doi-asserted-by":"crossref","first-page":"150","DOI":"10.1090\/S0025-5718-1980-0559197-0","article-title":"An incomplete factorization technique for positive definit linear systems","volume":"34","author":"MANTEUFFEL T","year":"1980","journal-title":"Math. Comput."},{"key":"e_1_2_1_12_2","doi-asserted-by":"publisher","DOI":"10.1137\/0907082"},{"key":"e_1_2_1_13_2","first-page":"137","article-title":"An iterative solution method for linear systems of which the coefficient matrix is a symmetric M-matrix","volume":"31","author":"MEIJERINK J.","year":"1977","journal-title":"Math. Comput."},{"key":"e_1_2_1_14_2","doi-asserted-by":"publisher","DOI":"10.1137\/0724091"},{"key":"e_1_2_1_15_2","first-page":"1","article-title":"Toward efficient implementations of preconditioned conjugate gradient methods on vector supercomputers","volume":"1","author":"MELHEM R","year":"1987","journal-title":"Int. J. Supercomput. Appl."},{"key":"e_1_2_1_16_2","first-page":"560","volume-title":"Proceedings of the 1987 International Conference on Parallel Processing (Aug. 1987","author":"MELHEM R.","year":"1987"},{"key":"e_1_2_1_17_2","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1016\/0167-8191(88)90082-8","article-title":"Parallel solution of linear systems with striped sparse matrices","volume":"6","author":"MELHEM R","year":"1988","journal-title":"Parallel Comput."},{"key":"e_1_2_1_18_2","doi-asserted-by":"crossref","first-page":"263","DOI":"10.1007\/BF02280884","article-title":"The NP-completeness of the bandwidth minimization problem","volume":"16","author":"PAPADIMITRIOU C","year":"1976","journal-title":"Computing"},{"key":"e_1_2_1_19_2","volume-title":"Univ. of Virginia","author":"POOLS E.","year":"1986"},{"key":"e_1_2_1_20_2","doi-asserted-by":"crossref","first-page":"585","DOI":"10.1145\/800186.810622","volume-title":"Proceedings of the ACM National Conference (1968","volume":"23","author":"ROSEN R.","year":"1968"},{"key":"e_1_2_1_22_2","first-page":"503","article-title":"A class of planar graphs containing hamilton circuits. IBM Res. Note","author":"TANG D.T","year":"1965","journal-title":"NC"},{"key":"e_1_2_1_23_2","doi-asserted-by":"publisher","DOI":"10.1137\/0215041"},{"key":"e_1_2_1_24_2","doi-asserted-by":"publisher","DOI":"10.1145\/355815.355816"},{"key":"e_1_2_1_25_2","volume-title":"McGraw-Hill","author":"ZIENKIEWICZ O.","year":"1979"}],"container-title":["ACM Transactions on Mathematical Software"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/45054.214373","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,3,4]],"date-time":"2021-03-04T09:15:10Z","timestamp":1614849310000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/45054.214373"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1988,6]]},"references-count":23,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1988,6]]}},"alternative-id":["10.1145\/45054.214373"],"URL":"http:\/\/dx.doi.org\/10.1145\/45054.214373","relation":{},"ISSN":["0098-3500","1557-7295"],"issn-type":[{"value":"0098-3500","type":"print"},{"value":"1557-7295","type":"electronic"}],"subject":["Applied Mathematics","Software"],"published":{"date-parts":[[1988,6]]}}}