3
$\begingroup$

I am designing an algorithm that solves a linear system using the QR factorization, and the matrices I am dealing with are sparse and very large ($6000 \times 6000$). In order to improve the efficiency of the algorithm, I am trying to exploit the sparsity of the matrix by finding its bandwidth, but I have to run through the matrix a lot of times to find it, and it is taking too long.

The main idea I am using to find the bandwidth is:

  • for each row, find the start(row) and end(row): these are the intervals in which the elements are different of $0$;

  • to find start(row): iterate from the beginning of the row until the element is not $0$;

  • to find end(row): iterate from the end of the row until the element is not $0$;

The problem is that I am running through many unnecessary $0$'s, but I can not figure out how to avoid this and guarantee a solid result. Thanks.

Improve this question
$\endgroup$
  • $\begingroup$ Are you acquainted with the Cuthill–McKee algorithm? $\endgroup$ – Rodrigo de Azevedo May 10 '17 at 9:36
  • $\begingroup$ Start in the bottom-left corner, and examine successively higher `\`-shaped diagonals (the first contains only the bottom-left corner itself, the second contains 2 elements, etc.) Stop as soon as you hit a nonzero element. Then do the same, starting at the top-right corner and moving down. This will be slow if the matrix has small bandwidth, but if you don't have any other information besides the matrix itself, nothing can possibly be faster on all inputs. $\endgroup$ – j_random_hacker May 13 '17 at 12:16
  • $\begingroup$ how does calculating bandwidth help you "exploit the sparsity of the matrix"? anyway there is a lot of existing research/ knowledge/ detail into efficient linear solving incl wrt sparse matrices and its unlikely to develop new methods that are any much better than slighly incremental vs specialized data... suggest further analysis in Computer Science Chat. there may be known methods to "find bandwidth of sparse matrix efficiently" but then its not even clear if this is your real/ main problem (it sounds like a possible "sideline" ie main problem is linear solving sparse matrices)... $\endgroup$ – vzn May 13 '17 at 16:18
  • 1
    $\begingroup$ @RodrigodeAzevedo I think you have misunderstood this question. The question asks to calculate the bandwidth for a given matrix (the steps described do precisely this), instead of the minimum bandwith (which the Cuthill–McKee algorithm gives). This also means the original 'explore' makes more sense than the 'exploit' you edited in. $\endgroup$ – Discrete lizard♦ May 13 '17 at 16:53
  • 1
    $\begingroup$ If the main problem is too many 0's in the matrix, a sparse matrix representation would help to iterate over only the non-zero elements. However, if the steps you describe are already too costly, creating this representation from a normal matrix representation would likely be too costly as well. So, whether there are more efficient methods would depend on how the linear system is generated. Could you clarify how the linear system is created? $\endgroup$ – Discrete lizard♦ May 13 '17 at 17:01
1
+50
$\begingroup$

As a sparse matrix is mostly made of zeros. Using a 2-dimensional array for all elements will be an inefficient way to represent such data as more than half of the array will be zeroes which is the reason for the increased time cost for finding bandwidth in your case.

In your case if you have a matrix $M$ of size $n * m$ then you'll be using a 2 dimensional array of size $n*m$. However it is not necessary to do so

A more efficient way will be to represent only the non zero elements using a 2 dimensional array with only three columns.e.g.

------------------------
 R    |   C    | V
------------------------
 0    |  0     |  1
------------------------
 0    |  3     |  4
------------------------
 1    |  5     |  11
------------------------
 .    |  .     |  .
------------------------
 .    |  .     |  .
------------------------
 .    |  .     |  .

Where R is the row of the nonzero element,C is its column and V is its value in a given matrix.

In this way if you have $t$ nonzero elements in the Matrix then you need to access only $3*t$ elements in the above 2-dimensional array.

Now you can find the maximum and minimum values of C for any row R and can calculate their difference.

The largest difference you'll come across will be the bandwidth.I hope it makes sense.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.