LUP Decomposition in Matrices

LUP Decomposition in Matrices is a similar method as LU Decomposition, but the difference is that LUP decomposition includes a permutation matrix.

The LUP decomposition is used in numerical analysis to solve systems of linear equations, and also in the solution of linear systems of equations, the calculation of the determinant of a matrix, and the calculation of the inverse of a matrix.

What is LUP Decomposition in Data Structures?

In data structures, LUP decomposition means splitting a square matrix A into three smaller matrices:

• L – Lower triangular matrix: A square matrix in which all the elements above the main diagonal are zero.
• U – Upper triangular matrix: A square matrix in which all the elements below the main diagonal are zero.
• P – Permutation matrix: A square matrix that represents the permutation of the rows of the identity matrix.

Why LUP Decomposition?

LUP decomposition is preferred over LU decomposition because it includes a permutation matrix P. The permutation matrix helps in reducing the error in the calculation of the determinant and inverse of a matrix.

LUP Decomposition Algorithm

The LUP decomposition algorithm is as follows:

1. Read the matrix A
2. Set the size of the matrix A as n x n
3. Initialize the matrices L, U, and P as n x n matrices
4. Set the diagonal elements of L as 1 and the other elements as 0
5. Set the elements of U as the elements of A
6. Set the elements of P as the elements of the identity matrix
7. For k = 1 to n-1
8. Find the pivot element in the k-th column
9. Swap the rows of U, L, and P according to the pivot element
10. For i = k+1 to n
11. Set L[i][k] = U[i][k]/U[k][k]
12. For j = k to n
13. Set U[i][j] = U[i][j] - L[i][k]*U[k][j]
14. Display the matrices L, U, and P

LUP Decomposition Code Example

Let’s consider a 3×3 matrix A. We will perform LUP decomposition on this matrix. Following is the example, using Java, CPP, C and Python programming languages.

CC++Java“”Python

#include <stdio.h>#include <stdlib.h>#include <math.h>voidLUPDecomposition(int n,float A[n][n],float L[n][n],float U[n][n],float P[n][n]){int i, j, k;for(i =0; i < n; i++){for(j =0; j < n; j++){
         L[i][j]=(i == j)?1:0;
         U[i][j]= A[i][j];
         P[i][j]=(i == j)?1:0;}}for(k =0; k < n -1; k++){float max =0;int pivot = k;for(i = k; i < n; i++){if(fabs(U[i][k])> max){
            max =fabs(U[i][k]);
            pivot = i;}}if(pivot != k){for(j =0; j < n; j++){float temp = U[k][j];
            U[k][j]= U[pivot][j];
            U[pivot][j]= temp;

            temp = P[k][j];
            P[k][j]= P[pivot][j];
            P[pivot][j]= temp;if(j < k){
               temp = L[k][j];
               L[k][j]= L[pivot][j];
               L[pivot][j]= temp;}}}if(U[k][k]==0){printf("Error: Singular matrix detected.\n");exit(1);}for(i = k +1; i < n; i++){
         L[i][k]= U[i][k]/ U[k][k];for(j = k; j < n; j++){
            U[i][j]-= L[i][k]* U[k][j];}}}}voidprintMatrix(int n,float M[n][n],constchar*name){printf("\n%s Matrix:\n", name);for(int i =0; i < n; i++){for(int j =0; j < n; j++){printf("%8.3f ", M[i][j]);}printf("\n");}}intmain(){int n =3;float A[3][3]={{2,-1,-2},{-4,6,3},{-4,-2,8}};float L[3][3], U[3][3], P[3][3];LUPDecomposition(n, A, L, U, P);printMatrix(n, L,"L");printMatrix(n, U,"U");printMatrix(n, P,"P");return0;}

Output

The output produced is as follows −

L Matrix:
   1.000    0.000    0.000 
   1.000    1.000    0.000 
  -0.500   -0.250    1.000 

U Matrix:
  -4.000    6.000    3.000 
   0.000   -8.000    5.000 
   0.000    0.000    0.750 

P Matrix:
   0.000    1.000    0.000 
   0.000    0.000    1.000 
   1.000    0.000    0.000  

Applications of LUP Decomposition

LUP decomposition is used in various applications in computer science, such as:

• Calculating the determinant of a matrix
• Calculating the inverse of a matrix
• Solving systems of linear equations
• Implementing numerical algorithms
• Performing matrix operations

Conclusion

In this chapter, we learned about LUP decomposition in matrices. LUP decomposition is a method used to solve systems of linear equations, calculate the determinant of a matrix, and calculate the inverse of a matrix.

LUP decomposition includes three matrices: L (lower triangular matrix), U (upper triangular matrix), and P (permutation matrix). LUP decomposition is preferred over LU decomposition because it includes a permutation matrix that helps in reducing errors in the calculation of the determinant and inverse of a matrix.