{"id":97,"date":"2018-07-19T05:33:39","date_gmt":"2018-07-19T05:33:39","guid":{"rendered":"http:\/\/csp5.epgpbooks.inflibnet.ac.in\/?post_type=chapter&p=97"},"modified":"2018-07-19T08:45:11","modified_gmt":"2018-07-19T08:45:11","slug":"more-transform-and-conquer-problems","status":"publish","type":"chapter","link":"https:\/\/ebooks.inflibnet.ac.in\/csp5\/chapter\/more-transform-and-conquer-problems\/","title":{"rendered":"More Transform and Conquer Problems"},"content":{"raw":"
\r\n

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<\/p>\r\n \r\n\r\n\u2022\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 To explain Matrix Decomposition\r\n\r\n\u2022\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 To explain Gaussian Elimination for matrix decomposition\r\n\r\n\u2022\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 To explain Crout Procedure for matrix decomposition\r\n\r\n\u2022\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 To explain matrix inverse and Determinant of matrix using transform and conquer\r\n\r\n \r\n\r\nTransform and Conquer Design paradigm<\/strong>\r\n\r\n \r\n

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<\/p>\r\n \r\n\r\n1.\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 First stage involves the transformation to another problem that is more amenable for solution\r\n\r\n2.\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 Second stage involves solving the new problem where the transformed new problem is solved. Then the solutions are converted back to the original problem.\r\n\r\n \r\n\r\nVariations of Transform and Conquer<\/strong>\r\n\r\n \r\n\r\nThree variants of transform and conquer are as follows:\r\n\r\n \r\n\r\n\u2013\u00a0 Instance Simplification\r\n\r\n\u2013\u00a0 Representation Change\r\n\r\n\u2013\u00a0 Problem Reduction\r\n\r\n \r\n\r\nInstance simplification <\/strong>is one variant where the problem transformed to the same problem of simpler or convenient instance.\r\n\r\n<\/div>\r\n

\r\n

\u00a0 \u00a0 \u00a0LU 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<\/em>], can be written as [A<\/em>] = [L<\/em>][U<\/em>], Here,<\/p>\r\n \r\n\r\n[L<\/em>] = lower triangular matrix\r\n\r\n \r\n\r\n[U<\/em>] = upper triangular matrix\r\n\r\n \r\n\r\nLet the set of simultaneous equations are represented as follows as discussed in the last module in matrix form as:\r\n\r\nAx <\/em>= b<\/em>\r\n\r\n \r\n\r\nSubstituting A = LU gives,\r\n\r\n \r\n\r\nLUx <\/em>= b<\/em>\r\n\r\n \r\n\r\nFirst, let y = Ux. So by keeping\r\n\r\n \r\n\r\nLy <\/em>= b<\/em>\r\n\r\nOne can solve for y.\u00a0 Then, by solving Ux<\/em> = y<\/em> ,\r\n\r\n \r\n\r\nOne can solve for the unknown x in the set of linear equations. By matrix decomposition, the process of computing becomes faster.\r\n\r\n \r\n\r\nGaussian Elimination method for LU Decomposition<\/strong>\r\n\r\n \r\n

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.<\/p>\r\n \r\n\r\nOne has to know the limitations of LU decomposition. They are listed below [1] :\r\n\r\n \r\n\r\n1.\u00a0\u00a0\u00a0\u00a0\u00a0 Not all the matrices have LU decomposition\r\n\r\n2.\u00a0\u00a0\u00a0\u00a0\u00a0 Rows or columns can be swapped to make LU decomposition feasible\r\n

3.\u00a0\u00a0\u00a0\u00a0\u00a0 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.<\/p>\r\n\r\n<\/div>\r\nThe following Example 1 illustrates the Gaussian elimination method for solving a set of equations and to find LU decomposition.\r\n\r\n \r\n\r\n\"\"\r\n

The lower-triangular matrix is obtained L<\/em> is made up of 1<\/em>\u2019s 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<\/p>\r\n \r\n\r\n\"\"\r\n\r\n\"\"\r\n\r\n\"\"\r\n\r\n\"\"\r\n\r\n\"\"\r\n\r\n \r\n\r\n\"\"\r\n\r\n\"\"\r\n\r\n \r\n\r\n\"\"\r\n\r\n\"\"\r\n\r\n\"\"\r\n

\r\n\r\nReferences:<\/strong>\r\n\r\n \r\n\r\n1.\u00a0\u00a0\u00a0\u00a0\u00a0 S.Sridhar , Design and Analysis of Algorithms , Oxford University Press, 2014.<\/em>\r\n\r\n<\/div>\r\n
    \r\n \t
  1. A.Levitin, Introduction to the Design and Analysis of Algorithms, Pearson Education, New Delhi, 2012.<\/em><\/li>\r\n \t
  2. T.H.Cormen, C.E. Leiserson, and R.L. Rivest, Introduction to Algorithms, MIT Press, Cambridge, MA 1992.<\/li>\r\n<\/ol>","rendered":"
    \n

    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<\/p>\n

     <\/p>\n

    \u2022\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 To explain Matrix Decomposition<\/p>\n

    \u2022\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 To explain Gaussian Elimination for matrix decomposition<\/p>\n

    \u2022\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 To explain Crout Procedure for matrix decomposition<\/p>\n

    \u2022\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 To explain matrix inverse and Determinant of matrix using transform and conquer<\/p>\n

     <\/p>\n

    Transform and Conquer Design paradigm<\/strong><\/p>\n

     <\/p>\n

    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<\/p>\n

     <\/p>\n

    1.\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 First stage involves the transformation to another problem that is more amenable for solution<\/p>\n

    2.\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 Second stage involves solving the new problem where the transformed new problem is solved. Then the solutions are converted back to the original problem.<\/p>\n

     <\/p>\n

    Variations of Transform and Conquer<\/strong><\/p>\n

     <\/p>\n

    Three variants of transform and conquer are as follows:<\/p>\n

     <\/p>\n

    \u2013\u00a0 Instance Simplification<\/p>\n

    \u2013\u00a0 Representation Change<\/p>\n

    \u2013\u00a0 Problem Reduction<\/p>\n

     <\/p>\n

    Instance simplification <\/strong>is one variant where the problem transformed to the same problem of simpler or convenient instance.<\/p>\n<\/div>\n

    \n

    \u00a0 \u00a0 \u00a0LU 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<\/em>], can be written as [A<\/em>] = [L<\/em>][U<\/em>], Here,<\/p>\n

     <\/p>\n

    [L<\/em>] = lower triangular matrix<\/p>\n

     <\/p>\n

    [U<\/em>] = upper triangular matrix<\/p>\n

     <\/p>\n

    Let the set of simultaneous equations are represented as follows as discussed in the last module in matrix form as:<\/p>\n

    Ax <\/em>= b<\/em><\/p>\n

     <\/p>\n

    Substituting A = LU gives,<\/p>\n

     <\/p>\n

    LUx <\/em>= b<\/em><\/p>\n

     <\/p>\n

    First, let y = Ux. So by keeping<\/p>\n

     <\/p>\n

    Ly <\/em>= b<\/em><\/p>\n

    One can solve for y.\u00a0 Then, by solving Ux<\/em> = y<\/em> ,<\/p>\n

     <\/p>\n

    One can solve for the unknown x in the set of linear equations. By matrix decomposition, the process of computing becomes faster.<\/p>\n

     <\/p>\n

    Gaussian Elimination method for LU Decomposition<\/strong><\/p>\n

     <\/p>\n

    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.<\/p>\n

     <\/p>\n

    One has to know the limitations of LU decomposition. They are listed below [1] :<\/p>\n

     <\/p>\n

    1.\u00a0\u00a0\u00a0\u00a0\u00a0 Not all the matrices have LU decomposition<\/p>\n

    2.\u00a0\u00a0\u00a0\u00a0\u00a0 Rows or columns can be swapped to make LU decomposition feasible<\/p>\n

    3.\u00a0\u00a0\u00a0\u00a0\u00a0 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.<\/p>\n<\/div>\n

    The following Example 1 illustrates the Gaussian elimination method for solving a set of equations and to find LU decomposition.<\/p>\n

     <\/p>\n

    \"\"<\/p>\n

    The lower-triangular matrix is obtained L<\/em> is made up of 1<\/em>\u2019s 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<\/p>\n

     <\/p>\n

    \"\"<\/p>\n

    \"\"<\/p>\n

    \"\"<\/p>\n

    \"\"<\/p>\n

    \"\"<\/p>\n

     <\/p>\n

    \"\"<\/p>\n

    \"\"<\/p>\n

     <\/p>\n

    \"\"<\/p>\n

    \"\"<\/p>\n

    \"\"<\/p>\n

    \n

    References:<\/strong><\/p>\n

     <\/p>\n

    1.\u00a0\u00a0\u00a0\u00a0\u00a0 S.Sridhar , Design and Analysis of Algorithms , Oxford University Press, 2014.<\/em><\/p>\n<\/div>\n

      \n
    1. A.Levitin, Introduction to the Design and Analysis of Algorithms, Pearson Education, New Delhi, 2012.<\/em><\/li>\n
    2. T.H.Cormen, C.E. Leiserson, and R.L. Rivest, Introduction to Algorithms, MIT Press, Cambridge, MA 1992.<\/li>\n<\/ol>\n","protected":false},"author":4,"menu_order":8,"template":"","meta":{"pb_show_title":"on","pb_short_title":"","pb_subtitle":"","pb_authors":["mr-s-sridhar"],"pb_section_license":""},"chapter-type":[],"contributor":[58],"license":[],"class_list":["post-97","chapter","type-chapter","status-publish","hentry","contributor-mr-s-sridhar"],"part":3,"_links":{"self":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-json\/pressbooks\/v2\/chapters\/97","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-json\/pressbooks\/v2\/chapters"}],"about":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-json\/wp\/v2\/types\/chapter"}],"author":[{"embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-json\/wp\/v2\/users\/4"}],"version-history":[{"count":5,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-json\/pressbooks\/v2\/chapters\/97\/revisions"}],"predecessor-version":[{"id":181,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-json\/pressbooks\/v2\/chapters\/97\/revisions\/181"}],"part":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-json\/pressbooks\/v2\/parts\/3"}],"metadata":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-json\/pressbooks\/v2\/chapters\/97\/metadata\/"}],"wp:attachment":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-json\/wp\/v2\/media?parent=97"}],"wp:term":[{"taxonomy":"chapter-type","embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-json\/pressbooks\/v2\/chapter-type?post=97"},{"taxonomy":"contributor","embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-json\/wp\/v2\/contributor?post=97"},{"taxonomy":"license","embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp5\/wp-json\/wp\/v2\/license?post=97"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}