Skip to main content

Sparse Matrix


Matrix with a relatively high proportion of zero entries are called sparse matrix. There are three types of sparse matrices:

  • LOWER TRIANGULAR MATRIX:

    In the lower triangular matrix the entries above the matrix diagonal are zero. Here the non-zero entries can occur only on the diagonal or below the diagonal.

    Your browser may not support display of this image. 4 0 0 0 0

    3 2 0 0 0

    1 -1 6 0 0

    5 -2 2 3 0

    6 2 3 4 4

  • UPPER TRIANGULAR MATRIX:

    In the upper triangular matrix all the entries below the matrix diagonal are zero.

    Your browser may not support display of this image. 4 9 8 5 6

    0 2 4 9 7

    0 0 6 1 4

    0 0 0 3 2

    0 0 0 0 4

  • TRIDIAGONAL MATRIX:

    In the tridiagonal matrix the non-zero entries can occur only on the diagonal or immediately above or below the diagonal.

    Your browser may not support display of this image. 4 -2 0 0 0

    3 2 3 0 0

    0 -1 6 3 0

    0 0 2 3 1

    0 0 0 4 4

    These incident and adjacency matrix represenation of graphs will usually results in these type of sparse matrices.

    If we use the conventional 2D array representation to store the above matrix there will be wastage of storage spaces. So an alternative representation is needed for sparse matrix. It is possible to store information regarding non-zero elements.

    Information about the non-zero elements have three parts.

  • Integer representing its row.
  • Integer representing its column
  • The data associated with the element.

That is, we can store the matrix as a list of three tuples of the form (i, j, value)

    E.g. consider the matrix

    Your browser may not support display of this image. 4 0 0 0 0

    3 2 0 0 0

    -1 1 6 0 0

    5 -2 2 3 0

    6 2 3 4 4

    The repesetation is as follows

Row column value

A[0 ] 5 5 15

A[1] 0 0 4

A[2] 1 0 3

A[3] 1 1 2

A[4] 2 0 -1

A[5] 2 1 1

A[6] 2 2 6

A[7] 3 0 5

A[8] 3 1 -2

A[9] 3 2 2

A[10] 3 3 3

A[11] 4 0 6

A[12] 4 1 2

A[13] 4 2 3

A[14] 4 3 4

A[15] 4 4 4

The elements A [0][ 1] and A [0][2] contains the total number of rows and columns and A[0][3] contains the total number of non-zero terms.

Comments

Popular posts from this blog

KTU-FOSS LAB Solutions

Write shell scripts to show the following  ( you can write menu driven programs)
 Currently logged user and his logname ( logname)  Your current shell ( echo $SHELL)  Your home directory ( echo $HOME)  Your operating system type (echo $OSTYPE)  Your current path setting ( echo $PATH)  Your current working directory ( echo $PWD )  Show Currently logged  users ( w or who -H)      Show only the user name of logged users in the host ( users)      Details of last login ( last cek....where cek is the user id )  About your OS and version, release number, kernel version ( uname -a or  cat  /proc/version)  Show all available shells ( cat /etc/shells )  Show mouse settings (cat  /sys/class/input/mouse*/device/name )  Show computer CPU information       CPU details      ( cat /proc/cpuinfo | more )       Show information on  CPU architecture ( lscpu)       Number of Processor core ( nproc)  Show memory information       Memory details ( cat /proc/meminfo | more )       Display file system disk usage ( d…

Important Directories and Files

Important Directories
/bin                            holds the “essential” Linux commands and utilities /boot                          holds files required for boot process (kernel, vmlinuz, grub) /dev                            holds device files (hard drive, USB, CD-ROM, etc.) /etc                             holds system configuration files /etc/init.d                    holds scripts to start/stop network services /etc/rc.d                     holds system startup/shutdown scripts /etc/X11                      holds configuration files for X-windows /home                        holds user home directories (except for the root account) /lib                               holds system/shared library files /lost+found                holds files restored after system crash /mnt                            used as temporary mount point for CD-ROM, floppy, etc. /opt                              typically where large software applications are installed /proc                           holds kerne…

ER Diagrams to Table

REDUCING E-R DIAGRAM TO TABLE - A database which conforms to an E R diagram can be represented by collection of tables .For each entity set and for each relationship set in the database, we will create unique tables, which is assigned the name of the corresponding entity set or relationship sets . Each table has a no. of columns which have unique names. Each row in the table corresponds to an entity or a relationship.

REPRESENTATION OF STRONG ENTITY SET -Let E be a strong entity set with descriptive attributes a1, a2....aN . We represent this entity by table called E with N distinct columns, each of which corresponds to one of the attributes of E.

REPRESENTATION OF RELATIONSHIP SET - Let R be a relation ship set involving entity set E1,E2....En Let attribute(R) consists of 'm' attributes We can represent this relation ship set by a table called R with m distinct columns, each of which corresponds to one of the attributes in attribute (R) plus the primary key of E1..En.

REPRESENTI…