A hypergraph partitioning model for profile minimization. (English) Zbl 1402.05153
Summary: In this paper, the aim is to symmetrically permute the rows and columns of a given sparse symmetric matrix so that the profile of the permuted matrix is minimized. We formulate this permutation problem by first defining the \(m\)-way ordered hypergraph partitioning (moHP) problem and then showing the correspondence between profile minimization and moHP problems. For solving the moHP problem, we propose a recursive-bipartitioning-based hypergraph partitioning algorithm, which we refer to as the moHP algorithm. This algorithm achieves a linear part ordering via left-to-right bipartitioning. In this algorithm, we utilize fixed vertices and two novel cut-net manipulation techniques in order to address the minimization objective of the moHP problem. We show the correctness of the moHP algorithm and describe how the existing partitioning tools can be utilized for its implementation. Experimental results on an extensive set of matrices show that the moHP algorithm obtains a smaller profile than the state-of-the-art profile reduction algorithms, which then results in considerable improvements in the factorization runtime in a direct solver.
MSC:
| 05C65 | Hypergraphs |
| 05C70 | Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) |
| 05C50 | Graphs and linear algebra (matrices, eigenvalues, etc.) |
| 05C85 | Graph algorithms (graph-theoretic aspects) |
| 65F05 | Direct numerical methods for linear systems and matrix inversion |
| 65F50 | Computational methods for sparse matrices |
| 68R10 | Graph theory (including graph drawing) in computer science |
Keywords:
sparse matrices; matrix ordering; matrix profile; matrix envelope; profile minimization; profile reduction; hypergraph partitioning; recursive bipartitioningReferences:
| [1] | S. Acer, E. Kayaaslan, and C. Aykanat, {\it A recursive bipartitioning algorithm for permuting sparse square matrices into block diagonal form with overlap}, SIAM J. Sci. Comput., 35 (2013), pp. C99-C121, . · Zbl 1263.05059 |
| [2] | S. Acer, O. Selvitopi, and C. Aykanat, {\it Improving performance of sparse matrix dense matrix multiplication on large-scale parallel systems}, Parallel Comput., 59 (2016), pp. 71-96, . |
| [3] | S. T. Barnard, A. Pothen, and H. D. Simon, {\it A spectral algorithm for envelope reduction of sparse matrices}, Numer. Linear Algebra Appl., 2 (1995), pp. 317-334, . · Zbl 0833.65038 |
| [4] | J. A. B. Bernardes and S. L. G. de Oliveira, {\it A systematic review of heuristics for profile reduction of symmetric matrices}, Procedia Comput. Sci., 51 (2015), pp. 221-230, . |
| [5] | M. W. Berry, B. Hendrickson, and P. Raghavan, {\it Sparse matrix reordering schemes for browsing hypertext}, in Lectures in Applied Mathematics 32, AMS, Providence, RI, 1996, pp. 99-124. · Zbl 0857.68036 |
| [6] | M. E. Bolanos, S. Aviyente, and H. Radha, {\it Graph entropy rate minimization and the compressibility of undirected binary graphs}, in 2012 IEEE Statistical Signal Processing Workshop (SSP), IEEE, Washington, DC, 2012, pp. 109-112, . |
| [7] | E. G. Boman and B. Hendrickson, {\it A Multilevel Algorithm for Reducing the Envelope of Sparse Matrices}, Tech. report SCCM-96-14, Stanford University, Stanford, CA, 1996. |
| [8] | D. Burgess and M. Giles, {\it Renumbering unstructured grids to improve the performance of codes on hierarchical memory machines}, Adv. Engrg. Softw., 28 (1997), pp. 189-201, . |
| [9] | Ü. V. Çatalyürek and C. Aykanat, {\it Hypergraph-partitioning-based decomposition for parallel sparse-matrix vector multiplication}, IEEE Trans. Parallel Distributed Syst., 10 (1999), pp. 673-693, . |
| [10] | Ü. V. Çatalyürek and C. Aykanat, {\it PaToH: A Multilevel Hypergraph Partitioning Tool, Version \textup3.0}, Dept. of Computer Engineering, Bilkent University, Ankara, Turkey, 1999; available at . |
| [11] | S. S. Clift and W.-P. Tang, {\it Weighted graph based ordering techniques for preconditioned conjugate gradient methods}, BIT, 35 (1995), pp. 30-47, . · Zbl 0839.65110 |
| [12] | Computational Mathematics Group, {\it HSL. A Collection of Fortran Codes for Large Scale Scientific Computation}, STFC Rutherford Appleton Laboratory, Chilton, Oxfordshire, England, . |
| [13] | T. A. Davis and Y. Hu, {\it The University of Florida Sparse Matrix Collection}, ACM Trans. Math. Softw., 38 (2011), 25, . · Zbl 1365.65123 |
| [14] | T. A. Davis, S. Rajamanickam, and W. M. Sid-Lakhdar, {\it A survey of direct methods for sparse linear systems}, Acta Numer., 25 (2016), pp. 383-566, . · Zbl 1346.65011 |
| [15] | E. F. D’Azevedo, P. A. Forsyth, and W.-P. Tang, {\it Ordering methods for preconditioned conjugate gradient methods applied to unstructured grid problems}, SIAM J. Matrix Anal. Appl., 13 (1992), pp. 944-961, . · Zbl 0760.65028 |
| [16] | J. Díaz, J. Petit, and M. Serna, {\it A survey of graph layout problems}, ACM Comput. Surv., 34 (2002), pp. 313-356, . |
| [17] | E. D. Dolan and J. J. Morè, {\it Benchmarking optimization software with performance profiles}, Math. Program., 91 (2002), pp. 201-213, . · Zbl 1049.90004 |
| [18] | I. S. Duff, {\it MA\textup57–a code for the solution of sparse symmetric definite and indefinite systems}, ACM Trans. Math. Softw., 30 (2004), pp. 118-144, . · Zbl 1070.65525 |
| [19] | I. S. Duff and G. A. Meurant, {\it The effect of ordering on preconditioned conjugate gradients}, BIT, 29 (1989), pp. 635-657, . · Zbl 0687.65037 |
| [20] | C. A. Felippa, {\it Introduction to Finite Element Methods}, Department of Aerospace Engineering Sciences and Center for Aerospace Structures, University of Colorado Boulder, 2001. |
| [21] | A. George, {\it Computer Implementation of the Finite Element Method}, Ph.D. thesis, Stanford University, Stanford, CA, 1971. |
| [22] | N. E. Gibbs, {\it Algorithm 509: A hybrid profile reduction algorithm [F1]}, ACM Trans. Math. Softw., 2 (1976), pp. 378-387, . |
| [23] | N. E. Gibbs, W. G. Poole, Jr., and P. K. Stockmeyer, {\it An algorithm for reducing the bandwidth and profile of a sparse matrix}, SIAM J. Numer. Anal., 13 (1976), pp. 236-250, . · Zbl 0329.65024 |
| [24] | S. L. Gonzaga de Oliveira, J. A. B. Bernardes, and G. O. Chagas, {\it An evaluation of reordering algorithms to reduce the computational cost of the incomplete Cholesky-conjugate gradient method}, Comput. Appl. Math., 37 (2018), pp. 2965-3004, . · Zbl 1416.65083 |
| [25] | S. L. Gonzaga de Oliveira, J. A. B. Bernardes, and G. O. Chagas, {\it An evaluation of low-cost heuristics for matrix bandwidth and profile reductions}, Comput. Appl. Math., 37 (2018), pp. 1412-1471, . · Zbl 1405.90111 |
| [26] | P. Grindrod, {\it Range-dependent random graphs and their application to modeling large small-world Proteome datasets}, Phys. Rev. E, 66 (2002), 066702, . |
| [27] | W. W. Hager, {\it Minimizing the profile of a symmetric matrix}, SIAM J. Sci. Comput., 23 (2002), pp. 1799-1816, . · Zbl 1014.65020 |
| [28] | D. J. Higham, {\it Unravelling small world networks}, J. Comput. Appl. Math., 158 (2003), pp. 61-74, . · Zbl 1028.65034 |
| [29] | Y. F. Hu and J. A. Scott, {\it A multilevel algorithm for wavefront reduction}, SIAM J. Sci. Comput., 23 (2001), pp. 1352-1375, . · Zbl 0999.65022 |
| [30] | G. Kumfert and A. Pothen, {\it Two improved algorithms for envelope and wavefront reduction}, BIT, 37 (1997), pp. 559-590, . · Zbl 0891.65043 |
| [31] | J. G. Lewis, {\it Implementation of the Gibbs-Poole-Stockmeyer and Gibbs-King algorithms}, ACM Trans. Math. Softw., 8 (1982), pp. 180-189, . · Zbl 0478.65026 |
| [32] | Y. Lin and J. Yuan, {\it Profile minimization problem for matrices and graphs}, Acta Math. Appl. Sin., 10 (1994), pp. 107-112, . · Zbl 0804.05060 |
| [33] | J. Meijer and J. van de Pol, {\it Bandwidth and wavefront reduction for static variable ordering in symbolic reachability analysis}, in 2016 NASA Formal Methods Symposium, Springer, Cham, 2016, pp. 255-271, . |
| [34] | C. Mueller, B. Martin, and A. Lumsdaine, {\it A comparison of vertex ordering algorithms for large graph visualization}, in 2007 6th International Asia-Pacific Symposium on Visualization (Sydney, NSW, Australia), IEEE, Washington, DC, 2007, pp. 141-148, . |
| [35] | J. K. Reid and J. A. Scott, {\it Ordering symmetric sparse matrices for small profile and wavefront}, Internat. J. Numer. Methods Engrg., 45 (1999), pp. 1737-1755. · Zbl 0959.65059 |
| [36] | J. K. Reid and J. A. Scott, {\it Implementing Hager’s exchange methods for matrix profile reduction}, ACM Trans. Math. Softw., 28 (2002), pp. 377-391, . · Zbl 1074.65046 |
| [37] | Y. Saad, {\it Iterative Methods for Sparse Linear Systems}, SIAM, Philadelphia, 2003, . · Zbl 1031.65046 |
| [38] | O. Selvitopi, S. Acer, and C. Aykanat, {\it A recursive hypergraph bipartitioning framework for reducing bandwidth and latency costs simultaneously}, IEEE Trans. Parallel Distributed Syst., 28 (2017), pp. 345-358, . |
| [39] | D. Silva, M. Velazco, and A. Oliveira, {\it Influence of matrix reordering on the performance of iterative methods for solving linear systems arising from interior point methods for linear programming}, Math. Methods Oper. Res., 85 (2017), pp. 97-112, . · Zbl 1362.90283 |
| [40] | S. W. Sloan, {\it An algorithm for profile and wavefront reduction of sparse matrices}, Internat. J. Numer. Methods Engrg., 23 (1986), pp. 239-251, . · Zbl 0601.65027 |
| [41] | S. Xu, W. Xue, and H. X. Lin, {\it Performance modeling and optimization of sparse matrix-vector multiplication on NVIDIA CUDA platform}, J. Supercomput., 63 (2013), pp. 710-721, . |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
