Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

What is LU factorization?

Aqsa Amir

Grokking Modern System Design Interview for Engineers & Managers

Ace your System Design Interview and take your career to the next level. Learn to handle the design of applications like Netflix, Quora, Facebook, Uber, and many more in a 45-min interview. Learn the RESHADED framework for architecting web-scale applications by determining requirements, constraints, and assumptions before diving into a step-by-step design process.

Overview

Breaking the original matrix, AA , into an upper triangular matrix, UU, and a lower triangular matrix, LL, is known as LU factorization. The product, LULUshould always equal the original matrix, AA.

The equation can be represented in the matrices as follows:

Example

The following example depicts the result of LU factorization.

Method

Let's find the LU factorization of the following example:

Where AA is as follows:

Step 1

Find the upper triangular matrix UU using the Gaussian elimination method.

Note: In the Gaussian elimination method,

1. All rows containing zeros must be at the bottom of the matrix.

2. The first non-zero entry of every row should be on the right side of the first non-zero entry of the previous row.

Perform the following operation:

The resulting matrix obtained is as follows:

Now, perform another operation to achieve the upper triangular matrix, UU:

The resulting matrix obtained is as follows:

Step 2

Method 1

Calculate the lower triangular matrix using the equation A=LUA = LU, where LL is set as an arbitrary matrix and its values will be calculated.

Method 2

Otherwise, LL can be calculated by equating the arbitrary elements in LL to the multiplier coefficients that made those respective elements zero.

We will use the second method to clarify it further.

  • O1O_{1} made l31l_{31} zero, hence, we will replace it with the multiplier element 2.
  • O2O_{2} made l32l_{32} zero, hence, we will replace it with the multiplier element -4.
  • l21l_{21} was already zero so it will remain the same.

The resulting matrix is as follows:

Step 3

  • Given that AX=CAX = C, we will replace AA with LULU since A=LUA=LU.
  • Now in the equation LUX=CLUX=C, replace UXUX with YY.
  • Solve the system of linear equations using the two equations LY=CLY = C and UX=YUX=Y.

Solving the first equation, LY=CLY = C.

The solution matrix, YY, is obtained as follows:

Solving the second equation, UX=YUX=Y.

The solution matrix, XX , is obtained as follows:

Q

Solve the following systems of equations:

6x1x_{1} + 18x2x_{2} + 3x3x_{3} = 3

2x1x_{1} + 12x2x_{2} + x3x_{3} = 19

4x1x_{1} + 15x2x_{2} + 3x3x_{3} = 0

A)

{3, -9, 12}

B)

{1, -3, 7}

C)

{-3, 3, -11}

D)

{-2, -5, 13}

Applications

LU factorization is used in numerous applications such as:

  • Finding the inverse of a matrix
  • Finding the determinant of a matrix
  • Finding current in a circuit
  • Solving discrete dynamical system problems

RELATED TAGS

CONTRIBUTOR

Aqsa Amir
Copyright ©2022 Educative, Inc. All rights reserved

Grokking Modern System Design Interview for Engineers & Managers

Ace your System Design Interview and take your career to the next level. Learn to handle the design of applications like Netflix, Quora, Facebook, Uber, and many more in a 45-min interview. Learn the RESHADED framework for architecting web-scale applications by determining requirements, constraints, and assumptions before diving into a step-by-step design process.

Keep Exploring