An Efficient and Generic Algorithm for Matrix Inversion

An Efficient and Generic Algorithm for Matrix Inversion

Ahmad Farooq, Khan Hamid, Inayat Ali Shah
Copyright: © 2012 |Pages: 6
DOI: 10.4018/978-1-4666-1752-0.ch008
OnDemand:
(Individual Chapters)
Available
$37.50
Current Special Offers
No Current Special Offers
TOTAL SAVINGS: $37.50

Abstract

This work presents an improvement on the simple algorithms of matrix inversion (Farooq & Hamid, 2010). This generalized algorithm supports selection of pivot randomly in the matrix thus supporting partial and full pivoting. The freedom in pivot selection can be used in minimizing the numerical error and prioritizing the variable to find the solution first. The algorithm is more suitable for finding inverse and determinant of dense matrices. The algorithm requires a mechanism for selection of pivot (e.g., selection of absolute maximum value) in the available sub-matrix and the mechanism to get the inverse from the final resultant matrix by rearranging the rows and columns. A method for assigning the sign of the determinant is also given. The algorithm is explained through solved examples. The number of arithmetic calculations performed by the algorithm is of O () however. The efficiency and simplicity of coding remains the same as of the original algorithm.
Chapter Preview
Top

Introduction

Farooq and Hamid (2010) presented an algorithm for matrix inversion which is simpler and efficient than the exiting techniques (Saad, 2000; Chang, 2006; Mikkawy, 2006; Vajargah, 2007) and is applicable in general irrespective of the structure of the matrix. They demonstrated that manual calculations of the algorithm are straightforward and computer implementation is extremely easy. The algorithm also utilizes minimal memory. However, the algorithm is limited in the pivot selection by allowing the pivot selection diagonally only. This work presents an extension of the same algorithm by making it generic in pivot selection.

An important feature of the algorithm is the ability to allow the user to select pivot off-diagonally during inversion. The pivots can be selected from anywhere within the legal candidates of the matrix elements using the group theory of permutations and projections. The legality of the pivot is determined by the fact that during the inverse process a row or a column can be selected only once for a pivot. The selection of the pivot can be left to the choice of the user for example to go for a maximum absolute value of an element to improve numerical accuracy.

The rest of the paper is organized as follows. In section 2 we are presenting the generic algorithm. Also a 3 x 3 matrix is inversed (and determinant calculated) by the algorithm using two different sequences of pivot selection. Future work is indicated in section 3 and the paper is concluded in section 4. Finally some references are given in the end.

The Generic Algorithm of Matrix Inversion

In many situations of matrix inversions and solution of equations it may be required to go off diagonal for some or all of the pivot elements because of the following reasons:

  • a.

    The diagonal element is zero and cannot be selected as pivot. However, if we can look for elements other than the diagonal, then in non-singular matrices we will always find a non-zero element for pivot.

  • b.

    To improve the accuracy of the result we may look for particular type of values for pivots. Let say selecting the element having maximum absolute value.

  • c.

    We are interested in particular row or column to be selected first for pivot, for example, in solution of equation the value of a variable is required to be evaluated first.

However, if pivots are selected off-diagonal the resultant matrix (after the application of the inversion algorithm) will contain the elements of the inverse but intermingled. To get the inverse, the rows and the columns of the resultant matrix have to be rearranged. Similarly the off-diagonal selection of pivots will affect the sign of the determinant and correct sign have to be determined.

In the generic algorithm the selection of pivots for the inversion of matrices and the calculation of their determinants are controlled by permutation group theory. If we take a matrix of order n then for the inverse we have to select exactly n pivots. Let 978-1-4666-1752-0.ch008.m02 is the set of pivot selections. Then 978-1-4666-1752-0.ch008.m03is the set of all bijections (possible permutations of pivot selection) on the set 978-1-4666-1752-0.ch008.m04. 978-1-4666-1752-0.ch008.m05 forms a group under the binary operation of composition of functions i.e., for any bijections 978-1-4666-1752-0.ch008.m06, 978-1-4666-1752-0.ch008.m07 where 978-1-4666-1752-0.ch008.m08 is the composition. Moreover for 978-1-4666-1752-0.ch008.m09 will denote its inverse. The number of elements in the given978-1-4666-1752-0.ch008.m10are equal to978-1-4666-1752-0.ch008.m11. In this context cycles and transpositions have their usual meanings.

During the inverse calculation, pivot selection is made according to some criterion. This could be to improve accuracy, efficiency or achieve priority in the calculation of some variable. Whatever sequence, 978-1-4666-1752-0.ch008.m12 of pivot selection is made it will be on the set 978-1-4666-1752-0.ch008.m13 i.e.,978-1-4666-1752-0.ch008.m14. Therefore, the inverse of the matrix A is then obtained when we alter the rows of the resultant matrix according to γ and columns of the resultant matrix according to978-1-4666-1752-0.ch008.m15.

Note that for any 978-1-4666-1752-0.ch008.m16the number of non-identity permutations are either even or odd, accordingly the number of transpositions are even or odd. The signature of 978-1-4666-1752-0.ch008.m17 is defined as follows;

978-1-4666-1752-0.ch008.m18

The determinant of A is given by, 978-1-4666-1752-0.ch008.m19, where all 978-1-4666-1752-0.ch008.m20are the pivot elements and 978-1-4666-1752-0.ch008.m21.

Note that during this process if a pivot element is found to be zero then certainly, matrix is not invertible.

Complete Chapter List

Search this Book:
Reset