8 More Transform and Conquer Problems

S. Sridhar

This module 18 focuses on an important design paradigm called Transform and Conquer. This module discusses problems related to matrix decomposition, matrix inverse and matrix determinant. The learning objectives of this module are

 

•       To explain Matrix Decomposition

•       To explain Gaussian Elimination for matrix decomposition

•       To explain Crout Procedure for matrix decomposition

•       To explain matrix inverse and Determinant of matrix using transform and conquer

 

Transform and Conquer Design paradigm

 

Transform and conquer is a design paradigm where a given problem is transformed to another domain. This can be done for familiarity of simplicity [2,3]. The problem is solved in the new domain. Then, the solutions are converted back to the original domain. In short, transform and conquer proposes two stage solution

 

1.       First stage involves the transformation to another problem that is more amenable for solution

2.       Second stage involves solving the new problem where the transformed new problem is solved. Then the solutions are converted back to the original problem.

 

Variations of Transform and Conquer

 

Three variants of transform and conquer are as follows:

 

–  Instance Simplification

–  Representation Change

–  Problem Reduction

 

Instance simplification is one variant where the problem transformed to the same problem of simpler or convenient instance.

     LU decomposition is an example of instance simplification. In LU decomposition, the given matrix is split or decomposed to two matrices L and U. Why? This splitting helps to solve a set of simultaneous equations faster. In other words, LU Decomposition is another method to solve a set of simultaneous linear equations effectively. Thus, the non-singular matrix [A], can be written as [A] = [L][U], Here,

 

[L] = lower triangular matrix

 

[U] = upper triangular matrix

 

Let the set of simultaneous equations are represented as follows as discussed in the last module in matrix form as:

Ax = b

 

Substituting A = LU gives,

 

LUx = b

 

First, let y = Ux. So by keeping

 

Ly = b

One can solve for y.  Then, by solving Ux = y ,

 

One can solve for the unknown x in the set of linear equations. By matrix decomposition, the process of computing becomes faster.

 

Gaussian Elimination method for LU Decomposition

 

Gaussian elimination method was discussed in the last module. It can be noted that the matrix U is the same as the coefficient matrix at the end of the forward elimination step and the matrix L is obtained using the multipliers that were used in the forward elimination process.

 

One has to know the limitations of LU decomposition. They are listed below [1] :

 

1.      Not all the matrices have LU decomposition

2.      Rows or columns can be swapped to make LU decomposition feasible

3.      LU decomposition is guaranteed if the leading submatrices have non-zero determinants. to make LU decomposition. A matrix Ak is called a leading submatrix of matrix A, if it is k x k matrix whose elements are top k rows and k left-most columns.

The following Example 1 illustrates the Gaussian elimination method for solving a set of equations and to find LU decomposition.

 

The lower-triangular matrix is obtained L is made up of 1’s in the diagonal and the multipliers used for row reduction in the Gaussian elimination. It can be observed that the multipliers used in the above Gaussian elimination process is used to give matrix L

 

 

 

References:

 

1.      S.Sridhar , Design and Analysis of Algorithms , Oxford University Press, 2014.

  1. A.Levitin, Introduction to the Design and Analysis of Algorithms, Pearson Education, New Delhi, 2012.
  2. T.H.Cormen, C.E. Leiserson, and R.L. Rivest, Introduction to Algorithms, MIT Press, Cambridge, MA 1992.