Intel® MKL Support to new functionality - Schur Complement

By Gennady Fedorov,

Published:10/29/2014   Last Updated:10/29/2014

Introduction

There is a wide range of domains in which there is a need to use a Schur complement matrix or a partial solver corresponding to it. For example, in mathematical statistics the Schur complement matrix is important in computation of the probability density function, and in computational mechanics the Schur complement matrix correlates to media stiffness. Partial solving also plays an important role in Linear Algebra for efficient preconditioner implementation based on Domain Decomposition algorithms. The application area is huge and has one point in common:  sparse matrices. That’s why computation of the Schur complement and partial solving have been implemented as new functionality in the sparse solver of Intel® Math Kernel Library (Intel® MKL)  based on the Intel® MKL PARDISO* solver.   

Product Overview

Starting from Intel® MKL 11.2 update 1, the Intel MKL PARDISO solver supports additional functionality covered by one main topic: the Schur complement. Using this new functionality, you can obtain a Schur complement of selected rows/columns of initial matrix, solve the system with a Schur complement matrix using the Intel MKL PARDISO interface, and solve the lower and upper triangular subsystem that produced by matrix factorization with Schur complement calculation. This functionality can be useful for customers who use the Schur complement in other sparse solver packages.

Let A be a sparse quadratic matrix:

where Aloc ,and C are quadratic and sparse and  B1 and B2 are sparse rectangular matrices. Then, we can make the following decomposition of matrix A, which is formally an LDU decomposition:

where

 

The matrix S is the Schur complement.

To use Schur complement functionality you need to:

  1. Set iparm(36) to 1 if you want to calculate Schur complement only, and to 2 if you want to use computed factorization of initial matrix (A) during the solver step.
  2. Set the columns/rows that specify Schur complement submatrix (matrix C in the example below)
  3. Provide an array of solution vectors of n2 elements to the factorization step of the pardiso routine, where n is the size of the Schur complement matrix. On output the Schur complement is returned via this array.

The charts below compare Intel MKL PARDISO [1] with MUMPS [2] in term of time needed for calculating the Schur complement. All experiments used a computation node with two  Intel® Xeon® E5-2697 v3 processors (35M Cache, 2.60 GHz) with 64Gb RAM memory, KMP_AFFINITY set to “compact”,  MUMPS version 4.10.0, and Intel MKL 11.2 update 1.  For the Schur complement matrix we choose the last 5000 rows/columns of each matrix. The tested matrix was acquired from Matrix Florida collection [3].

[1] Intel® Math Kernel Library

[2] Mumps

[3] T. A. Davis and Y. Hu, The University of Florida Sparse Matrix Collection, ACM Transactions on Mathematical Software, Vol 38, Issue 1, 2011, pp 1:1 - 1:25.

Product and Performance Information

1

Performance varies by use, configuration and other factors. Learn more at www.Intel.com/PerformanceIndex.