topic S = A - B * inverse(D) * C in Intel® oneAPI Math Kernel Library

MKL: Partial factorization and Schur Complement?

vahid_s_ — Fri, 13 Dec 2013 21:29:14 GMT

Hi,

I have a large symmetric sparse matrix (10000*10000) and I want to reduce the matrix to condense form of last N elements. In order to do that I need to calculate the schur complement form of the matrix:

K=[A B; C D]; S = A - B * inv(D) * C

K is symmetric sparse (10000*10000) ; S is condense form which is usually dense (N*N) N: between 1 to 1000.

My first approach was: 1. Calculate X = inv(D) * C with Pardiso sparse solver. 2. Calculate A - B * X with dgemm function of Math Kernel Library.

But I found the performance is very depend on N variable (size of condensed matrix) which in part1 is number of RHS and inpart 2 is the number of columns for X matrix.

If N = 9: Part1 time:0.06 seconds + Part2 time: 0.03 seconds = Total time around 0.09 seconds.

But if N=400: Part1 time:2 seconds + Part2 time: 3 seconds = Total time around 5 seconds.which is too much for my program!!!

Note: for both cases size of K is constant 10000*10000.

So it seems that Pardiso is not doing very well with so many RHS and dgemm matrix is not doing great with X having large number of columns.

I am using latest version of MKL. My program is in FORTRAN on Windows. Is there any way to speed up the process?

I found out that there are some libraries like MUMPS that have functions for partial factorization and calculating condense form of the sparse matrix. Is this feature available in Pardiso or Math Kernel library as well? If yes, would you please tell me the function name.

Thank you in advance for your help.

S = A - B * inverse(D) * C

vahid_s_ — Fri, 13 Dec 2013 21:44:38 GMT

S = A - B * inverse(D) * C

Matrix dimensions: S:N*N ; A: N*N ; B: N*(10000-N) ; C: transpose(B): (10000-N)*N ; D: (10000-N)*(10000-N)

Hi Vahid,

Olaf_Schenk — Sat, 14 Dec 2013 10:46:03 GMT

Hi Vahid,

This option is called a Partial Schur-Complement method and it is available in PARDISO 5.0.0 at www.pardiso-project.org.

It is described in two recent technical reports:

C. G. Petra, O. Schenk, M. Anitescu. Real-time Stochastic Optimization of Complex Energy Systems on High Performance Computers. To be submitted. ANL preprint.
C. G. Petra, Olaf Schenk, Miles Lubin, Klaus Gaertner. An augmented incomplete factorization approach for computing the Schur complement in stochastic optimization. ANL preprint.

I strongly suggest not to use DGEMM. You need to exploit the sparsity in the RHS vector

Please send me an email so that we can discuss if offline.

Regards,
Olaf Schenk

Thanks for the prompt reply,

vahid_s_ — Mon, 16 Dec 2013 20:15:47 GMT

Thanks for the prompt reply, Olaf.

I sent you a private message with some more detailed questions about new version of Pardiso.

vahid, Shur Complement

Gennady_F_Intel — Mon, 01 Dec 2014 05:07:10 GMT

vahid, Shur Complement support has been added to the latest version of MKL 11.2.update 1. Please check how it works on your side and let us know your feedback.

regards, Gennady

Could you confirm that

asd__asdqwe — Mon, 01 Dec 2014 08:33:36 GMT

Could you confirm that partial factorization is not yet available please ? Thank you.