Schur Complement Computations in Intel® Math Kernel Library PARDISO
- 1 Intel Corporation, Software and Services Group (SSG), Novosibirsk, Russia
- 2 Intel Corporation, Software and Services Group (SSG), Novosibirsk, Russia
- 3 Intel Corporation, Software and Services Group (SSG), Novosibirsk, Russia
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.
- Zhang, F. (2005) The Schur Complement and Its Applications, Series: Numerical Methods and Algorithms, Vol. 4, Springer, USA.
- Haynsworth, E.V. (1968) On the Schur Complement. Basel Mathematical Notes, BMN 20, 17 p.
- 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.
- Intel Math Kernel Library http://software.intel.com/en-us/intel-mkl
- 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
- 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.
- MUMPS http://mumps.enseeiht.fr/
- 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
- 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
- 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.
- 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
- 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
- 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
- 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