topic DSS/Pardiso is used for in Intel® oneAPI Math Kernel Library

Bandwidth of matrix

Twoot — Mon, 28 May 2018 10:10:51 GMT

Hi,

I'm using the DSS interface for solving a large linear set of equations. In order to do some analytical work on the performance of my implementation I would like to know the bandwidth of the system matrix. Is there a way to determine the bandwidth of the system matrix from the internal data structure? I also don't see how to use the column indices of the non-zero entries to calculate the bandwidth, as these are the indices of the un-reordered system matrix.

Furthermore, is there a way of computing the condition number of the internal system matrix?

Any help would be greatly appreciated. Many thanks in advance.

Regards,

Wouter

DSS/Pardiso is used for

mecej4 — Tue, 29 May 2018 10:59:00 GMT

DSS/Pardiso is used for matrices whose sparse-pattern is more general than that of a banded matrix. For your purposes, it may be sufficient to compute the bandwidth of the input matrix before pivoting and other operations are performed. The following code can do this (assuming that the row index and columns arrays ia and ja contain one-based indices):

bw = 0
do i  = 1, n
   k  = ia(i)
   jl = ja(k)     ! first non-zero column in row i
   k  = ia(i+1)-1
   jm = ja(k)     ! last non-zero column in row i
   bw = max(bw, jm-jl+1)
end do
print *,'Bandwidth = ',bw

Thanks for your reply mecej4.

Twoot — Tue, 29 May 2018 11:28:57 GMT

Thanks for your reply mecej4.

I already know the bandwidth of the input matrix. However, what I am interested in is the bandwidth of the matrix after reordering,which will of course be smaller than that of the input matrix.

With dss_reorder I obtain the vector perm which defines the (row- and column-) permutations of the input matrix. Is there a way to efficiently determine the bandwidth of the reordered matrix using this vector?

Regards,

Wouter

Reordering algorithms of the

mecej4 — Tue, 29 May 2018 12:16:13 GMT

Reordering algorithms of the types used in DSS seek to reduce the "fill-in" rather than to reduce the bandwidth. Therefore, it should be cause for little surprise if the bandwidth (the sum of the bandwidths of the L and U factors) is not reduced by reordering (we know that it cannot increase).

Sorry, I do not see why you consider bandwidth to be an important measure of sparseness, unless it is the case that (w . N) is of the same order of magnitude as N_nz, with w = bandwidth, N = rows in matrix.

I do not consider the

Twoot — Tue, 29 May 2018 12:25:00 GMT

I do not consider the bandwidth to be a measure of sparseness. In my problem I use the same LU factorisation of my input matrix to solve for several right-hand side vectors. Since the solution (backward/forward substitution) procedure scales with the bandwidth of the factors L and U, and these have the same lower- and upper bandwidth as the reordered matrix, I want to know the bandwidth of the reordered matrix such that I can make an estimate on the flopcount of the solve step. Such an estimate would be useful as a comparison with another (iterative) solution method.