Schur Complement Computations in Intel® Math Kernel Library PARDISO
ABSTRACT
This paper describes a method of calculating the Schur complement of a sparse positive definite matrix A. The main idea of this approach is to represent matrix A in the form of an elimination tree using a reordering algorithm like METIS and putting columns/rows for which the Schur complement is needed into the top node of the elimination tree. Any problem with a degenerate part of the initial matrix can be resolved with the help of iterative refinement. The proposed approach is close to the “multifrontal” one which was implemented by Ian Duff and others in 1980s. Schur complement computations described in this paper are available in Intel® Math Kernel Library (Intel® MKL). In this paper we present the algorithm for Schur complement computations, experiments that demonstrate a negligible increase in the number of elements in the factored matrix, and comparison with existing alternatives.
This paper describes a method of calculating the Schur complement of a sparse positive definite matrix A. The main idea of this approach is to represent matrix A in the form of an elimination tree using a reordering algorithm like METIS and putting columns/rows for which the Schur complement is needed into the top node of the elimination tree. Any problem with a degenerate part of the initial matrix can be resolved with the help of iterative refinement. The proposed approach is close to the “multifrontal” one which was implemented by Ian Duff and others in 1980s. Schur complement computations described in this paper are available in Intel® Math Kernel Library (Intel® MKL). In this paper we present the algorithm for Schur complement computations, experiments that demonstrate a negligible increase in the number of elements in the factored matrix, and comparison with existing alternatives.
KEYWORDS
Multifrontal Method, Direct Method, Sparse Linear System, Schur Complement, HPC, Intel® MKL
Multifrontal Method, Direct Method, Sparse Linear System, Schur Complement, HPC, Intel® MKL
Cite this paper
Kalinkin, A. , Anders, A. and Anders, R. (2015) Schur Complement Computations in Intel® Math Kernel Library PARDISO. Applied Mathematics, 6, 304-311. doi: 10.4236/am.2015.62028.
Kalinkin, A. , Anders, A. and Anders, R. (2015) Schur Complement Computations in Intel® Math Kernel Library PARDISO. Applied Mathematics, 6, 304-311. doi: 10.4236/am.2015.62028.
References
[1] Zhang, F. (2005) The Schur Complement and Its Applications, Series: Numerical Methods and Algorithms, Vol. 4, Springer, USA. [2] Haynsworth, E.V. (1968) On the Schur Complement. Basel Mathematical Notes, BMN 20, 17 p. [3] Schur, I. (1986) On Power Series Which Are Bounded in the Interior of the Unit Circle, Series: Operator Theory: Advances and Applications, Birkhauser, Basel, Vol. 18, 31-59. [4] Intel Math Kernel Library
http://software.intel.com/en-us/intel-mkl [5] Aleksandrov, V. and Samuel, H. (2010) The Schur Complement Method and Solution of Large-Scale Geophysical Problems. Bayerisches Geoinstitut (BGI).
http://karel.troja.mff.cuni.cz/documents/2010-ML-Aleksandrov.pdf [6] Yamazaki, I. and Li, S.X. (2010) On Techniques to Improve Robustness and Scalability of the Schur Complement Method. 9th International Conference on High Performance Computing for Computational Science, Berkeley, 22-25 June 2010, 14 p. [7] MUMPS
http://mumps.enseeiht.fr/ [8] Duff, I.S. and Reid, J.K. (1983) The Multifrontal Solution of Indefinite Sparse Symmetric Linear. ACM Transactions on Mathematical Software, 9, 302-325.
http://dx.doi.org/10.1145/356044.356047 [9] Liu, J.W.H. (1992) The Multifrontal Method for Sparse Matrix Solution: Theory and Practice. SIAM Review, 34, 82- 109.
http://dx.doi.org/10.1137/1034004 [10] Karypis, G. and Kumar, V. (1996) Parallel Multilevel Graph Partitioning. Proceedings of the 10th International Parallel Processing Symposium, Honolulu, 15-19 April 1996, 314-319. [11] Karypis, G. and Kumar, V. (1998) A Parallel Algorithm for Multilevel Graph Partitioning and Sparse Matrix Ordering. Journal of Parallel and Distributed Computing, 48, 71-85
http://dx.doi.org/10.1006/jpdc.1997.1403 [12] Amestoy, P.R., Duff, I.S., Pralet, S. and Voemel, C. (2003) Adapting a Parallel Sparse Direct Solver to Architectures with Clusters of SMPs. Parallel Computing, 29, 1645-1668.
http://dx.doi.org/10.1016/j.parco.2003.05.010 [13] Amestoy, P.R., Duff, I.S. and Vomel, C. (2005) Task Scheduling in an Asynchronous Distributed Memory Multifrontal Solver. SIAM Journal on Matrix Analysis and Applications, 26, 544-565.
http://dx.doi.org/10.1137/S0895479802419877 [14] Amestoy, P.R., Guermouche, A., L’Excellent, J.-Y. and Pralet, S. (2006) Hybrid Scheduling for the Parallel Solution of Linear Systems. Parallel Computing, 32, 136-156.
http://dx.doi.org/10.1016/j.parco.2005.07.004 [15] Amestoy, P.R. and Duff, I.S. (1993) Memory Management Issues in Sparse Multifrontal Methods on Multiprocessors. International Journal of High Performance Computing Applications, 7, 64-82.
http://dx.doi.org/10.1177/109434209300700105 [16] Amestoy, P.R., Duff, I.S., L’Excellent, J.-Y. and Koster, J. (2001) A Fully Asynchronous Multifrontal Solver Using Distributed Dynamic Scheduling. SIAM Journal on Matrix Analysis and Applications, 23, 15-41.
http://dx.doi.org/10.1137/S0895479899358194 [17] Kalinkin, A. (2013) Intel Direct Sparse Solver for Clusters, a Research Project for Solving Large Sparse Systems of Linear Algebraic Equations on Clusters. Sparse Days Meeting 2013 at CERFACS, Toulouse, 17-18 June 2013.
http://www.cerfacs.fr/6-27085-Sparse-Days-2013.php [18] Kalinkin, A. (2013) Sparse Linear Algebra Support in Intel Math Kernel Library. Sparse Linear Algebra Solvers for High Performance Computing Workshop, Scarman House, University of Warwick, 8-9 July 2013.
http://www2.warwick.ac.uk/fac/sci/dcs/research/pcav/linear solvers/programme/ [19] Kalinkin, A. and Arturov, K. (2013) Asynchronous Approach to Memory Management in Sparse Multifrontal Methods on Multiprocessors. Applied Mathematics, 4, 33-39.
http://dx.doi.org/10.4236/am.2013.412A004 [20] Kalinkin, A., Anders, A. and Anders, R. (2014) Intelreg; Math Kernel Library Parallel Direct Sparse Solver for Clusters. EAGE Workshop on High Performance Computing for Upstream, Chania, Crete, 7-10 September 2014.
http://www.eage.org/events/index.php?evp=12682&ActiveMenu=2&Opendivs=s3
http://dx.doi.org/10.3997/2214-4609.20141926 [21] Davis, T.A. and Hu, Y. (2011) The University of Florida Sparse Matrix Collection. ACM Transactions on Mathematical Software, 38, 1:1-1:25.
http://www.cise.ufl.edu/research/sparse/matrices
[1] Zhang, F. (2005) The Schur Complement and Its Applications, Series: Numerical Methods and Algorithms, Vol. 4, Springer, USA. [2] Haynsworth, E.V. (1968) On the Schur Complement. Basel Mathematical Notes, BMN 20, 17 p. [3] Schur, I. (1986) On Power Series Which Are Bounded in the Interior of the Unit Circle, Series: Operator Theory: Advances and Applications, Birkhauser, Basel, Vol. 18, 31-59. [4] Intel Math Kernel Library
http://software.intel.com/en-us/intel-mkl [5] Aleksandrov, V. and Samuel, H. (2010) The Schur Complement Method and Solution of Large-Scale Geophysical Problems. Bayerisches Geoinstitut (BGI).
http://karel.troja.mff.cuni.cz/documents/2010-ML-Aleksandrov.pdf [6] Yamazaki, I. and Li, S.X. (2010) On Techniques to Improve Robustness and Scalability of the Schur Complement Method. 9th International Conference on High Performance Computing for Computational Science, Berkeley, 22-25 June 2010, 14 p. [7] MUMPS
http://mumps.enseeiht.fr/ [8] Duff, I.S. and Reid, J.K. (1983) The Multifrontal Solution of Indefinite Sparse Symmetric Linear. ACM Transactions on Mathematical Software, 9, 302-325.
http://dx.doi.org/10.1145/356044.356047 [9] Liu, J.W.H. (1992) The Multifrontal Method for Sparse Matrix Solution: Theory and Practice. SIAM Review, 34, 82- 109.
http://dx.doi.org/10.1137/1034004 [10] Karypis, G. and Kumar, V. (1996) Parallel Multilevel Graph Partitioning. Proceedings of the 10th International Parallel Processing Symposium, Honolulu, 15-19 April 1996, 314-319. [11] Karypis, G. and Kumar, V. (1998) A Parallel Algorithm for Multilevel Graph Partitioning and Sparse Matrix Ordering. Journal of Parallel and Distributed Computing, 48, 71-85
http://dx.doi.org/10.1006/jpdc.1997.1403 [12] Amestoy, P.R., Duff, I.S., Pralet, S. and Voemel, C. (2003) Adapting a Parallel Sparse Direct Solver to Architectures with Clusters of SMPs. Parallel Computing, 29, 1645-1668.
http://dx.doi.org/10.1016/j.parco.2003.05.010 [13] Amestoy, P.R., Duff, I.S. and Vomel, C. (2005) Task Scheduling in an Asynchronous Distributed Memory Multifrontal Solver. SIAM Journal on Matrix Analysis and Applications, 26, 544-565.
http://dx.doi.org/10.1137/S0895479802419877 [14] Amestoy, P.R., Guermouche, A., L’Excellent, J.-Y. and Pralet, S. (2006) Hybrid Scheduling for the Parallel Solution of Linear Systems. Parallel Computing, 32, 136-156.
http://dx.doi.org/10.1016/j.parco.2005.07.004 [15] Amestoy, P.R. and Duff, I.S. (1993) Memory Management Issues in Sparse Multifrontal Methods on Multiprocessors. International Journal of High Performance Computing Applications, 7, 64-82.
http://dx.doi.org/10.1177/109434209300700105 [16] Amestoy, P.R., Duff, I.S., L’Excellent, J.-Y. and Koster, J. (2001) A Fully Asynchronous Multifrontal Solver Using Distributed Dynamic Scheduling. SIAM Journal on Matrix Analysis and Applications, 23, 15-41.
http://dx.doi.org/10.1137/S0895479899358194 [17] Kalinkin, A. (2013) Intel Direct Sparse Solver for Clusters, a Research Project for Solving Large Sparse Systems of Linear Algebraic Equations on Clusters. Sparse Days Meeting 2013 at CERFACS, Toulouse, 17-18 June 2013.
http://www.cerfacs.fr/6-27085-Sparse-Days-2013.php [18] Kalinkin, A. (2013) Sparse Linear Algebra Support in Intel Math Kernel Library. Sparse Linear Algebra Solvers for High Performance Computing Workshop, Scarman House, University of Warwick, 8-9 July 2013.
http://www2.warwick.ac.uk/fac/sci/dcs/research/pcav/linear solvers/programme/ [19] Kalinkin, A. and Arturov, K. (2013) Asynchronous Approach to Memory Management in Sparse Multifrontal Methods on Multiprocessors. Applied Mathematics, 4, 33-39.
http://dx.doi.org/10.4236/am.2013.412A004 [20] Kalinkin, A., Anders, A. and Anders, R. (2014) Intelreg; Math Kernel Library Parallel Direct Sparse Solver for Clusters. EAGE Workshop on High Performance Computing for Upstream, Chania, Crete, 7-10 September 2014.
http://www.eage.org/events/index.php?evp=12682&ActiveMenu=2&Opendivs=s3
http://dx.doi.org/10.3997/2214-4609.20141926 [21] Davis, T.A. and Hu, Y. (2011) The University of Florida Sparse Matrix Collection. ACM Transactions on Mathematical Software, 38, 1:1-1:25.
http://www.cise.ufl.edu/research/sparse/matrices