Storage formats for linear equations : Band Matrix and Skyline Method

To solve a system of simultaneous linear equations of n variables, we need n equations. We can represent this system in matrix notation as AX = B and solve for the matrix X. Most commonly used method for this is the Guass Elimination method in which we perform row/column operations on the matrix A and convert it into identity matrix. This method is suitable for dense matrices. But in case of sparse matrices we have methods to make the matrix more compact and reduce the cost.

Compact storage forms:

1. For band matrices: These are matrices of the form in which non-zero elements are concentrated along the diagonal only (on the diagonal and to both of its sides) while all other elemnts are zero.

 b471ce1c410e5636458d5b6c5d28434c

 This matrix can be converted into a more compact form by elimination the zeros as shown below:

4275a4136fef6dd7e97025ad9906637f

Now the cost of solving this matrix will be less than it was earlier.

2. Skyline method: This is another method for converting matrices into compact forms.  Finite element methods generate sparse matrices that  can be ordered so that it fits into a banded matrix. There will be actually a variable band width which is called skyline. Consider the matrix below:

img121

You might now be convinced why the method was named so as the  matrix resembles  skyline of a city.

This format is specified by two arrays: values and pointers.

  1. Values:  A scalar array. For a lower triangular matrix it contains the set of elements from each row of the matrix starting from the first non-zero element to and including the diagonal element. For an upper triangular matrix it contains the set of elements from each column of the matrix starting with the first non-zero element down to and including the diagonal element. Encountered zero elements are included in the sets.
  2. Pointers: An integer array with dimension (m+1), where m is the number of rows for lower triangle (columns for the upper triangle). pointers(i) – pointers(1)+1 gives the index of element in values that is first non-zero element in row (column) i.

Hence we need to store only the non-zero elements of the matrix. Thus these storage formats not only ensure less computation but lesser storage/space requirements too.

Advertisements
Posted in GD

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s