Decomposition in multidimensional Boolean-optimization problems with sparse matrices. (English. Russian original) Zbl 1391.90413
J. Comput. Syst. Sci. Int. 57, No. 1, 97-108 (2018); translation from Izv. Ross. Akad. Nauk, Teor. Sist. Upr. 2018, No. 1, 98-110 (2018).
Summary: In this paper, we review problems associated with sparse matrices. We formulate several theorems on the allocation of a quasi-block structure in a sparse matrix, as well as on the relation of the degree of the quasi-block structure and the number of its blocks, depending on the dimension of the matrix and the number of nonzero elements in it. Algorithms for the solution of integer optimization problems with sparse matrices that have the quasi-block structure are considered. Algorithms for allocating the quasi-block structures are presented. We describe the local elimination algorithm, which is efficient for problems with matrices that have a quasi-block structure. We study the problem of an optimal sequence for the elimination of variables in the local elimination algorithm. For this purpose, we formulate a series of notions and prove the properties of graph structures corresponding to the order of the solution of subproblems. Different orders of the elimination of variables are tested.
MSC:
| 90C09 | Boolean programming |
References:
| [1] | Shcherbina, O. A., Local elimination algorithms for sparse problems of discrete optimization, (2011) |
| [2] | Yannakakis, M., Computing the minimum fill-in is NP-complete, SIAM Algebraic Discrete Meth., 2, 77-79, (1981) · Zbl 0496.68033 · doi:10.1137/0602010 |
| [3] | Liu, J. W. H., Modification of the minimum-degree algorithm by multiple elimination, ACM Trans. Math. Software, 11, 141-153, (1985) · Zbl 0568.65015 · doi:10.1145/214392.214398 |
| [4] | Amestoy, P. R.; Davis, T. A.; Duff, I. S., An approximate minimum degree ordering algorithm, SIAM Matrix Anal. Appl., 17, 886-905, (1996) · Zbl 0861.65021 · doi:10.1137/S0895479894278952 |
| [5] | George, A., Nested dissection of a regular finite element mesh, SIAM Numer. Anal., 10, 345-363, (1973) · Zbl 0259.65087 · doi:10.1137/0710032 |
| [6] | Ashcraft, C.; Liu, J. W. H., Robust ordering of sparse matrices using multisection, SIAM Matrix Anal. Appl., 19, 816-832, (1998) · Zbl 0911.65021 · doi:10.1137/S0895479896299081 |
| [7] | Hendrickson, B.; Rothberg, E., Improving the run time and quality of nested dissection ordering, SIAM Sci. Comput., 20, 468-489, (1998) · Zbl 0922.65018 · doi:10.1137/S1064827596300656 |
| [8] | Pellegrini, F.; Roman, J., Sparse matrix ordering with scotch, 370-378, (1997), Berlin · doi:10.1007/BFb0031609 |
| [9] | Tarjan, R. E.; Yannakakis, M., Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs, SIAM Comput., 13, 566-579, (1984) · Zbl 0545.68062 · doi:10.1137/0213035 |
| [10] | Jegou, P.; Ndiaye, S. N.; Terrioux, C., Computing and exploiting tree-decompositions for solving constraint networks, 777-781, (2005), Singapore |
| [11] | Rose, D. J.; Tarjan, R. E.; Lueker, G. S., Algorithmic aspects of vertex elimination on graphs, SIAM J. Comput., 5, 266-283, (1976) · Zbl 0353.65019 · doi:10.1137/0205021 |
| [12] | Y. Saad, Iterative Methods for Sparse Linear Systems (SIAM, Philadelphia, 2003). · Zbl 1031.65046 · doi:10.1137/1.9780898718003 |
| [13] | L. Fox, An Introduction to Numerical Linear Algebra (Clarendon, Oxford, 1964), 111No. 04, 111QA251, 111F6. · Zbl 0122.35701 |
| [14] | J. H. Wilkinson, The Algebraic Eigenvalue Problem (Clarendon, Oxford, 1965), 111Vol. 87. · Zbl 0258.65037 |
| [15] | G. Forsythe and C. B. Moler, Computer Solutions of Linear Algebraic Equations (Prentice-Hall, Englewood Cliffs, 1967), 111Vol. 9, pp. 72-105. · Zbl 0154.40401 |
| [16] | G. W. Stewart, Introduction to Matrix Computations (Academic, 111New York, London, 1973). · Zbl 0302.65021 |
| [17] | G. Strang, Linear Algebra and its Applications, 2nd ed. (Academic, 111New York, London, 1980). · Zbl 0463.15001 |
| [18] | G. H. Golub and C. F. van Loan, Matrix Computations (JHU, Baltimore, 2012), Vol. 3. · Zbl 1268.65037 |
| [19] | M. Yu. Balandin and E. P. Shurina, Methods of Calculation of SLAU of Great Dimensionality (Novosib. Gos. Tekh. Univ., Novosibirsk, 2000) [in Russian]. |
| [20] | A. George and J. W. H. Liu, Computer Solutions of Large Sparse Positive Definite Systems, 111Prentice-Hall Ser. Comput. Math. (Prentice-Hall, Englewood Cliffs, 1981). |
| [21] | V. V. Voevodin and Yu. A. Kuznetsov, Matrices and Calculations (Nauka, Moscow, 1984) [in Russian]. · Zbl 0537.65024 |
| [22] | V. Yu. Zhigul’skaya, Numerical Methods (Al’ma-Mater, Lugansk, 2005) [in Russian]. |
| [23] | Tarjan, R. E., Depth first search and linear graph algorithms, SIAM Comput., 1, 146-160, (1972) · Zbl 0251.05107 · doi:10.1137/0201010 |
| [24] | Sargent, R. W. H.; Westerberg, A. W., Speed-up in chemical engineering design, Trans. Inst. Chem. Eng., 42, 190-197, (1964) |
| [25] | S. Pissanetsky, Sparse Matrix Technology (Academic, New York, 1984). · Zbl 0536.65019 |
| [26] | Prabhakar Murthy, D. N.; Anderson, K. W., Sub-optimal control of sparsely coupled systems, Int. Syst. Sci., 6, 565-578, (1975) · Zbl 0301.49020 · doi:10.1080/00207727508941839 |
| [27] | A. George and J. W. Liu, Computer Solution of Large Sparse Positive Definite Systems, 111Prentice-Hall Ser. Comput. Math. (Prentice-Hall, Englewood Cliffs, 1981). |
| [28] | Parter, S., The use of linear graphs in Gauss elimination, SIAM Rev., 3, 119-130, (1961) · Zbl 0102.11302 · doi:10.1137/1003021 |
| [29] | Rose, D. J., A graph-theoretic study of the numerical solution of sparse positive definite systems of linear equations, Graph Theory Comput., 183, 217, (1972) · Zbl 0266.65028 |
| [30] | Liu, J. W. H., Computational models and task scheduling for parallel sparse Cholesky factorization, Parallel Comput., 3, 327-342, (1986) · Zbl 0609.65014 · doi:10.1016/0167-8191(86)90014-1 |
| [31] | Hou, C.; Jiao, Y.; Nie, F.; etal., Two dimensional feature selection by sparse matrix regression, IEEE Trans. Image Proces., 5, 256-259, (2017) |
| [32] | Zheng, D.; Mhembere, D.; Lyzinski, V.; etal., Semi-external memory sparse matrix multiplication for billionnode graphs, IEEE Trans. Parallel Distrib. Syst., 28, 1470-1483, (2017) · doi:10.1109/TPDS.2016.2618791 |
| [33] | Bindu, K. R.; Visweswaran, R. L.; Sachin, P. C.; etal., Reducing the cold-user and cold-item problem in recommender system by reducing the sparsity of the sparse matrix and addressing the diversity-accuracy problem, 561-570, (2017), Singapore · doi:10.1007/978-981-10-2750-5_58 |
| [34] | Liu, H.; Liu, L.; Le, T. D.; etal., Non-parametric sparse matrix decomposition for cross-view dimensionality reduction, IEEE Trans. Multimedia, 15, 138-145, (2017) |
| [35] | Liu, J. X.; Wang, D.; Gao, Y. L.; etal., Regularized non-negative matrix factorization for identifying differential genes and clustering samples: a survey, IEEE/ACM Trans. Comput. Biol. Bioinform., 99, 384-396, (2017) |
| [36] | Ansari, S. U.; Hussain, M.; Mazhar, S.; etal., Mesh partitioning and efficient equation solving techniques by distributed finite element methods: a survey, Arch. Comput. Methods Eng., 5, 1-16, (2017) |
| [37] | Tommasel, A.; Godoy, D.; Zunino, A.; etal., A distributed approach for accelerating sparse matrix arithmetic operations for high-dimensional feature selection, Knowledge Inform. Syst., 51, 459-497, (2017) · doi:10.1007/s10115-016-0981-5 |
| [38] | Elafrou, A.; Goumas, G.; Koziris, N., Performance analysis and optimization of sparse matrix-vector multiplication on intel xeon phi, 1389-1398, (2017) |
| [39] | Aguerre, J. P.; Fernandez, E.; Besuievsky, G.; etal., Computing urban radiation: a sparse matrix approach, (2017) |
| [40] | K. Cheshmi, S. Kamil, M. M. Strout, et al., “Sympiler: transforming sparse matrix codes by decoupling symbolic analysis,” arXiv:1705.06575 (2017). · doi:10.1145/3126908.3126936 |
| [41] | Filippone, S.; Cardellini, V.; Barbieri, D.; etal., Sparse matrix-vector multiplication on gpgpus, ACM Trans. Math. Software, 43, 30, (2017) · Zbl 1380.65079 · doi:10.1145/3017994 |
| [42] | Hussain, M.; Kharat, G., Person detection and tracking using sparse matrix measurement for visual surveillance, 281-293, (2017), Singapore · doi:10.1007/978-981-10-1678-3_28 |
| [43] | Peng, H.; Li, B.; Ling, H.; etal., Salient object detection via structured matrix decomposition, IEEE Trans. Pattern Anal. Machine Intell., 39, 818-832, (2017) · doi:10.1109/TPAMI.2016.2562626 |
| [44] | Lazzaro, A.; Vondele, J.; Hutter, J.; etal., Increasing the efficiency of sparse matrix-matrix multiplication with a 2.5 D algorithm and one-sided MPI, (2017) |
| [45] | Rahmani, M.; Atia, G. K., High dimensional low rank plus sparse matrix decomposition, IEEE Trans. Signal Proc., 65, 2004-2019, (2017) · Zbl 1414.94501 · doi:10.1109/TSP.2017.2649482 |
| [46] | Werner, R.; Schetelig, D.; Sothmann, T.; etal., Low rank and sparse matrix decomposition as stroke segmentation prior: useful or not? A random forest-based evaluation study, 161-166, (2017), Berlin, Heidelberg · doi:10.1007/978-3-662-54345-0_39 |
| [47] | Schaub, M. T.; Trefois, M.; Dooren, P.; etal., Sparse matrix factorizations for fast linear solvers with application to Laplacian systems, SIAM Matrix Anal. Appl., 38, 505-529, (2017) · Zbl 1367.65041 · doi:10.1137/16M1077398 |
| [48] | Bouwmans, T.; Sobral, A.; Javed, S.; etal., Decomposition into low-rank plus additive matrices for background/ foreground separation: a review for a comparative evaluation with a large-scale dataset, Comput. Sci. Rev., 23, 1-71, (2017) · Zbl 1398.68572 · doi:10.1016/j.cosrev.2016.11.001 |
| [49] | Morii, M.; Ikeda, S.; Sako, S.; etal., Data compression for the tomo-e gozen using low-rank matrix approximation, Astrophys. J., 835, 1, (2017) · doi:10.3847/1538-4357/835/1/1 |
| [50] | Finkel’shtein, Yu. Yu., Solution methods of some discrete problems of mathematical programming, (1966), Moscow |
| [51] | Yu. I. Zhuravlev, Selected Scientific Works (Magistr, Moscow, 1998) [in Russian]. |
| [52] | Musliu, N.; Samer, M.; Ganzow, T.; etal., A CSP hypergraph library, (2005), Wien |
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.
